Dimension-exchange algorithms for token distribution on tree-connected architectures

Michael E. Houle, Antonios Symvonis, David R. Wood

    Research output: Contribution to journalArticleResearchpeer-review

    9 Citations (Scopus)

    Abstract

    Load balancing on a multi-processor system involves redistributing tasks among processors so that each processor has roughly the same amount of work 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 scalable method for distributing tokens over a parallel architecture is the so-called dimension-exchange approach. Our results include improved analysis of two existing dimension-exchange algorithms for token distribution on arbitrary graphs and on arbitrary trees, respectively. In particular, we establish a logarithmic upper bound on the discrepancy of the resulting distribution when the second algorithm is applied to an arbitrary initial distribution on a tree. We then present a new dimension-exchange algorithm for token distribution on trees, which assuming each node knows the number of nodes in the tree, determines a 'perfectly balanced' distribution. Furthermore, the rate of convergence is worst-case optimal for trees of bounded degree. Note that an algorithm for token-distribution on trees is applicable to arbitrary architectures, since the algorithm can be applied on a spanning tree of any given connected graph.

    Original languageEnglish
    Pages (from-to)591-605
    Number of pages15
    JournalJournal of Parallel and Distributed Computing
    Volume64
    Issue number5
    DOIs
    Publication statusPublished - 1 May 2004

    Keywords

    • Dimension-exchange
    • Load balancing
    • Token distribution
    • Tree

    Cite this