Efficient Workload-Balancing on Grids, Hypercubes and Trees
Max Böhm, Ewald Speckenmeyer · 1994
We present several algorithms for achieving efficient workload balancing (WLB) on message based MIMD machines. Given a set of n processors P = {p1,...,p n } and a communication network N ⊂ P × P. At a fixed point in time every processor p ∈ P has a workload (WL) λ(p) ∈ ℝ+, which is an estimation for the time needed to solve the problems placed on p. In the following we assume, that WL is dividible in infinitely small pieces, which can be exchanged between processors. The basic step move(p, q, l) with p, q ∈ P, (p,q) ∈ N, −λ(q)≤ l ≤ λ(p) means that workload l is moved from p to q if l > 0 or workload −l is moved from q to p if l < 0. WL λ(p) changes into λ(p) − l and λ(q) changes into λ(q) + l. The WLB problem consists of exchanging WL between processors resulting in a uniformly distributed WL, i. e. ∀p,q ∈ P: λ(p) = λ(q). The following algorithm solves the problem for processor-trees T = (P, N) in time O(h · d max ) with h = height of T and d max = maximal number of sons per processor.