A comparative analysis of static parallel schedulers where communication costs are significant
Douglas Michael Pase · OHSU Digital Commons · 1989
Efficient multiprocessor scheduling where communication between processors is free has been studied for almost three decades. However, modern distributed architectures have communication channels for which communication is not free. Such channels have a nonzero latency and a finite capacity for communication. Previous work on parallel scheduling accounting for communication effects has assumed that the channels had sufficient capacity to service all transmissions without significant delay from contention. We show that the average schedule length can be significantly shortened by taking contention into account. We define families of static schedulers based on the strategy chosen for various phases, and present a performance analysis based on that classification. Because certain static schedulers are equivalent to dynamic schedulers for which perfect knowledge is available, parts of this work also apply to dynamic scheduling.