Stochastic Load Balancing in Parallel Computers

摘要

This reprint presents several algorithms for determining load balancingparameters when partitioning work loads in the context of a parallel or distributed computing system. Several simple assumptions are made, to wit: (a) Any task can be partitioned arbitrarily finely; (b) Computation time at any node is directly proportional to task size; (c) Communication time is negligible; and (d) Computation times at distinct nodes are independent random variables with common density. The load balance parameter is shown to depend on the distribution of this density and in particular with the expectation of order statistics associated with this density. We give tables of load balance parameters for the exponential and the uniform densities. We also compute the expected load balanced computation time. We conclude with a discussion of randomized load balancing. (kr)