Fourier analysis for solving the load balancing problem

• Autorzy: Karagiorgos G. , Missirlis N. M.
• Języki publikacji: EN

Abstrakty

EN

A new approach based on Fourier analysis to study Diffusion-type methods for solving the load balancing problem is presented. This approach is applied on two newly introduced methods the Average Diffusion (ADF) and its extrapolated counterpart (EADF) for d-regular graphs. Necessary and sufficient conditions are found for their convergence, whereas the optimum value of the extrapolation parameter r is determined in terms of M and m, the second largest and smallest eigenvalues of the ADF iteration matrix. Instead of using matrix theory, we apply Fourier analysis to determine M and m in case the diffusion parameters Cij are not equal to a constant value, as is the usual assumption. Our approach is simpler than matrix analysis. Moreover, it is shown that EADF attains the same rate of convergence with the classical Diffusion (DF) method, exhibiting a better convergence behavior in certain applications (2D-torus) for large number of processors.

Słowa kluczowe

EN

Fourier analysis; load balancing

PL

analiza Fouriera; wyrównywanie obciążenia

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2002
• Tom: Vol. 27, No. 3
• Strony: 129--140
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Karagiorgos G.

autor

Missirlis N. M.

• Department of Informatics and Telecommunications, University of Athens, Panepistimioupolis 157 84, Athens, Greece,