---
_id: '16587'
abstract:
- lang: eng
  text: <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>
author:
- first_name: Robert
  full_name: Elsässer, Robert
  last_name: Elsässer
- first_name: Burkhard
  full_name: Monien, Burkhard
  last_name: Monien
- first_name: Robert
  full_name: Preis, Robert
  last_name: Preis
- first_name: Andreas
  full_name: Frommer, Andreas
  last_name: Frommer
citation:
  ama: Elsässer R, Monien B, Preis R, Frommer A. Optimal Diffusion Schemes and Load
    Balancing on Product Graphs. <i>Parallel Processing Letters</i>. 2004:61-73. doi:<a
    href="https://doi.org/10.1142/s0129626404001714">10.1142/s0129626404001714</a>
  apa: Elsässer, R., Monien, B., Preis, R., &#38; Frommer, A. (2004). Optimal Diffusion
    Schemes and Load Balancing on Product Graphs. <i>Parallel Processing Letters</i>,
    61–73. <a href="https://doi.org/10.1142/s0129626404001714">https://doi.org/10.1142/s0129626404001714</a>
  bibtex: '@article{Elsässer_Monien_Preis_Frommer_2004, title={Optimal Diffusion Schemes
    and Load Balancing on Product Graphs}, DOI={<a href="https://doi.org/10.1142/s0129626404001714">10.1142/s0129626404001714</a>},
    journal={Parallel Processing Letters}, author={Elsässer, Robert and Monien, Burkhard
    and Preis, Robert and Frommer, Andreas}, year={2004}, pages={61–73} }'
  chicago: Elsässer, Robert, Burkhard Monien, Robert Preis, and Andreas Frommer. “Optimal
    Diffusion Schemes and Load Balancing on Product Graphs.” <i>Parallel Processing
    Letters</i>, 2004, 61–73. <a href="https://doi.org/10.1142/s0129626404001714">https://doi.org/10.1142/s0129626404001714</a>.
  ieee: R. Elsässer, B. Monien, R. Preis, and A. Frommer, “Optimal Diffusion Schemes
    and Load Balancing on Product Graphs,” <i>Parallel Processing Letters</i>, pp.
    61–73, 2004.
  mla: Elsässer, Robert, et al. “Optimal Diffusion Schemes and Load Balancing on Product
    Graphs.” <i>Parallel Processing Letters</i>, 2004, pp. 61–73, doi:<a href="https://doi.org/10.1142/s0129626404001714">10.1142/s0129626404001714</a>.
  short: R. Elsässer, B. Monien, R. Preis, A. Frommer, Parallel Processing Letters
    (2004) 61–73.
date_created: 2020-04-16T05:46:56Z
date_updated: 2022-01-06T06:52:52Z
department:
- _id: '101'
doi: 10.1142/s0129626404001714
language:
- iso: eng
page: 61-73
publication: Parallel Processing Letters
publication_identifier:
  issn:
  - 0129-6264
  - 1793-642X
publication_status: published
status: public
title: Optimal Diffusion Schemes and Load Balancing on Product Graphs
type: journal_article
user_id: '15701'
year: '2004'
...
---
_id: '18936'
abstract:
- lang: eng
  text: 'We consider the following periodic sorting procedure on two-dimensional meshes
    of processors: Initially, each node contains one number. We proceed in rounds
    each round consisting of sorting the columns of the grid, and, in the second phase,
    of sorting the rows according to the snake-like ordering. We exactly characterize
    the number of rounds necessary to sort on an l × m-grid in the worst case, where
    l is the number of the rows and m the number of the columns. An upper bound of
    ⌈ log l⌉ + 1was known before. This bound is tight for the case that m is not a
    power of 2. Surprisingly, it turns out that far fewer rounds are necessary if
    m is a power of 2 (and m ≪ l) in this case, exactly min { log m + 1, ⌈ log l⌉
    + 1} rounds are needed in the worst case.'
author:
- first_name: Miroslaw
  full_name: Kutylowski, Miroslaw
  last_name: Kutylowski
- first_name: Rolf
  full_name: Wanka, Rolf
  last_name: Wanka
citation:
  ama: Kutylowski M, Wanka R. Periodic Sorting on Two-Dimensional Meshes. <i>Parallel
    Processing Letters 2</i>. Published online 1992:213-220. doi:<a href="https://doi.org/10.1142/s0129626492000349">10.1142/s0129626492000349</a>
  apa: Kutylowski, M., &#38; Wanka, R. (1992). Periodic Sorting on Two-Dimensional
    Meshes. <i>Parallel Processing Letters 2</i>, 213–220. <a href="https://doi.org/10.1142/s0129626492000349">https://doi.org/10.1142/s0129626492000349</a>
  bibtex: '@article{Kutylowski_Wanka_1992, title={Periodic Sorting on Two-Dimensional
    Meshes}, DOI={<a href="https://doi.org/10.1142/s0129626492000349">10.1142/s0129626492000349</a>},
    journal={Parallel Processing Letters 2}, author={Kutylowski, Miroslaw and Wanka,
    Rolf}, year={1992}, pages={213–220} }'
  chicago: Kutylowski, Miroslaw, and Rolf Wanka. “Periodic Sorting on Two-Dimensional
    Meshes.” <i>Parallel Processing Letters 2</i>, 1992, 213–20. <a href="https://doi.org/10.1142/s0129626492000349">https://doi.org/10.1142/s0129626492000349</a>.
  ieee: 'M. Kutylowski and R. Wanka, “Periodic Sorting on Two-Dimensional Meshes,”
    <i>Parallel Processing Letters 2</i>, pp. 213–220, 1992, doi: <a href="https://doi.org/10.1142/s0129626492000349">10.1142/s0129626492000349</a>.'
  mla: Kutylowski, Miroslaw, and Rolf Wanka. “Periodic Sorting on Two-Dimensional
    Meshes.” <i>Parallel Processing Letters 2</i>, 1992, pp. 213–20, doi:<a href="https://doi.org/10.1142/s0129626492000349">10.1142/s0129626492000349</a>.
  short: M. Kutylowski, R. Wanka, Parallel Processing Letters 2 (1992) 213–220.
date_created: 2020-09-03T11:05:14Z
date_updated: 2022-01-06T06:53:55Z
department:
- _id: '63'
doi: 10.1142/s0129626492000349
language:
- iso: eng
page: 213-220
publication: Parallel Processing Letters 2
publication_identifier:
  issn:
  - 0129-6264
  - 1793-642X
publication_status: published
status: public
title: Periodic Sorting on Two-Dimensional Meshes
type: journal_article
user_id: '15415'
year: '1992'
...