11.4.4.2 : Équilibrage de charge



Dans les calculs où la parallélisation s'effectue par décomposition de domaine, un problème de passage à l'échelle apparaît lorsque le découpage automatique du calcul en blocs ne produit pas des tâches dont la charge de travail est équivalente. On parle de déséquilibre de charge.

Si ce défaut n'est pas corrigé, certains threads ou nœuds termineront leur travail avant les autres, et la performance globale du programme deviendra limitée par l'ensemble moins parallèle des threads qui continuent à travailler. Dans le cadre d'un calcul en plusieurs passes, ce phénomène se reproduira potentiellement à chaque passe, et son effet sera donc décuplé.

Plusieurs approches classiques existent pour régler ce problème~:

  • Lorsque la répartition de la charge de travail est prévisible à l'avance, un algorithme de décomposition de domaine plus astucieux pourra être utilisé pour produire des tâches de difficulté comparable.
  • Dans des systèmes à faible niveau de parallélisme, le découpage du travail en petits blocs et leur insertion dans une file d'attente commune à tous les threads fournira une forme primitive de répartition dynamique du travail entre les threads.
  • À un niveau de parallélisme plus élevé, il faudra faire appel à des algorithmes de répartition du travail plus complexes mais moins riches en synchronisation comme le vol de travail. L'utilisation d'implémentations standardisées comme celle de TBB est alors fortement recommandée.


On le devine, certaines de ces approches sont beaucoup plus faciles à appliquer en présence d'une mémoire partagée que dans un contexte distribué. Les systèmes distribués devront en effet rivaliser d'ingéniosité pour adapter ces algorithmes d'une façon qui ne nécessite pas des communications globales.

Deux approches classiques pour l'équilibrage de charge en calcul distribué sont la nomination d'un réseau hiérarchique de nœuds "maîtres", qui détiennent seuls une vision globale de la charge de travail des nœuds "esclaves" sous leur commandement, et l'échange de travail localisé entre nœuds voisins dans la topologie du réseau utilisé.