Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Architecture des ordinateurs

Parallélisme au niveau des instructions : dépendances et renommage des registres

Dépendances vraies, anti et de sortie, renommage des registres avec démonstration, équation des performances avec arrêts, déroulage de boucles, limites de l'ILP.

https://www.electronics-engineering.com/fr/parallelisme-instructions-dependances-renommage-registres/

Pas encore de vote : soyez le premier à noter cette page.

Le cours de Systèmes d’élaboration a montré le pipeline à cinq étages, qui recouvre l’exécution d’instructions successives. Mais un pipeline simple atteint au plus une instruction par cycle, et s’arrête chaque fois qu’une instruction attend le résultat d’une autre. Pour aller plus loin, il faut comprendre quelles instructions peuvent vraiment être exécutées ensemble. Dans cette leçon, nous classons les dépendances, nous démontrons que seules les vraies limitent le parallélisme alors que les autres sont éliminées par le renommage des registres, nous écrivons l’équation des performances avec arrêts et nous regardons le déroulage de boucles.

Le parallélisme au niveau des instructions

Le parallélisme au niveau des instructions (ILP) est la possibilité d’exécuter en même temps plusieurs instructions d’un même programme séquentiel. Le programmeur écrit une suite ; le processeur doit garantir que le résultat est le même que celui d’une exécution une instruction à la fois, mais il est libre de changer l’ordre et de recouvrir tout ce qui ne change pas le résultat.

Les dépendances

Entre deux instructions, I_i précédant I_j dans le programme, il y a trois types de dépendance de registres :

  • la dépendance vraie ou de données (RAW, read after write) : I_j lit un registre écrit par I_i. La valeur doit passer de l’une à l’autre : I_j ne peut pas calculer avant que I_i ait produit son résultat ;
  • l’anti-dépendance (WAR, write after read) : I_j écrit un registre que I_i lit. Si I_j écrivait la première, I_i lirait la mauvaise valeur ;
  • la dépendance de sortie (WAW, write after write) : les deux écrivent le même registre. À la fin, la valeur de I_j doit rester.

S’y ajoutent les dépendances de contrôle, sur les branchements conditionnels, et les dépendances à travers la mémoire, plus difficiles à voir parce que les adresses ne sont connues que pendant l’exécution.

Graphe des dépendances entre quatre instructions
Les flèches rouges sont des dépendances vraies (lecture après écriture), qui obligent à attendre le résultat. La flèche bleue est une anti-dépendance et l’orange une dépendance de sortie : elles naissent seulement de la réutilisation du registre r1 et disparaissent quand on le renomme.

Dépendances vraies et dépendances de nom

Les anti-dépendances et les dépendances de sortie ne transportent aucune donnée : elles existent seulement parce que deux valeurs différentes utilisent le même nom de registre. Dans l’exemple de la figure, I_3 réutilise r_1 pour une valeur qui n’a rien à voir avec celle de I_1.

Théorème. Si chaque instruction écrit son résultat dans un nouveau registre physique, jamais utilisé auparavant, et si chaque lecture se réfère au registre physique de la dernière écriture précédente dans le programme, les dépendances WAR et WAW disparaissent et il ne reste que les RAW.

Démonstration. Une WAW demande deux écritures dans le même registre : avec un nouveau registre physique pour chaque écriture, il n’y en a aucune. Une WAR demande que I_j écrive un registre que I_i lit ; mais I_i lit le registre physique de l’écriture qui précède I_i, tandis que I_j écrit un nouveau registre, différent de tous les existants, donc différent de celui qui est lu. Enfin, chaque lecture trouve la valeur de l’écriture qui la précède dans le programme, c’est-à-dire la même valeur que dans l’exécution séquentielle : le résultat ne change pas. ∎

C’est le renommage des registres. Le processeur a beaucoup plus de registres physiques (des centaines) que de registres architecturaux visibles pour le programmeur (32 en RISC-V), et une table d’alias des registres (RAT) qui dit, pour chaque registre architectural, quel registre physique contient la valeur la plus récente. Dans l’exemple, après renommage, I_3 et I_1 sont indépendantes et peuvent être exécutées ensemble : il ne reste que les flèches rouges.

L’équation des performances avec arrêts

Le temps d’exécution est T = N_I\cdot CPI\cdot T_{clk} (leçon sur von Neumann et les performances). Dans un pipeline, le CPI idéal est 1, et chaque arrêt l’augmente :

    \[ CPI = CPI_{ideal} + \sum_k f_k\,p_k \]

où f_k est la fréquence (par instruction) d’un certain type d’aléa et p_k le nombre de cycles perdus chaque fois. Par exemple, si 25 % des instructions sont des chargements depuis la mémoire et que la moitié d’entre eux sont immédiatement suivis d’une instruction qui utilise la donnée, avec un cycle perdu chaque fois, la contribution est 0.25\cdot 0.5\cdot 1 = 0.125 : le CPI passe de 1 à 1,125, et le processeur est 12,5 % plus lent.

Le déroulage de boucles

Le compilateur peut augmenter l’ILP disponible. Considérons une boucle qui ajoute une constante à chaque élément d’un tableau : chaque itération charge, additionne, écrit, incrémente l’indice et branche. Les trois instructions utiles dépendent les unes des autres, et il reste entre elles des cycles vides, à attendre des résultats.

En déroulant la boucle quatre fois, c’est-à-dire en écrivant quatre itérations dans le corps avec des registres différents, on obtient quatre chaînes indépendantes. Le compilateur les entrelace : pendant que la première addition attend son chargement, on exécute les chargements des trois autres. Les cycles vides disparaissent, et l’incrément de l’indice et le branchement, exécutés une fois tous les quatre éléments au lieu de chaque élément, pèsent quatre fois moins. Le prix est un code plus long et plus de registres utilisés. Les compilateurs le font automatiquement avec les options d’optimisation, et la même idée est à la base de la vectorisation (leçon sur le SIMD et les GPU).

Combien d’ILP y a-t-il vraiment

Les études sur des processeurs idéaux, à unités infinies et prédiction parfaite, trouvent des dizaines d’instructions exécutables en parallèle dans les programmes courants. Les processeurs réels, limités par la prédiction, les fenêtres et la mémoire, en exploitent de 2 à 5 par cycle. Les leçons suivantes montrent les techniques qui s’en approchent : l’exécution dans le désordre, la prédiction des branchements, les processeurs superscalaires.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x