Eleventh Euromicro Conference on Parallel, Distributed and Network-Based Processing
Broken Edges and Dimension Exchange Algorithms on Hypercube Topology
Genova, Italy
February 05-February 07
ISBN: 0-7695-1875-3
In this paper, a new method of distributed load balancing is given. This method could be described as a generalization of the Dimension Exchange on hypercube topologies with dynamic links. A network with dynamic links assumes that edges of the topology may be broken down, but no processor is dynamically added on the network. We suppose that the topology of the network is a hypercube in the physical or logical sense, i.e. the communication channels are organized as a hypercube. The main result of this paper consists in proving the convergence toward the uniform load distribution of Dimension Exchange algorithm on hypercubes with broken edges. We need few conditions for the convergence and these conditions are close to real situations. To study the behavior of this method, we achieve a simulation on a real network and we compare the results with a simulation of the classical Dimension Exchange without broken links. These simulations illustrates the convergence of the method and shows the irregularity of convergence due to the broken edges.
Index Terms:
load balancing, hypercube, broken edge, dimension exchange
Citation:
Jacques Bahi, Raphaël Couturier, Flavien Vernier, "Broken Edges and Dimension Exchange Algorithms on Hypercube Topology," pdp, pp.140, Eleventh Euromicro Conference on Parallel, Distributed and Network-Based Processing, 2003