Accelerating divisible load distribution on tree and pyramid networks using pipelined communications

Summary form only given. We propose two methods which employ pipelined communications to distribute divisible loads on tree and pyramid networks. We derive the closed form solutions to the parallel time and speedup for both methods and show that the asymptotic speedup of both methods is 6β+1 for a complete b-ary tree network and 4β+1 for a pyramid network, where β is the ratio of the time for computing a unit load to the time for communicating a unit load.