Optimal dimension-exchange token distribution on complete binary trees

Load balancing on a multi-processor system involves redistributing tasks am ong processors so that each has roughly the same amount of work to perform. The token-distribution problem is a static variant of the load balancing p roblem for the case in which the workloads in the system cannot be divided arbitrarily; i.e., where each token represents an atomic element of work. A simple, scalable method for distributing tokens over a distributed-memory parallel architecture is the so-called dimension-exchange approach, which i s based on the repetitive application of an extremely simple and scalable l ocal exchange protocol. The behaviour of this approach depends heavily on t he topology of the interconnection network. This paper presents an analysis of dimension-exchange algorithms for token distribution on the complete binary tree. We show that for the complete bin ary tree of height H, and any initial distribution for which the discrepanc y in workloads is greater than H tokens, the dimension-exchange method will eventually reduce the discrepancy to at most H. Furthermore, we show that the rate of this convergence to H is worst-case optimal. These results are the first to establish that dimension-exchange techniques lead to optimal a lgorithms for finitely-divisible load balancing on a tree-connected network . (C) 1999 Elsevier Science B.V. All rights reserved.