Layer-Based Scheduling Algorithms for Multiprocessor-Tasks with Precedence Constraints

A current challenge in the development of parallel applications for distributed memory plat-forms is the achievement of a good scalability even for a high number of processors. The scal-ability is impacted by the use of communication operations, e.g. broadcast operations, whose runtime exhibits a logarithmic or linear dependence on the number of utilized processors. The multiprocessor-task programming model can help to reduce the communication overhead, but requires an appropriate schedule for an efficient execution. Many heuristics and approxima-tion algorithms are available for this scheduling task. The choice of a suitable scheduling al-gorithm is an important factor in the development of multiprocessor-task applications. In this paper, we consider layer-based scheduling algorithms and compare their runtimes for large task graphs consisting of up to 1000 nodes and target systems with up to 256 processors. Further-more, we introduce an extension methodology to enable scheduling algorithms for independent multiprocessor-tasks to handle precedence constraints.