Optimizing layer-based scheduling algorithms for parallel tasks with dependencies

• Published in: Concurrency and computation 2011-06, Vol.23 (8), p.827-849
• Main Authors: Kunis, R., Rünger, G.
• Format: Article
• Language: English
• Subjects: Algorithms; Concurrency; Construction; distributed memory; homogeneous platform; Optimization; optimization algorithm; parallel tasks with dependencies; Programming; Schedules; Scheduling; task scheduling; Tasks
• ISSN: 1532-0626; 1532-0634; 1532-0634
• DOI: 10.1002/cpe.1674

Programming with parallel tasks leads to task graphs with dependencies representing a parallel program. Scheduling algorithms are employed to find an efficient execution order of the parallel tasks. A large variety of scheduling algorithms exist, including layer‐based scheduling algorithms for homogeneous target platforms that build consecutive layers of independent parallel tasks and schedule each layer separately. Although these scheduling algorithms provide good results in terms of scheduling algorithm runtime and schedule execution time, the resulting schedules leave room for optimization. This article proposes an optimization for arbitrary layer‐based scheduling algorithms, which is called Move‐blocks algorithm. Given a layer‐based schedule of the parallel tasks, this algorithm moves blocks of parallel tasks into preceding layers in order to reduce the overall execution time of a task‐based application. Suitable blocks of parallel tasks are identified by the algorithm Find‐blocks, which is employed together with the Move‐blocks algorithm. The algorithm Move‐blocks is applied to four well‐known scheduling algorithms. A detailed evaluation for a wide range of test cases is given. Copyright © 2010 John Wiley & Sons, Ltd.