ALCOMFT-TR-02-98

Robert Elsässer, Burkhard Monien, Stefan Schamberger and Günter Rote
Toward optimal diffusion matrices
Paderborn. Work package 2. May 2002.

Abstract: Efficient load balancing algorithms are the key to many efficient parallel applications. Until now, research in this area has mainly been focusing on homogeneous schemes. However, observations show that the convergence rate of diffusion algorithms can be improved using edge weighted graphs without deteriorating the flows quality. In this paper we consider common interconnection topologies and demonstrate, how optimal edge weights can be calculated for the First and Second Order Diffusion Schemes. Using theoretical analysis and practical experiments we show, what improvements can be archived on selected networks.

Postscript file: ALCOMFT-TR-02-98.ps.gz (88 kb).