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 :

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 :

_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 :

_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 ?