Static load-balancing techniques for iterative computations on heterogeneous clusters

Hélène Renard (1) , Yves Robert (2) , Frédéric Vivien (2)

1 REMAP - Regularity and massive parallel computing
2 LIP - Laboratoire de l'Informatique du Parallélisme

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 calculation- s 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.

Ce rapport est consacré à l’ équilibrage de charge pour algorithmes itératifs sur plateformes hétérogènes. Les données sont réparties sur l’ensemble des ressources à chaque itération, les calculs indépendants sont transmis en parallèle et les communications ont lieu. Le problème est de déterminer comment partitionner les données et comment les répartir sur les ressources pour que le temps total d’exécution soit minimal. Nous avons démontré un résultat de complexité qui établit la difficulté de ce problème, et nous proposons des heuristiques pratiques qui prouvent l’efficacitéé de la distribution.

Mots clés: STATIC LOAD-BALANCING TECHNIQUES; COMMUNICATION; COMPLEXITY; HETEROGENEOUS CLUSTERS

Mots clés: GRAPPES HETEROGENES; EQUILIBRAGE DE CHARGE; COMMUNICATIONS; COMPLEXITE

Domaines: Autre [cs.OH]

Hélène Renard, Yves Robert, Frédéric Vivien. Static load-balancing techniques for iterative computations on heterogeneous clusters. [Research Report] RR-4745, LIP RR-2003-12, INRIA, LIP. 2003. ⟨inria-00071842⟩