Task allocation on a network of processors

This paper studies the scheduling of tasks on a pool of identical workstati ons in a network where message passing is used for data transfer and commun ication between processors and where the precedence relations among tasks f orm a send-receive graph. Our parallel computation model differs from previ ous models by including all of the following practical considerations: 1) T he sending and receiving of multiple messages from one processor to another is performed sequentially, 2) communication overhead is proportional to th e message size, and 3) the starting and ending task must be performed on th e same machine. These factors are crucial when performing parallel task exe cution using a pool of workstations whose communication primitives are prov ided by off-the-shelf packages, such as PVM, and whose message sizes are no ntrivial. Although our model is new, using reduction from other well-known scheduling results shows that finding a scheduling with the optimal makespa n is NP-hard. Our focus, therefore, is on developing and analyzing approxim ation algorithms for this problem. When the number of workstations in the n etwork is abundant. a linear approximation algorithm is given with a proven performance bound of two times the optimal. When the number of available w orkstations is a fixed constant k that is greater than 2, we show an O(nlog n)-time approximation algorithm which always performs better than (3 + k-2/ k) times the optimal. Simulation results show that, on the average, both of our approximation algorithms perform much better than the worst case analy sis and both generate schedulings whose makespans are very close to optimal .