Mapped Taskgraphs as a Tool for Optimization in Static Taskgraph Scheduling
Konferenz: ARCS Workshop 2018 - 31th International Conference on Architecture of Computing Systems
09.04.2018 - 12.04.2018 in Braunschweig, Germany
Tagungsband: ARCS 2018
Seiten: 5Sprache: EnglischTyp: PDFPersönliche VDE-Mitglieder erhalten auf diesen Artikel 10% Rabatt
Keller, Joerg; Eitschberger, Patrick (Faculty of Mathematics and Computer Science, FernUniversität in Hagen, 58084 Hagen, Germany)
We present the concept of mapped taskgraphs, which comprise all information of a static taskgraph and the corresponding static schedule. Mapped taskgraphs allow to reason about and optimize static schedules for taskgraphs in the language of graphs. This allows to employ the wealth of graph algorithmics, and still be able to extract easily a schedule with a task order similar to the original schedule, but possibly smaller makespan. We prove that our construction has the above properties, and present two exemplary applications that use mapped taskgraphs. One is new, the other a number of years old but only mentions a variant of this technique in passing and thus does not explicitly or formally explain it or deal with it.