Conception de processeurs rapides



- Organisation de processeurs sans pipeline (revision) :   (chapitre 4)
        - chemins de données à 1, 2 et 3 bus
- Conception avec pipeline :   (chapitre 5)
        - étages d'un pipeline d'instructions
        - dépendances, aléas ("hazards") et les solutions :
                - calage
                - sauts avec retard ("branch delay")
                - transit des données ("data forwarding")
                - chargement avec retard ("load delay")
- Émission d'instructions multiples (parallèle) :   (section 5.2)
        - Superscalaire
        - VLIW

Organisation de processeurs :

Description RT abstraite :  l'effet des instructions sur les registres et mémoire visibles au programmeur.
Description RT concrète : organisation du chemin de données et les transferts exactes nécessaires pour exécuter les instructions sur cette organisation particulière.
Plusieurs organisations réelles différentes peuvent exécuter le même jeux d'instructions.  Ceci veux dire qu'il y a plusieurs descriptions concrètes différentes possibles pour une même description abstraite (habituellement avec une performance et coût differents sur des modèles difféerents).

Réalisations concrètes pour la description abstraite de l'app.B :
Machine SRC à bus unique (sans pipeline) :  sections 4.2-4.5
Machine SRC à 2 et 3 bus (toujours sans pipeline) :  section 4.6


Pipelines :   (section 5.1)

Un pipeline c'est comme une chaine de montage.  Une instruction prend le même temps (pas exactement, mais bon...) pour être exécutée en entier mais on commence à exécuter la prochaine instruction avant d'avoir fini d'exécuter l'instruction courante. (pages 195-197)
Malheureusement, certaines instructions dépendent du résultat d'un instruction précédente et le fait de commencer une instruction avant d'avoir terminé la précédente peut causer des problèmes.  On appel ces problèmes aléas (ou "hazards").  Il y a plusieurs solutions à ces problèmes, dépendant du type de problème.

Dépendances entre les instructions :   (pages 198-199)
- Résultat d'une instruction est l'opérande de l'instruction suivante
- Condition de branchement n'est connue qu'après la recherche d'instruction suivante
- Chargement de registre, à partir de la mémoire (load), arrive trop tard
Solutions :
Une triviale, mais lente:
- Bloquer l'exécution (calage ou "stall") en attendant le résultat
Pour accélérer, on peut:
- Passer le résultat plus rapidement, sans passer par les registres ("forwarding")
- Exécuter toujours l'instruction qui suit un branchement ("delay slot")
- Prédiction de branchement
- Réorganiser le programme pour éliminer la dépendance ("load delay")

Positions de retard ("delay slots") :
Si on a une position de retard de branchement ("one branch delay slot") :
    la      r2, X  ; adresse ailleur dans le programme
    brzr r2, r3     ; brancher à l'adresse dans r2  si r3 = 0
    add r6, r7, r8  ; Cette instruction est toujours exécutée
    st  r6, addr    ; Exécutée seulement si r3 différent de 0
Si on a une position de retarde de chargement :
    ld  r2, addr
    add r5, r1, r2  ; Cette instruction utilise l'ancienne valeur de r2
    sub r6, r8, r2  ; Celle-ci obtient la nouvelle valeur de r2 (chargée de addr)
 

Caractéristiques des processeurs à pipeline :

- La mémoire doit répondre en un cycle d'horloge (pour aller chercher les instructions)
        - Queue de "prefetch"
        - Mémoire cache (vue plus loin dans le cours)
- Les mémoires d'instructions et de données doivent apparaître séparées
        - Architecture "Harvard" plutôt que "von Neumann"
        - Obtenue généralement avec caches séparés instructions/données, mais en gardant une mémoire principale commune.
- Peu de bus utilisés
        - La plupart des connexions sont point-à-point (moins de délai)
        - Quelques multiplexeurs utilisés
- Données et parties d'instructions sont mémoirisées à l'entrée de chaque étage du pipeline (registres tampons, "pipeline registers")
- Les opérations de l'UAL se font en un cycle (virgules flottantes sont traitées à part)

Structure du pipeline de la SRC :

Toute instruction passe par tous les étages.
Pipeline à 5 étages (assez commun pour les processeurs simples)
        - Recherche d'instruction
        - Décodage et lecture des opérandes (dans les registres)
        - Opération de l'UAL
        - Accès à la mémoire de données (lecture ou écriture)
        - Écriture des registres (les effets de l'instruction)
Donc une instruction prend 5 cycles d'horloge pour s'exécuter, mais s'il n'y a pas d'aléas, une instruction commence (et aussi, une termine) à chaque cycle.

Opérations sur l'unité arithmétique et logique :  pages 203-204
Opérations d'accès mémoire :  pages 204-206
Opérations de branchement :  page 206

Intégration des registres tampons du pipeline :
(voir figure 5.6, page 209)
- Registres de pipeline isolent les étages
- RT spécifie les valeurs des registres en sortie de l'étage en fonction des valeurs des registres en entrée du même étage.
- PC accédé dans les étages 1 et 2
- Registres lus dans l'étage 2 et écrits dans l'étage 5
- Mémoire d'instructions lue dans l'étage 1, et mémoire de données accédée dans l'étage 4

Il faut pouvoir tout faire en même temps (tous les étages fonctionnent à chaque cycle d'horloge).
Il faut pouvoir faire en même temps:
- lire une instruction (étage 1) et accéder une donnée en mémoire (étage 4).  Donc, il faut des mémoires séparées, ou une mémoire à deux ports.
- lire deux opérandes (étage 2) et écrire le résultat (étage 5).  Donc, il faut une banque de registres avec deux ports de lecture et un d'écriture.

Le chemin de données permettant tout ça : Fig. 5.7, page 210.

Fonctions des registres du pipeline SRC :
- Entre étages 1 et 2 :
    - IR2 contient l'instruction au complet
    - PC2 contient le PC incrémenté de 4, utilisé dans les modes d'adressage relatifs et appels de sous-routines
- Entre étages 2 et 3 :
    - IR3 contient le code d'opération et ra (qui est utilisé dans l'étage 5)
    - X3 contient la première opérande de l'UAL (soit le PC+4, soit le contenu d'un registre)
    - Y3 contient la deuxième opérande de l'UAL (soit une constante (c1 ou c2), soit le contenu d'un registre)
    - MD3 contient la valeur à mettre en mémoire lors d'un "store" (contenu d'un registre, pour l'étage 4)
- Entre étages 3 et 4 :
    - IR4 (comme IR3)
    - Z4 contient le résultat de l'UAL, qui peut être le résultat d'une opération ou l'adresse d'un accès mémoire (fait à l'étage 4)
    - MD4 (comme MD3)
- Entre étages 4 et 5 :
    - IR5 (comme IR3)
    - Z5 contient la valeur à mettre dans le registre destination (le PC dans un "brl", le résulat de l'UAL ou d'une lecture mémoire)

Fonctions des étages du pipeline SRC :
- Étage 1 :  recherche d'instruction
    - Lecture en mémoire à l'adresse contenu dans le PC
    - Incrémentation du PC placé dans PC2
- Étage 2 :  décode l'instruction et recherche les opérandes
    - Met les opérandes dans X3 et Y3 (constante ou contenu d'un registre)
    - Pour "store" :  met la valeur du registre source dans MD3
    - Met dans le PC, soit PC+4, soit l'adresse de destination du branchement (lorqu'un branchement est fait)
- Étage 3 :  effectue l'opération de l'UAL (Unité Arithmétique et Logique)
    - Calcule l'adresse effective, le resultat d'une opération (arithmétique ou logique) ou laisse passer le PC pour "branch and link"
    - Laisse passer la valeur de MD3 (pour "store")
- Étage 4 :  accès à la mémoire de données
    - Passe Z4 à Z5 pour les instructions sans accès mémoire
    - Passe Z4 comme adresse à la mémoire pour les instructions "load" et "store"
    - Pour "load" on met le résultat dans Z5, pour "store" on prend la donnée de MD4
- Étage 5 :  écrit dans le registre de résultat (ra)
    - Écrit la valeur de Z5 dans le registre ra si l'opération écrit dans un registre

Exemple de propagation d'instructions dans le pipeline :  section 5.1.5

Dépendances entre instructions dans le pipeline :  Les aléas   (section 5.1.6)

Dans un pipeline, la prochaine intruction commence avant que la précédente se termine.  Ceci pose un problème si les opérandes d'une instruction dépendent du résultat de l'autre instruction.  Le fait d'exécuter dan pipeline change l'ordre d'exécution réel des choses. (Normalement l'instruction 1 se fait avant l'instruction 2, mais dans un pipeline l'étage 5 de l'instruction 1 se fait après l'étage 2 de l'instruction 2, par exemple).
Ce changement d'ordre entraine deux types d'aléas :
- Aléa de données :  utilisation de la mauvaise donnée
- Aléa de branchement :  une instruction incorrecte est recherchée (car le PC n'est pas modifié au même moment lors d'un branchement)

Les types de dépendances pouvant produite de aléas de données :
(les noms sont selon l'ordre qui devrait être utilisé pour que le programme fonctionne)
- Lecture après écriture :  (Read After Write - RAW) une instruction utilise les données produites par une instruction précédente.  S'appel aussi dépendance de flux de données.
- Écriture après lecture :  (Write After Read - WAR) une instruction écrit dans un emplacement qui est utilisé comme opérande dans une instruction précédente.  S'appel aussi anti-dépendance.
- Écriture après écriture :  (Write After Write - WAW) une intruction écrit dans le même emplacement qu'un instruction précédente.  S'appel aussi dépendance de sortie.
Peut-il y avoir un aléa lorsqu'il y a lecture après lecture?  Non.

Aléas de données dans le pipeline SRC :
- Tout accès à la mémoire de données est dans l'étage 4, donc les accès mémoires sont fait dans le bon ordre (pas d'aléa ici).
- Toute écriture de regstre est dans l'étage 5, donc pas d'aléa WAW.
- Pour WAR dans les registres :  l'écriture dans l'étage 5 se fait après la lecture dans l'étage 2, donc pas d'aléa WAR.
- Pour RAW dans les registres :  la lecture dans l'étage 2 peut se produire avant et l'écriture dans l'étage 5, donc il peut y avoir aléa.

Solution aux aléas de données :
- Programme écrit pour qu'aucun aléa se produise.
- Détection automatique à l'exécution :
        - calage :  attente (perte de performance)
        - transit de données ("data forwarding") :  passer les résultat sans passer par les registres

Détection des aléas et distance de dépendance :  Table 5.1, page 220

Calage du pipeline dû à un aléa :
Lorsqu'on détecte un aléa, le contrôle peut caler les étages précédents en attendant que les étages suivants complètent l'opération qui cause l'aléa.  Une façon simple de le faire est d'inhiber l'horloge vers les registres destinations des étages en attente et il faut aussi passer une instruction NOP (une bulle) à l'étage qui n'a rien à faire.
Exemple :  Fig. 5.14, page 223

Transit de données (UAL à UAL) :  pages 223-225

Restrictions qui restent après la réalisation du transit de données :
- Position de retard de branchement ("branch delay slot")
        - L'instruction après un branchement est toujours exécutée
- Position de retard de chargement ("load delay slot")
        - Le registre chargé de la mémoire ne peut pas étre utilisé dans l'instruction suivante
        - Ni deux instructions après, si le registre est utilisé comme cible ou comme condition pour un branchement


Parallélisme au niveau d'instructions :   (section 5.2)

Un pipeline même rempli (et sans aléa) ne peut completer qu'une instruction par cycle d'horloge (appelé, des fois, la limite de Flynn).
Si on recherche plus d'une instruction à la fois et qu'il y a plusieurs unités fonctionnelles alors il est possible d'émettre plusieurs instructions en même temps, et donc de terminer plus d'une instruction par cycle.
Deux approches :
- Superscalaire :  émettre dynamiquement autant d'instructions prérecherchées que possible aux unités fonctionnelles disponibles.
- Mot d'instruction très large (Very Long Instruction Word - VLIW) :  plusieurs opérations sont mises dans chaque mot d'instruction (qui sont donc des gros mots).  Toutes les opération d'un mot sont exécutées en parallèle.

Machines à émission d'instructions multiples :
- Types des unités fonctionnelles :
        - Virgule flottante
        - Entier
        - Branchement
        - Accès mémoire
- Plus d'une unité de chaque type
- Chaque unité peut avoir un pipeline
- Problème restant : bris du flux d'instruction par des branchements
        - Aide par logiciel :  déroulement des boucles d'itération
        - Aide par matériel :  unité de branchement avec prédiction (pour prérecherche ou même exécution spéculative)


Présentation en classe (.PDF)