Travaux Dirigés Pipeline

Ce document présente un exercice d’analyse du comportement d’un code MIPS pipeliné, évaluant la compréhension des mécanismes de pipeline, de gestion des branchements et des dépendances dans un processeur MIPS à 5 étages. L’exercice demande de construire le diagramme d’exécution des instructions pour différentes conditions de branchement et de calculer le nombre de cycles nécessaires.

Exercice

Le code MIPS donné teste si un arbre trie est un DAG, en parcourant un tableau de nœuds et en vérifiant certaines conditions sur les champs gauche et droite. Le processeur est pipeliné sur 5 étages, avec résolution des aléas de structure et unités de forwarding. Les branchements conditionnels sont prédits et résolus à l’étage EX.

Question 1 : Diagramme d’exécution et nombre de cycles pour une itération de boucle selon différents cas de branchement

Il s’agit de représenter, pour une seule itération de la boucle, le déroulement des instructions dans le pipeline (diagramme d’exécution) et de calculer le nombre de cycles consommés selon quatre cas différents, liés aux conditions des instructions beq (I4, I6, I7).

Rappel du code pertinent dans la boucle :

• I2 : beq $t0, $a1, done
• I3 : lw $t1, 0($a0)
• I4 : beq $t1, $0, next
• I5 : lw $t2, 4($a0)
• I6 : beq $t2, $0, next
• I7 : beq $t1, $t2, true
• I8 : addi $a0, $a0, 8
• I9 : addi $t0, $t0, 1
• I10 : j loop

Les branchements sont résolus à l’étage EX (3e cycle d’exécution de l’instruction). La prédiction est prise en compte, donc en cas de branchement pris, on peut avoir un flush des instructions incorrectes.

Cas 1 : Condition vérifiée de beq 1 (instruction I4)

Dans ce cas, la condition de I4 est vraie, donc le branchement est pris à I4. Les instructions suivantes dans la séquence normale (I5, I6, I7, ...) ne sont pas exécutées.

Déroulement :

• I1 commence au cycle 1 (IF)
• I2 au cycle 2, I3 au cycle 3, I4 au cycle 4
• I4 est une beq prise, résolue à l’étage EX (cycle 6 de l’instruction I4)
• Les instructions après I4 qui auraient été chargées en IF et ID sont annulées (flush)
• Le pipeline doit attendre la résolution du branchement pour charger la bonne instruction cible (label next)

Instruction	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
I1	IF	ID	EX	MEM	WB
I2		IF	ID	EX	MEM	WB
I3			IF	ID	EX	MEM	WB
I4				IF	ID	EX	MEM	WB
I5					IF (flush)
I6
I7
I8						IF	ID	EX	MEM	WB
I9							IF	ID	EX	MEM	WB
I10								IF	ID	EX	MEM	WB

Explication :

• Le branchement I4 est résolu à EX (cycle 6 de I4), donc les instructions chargées en IF et ID après I4 (I5, I6, I7) sont annulées.
• Le pipeline doit attendre la résolution pour charger la bonne instruction (I8).
• Le flush entraîne un retard de 2 cycles (IF et ID des instructions annulées).
• Le total de cycles pour cette itération est donc 11 cycles (de cycle 1 à 11).

Nombre de cycles : 11

Cas 2 : Condition non vérifiée de beq 1 (I4) et condition vérifiée de beq 2 (I6)

Dans ce cas, I4 est fausse, donc on continue, I5 est exécutée, puis I6 est vraie (branche prise). Les instructions après I6 (I7, I8, ...) ne sont pas exécutées.

Instruction	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
I1	IF	ID	EX	MEM	WB
I2		IF	ID	EX	MEM	WB
I3			IF	ID	EX	MEM	WB
I4				IF	ID	EX	MEM	WB
I5					IF	ID	EX	MEM	WB
I6						IF	ID	EX	MEM	WB
I7							IF (flush)
I8
I9
I10

Explication :

• I6 est résolue à l’étage EX (cycle 8 de I6), donc les instructions chargées après I6 (I7, I8, ...) sont annulées.
• Le flush provoque un retard de 2 cycles.
• Le total de cycles pour cette itération est donc 13 cycles (de cycle 1 à 13).

Nombre de cycles : 13

Cas 3 : Condition non vérifiée de beq 1 (I4) et de beq 2 (I6), condition vérifiée de beq 3 (I7)

Dans ce cas, les deux premiers branchements sont faux, donc I4 et I6 ne provoquent pas de branchement, mais I7 est vrai. Le branchement I7 est pris.

Instruction	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
I1	IF	ID	EX	MEM	WB
I2		IF	ID	EX	MEM	WB
I3			IF	ID	EX	MEM	WB
I4				IF	ID	EX	MEM	WB
I5					IF	ID	EX	MEM	WB
I6						IF	ID	EX	MEM	WB
I7							IF	ID	EX	MEM	WB
I8								IF (flush)
I9
I10

Explication :

• I7 est résolue à EX (cycle 9 de I7), donc les instructions chargées après I7 (I8, I9, I10) sont annulées.
• Le flush provoque un retard de 2 cycles.
• Le total de cycles pour cette itération est donc 15 cycles (de cycle 1 à 15).

Nombre de cycles : 15

Cas 4 : Condition non vérifiée de beq 1, 2 et 3 (I4, I6 et I7)

Dans ce cas, aucun des trois branchements n’est pris. Toutes les instructions de la boucle sont exécutées normalement.

Instruction	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
I1	IF	ID	EX	MEM	WB
I2		IF	ID	EX	MEM	WB
I3			IF	ID	EX	MEM	WB
I4				IF	ID	EX	MEM	WB
I5					IF	ID	EX	MEM	WB
I6						IF	ID	EX	MEM	WB
I7							IF	ID	EX	MEM	WB
I8								IF	ID	EX	MEM	WB
I9									IF	ID	EX	MEM	WB
I10										IF	ID	EX	MEM	WB

Explication :

• Toutes les instructions sont exécutées sans flush ni stall.
• Le pipeline fonctionne en continu, chaque instruction entrant à chaque cycle.
• Le nombre de cycles est égal au nombre d’instructions plus le pipeline initial (5 cycles pour la première instruction).
• Il y a 10 instructions dans la boucle (I1 à I10), donc 10 + 4 = 14 cycles (car la première instruction met 5 cycles, et chaque instruction suivante arrive à chaque cycle).

Nombre de cycles : 14

Méthode

Ce type d’exercice récompense la maîtrise des concepts suivants :

• Compréhension du pipeline MIPS à 5 étages (IF, ID, EX, MEM, WB).
• Connaissance de la résolution des branchements à l’étage EX et des conséquences sur le pipeline (flush, stall).
• Capacité à tracer un diagramme d’exécution cycle par cycle, en tenant compte des instructions annulées en cas de branchement pris.
• Gestion des unités de forwarding pour éviter les aléas de données, même si ici on ne détaille pas les stalls liés aux dépendances.
• Attention à la prédiction de branchement et à la latence induite par la résolution tardive (EX).

Les erreurs fréquentes sont :

• Ignorer le flush des instructions après un branchement pris.
• Confondre le cycle de résolution du branchement (EX) avec le cycle d’IF ou ID.
• Ne pas compter correctement les cycles de pipeline nécessaires pour terminer l’itération.
• Omettre les instructions annulées dans le diagramme.