Mapped Taskgraphs as a Tool for Optimization in Static Taskgraph Scheduling

Conference: ARCS Workshop 2018 - 31th International Conference on Architecture of Computing Systems
04/09/2018 - 04/12/2018 at Braunschweig, Germany

Proceedings: ARCS 2018

Pages: 5Language: englishTyp: PDF

Personal VDE Members are entitled to a 10% discount on this title

Authors:
Keller, Joerg; Eitschberger, Patrick (Faculty of Mathematics and Computer Science, FernUniversit├Ąt in Hagen, 58084 Hagen, Germany)

Abstract:
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.