1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99)
A Task Scheduling Algorithm to Package Messages on Distributed Memory Parallel Machines
Fremantle, Australia
June 23-June 25
ISBN: 0-7695-0231-8
In this paper, we report a performance gap between a schedule with good makespan on the task scheduling model and the corresponding parallel program on distributed memory parallel machines. The main reason is the software overhead in the interprocessor communication. Therefore, speedup ratios of schedules on the model do not well approximate to those of parallel programs on the machines.The purpose of the paper is to get a task scheduling algorithm that generates schedules with good approximation to the corresponding parallel program. For this purpose, we propose an algorithm BCSH that generates only bulk synchronous style schedules. In those schedules, computation phases and communication phases appear alternately. All interprocessor communications are done only in the latter phases, and thus the corresponding parallel programs can make better use of the message technique easily. It reduces some software overheads of messages from a source processor to the same destination processor to almost one software overhead, and improves performance of a parallel program significantly.Finally, we show some results of performance between BCSH and Kruatrachue's algorithm DSH. schedules by the latter are famous for their good However, the approximations of ours are much better than those of Kruatrachue's.
Citation:
Noriyuki Fujimoto, Tomoki Baba, Takashi Hashimoto, Kenichi Hagihara, "A Task Scheduling Algorithm to Package Messages on Distributed Memory Parallel Machines," ispan, pp.236, 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), 1999