BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-89-1281
       ENTRY:: January 05, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Load balancing on the hypoercube and shuffle-exchange
        TYPE:: Technical Report
      AUTHOR:: Plaxton, C. Greg
        DATE:: August 1989
       PAGES:: 22
    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.
       NOTES:: [Adminitrivia V1/RAM/19950105]
         END:: STAN//CS-TR-89-1281