Comment accélérer un pipeline ? Qu'est-ce qu'un prédicteur de branchement ?

Introduction

Comme on a vu dans le dernier cours sur les systèmes embarqués, le pipeline permet de lancer une instruction par cycle. Néanmoins l’utilisation d’un pipeline peut avoir différents aléas :

aléa de données : donnée non disponible à cause de la latence du pipeline
aléa de contrôle : délai lors de l’exécution d’une instruction de branchement/saut
aléa de structure : conflit pour l’accès à une ressource matérielle

Les aléas de données

Les aléas de données arrivent quand la valeur que l’on souhaite récupérer n’est pas disponible ou que l’on obtient une ancienne valeur de la variable que l’on souhaite récupérer et non la nouvelle valeure calculé.

Donnée non disponible

Mais quand la donnée n’est pas disponible dans le processeur, les aléas de données ne peuvent être résolus par des court-circuits.
— Lecture mémoire
— opérations en plusieurs cycles (flottant)

On opére alors une suspension du pipeline (bubble ou pipeline stall)

En pratique, pour une suspension :
— on fige le pipeline pour les étages LI et DI (pas d’écriture des registres
pipeline)
— on injecte un nop dans le registre LR/EX

Latence de donnée

En décomposant les instructions dans chaque étage, il se peut que les données dont on a besoin ne soit pas encore disponible du fait qu’elle est traité dans le cycle suivant par exemple. Ceci s’appelle une latence de cycle ou délai de chargement de cycle.

Voici un exemple de latence :

li	di	ex	mm	rr
	li	di	ex	mm	rr
		li	di	ex	mm	rr

Ici on peut voir que si « mm » de la première ligne souhaite avoir la nouvelle valeur de « ex », alors il va devoir attendre deux cycles.

Les opérations entières complexes (multiplication/division) et les opérations flottantes ont souvent une latence de plusieurs cycles.

Les aléas de données entraînent alors un délai d’attente et donc on perds l’intérêt d’un pipeline.

C’est pour cela que certaine opérations ne sont pas pipeliné, notamment les divisions.

Les dépendances

La dépendance est la contrainte de séquentialité entre instructions qui lisent ou écrivent une donnée dans un même registre.

Il y a différent type de dépendances :

Dépendance de données (read-after-write) : L’instruction i écrit le registre r et l’instruction i + n lit r
Dépendance de nom (write-after-read) : L’instruction i lit la donnée dans r et l’instruction i+ n génère une nouvelle valeur dans r
Dépendance de sortie (write-after-write) : Les instructions i et i + n génèrent une information dans le même registre r.

On va donner un exemple de dépendance entre plusieurs registres :

add r1,r2,r3
add r4, r1, r5
add r1, r6, r7
add r1, r8, r9
add r10,r1,r11

dépendance de donnée : L’information dans r1 est utilisée par l’instruction 2 . C’est une vraie dépendance de donnée qui doit être respectée.
dépendance de nom : Le registre r1 est écrit par l’instruction 3 et l’instruction 2 doit lire son contenu avant. Par contre, il suffit d’utiliser un autre registre que r1 pour que le problème disparaisse.
dépendance de sortie : Les instructions 3 et 4 écrivent successivement le registre r1. L’ordre des écritures doit être respecté.

Interruption sur les pipelines

Comme sur les fonctions, il existe aussi des interruptions sur les pipelines. On va voir comment les gérer.

L’exécution d’un programme peut être interrompue par :

un événement extérieur (interruption)
un problème interne au processeur (exception) (erreur arithmétique (÷0), problème d’accès mémoire (erreur du bus))…

Pour une exception propre :

toutes les instructions avant celle qui a provoqué l’exception doivent se terminer
aucune instruction suivant celle qui a provoqué l’exception ne doit se terminer

Il y a plusieurs façon de traiter les interruptions dans un pipeline :

Terminaison dans l’ordre des instructions : Une instruction multi-cycles oblige toutes les instructions suivantes à attendre pour se terminer, même s’il n’y pas de dépendances de données ou si elles ne provoquent pas d’exceptions.
Terminaison non ordonnées des instructions : Sans dépendance de données, si on autorise les instructions suivantes à se terminer, elles vont modifier les registres et donc la mémoire. Des exceptions « propres » sont alors impossibles (les instructions suivant l’exception ne doivent pas terminer).

Exécution « spéculative » des instructions

La dernière façon de traiter les interruptions dans un pipeline est l’exécution spéculative des instructions.

Les instructions peuvent s’exécuter, mais on attend pour modifier l’état du processeur ou de la mémoire.
Pour cela on range temporairement les résultats des instructions et on ne modifie les registres et la mémoire que lorsque l’on est sûr qu’il n’y aura pas d’exception.

Le renommage des registres

Le renommage des registres est aussi utile pour l’exécution spéculative.
Pour cela il y a deux possibilités :

Duplication du banc de registres : Une instruction écrit dans un registre futur et on recopie dans un registre présent quand l’instruction est garantie.
Au lancement de l’instruction, on associe un registre physique à un registre logique avec une table de correspondance (renommage). La recopie du registre physique vers le registre logique se fait quand l’instruction est achevée et garantie.

Augmentation profondeur du pipeline

En ajoutant des étages d’un pipeline, on peut augmenter la fréquence d’horloge (superpipeline). Ceci corresponds à la duplication des étages critiques et l’accroissement de la profondeur du pipeline.

Néanmoins ceci a un coût : Le superpipeline augmente les délais de chargement et de branchement (en cycles) mais permet de réduire le temps de cycle.

Le nombre d’étages de pipeline dépend beaucoup du processeur utilisé :

Architecture Pentium	Pipeline	Architecture Arm	Pipeline
Pentium	5	ARM 1-7	3
Pentium Pro	14	ARM 11	8
Intel Core	14	Cortex A8	13

Aléa de branchement

Une rupture de séquence dans un programme provoque un délai de branchement. Pour supprimer ce temps de branchement, on fait de la prédiction de branchement matériel et de l’ordonnancement des instructions.

Nous allons maintenant voir comment faire de la prédiction de branchement. Pour cela on doit introduire

Il y a différente manière de supprimer le temps prit par le changement de branchement :
— La prédiction de branchement
— L’instructions de transfert conditionnel
— L’ ordonnancement des instructions

La prédiction de branchement

Si on attend d’avoir décodé l’instruction de branchement, on va avoir une pénalité de temps. On va donc supposer dans la prédiction de branchement qu’une instruction de branchement a un comportement souvent répétitif.

De plus on va mémoriser dans une petite mémoire le comportement des instructions de branchement (pris/non pris + adresse cible).

Il y a deux grand types de prédiction :

Prédiction statique (à la compilation)
Prédictions dynamiques (à l’exécution)

Prédiction statique

La prédiction statique est l’information connues à la compilation (boucles, par exemple) grâce au profilage des programmes.

Dans la prédiction statique on suppose le même comportement pour un branchement dans un programme.

Il peut être défini par le matériel ou prédit par le compilateur :

toujours pris
toujours non-pris
branchement arrière pris (avec une boucle while ou boucle for)
branchement avant non pris (avec if then else)

Prédiction dynamique

Les prédictions dynamiques sont faite durant l’exécution du programme.

Il y a deux type prédicteurs dynamique :

Prédicteurs locaux (1 et 2 bits)
Prédicteurs globaux (historique de branchements)

Le Prédicteur 1 bit

Pour ce prédicteur on mémorise l’état pris/non pris pour chaque branchement. Avec ce prédicteur 1 bit on suppose le comportement d’un branchement suffisamment répétitif.

On va maintenant voir un exemple de prédicteur 1 bits.

Dans cet exemple on va alterner les branchements pris puis non pris (P = pris et N = Non pris.). Ceci se trouve sur la première ligne.

La deuxième ligne corresponds aux valeurs du prédicteur.

On va maintenant expliquer la deuxième ligne du prédicteur. Pour le premier branchement, on n’a pas d’historique donc on met un point d’interrogation. Comme le premier branchement était pris, alors le deuxième branchement prédit est aussi pris ce qui n’était pas le bon banchement . (Il faut regarder colonne par colonne)

On peut voir dans les colonnes suivante que le prédicteur se trompe à chaque fois (quand c’est pris le prédicteur prédit non pris et inversement).

A chaque mauvaise prédiction on entoure la mauvaise valeur du prédicteur. On peut donc voir qu’avec un changement de branchement de pris à non pris le prédicteur ne peut pas s’adapter et se trompe à chaque fois.

Conclusion : En changeant de branchement à chaque fois on n’obtient aucune prédiction de bonne avec un prédicteur 1 bit.

On va maintenant voir un autre exemple avec un changement de branchement moins rapide afin de voir si le prédicteur 1 bit est plus performant.