The Generalized Dimension Exchange Method for Load Balancing in k-ary n-Cubes and Variants

Abstract

The generalized dimension exchange (GDE) method is a fully distributed load balancing method that operates in a relaxation fashion for multicomputers with a direct communication network. It is parameterized by an exchange parameter λ that governs the splitting of load between a pair of directly connected processors during load balancing. An optimal λ would lead to the fastest convergence of the balancing process. Previous work has resulted in the optimal λ for the binary n-cubes. In this paper, we derive the optimal lambda′s for the k-ary n-cube network and its variants-the ring, the torus, the chain, and the mesh. We establish the relationships between the optimal convergence rates of the method when applied to these structures, and conclude that the GDE method favors high-dimensional k-ary n-cubes. We also reveal the superiority of the GDE method to another relaxation-based method, the diffusion method. We further show through statistical stimulations that the optimal lambda′s do speed up the GDE balancing procedure significantly. Because of its simplicity, the method is readily implementable. We report on the implementation of the method in two data-parallel computations in which the improvement in performance due to GDE balancing is substantial. © 1995 Academic Press. All rights reserved.