Travaux Dirigés Pipeline
Exercice
Considérons le code MIPS suivant :
| | | |
| --- | --- | --- |
| | isDAG: | # a0 = trie, a1 = n |
| I1 | li $t0, 0 | # t0 = i, a0 = &trie[i] |
| | loop: | |
| I2 | beq $t0, $a1, done | # while(i != n) |
| I3 | lw $t1, 0($a0) | # t1 = trie[i].left |
| I4 | beq $t1, $0, next | # if(t1 != 0) |
| I5 | lw $t2, 4($a0) | # t2 = trie[i].right |
| I6 | beq $t2, $0, next | # if(t2 != 0) |
| I7 | beq $t1, $t2, true | # if(t1 == t2) goto true |
| | next: | |
| I8 | addi $a0, $a0, 8 | # a0 = &trie[i+1] |
| I9 | addi $t0, $t0, 1 | # i++ |
| I10 | j loop | # end-while |
| | done: | |
| I11 | li $v0, 0 | # answer = false |
| I12 | jr $ra | # return |
| | true: | |
| I13 | li $v0, 1 | # answer = true |
| I14 | jr $ra | # return |
Cette fonction prend deux arguments: un tableau de nœuds trie et la longueur du tableau n. elle détermine si le trie est un DAG (Direct Acyclic Grapg, càd quelques nœuds possèdent des champs droite et gauche à la fois égaux et différents de zéro).
Ce code tourne sur un processeur MIPS pipeliné à 5 étages, sachant que les aléas de structure sont résolus et que les unités de renvois sont implémentés. Nous supposons que les branchements conditionnels sont résolus par prédiction et qu’ils sont résolus à l’étage EX.
1/ Le corps de la boucle inclut 3 beq (mis à part le beq au début de la boucle). Donnez pour une seule itération de la boucle le diagramme d’exécution ainsi que le nombre de cycles nécessaires dans chacun des cas suivants :
Publicité
Rmq : laisser la ligne vide si l’instruction n’est pas exécutée.
Cas 1 : condition vérifiée de beq 1 (instruction I4)
| | | | | | | | | | | | | | | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Instru | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| I1 | | | | | | | | | | | | | | | | |
| I2 | | | | | | | | | | | | | | | | |
| I3 | | | | | | | | | | | | | | | | |
| I4 | | | | | | | | | | | | | | | | |
| I5 | | | | | | | | | | | | | | | | |
| I6 | | | | | | | | | | | | | | | | |
| I7 | | | | | | | | | | | | | | | | |
| I8 | | | | | | | | | | | | | | | | |
| I9 | | | | | | | | | | | | | | | | |
| I10 | | | | | | | | | | | | | | | | |
| I11 | | | | | | | | | | | | | | | | |
| I12 | | | | | | | | | | | | | | | | |
| I13 | | | | | | | | | | | | | | | | |
| I14 | | | | | | | | | | | | | | | | |
Nombre de cycles
Cas 2 : condition non vérifiée de beq 1 (instruction I4)
& condition vérifiée de beq 2 (instruction I6)
| | | | | | | | | | | | | | | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Instru | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| I1 | | | | | | | | | | | | | | | | |
| I2 | | | | | | | | | | | | | | | | |
Publicité
| I3 | | | | | | | | | | | | | | | | |
| I4 | | | | | | | | | | | | | | | | |
| I5 | | | | | | | | | | | | | | | | |
| I6 | | | | | | | | | | | | | | | | |
| I7 | | | | | | | | | | | | | | | | |
| I8 | | | | | | | | | | | | | | | | |
| I9 | | | | | | | | | | | | | | | | |
| I10 | | | | | | | | | | | | | | | | |
| I11 | | | | | | | | | | | | | | | | |
| I12 | | | | | | | | | | | | | | | | |
| I13 | | | | | | | | | | | | | | | | |
| I14 | | | | | | | | | | | | | | | | |
Nombre de cycles
Cas 3 : condition non vérifiée de beq 1 (instruction I4) et de beq 2 (instruction I6)
& condition vérifiée de beq 3 (instruction I7)
| | | | | | | | | | | | | | | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Instru | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| I1 | | | | | | | | | | | | | | | | |
| I2 | | | | | | | | | | | | | | | | |
| I3 | | | | | | | | | | | | | | | | |
| I4 | | | | | | | | | | | | | | | | |
| I5 | | | | | | | | | | | | | | | | |
| I6 | | | | | | | | | | | | | | | | |
| I7 | | | | | | | | | | | | | | | | |
| I8 | | | | | | | | | | | | | | | | |
| I9 | | | | | | | | | | | | | | | | |
Publicité
| I10 | | | | | | | | | | | | | | | | |
| I11 | | | | | | | | | | | | | | | | |
| I12 | | | | | | | | | | | | | | | | |
| I13 | | | | | | | | | | | | | | | | |
| I14 | | | | | | | | | | | | | | | | |
Nombre de cycles
Cas 4 : condition non vérifiée de beq 1, 2 et 3 (instruction I4, I6 et I7)
| | | | | | | | | | | | | | | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Instru | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| I1 | | | | | | | | | | | | | | | | |
| I2 | | | | | | | | | | | | | | | | |
| I3 | | | | | | | | | | | | | | | | |
| I4 | | | | | | | | | | | | | | | | |
| I5 | | | | | | | | | | | | | | | | |
| I6 | | | | | | | | | | | | | | | | |
| I7 | | | | | | | | | | | | | | | | |
| I8 | | | | | | | | | | | | | | | | |
| I9 | | | | | | | | | | | | | | | | |
| I10 | | | | | | | | | | | | | | | | |
| I11 | | | | | | | | | | | | | | | | |
| I12 | | | | | | | | | | | | | | | | |
| I13 | | | | | | | | | | | | | | | | |
| I14 | | | | | | | | | | | | | | | | |
Nombre de cycles