[{"abstract":[{"text":" 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 l2 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. ","lang":"eng"}],"user_id":"15701","title":"Optimal Diffusion Schemes and Load Balancing on Product Graphs","author":[{"last_name":"Elsässer","full_name":"Elsässer, Robert","first_name":"Robert"},{"last_name":"Monien","first_name":"Burkhard","full_name":"Monien, Burkhard"},{"first_name":"Robert","full_name":"Preis, Robert","last_name":"Preis"},{"last_name":"Frommer","full_name":"Frommer, Andreas","first_name":"Andreas"}],"publication":"Parallel Processing Letters","department":[{"_id":"101"}],"status":"public","date_created":"2020-04-16T05:46:56Z","publication_status":"published","publication_identifier":{"issn":["0129-6264","1793-642X"]},"_id":"16587","date_updated":"2022-01-06T06:52:52Z","doi":"10.1142/s0129626404001714","language":[{"iso":"eng"}],"year":"2004","type":"journal_article","citation":{"ieee":"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.","short":"R. Elsässer, B. Monien, R. Preis, A. Frommer, Parallel Processing Letters (2004) 61–73.","mla":"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.","bibtex":"@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} }","ama":"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","apa":"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","chicago":"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."},"page":"61-73"},{"year":"1992","type":"journal_article","citation":{"short":"M. Kutylowski, R. Wanka, Parallel Processing Letters 2 (1992) 213–220.","ieee":"M. Kutylowski and R. Wanka, “Periodic Sorting on Two-Dimensional Meshes,” Parallel Processing Letters 2, pp. 213–220, 1992, doi: 10.1142/s0129626492000349.","chicago":"Kutylowski, Miroslaw, and Rolf Wanka. “Periodic Sorting on Two-Dimensional Meshes.” Parallel Processing Letters 2, 1992, 213–20. https://doi.org/10.1142/s0129626492000349.","apa":"Kutylowski, M., & Wanka, R. (1992). Periodic Sorting on Two-Dimensional Meshes. Parallel Processing Letters 2, 213–220. https://doi.org/10.1142/s0129626492000349","ama":"Kutylowski M, Wanka R. Periodic Sorting on Two-Dimensional Meshes. Parallel Processing Letters 2. Published online 1992:213-220. doi:10.1142/s0129626492000349","mla":"Kutylowski, Miroslaw, and Rolf Wanka. “Periodic Sorting on Two-Dimensional Meshes.” Parallel Processing Letters 2, 1992, pp. 213–20, doi:10.1142/s0129626492000349.","bibtex":"@article{Kutylowski_Wanka_1992, title={Periodic Sorting on Two-Dimensional Meshes}, DOI={10.1142/s0129626492000349}, journal={Parallel Processing Letters 2}, author={Kutylowski, Miroslaw and Wanka, Rolf}, year={1992}, pages={213–220} }"},"page":"213-220","language":[{"iso":"eng"}],"doi":"10.1142/s0129626492000349","date_updated":"2022-01-06T06:53:55Z","_id":"18936","publication_identifier":{"issn":["0129-6264","1793-642X"]},"publication_status":"published","status":"public","date_created":"2020-09-03T11:05:14Z","author":[{"first_name":"Miroslaw","full_name":"Kutylowski, Miroslaw","last_name":"Kutylowski"},{"last_name":"Wanka","first_name":"Rolf","full_name":"Wanka, Rolf"}],"publication":"Parallel Processing Letters 2","department":[{"_id":"63"}],"title":"Periodic Sorting on Two-Dimensional Meshes","user_id":"15415","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."}]}]