= Architecture des Processeurs et Optimisation =

== Examen – 2014 – 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 souhaite étudier la performance d'exécution d'une fonction de tri sur une réalisation superscalaire de l'architecture Mips. Il s'agit de la réalisation à 2 pipelines appelée SS2 étudiée en cours. On considère deux versions différentes de la même fonction.
On considère la fonction `Partition`. Cette fonction prend en entrée un tableau d'entiers `src` et le recopie dans un autre tableau `trg` en séparant les plus petits éléments des plus grands. En parcourant le tableau `src`, chaque élément est comparé au premier élément du tableau. S'il est plus petit que celui-ci, il est placé au début du tableau `trg` sinon à la fin du tableau `trg`.

{{{
#!C
unsigned int Partition(int * src, int * trg, unsigned int size) {
    unsigned int i = 0;
    unsigned int idx_d = 0;
    unsigned int idx_f = size - 1;
    int pivot = 0;

    pivot = src [0];
  
    for (i = size ; i !=0  ; i--) {
        if (src[i - 1] < pivot) {
            trg[idx_d] = src[i - 1];
            idx_d++;
        }
        else {
            trg[idx_f] = src[i - 1];
            idx_f--;
        }
   }
   return indx_d;
}
}}}

Dans un premier temps, on suppose que le système mémoire est parfait.
Un premier compilateur a produit une première version de code assembleur pour la boucle principale de cette fonction.
On suppose qu'à l'entrée de la boucle le registre `R4` contient l'adresse du tableau `src`, `R5` l'adresse de fin du tableau `src` (l'adresse qui suit immédiatement celle de la dernière case du tableau), `R6` l'adresse du tableau `trg`, et `R7` l'adresse de la dernière case du tableau `trg`. On suppose que `R8` contient la valeur du pivot.

'''Version 1 :'''

{{{
#!asm
_For:
    Lw    r9,  -4 (r5)   ; src [i - 1]
    Slt   r10, r9, r8    ; src [i - 1] < pivot ?
    Beq   r10, r0, _Else
    Nop
    Sw    r9, 0(r6)
    Addiu r6, r6,  4
    J     _Endif
    Nop
_Else:
    Sw    r9, 0(r7)
    Addiu r7, r7, -4
_Endif:
    Addiu r5, r5, -4
    Bne   r4, r5, _For
    Nop
}}}

On suppose que l'étiquette For est placée sur une adresse alignée (multiple de 8) et qu'à l'entrée de la boucle, le buffer d'instructions est vide.

''1 - Analyser l'exécution de la boucle à l'aide d'un schéma simplifié sur SS2 dans le cas où le branchement échoue et dans le cas où le branchement réussit. Combien de cycles sont-ils nécessaires pour l'exécution d'une itération dans chaque cas ?''

''2 - Optimiser le code à l'aide de la technique Software pipeline de manière à éviter au maximum les cycles perdus (expliquer votre démarche). Indiquer clairement le nombre d'étages et les instructions contenues dans chaque étage.''

Un second compilateur a produit une autre version pour le code de la boucle. On suppose de nouveau que l'étiquette `For` est placée sur une adresse alignée (multiple de 8) et qu'à l'entrée de la boucle, le buffer d'instructions est vide.

'''Version 2 :'''

{{{
#!asm
_For:
    Lw    r9,  -4(r5)    ; src[i - 1]
    Slt   r10, r9,  r8   ; src[i - 1] < pivot ?
    Sll   r10, r10, 2
    Sw    r9,  0(r6)
    Sw    r9,  0(r7)
    Addiu r7,  r7,  -4
    Addu  r7,  r7,  r10
    Addu  r6,  r6,  r10
    Addiu r5,  r5,  -4
    Bne   r4,  r5,  _For
    Nop
}}}

''3 - Analyser l'exécution de la boucle à l'aide d'un schéma simplifié sur SS2. Combien de cycles sont-ils nécessaires pour l'exécution d'une itération ?''

''4 - Optimiser le code à l'aide de la technique Software pipeline de manière à éviter au maximum les cycles perdus (expliquer votre démarche). Indiquer clairement le nombre d'étages et les instructions contenues dans chaque étage.''

On souhaite étudier maintenant l'influence du système mémoire sur la performance des deux versions. Dans le reste du sujet, on considère le code original des deux versions.

On suppose que le tableau `src` contient 256 entiers. Les adresses des deux tableaux `src` et `trg` sont alignées (multiples de 1024).

On évalue la performance d'exécution des deux codes sur différentes plateformes matérielles. Sur toutes les plateformes, le processeur est relié à un cache de données et à un cache d'instructions séparés. Le cache d'instructions est parfait (taux de miss = 0).
On suppose qu'au début de l'exécution de la fonction le cache de données est vide.

Le cache de données a une capacité de 1 Koctets. C'est un cache à correspondance directe (Direct Mapping) et un bloc du cache contient 64 octets. Le temps d'accès au cache est de 1 cycle en cas de hit.
Le cache de données est relié à la mémoire primaire à travers un bus. Ce bus permet d'effectuer une transaction à la fois. A chaque cycle, on peut transférer 4 octets (1 mot) sur le bus. Pour initialiser le transfert, il faut, en moyenne, 6 cycles. Ainsi, en cas de Miss dans le cache, il faut 1 cycle pour détecter le Miss, puis 22 cycles (6 + 1 * 64 / 4) pour transférer le bloc manquant. Après le chargement du bloc, il faut encore 1 cycle pour mettre à jour le cache et 1 cycle supplémentaire pour répondre au processeur.
Sur la première plateforme, on utilise un cache de données Write Through qui dispose d'un buffer d'écritures postées de 2 places. Pour une écriture, si le bloc à écrire n'est pas présent, il n'est pas chargé dans le cache. S'il y a au moins une place libre dans le buffer, une écriture coûte 1 cycle, le temps nécessaire pour écrire dans le buffer. Chaque requête d'écriture postée est réalisée par une transaction sur le bus. Une requête d'écriture postée présente dans le buffer est supprimée à la fin de la transaction sur le bus ce qui nécessite en moyenne 7 (6 + 1 * 4 / 4) cycles.

''5 - Quelle est l'utilité de disposer de 2 places dans le buffer d'écritures postées ?''

''6 - Pour la Version 1, combien de Miss se produisent-ils lors de l'exécution de la boucle ? Calculer le nombre moyen de cycles supplémentaires par itération dus aux lectures. Calculer le nombre moyen de cycles supplémentaires par itération dus aux écritures.
En déduire le nombre moyen de cycles par itération dans le cas où le branchement réussit et dans le cas où il échoue.''

''7 - Pour la Version 2, combien de Miss se produisent-ils lors de l'exécution de la boucle ? Calculer le nombre moyen de cycles supplémentaires par itération dus aux lectures. Calculer le nombre moyen de cycles supplémentaires par itération dus aux écritures.
En déduire le nombre moyen de cycles par itération.''

Sur la seconde plateforme, on utilise un cache de données Write Back. Lors d'une écriture, si le bloc à écrire n'est pas présent, le cache commence par le charger depuis la mémoire puis, le modifie.
On suppose que tous les éléments du tableau src sont plus grands que le pivot.

''8 - Pour la Version 1, combien de Miss se produisent-ils lors de l'exécution de la boucle (distinguer 2 cas) ? Calculer le nombre moyen de cycles supplémentaires par itération dus aux lectures. Calculer le nombre moyen de cycles supplémentaires par itération dus aux écritures. En déduire le nombre moyen de cycles par itération.''

''9 - Mêmes questions pour la Version 2.''

On suppose que tous les éléments du tableau `src` sont plus petits que le pivot.

''10 - Pour la Version 1, combien de Miss se produisent-ils lors de l'exécution de la boucle (distinguer 2 cas) ? Calculer le nombre moyen de cycles supplémentaires par itération dus aux lectures. Calculer le nombre moyen de cycles supplémentaires par itération dus aux écritures. En déduire le nombre moyen de cycles par itération.''

''11 - Mêmes questions pour la Version 2.''