Dimension-Exchange Token Distribution on Complete Binary Trees

CS-TR-96-22

Authors: Ewan Tempero, Gavin Turner
Source: GZipped PostScript (80kb); Adobe PDF (428kb)


Load balancing on a multi-processor systems involves shifting the work around the system so that each processor has about the same amount of work to do. The {\em token-distribution} problem is a static variant of load balancing for the case when the workloads in the system cannot be divided arbitrarily, where each token represents an atomic element of work. A simple method for distributing tokens is the so-called {\em 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 an analysis of the convergence properties of a dimension{-}exchange algorithm 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 $\limit$ tokens, the dimension-exchange approach leads to the eventual convergence of the distribution such that the discrepancy is at most $\limit$. These results are the first to establish that dimension{-}exchange techniques lead to useful algorithms for finitely{-}divisible load balancing on a tree{-}connected network.


[Up to Computer Science Technical Report Archive: Home Page]