Mapped Taskgraphs as a Tool for Optimization in Static Taskgraph Scheduling

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.