Jelena Spasic
ABSTRACT
In this paper, we study the problem of exploiting parallelism in a hard real-time streaming application modeled as a Synchronous Data Flow (SDF) graph and scheduled on a cluster heterogeneous Multi-Processor System-on-Chip (MPSoC) platform such that energy consumption is minimized and a throughput requirement is satisfied. We propose a polynomial-time solution approach which: 1) determines a processor type for each task in an SDF graph such that the throughput constraint is met and energy consumption is minimized; 2) determines a replication factor for each task in an SDF graph such that the distribution of the workload on the same type of processors is balanced, which enables processors to run at a lower frequency, hence reducing the energy consumption. Experiments on a set of real-life streaming applications demonstrate that our approach reduces energy consumption by 66% on average while meeting the same throughput requirement when compared to related energy minimization approaches.
- H. Aydin and Q. Yang. Energy-aware partitioning for multiprocessor real-time systems. In IPDPS, 2003. Google Scholar
Digital Library
- M. Bambagini, M. Marinoni, H. Aydin, and G. Buttazzo. Energy-aware scheduling for real-time systems: A survey. ACM Trans. Embed. Comput. Syst., 15(1):7:1--7:34, 2016. Google ScholarDigital Library
- A. Bastoni, B. B. Brandenburg, and J. H. Anderson. An empirical comparison of global, partitioned, and clustered multiprocessor edf schedulers. In RTSS, 2010. Google ScholarDigital Library
- G. Bilsen et al. Cyclo-static dataflow. IEEE Trans. Signal Process., 44(2):397--408, 1996. Google ScholarDigital Library
- D. Bui and E. A. Lee. Streamorph: A case for synthesizing energy-efficient adaptive programs using high-level abstractions. In EMSOFT, 2013. Google ScholarDigital Library
- E. G. Coffman, Jr., M. R. Garey, and D. S. Johnson. Approximation algorithms for bin packing: A survey. In Approximation algorithms for NP-hard problems, pages 46--93. 1996. Google ScholarDigital Library
- A. Colin, A. Kandhalu, and R. Rajkumar. Energy-efficient allocation of real-time applications onto heterogeneous processors. In RTSCA, 2014.Google ScholarCross Ref
- M. Damavandpeyma, S. Stuijk, T. Basten, M. Geilen, and H. Corporaal. Throughput-constrained dvfs for scenario-aware dataflow graphs. In RTAS, 2013. Google ScholarDigital Library
- R. I. Davis and A. Burns. A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv., 43(4):35, 2011. Google ScholarDigital Library
- P. Greenhalgh. Big.LITTLE processing with ARM Cortex-A15 & Cortex-A7, 2011.Google Scholar
- S. Herbert and D. Marculescu. Analysis of dynamic voltage/frequency scaling in chip-multiprocessors. In ISLPED, 2007. Google ScholarDigital Library
- S. Holmbacka, E. Nogues, M. Pelcat, S. Lafond, D. Menard, and J. Lilius. Energy-awareness and performance management with parallel dataflow applications. J. of Signal Processing Systems, pages 1--16, 2015.Google Scholar
- P. Huang, O. Moreira, K. Goossens, and A. Molnos. Throughput-constrained voltage and frequency scaling for real-time heterogeneous multiprocessors. In SAC, 2013. Google ScholarDigital Library
- E. A. Lee and D. G. Messerschmitt. Synchronous data flow. Proceedings of the IEEE, 75(9):1235--1245, 1987.Google ScholarCross Ref
- W. Y. Lee. Energy-saving dvfs scheduling of multiple periodic real-time tasks on multi-core processors. In DS-RT, 2009. Google ScholarDigital Library
- D. Li and J. Wu. Energy-aware scheduling for acyclic synchronous data flows on multiprocessors. J. of Interconnection Networks, 14(4), 2013.Google Scholar
- C. Liu and J. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM, 20(1):46--61, 1973. Google ScholarDigital Library
- D. Liu, J. Spasic, G. Chen, and T. Stefanov. Energy-efficient mapping of real-time streaming applications on cluster heterogeneous mpsocs. In ESTIMedia, 2015.Google ScholarCross Ref
- T. Mitra. Heterogeneous multi-core architectures. IPSJ Trans. on System LSI Design Methodology, 8:51--62, 2015.Google ScholarCross Ref
- A. Nelson, O. Moreira, A. Molnos, S. Stuijk, B. T. Nguyen, and K. Goossens. Power minimisation for real-time dataflow applications. In DSD, 2011. Google ScholarDigital Library
- nVidia. NVIDIA Tegra X1: NVIDIA'S New Mobile Superchip, 2015.Google Scholar
- ODROID. http://www.hardkernel.com.Google Scholar
- M. Sackmann, P. Ebraert, and D. Janssens. A fast heuristic for scheduling parallel software with respect to energy and timing constraints. In IPDPSW, 2011. Google ScholarDigital Library
- Samsung. http://www.samsung.com.Google Scholar
- A. K. Singh, A. Das, and A. Kumar. Energy optimization by exploiting execution slacks in streaming applications on multiprocessor systems. In DAC, 2013. Google ScholarDigital Library
- J. Spasic, D. Liu, E. Cannella, and T. Stefanov. Improved hard real-time scheduling of csdf-modeled streaming applications. In CODES+ISSS, 2015. Google ScholarDigital Library
- J. Spasic, D. Liu, and T. Stefanov. Exploiting resource-constrained parallelism in hard real-time streaming applications. In DATE, 2016. Google ScholarDigital Library
- W. Thies and S. Amarasinghe. An empirical characterization of stream programs and its implications for language and compiler design. In PACT, 2010. Google ScholarDigital Library
- Y.-H. Wei, C.-Y. Yang, T.-W. Kuo, S.-H. Hung, and Y.-H. Chu. Energy-efficient real-time scheduling of multimedia tasks on multi-core processors. In SAC, 2010. Google ScholarDigital Library
- H. Xu, F. Kong, and Q. Deng. Energy minimizing for parallel real-time tasks based on level-packing. In RTCSA, 2012. Google ScholarDigital Library
- J. Zhu, I. Sander, and A. Jantsch. Energy efficient streaming applications with guaranteed throughput on mpsocs. In EMSOFT, 2008. Google ScholarDigital Library
Recommendations
Energy-Efficient Scheduling Algorithms for Real-Time Parallel Applications on Heterogeneous Distributed Embedded Systems
Energy consumption minimization is one of the primary design requirements for heterogeneous distributed systems. State-of-the-art algorithms are used to study the problem of minimizing the energy consumption of a real-time parallel application with ...
Energy-Efficient Task Scheduling and Task Energy Consumption Analysis for Real-Time Embedded Systems
TASE '14: Proceedings of the 2014 Theoretical Aspects of Software Engineering Conference (tase 2014)As the limitations of energy consumption for real-time embedded systems more strict, it has been difficult to ignore the context switch overhead for Fixed-Priority task with Preemption scheduling (FPP) in multitasking environment. This paper presents a ...
Comments