Changes between Version 2 and Version 3 of fr-Architecture_Predictor


Ignore:
Timestamp:
Apr 17, 2008, 11:04:19 AM (16 years ago)
Author:
kane
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • fr-Architecture_Predictor

    v2 v3  
    1818Posons comme hypothèse que la section code d'un programme est en lecture seule, ceci implique que si le processeur décode un branchement à une adresse donnée, alors pour tous cycles, il y aura toujours le même branchement à cette même adresse. Ce principe est exploité dans les caches et ce base sur la localité temporelle (il y a de grande probabilité pour qu'un branchement soit réutilisé dans un avenir proche).
    1919
    20 Ce cache ce nomme couramment '''Branch Target Buffer''' (BTB) ([wiki:fr-Bibliography#bib_1983_lee 1983_lee]). La partie contrôle de ce cache sert à déterminer la présence d'un branchement. Avec les hypothèses données, un hit informe la présence d'un branchement, alors qu'un miss informe soit l'absence d'un branchement, ou un branchement mais jamais rencontré ou évincé car rarement utilisé. Ceci est une prédiction de la présence d'un branchement.
     20Ce cache ce nomme couramment '''Branch Target Buffer''' (BTB) ([wiki:common-Bibliography#bib_1983_lee 1983_lee]). La partie contrôle de ce cache sert à déterminer la présence d'un branchement. Avec les hypothèses données, un hit informe la présence d'un branchement, alors qu'un miss informe soit l'absence d'un branchement, ou un branchement mais jamais rencontré ou évincé car rarement utilisé. Ceci est une prédiction de la présence d'un branchement.
    2121
    2222== Destination ==
    … …  
    3333Pour le deuxième cas, nous allons réutilisons l'adresse stocké dans le BTB. (Il y a donc 2 ports d'écritures pour mettre à jour l'adresse : le premier au moment de l'étage décode, le second au moment à l'étage commit.
    3434
    35 Pour le troisième cas, nous nous référons au travaux de Kaeli et Emma ([wiki:fr-Bibliography#bib_1991_kaeli 1991_kaeli]) qui constatent que pour chaque appel de procédure, il y a un retour de procédure associé. Pour ce faire, nous utilisons une pile qui va stocker les adresses de retour des appels de procédure. Cette pile porte en général le nom de '''Return Address Stack''' (RAS). A chaque appel de procédure, nous allons empiler l'adresse de retour (PC + 8 (ne pas oublier le Delayed Slot)). Si la pile est pleine, la plus ancienne sera écraser. Dans le cadre d'un retour de procédure, nous dépilons alors le sommet de pile et sera l'adresse de retour. Si la pile est vide, le prédicteur de branchement informe l'étage '''Ifetch''' d'attendre de ne plus être spéculatif. Ceci est réaliser en informant que le prédicteur est occupé.
     35Pour le troisième cas, nous nous référons au travaux de Kaeli et Emma ([wiki:common-Bibliography#bib_1991_kaeli 1991_kaeli]) qui constatent que pour chaque appel de procédure, il y a un retour de procédure associé. Pour ce faire, nous utilisons une pile qui va stocker les adresses de retour des appels de procédure. Cette pile porte en général le nom de '''Return Address Stack''' (RAS). A chaque appel de procédure, nous allons empiler l'adresse de retour (PC + 8 (ne pas oublier le Delayed Slot)). Si la pile est pleine, la plus ancienne sera écraser. Dans le cadre d'un retour de procédure, nous dépilons alors le sommet de pile et sera l'adresse de retour. Si la pile est vide, le prédicteur de branchement informe l'étage '''Ifetch''' d'attendre de ne plus être spéculatif. Ceci est réaliser en informant que le prédicteur est occupé.
    3636
    3737Afin de sélectionner la bonne adresse de destination, nous devons connaître le type du branchement. Le type sera donc également enregistré dans la BTB.
    … …  
    4343Le troisième rôle d'un prédicteur de branchement est de déterminer si la partie génératrice d'adresse doit utiliser une adresse en séquence ou doit utiliser l'adresse fournit par le prédicteur de branchement. Pour ce faire, le type de l'instruction est importante : les sauts (l.j, l.jr, l.jal, l.jalr) vont toujours prendre alors que les branchements conditionnels (l.bf et l.bnf) vont dépendre de leur historique.
    4444
    45 Les articles [wiki:fr-Bibliography#bib_1992_yeh 1992_yeh], [wiki:fr-Bibliography#bib_1992_pan 1992_pan] et [wiki:fr-Bibliography#bib_1993_yeh 1993_yeh] définissent un schma gnral des prdicteurs de branchements  deux niveaux. Selon les notations de [wiki:fr-Bibliography#bib_1993_yeh 1993_yeh], le premier niveau appelé '''Branch History Table''' (BHT) est une table contenant des registres à décalage. Ces derniers représentent les ''c'' derniers directions de branchements survenus. Le deuxième niveau est appelé '''Pattern History Table''' (PHT) qui est une table de compteur à saturation de ''d'' bits. Ce compteur permet de sauvegarder le comportement des ''2^d^'' dernières occurrences.
     45Les articles [wiki:common-Bibliography#bib_1992_yeh 1992_yeh], [wiki:common-Bibliography#bib_1992_pan 1992_pan] et [wiki:common-Bibliography#bib_1993_yeh 1993_yeh] définissent un schma gnral des prdicteurs de branchements  deux niveaux. Selon les notations de [wiki:common-Bibliography#bib_1993_yeh 1993_yeh], le premier niveau appelé '''Branch History Table''' (BHT) est une table contenant des registres à décalage. Ces derniers représentent les ''c'' derniers directions de branchements survenus. Le deuxième niveau est appelé '''Pattern History Table''' (PHT) qui est une table de compteur à saturation de ''d'' bits. Ce compteur permet de sauvegarder le comportement des ''2^d^'' dernières occurrences.
    4646
    4747La figure \label{MORPHEO_component-prediction_unit-predictor} présente un prédicteur 2 niveaux généralistes. Par la suite les BHT et PHT sont considéré comme des structures à correspondance direct. Ceci permet d'économiser de la surface en ne rajoutant aucun Tag. De plus le gain est négligeable. Nous allons maintenant approfondir les deux blocs principaux du choix de la direction : la BHT et la PHT.
    … …  
    4949=== Branch History Table ===
    5050
    51 Le premier niveau de prédiction contient ''2^a^'' registres à décalages. Ces registres contiennent les résultats des branchements de ''c'' dernier branchement. La table est indexée par les ''a'' bits les moins significatif de l'adresse du branchement. Selon la nomenclature de Yeh et Patt ([wiki:fr-Bibliography#bib_1992_yeh 1992_yeh], [wiki:fr-Bibliography#bib_1993_yeh 1993_yeh]), si ''2^a^=1'', alors il y a un seul historique pour tout les branchements, le BHT est dit Prédicteur Global (Global Branch History Register (GBHR) ). Sinon le Prédicteur est dit Local (Per address Branch History Table (PBHT) ). Il existe une troisième version, le Par ensemble (Per set Branch History Register (SBHT) ) mais dont les ensembles sont déterminées par le compilateur ou à partir de l'adresse du branchement, ou encore par un numéro de contexte.
     51Le premier niveau de prédiction contient ''2^a^'' registres à décalages. Ces registres contiennent les résultats des branchements de ''c'' dernier branchement. La table est indexée par les ''a'' bits les moins significatif de l'adresse du branchement. Selon la nomenclature de Yeh et Patt ([wiki:common-Bibliography#bib_1992_yeh 1992_yeh], [wiki:common-Bibliography#bib_1993_yeh 1993_yeh]), si ''2^a^=1'', alors il y a un seul historique pour tout les branchements, le BHT est dit Prédicteur Global (Global Branch History Register (GBHR) ). Sinon le Prédicteur est dit Local (Per address Branch History Table (PBHT) ). Il existe une troisième version, le Par ensemble (Per set Branch History Register (SBHT) ) mais dont les ensembles sont déterminées par le compilateur ou à partir de l'adresse du branchement, ou encore par un numéro de contexte.
    5252
    5353=== Pattern History Table ===
    … …  
    6666Chaque prédicteur est efficace sur un type précis pattern. Par exemple les prédicteurs locaux sont performants pour les branchements qui exécute des patterns répétitifs (L'exemple le plus commun étant la boucle énumérée (for)), alors que les prédicteurs globaux sont efficaces pour par exemple des boucles imbriqués.
    6767
    68 De cette constatation, !McFarling [wiki:fr-Bibliography#bib_1993_mcfarling 1993_mcfarling] à conçut le prédicteur combiné (appelé également le méta prédicteur).  L'objectif de ce prédicteur est de tirer partie de plusieurs prédicteurs différent. Dans son concept général (voir figure \label{MORPHEO_component-prediction_unit-meta_predictor} ), il y a 3 prédicteurs. 2 qui vont prédire la direction à prendre, et le dernier qui va prédire quel prédicteur à le plus de chance d'avoir la bonne prédiction. Ce dernier prédicteur est mis à jour par rapport au succès de sa prédiction. Cette structure peut être récursive : un prédicteur appartenant au méta prédicteur peut lui-même être un méta prédicteur.
     68De cette constatation, !McFarling [wiki:common-Bibliography#bib_1993_mcfarling 1993_mcfarling] à conçut le prédicteur combiné (appelé également le méta prédicteur).  L'objectif de ce prédicteur est de tirer partie de plusieurs prédicteurs différent. Dans son concept général (voir figure \label{MORPHEO_component-prediction_unit-meta_predictor} ), il y a 3 prédicteurs. 2 qui vont prédire la direction à prendre, et le dernier qui va prédire quel prédicteur à le plus de chance d'avoir la bonne prédiction. Ce dernier prédicteur est mis à jour par rapport au succès de sa prédiction. Cette structure peut être récursive : un prédicteur appartenant au méta prédicteur peut lui-même être un méta prédicteur.
    6969
    70 Dans la version définit dans [wiki:fr-Bibliography#bib_1993_mcfarling 1993_mcfarling], il s'agit d'un prédicteur bimodal qui va sélectionner entre un prédicteur global et un prédicteur local.
     70Dans la version définit dans [wiki:common-Bibliography#bib_1993_mcfarling 1993_mcfarling], il s'agit d'un prédicteur bimodal qui va sélectionner entre un prédicteur global et un prédicteur local.
    7171
    7272=== Mise à jour ===