Report Number: CS-TR-89-1281
Institution: Stanford University, Department of Computer Science
Title: Load balancing on the hypoercube and shuffle-exchange
Author: Plaxton, C. Greg
Date: August 1989
Abstract: Maintaining a balanced load is of fundamental importance on
any parallel computer, since a strongly imbalanced load often
leads to low processor utilization. This paper considers two
load balancing operations: Balance and MultiBalance. The
Balance operation corresponds to the token distribution
problem considered by Peleg and Upfal  for certain
expander networks. The MultiBalance operation balances
several populations of distinct token types simultaneously.
Efficient implementations of these operations will be given
for the hypercube and shuffle-exchange, along with tight or
near-tight lower bounds.