Min-cut methods for mapping dataflow graphs
Volker Elling, Karsten Schwan
Full text: pdf ps (gz)
Abstract
High performance applications and the underlying hardware platforms
are becoming increasingly dynamic; runtime changes in the
behavior of both are likely to result in inappropriate mappings of tasks to
parallel machines during application execution. This fact is prompting new
research on mapping and scheduling the dataflow graphs that represent
parallel applications. In contrast to recent research which focuses on
critical paths in dataflow graphs, this paper presents new mapping methods
that compute near-min-cut partitions of the dataflow graph.
Our methods deliver mappings that are an order of magnitude more efficient
than those of DSC, a state-of-the-art critical-path algorithm,
for sample high performance
applications.