Premium
On Finite Dimension Exchange Algorithms
Author(s) -
Arndt H.
Publication year - 2002
Publication title -
pamm
Language(s) - English
Resource type - Journals
ISSN - 1617-7061
DOI - 10.1002/1617-7061(200203)1:1<500::aid-pamm500>3.0.co;2-z
Subject(s) - dimension (graph theory) , bounded function , computer science , algorithm , graph , port (circuit theory) , diffusion , theoretical computer science , mathematics , combinatorics , electrical engineering , mathematical analysis , physics , thermodynamics , engineering
Load balancing on parallel computers aims at equilibrating some initial load which is different from one processor to another. We consider only nearest neighbour algorithms: in each step a processor communicates only with its direct neighbours. Load balancing algorithms can be divided into two classes: diffusion and dimension exchange. Whereas the first is appropriate for the so‐called all‐port‐model where a processor can send tokens to all its neighbours at a time, the latter is useful for the one‐port‐model. Both kinds of algorithms can be viewed as methods for solving certain singular linear systems. Since a few years there exist finite diffusion algorithms which have the property that they compute l 2 ‐minimal flows. In this paper a new finite dimension exchange method will be presented that is based on edge‐colourings of the underlying graph. It is usually faster and more stable than its diffusion counterpart. The flows computed by the new method are not minimal but it can be shown that they are bounded. Our analysis is based on techniques from numerical linear algebra.