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 [9] 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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/89/1281/CS-TR-89-1281.pdf