An Improved Direct Dimension Exchange Method for Load Balancing in k-ary n-cube Multicomputers.
Siu-Cheung Chau, Ada Wai-Chee Fu · 2000
This paper presents an improved direct dimension exchange method (DDE) for synchronous load balancing for k-ary n-cube multicomputers. The new method is based on the improved DEM for hypercube. The original DEM when extended to the k-ary n-cube requires many iterations in exchanging loads between neighboring nodes to converge to a balanced state. The original DDE does not requires iteratively exchanging loads between nodes. It can balance the load with fewer communication steps and can provide better load balancing quality than DEM. The improved DDE has better load balancing quality than the original DDE and has the same complexity of the original DDE. Keywords: dynamic load balancing, k-ary n-cube, multicomputer This research was supported by the National Sciences and Engineering Research Council of Canada 1 Introduction In a highly parallel multicomputer, time critical tasks can be executed quickly by splitting a task into sub-tasks. The sub-tasks are then executed in parallel...