### 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 language | English |
---|---|

Pages (from-to) | 591-605 |

Number of pages | 15 |

Journal | Journal of Parallel and Distributed Computing |

Volume | 64 |

Issue number | 5 |

DOIs | |

Publication status | Published - 1 May 2004 |

### Keywords

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

## Cite this

*Journal of Parallel and Distributed Computing*,

*64*(5), 591-605. https://doi.org/10.1016/j.jpdc.2004.03.011