Equilibrage de charge - Lycée la Découverte (Decazeville) Lycée Raymond Savignac (Villefranche de Rouergue)

• Problème général :
▪ on a des processeurs dans un supercalculateur
• un processeur sert à faire des calculs
• tous les processeurs sont identiques
▪ on a des calculs à faire faire aux processeurs
• chaque calcul va prendre un temps plus ou moins long
• on connaît à l’avance la durée d’un calcul
▪ on doit décider de l’affectation des calculs aux
processeurs
• quels calculs va faire chaque processeur
• dans quel ordre chaque processeur doit faire ses calculs

Plusieurs affectations possibles
• C1 et C2 sur P1, C3 et C4 sur P2
• C1, C2, C3 sur P1, C4 sur P2
• C1, C3 sur P1, C2, C4 sur P2
• C3 sur P1, C1, C2, C4 sur P2
• Etc.
• (Il y a beaucoup de possibilités !)
• (Combien d’ailleurs ?...)

Ce qu’on aimerait
• On aimerait que le dernier calcul se finisse le plus tôt
possible
• Exemple :
▪ C1 (4 minutes) et C2 (5 minutes) sur P1 : fini dans 9
minutes
▪ C3 (10 minutes) et C4 (2 minutes) sur P2 : fini dans 12
minutes
▪ le dernier calcul est donc fini au bout de 12 minutes
▪ peut-on finir plus tôt ?
• Si oui, quand ? Si non, pourquoi ?

Ce qu’on aimerait par-dessus
tout
• Une méthode générale pour déterminer la meilleure
affectation possible (on appelle cela un algorithme
en fait…)
• Si on a un nombre quelconque de processeurs
• Si on a un nombre quelconque de tâches, de durées
quelconques