Changes between Version 3 and Version 4 of Partiel2016
- Timestamp:
- Nov 19, 2018, 11:25:22 AM (6 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
Partiel2016
v3 v4 3 3 4 4 5 == Novembre 2016 Documents autorisés -Durée 2h ==5 == Partiel – 2016 – Documents autorisés – Durée 2h == 6 6 7 7 … … 12 12 13 13 14 On souhaite comparer deux réalisations de l'architecture Mips-32. La première réalisation, appelée `Mips`, est la réalisation en 5 étages (`IFC`, `DEC`, `EXE`, `MEM` et `WBK`) étudiée en cours. 14 15 15 On souhaite comparer deux réalisations de l’architecture Mips-32. 16 La première réalisation, appelée `Mips`, est la réalisation en 5 étages (`IFC`, `DEC`, `EXE`, `MEM` et `WBK`) étudiée en cours.[[BR]] 16 La seconde réalisation, appelée `MipsO`, est également une réalisation en 5 étages : `IFC`, `DEC`, `EXE`, `MEM` et `WBK`. Les étages `MipsO` sont identiques à ceux de `Mips`. 17 17 18 L a seconde réalisation, appelée `MipsO`, est également une réalisation en 5 étages : `IFC`, `DEC`, `EXE`, `MEM` et `WBK`. Les étages `MipsO` sont identiques à ceux de `Mips`.[[BR]]18 L'objectif de cette comparaison est d'étudier l'impact de la mise en place de bypass impliquant les instructions de type load. En effet, dans `Mips`, lorsqu'une instruction load est suivie par une instruction qui dépend du résultat du load, des bypass permettent d'éviter des cycles de gel. Ces bypass récupèrent l'opérande mémoire lu par l'instruction load dans son étage `MEM` et l'achemine vers l'instruction qui a besoin de cet opérande. 19 19 20 L’objectif de cette comparaison est d’étudier l’impact de la mise en place de bypass impliquant les instructions de type load. En effet, dans `Mips`, lorsqu’une instruction load est suivie par une instruction qui dépend du résultat du load, des bypass permettent d’éviter des cycles de gel. Ces bypass récupèrent l’opérande mémoire lu par l’instruction load dans son étage `MEM` et l’achemine vers l’instruction qui a besoin de cet opérande.[[BR]] 20 On souhaite étudier l'impact de la suppression de ces bypass dans la réalisation `MipsO`. 21 21 22 On souhaite étudier l’impact de la suppression de ces bypass dans la réalisation `MipsO`.[[BR]] 22 ''1 - Si l'on ignore les techniques d'optimisation, un compilateur pour `MipsO` est-il différent d'un compilateur pour `Mips` ?'' 23 23 24 1- Si l’on ignore les techniques d’optimisation, un compilateur pour `MipsO` est-il différent d’un compilateur pour `Mips` ?[[BR]] 24 ''2 - Dans une réalisation encore plus simplifiée du processeur, les dépendances de données sur le résultat des instructions load ne sont pas gérées par le matériel ni en ce qui concerne les bypass ni pour la génération des cycles de gel. Cette simplification a-t-elle un impact sur le compilateur ?'' 25 25 26 2- Dans une réalisation encore plus simplifiée du processeur, les dépendances de données sur le résultat des instructions load ne sont pas gérées par le matériel ni en ce qui concerne les bypass ni pour la génération des cycles de gel. Cette simplification a-t-elle un impact sur le compilateur ? [[BR]] 26 ''3 - Dans `MipsO`, on supprimant les bypass sur les opérandes mémoire, on espère augmenter la fréquence de fonctionnement du processeur. Expliquer pourquoi peut-on obtenir une telle amélioration ?'' 27 27 28 3- Dans `MipsO`, on supprimant les bypass sur les opérandes mémoire, on espère augmenter la fréquence de fonctionnement du processeur. Expliquer pourquoi peut-on obtenir une telle amélioration ?[[BR]] 28 ''4 - Dans `Mips`, il existe 8 bypass pour limiter la dégradation des performances due aux dépendances de données. Quels sont les bypass dans la réalisation `MipsO` ? Justifier votre réponse à l'aide de schémas simplifiés. Pour chaque bypass donner un exemple de suite d'instructions qui illustre la nécessité de ce bypass.'' 29 29 30 4- Dans `Mips`, il existe 8 bypass pour limiter la dégradation des performances due aux dépendances de données. Quels sont les bypass dans la réalisation `MipsO` ? Justifier votre réponse à l’aide de schémas simplifiés. Pour chaque bypass donner un exemple de suite d'instructions qui illustre la nécessité de ce bypass.[[BR]] 30 31 On souhaite comparer les 2 réalisations sur un programme de traitement d'images en 'niveaux de gris'. 32 33 Une image est composée d'un ensemble de pixels organisés sous forme d'un tableau. Pour une image en 'niveaux de gris', chaque pixel est codé sur un octet. La valeur 0 représente la couleur noire, la valeur 255 la couleur blanche. Les valeurs comprises entre 0 et 255 représentent les différentes nuances de gris. 34 35 Souvent les fonctions de traitement d'images ne sont pas appliquées sur l'ensemble de l'image mais uniquement sur une partie de celle-ci. Pour cela on utilise un masque. Pour chaque pixel, le masque permet d'indiquer si le pixel subit le traitement ou non. Si le masque vaut 0, le pixel n'est pas modifié. Si le masque vaut 255, on lui applique la fonction de traitement. Le masque de l'image est donc un tableau d'octets de même taille que l'image. 31 36 32 37 33 34 On souhaite comparer les 2 réalisations sur un programme de traitement d’images en 'niveaux de gris'.[[BR]] 35 36 Une image est composée d'un ensemble de pixels organisés sous forme d'un tableau. Pour une image en 'niveaux de gris', chaque pixel est codé sur un octet. La valeur 0 représente la couleur noire, la valeur 255 la couleur blanche. Les valeurs comprises entre 0 et 255 représentent les différentes nuances de gris.[[BR]] 37 38 Souvent les fonctions de traitement d’images ne sont pas appliquées sur l’ensemble de l’image mais uniquement sur une partie de celle-ci. Pour cela on utilise un masque. Pour chaque pixel, le masque permet d’indiquer si le pixel subit le traitement ou non. Si le masque vaut 0, le pixel n’est pas modifié. Si le masque vaut 255, on lui applique la fonction de traitement. Le masque de l’image est donc un tableau d’octets de même taille que l’image.[[BR]] 39 40 41 La fonction suivante permet d’obtenir le négatif de l’image sur une partie de l’image. 38 La fonction suivante permet d'obtenir le négatif de l'image sur une partie de l'image. 42 39 43 40 {{{ 44 41 #!C 45 unsigned char *neg_msk (unsigned char *pt_img, 46 unsigned char *pt_msk, 47 unsigned int size ) 48 { 49 unsigned int i = 0 ; 50 51 for (i=0 ; i!=size ; i++) 52 { 53 if (pt_msk [i] != 0) 54 pt_img [i] = 255 – pt_img [i]; 55 } 56 return (pt_img); 57 } 42 unsigned char * neg_msk (unsigned char * pt_img, 43 unsigned char * pt_msk, 44 unsigned int size) { 45 unsigned int i = 0; 46 for (i = 0; i != size; i += 1) { 47 if (pt_msk[i] != 0) { 48 pt_img[i] = 255 - pt_img [i]; 49 } 50 } 51 return pt_img; 52 } 58 53 }}} 59 54 60 55 61 Un compilateur (non pipeline) a produit le code assembleur suivant pour la boucle principale de cette fonction. On suppose qu'à l'entrée de la boucle le registre `R4` contient l'adresse du tableau ''pt_img'', `R5` l'adresse du tableau ''pt_msk'' et le registre `R6` l’adresse de fin du tableau ''pt_img'' (l'adresse qui suit immédiatement celle de la dernière case du tableau). Le registre `R7` contient la valeur 255.[[BR]]56 Un compilateur (non pipeline) a produit le code assembleur suivant pour la boucle principale de cette fonction. On suppose qu'à l'entrée de la boucle le registre `R4` contient l'adresse du tableau `pt_img`, `R5` l'adresse du tableau ''pt_msk'' et le registre `R6` l'adresse de fin du tableau `pt_img` (l'adresse qui suit immédiatement celle de la dernière case du tableau). Le registre `R7` contient la valeur 255. 62 57 63 Version 1 :[[BR]] 58 '''Version 1 :''' 64 59 65 60 {{{ 66 61 #!asm 67 _For : Lbu r7 , 0 (r5 ) ; pt_msk[i] 68 Bne r7 , r0 , _Endif 69 Lbu r8 , 0 (r4 ) ; pt_img[i] 70 Sub r8 , r7 , r8 ; 255-pt_img[i] 71 Sb r8 , 0 (r4 ) 72 _Endif: Addiu r5 , r5 , 1 73 Addiu r4 , r4 , 1 74 Bne r4 , r6 , _For 75 62 _for: 63 lbu r7, 0(r5) ; pt_msk[i] 64 bne r7, r0, _endif 65 lbu r8, 0(r4) ; pt_img[i] 66 sub r8, r7, r8 ; 255 - pt_img[i] 67 sb r8, 0(r4) 68 _endif: 69 addiu r5, r5, 1 70 addiu r4, r4, 1 71 bne r4, r6, _for 76 72 }}} 77 73 78 74 79 5- Modifier le code pour qu’il soit exécutable sur `Mips` et analyser l’exécution de la boucle à l’aide d’un schéma simplifié dans le cas où le branchement échoue (faire figurer les bypass sur le schéma). Combien de cycles sont-ils nécessaires à l’exécution d’une itération de la boucle dans le cas où le branchement échoue et dans le cas où le branchement réussit ? Calculer le CPI et le CPI-utile en supposant que dans 25% des cas le branchement échoue.[[BR]] 75 ''5 - Modifier le code pour qu'il soit exécutable sur `Mips` et analyser l'exécution de la boucle à l'aide d'un schéma simplifié dans le cas où le branchement échoue (faire figurer les bypass sur le schéma). Combien de cycles sont-ils nécessaires à l'exécution d'une itération de la boucle dans le cas où le branchement échoue et dans le cas où le branchement réussit ? Calculer le CPI et le CPI-utile en supposant que dans 25% des cas le branchement échoue.'' 80 76 81 6- Modifier le code pour qu’il soit exécutable sur `MipsO` et analyser l’exécution de la boucle à l’aide d’un schéma simplifié dans le cas où le branchement échoue (faire figurer les bypass sur le schéma). Combien de cycles sont-ils nécessaires à l’exécution d’une itération de la boucle dans le cas où le branchement échoue et dans le cas où le branchement réussit ? Calculer le CPI et le CPI-utile en supposant que dans 25% des cas le branchement échoue.[[BR]] 77 ''6 - Modifier le code pour qu'il soit exécutable sur `MipsO` et analyser l'exécution de la boucle à l'aide d'un schéma simplifié dans le cas où le branchement échoue (faire figurer les bypass sur le schéma). Combien de cycles sont-ils nécessaires à l'exécution d'une itération de la boucle dans le cas où le branchement échoue et dans le cas où le branchement réussit ? Calculer le CPI et le CPI-utile en supposant que dans 25% des cas le branchement échoue.'' 82 78 83 7- Optimiser le code de la boucle pour `MipsO` en modifiant l’ordre des instructions de manière à éviter au maximum les cycles perdus (expliquer votre démarche). Combien de cycles sont-ils nécessaires dans `MipsO` pour effectuer une itération ? Il n'est pas nécessaire de faire un schéma mais d'indiquer simplement les cycles perdus sur le code après optimisation.[[BR]] 79 ''7 - Optimiser le code de la boucle pour `MipsO` en modifiant l'ordre des instructions de manière à éviter au maximum les cycles perdus (expliquer votre démarche). Combien de cycles sont-ils nécessaires dans `MipsO` pour effectuer une itération ? Il n'est pas nécessaire de faire un schéma mais d'indiquer simplement les cycles perdus sur le code après optimisation.'' 84 80 85 Même question pour la réalisation `Mips`.[[BR]] 81 ''8 - Même question pour la réalisation `Mips`.'' 86 82 87 8- Pour améliorer les performances d’exécution, on décide de dérouler une fois le code de la boucle (traitement de 2 éléments à chaque itération). Proposer un code optimisé après le déroulement pour `MipsO`. Combien de cycles sont-ils nécessaires dans `MipsO` pour traiter un élément ? Il n'est pas nécessaire de faire un schéma mais d'indiquer simplement les cycles perdus sur le code après optimisation.[[BR]] 83 ''9 - Pour améliorer les performances d'exécution, on décide de dérouler une fois le code de la boucle (traitement de 2 éléments à chaque itération). Proposer un code optimisé après le déroulement pour `MipsO`. Combien de cycles sont-ils nécessaires dans `MipsO` pour traiter un élément ? Il n'est pas nécessaire de faire un schéma mais d'indiquer simplement les cycles perdus sur le code après optimisation.'' 88 84 89 Même question pour `Mips`.[[BR]] 85 ''10 - Même question pour `Mips`.'' 90 86 91 87 92 88 93 Un autre compilateur (non pipeline) a produit une version différente pour le code de la boucle en remarquant que lorsque l ’on calcule sur 8 bits ''255-x = not(x)'':[[BR]]89 Un autre compilateur (non pipeline) a produit une version différente pour le code de la boucle en remarquant que lorsque l'on calcule sur 8 bits ''255 - x = not(x)'': 94 90 95 91 96 Version 2 :[[BR]] 92 '''Version 2 :''' 97 93 98 94 {{{ 99 95 #!asm 100 _For : Lbu r7 , 0 (r5 ) ; pt_msk[i] 101 Lbu r8 , 0 (r4 ) ; pt_img[i] 102 Xor r8 , r7 , r8 103 Sb r8 , 0 (r4 ) 104 Addiu r5 , r5 , 1 105 Addiu r4 , r4 , 1 106 Bne r4 , r6 , _For 96 _for: 97 lbu r7, 0(r5) ; pt_msk[i] 98 lbu r8, 0(r4) ; pt_img[i] 99 xor r8, r7, r8 100 sb r8, 0(r4) 101 addiu r5, r5, 1 102 addiu r4, r4, 1 103 bne r4, r6, _for 107 104 }}} 108 105 109 106 110 9- Après adaptation du code de la version 2 à `MipsO`, combien de cycles sont-ils nécessaires à l’exécution d’une itération de la boucle ? Calculer le CPI-utile. Il n'est pas nécessaire de faire un schéma mais d'indiquer simplement les cycles perdus sur le code.[[BR]] 107 ''11 - Après adaptation du code de la version 2 à `MipsO`, combien de cycles sont-ils nécessaires à l'exécution d'une itération de la boucle ? Calculer le CPI-utile. Il n'est pas nécessaire de faire un schéma mais d'indiquer simplement les cycles perdus sur le code.'' 111 108 112 Même question pour la réalisation `Mips`.[[BR]] 109 ''12 - Même question pour la réalisation `Mips`.'' 113 110 114 10- Optimiser le code de la boucle en modifiant l’ordre des instructions pour `MipsO` de manière à éviter au maximum les cycles perdus. Combien de cycles sont-ils nécessaires pour effectuer une itération ? Il n'est pas nécessaire de faire un schéma mais d'indiquer simplement les cycles perdus sur le code après optimisation.[[BR]] 111 ''13 - Optimiser le code de la boucle en modifiant l'ordre des instructions pour `MipsO` de manière à éviter au maximum les cycles perdus. Combien de cycles sont-ils nécessaires pour effectuer une itération ? Il n'est pas nécessaire de faire un schéma mais d'indiquer simplement les cycles perdus sur le code après optimisation.'' 115 112 116 Même question pour la réalisation `Mips`.[[BR]] 113 ''14 - Même question pour la réalisation `Mips`.'' 117 114 118 11- Pour améliorer les performances d’exécution, on décide de dérouler une fois le code de la boucle (traitement de 2 éléments à chaque itération). Proposer un code optimisé pour `MipsO` après le déroulement. Combien de cycles sont-ils nécessaires pour traiter un élément ? Il n'est pas nécessaire de faire un schéma mais d'indiquer simplement les cycles perdus sur le code après optimisation.[[BR]] 115 ''15 - Pour améliorer les performances d'exécution, on décide de dérouler une fois le code de la boucle (traitement de 2 éléments à chaque itération). Proposer un code optimisé pour `MipsO` après le déroulement. Combien de cycles sont-ils nécessaires pour traiter un élément ? Il n'est pas nécessaire de faire un schéma mais d'indiquer simplement les cycles perdus sur le code après optimisation.'' 119 116 120 Même question pour la réalisation `Mips`.[[BR]] 117 ''16 - Même question pour la réalisation `Mips`.'' 121 118 122 12- Pour chacune des 6 versions du code :[[BR]] 119 ''17- Pour chacune des 6 versions du code :'' 120 * Version 1 (code original, code réordonné, code déroulé) 121 * Version 2 (code original, code réordonné, code déroulé) 123 122 124 o Version 1 (code original, code réordonné, code déroulé)[[BR]] 125 o Version 2 (code original, code réordonné, code déroulé)[[BR]] 126 127 quel gain en fréquence doit-on obtenir pour que la réalisation `MipsO` soit plus performante que la réalisation `Mips` ? 123 ''Quel gain en fréquence doit-on obtenir pour que la réalisation `MipsO` soit plus performante que la réalisation `Mips` ?''
