Abstract
This paper is devoted to static load balancing techniques for mapping iterative algorithms onto heterogeneous clusters. The application data is partitioned over the processors. At each iteration, independent calculations are carried out in parallel, and some communications take place. The question is to determine how to slice the application data into chunks, and to assign these chunks to the processors, so that the total execution time is minimized. We establish a complexity result that assesses the difficulty of this problem, and we design practical heuristics that provide efficient distribution schemes.
Chapter PDF
Similar content being viewed by others
References
Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. The MIT Press, Cambridge (1990)
Culler, D.E., Singh, J.P.: Parallel Computer Architecture: A Hardware/Software Approach. Morgan Kaufmann, San Francisco (1999)
Feautrier, P.: Parametric integer programming. RAIRO Recherche Opérationnelle 22, 243–268 (1988),Software available at http://www.prism.uvsq.fr/~cedb/bastools/piplib.html
Feautrier, P., Tawbi, N.: Résolution de systèmes d’inéquations linéaires; mode d’emploi du logiciel PIP. Technical Report 90-2, Institut Blaise Pascal, Laboratoire MASI (Paris) (January 1990)
Foster, I., Kesselman, C. (eds.): The Grid: Blueprint for a New Computing Infrastructure. Morgan-Kaufmann, San Francisco (1999)
Garey, M.R., Johnson, D.S.: Computers and Intractability, a Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1991)
Helsgaun, K.: An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research 126(1), 106–130 (2000), Software available at http://www.dat.ruc.dk/~keld/research/LKH/
Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling salesman problem. Operations Research 21, 498–516 (1973)
Renard, H., Robert, Y., Vivien, F.: Static load-balancing techniques for iterative computations on heterogeneous clusters. Research Report RR-2003-12, LIP, ENS Lyon, France (February 2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Renard, H., Robert, Y., Vivien, F. (2003). Static Load-Balancing Techniques for Iterative Computations on Heterogeneous Clusters. In: Kosch, H., Böszörményi, L., Hellwagner, H. (eds) Euro-Par 2003 Parallel Processing. Euro-Par 2003. Lecture Notes in Computer Science, vol 2790. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45209-6_24
Download citation
DOI: https://doi.org/10.1007/978-3-540-45209-6_24
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40788-1
Online ISBN: 978-3-540-45209-6
eBook Packages: Springer Book Archive