  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.
