License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.NG-RES.2020.2
URN: urn:nbn:de:0030-drops-117781
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11778/
Go to the corresponding OASIcs Volume Portal

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

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

pdf-format:
OASIcs-NG-RES-2020-2.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{simon_et_al:OASIcs:2020:11778,
  author =	{Bertrand Simon and Joachim Falk and Nicole Megow and J{\"u}rgen Teich},
  title =	{{Energy Minimization in DAG Scheduling on MPSoCs at Run-Time: Theory and Practice}},
  booktitle =	{Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2020)},
  pages =	{2:1--2:13},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-136-8},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{77},
  editor =	{Marko Bertogna and Federico Terraneo},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11778},
  URN =		{urn:nbn:de:0030-drops-117781},
  doi =		{10.4230/OASIcs.NG-RES.2020.2},
  annote =	{Keywords: energy minimization, speed scaling, precedence graphs, scheduling, critical path, MPSoC}
}

Keywords: energy minimization, speed scaling, precedence graphs, scheduling, critical path, MPSoC
Collection: Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2020)
Issue Date: 2020
Date of publication: 20.01.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI