Ordonnancement de t ches dans un milieu h t rog ne

Cette conférence traite de l'ordonnancement de tâches indépendantes dans un environnement hétérogène, c’est-à-dire sur plusieurs processeurs ayant des vitesses différentes. Elle s’inscrit dans un cours d’informatique ou d’ingénierie des systèmes, abordant les méthodes et algorithmes visant à minimiser le temps total d’exécution (makespan) en équilibrant la charge entre processeurs.

Contexte et objectifs de l’ordonnancement en milieu hétérogène

L’ordonnancement de tâches indépendantes en milieu hétérogène (OTIMHTR) concerne la répartition de n tâches indépendantes, chacune ayant un coût d’exécution cj, sur p processeurs de vitesses différentes v1, v2, … vp. L’objectif principal est d’équilibrer la charge de travail afin de minimiser le makespan, c’est-à-dire le temps total nécessaire pour terminer toutes les tâches.

Le makespan est défini comme le maximum des charges pondérées des processeurs, où la charge pondérée CHPi d’un processeur Pi est la somme des coûts des tâches qui lui sont affectées divisée par sa vitesse vi :

CHPi = (Σ cj) / vi

Le makespan M(p) est donc :

M(p) = max(CHPi) pour i = 1..p

Principes d’ordonnancement

Deux principes fondamentaux guident l’allocation des tâches aux processeurs :

• Principe 1 : Affecter la tâche courante au processeur dont la charge pondérée (CHP) est la plus faible. En cas d’égalité, on choisit le processeur le plus rapide.
• Principe 2 : Affecter la tâche au processeur qui la terminera le plus rapidement, en comparant les charges pondérées résultantes si la tâche était affectée à chaque processeur.

Algorithmes d’ordonnancement

Trois algorithmes itératifs sont présentés, chacun avec deux versions selon le principe appliqué :

• LS (List Scheduling) : les tâches sont prises dans l’ordre naturel 1...n.
• SPT (Shortest Processing Time) : les tâches sont triées par coût croissant.
• LPT (Longest Processing Time) : les tâches sont triées par coût décroissant.

Chaque algorithme a une version 1 (basée sur le principe 1) et une version 2 (basée sur le principe 2), donnant six versions au total : LS-1, LS-2, SPT-1, SPT-2, LPT-1, LPT-2.

Exemple d’application des algorithmes LS-1, SPT-1 et LPT-1

Considérons 8 tâches avec les coûts suivants : 4, 6, 3, 10, 7, 3, 8, 3, à ordonnancer sur 2 processeurs P1 et P2 avec vitesses v1 = 1 et v2 = 1/2.

Les résultats des makespans sont :

• LS-1 : M(2) = 32
• SPT-1 : M(2) = 38
• LPT-1 : M(2) = 30

LPT-1 est le plus performant dans cet exemple.

Lors de l’allocation, si deux processeurs ont la même charge pondérée, on choisit le plus rapide. Par exemple, pour la tâche de coût 4, les charges sont égales, donc on choisit P1.

Heuristique d’amélioration par transfert de tâches

Une méthode d’amélioration consiste à transférer une tâche d’un processeur à un autre pour réduire le makespan. Par exemple, dans SPT-1, transférer une tâche de coût 3 de P2 vers P1 réduit le makespan de 38 à 32.

On calcule la différence d entre la charge maximale et la charge minimale des processeurs :

d = max CHP - min CHP

On choisit alors une tâche à transférer du processeur le plus chargé vers le moins chargé afin de minimiser d.

Comparaison des versions 1 et 2 des algorithmes

Les versions 2, basées sur le principe 2, sont généralement plus performantes :

• LS-2 est meilleur que LS-1.
• SPT-2 est meilleur que SPT-1.
• LPT-2 a le même makespan que LPT-1 mais offre un meilleur équilibrage de charge.

Le principe 2 est donc plus pertinent dans un contexte hétérogène, car il permet d’éliminer les processeurs les plus lents au début ou au milieu de l’ordonnancement, évitant ainsi qu’ils ralentissent l’exécution globale.

Exemple illustrant l’élimination d’un processeur lent

Considérons 2 processeurs P1 (v1=1) et P2 (v2=1/5) et 2 tâches de coûts 10 et 5 :

• Si on affecte la tâche de coût 10 à P1 et celle de coût 5 à P2, le makespan est :

M(2) = max(10/1, 5/(1/5)) = max(10, 25) = 25

• Si on affecte les deux tâches à P1, on obtient :

M(1) = (10 + 5) / 1 = 15

Le makespan est plus faible en utilisant un seul processeur, ce qui signifie que P2, le processeur plus lent, sera éliminé dès le début car son utilisation ralentit l’exécution.

Généralisation du principe d’élimination

Pour p=2 processeurs P1 et P2 avec v1 > v2 et n tâches de coûts c1,..., cn :

• Si on affecte la tâche tq de coût cq = min(ci) à P2 et le reste à P1, alors :

M(2) = max((Σ ci - cq) / v1, cq / v2)

• Si on affecte toutes les tâches à P1 :

M(1) = (Σ ci) / v1

Si M(2) > M(1), alors P2 sera éliminé dès le début.

Pour p=3 processeurs avec v1 > v2 ≥ v3 et n tâches triées par coût décroissant c1 ≥ c2 ≥ ... ≥ cn :

• Si on affecte la tâche de coût cn à P3, celle de coût c(n-1) à P2, et le reste à P1 :

M(3) = max((Σ ci - cn - c(n-1)) / v1, c(n-1) / v2, cn / v3)

• Si on affecte toutes les tâches à P1 :

M(1) = (Σ ci) / v1

Si M(3) > M(1), alors P2 et P3 seront éliminés dès le début.

Points clés

• L’ordonnancement en milieu hétérogène vise à minimiser le makespan en équilibrant la charge pondérée sur des processeurs de vitesses différentes.
• La charge pondérée d’un processeur est la somme des coûts des tâches qui lui sont affectées divisée par sa vitesse.
• Deux principes d’allocation : affecter la tâche au processeur le moins chargé (principe 1) ou à celui qui la terminera le plus vite (principe 2).
• Trois algorithmes principaux (LS, SPT, LPT) avec deux versions selon le principe appliqué.
• Le principe 2 donne généralement de meilleurs résultats, notamment en éliminant les processeurs trop lents qui ralentiraient l’exécution.
• Une heuristique d’amélioration consiste à transférer des tâches entre processeurs pour réduire le makespan.
• Dans certains cas, utiliser moins de processeurs est plus efficace que d’utiliser tous les processeurs disponibles.