A simple algorithm for optimal load balancing on hypercube multiprocessor

This paper proposes a simple yet optimal algorithm to distribute loads evenly on multiprocessor computers with hypercube interconnection networks. The algorithm is developed upon the well-known dimension exchange method. However, the error accumulation suffered by other algorithms based on the dimension exchange method is avoided by, exploiting the notion of block distributions, which are commonly deployed for data distributions in parallel programming. The algorithm achieves perfect load balance over P processors with error of 1 and the worst-case time complexity of O(M log(2) P), where 11 is the maximum load assigned to each processor initially. Furthermore, perfect load balance is achieved over subcubes as well - once a cube is balanced, if the cube is decomposed into two subcubes by tile lowest bit of node addresses. then the difference between the number, of the total tasks of these subcubes is at most 1.