Ordonnancement des instructions (instruction scheduling) ------------------------------- Source du problème: ------------------ Les processeurs modernes disposent d'un certain degré de parallélisme dans l'exécution des instructions: l'exécution de deux instructions peut se recouvrir partiellement. [Référence: J. Hennessy et D. Patterson, "Computer architecture: a quantitative approach".] Exemple: le résultat d'un load n'est pas disponible immédiatement, mais dans le cycle suivant on peut quand même lancer une nouvelle instruction. r1 <- load(r2) versus r3 <- r4 + r5 r3 <- r4 + r5 r1 <- load(r2) r1 <- r1 + r3 r1 <- r1 + r3 (bloque - stalling) On peut lancer une instruction [ou plus] à chaque cycle, mais certaines instructions prennent plusieurs cycles à s'exécuter. 1ière source de parallélisme: les unités de calcul multiples qui peuvent opérer en parallèle: Presque tous les chips: une unité arithmétique entière + une unité flottante Le R3000: une unité entière + une unité flottante + un multiplieur / diviseur Le PowerPC 604: deux unités entières + un multiplieur / diviseur + une unité flottante + une unité load/store Un processeur superscalaire peut lancer plusieurs instructions par cycles si elles occupent des unités de calcul différentes. 2ième source de parallélisme: le pipeline Plusieurs étapes mises en série, pouvant travailler à la chaîne. Exemple: addition flottante chargement alignement addition normalisation écriture opérandes des args du résultat du résultat -> 5 cycles. Mais on peut démarrer une nouvelle addition à chaque cycle, pourvu qu'elle n'utilise pas les résultats d'une instruction précédente. Exemple: r2 <- r2 + r1 r3 <- r3 + r1 En fait: existence d'un raccourci [bypass] pour court-circuiter l'étape écriture résultat / chargement opérande. r2 <- r2 + r1 D'où latence de 3 cycles au plus. Sur un processeur moderne, presque toutes les opérations arithmétiques sont ``fully pipelined'', c.à.d. qu'on peut lancer une nouvelle opération à chaque cycle, même si chaque opération prend plusieurs cycles. Les principales exceptions sont: division entière et flottante (algorithme essentiellement itératif), et sur les processeurs plus anciens, multiplication entière et flottante. Que se passe-t'il si une instruction B essaye d'accéder au résultat d'une autre instruction A qui est encore en cours de calcul? - Sur la plupart des processeurs: le processeur bloque (ne lance pas l'instruction B ni les suivantes) et attend que A ait terminé - Sur les processeurs permettant le réordonnancement au vol des instructions (out-of-order execution): l'instruction B est mise en attente, mais le processeur essaye de lancer les instructions qui suivent B (si leurs arguments sont disponibles). - Sur certains processeurs anciens (MIPS, Intel 860): B s'exécute avec l'ancienne valeur du registre résultat de A (notion de delay slot): r1 <- 0 r1 <- load r2 r3 <- r1 + 1 # s'exécute avec r1 = 0 r4 <- r1 + 1 # s'exécute avec r1 = le mot à l'adresse r2 C'est la responsabilité du compilateur de mettre après le "load" ou bien une instruction qui ne dépend pas du résultat du load, ou bien une instruction "nop". Dans le même ordre d'idée, certains processeurs anciens (MIPS, SPARC, HPPA) ont un "delay" slot après les instructions de branchement: l'instruction qui suit immédiatement le branchement est toujours exécutée. L'ordonnancement des instructions --------------------------------- Consiste à réordonner les instructions pour tirer parti du parallélisme interne au processeur, c.à.d. pour réduire les cycles bloqués passés à attendre un résultat. - Ordonnancement statique: au moment de la production du code - Ordonnancement dynamique: certains processeurs réordonnent "à la volée" les instructions à exécuter (out-of order execution, par opposition au in-order execution). Ordonnancement d'un bloc de base: --------------------------------- Un bloc de base est une suite d'instructions toujours exécutées en séquence: - pas de branchements conditionnels (sauf évt. la dernière instruction) - le seul point d'entrée est au début Dans le graphe de flot, c'est un chemin tel que: - les noeuds intermédiaires ont exactement 1 arc entrant et 1 arc sortant - le 1ier noeud peut avoir plusieurs arcs entrants - le dernier noeud peut avoir plusieurs arcs sortants On construit le DAG de dépendences de données associé au bloc de base: - noeuds = instructions du bloc de base - arcs: A --> B étiqueté l signifiant que B ne peut pas démarrer avant que l cycles se soient écoulés depuis le démarrage de A. Pour chaque paire d'instructions (A, B), A précédant B dans le bloc de base, le DAG contient les arcs suivants: Arcs du 1ier type (vraies dépendances de données): un des arguments de B est un des résultats de A (Read After Write). l est la latence de l'opération A. Exemples de latences (Dec Alpha 21164): additions, soustractions, comparaisons entières 1 cycle loads 2 cycles (plus si accès hors du cache) additions, soustractions, multiplications flottantes 4 cycles multiplications entières 12 cycles divisions flottantes 15-60 cycles Arcs du 2ieme type (fausses dépendances introduites par les registres): A et B ont un registre résultat en commun (Write After Write) ou un des résultats de B est argument de A (Write After Read). On prend l=1. Arcs du 3ieme type (dépendances sur la mémoire): A est un store et B un load, ou A et B sont deux stores, et on ne peut pas prouver que les adresses accédées sont différentes. On prend l=1. Exemple: le coeur d'un produit de matrices a[i] = a[i] + b[j] * c[k] r1 <- a + i * 8 f1 <- load r1 r2 <- b + j * 8 f2 <- load r2 r3 <- c + k * 8 f3 <- load r3 f4 <- f2 * f3 f5 <- f1 + f4 r1 <- a + i * 8 store f5, r1 Algorithme glouton d'ordonnancement: On dit qu'une instruction B est activable à la date t si pour tout arc A --l--> B, A a déjà été émise à la date t-l. t = 0 répéter tant que toutes les instructions n'ont pas été émises: * déterminer les instructions activables à la date t * si au moins une est activable: choisir une instruction activable (ou plusieurs instructions exécutables simultanément) et l'émettre * faire t <- t + 1 fin Algorithme en temps linéaire. Efficacité: si on émet 1 instruction par cycle on a M unités de calcul chaque unité a une latence de K alors T(glouton) / T(optimal) <= 2 - 1/MK E.g. M = 1, K = 2 --> T(glouton) <= 1.5 T(optimal) Au pire, T(glouton) <= 2 T(optimal). Choix d'une instruction à émettre parmi les instructions activables: 1- Prendre en compte les contraintes du processeur Ex: ne pas émettre une instruction qui a besoin d'une ressource occupée par une autre instruction en cours d'exécution, e.g. l'unité multiplieur / diviseur. Sur les processeurs superscalaires, plusieurs instructions peuvent être émises simultanément, sous réserve de respecter les contraintes structurelles du processeur. Exemple (Dec Alpha 21064): A B opérations entières opération flottante load/store flottant load/store entier branchement cond. flottant branchement inconditionnel ou conditionnel entier On peut exécuter simultanément une instruction du type A et une du type B, avec au plus un load/store ou un branchement par paire d'instruction. 2- Prendre en compte la structure du DAG de dépendences: a- Favoriser les instructions à plus grande distance du résultat d(A) = max { d(B) + l | A -l-> B est un arc de dépendence } La distance correspond au temps nécessaire pour faire le calcul si le processeur disposait d'un parallélisme illimité. C'est la notion de chemin critique en ordonnancement classique. b- Favoriser les instructions qui ont plus de successeurs dans le graphe de dépendences (vont débloquer plus de calculs) Interférences avec l'allocation de registres: --------------------------------------------- * Si on fait l'ordonnancement après l'allocation de registres, on peut se heurter à de fausses dépendences (RAW ou WAW) introduites par une mauvaise affectation de registres Ex: r1 <- load(r0) store(r1, r2) r3 <- load(r0+4) store(r3, r2+4) Si r1 et r3 sont mis dans le même registre physique, on ne peut pas produire le meilleur ordonnancement (load, load, store, store). Certains processeurs font du renommage de registres à la volée pour éviter les dépendances RAW ou WAW (register renaming). * Si on fait l'ordonnancement avant l'allocation de registres, on peut augmenter les besoins en registres et provoquer du spilling. Ex: r2 <- load(r0) Après r2 <- load(r0) r1 <- r1 + r2 scheduling r3 <- load(r0+4) r3 <- load(r0+4) r4 <- load(r0+8) r1 <- r1 + r3 r1 <- r1 + r2 r4 <- load(r0+8) r1 <- r1 + r3 r1 <- r1 + r4 r1 <- r1 + r4 S'évalue en 3 registres Nécessite 5 registres (r0, r1, et les autres) (si r0 reste vivant) Ordonnancement en présence de branchements (sans cycles): trace scheduling -------------------------------------------------------------------------- On a un graphe de contrôle acyclique. On s'appuie sur des heuristiques ou des mesures expérimentales pour choisir un chemin le plus fréquemment pris à travers le graphe. On ordonnance sur ce chemin comme précédemment. On insère du code sur les arcs qui sortent ou rejoignent le chemin pour compenser l'effet du déplacement d'instructions. Les 4 cas de compensation. Ordonnancement de boucles simples: software pipelining ------------------------------------------------------ loop A; B; C end A, B, C dépendent l'une de l'autre et doivent être exécutées en séquence. Idée: recouvrir plusieurs exécutions de la boucle. Si pas de dépendences entre deux itérations successives et ressources suffisantes: A1 B1 C1 A2 B2 C2 A3 B3 C3 A4 B4 C4 ..... On voit apparaître un motif (C|B|A) et on produit une boucle modifiée de la forme: A1 B1 loop C(i) end A2 B(i+1) C(n+1) A(i+2) B(n+2) C(n+2) Exemple: boucle A[i] = A[i] * c Avant pipelining: L: f1 <- load r1 f2 <- f1 * fc # bloque pendant 1 cycle sur f1 store f2, r1 # bloque pendant 3 cycles sur f2 r1 <- r1 + 8 branchif r1 < r2, L Apres pipelining: L: store f2, r1 # stocker A[i] f2 <- f1 * fc # calculer A[i+1] * c f1 <- load r1 + 16 # charger A[i+2] r1 <- r1 + 8 branchif r1 < r2, L Plus aucun blocage. Remarque: c'est plus fin et plus efficace que ce qu'on peut obtenir par déroulement de la boucle. Après déroulement 2 fois: L: f1 <- load r1 f2 <- f1 * fc store f2, r1 f3 <- load r1+8 f4 <- f3 * fc store f4, r1+8 r1 <- r1 + 16 branchif r1 < r2, L on peut obtenir le schedule suivant: L: f1 <- load r1 f3 <- load r1+8 f2 <- f1 * fc f4 <- f3 * fc store f2, r1 # bloque pendant 2 cycles store f4, r1+8 # bloque pendant 2 cycles r1 <- r1 + 16 branchif r1 < r2, L Il faut dérouler 4 fois pour faire disparaître les délais multiplication/store.