Comparing optimal and heuristic taskgraph scheduling on parallel machines with frequency scaling
Patrick Eitschberger, Jörg Keller · Concurrency and Computation Practice and Experience · 2019
Summary We investigate static scheduling of taskgraphs onto parallel machines where the frequency of processors can be scaled at runtime. Given a deadline until which execution of the resulting schedule must be completed, we aim at minimizing the energy consumed by the parallel processors during execution. We present optimal and heuristic solutions to this problem and partial problems. We quantify the increase in energy consumption when switching from a globally optimal solution via a combination of optimal partial solutions to heuristic solutions. We find that, on our set of benchmark taskgraphs, the increase is 32.56% on average for a combination of heuristic solutions and thus tolerable.