A task scheduling algorithm to package messages on distributedmemory parallel machines

摘要

In this paper, we report a performance gap between a schedule withgood makespan on the task scheduling model and the correspondingparallel program on distributed memory parallel machines. The mainreason is the software overhead in the interprocessor communication.Therefore, speedup ratios of schedules on the model do not wellapproximate to those of parallel programs on the machines. The purposeof the paper is to get a task scheduling algorithm that generatesschedules with good approximation to the corresponding parallel program.For this purpose, we propose an algorithm BCSH that generates only bulksynchronous style schedules. In those schedules, computation phases andcommunication phases appear alternately. All interprocessorcommunications are done only in the latter phases, and thus thecorresponding parallel programs can make better use of the messagepackaging technique easily. It reduces some software overheads ofmessages from a source processor to the same destination processor toalmost one software overhead, and improves the performance of a parallelprogram significantly. Finally we show some results of performancecomparisons between BCSH and Kruatrachue's algorithm DSH. The schedulesby the latter are famous for their good makespans. However theapproximations of ours are much better than those of Kruatrachue's