Optimizing Message Passing Programs Based on Task Section Duplication

The task scheduling model and algorithm is very important to achieve high performance for message passing programs. The SPG (subtask precedence graph) model abstracts a task as a set of communication and computation sections so it can explore the dependence among subtasks precisely. The TSSF (task section based scheduling framework ) is designed to show how to generate subtasks and how to schedule subtasks on to different processors. Based on the SPG model and the TSSF Framework, two TSD(task section duplication based) algorithms, SMU(searching-marking-unmarking) and Scalable SMU are described in detail to show how to get multiple parallel executing paths based on task section duplication. Compared with four typical traditional task scheduling algorithms, the simulation results show that our algorithms outperform other algorithms significantly.