Premium
Comparing optimal and heuristic taskgraph scheduling on parallel machines with frequency scaling
Author(s) -
Eitschberger Patrick,
Keller Jörg
Publication year - 2019
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.5396
Subject(s) - computer science , benchmark (surveying) , heuristic , scheduling (production processes) , mathematical optimization , frequency scaling , schedule , parallel computing , energy consumption , set (abstract data type) , scaling , mathematics , engineering , geometry , geodesy , artificial intelligence , electrical engineering , programming language , geography , operating system
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.