= Architecture des Processeurs et Optimisation =

== Partiel – 2017 – Documents autorisés – Durée 2h ==


'''Utiliser impérativement les feuilles quadrillées fournies pour les schémas simplifiés.'''

'''Une réponse non justifiée sera considérée comme fausse.'''

On considère le processeur pipeline P7. Ce processeur a le même jeu d'instructions que le Mips. Il est construit autour d'un pipeline à 7 étages :
`IF1`, `IF2`, `DEC`, `EXE`, `MEM1`, `MEM2`, `WBK`.

Le découpage en étages de ce pipeline a été obtenu à partir du pipeline du processeur Mips. Les étages `IFC` et `MEM` ont chacun été divisé en deux étages.

Le calcul de l'adresse de l'instruction suivante s'effectue dans l'étage `EXE`.

La réalisation contient tous les bypass nécessaires pour prendre en charge les dépendances de données. Cependant il n’y a aucun bypass en entrée de l'étage `MEM1`.

On souhaite étudier, sur cette réalisation, la performance d'exécution d'une fonction de calcul de la distribution des valeurs des pixels d'une image (dite application ''histogramme''), pour les pixels ayant une valeur inférieure à un seuil.

Le code C de la fonction `histogram` est le suivant :
{{{
#!C

void histogram(unsigned char * img, int size, int histo[256], unsigned char seuil) {
   for (int i = 0; i < size; i += 1) {
      if (img[i] < seuil) {
         histo[img[i]] += 1;
      }
   }
}
}}}

Un compilateur pour assembleur Mips non pipeline a produit deux versions pour le code suivant. Conformément aux conventions Mips, à l'entrée de la fonction, le registre `r4` contient la valeur de `img` (adresse du début de l'image), le registre `r5` contient le paramètre `size` de taille du tableau, le registre `r6` contient l'adresse de début du tableau `histo` et le registre `r7` contient la valeur du paramètre `seuil`. Le registre `r10` est initialisé avec l'adresse du dernier élément de `img`.

'''Version 1 :'''

{{{
#!asm
_loop:
    lbu   r8, 0(r4)       # lecture img[i]
    sltu  r9, r8, r7      # img[i] < seuil ?
    beq   r9, r0, _endif
    addu  r9, r6, r8      # calcul &histo[img[i]]
    lw    r11, 0(r9)      # lecture histo[img[i]]
    addiu r11, r11, 1
    sw    r11, 0(r9)      # écriture histo[img[i]]
_endif:
    addiu r4, r4, 1
    bne   r4, r10, _loop
}}}

'''Version 2 :'''

{{{
#!asm
_loop:
    lbu   r8, 0(r4)       # lecture img[i]
    sltu  r9, r8, r7      # img[i] < seuil ?
    addu  r11, r6, r8     # calcul &histo[img[i]]
    lw    r12, 0(r11)     # lecture histo[img[i]]
    addu  r12, r12, r9
    sw    r12, 0(r11)     # écriture histo[img[i]]
    addiu r4, r4, 1
    bne   r4, r10, _loop
}}}

Dans tout l'exercice, on suppose que dans le tableau `img`, la probabilité que `img[i] < seuil` est de 70%.

''1 - Le découpage du pipeline en 7 étages a-t-il un impact sur le compilateur ? Expliquer pourquoi.''

''2 - Dans le processeur Mips, il existe des dépendances de données d'ordre 1, 2 et 3. Dans P7 quelles sont les dépendances de données ?''

''3 - Quels sont les bypass nécessaires à l'exécution des instructions dans ce P7 ? Illustrer pour chaque bypass son utilisation à l'aide d'un exemple d'une suite d'instructions.''

''4 - Pour la Version 1, modifier le code de la boucle pour qu'il soit exécutable sur la réalisation P7. Analyser l'exécution de cette boucle à l'aide d'un schéma simplifié dans l'hypothèse où le branchement échoue. Calculer le nombre moyen de cycles par élément. Calculer le CPI et le CPI-utile.''

''5 - Pour la Version 2, modifier le code de la boucle pour qu'il soit exécutable sur la réalisation P7. Analyser l'exécution de cette boucle à l'aide d'un schéma simplifié. Calculer le nombre moyen de cycles par élément.''

''6 - Pour chacune des deux versions, proposer un code optimisé en modifiant l'ordre des instructions et en utilisant l'exécution spéculative. Il n'est pas nécessaire de faire un schéma mais d'indiquer simplement les cycles de gel sur le code après optimisation. Pour chacune des deux versions, calculer le nombre moyen de cycles par élément.''

''7 - Pour chacune des deux versions, dérouler une fois le code de la boucle (traitement de 2 éléments à chaque itération) et optimiser (en modifiant l'ordre des instructions et en utilisant l'exécution spéculative). Il n'est pas nécessaire de faire un schéma mais d'indiquer simplement les cycles de gel sur le code après optimisation. Pour chacune des deux versions, calculer le nombre moyen de cycles par élément.''

''8 - On souhaite comparer l'éxecution sur le P7 avec l'exécution sur le Mips. Pour chacune des deux versions, calculer le nombre moyen de cycles par élément pour une exécution sur le Mips, pour la version originale du code. Il n'est pas nécessaire de faire un schéma mais d'indiquer simplement les cycles de gel sur le code. Pour chacune des deux versions, quel doit être le rapport minimal entre les fréquences du P7 et du Mips pour que l'exécution soit plus efficace sur le P7 ?''