Examen #3

INF4170 -- Architecture des ordinateurs
Examen #3 (30 juillet 1996)

Durée: 17:30 - 19:00 Documentation autorisée: Toute documentation personnelle.

Nom:

Code permanent:

1. Pipeline et aléas de branchement (10 pts)

Soit une machine avec un pipeline de 4 étage où le nettoyage du pipeline entraîne une pénalité de 2 bulles.

Supposons que les branchements représentent 25% des instructions exécutées et que l'on utilise une technique de prédiction dynamique des branchements.

Quel devrait être le taux minimal de succès des prédictions pour que le CPI moyen (asymptotique) de la machine soit inférieur à 1.1?

2. Pipeline et aléas (15 pts)

Soit un pipeline à 3 étages comme suit (i.e., les actions effectuées dans chacun des étages correspondent à la combinaison des actions correspondantes du pipeline à 5 étages) et où la condition pour un branchement est déterminée (connue) seulement à la fin du étage:

[5]a) Soit la boucle suivante:

     Boucle:    addi  $10, $10, -1  
                add   $20, $20, $10  
                bne   $20, $0, Boucle

i) Combien de cycles d'horloge seront requis pour exécuter N itérations de cette boucle dans le cas où des instructions nop sont ajoutées par le compilateur pour éliminer les aléas (données et branchement)?

[10]b) Supposons de façon plus générale que:

• 20% des instructions exécutées sont des branchements;
• 45% des branchements sont effectués (condition vraie).

Si l'on désire traiter les branchements à l'aide d'une stratégie de prédiction statique.

i)
Serait-il préférable de prédire que le branchement sera effectué ou de prédire qu'il ne s'effectuera pas? Pourquoi?

ii)
Quel sera alors le délai moyen dû aux aléas de branchement en utilisant cette prédiction?

3. Cache (10 pts)

Soit un cache associatif par ensemble de 2 avec 8 lignes de cache, où chaque bloc contient 4 mots (de 4 octets chacun), où les étiquettes occupent 2 octets et où une stratégie de réécriture est utilisée. Quelle sera la taille totale du cache (en octets)? (N'oubliez pas de tenir compte des bits associés à la gestion des lignes de cache.)

4. Machine superscalaire (10 pts)

On désire comparer deux (2) mises en oeuvre d'une même architecture:

• : Mise en oeuvre utilisant un pipeline comme celui du chapitre 6 et utilisant une fréquence d'horloge de 125 MHz.
• : Mise en oeuvre superscalaire qui réussit à exécuter, en moyenne, 2 instructions par cycle et dont la fréquence d'horloge est de 100 MHz.

Si on ignore les délais associés aux aléas et aux accès mémoire, quelle machine est la plus rapide et de combien?

5. Pipeline et caches (15 pts)

Soit une machine avec un pipeline dans le style de celui du chapitre 6 (pipeline à 5 étages) et supposons que l'on ait les temps suivants d'opération pour les diverses unités fonctionnelles:

• Accès mémoire avec succès cache: 10 ns
• Opération UAL: 8 ns
• Accès au banc de registres: 6 ns
• Autres éléments: négligeable

[5]a) Quelle fréquence d'horloge pourrait être utilisée pour cette machine avec pipeline?

[10]b) Supposons que, pour des raisons de coût, on doive utiliser un cache moins performant dont le temps d'accès, en cas de succès, est de 15 ns.

i) Si on garde la même structure de pipeline, quelle fréquence d'horloge devrait maintenant être utilisée?

ii) Proposez une stratégie permettant d'utiliser une fréquence d'horloge plus élevée, si nécessaire en modifiant la structure du pipeline. Quelle serait alors la fréquence d'horloge utilisée?

6. Machines superscalaires (5 pts)

Pour chacun des énoncés suivants, dites s'il caractérise correctement les machines superscalaires modernes:

1. Le temps total requis pour exécuter complètement une instruction, en ignorant les aléas et fautes de cache, est de un (1) cycle.

   

2. Pour que la machine fonctionne efficacement, il suffit que le cache d'instructions soit capable de fournir, à chaque cycle, une (1) instruction à la fois.

   

7. Chaîne de montage (15 pts)

Une usine de lampes utilise une chaîne de montageassemblage composée de 3 étapes. Une lampe, pour être fabriquéeassemblée, doit parcourir séquentiellement chacune des étapes. Le temps requis pour chacune de ces étapes est comme suit:

Supposons que 3 personnes soient engagées pour assembler des lampes et que chacune est assignée à une des étapes (personne # Étape #i).

[5]a) Combien de temps sera requis, au total, pour assembler N lampes?

[10]b) Le problème avec cette chaîne de montage est que l'étape #2 représente une forme de goulot d'étranglement: le travail complété en #1 s'accumule alors que #3 passe la moitié de son temps à ne rien faire.

Proposez une stratégie qui augmenterait la productivité et assurerait une meilleure utilisation des diverses étapes de la chaîne de montage. Votre proposition doit tenir compte du fait que le travail à l'étape #2 ne peut pas être scindé en deux sous-étapes indépendantes. Combien de temps serait alors requis pour assembler N lampes? (Utilisez le verso si nécessaire.)

• About this document ...