Parallélisme d'instruction

Quand on lance une instruction sur un processeur pipeliné, le résultat n'est pas disponible immédiatement.

On appelle latence (additionnelle) d'une instruction (I) le nombre de cycles qu'il faut attendre avant de pouvoir lancer une instruction utilisant le résultat de (I).

Attention: si le pipeline dispose de courts-circuits, la latence peut dépendre de l'instruction suivante.

Pour qu'un pipeline soit plein, le parallélisme d'instruction doit être exploité : il faut trouver des séquences d'instructions indépendantes pouvant être intercalées dans le pipeline. Pour éviter une suspension du pipeline, une instruction J dépendant d'une instruction I doit être placée à une distance de I au moins égale à la latence du pipeline pour réaliser I.

On appelle CPI (cycles par instruction) le nombre moyen de cycles mis par un processeur pour exécuter une instruction.

Le but du pipeline est d'essayer de faire un CPI de 1. Ce TD est une introduction à quelques techniques de compilation destinées à faire baisser le CPI.

Considérons les quatre suites d'instructions suivantes:

Cas 1:
ADD $t3, $t1, $t2
SW 0($t3), $t4

Cas 2:
ADD $t3, $t1, $t2
SW 12($t0), $t3

Cas 3:
ADD $t3, $t1, $t2
ADD $t5, $t3,$t4

Cas 4:
LW $t1, 12($t0)
ADD $t3, $t1,$t2

1. Quelle est la latence de chacune de ces suites d'instructions s'il n'y a pas de courts-circuits ?
2. Même question avec des courts-circuits.
   
   On veut compiler le code C suivant:

   a = b + c;
   d = e - f;	
   

   On suppose que les variables sont en mémoire à une adresse que l'on pourra représenter symboliquement par le nom de la variable. Tous les registres sont libres.
3. Ecrire le code MIPS qui exécute directement le code C ci-dessus.
4. Ecrire les suspensions de pipeline correspondant aux temps de latence des différentes instructions sans et avec courts-circuits.
5. Ordonnancer le code pour éviter les suspensions dans le cas d'un pipeline avec courts-circuits.

Pour simplifier, on suppose les latences suivantes (on a diminué les latences des instructions flottantes):

------------------------------------------------------------------------
|Instruction produisant  |  Instruction utilisant |  Latence en cycles |
|le résultat             |  le résultat           |                    |
------------------------------------------------------------------------
|  Op UAL entière        |  Tout type             |   0                |    
------------------------------------------------------------------------
|  Chargement entier     |  Tout type             |   1                |
------------------------------------------------------------------------
|  Op UAL flottante      |  Op UAL flottante      |   3                |
------------------------------------------------------------------------
|  Op UAL flottante      |  Rangement flottant    |   2                |
------------------------------------------------------------------------
|  Chargement flottant   |  Op UAL flottante      |   1                |
------------------------------------------------------------------------
|  Chargement flottant   |  Rangement flottant    |   0                |
------------------------------------------------------------------------

Il faut noter que tout branchement est suivit d'une latence de 1 qui est inévitable. On veut compiler le code C suivant, qui ajoute un scalaire s à tous les éléments d'un vecteur x flottant:

    int i;
    float s;
    float x[1000];

    for (i=0; i<1000; i++) x[i] = x[i] + s;

Pour simplifier, on suppose que $t1 contient initialement l'adresse du dernier élément du vecteur (i.e. x[999]) et que le registre flottant F_2 contient la valeur scalaire s.

1. Ecrire la boucle sans tenir compte du pipeline.
2. Ecrire les suspensions en tenant compte de la latence des opérations et du branchement retardé. Combien de cycles faut-il par élément de vecteur ?
3. Ordonnancer la boucle. Combien de cycles faut-il maintenant par élément de vecteur ?
   
   A chaque itération, on perd 3 cycles pour la boucle. Pour résoudre ce problème, on doit faire plus d'opérations dans le corps de la boucle (ou moins souvent d'opérations de gestion de boucle). Une solution simple à ce problème s'appelle le déroulage de boucle. Cette solution consiste à dupliquer le corps de la boucle plusieurs fois puis à adapter le code de terminaison de la boucle.
4. Ecrire la boucle déroulée avec 4 copies du corps de la boucle. Combien de cycles faut-il pour exécuter une boucle ? Combien de cycles faut-il par élément de vecteur ?
5. Ordonnancer le code précédent. Combien de cycles faut-il pour exécuter une boucle ? Combien de cycles faut-il par élément de vecteur ?