Document Open Access Logo

Energy Minimization in DAG Scheduling on MPSoCs at Run-Time: Theory and Practice

Authors Bertrand Simon, Joachim Falk, Nicole Megow, Jürgen Teich

PDF
Thumbnail PDF

File

OASIcs.NG-RES.2020.2.pdf
  • Filesize: 0.51 MB
  • 13 pages

Document Identifiers

Author Details

Bertrand Simon
  • Universität Bremen, Germany
Joachim Falk
  • Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Germany
Nicole Megow
  • Universität Bremen, Germany
Jürgen Teich
  • Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Germany

Cite As Get BibTex

Bertrand Simon, Joachim Falk, Nicole Megow, and Jürgen Teich. Energy Minimization in DAG Scheduling on MPSoCs at Run-Time: Theory and Practice. In Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2020). Open Access Series in Informatics (OASIcs), Volume 77, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/OASIcs.NG-RES.2020.2

Abstract

Static (offline) techniques for mapping applications given by task graphs to MPSoC systems often deliver overly pessimistic and thus suboptimal results w.r.t. exploiting time slack in order to minimize the energy consumption. This holds true in particular in case computation times of tasks may be workload-dependent and becoming known only at runtime or in case of conditionally executed tasks or scenarios. This paper studies and quantitatively evaluates different classes of algorithms for scheduling periodic applications given by task graphs (i.e., DAGs) with precedence constraints and a global deadline on homogeneous MPSoCs purely at runtime on a per-instance base. We present and analyze algorithms providing provably optimal results as well as approximation algorithms with proven guarantees on the achieved energy savings. For problem instances taken from realistic embedded system benchmarks as well as synthetic scalable problems, we provide results on the computation time and quality of each algorithm to perform a) scheduling and b) voltage/speed assignments for each task at runtime. In our portfolio, we distinguish as well continuous and discrete speed (e.g., DVFS-related) assignment problems. In summary, the presented ties between theory (algorithmic complexity and optimality) and execution time analysis deliver important insights on the practical usability of the presented algorithms for runtime optimization of task scheduling and speed assignment on MPSoCs.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Scheduling
  • Theory of computation → Scheduling algorithms
Keywords
  • energy minimization
  • speed scaling
  • precedence graphs
  • scheduling
  • critical path
  • MPSoC

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Epigenomics dataset from the Pegasus library. https://confluence.pegasus.isi.edu/display/pegasus/WorkflowGenerator. [Online; accessed 02-September-2019].
  2. Susanne Albers. Energy-efficient algorithms. Communications of the ACM, 53(5):86-96, 2010. Google Scholar
  3. Guillaume Aupy, Anne Benoit, Fanny Dufossé, and Yves Robert. Reclaiming the energy of a schedule: models and algorithms. Concurrency and Computation: Practice and Experience, 25(11):1505-1523, 2013. Google Scholar
  4. Evripidis Bampis, Dimitrios Letsios, and Giorgio Lucarelli. A note on multiprocessor speed scaling with precedence constraints. In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 138-142, 2014. Google Scholar
  5. Gang Chen, Kai Huang, and Alois Knoll. Energy optimization for real-time multiprocessor system-on-chip with optimal DVFS and DPM combination. ACM Trans. Embedded Comput. Syst., 13:111:1-111:21, 2014. URL: https://doi.org/10.1145/2567935.
  6. Pravanjan Choudhury, P. P. Chakrabarti, and Rajeev Kumar. Online Dynamic Voltage Scaling using Task Graph Mapping Analysis for Multiprocessors. In 20th International Conference on VLSI Design, pages 89-94, 2007. Google Scholar
  7. Pepijn J. de Langen and Ben H. H. Juurlink. Leakage-Aware Multiprocessor Scheduling. Signal Processing Systems, 57(1):73-88, 2009. URL: https://doi.org/10.1007/s11265-008-0176-8.
  8. R. Dick. Embedded System Synthesis Benchmarks Suite (E3S). http://ziyang.eecs.umich.edu/~dickrp/e3s/. [Online; accessed 02-September-2019].
  9. M.R. Garey and D.S. Johnson. Strong NP-completeness results: motivation, examples, and implications. J. Assoc. Comput. Mach., 25(3):499-508, 1978. Google Scholar
  10. R. L. Graham. Bounds for certain multiprocessing anomalies. The Bell System Technical Journal, 45(9):1563-1581, November 1966. URL: https://doi.org/10.1002/j.1538-7305.1966.tb01709.x.
  11. Abdou Guermouche, Loris Marchal, Bertrand Simon, and Frédéric Vivien. Scheduling trees of malleable tasks for sparse linear algebra. In European Conference on Parallel Processing, pages 479-490. Springer, 2015. Google Scholar
  12. Sandy Irani and Kirk Pruhs. Algorithmic problems in power management. SIGACT News, 36(2):63-76, 2005. Google Scholar
  13. Woo-Cheol Kwon and Taewhan Kim. Optimal voltage allocation techniques for dynamically variable voltage processors. ACM Trans. Embedded Comput. Syst., 4(1):211-230, 2005. Google Scholar
  14. Eugene L Lawler. Sequencing jobs to minimize total weighted completion time subject to precedence constraints. In Annals of Discrete Mathematics, volume 2, pages 75-90. Elsevier, 1978. Google Scholar
  15. Keqin Li. Performance Analysis of Power-Aware Task Scheduling Algorithms on Multiprocessor Computers with Dynamic Voltage and Speed. IEEE Trans. Parallel Distrib. Syst., 19(11):1484-1497, 2008. URL: https://doi.org/10.1109/TPDS.2008.122.
  16. Minming Li and F. Frances Yao. An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules. SIAM J. Comput., 35(3):658-671, 2005. Google Scholar
  17. Nicole Megow and José Verschae. Dual Techniques for Scheduling on a Machine with Varying Speed. SIAM J. Discrete Math., 32(3):1541-1571, 2018. Google Scholar
  18. Andrew Nelson, Orlando Moreira, Anca Mariana Molnos, Sander Stuijk, Ba Thang Nguyen, and Kees Goossens. Power Minimisation for Real-Time Dataflow Applications. In 14th Euromicro Conference on Digital System Design, Architectures, Methods and Tools (DSD 2011), pages 117-124, 2011. Google Scholar
  19. Yurii Nesterov and Arkadii Nemirovskii. Interior Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1994. Google Scholar
  20. G. N. Srinivasa Prasanna and Bruce R. Musicus. Generalized Multiprocessor Scheduling and Applications to Matrix Computations. IEEE TPDS, 7(6):650-664, 1996. URL: https://doi.org/10.1109/71.506703.
  21. Kirk Pruhs, Rob van Stee, and Patchrawat Uthaisombut. Speed scaling of tasks with precedence constraints. Theory of Computing Systems, 43(1):67-80, 2008. Google Scholar
  22. Dongkun Shin and Jihong Kim. Power-aware scheduling of conditional task graphs in real-time multiprocessor systems. In Proceedings of the 2003 International Symposium on Low Power Electronics and Design, 2003, Seoul, Korea, August 25-27, 2003, pages 408-413, 2003. Google Scholar
  23. Amit Kumar Singh, Anup Das, and Akash Kumar. Energy optimization by exploiting execution slacks in streaming applications on multiprocessor systems. In The 50th Annual Design Automation Conference 2013 (DAC 2013), pages 115:1-115:7, 2013. Google Scholar
  24. Ola Svensson. Hardness of Precedence Constrained Scheduling on Identical Machines. SIAM J. Comput., 40(5):1258-1274, 2011. Google Scholar
  25. Umair Ullah Tariq and Hui Wu. Energy-Aware Scheduling of Periodic Conditional Task Graphs on MPSoCs. In Proceedings of the 18th International Conference on Distributed Computing and Networking, page 13, 2017. Google Scholar
  26. J.D. Ullman. NP-complete scheduling problems. J. Comput. System Sci., 10:384-393, 1975. Google Scholar
  27. F. Frances Yao, Alan J. Demers, and Scott Shenker. A Scheduling Model for Reduced CPU Energy. In Proc. of the 36th Annual Symposium on Foundations of Computer Science (FOCS 1995), pages 374-382, 1995. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact