Authors: Michale E. Houle, Ewan Tempero, Gavin Turner
Source: GZipped PostScript (76kb); Adobe PDF
(389kb)
Load balancing on a multi-processor systems involves shifting work around the system so that each processor has about the same amount of processing to perform. The token-distribution problem is a static variant of the load balancing problem for the case in which the workloads in the system cannot be divided arbitrarily; that is, 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 is based on the repetitive application of an extremely simple and scalable local exchange protocol. The behaviour of this approach depends on the topology of the interconnection network.This paper presents the analysis of dimension-exchange algorithms for token distribution on the complete binary tree. We show that for the height H complete binary tree and any initial distribution for which the discrepancy in workloads is greater than H tokens, the dimension-exchange approach leads to the eventual convergence of the distribution such that the discrepancy is at most H. Furthermore, we show that the rate of this convergence is optimal with respect to the bisection width lower bound. These results are the first to establish that dimension-exchange techniques lead to optimal algorithms for finitely-divisible load balancing on a tree-connected network.