A robust Compile Time Method for Scheduling Task Parallelism on Distributed Memory Machines

摘要

The problem of compile time scheduling of tasks of a program represented as a directed acyclic graph (DAG) s NP-hard in its general form. A number of approaches have been proposed which attempt to solve the problem either sub-optimally for general cases or optimally for restrictive special cases. But all the compile time approaches suffer due to the inability to accurately model the computation and communication costs of the target architecture. A desirable property of a compile time scheduling algorithm is robustness against the variations in the computation and communication costs so that the run time performance is close to the compile time estimates; this aspect of scheduling has been left open in the literature.