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

Simon B, Falk J, Megow N, Teich J (2020)

Publication Language: English

Publication Type: Conference contribution, Conference Contribution

Publication year: 2020

Pages Range: 2:1-2:13

Conference Proceedings Title: Proceedings of the Workshop on Next Generation Real-Time Embedded Systems (NG-RES)

Event location: Bologna IT

URI: https://drops.dagstuhl.de/opus/volltexte/2020/11778/

DOI: 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.

Authors with CRIS profile

Jürgen Teich Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design)

Involved external institutions

Universität Bremen DE Germany (DE)

How to cite

APA:

Simon, B., Falk, J., Megow, N., & Teich, J. (2020). Energy Minimization in DAG Scheduling on MPSoCs at Run-Time: Theory and Practice. In Proceedings of the Workshop on Next Generation Real-Time Embedded Systems (NG-RES) (pp. 2:1-2:13). Bologna, IT.

MLA:

Simon, Bertrand, et al. "Energy Minimization in DAG Scheduling on MPSoCs at Run-Time: Theory and Practice." Proceedings of the Workshop on Next Generation Real-Time Embedded Systems, Bologna 2020. 2:1-2:13.

BibTeX: Download