Adaptive scheduling of computations and communications on distributed memory systems

Compile-time scheduling is one approach to extract parallelism which proved to be effective when the execution behavior is predictable. Unfortunately, the performance of most priority-based scheduling algorithms is computation dependent. Scheduling by using earliest-task-first (ETF) produces reasonably short schedules only when available parallelism is large enough to cover the communications. A priority-based decision is much more effective when parallelism is low. We propose a scheduling in which the decision function combines: (1) task-level as global priority, and (2) earliest-task-first as local priority. The degree of dominance of one of the above concepts is controlled by a computation profile factor such as task parallelism and communication. An iterative scheduler (forward and backward) is proposed for tuning the solution. In each iteration, the new schedule is used to sharpen the task-levels. This contributes in finding shorter schedules in next iteration. Evaluation is carried out by using synthetic task-graphs for computations with communications times for which optimum schedules are known. It is found that finish time of pure local scheduling (like ETF) and static priority-based scheduling significantly deviate from optimum when task parallelism is low in presence of relatively large communication. Our approach to adapting the scheduling decision to computation profile was able to produce near-optimum solutions through much less number of iterations than other approaches.