wiki:TracRevision

Context Navigation

Version 2 (modified by meunier, 4 years ago) (diff)
--

M1 SESI – Architecture des Processeurs et Optimisation

TD3 – Pipeline, Superpipeline, Optimisation de codes

Exercice 1 :

La fonction GetListLength calcule le nombre d'éléments d'une liste. Un élément d'une liste est une structure de donnée appelée chain. Une structure chain est composée de deux pointeurs (un pointeur est un mot de 4 octets qui contient l'adresse d'un autre objet). Le premier pointeur donne l'adresse de la structure chain suivante. Le deuxième pointeur donne l'adresse de la donnée.

struct chain {
    struct chain * NEXT;
    void * DATA;
};

int GetListLength (struct chain * pt) {
    int i = 0;
    while (pt != NULL) {
        i++;
        pt = pt->NEXT;
    }
    return i;
}

Ecrire en assembleur Mips-32 la boucle principale de GetListLength. On suppose que R4 contient l'adresse de la liste (pt).

Analyser l'exécution de la boucle à l'aide d'un schéma simplifié.

Solution 1 :

Loop :
    Lw    r4 , 0 (r4)
    Bne   r4 , r0 , loop
    Addi  r2 , r2 , 1

Exercice 2 :

On considère un programme de traitement d'images. 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. Une fonction de traitement d'images consiste à appliquer un certain algorithme à un tableau de pixels. On considère le programme suivant.

loop:
    Lbu   r8 , 0(r4)        ; lire un pixel
    Addu  r8 , r8 , r5
    Lbu   r9 , 0(r8)        ; lire f(pixel)
    Sb    r9 , 0(r4)

    Addiu r4 , r4 , 1
    Bne   r4 , r10, loop

À l'entrée de la boucle, le registre R4 contient l'adresse du tableau de pixels (l'image à traiter). Le registre R10 contient l'adresse de la fin de l'image. Le registre R5 contient l'adresse d'un tableau F de 256 octets. Ce tableau représente une fonction f(x) avec 0 <= x <= 255 et 0 <= f(x) <= 255. Ce programme permet d'appliquer la fonction f(x) à chaque pixel de l'image. Si x est la valeur d'un pixel, celle-ci est remplacée par f(x). Par exemple, si f(x) = 255 - x, l'application de ce programme à une image permet d'obtenir l'image négative.

a - Modifier le programme pour qu'il soit exécutable sur le Mips-32.

Solution 2-a :

Il faut un delayed slot après chaque branchement

loop:
    Lbu   r8 , 0(r4)        ; lire un pixel
    Addu  r8 , r8 , r5
    Lbu   r9 , 0(r8)        ; lire f(pixel)
    Sb    r9 , 0(r4)

    Addiu r4 , r4 , 1
    Bne   r4 , r10, loop
    Nop

b - Analyser, à l'aide d'un schéma simplifié, l'exécution de ce programme dans le Mips. Calculer le nombre de cycles pour effectuer une itération.

Solution 2-b :

Il faut 10 cycles par itération soit : CPI = 10/7 cycles/inst -- CPI-utile = 10/6 cycles/inst

c - Optimiser le code en changeant l'ordre des instructions de manière à obtenir un CPI et un CPI-utile de 1

Solution 2-c :

Au total, il y a 4 cycles perdus :

1 cycle de gel entre le premier Lbu et le Addu
1 cycle de gel entre le second Lbu et le Sb
1 cycle de gel entre le Addiu et le Bne
1 cycle de Nop

Par ailleurs, les 4 premières instructions sont dépendantes et on ne peut pas modifier leur ordre. Les deux dernières instructions sont dépendantes. L'idée est de remonter le Addiu après le premier Lbu et de descendre le Sb à la place du delayed slot.

loop:
    Lbu   r8 ,  0(r4)        ; lire un pixel
    Addiu r4 , r4 , 1
    Addu  r8 , r8 , r5
    Lbu   r9 ,  0(r8)        ; lire f(pixel)

    Bne   r4 , r10, loop
    Sb    r9 , -1(r4)

Il faut 6 cycles par itération soit CPI = CPI-utile = 1 cycle/inst

d - Optimiser le code en utilisant la technique du "pipeline logiciel". Calculer le nombre de cycles par itération.

Solution 2-d :

On peut décomposer le traitement d'un pixel en trois étapes : lecture du pixel (le premier Lbu), calcul de la valeur de la fonction (Addu et le second Lbu), sauvegarde du pixel (Sb).

A chaque itération de la boucle, l'idée est de traiter trois pixels : pour le pixel i, on fait la lecture, pour le pixel i-1 on fait le calcul et pour le pixel i-2 on sauvegarde.

loop:
    Sb    r11, -2(r4)        ; sauvegarde de pixel i-2
    Addu  r9 , r8 , r5
    Lbu   r11,  0(r9)        ; lire f(pixel i-1)
    Lbu   r8 ,  0(r4)        ; lire le pixel i

    Addiu r4 , r4 , 1
    Bne   r4 , r10, loop
    Nop

Maintenant, on peut réordonner ce code pour éviter les cycles perdus. Il faut déplacer le dernier Lbu dans le delayed slot et remonter le Addiu avant le premier Lbu.

loop:
    Sb    r11, -2(r4)        ; sauvegarde de pixel i-2
    Addu  r9 , r8 , r5
    Addiu r4 , r4 , 1
    Lbu   r11,  0(r9)        ; lire f(pixel i-1)

    Bne   r4 , r10, loop
    Lbu   r8, -1(r4)        ; lire le pixel i

Il faut 6 cycles par itération soit CPI = CPI-utile = 1 cycle/inst.

Exercice 3 :

On considère un processeur RISC pipeline, appelé PROC. PROC a le même jeu d'instructions que le Mips-32. PROC a un pipeline à 7 étages : IF1, IF2, DEC, EXE, MM1, MM2, WBK.

Au début de l'étage IF1, l'adresse de l'instruction est envoyée à la mémoire et l'instruction correspondante est récupérée à la fin du cycle IF2. De la même manière, l'accès à la mémoire de données se déroule en deux cycles. Comme dans Mips-32, le calcul de l'adresse d'instruction s'effectue dans DEC. De même, les étages EXE et WBK ressemblent aux étages EXE et WBK du Mips.

a - Montrer, à l'aide d'un schéma détaillé, l'exécution de l'instruction SW dans PROC.

Solution 3-a :

Dans PROC les accès mémoire se font en deux cycles. Cela veut dire que le système mémoire est lui-même en pipeline pour pouvoir traiter une nouvelle demande à chaque cycle. Dans le cycle WBK, à chaque cycle on écrit dans le banc de registres. Lorsque l'instruction ne nécessite pas de sauvegarder un résultat dans un registre, on écrit dans le registre 0.

PROC contient tous les bypass qui arrivent dans les étages DEC et EXE. On souhaite étudier l'impact de la mise en place d'un bypass dans l'étage MM1 sur la performance du processeur. On considère donc deux versions de PROC.

Dans PROC1, il n'y a pas de bypass entre l'étage MM2 de l'instruction i et l'étage MM1 de l'instruction i+2. La période de l'horloge est de 2 ns pour PROC1. Dans PROC2, il y a un bypass entre l'étage MM2 de l'instruction i et l'étage MM1 de l'instruction i+2. La période de l'horloge est de 2,1 ns pour PROC2.

b - Expliquer pourquoi la période de l'horloge est plus longue dans PROC2 ?

Solution 3-b :

Dans un processeur pipeline, le temps de cycle est souvent déterminé par le temps d'accès à la mémoire. En effet, l'accès à la mémoire se trouve souvent sur le chemin critique du processeur (l'opération la plus longue). Dans PROC, l'accès à la mémoire s'effectue en deux cycles. Si l'on place un bypass dans les cycles d'accès à la mémoire, il y a une très forte probabilité d'aggraver le chemin critique du processeur et donc de ralentir le temps de cycle.

Pour comparer la performance des 2 versions de PROC, on considère le code de l'exercice 2.

c - Modifier le code du programme pour qu'il soit exécutable sur PROC.

Solution 3-c :

Dans PROC, l'adresse de l'instruction est calculée dans le cycle DEC, c'est-à-dire le troisième cycle du pipeline. Il y a donc 2 delayed slots dans ce processeur. La manière la plus simple de rendre le code exécutable est de remplir les delayed slots avec des Nop.

loop:
    Lbu   r8, 0(r4)        ; lire un pixel
    Addu  r8 , r8, r5
    Lbu   r9 , 0(r8)       ; lire f(pixel)
    Sb    r9 , 0(r4)

    Addiu r4 , r4 , 1
    Bne   r4 , r10, loop
    Nop
    Nop

d - Analyser, à l'aide d'un schéma simplifié, l'exécution de ce code dans PROC1. Combien de cycles sont nécessaires pour l'exécution d'une itération de la boucle ? Calculer le CPI et le CPI-utile. Combien dure (en seconde) le traitement d'une image de 1024 pixels ?

Solution 3-d :

On a les dépendances de données suivantes :

entre Lbu et Addu (2 cycles de gel et bypass MM2-EXE)
entre Addu et Lbu (bypass EXE-EXE)
entre Lbu et Sb (2 cycles de gel et bypass MM2-EXE)
entre Addiu et Bne (1 cycle de gel et bypass EXE-DEC)

En tout, il faut donc 13 cycles pour exécuter une itération de la boucle.

CPI = 13/8 cycles/instruction -- CPI-utile = 13/6 cycles/instruction

Pour une image de 1024 pixels il faut 13 x 1024 = 13312 cycles soit 13312 x 2 = 26624 ns

e - Analyser, à l'aide d'un schéma simplifié, l'exécution de ce code dans PROC2. Combien de cycles sont nécessaires pour l'exécution d'une itération de la boucle. Calculer le CPI et le CPI-utile. Combien dure (en seconde) le traitement d'une image de 1024 pixels ?

Solution 3-e :

On a les dépendances de données suivantes :

entre Lbu et Addu (2 cycles de gel et bypass MM2-EXE)
entre Addu et Lbu (bypass EXE-EXE)
entre Lbu et Sb (1 cycle de gel et bypass MM2-MM1)
entre Addiu et Bne (1 cycle de gel et bypass EXE-DEC)

En tout, il faut donc 12 cycles pour exécuter une itération de la boucle.

CPI = 12/8 cycles/instruction -- CPI-utile = 12/6 cycles/instruction

Pour une image de 1024 pixels il faut 12 x 1024 = 12288 cycles soit 12288 x 2.1 = 25804.8 ns

La mise en place du bypass permet de gagner un cycle dans le traitement (gain de 1/13). En contrepartie on perd 5% sur le temps de cycle. On aboutit donc globalement à une accélération dans le traitement de l'image.

f - Pour PROC1, réordonner le code afin d'éviter au maximum les cycles perdus. Combien de cycles sont maintenant nécessaires pour l'exécution d'une itération de la boucle. Calculer le CPI et le CPI-utile. Combien dure (en seconde) le traitement d'une image de 1024 pixels ?

Solution 3-f :

Il y a en tout 7 cycles perdus (5 cycles de gel et 2 de Nop). Les 4 premières instructions sont dépendantes. On ne peut donc pas changer leur ordre. La seule instruction que l'on peut réordonner est la deuxième Addiu. Elle peut être placée entre le premier Lbu et Addiu pour combler un cycle de gel. On peut aussi placer le Sb dans le deuxième delayed slot pour l'écarter du Lbu.

loop:
    lbu   r8 , 0(r4)        ; lire un pixel
    addiu r4 , r4 , 1
    addu  r8 , r8 , r5
    lbu   r9 , 0(r8)        ; lire f(pixel)

    bne   r4 , r10, loop
    nop
    sb    r9 , -1(r4)

On a les dépendances de données suivantes :

entre Lbu et Addu (1 cycle de gel et bypass MM2-EXE)
entre Addu et Lbu (bypass EXE-EXE)
entre Lbu et Sb (bypass MM2-EXE)
entre Addiu et Bne (bypass MM2-DEC)

En tout, il faut donc 8 cycles pour exécuter une itération de la boucle.

CPI = 8/7 cycles/instruction -- CPI-utile = 8/6 cycles/instruction

Pour une image de 1024 pixels il faut 8 x 1024 = 8192 cycles soit 8192 x 2 = 16384 ns.

g - Pour PROC2, réordonner le code afin d'éviter au maximum les cycles perdus. Combien de cycles sont maintenant nécessaires pour l'exécution d'une itération de la boucle. Calculer le CPI et le CPI-utile. Combien dure (en seconde) le traitement d'une image de 1024 pixels ?

Solution 3-g :

Le même ordonnancement convient à PROC2. En tout, il faut donc 8 cycles pour exécuter une itération de la boucle.

CPI = 8/7 cycles/instruction -- CPI-utile = 8/6 cycles/instruction

Pour une image de 1024 pixels il faut 8 x 1024 = 8192 cycles soit 8192 x 2.1 = 17203.2 ns.

Le réordonnancement a permis d'éliminer les cycles de gel entre Lbu et Sb. Le bypass entre MM2 et MM1 n'apporte donc aucune amélioration. Globalement le traitement est ralenti à cause de la période d'horloge.

h - Pour améliorer la performance du traitement, on décide de dérouler une fois la boucle (traitement de 2 pixels par itération). Proposer un code optimisé pour PROC1. Combien de cycles sont maintenant nécessaires pour l'exécution d'une itération de la boucle. Calculer le CPI et le CPI-utile. Combien dure (en seconde) le traitement d'une image de 1024 pixels ?

Solution 3-h :

loop:
    Lbu   r8 , 0(r4)        ; lire un pixel
    Lbu   r12, 1(r4)        ; lire un pixel
    Addiu r4 , r4 , 2
    Addu  r8 , r8 , r5
    Addu  r12, r12, r5
    Lbu   r9 , 0(r8)        ; lire f(pixel)
    Lbu   r13, 0(r12)       ; lire f(pixel)

    Bne   r4 , r10, loop
    Sb    r9 , -2(r4)
    Sb    r13, -1(r4)

Il n'y a aucun cycle perdu. En tout, il faut donc 10 cycles pour exécuter une itération de la boucle.

CPI = 10/10 cycles/instruction -- CPI-utile = 10/10 cycles/instruction

Pour une image de 1024 pixels il faut 512 itérations soit 10 x 512 = 5120 cycles soit 5120 x 2 = 10240 ns.

i - Pour améliorer la performance du traitement, on décide de dérouler une fois la boucle (traitement de 2 pixels par itération). Proposer un code optimisé pour PROC2. Combien de cycles sont maintenant nécessaires pour l'exécution d'une itération de la boucle. Calculer le CPI et le CPI-utile. Combien dure (en seconde) le traitement d'une image de 1024 pixels ?

Solution 3-i :

Le même code convient à PROC2. En tout, il faut donc 10 cycles pour exécuter une itération de la boucle.

CPI = CPI-utile = 1 cycles/instruction

Pour une image de 1024 pixels il faut 10x 512 = 5120 cycles soit 5120 x 2.1 = 10752 ns.

Exercice 4 :

On considère le processeur pipeline P9. Il a le même jeu d'instructions que le Mips. Il est construit autour d'un pipeline à 9 étages :

IF1, IF2, DEC1, DEC2, EXE1, EXE2, MEM1, MEM2, WBK

Le découpage en étages de ce pipeline a été obtenu à partir du pipeline du processeur Mips. Chacun des étages IFC, DEC, EXE et MEM a été divisé en deux étages. Le calcul de l'adresse de l'instruction suivante s'achève dans l'étage DEC2.

On souhaite étudier le fonctionnement de ce processeur. Le code suivant est la boucle principale d'une fonction qui calcule la valeur absolue des éléments d'un tableau d'entiers. A l'entrée de la boucle R4 contient l'adresse du tableau, le registre R9 contient l'adresse de la fin du tableau.

loop:
    Lw    r8 , 0(r4)        ; lire un élément
    Bgez  r8 , _endif
    Sub   r8 , r0 , r8      ; calculer l'opposé
    Sw    r8, 0(r4)

_endif:
    Addiu r4 , r4 , 4
    Bne   r4 , r9 , loop

a - Le découpage du pipeline en 9 étages a-t-il un impact sur le compilateur ?

Solution 4-a :

Oui. Dans le processeur P9, le calcul de l'adresse de l'instruction suivante se fait dans le cycle DEC2 (4ème cycle du pipeline). Il y a donc 3 delayed slot après chaque branchement dans cette réalisation. Le compilateur doit en tenir compte pour générer le code et pour effectuer les optimisations.

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

Solution 4-b :

Dans le processeur P9, il y a des dépendances de données d'ordre 1 à 6. En effet, le cycle DEC1 (où s'effectue la lecture du banc de registres) de l'instruction i+7 s'effectue après le cycle WBK de l'instruction i.

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

Solution 4-c :

1 bypass de la sortie de EXE2 vers EXE2 (ordre 1) : sur RT
```
    Add  r7 , r1 , r2
    Sw   r7 , 0(r3)
```

2 bypass de la sortie de EXE2 vers EXE1 (ordre 2) : un sur RS et un sur RT

    Add  r7 , r1 , r2         Add  r8 , r1 , r2
    ...                       ...
    Add  r9 , r7 , r8         Add  r9 , r7 , r8

1 bypass de la sortie de MEM2 vers EXE2 (ordre 3) : sur RT

    Lw   r7 , 0(r1)
    ...
    ...
    Sw   r7 , 0(r3)

2 bypass de la sortie de EXE2 vers DEC2 (ordre 3) : un sur RS et un sur RT

2 bypass de la sortie de MEM1 vers EXE1 (ordre 3) : un sur RS et un sur RT

    Add  r7 , r1 , r2         Add  r8 , r1 , r2
    ...                       ...
    ...                       ...
    Add  r9 , r7 , r8         Add  r9 , r7 , r8

2 bypass de la sortie de EXE2 vers DEC1 (ordre 4) : un sur RS et un sur RT

    Add  r7 , r1 , r2         Add  r8 , r1 , r2
    ...                       ...
    ...                       ...
    ...                       ...
    Beq  r7 , r8 , suite      Beq  r7 , r8 , suite

2 bypass de la sortie de MEM2 vers EXE1 (ordre 4) : un sur RS et un sur RT

    Lw   r7 , 0(r1)           Lw   r8 , 0(r1)
    ...                       ...
    ...                       ...
    ...                       ...
    Add  r9 , r7 , r8         Add  r9 , r7 , r8

2 bypass de la sortie de MEM1 vers DEC1 (ordre 5) : un sur RS et un sur RT

    Add  r7 , r1 , r2         Add  r8 , r1 , r2
    ...                       ...
    ...                       ...
    ...                       ...
    ...                       ...
    Beq  r7 , r8 , suite      Beq  r7 , r8 , suite

2 bypass de la sortie de MEM2 vers DEC2 (ordre 5) : un sur RS et un sur RT

    Lw   r7 , 0(r1)           Lw   r8 , 0(r1)
    ...                       ...
    ...                       ...
    ...                       ...
    ...                       ...
    Add  r9 , r7 , r8         Add  r9 , r7 , r8

2 bypass de la sortie de MEM2 vers DEC1 (ordre 6) : un sur RS et un sur RT

    Add  r7 , r1 , r2         Add  r8 , r1 , r2
    ...                       ...
    ...                       ...
    ...                       ...
    ...                       ...
    ...                       ...
    Add  r9 , r7 , r8         Add  r9 , r7 , r8

Au total il y a 16 bypass.

d - Quelles sont les situations qui provoquent des cycles de gel ? Illustrer chaque cas à l'aide d'un exemple d'une suite d'instructions.

Solution 4-d :

Toutes les dépendances qui ne peuvent pas être résolues par un bypass provoquent des cycles de gel.

dépendance d'ordre 1 sur RS ou sur RT (autre que les Store)
```
    Add  r7 , r1 , r2
    Add  r9 , r8 , r7
```

dépendance d'ordre 2 sur RS ou sur RT lorsque la valeur est produite par le cycle MEM2 ou lorsque l'opérande est consommé dans le cycle DEC1.
```
    Add  r7 , r1 , r2         Lw   r7 , 0(r1)
    ...                       ...
    Beq  r7 , r8 , suite      Add  r9 , r7 , r8
```

dépendance d'ordre 3 sur RS ou sur RT lorsque la valeur est produite par le cycle MEM2 ou lorsque l'opérande est consommé dans le cycle DEC1.

    Add  r7 , r1 , r2         Lw    r7 , 0(r1)
    ...                       ...
    ...                       ...
    Beq  r7 , r8 , suite      Add    r9 , r7 , r8

dépendance d'ordre 4 sur RS ou sur RT lorsque la valeur est produite par le cycle MEM2 et consommée dans le cycle DEC1.
```
    Lw   r7 , 0(r1)
    ...
    ...
    ...
    Beq  r7 , r8 , suite
```

dépendance d'ordre 5 sur RS ou sur RT lorsque la valeur est produite par le cycle MEM2 et consommée dans le cycle DEC1.
```
    Lw   r7 , 0(r1)
    ...
    ...
    ...
    ...
    Beq  r7 , r8 , suite
```

e - Modifier le code de la boucle pour qu'il soit exécutable sur le processeur P9.

Solution 4-e :

La manière la plus simple est de remplir les delayed slots avec des Nop.

loop:
    Lw    r8 , 0(r4)        ; lire un élément
    Bgez  r8 , _endif
    Nop
    Nop
    Nop
    Sub   r8 , r0 , r8      ; calculer l'opposé
    Sw    r8 , 0(r4)

_endif:
    Addiu r4 , r4 , 4
    Bne   r4 , r9 , loop
    Nop
    Nop
    Nop

f - Analyser l'exécution d'une itération de la boucle à l'aide d'un schéma simplifié.

Solution 4-f :

On a les dépendances de données suivantes :

entre le Lw et le Bgez (5 cycles de gel)
entre le Sub et le Sw (pas de cycle de gel)
entre le Addiu et le Bne (3 cycles de gel)

g - Calculer le CPI et le CPI-utile en supposant que 50% des nombres sont négatifs.

Solution 4-g :

Il faut 20 cycles pour une itération si le branchement échoue et 18 cycles s'il réussit. D'où :

CPI = (20*0.5 + 18*0.5)/(12*0.5 + 10*0.5) = 1.73 cycles/inst

CPI-utile = (20*0.5 + 18*0.5)/(6*0.5 + 4*0.5) = 3.8 cycles/inst-utile

h - Réordonner ce code de manière à éviter au maximum les cycles perdus.

Solution 4-h :

On peut déplacer le Addiu entre le Lw et le Bgez.

loop:
    Lw    r8 , 0(r4)        ; lire un élément
    Addiu r4 , r4 , 4
    Bgez  r8 , _endif
    Nop
    Nop
    Nop
    Sub   r8 , r0 , r8      ; calculer l'opposé
    Sw    r8 , -4(r4)

_endif:
    Bne   r4 , r9 , loop
    Nop
    Nop
    Nop

Il faut maintenant 16 cycles par itération si le branchement échoue et 14 cycles s'il réussit.

i - Optimiser ce code à l'aide de la technique "software pipeline".

Solution 4-i :

A première vue, on peut décomposer le traitement d'un élément du tableau en deux étapes : la lecture et le test et le rangement. On peut alors réorganiser le code de manière à traiter deux éléments dans une itération : la lecture de l'élément i et le rangement de l'élément i-1.

loop:
    Bgez  r8 , _endif
    Nop
    Nop
    Nop
    Sub   r10, r0 , r8  ; calculer l'opposé (elem i-1)
    Sw    r10, -4(r4)

_endif:
    Lw    r8 , 0(r4)    ; lire un élément (elem i)
    Addiu r4 , r4 , 4
    Bne   r4 , r9 , loop
    Nop
    Nop
    Nop

On peut maintenant réordonner ce code. Il faut écarter le Addiu et le Bne. On peut par exemple placer le Addiu avant le Bgez. Par contre, il vaut mieux ne pas placer le Lw dans les delayed slot du Bne. En effet, on a une dépendance entre le Lw et le Bgez de l’itération suivante. Pour que cette dépendance ne crée pas de cycle de gel, il faut au moins une distance de 6.

loop:
    Addiu r4 , r4 , 4
    Bgez  r8 , _endif
    Nop
    Nop
    Nop
    Sub   r10, r0 , r8   ; calculer l'opposé (elem i-1)
    Sw    r10, -8(r4)

_endif:
    Lw    r8 , -4(r4)    ; lire un élément (elem i)
    Bne   r4 , r9 , loop
    Nop
    Nop
    Nop

Il faut maintenant 12 cycles pour une itération si le branchement échoue et 10 cycles s'il réussit.

Une autre idée consiste à sortir le Sub de la partie du code exécutée de manière conditionnelle (on exécute le Sub dans tous les cas, et on ne fait le Sw que si le branchement échoue). On peut gagner alors 1 cycle en déplaçant le Sub dans le dernier delayed Slot du Bgez.

Il faut maintenant 11 cycles pour une itération si le branchement échoue et 10 cycles s'il réussit.

loop:
    Addiu r4 , r4 , 4
    Bgez  r8 , _endif
    Nop
    Nop
    Sub   r10, r0 , r8    ; calculer l'opposé (elem i-1)
    Sw    r10, -8(r4)

_endif:
    Lw    r8 , -4(r4)    ; lire un élément (elem i)
    Bne   r4 , r9 , loop
    Nop
    Nop
    Nop

Autre solution :

loop:
    Bgez  r8 , _endif
    Addiu r4 , r4 , 4
    Sub   r10, r0 , r8      ; calculer l'opposé
    Lw    r8 , -4(r4)       ; lire un élément

    Sw    r10, -8(r4)

_endif:
    Bne   r4 , r9 , loop
    Nop
    Nop
    Nop

Avec cette solution on a 9 cycles que le branchement réussisse ou non.

j - Le temps de cycle du processeur P9 est égal à 0,6 fois le temps de cycle du processeur Mips. Comparer le temps nécessaire à l'exécution d'une itération de la boucle entre le Mips et P9. Quelle conclusion en tirez-vous ?

Solution 4-j :

Si l'on considère le code original, dans P9, il faut 20 cycles pour l'exécuter. Dans le Mips, il faut 11 cycles si le branchement échoue et 9 cycles s'il réussit.

loop:
    Lw    r8 , 0(r4)    ; lire un élément
    Bgez  r8 , _endif
    Nop
    Sub   r8 , r0 , r8  ; calculer l'opposé
    Sw    r8 , 0(r4)

_endif:
    Addiu r4 , r4 , 4
    Bne   r4 , r9 , loop
    Nop

Ainsi, par rapport au Mips, l'exécution du code sans optimisation dans le P9 prend (20*0.5 + 18*0.5)*0.6/(11*0.5 + 9*0.5) = 1.14 fois plus de temps.

Si l'on optimise le code dans le Mips :

loop:
    Bgez  r8 , _endif
    Addiu r4 , r4 , 4
    Sw    r10, -8(r4)

_endif:
    Lw    r8 , -4(r4)     ; lire un élément
    Bne   r4 , r6 , loop
    Sub   r10 , r0 , r8   ; calculer l'opposé

et si on considère la meilleure optimisation obtenue dans P9, l'exécution dans P9 prend (11*0.5 + 10*0.5)*0.6/(6*0.5+5*0.5) = 1.15 fois plus de temps.

Même si la fréquence de fonctionnement de P9 est plus élevée que celle du Mips, globalement, sur ce code, le traitement est ralenti. Cela est dû au grand nombre de delayed slots dans P9 et au fait que la boucle étant très court, il n'y a pas beaucoup d'occasion d'ordonnancement. Sans doute en déroulant la boucle, on peut obtenir de meilleurs résultats.

Download in other formats:

Plain Text