Optimal Diffusion Schemes and Load Balancing on Product Graphs

R. Elsässer, B. Monien, R. Preis, A. Frommer, Parallel Processing Letters (2004) 61–73.

Download
No fulltext has been uploaded.
Journal Article | Published | English
Author
; ; ;
Abstract
<jats:p> We discuss nearest neighbor load balancing schemes on processor networks which are represented by a cartesian product of graphs and present a new optimal diffusion scheme for general graphs. In the first part of the paper, we introduce the Alternating-Direction load balancing scheme, which reduces the number of load balance iterations by a factor of 2 for cartesian products of graphs. The resulting flow is theoretically analyzed and can be very high for certain cases. Therefore, we further present the Mixed-Direction scheme which needs the same number of iterations but computes in most cases a much smaller flow. In the second part of the paper, we present a simple optimal diffusion scheme for general graphs, calculating a balancing flow which is minimal in the l<jats:sub>2</jats:sub> norm. It is based on the spectra of the graph representing the network and needs only m-1 iterations to balance the load with m being the number of distinct eigenvalues. Known optimal diffusion schemes have the same performance, however the optimal scheme presented in this paper can be implemented in a very simple manner. The number of iterations of optimal diffusion schemes is independent of the load scenario and, thus, they are practical for networks which represent graphs with known spectra. Finally, our experiments exhibit that the new optimal scheme can successfully be combined with the Alternating-Direction and Mixed-Direction schemes for efficient load balancing on product graphs. </jats:p>
Publishing Year
Journal Title
Parallel Processing Letters
Page
61-73
LibreCat-ID

Cite this

Elsässer R, Monien B, Preis R, Frommer A. Optimal Diffusion Schemes and Load Balancing on Product Graphs. Parallel Processing Letters. 2004:61-73. doi:10.1142/s0129626404001714
Elsässer, R., Monien, B., Preis, R., & Frommer, A. (2004). Optimal Diffusion Schemes and Load Balancing on Product Graphs. Parallel Processing Letters, 61–73. https://doi.org/10.1142/s0129626404001714
@article{Elsässer_Monien_Preis_Frommer_2004, title={Optimal Diffusion Schemes and Load Balancing on Product Graphs}, DOI={10.1142/s0129626404001714}, journal={Parallel Processing Letters}, author={Elsässer, Robert and Monien, Burkhard and Preis, Robert and Frommer, Andreas}, year={2004}, pages={61–73} }
Elsässer, Robert, Burkhard Monien, Robert Preis, and Andreas Frommer. “Optimal Diffusion Schemes and Load Balancing on Product Graphs.” Parallel Processing Letters, 2004, 61–73. https://doi.org/10.1142/s0129626404001714.
R. Elsässer, B. Monien, R. Preis, and A. Frommer, “Optimal Diffusion Schemes and Load Balancing on Product Graphs,” Parallel Processing Letters, pp. 61–73, 2004.
Elsässer, Robert, et al. “Optimal Diffusion Schemes and Load Balancing on Product Graphs.” Parallel Processing Letters, 2004, pp. 61–73, doi:10.1142/s0129626404001714.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar