source: trunk/IPs/systemC/processor/Morpheo/Documentation/Source/Documents/article-07sympa/common/bibliographie.bib @ 63

@book{1983_Lee,
  title={{Analysis of Branch Prediction Strategies and Branch Target Buffer Design}},
  author={Lee, J.K.F. and Smith, A.J.},
  year={1983},
  publisher={Computer Science Division (EECS), University of California}
}
@article{1991_kaeli,
  title={{Branch history table prediction of moving target branches due to subroutine returns}},
  author={Kaeli, D.R. and Emma, P.G.},
  journal={Proceedings of the 18th annual international symposium on Computer architecture},
  pages={34--42},
  year={1991},
  publisher={ACM Press New York, NY, USA}
}
@article{scherson1991ogc,
  title={{Orthogonal graphs for the construction of a class ofinterconnection networks}},
  author={Scherson, ID},
  journal={Parallel and Distributed Systems, IEEE Transactions on},
  volume={2},
  number={1},
  pages={3--19},
  year={1991}
}
@article{1991_wall,
  title={{Wall, Limits of instruction-level parallelism}},
  author={David, W.},
  journal={Proceedings of the fourth international conference on Architectural support for programming languages and operating systems},
  pages={176--188},
  year={1991}
}

01/12/2004

Etude sur le niveau de parallélisme d'un programme => l'ILP ne dépasse pas 5-7 instructions
Ceci déterminera la viabilité d'ajout de mécanismes pour traiter en parralléle un maximum d'instructions (superscalaire, renommage de registre etc..)
               #instruction
Parrallelism = -------------
               #cycle requit

Le parallélisme est en moyenne de 3-4 inst. Peut être plus haut (ex. Programme numérique). Le profit d'une crête de parrallélisme est bas si la moyenne est basse.

Augmenter l'ILP : 2 variétés de techniques :
 a) Parrallélisme dans un bloc de base
 b) Parrallélisme entre plusieurs blocs de base

a) limité par les dépendances entre paire d'instructions
    -> Renommage de registres (Hardware ou Software). Les compilos préfére utilisé le moins de registres possibles.
    -> Pur les dépendances d'adresse mémoire => analyse d'alias
b) Nombre d'instructions entre 2 branchements est en moyenne moins de 6 instructions
    -> Prédiction de branchement pour exécuter de manière spéculatives les blocs de bases
    -> Déroullement de boucles => augmentation de la taille des blocs de base
    -> Pipeline logiciel => augmente le parallélisme au sein d'un bloc
    -> Ordonnanceur de trace => trace : séquence de blocs souvent éxecuté

CADRE DE TRAVAIL:

* Execution du programme pour produire une trace d'execution
* Algorithme va "paquetiser" ses instructions en groupe d'instruction non suspendu => on tente d'avoir 64 inst en //
* Pas de limites d'unité fonctionnelle ni de limite d'accès au banc de registres. Chaque instruction à une latence d'un cycle, de même pour les opérations mémoires
* L'execution se faire par groupe de paquet, si la suspension à également lieu dans le modèle, alors le paquet suivant sera exécuter le cycle suivant. Sinon, nous pouvons l'exécuter le même cycle.

Le parrallélisme sera donc le nombre d'instruction par le nombre de cycles

Paramètres :
Register renamings : Parfait(nombre infinie de registres)
                     finit (allocation dynamique => LRU, 256 registres entier, 256 flottant)
                     aucun
Prédiction de branchement : Prédiction parfaite (tjs correctement prédit)
                            finit (dynamique) (prédiction d'un schéma à 2 bits , avec une table à 2048 entrées)
                            finit (statique)  (tjs la même prédiction (dépendant de la prédiction parfaite))      
                            aucun -> prédiciton tjs faux
Idem pour le jump prediction
analyse d'alias : Parfait (Il y a un conflit d'adresse que si l'adresse d'une écriture est la même qu'une autre écriture ou lecture)
                  Aucune analyse (Une écritures sont en conflits avec chaque autre écriture et lecture)
                  inspection d'instruction => pas de conflits si même registre de base mais dpt différent
                                                              si registre de base différent (Mais explecitement différent ex utilisation de sp et gp qui sont deux pointeurs différents)
                  analyse par le compilateur => analyse parfaite de la pile et des références globales
Taille de la fenêtre : Nombre maximum d'instructions pouvant apparaître dans un cycle de traitement
                     => Gestion de la fenêtre de manière discrète (Chercher une fênetre entière)
                                                         continue (Chercher autant d'instruction qui viennent de ce terminer)

Définitions de 5 modèles :

          +----------------+--------------+--------------+----------------+
          | branch Perfect | Jump predict | Reg renaming | Alias analysis |
+---------+----------------+--------------+--------------+----------------+
| Stupid  | none           | none         | none         | none           |
| Fair    | infinite       | infinite     | 256          | inspection     |
| Good    | infinite       | infinite     | 256          | perfect        |
| Great   | infinite       | infinite     | perfect      | perfect        |
| Perfect | perfect        | perfect      | perfect      | perfect        |
+---------+----------------+--------------+--------------+----------------+

Pour une taille de fenêtre de 2048 instructions ( continue)

Sur les jeux de tests, on notera que le parrallélisme du modèle :
 - stupide ne dépasse pas 2 
 - pauvre  ne dépasse pas 4
 - Great   ne dépasse pas 8 sauf pour quelque modèle numérique qui exploite l'analyse des alias 
 - Parfait 

Le déroullage de boucles à un effet significatif pour les modèles ambitieux. Sinon, ceci est limite par les load de début de boucle et les stores de fin de boucles (càd réduite par les technique d'alias analysis)

Taille de la fenêtre

La modification de la taille de la fenêtre n'influe que sur les modèles ambitieux grâce à leur technique de prediction améliorer. La plupart des benchmarks ont besoin que d'une fenêtre de 32 inst
Avec une gestion de fenêtre demanière discrete, cela exploite moins de parrallélisme (- d'inst prete)

Effet des predictions de branchements :

Réduire le niveau de la prédiction de branchment à un impact significatif sur le parrallélisme (Beaucoup moins d'instructions prête à être executer). Mais réduire le niveau de la prédiction de saut n'a d'effet que si la prédiction de branchement est parfaite.
De plus sur le modèle parfait, l'augmentation de la latence d'un miss à un effet significatif sur le parrallélisme (Car les instructions feteched ne sont plus executé en parralléle car les instructions précédentes sont déjà terminées)

Effet du rennommage de registres et de l'analyse des alias

L'analyse d'alias par inspection n'est pas très performantes (augmente l'ILP de 0.5). L'analyse par compilation n'est performante que pour des programmes utilisant la pile .
Le nombre de registre pour le renomage de registres n'influe que très peu sur le parallélisme dans un modèle où les prédictions ne sont pas parfaite (à l'exception faite des programmes ayant beaucoup de dépendance)

CONCLUSION

Une bonne prédiction (hard ou soft) est un facteur déterminant pour l'augmentation de l'ILP. Le renommage de registres est important si le compilateur l'exploite.
Le parrallelism moyen tourne autour de 5 d'après cette étude. (Dans un contexte très favorable => latence des inst = 1, etc...)
@article{1992_pan,
  title={{Improving the accuracy of dynamic branch prediction using branch correlation}},
  author={Pan, S.T. and So, K. and Rahmeh, J.T.},
  journal={Proceedings of the fifth international conference on Architectural support for programming languages and operating systems},
  pages={76--84},
  year={1992},
  publisher={ACM Press New York, NY, USA}
}
@article{1992_yeh,
  title={{Alternative Implementations of Two-Level Adaptive Branch Prediction}},
  author={Yeh, T.Y. and Patt, YN},
  journal={Computer Architecture, 1992. Proceedings., The 19th Annual International Symposium on},
  pages={124--134},
  year={1992}
}
@techreport{1993_mcfarling,
  title={{Combining Branch Predictors}},
  author={McFarling, S.},
  institution={Technical Report WRL Technical Note TN-36, Digital Equipment Corporation, June 1993}
}
@article{1993_Perleberg,
  title={{Branch target buffer design and optimization}},
  author={Perleberg, CH and Smith, AJ},
  journal={Computers, IEEE Transactions on},
  volume={42},
  number={4},
  pages={396--412},
  year={1993}
}
@article{1993_yeh,
  title={{A comparison of dynamic branch predictors that use two levels of branch history}},
  author={Yeh, T.Y. and Patt, Y.N.},
  journal={Proceedings of the 20th annual international symposium on Computer architecture},
  pages={257--266},
  year={1993},
  publisher={ACM Press New York, NY, USA}
}
@article{gallagher1994dmd,
  title={{Dynamic memory disambiguation using the memory conflict buffer}},
  author={Gallagher, D.M. and Chen, W.Y. and Mahlke, S.A. and Gyllenhaal, J.C. and Wen-mei, W.H.},
  journal={Proceedings of the sixth international conference on Architectural support for programming languages and operating systems},
  pages={183--193},
  year={1994},
  publisher={ACM Press New York, NY, USA}
}
@InProceedings{1995_sohi,
  author =       {Sohi, G.S.     and
                  Breach, S.E.   and
                  Vijaykumar, T.N. },
  title =        {Multiscalar processors},
  OPTcrossref =  {},
  OPTkey =       {},
  OPTbooktitle = {Computer Architecture, 1995. Proceedings. 22nd Annual International Symposium on},
  OPTpages =     {414-425},
  OPTyear =      {1995},
  OPTeditor =    {},
  OPTvolume =    {},
  OPTnumber =    {},
  OPTseries =    {},
  OPTaddress =   {Santa Margherita Ligure  ,   Italy},
  OPTmonth =     {22-24 Jun},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote =      {},
  OPTannote =    {}
}

22/02/2005

Paradigme de base : fetch-execute - pointé par un program counter
                    -> sous entend que les instructions vont être executer dans le même ordre que le programme.

processeur ILP et les compilos désordonne le programme en respectant toutefois les dépendances sur les données et les controles.
Les dépendances de contrôles peuvent être représenté par un "control flow graph" -> bloc de bases sont représenté par des noeuds et les arcs représentent les flots de contrôles

Overview
--------
Objectif : A partir du "control flow graph" (CFG), on peut établir une fenêtre dynamique d'instruction pouvant être extré et lancé.

le CFG peut être vut : - instruction / instruction
                       - bloc / bloc
                       - tâche / tâche (thread)

Assignation d'une tâche à une unité d'execution.
Le multiscalar à une collection d'unité d'execution et un séquenceur s'occupant de distribuer les tâches au UE.

=> Obligation de maintenir l'ordre séquentielle de consommation et de production de données (registre ou accès mémoire)
 Synchronisation  des accès mémoires 
 - approche conservatrice : Attendre que les accès mémoires des tâches moins spéculatives soit terminer
 - approche aggréssive    : Réaliser des chargements spéculatifs (vérif dynamique si une tâche moins spéculatifs écrit dans un zone chargé spéculativement.)

Le contrôle et les accès aux données peuvent être spéculative. -> Mécanisme de "Retour en arrière" et de commit
Gestion circulaire des tâches : La tâche en tête n'est jamais spéculative. On retire les tâches de manière circulaire.

Software
~~~~~~~~
 - Le séquenceur a besoin des informations sur le CFG.
 - Il faut caractériser une tâche par les données consommés et les données produites.
   |-> Analyse statique par la compilation et création d'un "create mask" indiquant quel registres sont produits par la tâche.
   |-> Noté quel est la dernière instructions produisant le registre pour pouvoir ensuite le forwarder.

Hardware
~~~~~~~~
Hardware -> lancement des tâches vers une unités d'execution
         -> Maintient d'une execution séquentielle apparente

Le séquenceur détermine l'ordre des tâches. (Charge le descripteur de tâche et à partir de la va charger la tâche, creer les différent masqie et déterminer (ou prédit) la prochaine tâche à executer)

Les accès à la mémoire donnée sont réalisées par le Address résolution buffer (ARB) qui gére la spéculation, dépendance ...

Distribution des cycles pour l'execution
----------------------------------------
Relacement d'un calcul si :
 - utilisation d'une valeur incorrect
 - prediction incorrect

Pour cela :
 a) Synchronisation des communications de données

 b) Détermination de la prediction :
  - Registre pas de problèmes
  - Accès mémoires : synchronisé explicitement
Pour les prédictions -> Valider la prédiction au plus tôt : 
  * intruction explicite de validation de prediction
  * changer la structure de la bcl afin de tester la condition au + tôt


Cycle idle          : aucune unité de calculs n'a de tâches à executer
Cycle de non calcul : les unités ont des tâches mais ne peux pas les executer
 - Dépendances intra-tâche : dépendance entre instructions d'une même tâche (désordonnancement, cache non bloquant etc ...)
 - Dépendances inter-tâche : dépendance entre tâches (calculs de la condition de la boucle à la fin du corps de bcl etc ...)

Conclusion
----------
Exploite l'ILP. Pour cela utilisation d'une combinaison hardware/software afin d'extraire l'ILP
 -> division le CFG en tâche 
 -> traverser le CFG de manière spéculative
 -> Les tâches sont distribués à une collection d'unité d'execution.
 -> Chaque unité d'execution fetche et execute les instructions de la tâche associées
 -> Processeurs utilise plusieurs PCs  afin de pouvoir séquencer plusieurs parties différente du CFG.
@InBook{         1996_mudge,
  ALTauthor =    {trevor mudge},
  ALTeditor =    {},
  title =        {ACM Computing Surveys (CSUR)},
  chapter =      { Special ACM 50th-anniversary issue: strategic directions in computing research},
  publisher =    {ACM Press   New York, NY, USA },
  year =         {1996},
  OPTkey =       {},
  OPTvolume =    {},
  OPTnumber =    {},
  OPTseries =    {},
  OPTtype =      {},
  OPTaddress =   {},
  OPTedition =   {},
  OPTmonth =     {december},
  OPTpages =     {671 - 678},
  OPTnote =      {},
  OPTannote =    {}
}

01/12/2004

Architecture des ordinateurs est un degré significatif sur les activités de l'ingénieurs pour trouver une solution à un problem avec une contrainte de coûts.

Tendance -> a) resulte d'un apport de la technologie (ex. techno micronique et submicronique)
         -> b) resulte d'un contexte d'application (ex. Multi processings => ajout de mécanisme de tâches)
a) Défi : Consommation (Au premier ordre conso est proportionnel à la fréquence, loi de moore : Double la fréquence tous les Deux ans donc double la conso)
          Latence : La fréquence d'horloge croit plus vite que la technologie des Rams : f(CPU) +50\%/an , vitesse(DRAM) +10\%/an
b) application guide les architectures : Les processeurs deviennent de + en + grand public  (jeux 3D, multimédia etc..). Avant ils étaient surtout utilisé par des militaires. 

L'auteur voit 3 challenges pour la prochaine décade (càd jusqu'en 2006)
-> Puissance et taille
-> Performance
-> Complexité

Axes de recherches
-> locality
-> Paralélisme
-> Prédictabilité

Paralélisme au niveau instructions (ILP) -> Approche VLIW et superscalaire
            au niveau application  -> Simultaneous multithreadings (SMT)

l'idée de ce SMT viens du processeur HEP devellopper par denelcor vers la fin des années 70

Hierarchie mémoire => nécessité de masquer la latence des accès mémoires (technique de prefetching => utilisation de la bande passante innoccupé en vue d'aller chercher des instructions potentiellement utiles)

Evolution des benchmarks pour prendre en compte des évolutions de marché pour le processeurs (c'est à dire bench "multimédia")
@InProceedings{,
  author =       { Kunle Olukotun  and
                   Basem A. Nayfeh and
                   Lance Hammond   and
                   Ken Wilson      and
                   Kunyung Chang        
                 },
  title =        {the case for a single-chip multiprocessor},
  OPTcrossref =  {ISBN:0-89791-767-7},
  OPTkey =       {},
  OPTbooktitle = {Proceedings of the seventh international conference on Architectural support for programming languages and operating systems},
  OPTpages =     {2-11},
  OPTyear =      {1996},
  OPTeditor =    {},
  OPTvolume =    {},
  OPTnumber =    {},
  OPTseries =    {},
  OPTaddress =   {Cambridge, Massachusetts, United States},
  OPTmonth =     {},
  OPTorganization = {},
  OPTpublisher = {ACM Press},
  OPTnote =      {},
  OPTannote =    {}
}

24/01/2005

Opposition entre un mono-processeur compléxe et des multi-processeurs simple.

Comparaison entre un processeur super scalaire 6 voies à ordonnancement dynamique et 4 processeurs superscalaire 2 voies. 
Un superscalaire est décomposé en 3 phases :

                     |----| <-> E
           |----| -> |    | <-> E
ICache <-> | IF | -> | IR | <-> E
           |----| -> |    | <-> E
                     |----| <-> E

- Instructions fetch => fournir le maximum d'instruction prête.
  Limitation : 
   * Branchement mal prédit (degré de spéculation)
   * Instruction mal aligné
   * Miss de caches
- Issue and retirement 
  Rennommage : 
   * Table de mappage (nb_opérande * nb_voie_scalaire   ports de lecture)
   * Reorder buffer   (nb_bit_codage_registre * Taille_file_instruction_issue * nb_opérande * nb_voie_scalaire
- Execution
  Augmentation du temps de cycle lors de l'écriture si beaucoup de voie scalaire
  Compléxité du by-pass (augmentation quadratique en fonction du nombre d'unité d'execution)

Single-Chip Multiprocessor
--------------------------
1) -> Les OS actuelles sont multi processus => fort parrallélisme
2) -> Les processus sont également multi thread
3) -> Les appli mono thread peuvent être découper en thread de manière hard. assez contraignant.

Architecture pour comparaison
-----------------------------

* Super Scalaire => R10000 de degré 4 à 6. (Augmentation des caractéristiques pour arriver à 430 mm2)
* Multi proc     => 4 * R10000 de degré 2  (Diminution   des caractéristiques pour arriver à 430 mm2)

=> Même surface de silicium pour les deux architectures.

Performance
-----------
Gel d'un proceeseur dut au miss de cache. 
Superscalaire -> execution désordonné, spéculative, cache non bloquant. Masquage des couts de Miss.

Mesure de performance : Gain par rapport à la version MP - 1 proc.
- Sur les applications avec peu de parallélismes, le superscalaire est plus performant car exploite mieux l'ILP.
- Sur les applications avec un grain fin de parallélisme et beaucoup de communication, l'approche SS et MP est équivalente (Les deux approches exploite le parrallélisme grain fin)
- Sur les applications avec un large degré de parallélisme, le multi proc prend l'avantage. Car le parrallélisme dépasse la fenêtre du supersclaire.


=> l'approche SS est limité par l'ILP du programme, et le matériel nécessaire (lancement dynamique et banc de registres) augmente de manière quadratique le matériel et donc le temps de cycle.

@article{1996_tullsen,
  title={{Exploiting choice: instruction fetch and issue on an implementable simultaneous multithreading processor}},
  author={Tullsen, D.M. and Eggers, S.J. and Emer, J.S. and Levy, H.M. and Lo, J.L. and Stamm, R.L.},
  journal={Proceedings of the 23rd annual international symposium on Computer architecture},
  pages={191--202},
  year={1996},
  publisher={ACM Press New York, NY, USA}
}

16/03/2005

Préentation d'un architecture SMT suivant 3 contraintes :
 - Minimiser l'impact par rapport à une architecture Superscalaire
 - Minimiser la perte de performance lors de l'execution de programme monothread
 - Avoir un gain de performance lors de l'execution de programme multithread

Architecture SMT
----------------
L'article dérive un Supersclaire classique 
(Fetch unit, Decode, Register renaming, wait\_queue, lecture des registres, unités d'executions, commit).
Les instructions sont lancées dans le désordre, retiré dans l'ordre

Changement minimum à apporter :
 - un pc/thread et un thread séquenceur
 - une pile de retour séparé (pour la prédiction de retours)
 - Par thread : mécanisme pour retirer les instructions, file d'instructions à retirer et mécanisme de trape
 - un thread id pour le BTB
 - un large banc de registres

Note : les instructions présente dans la file d'executions sont partagé par plusieurs threads donc grâce au mécanisme de renommage, on ne sélectionne que les instructions indépendante

Conséquence :

* Un pc est prioritaire (choisit de manière round robin)
* Taille du banc de registres conséquents impose l'augmentation de la profondeur du pipeline.

Performance
~~~~~~~~~~~
L'architecture gère 8 threads.

Remarque : Si un seul thread est utilisé, il y a une perte de 2\% sur l'IPC par rapport au superscalaire de référence dut à l'augmentation du pipeline.

Goulot d'étranglement :
- Taille des files d'instructions : à cause de l'augmentation de l'IPC, elle deviennent souvent pleines
- l'étage ifetch n'a pas la connaissance que les files sont pleines donc continue à fétché des instructions.
- manque de parrallélisme : à cause des fausses instructions.

Fetch Unit
----------
Il y à un partage de la bande passante de fetch avec tous les threads.
 -> le fetch unit peut choisir parmit plusieurs source, donc incrémenter l'utilisation de la bande passante (car si un thread est bloqué, les autres ne le sont pas forcément)
 -> le fetch unit peut choisir pour quels threads travailler (si un thread n'est pas bloqué mais qu'il réalise beaucoup de miss de spéculation, alors il est peut profitable de lui chargé des instructions qui auront de fortes chances d'être fausse)

Définition de plusieurs stratégie de fetchs, classement suivant 3 critères :

 1) Partionnement du l'unité d'ifetch parmis les threads
 2) Efficacité de l'unité de fetch (Qualité des instructions chargés)
 3) Disponiblitité de l'unité de fetch (Elimination des conditions de blockage de l'unité)

1) Partitionnement
~~~~~~~~~~~~~~~~~~
L'unité fetch charge jusqu'a 8 instructions par cycle.
Mais comme les blocs de bases sont plutôt petit, il est difficille d'exploiter complétement la bande passante utilement pour un thread.
 -> Partage des 8 instructions parmit plusieurs threads. Le cache reste identique mais est découpé en plusieurs banc, deux threads peuvent intérrogé deux bancs différents

1.8 (1 threads ayant 8 instructions) -> blocs trop petits 
2.4 - 4.2                            -> idéal
8.1                                  -> Il n'y a pas assez de threads non bloqué

Ajout de matériel : Mutipléxeur d'adresse, plusieurs buses d'adresse; logique de sélection des tristates de sorties, logique de conflit de bancs, duplication de la logique de calcul des hit/miss
=> Augmente la latence du cache mais réduit la latence du bloc decode et rename (car moins de dépendance à calculer)

autre vision : 
2.8 -> le premier thread est prioritaire et peut charger jusqu'a 8 instructions, s'il n'y arrive pas un autre thread oeut tenter de combler le manque.
c'est la méthode la plus performante car elle permet de gère la bande passante parmit plusieurs threads et d'avoir un partitionnement flexible.

2) Algorithme
~~~~~~~~~~~~~
Algorithme de décision sur le thread prioritaire : Déterminer le meilleur "thread"
 a) probabilité de ne pas charger un faux chemin
 b) temps prit par l'instructions pour être executable

* Round-robin
* BRCOUNT     -> Favorise le thread qui à le moins de branchement non résolue (améliore a)
* MISSCOUNT   -> Favorise le thread qui à le moins de miss de donnée (améliore b)
* ICOUNT      -> Favorise le thread qui à le moins d'instructions dans les étages D R IQ (IQ = Instruction queue) (améliore b)
* IQPOSN      -> Donne la plus basse priorité au thread la plus proche de la tête des files d'attente (améliore b) (la plus vieille instruction) (Ne requiert pas de compteur)

ICOUNT et IQPOSN sont les deux algos les plus performants.

3) Disponibilité
~~~~~~~~~~~~~~~~
Condition de blocage du fetch unit : IQ full, Icache miss.

* BIGQ -> Augmentation de la taille du IQ sans augmenter la taille de la zone de recherche
* ITAG -> Scrute le cache un cycle plutôt est on sélectionne que les threads qui ne vont pas faire de miss

Choix de l'instruction à lancé
------------------------------

Superscalaire : le degré de spéculation est croissant avec sa position dans l'IQ
Dans un SMT, ceci n'est pas vrai. 

* OLDEST
* OPT\_LAST     -> Optimiste
* SPEC\_LAST    -> Spéculatif en dernier (les instructions sont spéculatifs sont prioritaires)
* BRANCH\_FIRST -> Branchement sont prioritaires (afin de connaître si un branchement est spéculatif)
 
Les performances n'influe pas énormément -> la bande passante du lancement n'influe pas sur les performances.

Goulot d'étranglement
---------------------
Bande passante du lancement      -> non
Taille de la file d'instructions -> non
Bande passante du fetch          -> oui : la fréquence des sauts et les problèmes d'alignements du pc ne permet pas d'utiliser entièrement la bande passante.
Prédiction de branchement        -> non : Le SMT est plus tolérant au mauvaise prédiction qu'un superscalaire classique. plus il y a de threads, plus ils seront entrelacés donc moins d'instructions seront chargé après un branchement.
Execution spéculative            -> non, mais un SMT bénéficie beaucoup moins de l'apport de l'execution spéculative.
Sortance de la mémoire           -> non
Taille du banc de registres      -> oui : Temps d'accès devient limitant





@InProceedings{1996_wallace,
  author =       {Wallace, S.     and
                  Bagherzadeh, N.    },
  title =        {A scalable register file architecture for dynamically scheduled processors},
  OPTcrossref =  {},
  OPTkey =       {},
  OPTbooktitle = {Parallel Architectures and Compilation Techniques, 1996., Proceedings of the 1996 Conference on},
  OPTpages =     {179-184},
  OPTyear =      {1996},
  OPTeditor =    {},
  OPTvolume =    {},
  OPTnumber =    {},
  OPTseries =    {},
  OPTaddress =   {Boston, MA, USA},
  OPTmonth =     {Oct},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote =      {},
  OPTannote =    {}
}

01/04/2005

Abstract
--------

A major obstacle in designing dynamically scheduled processors is the size and port requirement of the register file. By using a multiple banked register file and performing dynamic result renaming, a scalable register file architecture can be implemented without performance degradation. In addition, a new hybrid register renaming technique to efficiently map the logical to physical registers and reduce the branch misprediction penalty is introduced. The performance was simulated using the SPEC95 benchmark suite

@article{1996_yeager,
  title={{The Mips R10000 superscalar microprocessor}},
  author={Yeager, KC},
  journal={Micro, IEEE},
  volume={16},
  number={2},
  pages={28--41},
  year={1996}
}
@article{burger1997sts,
  title={{The SimpleScalar tool set, version 2.0}},
  author={Burger, D. and Austin, T.M.},
  journal={ACM SIGARCH Computer Architecture News},
  volume={25},
  number={3},
  pages={13--25},
  year={1997},
  publisher={ACM Press New York, NY, USA}
}
@InProceedings{1997_palacharla,
  author =       {Palacharla, S.  and
                  Jouppi, N.P.    and
                  Smith, J.E.   },
  title =        {Complexity-Effective Superscalar Processors},
  OPTcrossref =  {},
  OPTkey =       {},
  OPTbooktitle = {Computer Architecture, 1997. Conference Proceedings. The 24th Annual International Symposium on},
  OPTpages =     {206 - 218},
  OPTyear =      {1997},
  OPTeditor =    {},
  OPTvolume =    {},
  OPTnumber =    {},
  OPTseries =    {},
  OPTaddress =   {},
  OPTmonth =     {Jun},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote =      {},
  OPTannote =    {}
}

07/02/2005

=> Perte de performances du au matériel très couteux.

2 directives pour fabriquer un mono processeurs :
 - Le compléxifier le matériel afin d'extraire encore plus le nombre d'instructions lancée
 - Le rendre plus simple afin d'avoir une plus grande fréquence d'horloge

Source de compléxité
--------------------

Modèle de pipeline typique :

1) FETCH             Lecture de plusieurs instructions, prediction de branchement
2) DECODE            Décodage d'instruction
3) RENAME            renommage de registre, dispatchement dans la fenêtre d'isntructions
4) SELECT/ISSUE      Une fois qu'une instruction à ces opérandes => prête à être lancé -> Envoie vers l'UF approprié
5) REG READ          Prise des opérandes / bypass
6) EXECUTE/BY PASS   Execution
7) DCACHE ACCESS     Accès mémoire
8) REG WRITE/COMMIT  Accès dans les registres et valdiation (instruction non spéculatif et non érroné)

Dépendance de complexité :
- Largeur/profondeur de la fenêtre de lancement
- Structure "Dispatch et issue"
- Longeur des fils dans ces structures qui se mettent à jour par broadcasting

-> Logique de renommage
-> Logique de wake up (détermine quel instructions est prête ou non)
-> Logique de selection
-> Logique des by-pass

Détails
-------

Logique de renommage
~~~~~~~~~~~~~~~~~~~~
Accès à une table de mappage pour diriger le numéro de registres logique vers le numéro de registres physique
Accès multiple (plusieurs instructions)
-> Logique de vérification de dépendances

2 schémas : - schéma RAM : Une table de NB\_REG\_LOG pointant sur les registres physiques
            - schéma CAM : Une table de NB\_REG\_PHY pointant vers les registres logiques
Trename   = Tdecode + Twordline + Tbitline + Tsenseamp
          = cst0 + cst1*IW + cst2*IW²

Twordline (proportionnel à la taille de l'adresse du registre physique (environ 8) )
Tbitline  (proportionnel au # de registre logique (souvent 32) )
Tsenseamp fonction de bitline delay
cst sont donnée par la technologie

=> croit linéairement avec la taille de la fenêtre

Logique de wakeup
~~~~~~~~~~~~~~~~~
A chaque résultat produit, a tag associé au résultat est diffusé à toutes les instructions contenus dans la fenête de lancement (IW).
Chaque instructions compare le tag avec ses opérandes sources
Si la comparaison est positive => mise à jour du bit ready de(s) l'opérande(s) (Quand tous les bit sont positionnés => instructions prête au lancement)

Il y a IW tag soit NB\_OPERANDE x IW comparaions

Twakeup = Ttagdrive + Ttagmatch + Tmatch\_or
        = c0 + (c1 + c2 * IW)*WINSIZE + (c3 + c4*IW + c5*IW²)*WINSIZE²        

(IW => nombre d'instruction en attente d'être executer)
(WINSIZE => nombre d'instruction allant être executé)

Incrémenter le nombre de ligne va incrémenter le nombre de comparaisone et la puissance nécessaire pour atteindre ces comparaisons.
Seul le Ttagdrive dépend de la taille de fenêtre de lancement (fan-out + élevé car + de comparateur)

Logique de selection
~~~~~~~~~~~~~~~~~~~~
Choix des instructions à executer parmit la IW
 -> Plusieurs types d'instructions
 -> Plusieurs types d'unités fonctionnelles pouvant acceptés une instructions de plusieurs types d'instructions.

Un signal REQ par instruction contenant dans la IW (actif si instruction prête)
Un signal GRANT est émit par le bloc de sélection (1 par signal de requête) => indique que l'instructions est lancé dans une unité fonctionnelle.
Politique de selection -> en général FIFO, ou la plus vieille (C'est à dire la plus en bas de la fenêtre d'instruction)

=> Arbre d'arbitrage.
 2 phases : 1) Propagation de la requête jusqu'à la l'unité fonctionnelle
            2) Propagation de la réponse (GRANT) jusqu'a toute les req d'instructions

Tselection = c0 + c1 * log4(WINSIZE)

log4 car les noeuds de l'arbre d'arbitre accepte 4 requêtes.

Logique des bypass
~~~~~~~~~~~~~~~~~~
Si complétement bypassé, il faut : 2*IW²*S (S est le nombre d'étage)
-> Un fils par unité fonctionnelle
-> Tous les unité fonctionnelle (ainsi que le banc de registres) doivent avoir un bloc mux
-> banc de registres à autant 2*UF ports de lecture et UF ports d'écriture
-> Bloc mux à UF ports d'entrée et en sorties ce sont des bus attaqués pas UF signaux.
-> Sans oublier les compateurs dans chaque alu

Tbypass = 0.5*R*C*L²   => Dépend principalement de la longueur des fils.

Analyse des résultats
---------------------

IW  Window-size Trename Tselection Tbypass

(0.18)
4   32          351.0   578.0      184.9
8   64          427.9   724.0      1056.4

-> La selection (logique de fenêtrage) et les bypass posent des problèmes de scalabilités.
=> Toutes les autres structures ne posent pas de pbl d'horloge, où s'il y en a, alors ils peuvent être pipeliné.

Si on découpe l'étage Wakeup (Chercher les opérances) et selection (Chercher une ALU disponible), alors il y aura au meilleur des cas au moins un cycle de gels entre deux instructions dépendante consécutive.

... | WUP | SEL | EXE | ...                add r3,r2,r1
                   | (Bypass)
......... | WUP | WUP | SEL | EXE | ...    add r5,r4,r3

Proposition d'architecture
--------------------------
Remplacement de la fenêtre de lancement par une architecture "dependance-based"
Clusterisation des by-pass.

=> architecture "dependance-based"
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Exploitation des dépendances instraséques entre instructions.
Fenêtre de lancement découpé en plusieurs fifos. Les instructions dépendantes sont routés vers la même fifos.
Execution In-order des instructions dépendante entre elles. Execution désordonné des autres flots d'instructions.
Il n'y que les instructions de têtes à aller verifier le banc de registres.

Besoin d'une table(SRC\_FIFO)  où les dépendances des instructions sont maintenus à jour
SRC\_FIFO(num reg log) -> numéro fifo

=> Clusterisation des by-pass
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Décomposé les unités fonctionnelles en cluster. 
Il y a 2 types de bypass 
 - intra cluster (dans le même cycle) 
 - inter cluster (peut nécessité plusieurs cycles)
=> N copies du banc de registres : 1 pour chaque cluster

Conclusion
----------
Les techniques diminues faiblement (au max 12\%) le CPI mais augmente sensiblement la fréquence d'horloge. Au total, la performance global est meilleur.

Autre technique :

1 cluster - 1 window (Superscalar basique)

-> Window -> Cluster0


2 cluster - Fifo dispatch

     -> Cluster0
   /
-> 
   \ 
     -> Cluster1

2 cluster - windows - Choix du cluster : exec

Instruction stocké dans une fenêtre global puis assigne à un cluster

             -> Cluster0
           /
-> Windows 
           \ 
             -> Cluster1

2 cluster - windows - Choix du cluster : dispacth


     -> Windows -> Cluster0
   /
-> 
   \ 
     -> Windows -> Cluster1

2 cluster - windows - Choix du cluster : random

Choix des clusters aléatoire
     -> Windows -> Cluster0
   /
-> 
   \ 
     -> Windows -> Cluster1

@article{chrysos1998mdp,
  title={{Memory dependence prediction using store sets}},
  author={Chrysos, G.Z. and Emer, J.S.},
  journal={ACM SIGARCH Computer Architecture News},
  volume={26},
  number={3},
  pages={142--153},
  year={1998}
}
@InProceedings{1998_krishnan,
  author =       {Krishnan, V.   and
                  Torrellas, J.  },
  title =        {A clustered approach to multithreaded processors},
  OPTcrossref =  {},
  OPTkey =       {},
  OPTbooktitle = {Parallel Processing Symposium, 1998. 1998 IPPS/SPDP. Proceedings of the First Merged International...and Symposium on Parallel and Distributed Processing 1998},
  OPTpages =     {627-634},
  OPTyear =      {1998},
  OPTeditor =    {},
  OPTvolume =    {},
  OPTnumber =    {},
  OPTseries =    {},
  OPTaddress =   {Orlando, FL  ,   USA},
  OPTmonth =     {30 Mar - 3 Apr},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote =      {},
  OPTannote =    {}
}

25/02/2005

SMT                    -> Flexible (TLP et ILP) 
Fixed assignement (FA) -> Sous utilisation des ressources

CMT -> un thread à tous les ressources à un instant donné
Pbl SMT -> Conséquence sur le temps de cycle !!!

SMT clusterisé : Unité de calculs sont multisthreadé, l'unité de dispatch va envoyé les instructions d'un thread vers les unités de calculs qui lui sont associés.

Model de parallélisme
---------------------

Architecture fixe : N threads ayant M unités d'execution. Une unité d'execution n'apaprtient qu'a un thread => jusqu'a M IPC
Si X nb d'Unité d'execution total fixe -> M = X/M 
  - Si N trop grand -> exploite peu l'ILP
  - Si N trop petit -> exploite peu le TLP

Architectures
-------------

Centralisé et clusterisé SMT:

Fetch unit partagé par ts les threads, (géré round robin ou autre), les instructions sont ensuite placé dans une fênetre d'instructions commune. Les instructions sont commité par thread.
 -> limite : large interconnections entre les unités fonctionnelles et le banc de registres (en particulier les by-pass)

FA :

Réduction de la centralisation des ressources : partionnement du SMT classique en clusters (SMT d'ordre X*Y devient X clusters étant des SMT d'ordre Y).
Chaque cluster à sont unités de FETCH

Evaluation
----------
Un gaspillage d'un slot d'instructions peut être classé en :
- struc : Manque d'unités fonctionnelle
- mem   : Accès mémoire
- data  : Dépendance de donnnées
- ctrl  : Miss predictions de branchements
- sync  : Barrières de synchro
- fetch : Pas d'instructons pour un thread dans la fenêtre
- autre

Comparaison d'un FA8  (8 clusters qui sont des superscalaire d'ordre 1)
                 FA4  (4 clusters qui sont des superscalaire d'ordre 2)
                 FA2  (2 clusters qui sont des superscalaire d'ordre 4)
                 FA1  (1 clusters qui sont des superscalaire d'ordre 8)
                 SMT8 (8 clusters qui sont des SMT supportant 1 threads lancant 1 inst/cycles) 
                 SMT4 (4 clusters qui sont des SMT supportant 2 threads lancant 2 inst/cycles) 
                 SMT2 (2 clusters qui sont des SMT supportant 4 threads lancant 4 inst/cycles) 
                 SMT1 (1 clusters qui sont des SMT supportant 8 threads lancant 8 inst/cycles) 
En terme de complexité SMTx = FAx
SMT8 est identique à FA8
SMT1 est une architectures SMT centralisés

de FA8 à FA1 : sync décroit mais les data et mem croit. (logique :P)

@article{1998_tullsen,
  title={{Simultaneous multithreading: maximizing on-chip parallelism}},
  author={Tullsen, D.M. and Eggers, S.J. and Levy, H.M.},
  journal={International Conference on Computer Architecture},
  pages={533--544},
  year={1998},
  publisher={ACM Press New York, NY, USA}
}

15/02/2005

Présentation du multi-threading.
-> lancement de plusieurs flots de plusieurs threads dans les unités fonctionnelles du processeurs.
-> but : augmenter l'utilisation du processeur face au long latence de la mémoire et de ILP limité dans un seul thread

plan :
 - modèle de SMT
 - evaluation des perfs (par rapport à un superscalaire et un fine grain multi threading)
 - hierarchie mémoire dans un SMT
 - SMT vs CMP

Modification d'un alpha 21164 :

- 10 unités d'execution (4 integer, 2 flottant, 3 load/store et 1 branchement) => complétement pipeliné
- Issue : 8 inst/cy
- execution dynamique
  |-> gestion des dépendance in-order
  |-> lancement out-order
- Prediction de bcht

Limitations du super-scalaire
-----------------------------
en moyenne, le processeur lance 1.5 inst/cy sur une machine pouvant en lancer 8.
différente cause :
 - conflits mémoire, dépendance de donnée (flottant, ou entiere), délai de chargement, bulle de contrôle, mauvaise prédiction, miss de cache et de TLB.

Toutes les cas peuvent être classé suivant deux types d'incidences sur le pipeline
 - gaspillage verticale   : à un cycle donnée, aucune unité d'exécution ne sera utilisé
 - gaspillage horizontale : à un cycle donnée, non utilisation d'un créneau de lancement (issue slot)

un corse grain / Fine grain multithreading limite le gaspillage verticale.

Modèles de processeurs
----------------------
Chaque modèles à 10 unités fonctionnelles et peut lancer 8 inst/cycles (Donc au max 8 threads)

- Fine-grain multithreading : 1 thread peut lancer des instructions pendant 1 cycle (cycle suivant commutation)
- SMT : full issue : les 8 threads sont en compétitions sur chaque issue slots à chaque cycle
- SMT : N issue : chaque threads peut lancer un maximum de N inst/cycle (full issue = 8)
- SMT : Connection limité : Chaque thread hardware est directement connecter à une unité fonctionnelle de chaque type (si il y a 8 threads et 4 unités fonctionnelles d'un type, alors chaque unité fonctionnelle est connecté à 2 threads)

3 facteurs :
 1- # de threads en compétition
 2- # d'instructions lancé/thread
 3- # d'UF visible/thread

augmente   Port registre | dépendance interinst | logique forward | ordonnancement inst
1                                                 + complexe        + complexe          -> les ufs ont plus destination possible pour les résultats
                                                                                        -> plus d'instructions devant être routé
2          + complexe      + complexe                                                   -> plus d'instruction à lancer (donc chercher les opérandes)
                                                                                        -> plus d'instruction à analyser (augmentation de la fenêtre de chaque thread)
3          + complexe      + complexe             + complexe        + complexe          -> l'ordonnancement devient de + en + dépendant d'autre FU
                                                                                        -> une UF qui est privé à moins de destination possible

Caches
------
Le partage des caches et des TLB est néfastes sur les performances.
Lors du partage des caches entre threads :
 - Il y a virtuellement moins d'espace par threads
 - Il faut des caches non bloquants

-> Cache privé afin d'avoir des caches dédié à un thread (le cache est partionné en NB\_THREAD parties) Bon pour les Icaches (Pas d'évincement d'une ligne d'instruction par un autre thread)
-> Cache partagé : Tous les threads ont accès au même cache => peu de contrôle, bon pour les Dcaches car 1 seules mécanisme de cohérence mémoires à implémenter.

SMT vs CMP
----------
Ressemblance :
Duplication des registres, multiple unité fonctionnelle, grand nombre d'instruction lancé par cycle
Différence :
les ressources ne sont pas partitionné et ordonnancé. Ils ont alloué de manière statique à un thread (ou un groupe de threads)

Le SMT surpasse le CMP à complexité égal :
 -> Un SMT 8 threads - 8 issues avec 10 FU surpasse de 24\% 8 proc 1 issue avec 4 UFs

 * performance avec peu de thread (car partage des ufs)
 * granularité et flexibilité

@InProceedings{ 1998_hammond,
  author =       {Lance Hammond and
                  Mark Willey   and
                  Kunle Olukotun},
  title =        {},
  OPTcrossref =  {SSN:0163-5980},
  OPTkey =       {},
  OPTbooktitle = {Proceedings of the eighth international conference on Architectural support for programming languages and operating systems},
  OPTpages =     {58-69},
  OPTyear =      {1998},
  OPTeditor =    {},
  OPTvolume =    {},
  OPTnumber =    {},
  OPTseries =    {},
  OPTaddress =   { San Jose, California, United States},
  OPTmonth =     {},
  OPTorganization = {},
  OPTpublisher = {ACM Press},
  OPTnote =      {},
  OPTannote =    {}
}

27/01/2005

Thread level speculation
------------------------
Technique autorisant l'execution paralléle d'une application séquentiel (donc à pour but de tourner sur un multi processeur).
=> Mécanisme fonctionnant bien pour des applications avec un grain moyen de parallélisme de boucle. Mais quand la granularité de parallélisme devient trop petite, l'overhead devient trop couteux.

DATA Spéculatation
~~~~~~~~~~~~~~~~~~

Processeur superscalaire avec execution désordonné :
 -> réordonne les instructions ALU (renommage de registre , ordonnancement dynamique).
Pas de réordonnancement des accès mémoires si les adresses ne sont pas connut on sont connus et dépendante.

Data spéculation : On execute des loads qui ce situe après des stores dont l'adresse n'est pas encore connus.
 -> S'il y a une vrai dépendance => le store est prioritaire et le load (et chaque execution en dépendant) sont ré-executés.

Le programmeurs / Compilateur peut diviser un programme séquentiel en plusieurs threads. Or les dépendances de registres et de mémoires imposent beaucoup de contraintes.
=>Si les dépendance ne peut pas être connus lors de la compilation (exemple des pointeurs en C) alors impossibilité  de diviser le code ou alors placer des routine de synchronisation logicielle.

Avec le thread level data speculation (TLDS)
=> le compilo divise seulement le programme en threads. 
=> Chaque thread à un numéro, celui-ci indique le numéro correspondant à l'ordre dans lequel il devrait être s'il été executer en séquence.
=> La spéculation hardware d'occupe des vrais dépendances entre les accès mémoires

Les écritures deviennent des points de synchronisations.

Chaque processeur execute un thread :
On classe les procs par rapport au numéro que le thread possède.
Celui avec le numéro le plus faible (executer sur le processeur de tête) est donc non spéculatif. Les autres sont de + en + spéculatif.

Temps 0 : CPU i   -> R
Temps 1 : CPU i+1 -> R
Action  : -

Temps 0 : CPU i   -> R
Temps 1 : CPU i+1 -> W
Action  : renomage dans i+1

Temps 0 : CPU i   -> W
Temps 1 : CPU i+1 -> R
Action  : envoie de la donnée écrite par i vers i+1

Temps 0 : CPU i   -> W
Temps 1 : CPU i+1 -> W
Action  : Ecriture de i puis renommage de i+1 et écrasage de la donnée

Temps 0 : CPU i+1 -> R
Temps 1 : CPU i   -> R
Action  : -

Temps 0 : CPU i+1 -> R
Temps 1 : CPU i   -> W
Action  : Renommage de i+1

Temps 0 : CPU i+1 -> W
Temps 1 : CPU i   -> R
Action  : RAW : i+1 redemarré

Temps 0 : CPU i+1 -> W
Temps 1 : CPU i   -> W
Action  : Renommage de i+1, + tard le forward de i sera ignoré

Le matériel de spéculation des donnés doit fournir :
 - Détection des vrai dépendances mémoire dans l'ordre.
 - Possibilité de retour en arrière et ré-execution du threads
 - Bufferisation des écritures jusqu'a ce qu'elle ne sont plus spéculative (Ou supprimé)

Décomposition en thread spéculatif
----------------------------------

2 architectures différentes :
 - The Multiscalar architecture => découpage en tâche arbitraire, allocation des tâche dans l'ordre sur un anneau de processeur
 - The TLDS architecture => support minimum pour la spéculation, principalement controlé par logiciel.

Solution apportée ici :
Combinaison de l'approche hard/Soft (~TLDS)
-> Utilisation du support du hardware pour diviser le programme en thread et les distribuer sur les différents processeurs.
  |-> Coprocesseur de spéculation

Comment diviser un prcess en threads?
 -> utilisation d'appel de sous fonction
   -> Un autre processeur va executer de manière spéculatif la suite du programme principal
 -> Boucle (Ceux indiqué par le compilateur)
   -> Les différentes itérations sont distribuées sur les différents processeurs

Subroutine Thread
~~~~~~~~~~~~~~~~~

Spéculation de fonction géré par une list chainé de threads actifs ordonnée du moins au + spéculatif
Lors d'un appel de fonction, envoie d'un message au autre processeur.

1) Le processeur alloue un register passing buffer (RPB) pour le thread nouvellement crée. 
2) Sauvegarde des registres (devant être sauvegarder lors d'un appel systems) puis prédition de la valeur retourné 
  alogo repeat least return value (car en C -> beaucoup de void fonction ou de retour d'erreur, ou imprédictible)
3) Insertion du buffer dans la list des buffer actif juste après le process courent (pour garder l'ordre par spéculation)
4) Attribution d'un processeur à ce nouveau thread (soit un libre, soit un executant le plus spéculatif des threads)

Ceci est réaliser dans l'exception handler (Donc chaque appel à une sous fonction génére une exception)
Si l'appel de fonction à une valeur de type imprédictible, alors on ne considère pas la spéculation.

Au retour d'un appel de fonction :
1) Le processeur attend jusqu'a ce qu'il soit le processeur de tête (donc sont code devient non spéculatif et deplus il n'est pas en conflit avec les autres thread)
2) La valeur retourné est comparé avec la une valeur prédite. Si miss => Toute les threads sont relancés
3) Le RPB est remis dans la free-list, le thread suivant devient celui de tête
4) L'ancien processeur de tête va executer un thread (donc devient le plus spéculatif)

Loop itération Thread
~~~~~~~~~~~~~~~~~~~~~

Un boucle spéculatice est préceder d'une verification pour savoir s'il est avantageux ou non de l'exécuter de manière spéculative.
Une itération de boucle est donnée a chaque proc disponible.

A la fin d'une itération -> validation, l'itération suivante devient le CPU de tête.
Ceci jusqu'à ce que la condition de terminaison soit trouvée (dans ce cas invalidation de tous les autres threads) 

2 manières de traiter les boucles :
 - Si la boucle est longue : rebouclage des RPB
 - sinon Schéma habituel : insertion de 4 RPB (1 pour chaque proc) => Overhead moins couteux mais méthode peu fléxible

Taille des Threads
~~~~~~~~~~~~~~~~~~

Facteur de Limitations :
1) Taille limité des buffers : Il n'y a que le CPU de tête qui réalise des mise à jour de la mémoire. Les CPU spéculative ne peuvent commiter leur buffer que s'il deviennent buffers de têtes.
2) Vrai dépendance : Les grands threads augmente la probabilité de vrai dépendance
3) Longueur des redémarrages : Un redémmarrage sur un grand thread augmente la charge de travail (données à défaire etc..)
4) Overhead : Les très petits threads ont un coût d'overhead trop élevé.

=> Violation counters : élimine les threads avec trop de dépendances
=> Thread timers : élimine les threads trop long
=> Stall timers : élimine les threads trop souvent bloqués (voir plus bas)

Exception
~~~~~~~~~
Si un thread réalise une exception, ou un appel système, alors celui-ci est bloqué.

Speculation Control Coprocessor
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
=> Implémenter dans le Coprocesseur2 du mips
-> Fonction accèder par software
-> Contient la table des vecteurs d'exceptions

Hardware Support
----------------

Sur le multiscalar processor => ARB (Dcache partagé) associé avec un traceur de reférence mémoire spéculative.
Sur le TDLS processor        => Protocole plus simple

Ici : 
 - Modification dans le Dcache : Sur chaque tag d'une ligne de cache, ajout de qq bits (modified bit, pre-invalidate bit) (Read, Write bits => pour détecter les vrai dépendance, un bit par mots contenu dans la ligne)
 - Buffers dans le cache L2    : Bufferisation des écritures encore spéculative. Une fois qu'il ne sont plus spéculative, ordre venant du processeur pour rentre permannent les changement. Le buffer est dépiller par ordre d'arriver et écrit dans le L2. Le buffer full est détecter par chaque proc qui possède une copie local des Tags du buffer couramment utilisé.
Lors d'un load  spéculatif , On va lire le DCACHE, puis on va lire dans le buffer courrant au proc, puis on remonte tous les buffer appartement a des process moins spéculative (jusqu'a la tête) et enfin on va lire dans le L2 cache. (Tous est vérifier en parralléle)
Lors d'un sotre spéculatif , il peut se produire : écriture dans le DCACHE (demander par le proc courant), une invalidation par un cpu moins spéculatif (vrai dépendance), une pré invalidation venant des cpu plus spéculatif (vérification). Si proc devient la tête : Drainage du buffer.
@TechReport{1998_olukotun,
  author =       {Lance Hammond and
                  Kunle Olukotun},
  title =        {Considerations in the design of hydra : a multiprocessor-on-a-chip microarchitecture},
  institution =  {Stanford University},
  year =         {1998},
  OPTkey =       {CSL-TR-98-749},
  OPTtype =      {},
  OPTnumber =    {},
  OPTaddress =   {},
  OPTmonth =     {February},
  OPTnote =      {},
  OPTannote =    {}
}

24/01/2005

Décrit de manière détaillée :
- Hiérarchie mémoire
- Bus internes
- Contrôle et arbitrage

Hierarchie Mémoire
~~~~~~~~~~~~~~~~~~
L1 - On chip - I D séparé , et 1 couple pour chaque proc
L2 - On chip - Partagé avec les 4 processeurs
L3 - Off chip
Mémoire principale - Off chip

L1 unifié pour les 4 procs :
 - Trop de ports R/W
 - Cache L1 devient "plus gros" pour rendre les même services
 - Logique entre le cache et le L1 (en cas d'accès à la même case)
 - Trop de logique => Ne réponds pas en 1 cycle

L1 séparé
 - Obligation d'un mécanisme de snoop

Limitation d'avoir un L3 off chip :
 - RAM rapide sont onéreuse
 - Demande beaucoup de plots
 - Electriquement non triviale

Communication
~~~~~~~~~~~~~
2 bus internes :
 - Bus Read/Replace
 - Bus Write-through 

Gérer de manière pipeliné, demande 1 cycle pour l'arbitrage afin d'avoir un débit d'un accès par cycle

Bus Read/Replace  : 256b de large (1 ligne de cache L1 / L2). Liaison entre le L2, et le L3 ainsi que tous les L1 (en lecture uniquement). Bus avec un faible traffic (dans leur exemple : occupation inférieur à 50\% pour les tests les plus gourmand en accès mémoires)

Bus Write-through : 64b de large, de tous les caches L1 vers le L2. Cohérence du cache L1 sur snoop de ce bus (pas le read/replace bus) , Invalidation sur écriture (Un seul cache est propriétaire d'un bloc). Les écritures de tous les procs se retrouvent séquencer.

L'utilisation du write-bus n'est pas scalable :
 * write-bus multiple (Ou 1 seul rapide) => Ports supplémentaires pour le L1 Tags, snoop et invalidation multiple par cycle. Dans le L2 => plusieurs données peuvent être écrite par cycle.
 * Une ligne de bus avec un mode rafale
 * Protocole conventionnel de cohérence MESI, et elimination du write bus pour un bus partagé entre les lecture et les écritures

Contrôleur mémoire
~~~~~~~~~~~~~~~~~~
Chaque ctrl mémoire est divisé en 2 pipelines indépendants. 
 - un pour manager les accès en lecture (Instruction fetch et load)
 - l'autre pour manager les accès en écriture

Lecture  : en général prévisible et donc absorbé par le cache
Ecriture : A cause du write throught : répercuter à chaque fois sur le bus. De plus les codes ont tendance à faire des burst de store. En général absorbé par le store buffer.

pipeline de Lecture et celui d'ecriture sont similaire :
3 étages :
 - accès L2 (~5  cycles)
 - accès L3 (~15 cycles)
 - Initiation de l'accès à la mémoire principal ( 5-10 cycles)
L'avancement dans le pipeline se fait sur un miss de l'accès courant.

Degré de pipeline :
Accès L2, Accès L3 pipeliné
Accès mémoire non pipeliné (1 seul requêtes dans cet étage)

De plus il y a deux autres ctrl dans la mémoire principale et l'interface I/O
-> Retourne les données venant de l'extérieur vers le cache approprié.
-> ~ au ctrl des caches

Arbitre
~~~~~~~
Les demandes d'accès les plus anciennes sont servies en premier

Ce n'est pas une allocation cycle par cycle ou ressource par ressource. Mais par unité de cycle (de 5 à 20 cycles).

Chaque CPU pipeline (ctrl mémoire) envoie une requete de ressource au début de chaque étage de pipeline.
Priorité fixe :
 - vers Accès mémoire et I/O
 - vers L3
 - vers L2
(Les plus courants sont les moins prioritaire, évite la famine)

Read pipeline est prioritaire sur le write pipeline. Possibilité au L1 d'inverser la priorité si le write buffer est (proche d'être) plein.

Arbitrage sur la même adresse
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2 accès se réalise en parrallèle (L1 / L2 / L3 / Mémoire) sur le même adresses
Problèmes :
 - Copie multiple d'une ligne de cache => Plus de proporité d'exclusivité des lignes de caches.
 
@article{1998_kessler,
  title={{The Alpha 21264 microprocessor architecture}},
  author={Kessler, RE and McLellan, EJ and Webb, DA},
  journal={Computer Design: VLSI in Computers and Processors, 1998. ICCD'98. Proceedings., International Conference on},
  pages={90--95},
  year={1998}
}

@article{2000_barroso,
  title={{Piranha: a scalable architecture based on single-chip multiprocessing}},
  author={Barroso, L.A. and Gharachorloo, K. and McNamara, R. and Nowatzyk, A. and Qadeer, S. and Sano, B. and Smith, S. and Stets, R. and Verghese, B.},
  journal={Proceedings of the 27th annual international symposium on Computer architecture},
  pages={282--293},
  year={2000},
  publisher={ACM Press New York, NY, USA}
}

02/12/2004

systeme Piranha : Exploite le multiprocesseur à l'aide de 8 alpha (simple) avec 2 niveaux de caches, le tout sur un seul chip.

Les processeurs hautes performances vise l'exploitation au maximum de l'ILP. Réalisant des architectures de + en + complexe, afin d'améliorer les benchmarks de types SPEC.
Or Les domaines d'applications demandant vraiment de la haute performance se situe au niveau des serveurs. (Application internet) => Comportement n'est pas comme les bench SPEC

Pourquoi cette architecture : Le coût d'un SMT (simultaneous multithrading) étant plus cher qu'un CMP (chip multiprocessing), car plus complexe (le SMT contient du matériel pour gérer les changement de thread, + de banc mémoire etc ...). Alors que l'approche CMP peut être réaliser avec des processeurs plus simple.

Idée dans le piranha :
 -> Mémoire secondaire partagée (non inclusive avec un niveau L1)
 -> Cohérence des caches
 -> architecture I/O

Architecture générale :
-----------------------

 * CPU alpha possèdant un I et DCACHE dédié
 * Tous ces couple Proc+Cache sont relié autours d'un Interconnect
 * Sur cette interconnect, il y a également les caches L2 (donc partagés avec n'importe lequel des CPU)
 * Sur chacun des caches L2 est connecté un controleur mémoire.
 * Ce dernier à une liaison directer avec des RDRAM.
 * Connecté sur le Bus, pour la communication avec le monde extérieur
    - Home engine
    - Remote engine
 * Les 2 moteurs de protocoles sont connecté au routeur de paquet qui distribue les paquets entre les moteurs internes et file d'entrée et de sortie. 
 * Le bus étant piloté par un module : system control

Structure hiérarchique forte.

Réseau de noeud Piranha :
 - Les P-chip   => en interne possède 8 CPU alpha
 - Les I/O-chip => Permet de faire la liaison avec le monde extérieur (Au lieu des 8 CPU, il n'y en a qu'un + un bloc I/O)

D'après les concepteurs, un réseau peut aller jusqu'a 1024 noeuds avec un nombre quelconque de noeud I/O.
Un des principes fondamental, est qu'un noeud I/O est traité de la même manière qu'un noeud de traitements.

Architecture détaillée :
------------------------

CPU + L1 cache
~~~~~~~~~~~~~~
Processeur alpha de 500Mhz, 8 étages de pipeline classique (Ifetch, Decode, Execute (*5), Writeback).
 -> Unité flottante, BTB, logic de prédécodage.
2 caches séparé :
 -> 64 ko, ass 2voies. Cache bloquant avec adresse Virt et Tag phy. 
 -> TLB de 256, ass 4voies
 -> Protocole de cohérence MESI
 -> Non inclusif avec le niveau L2

Intra-Chips Switch (ICS)
~~~~~~~~~~~~~~~~~~~~~~~~
Conceptuellement, c'est un crossbar.
-> Uni-directionnel, interface Push-only
-> ECC , bits de parités
-> pré-allocation (spéculation)
-> 2 priorités (low & high), un chip peut choisir la priorité désiré.

Cache L2
~~~~~~~~
Cache unifié d'1Mo, découpé en 8 bancs qui sont ass 8voies (Remplacement round robin)
-> Maintient de la cohérence intra-chip
-> Non inclusif avec le niveau 1 de caches (Non dédoublement des instructions)
-> write no allocate
-> Duplication du registre de TAG du cache L1 associé au cache L2

L1 envoie une requete mémoire à son banc L2. Celui-ci peut :
 -> Servir directement la requête
 -> La renvoie à un autre Cache L1
 -> La renvoie à un autre protocle de cohérence
 -> Obtient la donnée à par le contrôleur mémoire

Contrôlleur Mémoire
~~~~~~~~~~~~~~~~~~~
Un Contrôlleur mémoire par cache L2.
A une liaison rapide avec les RAMs,
N'a pas de liaison direct avec l'ICS

Protocole Engine
~~~~~~~~~~~~~~~~
Assure le support pour la mémoire partagé, 2 blocs spérarés :
 -> "home engine"   responsable d'exporter la mémoire local a ce noeud
 -> "remote engine" importe la mémoire qui se trouve dans un noeud distant

Chaque bloc est a peu de chose près conçu de la même manière :
* Input controller
* microcode controlled execution unit
* Ouput controller

Une execution micoprogrammé assure la gestion entre les deux interfaces.

Cohérence des caches : Read, Read-exclusive, Exclusive, Exclusive-without-data

Interconnecte système
~~~~~~~~~~~~~~~~~~~~~
3 partie distinct :
-> Output Queue
-> Input  Queue
-> Routeur

Topologie indépendante, adaptatif, Buffer avec différents niveau de priorités, canaux virtuels

Mise en place de dispositifs pour assurer la fiabilité, disponibilité et l'utilité des données :
 - redondance sur les dispositifs mémorisants
 - procetection CRC sur les chemins de donn"s
 - protocle de recouvrement d'erreur
 - enregistrement d'erreur
 - Liens permuttable à chaud

METHODOLOGIE D'EVALUATION
-------------------------

Utilisation d'un bench simulant des accès de clients sur des bases de données.
 -> Oracle (logiciel)
 -> SimOS-Alpha (Os pour processeur alpha assez fournit (gère le multi processeur, la mémoire virtuel ...)

Comparaison de l'archi piranha avec :
 - Un alpha21364 : un superscalaire Out of order, à 1Ghz, 2 niveaux de caches etc...
 - un système piranha avec 8 procs (P8)
 - un système piranha avec 1 proc  (P1)
 - un proc superscalaire In order

Constatation :
 - le piranha 8 est relativement performant
 - Le traffic dans l'interconnect local est d'autant plus grand qu'il y a de processeurs, surtout a cause des mécanisme de cohérence de cache (Forwarding vers d'autre cache L2)

Remarque de fin :
Les auteurs finissent par cette perspective :
 => La question clé pour les designers des processeurs futures ne va pas être de savoir si on va employés des multi procs, mais de déterminer la bonne compensation entre le nombre de coeurs et la puissance de chaque coeurs. Et quel sera la meilleur hierarchie mémoire.
@article{cruz2000mbr,
  title={{Multiple-banked register file architectures}},
  author={Cruz, J.L. and Gonzalez, A. and Valero, M. and Topham, N.P.},
  journal={ACM SIGARCH Computer Architecture News},
  volume={28},
  number={2},
  pages={316--325},
  year={2000}
}
@article{2000_hammond,
  title={{The Stanford Hydra CMP}},
  author={Hammond, L. and Hubbert, B.A. and Siu, M. and Prabhu, M.K. and Chen, M. and Olukotun, K.},
  journal =      {Micro, IEEE},
  year =         {2000}
}

07/12/2004

MOTIVATION
----------

Les processeurs sont plus petits et rapide. Donc pour une même surface, nous avons une augmentation du "budget" de processeur.
 -> Soit on augmente la complexité d'un mono-processeur
 -> Soit on augment le nombre de mono-processeur simple sur un chip

Parrallélisme:
2 types de parrallélisme : ILP (Instruction level parrallelism) et TLP (Thread level parrallelism)
Souvent la logique utilisé pour augmenter l'ILP fait augmenter le cycle d'horloge de manière quadratique.
De plus il est limite à 4-6 instructions (cf 1991\_wall)

Contrainte technologique :
Délai causé par l'interconnection des portes (délai des nets) devient significatif => zone localement synchrone et globalement asynchrone. Un CMP peut faire en sorte de placer des processeurs simples dans les zones localement synchrones

Temps de design:
La conception d'un CMP s'appuie plus sur l'utilisation d'IP.

Pourquoi les CMP ne sont pas utilisé?
 -> Difficulté à convertir un programme pour mono-proc en multi-proc (Problème de consitence mémoire, synchronisation entre proc etc ...)
 -> Les compilateurs parralléles sont encore très assistés par le programmeur

DESIGN
------

Le chip Hydra est un chip multiprocessor (CMP) intégrant 4 processeurs MIPS possédant chacun un Icache et un Dcache L1, mais un niveau L2 partagé.
Tous les controleurs des Caches L1 et le cache L2 sont sur le même bus. (Appellé bus d'écriture)
Un autre bus prévut pour les échanges entre l'extérieur et le cache L2 mais avec possibilités de lecture des contrôleurs L1

Protocole d'invalidation simple sur le bus d'écriture

Il existe beaucoup d'application pour mono-processeur. Pour l'executer sur un système multi-proc, soit on sous utilise notre architecture, soit on ajoute de la thread-level speculation.
L'hydra va utiliser la deuxième technique.

thread-level speculation
~~~~~~~~~~~~~~~~~~~~~~~~
Prends une séquence d'instructions, la découpe de manière arbitraire en thread. Le hardware doit suivre ces threads. Si un thread réalise une lecture trop tôt (Donc un autre thread n'a pas encore fournit de résultat), le hard doit s'arranger pour que ce thread ce réexecute avec la bonne lecture.
Grande complexité car on doit déterminer toute les possibilités de "vrai dépendances"

Outre le cas normal, il y a 5 types de problèmes de cohérences :
- Cas normal : début de boucle load X , fin de boucle write X
- Renvoie de la donnée entre thread parralléle
- Détection si les lectures sont "proche" (Dépendance RAW) : Au moment de faire un write sur X à l'itération i, alors le distribuer au load de l'itération i+1 (Forward data entre deux thread paralléle). 
 => Mécanisme pour ce souvenir des traces d'execution (S'il y a eu précedement une lecture sur X dans l'itération i+1 lros de l'execution de l'instuction write sur X de l'itération i, alors il y a une erreur).
- Annulation saine de l'exec spéculatif après violation 
- Retirer les écritures spéculatives dans le bonne ordres (Dépendance WAW) (tjs l'itération la plus ancienne en premier) => Les écritures ne deviennent plus spéculative.
- Fournir le rennomage mémoire (Dépendance WAR)

Le système doit avoir un mécanisme pour décomposer en thread, et pouvoir les arreter les threads spéculatifs.

Où découper les threads : En pratique : que lorsque l'on peut avoir plusieurs voie, càd boucle et appel de fonctions (Si la fonction ne retourne pas de résultats ou le résultat est facilement prédictible)
Le speculation runtime system va choisir les 4 threads les moins spéculatifs et les executer (car il y a 4 procs).

Le mécanisme de spéculation demande des médiums de communication rapide inter processor, sinon le processus mono thread risque de couter moins cher que sont équivalents découpés en plusieurs threads (spéculatif).

Sur l'hydra, le matériel additionnel pour utiliser cette technique est placé dans 2 blocs matériels :
- Ram de flags pour les caches L1 (est ce que la donnée contenu dans la ligne à été spéculativement lut ou écrite?)
- Write buffers dans le cache L2 (Buffer d'écriture permettant de sauvegarder "sainement" les données dans le cache L2. (Garantie de donnée non spéculative)

Comment cela fonctionne?
~~~~~~~~~~~~~~~~~~~~~~~~
- Un buffer est alloué à chaque thread en train d'être éxecuté sur ce système. Dès qu'un thread ne devient plus spéculative, alors les buffers écrivent dans la mémoire.
- Pour contrôler le séquencement des threads, il y a un petit composant utilisant l'interface coprocesseur du mips.
  |-> "speculation coprocessors"

Classement de threads par degré de spécultation, quand un thread spéculatif d'ordre i envoie un message sur le writebus, seul les ctrls rattaché à des procs éxecutant un thread plus spéculatif (donc d'ordre > i) snoop le bus (rappel => utilisation de l'invalidation sur snoop)

=> Lors d'un accès mémoire => Lecture en L1, si miss (surement invalidé) alors regarde dans son write buffer  puis dans les write buffer des threads de - en - spéculatif, et enfin dans le cache L2.

COUT ET PERFORMANCE
-------------------
Cout        : augmente la surface de quelques pourcents.
Performance : Programme difficille ou impossible à parralléser, cependant ce sont des applications hautements parralléles.
@article{2000_sharangpani,
  title={{Itanium processor microarchitecture}},
  author={Sharangpani, H. and Arora, H.},
  journal={Micro, IEEE},
  volume={20},
  number={5},
  pages={24--43},
  year={2000}
}
@article{2001_burns,
  title={{Area and system clock effects on SMT/CMP processors}},
  author={Burns, J. and Gaudiot, J.L.},
  journal={Parallel Architectures and Compilation Techniques, 2001. Proceedings. 2001 International Conference on},
  pages={211--218},
  year={2001}
}
@article{2001_hinton,
  title={{The microarchitecture of the Pentium 4 processor}},
  author={Hinton, G. and Sager, D. and Upton, M. and Boggs, D. and Carmean, D. and Kyker, A. and Roussel, P.},
  journal={Intel Technology Journal},
  volume={1},
  pages={2001},
  year={2001}
}
@InProceedings{2001_nagarajan,
  author =       { Ramadass Nagarajan             and
                   Karthikeyan Sankaralingam     and
                   Doug Burger   and
                   Stephen W. Keckler},
  title =        {A design space evaluation of grid processor architectures},
  OPTcrossref =  {SBN ~ ISSN:1072-4451 , 0-7695-1369-7},
  OPTkey =       {},
  OPTbooktitle = {Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture },
  OPTpages =     {40-51},
  OPTyear =      {2001},
  OPTeditor =    {},
  OPTvolume =    {},
  OPTnumber =    {},
  OPTseries =    {},
  OPTaddress =   { Austin, Texas},
  OPTmonth =     {},
  OPTorganization = {},
  OPTpublisher = { IEEE Computer Society },
  OPTnote =      {},
  OPTannote =    {}
}

02/02/2005

En quoi consiste un Grid processors architecture?
 -> tableau d'ALU avec un contrôle limité.
 -> Les alu sont connecté par un réseau ou circule leur opérande
 -> Les programmes sont éxécutés en mappant les blocs de manière statique et a executé les isntructions de manières dynamiques
 -> Executions possible via une chaine d'alu (sorte de pipeline)

Le GPA est conçut en vut d'avoir une grande fréquence d'horloge et une grande exploitation de l'ILP
Le coeur de calcul d'un GPA consiste en une matrice 2D de noeuds. Chaque noeud contient un buffer d'instruction et une unité d'execution.
-> noeud peuvent donc réaliser des calculs à grain fins
-> les noeuds sont interconnecter avec un réseau dédié à la communication de données et d'opérande.
-> Contrôle assuré par un mécanisme mappant les instructions sur les noeuds

=> Equivalent à une approche VLIW : Ressources alloués statiquement par le compilo mais le lancement est dynamique

MODELE D'EXECUTION
------------------

Modèle d'execution : traite des groupes d'instructions comme une unité atomique pour le fetch, mappage de ressources des unités d'execution et le commit.
Dans ce modèle, les groupes d'instructions sont définit par le compileur.
 -> Un groupe n'a pas de transfert interne de ctrl (c'est à dire un saut prit sera la dernière instruction d'un groupe) (Un bloc peut être un bloc de base ou une trace d'execution ...)
 -> Données utilisé sont de 3 types : (Modèle Producteur - consommateur)
    * entrée : valeur produite par un autre groupe et consommé par ce groupe
    * sortie : valeur produite par le groupe et consommé par un autre groupe -> écriture des données dans un mémoire tampon jusqu'au commit
    * temporaire : valeur produite et consommé par le groupe -> transimition des données en internes

Compilateur assigne statiquement chaque instruction à un groupe d'alu. Un groupe ne peut être allouer à plus d'une instruction

1) Un groupe est fétché et mapped sur les ALUs
2) Chaque instruction dans le groupe est écrite dans les buffers d'instructions ( ~ station de réservations)
3) Lecture des opérandes dans le banc de registres et placement des opérandes dans les alus.
4) Execution de l'instruction
5) Une fois que l'execution est terminé, le résultat est renvoyé vers l'alu consomatrice. (Ou vers le banc de registres)

Destination encodé explicitement dans l'instruction

6) Lorsque tte les instructions d'un groupe sont finis => commit : update de la mémoire
7) Le groupe est libéré des ALUs
8) Mappage du prochain groupe ...

Il existe un branch register pour les résultats des branchements.

Avantage
--------
-> Peu de structures larges impliqué dans l'execution (càd non centralisé, pas de fenêtre de lancement associative, pas de table de renommage de registres, peu d'accès en lecture et écriture simultané)
-> Execution désordonnée (sans vérification de dépendance large, diffusion des bypass, réseau dédié au forward)

Implémentation
--------------

ICACHEM -- REG --- REG --- REG --- REG
            |  \ /  |  \ /  |  \ /  |
            |  / \  |  / \  |  / \  |
ICACHE --- ALU --- ALU --- ALU --- ALU --- DCACHE
            |  \ /  |  \ /  |  \ /  |
            |  / \  |  / \  |  / \  |
ICACHE --- ALU --- ALU --- ALU --- ALU --- DCACHE
            |  \ /  |  \ /  |  \ /  |
            |  / \  |  / \  |  / \  |
ICACHE --- ALU --- ALU --- ALU --- ALU --- DCACHE
            |  \ /  |  \ /  |  \ /  |
            |  / \  |  / \  |  / \  |
ICACHE --- ALU --- ALU --- ALU --- ALU --- DCACHE

          BLOC TERMINAISON ET TERMINAISON


ALU rangé en matrice de n*m cases.
Le bloc de terminaison détermine quel groupe d'instructions est mappé et quand celui-ci à terminé (dc commit)
Chaque alu contient 
 * des ports d'entrée pour les opérandes
 * des buffers d'instructions et d'opérandes
 * un routeur pour délivrer les résultats vers les ports de sorties
Un prédicteur de branchement va prédire le succès de ce blocs et va fetché et mappé sur la grille le bloc suivant.

Caractéristique influencant les performances :
- Organisation des ALUs (nombre et position)
- la latence du réseau d'unterconnection d'un noeud
- le nombre d'I/O de chaque noeud

Alternatives
------------
* Changer le design du réseaux de grille : Préreservations du flow, découpage du message, 
* Chgt du système mémoire : Format d'instruction compressé, envoyant ce code compréssé au L1. Dcache ~ fifo pour maintenir la cohérence => Utilisation de technique de spéculation.
* Spéculation de grille
* Management des frames : Execution de multi thread, thread spéculatif 


@article{ernst2002eds,
  title={{Efficient dynamic scheduling through tag elimination}},
  author={Ernst, D. and Austin, T.},
  journal={Computer Architecture, 2002. Proceedings. 29th Annual International Symposium on},
  pages={37--46},
  year={2002}
}
@article{akkary2003cpa,
  title={{Checkpoint processing and recovery: towards scalable large instruction window processors}},
  author={Akkary, H. and Rajwar, R. and Srinivasan, ST},
  journal={Microarchitecture, 2003. MICRO-36. Proceedings. 36th Annual IEEE/ACM International Symposium on},
  pages={423--434},
  year={2003}
}
@article{2002_mukherjee,
  title={{The Alpha 21364 network architecture}},
  author={Mukherjee, SS and Bannon, P. and Lang, S. and Spink, A. and Webb, D.},
  journal={Micro, IEEE},
  volume={22},
  number={1},
  pages={26--35},
  year={2002}
}
@article{sprangle2002ipp,
  title={{Increasing processor performance by implementing deeper pipelines}},
  author={Sprangle, E. and Carmean, D.},
  journal={Computer Architecture, 2002. Proceedings. 29th Annual International Symposium on},
  pages={25--34},
  year={2002}
}
@article{2002_tendler,
  title={{POWER4 system microarchitecture}},
  author={Tendler, J.M. and Dodson, J.S. and Fields Jr, J.S. and Le, H. and Sinharoy, B.},
  journal={IBM Journal of Research and Development},
  volume={46},
  number={1},
  pages={5--25},
  year={2002}
}
@Article{2002_ungerer,
  author =       {T. Ungerer and 
                  B. Robic   and
                  J. Silc },
  title =        {Multithreaded processors},
  journal =      {The Computer Journal},
  year =         {2002},
  OPTkey =       {},
  OPTvolume =    {45},
  OPTnumber =    {3},
  OPTpages =     {320-348},
  OPTmonth =     {},
  OPTnote =      {},
  OPTannote =    {}
}

17/02/2005

Contrainte de la conception d'un proc multi thread :
 - Différente logique pour le calcul d'adresse
 - Les threads doivent avoir une espaces d'adressage commun
 - Extraction de thread de manière hardware ou software (compilo)

-> implicite multi threading : Chaque architecture va executer de manière concurrentiel différent thread d'un même programme séquentiel (predication de branchement etc...)
-> explicite multi threading : Execution d'un flots multi programmé

But principal -> recouvrir la latence d'un thread par l'execution d'un autre.


Mécanisme minimal :
- Plusieurs PC
- Mécanisme pour commuter les threads
  |-> Potentiellement avoir plusieurs banc de registres permet d'augmenter la commutation

3 approches :
- multithreading imbriqué  (FMT) : Changement de thread à chaque cycle
- multithreading bloqué    (VMT) : Changement de thread à chaque évenement (evt induiant une latence => ex div, miss etc ...)
- multithreading simultané (SMT) : Plusieurs threads actifs en même temps

Fine graine MT
~~~~~~~~~~~~~~
L'imbrication de plusieurs threads va limiter la perf de chaque thread
 -> technique "dependance lookahead" : ajout de bits à chaque inst dans l'isa pour déterminer combien d'inst suivant n'a pas de dépendance avec celle-ci
 -> technique d'imbrication : chgt de thread à chaque cycle

Diverses "astuces" : Cray-MTA à au moins 128 contextes afin de masquer la latence de la mémoire étant de 128 cycles (Changement de contexte à chaque cycle)

Coarse graine MT
~~~~~~~~~~~~~~~~

=> Execution d'un thread jusqu'a ce qu'une condition de changement de contexte est atteinte :

 -> Modèle statique
     -> Chgt explicite (Par instr "switch" ou une instruction "taggé")
     -> Chgt implicite (Sur load, store, branch etc ...)
 -> Modèle dynamique
     -> Chgt sur miss de cache
     -> Chgt sur evenement (interruption, trap ...)
     -> Chgt sur profil d'utilisation (trop de chargemement (ou pas accès) etc ...)
     -> Chgt conditionnel (instruction de switch conditionnelle)

Un plus petit nombre de threads est nécessaire pour atteindre de bonne performance.
-> Pénalisation d'un thread remplicant souvent la condition de changement de contexte

Avantage de Modèle statique -> le changement de contexte peut être détecter tôt dans le pipeline (Voir tjs dans le même étage).

Simultaneous MT
~~~~~~~~~~~~~~~
FMT et CMT sont très performant pour des processeurs scalaire ou VLIW (un flut d'instruction)

L'unité d'IFETCH peut être partagé par plusieurs threads, (Dans ce cas on augmente la probabilité d'aller chercher des instructions non spéculative). 
De plus l'unité IFECTH peut choisir quel thread privilégié pour aller chercher ces instructions.

 -> Partage de ressources : tous les thread partage un maximum de ressources (ifetch buffer, décodeur, banc de registres, fenêtre d'instruction etc ...)
 -> Duplication de ressources : Chaque buffer interne appartient à un thread spécifique. Les étages internes peuvent être multiplexé ou dupliqué entre les threads.

Priorité :
 RR        : Round-Robin
 ICOUNT    : La priorité est donné au thread ayant le moins d'instructions dans les étages decodes, rename et queue
 BRCOUNT   : La priorité est donné au thread ayant le moins de branchement (donc le - spéculatif)
 MISSCOUNT : La priorité est donné au thread ayant le moins de DCACHE miss
 IQPOSN    : La priorité est donné au thread ayant les plus vieille instructions

SMT peut aussi executer les deux chemins d'un branchement. 

Diverses technique :
~~~~~~~~~~~~~~~~~~~~

- Division d'un thread en collection de tâches qui sont distribués dans les unités d'executions.
  -> processeur de trace
- Processeur "super-threadé" un pipeline d'execution/thread,  peut être alloué par le compilateur
- dynamic multi threading processor : Création de threads de manière dynamique (sur appel de procédure et déroulement de boucle ...)
- microthread -> Création d'un microthread de manière explicite => préfetech une donner, calculer en avance la condition de saut ...
              -> Utilisation des threads "idle"
- Execution des 2 branches d'un saut -> utilisation des threads "idle"
                                     -> utilisation de la prédication

Multi-threading et le temps réel
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-> Le chgt de contexte "rapide" est un avantage clé pour les systèmes temps réel.
-> Le multi threading permet d'avoir la routine d'intérruption et le programme principale dans 2 threads du processeurs

Chip multi processors
---------------------
Symetric multiprocessors (SMP) et le Distribued shared Memory multiprocessors (DSM) -> espace mémoire uniforme (UMA)
un DSM peut également ne pas maintenir la propriété d'espace mémoire uniforme => Communication par passage de message

Cohérence des caches par snooping (SMP) ou directory based (DSM).

3 alternatives de CMP :
 - mémoire partagé (SMP typique)
 - L2 partagé
 - L1 partagé
partagé les niveaux de caches diminue le délai de communication iter-processeur. Plus d'espaces pour les threads

@article{2003_jeong,
  title={{Cost-sensitive cache replacement algorithms}},
  author={Jeong, J. and Dubois, M.},
  journal={High-Performance Computer Architecture, 2003. HPCA-9 2003. Proceedings. The Ninth International Symposium on},
  pages={327--337},
  year={2003}
}
@article{2003_koufaty,
  title={{Hyperthreading technology in the netburst microarchitecture}},
  author={Koufaty, D. and Marr, DT},
  journal={Micro, IEEE},
  volume={23},
  number={2},
  pages={56--65},
  year={2003}
}
@article{2003_mcnairy,
  title={{Itanium 2 processor microarchitecture}},
  author={McNairy, C. and Soltis, D.},
  journal={Micro, IEEE},
  volume={23},
  number={2},
  pages={44--55},
  year={2003}
}
@article{park2003rdc,
  title={{Reducing design complexity of the load/store queue}},
  author={Park, I. and Ooi, C.L. and Vijaykumar, TN},
  journal={Microarchitecture, 2003. MICRO-36. Proceedings. 36th Annual IEEE/ACM International Symposium on},
  pages={411--422},
  year={2003}
}
@InProceedings{2003_sankaralingam,
  author =       { Karthikeyan Sankaralingam      and
                   Ramadass Nagarajan    and
                   Haiming Liu   and
                   Changkyu Kim          and
                   Jaehyuk Huh   and
                   Doug Burger   and
                   Stephen W. Keckler    and
                   Charles R. Moore},
  title =        {Exploiting ILP, TLP, and DLP with the polymorphous TRIPS architecture},
  OPTcrossref =  { ISBN:0-7695-1945-8},
  OPTkey =       {},
  OPTbooktitle = {Proceedings of the 30th annual international symposium on Computer architecture},
  OPTpages =     {422-433},
  OPTyear =      {2003},
  OPTeditor =    {},
  OPTvolume =    {Volume 31 Issue 2},
  OPTnumber =    {},
  OPTseries =    {},
  OPTaddress =   {San Diego, California},
  OPTmonth =     {May},
  OPTorganization = {},
  OPTpublisher = {ACM Press},
  OPTnote =      {},
  OPTannote =    {}
}

01/02/2005

Architecture polymorphe : TRIPS
Peut être configuré pour différente granularité et types de parallélisme => Instruction level paralelism, Thread LP Data LP.

Processeur : Soit on a un général-purpose microprocesseur qui sait tout ou alors on spécialise le processeur :
 -> Bureautique, network, serveur, scientifique, graphique ou signaux digitaux.

La spécialisation à un défaut :
 -> Le processeur devient peut performant dans un domaine qui n'est pas sa spécialisation.

Les CMP peuvent être vut de 2 manières :
 -> Homogène   : Ensemble de processeurs identiques
 -> Hétérogène : Regroupement de processeurs spécialisé -> mappage d'une application sur cet architecture ...
    |-> Défauts : * Augmentation de la compléxité
                  * Sous utilisation des ressources si un thread n'a pas besoin de la spécialité

Une architecture polymorphique est capable de configurer le hard pour exécuter de manière efficace un large spectre d'applications.
-> Approche synthétique : Utilisation de CMP à grain fin -> synthése de plusieurs éléments de calcul en une large entité logique.
-> Approche partitionné : Utilisation de CMP à grain grossier => Partitionnement de l'entité la plus large pour exploiter le parrallélisme à grain fin.

Une architecture polymorphe ne va pas surpasser une architecture dédié, mais devrait bien se comporter avec un large spectre d'application.

TRIPS -> Architecture polymorphique, approche partitionné combiné avec un coeur de processeur en grille à grain grossier et avec un système  mémoire on chip adaptatif.
Objectif -> Avoir un coeur d'architecture qui peut aussi bien être très large que minuscule (scalable)

Architecture TRIPS
------------------
Architecture orienté blocs.
Un programme compilé pour le TRIPS est partitionné en bloc large d'instruction avec un seul point d'entrée, sans boucle et plusieurs point de sorties
Les blocs valide de manière atomique et les intérruptions sont "blocs précis". (Plus de décision au point de vue instruction mais au point de vue bloc)

Compilateur est résponsable de l'allocation statique de chaque bloc d'instruction dans le le système (Dépendance explicite).

Une opération de flot usuel du proc : Chgt d'un boc depuis la mémoire, chgt dans le moteur de calcul, execution,  reporter les resultats dans la mémoire, chgt d'un autre bloc ...

-> TRIPS est constitué de 4 blocs de 16 coeurs polymorphe. Une grille de 32Ko de mémoire connecter en quadrillage, des ctrl mémoires distribué pour connecter de la mémoire externe.
-> Chaque blocs est constitué de d'un tableau de noeud d'execution, Il y a un ICACHE L1 par ligne dans la matrice , et une partie du banc de registre par colonne. Sur chaque ligne (droite) il y a également un DCACHE L1. En dessous de la matrice il y a le block de logique de ctrl qui s'occupe du séquencement de ce bloc et de la sélection du prochain bloc. Les caches L1 sont connecté au cache L2 a l'aide d'un interconnect.

-> Chaque noeud d'execution contient une IU, FPU, des stations de réservations, un routeur de connections I/O, un noeud est directement connecter avec ses plus proches voisins, mais peut communiquer avec n'importe quel noeud dans la matrice
-> Chaque stations de réservations stocke des isntructions et 2 opérandes sources.

3 types principaux de ressources :
 * hardcoded (ressources utilisées dans tous les mode et non modfiable) ex : interconnect, unité d'execution, cache L1
 * ressources utilisé dans tous les modes et modifiable
 * ressources non nécessaires dans tous les modes et pouvant être désactivés.

Gestion du ILP : D-morph
------------------------
-> La configuration D-morph traite les buffers d'instructions comme un large, distribué fenêtre de lancement d'instructions. Possibilé d'avoir de l'execution our-of-order
Le buffer d'instruction doit fournir une large bande passante de chargement d'instruction, un contrôle aggréssif et une spéculation sur les données, une mémoire à faible latence et qui préserve les accès mémoires de manière séquentiels

Vue des buffers comme en trois dimension (x,y sont les coordonées physique dans un bloc et z correspond au nombre de place d'instructions dans chaque noeuds d'ALU.
Le compilateur va découper le code en hyperblock (morceau de code communicant dans un graphe en 3D et dont il n'y à qu'un net de sortie.) Mappage de ces blocs dans des frames. (Différents slots de buffers sur le même noeuds d'alu). Les A-frame est la zone contenant tous les frame mappant un hyperblock.

Spéculation de Multiblock : Les A-frames vide vont spéculativement chargé et executé un hyperblock. Les A-frames sont traités de manière circulaire : Le buffer de tête étant le moins spéculatif

Instruction fetching -> pc pointe sur les têtes d'hyperblocks. Prédiction sur le prochain hyperblock (et non sur la prochaine instruction). Hyperblock sont codés du style VLIW.
Interface mémoire : Entrelacement des bancs mémoires -> accès simultané a des adresses non conflictuelles.
Mémoire secondaire configure le réseau de bank comme un cache à accès non uniform.

Résumé : Prédiction  de fin assuré, grande bande passante pour l'ifecth, Dcache partitioné, execution concourente d'hyperblock (avec le réenvoie des valeur d'interbloc), le Dmorph est capable d'utiliser le buffer d'instrcution comme une fenêtre de lancement out of order

Gestion du TLP : T-morph
------------------------
-> fournit un mappage un contrôle pour les multi thread.
SMT -> cache et unité d'execution sont partagé.

2 stratégies : 
 - processeurs de lignes -> Partage la matrice d'ALU, en alloue une ou plusieurs lignes par threads. -> chaque thread à un nombre de  ICACHE et un DCACHE proportionnel au nombre de lignes alloué. Attention : La distance du banc de registre n'est pas uniforme (pénalise les lignes inférieurs)
 - processeurs de frames -> Partage le processeur par un ensemble de frames

|-> Les frames sont partagé entre thread. Un l'intérieur d'un thread, les frmae peuvent être spéculatif (cf D-morph)
|-> T-morph maintient n PC et n historique de banc de registres

Gestion du DLP : S-morph
------------------------
TRIPs est principalement prévut pour les flots multimédia et les calculs scientifiques => contient beaucoup de parrallélisme a niveau donnée

-> fusion des Aframe pour un Super Aframe => Les boucles sont déroullées
-> mapping reuse : un bloc est gardé dans les stations de réservations pour être utilisé plusieurs fois
-> Dans les caches, ajout d'une fonctionnalité DMA
@article{sethumadhavan2003shm,
  title={{Scalable hardware memory disambiguation for high ILP processors}},
  author={Sethumadhavan, S. and Desikan, R. and Burger, D. and Moore, CR and Keckler, SW},
  journal={Microarchitecture, 2003. MICRO-36. Proceedings. 36th Annual IEEE/ACM International Symposium on},
  pages={399--410},
  year={2003}
}
@InProceedings{2004_chaudhuri,
  author =       {Mainak Chaudhuri   and
                  Mark Heinrich},
  title =        {SMTp: An Architecture for Next-generation Scalable Multi-threading},
  OPTcrossref =  {},
  OPTkey =       {},
  OPTbooktitle = {Proceedings of the 31st annual international symposium on Computer architecture},
  OPTpages =     {124-136},
  OPTyear =      {2004},
  OPTeditor =    {},
  OPTvolume =    {0},
  OPTnumber =    {},
  OPTseries =    {},
  OPTaddress =   {München, Germany},
  OPTmonth =     {},
  OPTorganization = {},
  OPTpublisher = {IEEE Computer Society},
  OPTnote =      {},
  OPTannote =    {}
}

17/03/2005

Modification d'uns SMT pour intégré un protocol de cohérence des threads afin de le placer dans un système à mémoire distribué (DSM).

DSM sont scalable, mais s'ils n'utilisent pas de protocoles de snoop. Le directory based impose des structations de tableaux.

Architecture
------------

Le processeur à une architecture classique :
 9 étages : fetch, decode, issue, lecture1, lecture2, exec, cache accès, commit
fetch suit la politique ICOUNT (cf 1996\_tullsen)
=> Il y a 2 threads. Tous est partagé sauf pile des adresses de retours, table de mappage, prédicteur dynamqiue

Un noeud est séparé en deux parties :
 - le coeur du proc
 - le contrôlleur mémoire

Le protocole de cohérence est lié à un thread. Celui-ci n'execute que cela (programme dédié donc n'est pas visible de l'extérieur). Il n'est pas aborder de solution dynamique (dès que la cohérence est nécessaire, un thread doit executer ce dernier)

Afin d'éviter les deadlocks (applications tournants sur les threads et le threads gérant le protocole partagent les même ressources (file d'execution etc ...)), il y a des ressources dédié au threads executant le protocles des threads.

Performance
-----------
3 limitations :
- Le protocole de thread souffre de la latence du pipeline
- Le nombre de registre entiers
- Le DCACHE-L1 et les CACHE-L2 sont partagés entre les applications tounants sur les threads et le protocole de cohérences des threads

@article{2004_collins,
  title={{Clustered multithreaded architectures-pursuing both IPC and cycle time}},
  author={Collins, JD and Tullsen, DM},
  journal={Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International},
  year={2004}
}
@article{2004_dolbeau,
  title={{CASH: Revisiting hardware sharing in single-chip parallel processor}},
  author={Dolbeau, R. and Seznec, A.},
  journal={Journal of Instruction-Level Parallelism},
  volume={6},
  pages={1--16},
  year={2004}
}
@article{2004_kalla,
  title={{IBM Power5 chip: a dual-core multithreaded processor}},
  author={Kalla, R. and Sinharoy, B. and Tendler, JM},
  journal={Micro, IEEE},
  volume={24},
  number={2},
  pages={40--47},
  year={2004}
}
@article{2004_kumar,
  title={{Conjoined-Core Chip Multiprocessing}},
  author={Kumar, R. and Jouppi, N.P. and Tullsen, D.M.},
  journal={Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture},
  pages={195--206},
  year={2004},
  publisher={IEEE Computer Society Washington, DC, USA}
}

@InProceedings{  2004_wang,
  author =       {Nicholas J. Wang and
                  Justin Quek      and
                  Todd M. Rafacz   and 
                  Sanjay J. Pate},
  title =        {Characterizing the Effects of Transient Faults on a High-Performance Processor Pipeline},
  OPTcrossref =  {In the Proceedings of the 2004 International Conference on Dependable Systems and Networks},
  OPTkey =       {},
  OPTbooktitle = {},
  OPTpages =     {},
  OPTyear =      {2004},
  OPTeditor =    {},
  OPTvolume =    {},
  OPTnumber =    {},
  OPTseries =    {},
  OPTaddress =   {Florence , ITALY},
  OPTmonth =     {june},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote =      {},
  OPTannote =    {}
}

30/11/2004

Moins de 15 \% des corruptions binaires sont visibles du logiciel, des techniques simples d'overhead diminues de 75\% des fautes.

D'ou viennent les fautes :
 - Sources externe (pulsation electro magnétique)
 - Sources interne (fuite, bruit da'alimentation ...)

Pour caractériser ses fautes, ils ont définit un modèle de processeur :
 - ISA alpha
 - Superscalaire, ordonnacement dynamique (à 32 entrées)
 - execution spéculative
 - prédiction des dépendances mémoires
 - 12 étages de pipelines
 - 6 inst lancées/cycle

4 types d'erreurs :
 - Correspondances à un état de la micro architecture
 - Arret prématuré de la tâche
 - Corruption d'une donnée
 - Rien sur le comportement

85\% des fautes sont masqués
 3\% sont invisibles
12\% réalise une execution erronée

=> Les registres visibles sont les plus vulnérables

Types d'erreurs dut à une execution erronnée :
 - Inconsistence du banc de registres
 - Inconsistence mémoire
 - deadlock ou livelock
 - Accès à une page virtuel invalide (Inst ou data)
 - Part en exception
 - Réalise une instruction non demandé
 
Mécanisme de protection :
 - Timeout => Evite les lock
 - Code correcteur d'erreur => sur le banc de registres et sur le pointeur de ce banc (register renaming)
 - Bit de parité => sur le registre IP (il traverse tous le pipeline)
@article{2005_kongetira,
  title={{Niagara: a 32-way multithreaded Sparc processor}},
  author={Kongetira, P. and Aingaran, K. and Olukotun, K.},
  journal={IEEE Micro},
  volume={25},
  number={2},
  pages={21--29},
  year={2005}
}
@article{2005_mcnairy,
  title={{Montecito: a dual-core, dual-thread Itanium processor}},
  author={McNairy, C. and Bhatia, R.},
  journal={Micro, IEEE},
  volume={25},
  number={2},
  pages={10--20},
  year={2005}
}
@article{2006_ghasemzadeh,
  title={{Modified Pseudo LRU Replacement Algorithm}},
  author={Ghasemzadeh, H. and Mazrouee, SS and Kakoee, MR},
  journal={Engineering of Computer Based Systems, 2006. ECBS 2006. 13th Annual IEEE International Symposium and Workshop on},
  pages={368--376},
  year={2006}
}
@article{sethumadhavan2007lbe,
  title={{Late-binding: enabling unordered load-store queues}},
  author={Sethumadhavan, S. and Roesner, F. and Emer, J.S. and Burger, D. and Keckler, S.W.},
  journal={Proceedings of the 34th annual international conference on Computer architecture},
  pages={347--357},
  year={2007},
  publisher={ACM Press New York, NY, USA}
}