A general strategy for scheduling parallel programs on distributed memory multiprocessor
Neelima Mehdiratta · 1995
Developing programs for multiprocessor systems involves partitioning the program into its sub-components and scheduling these components on the available processors. Since this development process is complex, automation of the techniques of partitioning and scheduling is necessary to ensure error free and deadlock free execution, as well as to improve the overall performance of the system. Several tools have been created for this purpose. Some of these are Hypertool (WuGa 90), POKER (Sn 84), PTOOL (ABKP 86), CAMP (PiGa 86), SUPERB (ZiCh 91) and MIMDizer from Applied Parallel Research. Programming for distributed memory multiprocessors is complicated by the existence of non-zero delays on the communication channels, making the program execution time sensitive to the interconnection topology, the type of routing used and the extent of contention among the communication channels. This requires the scheduling of concurrent units to processors in a manner that minimizes communication costs by reducing channel conflicts and actual communication time and possibly through the introduction of computation and communication overlap. Most existing schedulers for distributed memory systems are handicapped in their inability to address all of the factors that minimize the adverse effects of non-zero communication costs. We present a list based approach for statically scheduling parallel programs modeled as directed acyclic graphs (DAGS) on any type of distributed memory architecture, with the objective of reducing the overall execution time of the parallel program. The scheduler factors in the impact of the interconnection topology, the type of routing used (such as message-switched, packet switched, circuit-switched and wormhole) and delays due to channel conflicts on the overall execution time of the parallel program. Existing scheduling schemes assign tasks to processors proceeding from the top of the DAG or top down. Our scheduler departs from conventional list schedulers in its use of a bottom up approach to schedule task nodes. This is done to obtain accurate scheduling priorities that are based on the actual communication cost of a task to its successors. The scheduler incorporates heuristics to allocate task nodes to processors and to allocate communication channels in a manner that reduces channel contention delays. Experimental evaluations based on a number of randomly generated task graphs as well as task graphs corresponding to real programs indicate that the bottom up scheduler performs well. The scheduler shows a reduction in overall execution time of 40% to 70% on the average when compared against the schedule generated by the Mapping Heuristic (MH) scheduler (ElLe 90) --an existing and functionally comparable top down scheduler.