Embed Size (px)
Citation preview
1
ARPO
Architectures des processeurssuperscalaires, VLIW et optimisations
2
L’interface logiciel / matériel
transistor
micro-architecture
jeu d’instructions (ISA)
compilateur
langagelogiciel
matériel
3
Jeu d’instructions (ISA)
� C’est l’interface matériel / logiciel� Exemples
� Intel x86 (1979)� MIPS , SPARC (milieu années 80)� Alpha (début années 90)
� Les ISA évoluent lentement, par ajouts successifs� il faut avoir de bonnes raisons pour lancer un nouveau jeu
d’instructions• plus de raisons pour les processeurs enfouis : applications
spécifiques, densité du code, consommation électrique, ...
4
Microarchitecture
� Vision macrocospique de l ’implémentation du matériel:� pas besoin de savoir comment fonctionne un transistor !!
� Mais comprendre pourquoi un programme séquentiel (ensémantique), lisant ses données et instructions dans unemémoire répondant en 100 ns peut exécuter 4 instructionstoutes les 500 ps
5
Contextes des processeurs hautesperformances
� Processeurs à usage général� serveurs, ordinateurs de bureau, ordinateurs de poche
...� exécute tous types d’applications
� Processeurs « enfouis »� téléphone, télévision, voiture ...� application spécifique� processeur spécialisé ou dérivé d’un processeur à
usage général
6
Besoins en performances
� Performance:� améliorer le temps de réponse => interactivité� applications scientifiques� bases de données� traitement du signal� multimédia� …
� Pseudo-loi vérifiée dans l ’histoire de l’informatique:
Tout gain en performance génère de nouvelles applications qui génèrent de nouvelles demandes en performance
7
Comment améliorer la performance ?
transistor
micro-architecture
jeu d’instructions (ISA)
compilateur
langage
écrire un meilleuralgorithme
optimisations ducompilateur
améliorer l’ISA
meilleure micro-architecture
nouvelletechnologie
8
Où doit porter l’effort ?
compilateur ISA micro-architecture
processeur usage général
processeur enfoui
+ + + + + ++ ++ + + + +
Processeur usage général ISA préexistant (exemple: Intel x86)
compatibilité binaire: la nouvelle génération de processeur doit pouvoir exécuterles codes exécutables sur les anciennes générations
Processeur enfouiattention au coût du processeurcompromis performance / consommation électrique
9
Qu’est ce que la performance ?
� Choisissez votre point de vue !
� Débit d’exécution: faire plus de travail utile pendant un temps donné� serveurs� environnement multiprogrammé
� Temps d’exécution : faire un travail donné dans un temps plus court� point de vue de l’utilisateur
� Faire un travail en un temps déterminé: temps réel, une fois l’objectifrien ne sert d’aller plus vite� consommer moins, circuit plus petit, ..
10
Quelques métriques
Fréquence CPU f : fréquence de l’horloge interne du processeur
dépend de la technologie et de la micro-architecture
Cycle CPU: T = 1 / f
Nombre moyen d’instructionsexécutées par cycle cycles de totalnb
exécutées nsinstructiod' totalnb=IPC
11
pour l’architecte, à application, jeux de données, ISA et compilateurfixés,
+ fréquence fixée: Instruction par Cycle (IPC)
MIPS / megaflops
MIPS =
f⋅= IPCMIPS
nombre moyen de millions d’opérationsvirgule flottante par seconde
Utilisé pour le calcul numérique intensif
megaflops =
nombre moyen de millions d’instructionsexécutées par seconde
12
Comparer des machines différentes !?
Solution 1 : temps CPU
Les MIPS n’ont aucune signification ici car les ISA sont différents
Solution 2 : utiliser une machine de référence
référenceréférencerelatif MIPSonaccélératiMIPS ×=
Exemple: VAX MIPS
13
Accélération locale / globale
Un programme passe 50% du temps d’exécution dans du calculen virgule flottante, et supposons qu’on multiplie par 10 lesperformances du calcul en virgule flottante. Quelle estl’accélération globale ?
tttt2011
201
21 =+=′
81.11120 ==
′=
ttaglobale
14
Accélération locale / globale (2)
supposons qu’on multiplie par 1.5 les performances du calcul enentier et par 4 les performances en virgule flottante. Quelle estl’accélération globale ?
tttt2411
41*
21
32*
21 =+=′
18.21124 ==
′=
ttaglobale
15
Accélération locale / globale (3)
tttt50069
5049*
101
501 =+=′
24.769
500 ==′
=ttaglobale
Un programme passe 98 % du temps d’exécution dans du calculen virgule flottante, et supposons qu’on multiplie par 10 lesperformances du calcul en virgule flottante. Quelle estl’accélération globale ?
16
Loi d’Amdahl
tfractionta
fractiont
tta
amélioréelocale
amélioréeglobale
)1( −+=
′=
locale
amélioréeaméliorée
globale
afractionfraction
a+−
=)1(
1
17
Que dit la loi d’Amdhal
Il faut optimiser d’abord le cas le plus fréquent
Mais aussi optimiser tous les composants
18
Programmes de test
� Programmes « standards » (benchmarks)� exemple 1 : SPEC CPU2000
• SPEC int : compression de données, compilateur, interpréteur,synthèse d’image, analyseur grammatical, jeu d’échec,conception de circuits ...
• SPEC fp : physique, maths, chimie, météo ...� Exemple 2 : TPC (Transaction Processing Performance)
• base de données multi-utilisateurs• sollicite les entrées-sorties
� Programmes spécifiques
Il faut choisir les programmes de test
appropriés à l’utilisation envisagée ...
19
Évaluer / analyser les performances
� L ’utilisateur lambda: mesures de temps d’exécution� Comprendre le temps d’exécution: instrumentation
� quelle partie du code contribue le plus au temps d’exécution ?� code instrumenté = code original + code supplémentaire permettant de
récupérer de l’information à l’exécution (exemple: adresses mémoire)� exemples d’outils: Prof, Pixie, Salto, EEL, Atom, …
� Compréhension fine: utiliser les compteurs matériels du processeur� compte certains évènements
� Définition de nouvelles architectures� simuler l’exécution au lieu d’exécuter réellement� l’ISA simulé peut ne pas être celui de la machine sur laquelle on simule� Exemples de simulateurs: Simplescalar, Shade, SimOS, Impact ...
20
N’oubliez pas
Pour comprendre l’architecture,il faut une vision minimale du contexte technologique
mais aussi économique
Contexte technologique =
Cible mouvante
Contexte économique
« Intel est le plus fort »
21
« Loi » de Moore
� Le nombre de transistors sur un micro-processeur double tous les 18 mois� 1972: 2000 transistors (Intel 4004)� 1979: 30000 transistors (Intel 8086)� 1989: 1 M transistors (Intel 80486)� 1999: 130 M transistors (HP PA-8500)
� Les performances des processeurs doublent tous les 18 mois:� 1989: Intel 80486 16 Mhz (< 1inst/cycle)� 1993 : Intel Pentium 66 Mhz x 2 inst/cycle� 1995: Intel PentiumPro 150 Mhz x 3 inst/cycle� 06/2000: Intel Pentium III 1Ghz x 3 inst/cycle� 09/2002: Intel Pentium 4 2.8 Ghz x 3 inst/cycle
22
Utilisation des transistors: évolution
années 70
Étoffer l’ISA pour diminuer lenombre d’instructions exécutées + +
+ de mémoire on-chip (cache,registres)pour diminuer les accès externes
années 80
+ +
années 90
+
+ ++
Exécution superscalaire + +
+
RISC
8 => 16 => 32 bitscalcul flottant
32 => 64 bitsmultimédia
+
23
Quelques repères (sept. 2002)
� Fréquence : 900 Mhz à 2.8 Ghz� Durée d'une opération ALU: 1 cycle� Durée d'une opération flottante : 3 cycles� Lecture/écriture dans un registre : 1-3 cycles
� souvent un chemin critique ...� Lecture/écriture du cache L1: 1-2 cycles
� dilemme taille-associativité-temps d ’accès
24
Quelques repères (2001)
� L'intégration : 0.18µ, 0.130µ, 0.90µ� 10 à 20 millions de transistors de logique� Le reste en mémoire cache: jusqu'à 100 millions de
transistors� 20 à 75 Watts
� > 120 W (Itanium 2)� 400 à 600 broches
� > 1000 bientôt
25
Quelques repères (sept. 2002)
� Processeurs x86 pour PC:�bas de gamme: Duron 1.3 Ghz, 64 $�haut de gamme: Athlon 2.25 Ghz, 397 $
� La mémoire DDR DRAM : 0.20 $ le Mbyte
26
Compatibilité binaire
� Une donnée économique : 500 000 000 dePCs !�un nouveau jeu d'instructions: RISQUÉ !!
� Le monde change (peut-être):�les processeurs enfouis, le multimédia�l'IA 64 arrive�x86: mutation vers 64 bits (AMD ) ?
27
Architecture 32 ou 64 bits
� Architecture 32 bits: l'adresse virtuelle est de 32 bits� PowerPC, x86,
� Architecture 64 bits : l'adresse virtuelle est de 64bits.� MIPS III, Alpha, Sparc V9, HP-PA 2.x, IA64� En 2005: les jeux ? Word ?
� LE MOUVEMENT EST INEXORABLE:� x86 la rupture ou x86-64 ?
28
L’angoisse de l’architectedu processeur haute performance
� 400 mm2 de silicium� 3 générations de technologie en avant� que faire pour obtenir les performances ?
� Pipeline� Parallélisme d’instruction� L’exécution spéculative� La hiérarchie mémoire
� demain, le parallélisme de processus
29
Le pipeline
30
Principe de base
� Faire se chevaucher l'exécution de plusieurs instructions.
� On décompose l'exécution d'une instruction en plusieursphases successives
31
Pipeline (2)� On ajuste les phases pour qu'elles aient la même durée :
� 1 cycle de la machine
� L'exécution d'une instruction est allongée� Difficile de découper en phases de même durée� Le découpage entraîne un surcoût :
• traversée de buffers
� Mais une instruction peut être lancée tous les cycles.
32
Exemples de pipeline
� MIPS R3000 :
� MIPS R4000 :
33
Exemples de pipeline (2)
� DEC 21064 :� 2 étages d’exécution
� Cypress Sparc� étages EX et MEM confondus
� Aujourd’hui:� Pentium 4: 18 cycles avant l ’étage EX !
34
Le débit d'un pipeline
� Hypothèse on peut séquencer une instruction par cycle� débit maximum d'1 instruction par cycle� Exemple : 5 étages
� Sur une machine non pipeline : 300 ps, 400 ps, 300 ps ,200 ps, 400 ps
• Durée totale = 1600 ps� Sur une machine pipeline : cycle 500 ps = 400 ps + 100 ps
(pour les buffers)• Speed-up potentiel : 3.2
� Limite en multipliant les étages du pipeline : overhead desbuffers
35
Le pipeline: les limites
� Actuellement:� 1 cycle = traversée de 12 à 15 portes logique:
• en gros le temps d ’une addition 64 bits
� Demain:� 6 à 8 portes� Déjà sur le Pentium 4:
• ALU séquencée au 1/2 cycle:– temps d’une addition 16 bits
36
Attention aux exécutions longues
� Sur les entiers :� multiplication : 5-10 cycles� division : 20-50 cycles
� Sur les flottants :� Addition : 2-5 cycles� Multiplication: 2-6 cycles� Division: 10-50 cycles
37
Vie d’une instruction (MIPS 4000)
� 1. IF (Instruction Fetch).� Lecture du cache instructions et lecture du TLB
� 2. IS (Instruction Fetch, Second Half)� Fin de lecture du TLB et du cache instructions
� 3. RF (Register File):� Décodage de l’instruction , lecture des opérandes,
vérification des étiquettes� 4.EX (Exécution).
� Exécution des opérations registre-registre ou� calcul de l’adresse virtuelle pour les Load/Store ou� calcul de l'adresse virtuelle de la cible pour les
branchements
38
Vie d ’une instructionsur le MIPS R4000 (2)
� 5 DF (Data Fetch, First Half):� accès au cache de données, et parallèlement, et
traduction de l'adresse virtuelle en adresse physique� 6. DS (Data Fetch, Second Half):
� fin de l'accès au cache et de la traduction d'adresses.� 7. TC (Tag Check) :
� comparaison de l'étiquette du cache avec l'adressephysique du TLB pour déterminer si il y a eu un défaut decache ou non.
� 8. WB (Write Back) :� Ecriture du résultat de l'instruction dans un registre (s'il y a
lieu).
39
Les aléas dans les processeurspipelines
� Parfois (souvent), l'instruction suivante ne peut pas êtreexécutée tout de suite :� Ces situations sont appelées aléas
� Aléas de structure : conflits de ressources� Aléas de données : dépendances de données� Aléas de contrôle : les branchements
40
Que faire sur les aléas?
� Gestion par matériel :� détecter les aléas et les éviter en retardant l'avancée de
l'instruction amont en attendant la résolution de l'aléa.
� Gestion par logiciel :� retarder les instructions pour éviter les dépendances, ..
41
Petite digression:De l'avantage d'un jeu d'instruction
régulier pour le pipeline
42
RISC versus CISC
� Entre 1960 et 1980, la complexité des opérations qui pouvaientêtre implémentées en matériel a augmenté
� les jeux d'instructions ont suivi le même chemin.
43
Complex Instruction Set Computing(CISC).
� But: une instruction machine = une instruction langage de hautniveau� VAX, Intel 80x86, Motorola 680x0, IBM 360
� sur le VAX, une opération arithmétique (2 opérandes, unrésultat) :� opérandes et résultat soit en registre, soit en mémoire� 8 cas� Le calcul de l'adresse pour chacun des accès à la mémoire peut être :
• absolu : adresse codée dans l'instruction• basé : registre + immédiat• indexé : registre + registre• indirect : lue en mémoire
44
CISC (2)
� Codage compact des applications:� peu demandeur en lecture sur les instructions� Tailles d'instructions variables (1 à 15 octets sur le xxx86)� Temps d'exécution variables et occupation chaotique des
ressources:• une même instruction peut occuper 6 fois la mémoire
sur le VAX.
45
De la difficulté du pipeline sur les CISC
� Taille variable des instructions� pour connaître l'adresse de l'instruction suivante, il faut
d'abord décoder l'instruction courante.� Le séquencement des instructions entraîne de nombreux
conflits de ressource :� plusieurs utilisations de la même unité fonctionnelles
� Pipeline difficile, mais pas impossible :� Le coût de la logique de contrôle est relativement important
46
RISC : Reduced Instruction SetComputer
� Concept mis en forme par Patterson et Ditzel (1980), préexistaitbien avant.
� Principes :� Une seule taille d'instruction : 32 bits en général , simplifie
le décodage� Architecture load/store : pas d'opérations avec opérandes
ou résultat en mémoire� Modes d'adressage simples : basé et indexé� Instructions simples registre-registre : opérandes dans les
registres et résultat dans les registres� Registres indifférenciés
47
RISC (2)
� Code relativement volumineux :� C= A+B :
• load A,R2• load B,R3• add R3, R2, R1
� pour une même application:� 1.5 à 2 fois le volume que pour un CISC.
� Avantage : se pipeline bien !� Lecture de l'instruction et décodage en temps constant.� Occupation d'une unité fonctionnelle à un instant précis
48
La saga RISC
� 1980 : Patterson et Ditzel formalisent le concept� 1982 : IBM 801, RISC I et RISC II� 1987-88 : MIPS R2000, Sparc� 1990 : IBM Power, Intel i860� 1992- : DEC Alpha, TI Supersparc, MIPS R4000, R8000 et
R10000, HP8000, Ultrasparc , ..
� Intel xxx86 fait de la résistance !
49
Jeux d'instructions des processeurs RISCPrincipes communs
� Une seule taille d'instruction : 32 bits en général� simplifie le décodage et le calcul de l'anticipation de
l'adresse suivante� Architecture load/store� Modes d'adressage simples : basé et indexé� Instructions simples registre-registre
� Presque consensus:� 32 registres� Bloc de registres distincts pour les flottants
50
RISC et Instructions multimédia:une entorse à la simplicité
� Principe général:
� Les instructions multimédia:
N’implémenter une instruction que si le compilateur est capable de la générer.
On « packe » plusieurs mots de 16 bits dans un registre de 64 bits. On exécute 4 fois la même instruction en //.
Aucun compilateur ne les gère correctement
51
Retour au pipeline
52
Les aléas de données
� L’exécution pipeline d'une séquence d'instructions doitproduire le même résultat qu'une exécution séquentielle.
� 3 types d'aléas peuvent se produire: i précède j� RAW (Read After Write) :
• j utilise un résultat de i comme opérande:– le résultat doit être écrit par avant que j ne le lise.
� WAR (Write After Read) :• j écrit un résultat dans une source de i
– i doit avoir lu sa source avant que j ne l'écrive� WAW (Write After Write) :
• i et j écrivent leurs résultats à la même place– j doit écrire son résultat après i
53
Read After Write sur les processeursRISC� Le problème:
� Une solution: mais perte de 2 cycles !
54
De l'utilité des mécanismes de bypass
� Le résultat en sortie de l'ALU est en fait disponible plus tôt :� On peut l'intercepter avant l'écriture dans le fichier de registres
55
Aléas Read After Write sur lesprocesseurs RISC
� Le délai de chargement mémoire
56
Et comment s'en affranchir
� a= b+c ; d= e+f
57
Les aléas WAR et WAW sur lesprocesseurs RISC
� Il n'y en a jamais !� Les opérandes sont lus dans les registres dès le décodage.� Les aléas Write After Write sur les processeurs RISC
� Il ne peut y en avoir que si les écritures ne sont pas faites à uncycle précis du pipeline:� en principe, il n'y en a pas.� Sauf que … (multiplication, division, flottants)
58
Les aléas de données sur lesprocesseurs CISC
� Tous les types d'aléas sont possibles :� Read After Write� Write after Read :
• le nombre des opérandes d'une instruction est trèsélevé.
� Write after Write :• la durée d'exécution des instructions est tout à fait
variable� Pipeliner l'exécution de plusieurs instructions sur un processeur
CISC requiert beaucoup de précautions.
59
RISC versus CISC
� RISC :� mécanismes de contrôle plus simple� possibilité de réordonnancement de code� RISC : coût et temps de conception plus réduit.� RISC : taille du composant plus réduit (à performance et
technologies équivalentes)
� CISC : volume de code plus réduit
60
Les aléas de contrôle
� L'instruction est un branchement conditionnel ou non� quelle instruction exécuter ?
� Le nombre de cycles perdu sur les branchements peut êtretrès important.
61
Les dépendances de contrôle
� 15 à 30% des instructions sont des branchements.� La cible et la direction d'un branchement sont
connues très tard dans le pipeline. Au plus tôt :� Cycle 7 sur le DEC 21264� Cycle 11 sur l'Intel Pentium III� Cycle 18 sur l ’Intel Pentium 4
� multiplié par X inst./ cycles !� Pas question de perdre tous ces cycles !
62
Le problème des sauts
En moyenne, un saut se produit toutes les 7 instructions
Pipeline de plus en plus long: > 10 étages (Intel P6, Ultrasparc 3, AMD Athlon…), et même ~20 étages (Intel Pentium 4)
)1(77
−+ N inst / cycleIPC = 0
0.25
0.5
0.75
1
1 2 3 4 5 6 7 8
N
IPC
N= étage auquel les sautssont exécutés
63
Le problème des sauts (2)
En moyenne, un saut se produit toutes les 7 instructions
Pipeline de plus en plus long: > 10 étages (Intel P6, Ultrasparc 3, AMD Athlon…), et même ~20 étages (Intel Pentium 4)
)1(77
−+ N inst / cycleIPC = 0
0.25
0.5
0.75
1
1 2 3 4 5 6 7 8
N
IPC
N= étage auquel les sautssont exécutés
64
La prédiction de branchements
prédiction PC
chargement
décodage
exécution
écriture registre
accès cache
correction simal prédit
On essaie de prédirel ’adresse de la prochaine
instruction
65
Types de branchements
� Branchement inconditionnel� le saut est systématique� saut relatif
• adresse de saut statique, connue à la compilation• exemple: PC du branchement + offset immédiat
� saut indirect• adresse de saut dynamique, lue dans un registre• retours de fonction, appels de fonctions, switch case, pointeurs de
fonctions …� Branchement conditionnel
� dépend de l’évaluation d’une condition: le branchement peut être pris (onsaute) ou non pris (on passe à l’instruction suivante)
� comparaison entre 2 registres ou comparaison d’un registre avec 0� en général, adresse de saut statique� boucles, if…then…else, switch case, ...
66
Quelques statistiques ...
� En moyenne 1 instruction sur 5 est un branchement (conditionnel ou inconditionnel)� les blocs de base sont petits (certains font 1 ou 2 instructions)� il est souhaitable de pouvoir prédire un branchement par cycle
� 75 % des branchements sont conditionnels� il est important de bien prédire les branchements conditionnels� 40 % des branchements conditionnels sont non pris
• prédire toujours non pris 60 % de mauvaises prédictions� 10 % des branchements sont des retours de fonction� 0 à 10 % des branchements sont des appels de fonction indirects
� plus nombreux dans les codes orientés objet� Restant = branchements inconditionnels relatifs
67
Les branchements dans le pipeline
Adresse de saut relatif
Branchementconditionnel exécuté
Saut indirect exécuté
prédiction
chargement
décodage
exécution
écriture registre
accès cache
Branchement identifié
68
Prédiction de branchementdynamique
� Garder un historique des derniers passages etutiliser cet historique pour anticiper le branchement
� Mise en œuvre: une table lue en même temps que lecache d’instructions
� On prédit:� la cible et la direction des branchements� les retours de procédures� les branchements indirects
69
Les étapes de la prédiction
� Prédire qu’à l’adresse indiquée par le compteur de programme se trouve une instructionde branchement
� Identifier le branchement� branchement conditionnel ou inconditionnel ?� appel de fonction ?� retour de fonction ?
� Prédire l’adresse de saut� Pour les branchements conditionnels, prédire si le branchement est pris (1) ou non pris
(0)� En cas de mauvaise prédiction, profiter du temps de réparation du pipeline pour corriger
la table de prédiction
70
Table de prédictions
prédiction
chargement
décodage
exécution
écriture registre
accès cache
Est-ce un branchement ?Si oui : info table= (type, 0/1,adresse saut) PC <== F (PC, info table)Si non : PC <== PC + 4
PC suivant
PC courant
Mise à jour si mauvaise prédiction
71
Identifier le branchement
BTB (Branch Target Buffer)
étiquettes cibles
PC
= ?
Cible
72
Utilisation du BTB
� On stocke dans le BTB les sauts inconditionnels et les branchements pris� La présence d’une entrée dans le BTB entraîne un saut à l’adresse indiquée par le BTB� En l’absence d’une entrée BTB, on suppose que l’instruction n’est pas un branchement
ou est un branchement non pris� En cas de mauvaise prédiction, corriger le BTB
� si on a « manqué » un saut, rajouter l’entrée manquante� si on a prédit un branchement pris alors qu’en réalité il est non pris, enlever
l’entrée du BTB� si on a sauté à une mauvaise adresse, corriger l’adresse de saut dans le BTB
73
Direction d ’un branchementconditionnel
� Il est plus important de prédire la direction que la cible d ’unbranchement conditionel:
� saut relatif: cible recalculée au décodage
� direction connue: à l ’exécution
74
Prédiction comme la dernière fois
for (i=0;i<1000;i++) { for (j=0;j<4;j++) { : corps de la boucle }}
Branchement mal prédit à lapremière et à la dernière itération
prédictiondirectioneffective
11101110
1110111
1 0
mal préditmal prédit
mal préditmal prédit
75
Le compteur 2 bits
0123
0000
11 1 1
prédit 0prédit 1
� 4 états 2 bits� la prédiction est obtenue en lisant le bit de poids fort du compteur� il faut 2 mauvaises prédictions consécutives pour changer la prédiction en partant d’un état « fort » (0
ou 3)� Se trompe seulement à la dernière itération d ’une boucle
76
Efficacité du compteur 2 bits
for (i=0;i<1000;i++) { for (j=0;j<4;j++) { : corps de la boucle }}
Branchement mal prédit à ladernière itération seulement
� Le compteur 2 bits divise par 2 le nombre de mauvaises prédictions sur lesbranchements conditionnels� 10 % de mauvaises prédictions sur les conditionnels
77
Compteur 2 bits : mise en œuvre
� Première possibilité : rajouter un compteur 2 bits dans chaque entrée du BTB
� si un branchement est prédit pris mais qu’en réalité il est non pris, on décrémentele compteur et on laisse l’entrée dans le BTB
� Deuxième possibilité : stocker les compteurs 2 bits dans une table spécifique, la BHT(branch history table)� MIPS R10000, IBM Power3, PowerPC, AMD Athlon, HP PA-8500� pas de tags, juste 2 bits dans chaque entrée
• la BHT peut comporter plus d’entrées que le BTB• taille: 256 à 2k entrées
� quand le compteur passe de l’état 2 à l’état 1, l’entrée dans le BTB n’est plusnécessaire
� Autre avantage: plus important de prédire direction que la cible
78
BHT
poids forts poids faibles
BHT
2n compteurs2 bits
n bits
PC du branchementconditionnel
Le bit de poids fort ducompteur donne la prédiction
Interférences entre branchements:
2 branchements en conflit pourune même entrée.
79
Prédire les retours de fonction
� Utiliser une pile d’adresses de retour� pour chaque call exécuté, on empile l’adresse de retour� pour prédire un retour, au lieu d’utiliser l’adresse fournie par le BTB,
dépiler l’adresse au sommet de la pile et sauter à cette adresse� Peut être utilisé aussi pour prédire les retours d’interruptions et d’exceptions� Si pile suffisamment profonde, 100 % de bonnes prédictions
� UltraSparc-3 (8 entrées), AMD Athlon (12 entr.), Alpha 21264 (32 entr.)� ne pas abuser de la récursivité
� Principale « difficulté »: identifier les appels et les retours� utiliser le code-op (ex. appel = saut avec lien)� le compilateur peut aider le processeur
• exemple: hint (Alpha), jr $31 (MIPS) ...
80
Mauvaises prédictions: 10 % c’est trop
� Les processeurs actuels sont superscalaires� chaque étage du pipeline peut traiter plusieurs instructions
simultanément� Le pipeline d’instructions est long� Exemple
� 4 instructions par cycles• IPCidéal = 4
� 12 cycles de pénalité si branchement mal prédit• 1 conditionnel pour ~ 8 instructions, soit 80 instructions par
mauvaise prédiction• IPCmaxi = 80 / (80/4 + 12) = 2.5
� On sait faire mieux: la prédiction à 2 niveaux d’historique
81
Inter-corrélations
B1: SI cond1 ET cond2 …
B2: SI cond1 …
Supposons les 4 cas équiprobables.
La probabilité de bien prédire B2 en se basant sur soncomportement passé vaut 50 %
cond1 cond2 cond1 ET cond2
FFVV
FVFV
FFFV
Supposons maintenant qu’on connaisse le résultat de B1 au moment de prédire B2Si cond1 ET cond2 vrai (probabilité 1/4), prédire cond1 vrai 100 % de succèsSi cond1 ET cond2 faux (probabilité 3/4), prédire cond1 faux 66 % de succèsOn peut prédire B2 avec un taux de succès de 1/4 + 3/4 * 2/3 = 75 %
Remarque: si on permute B1 et B2, c’est moins bien ...
82
Auto-corrélation
for (i=0; i<100; i++)
for (j=0;j<4;j++)
: corps de la boucle
111011101110
Si les 3 dernières directions sontdes 1, prédire 0, sinon prédire 1
100 % de succès
83
Prédicteur à 2 niveaux d’historique
� Premier niveau d’historique� historique global pour détecter les inter-corrélations
• un seul registre à décalage de L bits contient les directions prises par les Lderniers branchements rencontrés
� historique local pour détecter les auto-corrélations• un registre à décalage de L bits pour chaque branchement• contient les L dernières directions prises par ce branchement• prédit bien les boucles faisant au plus L itérations
� Deuxième niveau d’historique� chaque branchement utilise plusieurs compteurs 2 bits, stockés dans une PHT
(pattern history table)� utiliser la valeur d’historique local ou global pour sélectionner le compteur dans la
PHT
84
Prédicteur à historique global
PC du branchement conditionnel
PHT
2n compteurs2 bits
histo L bits
n bits
xor
prédiction 0/1
Prédiction insérée dansl’historique pour prédirele branchement suivant
Appliquer une fonction dehachage entre l’adresse etl’historique (par ex. OUexclusif bit à bit)
85
Prédicteur à historique local
2m historiqueslocaux de L
bits
PHT
2n compteurs 2 bits
histo L bits
Prédiction 0/1
NB: temps d’accès pluslong (2 accès chaînés)
PC du branchement conditionnelm bits
86
Hors contraintes matérielles ...
� Les prédicteurs à deux niveaux permettent de diviser par 2-3 le nombre demauvaises prédictions� typique: 5 % de mauvaises prédictions
• voire moins sur les codes « flottants »� Historique global
� efficace sur les codes « entiers »� Historique local
� plus efficace sur les codes « flottants »• beaucoup de boucles, comportement régulier
87
En pratique ...
� Beaucoup d’interférences de conflits dans la PHT� « paradoxe » de l’anniversaire:
• soit une classe de 23 élèves, la probabilité d’avoir 2 élèves quifêtent leur anniversaire le même jour est de 50 %
� l’espace de la PHT est très mal utilisé
� Quelle longueur d’historique ?� sur les « grosses » applications, trop d’interférences de capacité,
on préfère un historique court (voire une BHT)� sur les « petites » applications, on préfère un historique long
� Historique local ou historique global ?� ça dépend de l’application
88
Prédicteurs hybrides : principe
Prédicteur 1
Prédicteur 2
Prédicteur N
Méta-prédicteur
PC dubranchement
••
•
Prédiction
Quelles étaient lesprédictions correctes ?
89
PHT 4kcompteurs
2 bits
Le prédicteur de l’Alpha 21264
1k historiqueslocaux de 10
bits
PHT 1kcompteurs 3
bits
Méta 4kcompteurs
2 bits
historiqueglobal 12 bits
PC du branchement
prédictiontotal: 29 Kbits
90
Exécution conditionnelle
saute à SUITE si (r1 >= r2)r4 = mem(a)r4 = r4 + 1mem(a) = r4SUITE:
r3 = r1 - r2r4 = mem(a)r5 = r4+1r4 = r5 si (r3<0)mem(a)=r4
r3 = r1 - r2p1 = (r3<0)r4 = mem(a) si p1r4 = r4+1 si p1mem(a)=r4 si p1
a = a + (((x - y)>>31)&1) ;
code initial, avec un branchement move conditionnel prédication
if (x<y) { a++;}
prédication sans supports ?
Attention au surcoût en instructions
91
Prédiction de branchement
� 1992: Alpha 21064, schéma à 1 bit� 1993: Pentium, schéma à 2 bits� 1995: PentiumPro, historique local� 1998: Alpha 21264, prédicteur hybride
� 2000: Pentium 4 secret !� Alpha 21464 (arrété en juin 2001):
� global, mixe 4 longueurs d ’historique� 352 Kbits au total
92
Prédiction de branchement:tendance générale
� Schémas de plus en plus complexes� Découplage de la prédiction de l'adresse et
de la direction� Pile de retour pour les procédures� Support dans les jeux d'instructions pour
l’exécution spéculative:�CMOV�prédicats de l ’IA64
93
Le parallélisme d’instructions
94
Toujours plus de puissance : les processeurssuperscalaires, VLIW et EPIC
� Processeurs RISC jusqu'en 1991 :� objectif 1 instruction par cycle
� mais comment aller plus vite :� Diviser le temps de cycle et multiplier les étages :
superpipeline� Lancer plusieurs instructions par cycle :
• qui contrôle:– Le matériel: superscalaire– Le compilateur: VLIW (Very Long Instruction Word)– Les 2: EPIC (Explicitly Parallel Instruction
Computing)
95
Les processeurs superscalaires
� le droit de lancer les instruction par cycle est géré à l'exécutionpar matériel:� aléas de ressource : e.g. partage d'une même unité fonctionnelle� aléas de données : ne pas lancer 2 opérations dépendantes� aléas de contrôle : attention aux branchements
� permet la compatibilité binaire d'une génération deprocesseurs à l'autre:� du processeur RISC (1 instruction par cycle) au processeur
superscalaire (x instructions par cycle)� TOUS LES PROCESSEURS (GENERAUX) ANNONCES
DEPUIS 1993 SONT SUPERSCALAIRES
On va en parler (beaucoup)
96
VLIW: Very Long Instruction Word
� Parallélisme contrôlé par logiciel:� Le compilateur est en charge de contrôler les unités
fonctionnelles:• gère les aléas de contrôle, de données et de ressources
� Problème: l’absence de compatibilité binaire
� Non utilisé pour les processeurs généraux, mais populairepour les calculateurs enfouis
97
Architecture VLIW (Very LongInstruction Word)
� Une unité de contrôle émet une instruction longue par cycle.
� Chaque instruction longue initialise simultanément plusieurs opérationsindépendantes:� le compilateur garantit que les instructions d ’une même instruction
longue sont indépendantes.� Ie compilateur garantit que les instructions lancées sont
indépendantes de toutes les instructions encore « en vol »� Il n’y a pas de matériel pour imposer le respect des dépendances
98
Architecture VLIW
UF
Unité decontrôle
UF UF UF inte
rfac
e m
émoi
reBanc de registres
igtr r6 r5 -> r127, uimm 2 -> r126, iadd r0 r6 -> r36, ld32d (16) r4 -> r33, nop;igtr r6 r5 -> r127, uimm 2 -> r126, iadd r0 r6 -> r36, ld32d (16) r4 -> r33, nop;
99
VLIW: format des instructions
� Le format des instructionscomporte un grand nombre de bitspour contrôler directement l'actiondes multiples unités fonctionnelles.
� Pb: trop de NOPs� Multiflow 27 UFs 1024 bits de
large
� Un groupe d’instructions RISC
� Plus d ’unités fonctionnellesque d ’instructions codées dansun mot VLIW
À l’origine Aujourd’hui
Les instructions sont, en général,compressées en mémoire, mais
expansées dans le cache instruction
100
Un exemple de de jeu d’instructions:Trimedia
� Les instructions:� 5 opérations par instruction� la plupart des opérations sont de la forme:
IF rc opcode op1 op2 -> op3
avec rc la garde, op1, op2 et op3les opérandes.Si rc contient « vrai » alors op3 est modifié.Les gardes s ’applique à l ’ensemble des opérations saufiimm et uimm (load de constante)
� 128 registres généraux de 32bits (r0==0, r1==1)
101
Gardes
� Intérêt : éliminer des branchements
if (x==3) y=y1+y2;if (x==3) y=y1+y2;
cmp r11,3bne suiteadd r2 r3 r4
suite:
cmp r11,3bne suiteadd r2 r3 r4
suite:
iseq r11 3 r10IF r10 add r2 r3 r4
iseq r11 3 r10IF r10 add r2 r3 r4
ALU
r2 r3r10
r4
?
102
« Slots » des instructions
� Les opérations ne peuvent être affectées indifféremment dansn’importe quels emplacements (slots) de l’instructions
� Un slot « contrôle » un sous ensemble des unités fonctionnellescapable d ’exécuter un sous ensemble des opérations del ’architecture
FU Type Slot 1 Slot 2 Slot 3 Slot 4 Slot 5CONST X X X X XALU X X X X XDMEM X XBR. X X X....
103
Ordonnancement statique
� latence d’une multiplication = 3 cycles
VLIW
add r1 r2 r9
nop
add r3 r4 r5
mul r6 r7 r3
RISC-CISC
add r1 r2 r9
add r3 r4 r5
mul r6 r7 r3
3 cycles
104
slot 1 slot 2 slot 3 slot 4 slot 51 add r1,r2,r3 add r5,1,r62 ld [r3],r4345 add r4,4,r4 jmp suite
Ordonnancement statique
add r1,r2,r3ld [r3],r4add r5,1,r6add r4,4,r4jmp suite...
add r1,r2,r3ld [r3],r4add r5,1,r6add r4,4,r4jmp suite...
Ordonnancement
ld [r3],r4
105
Et aussi les branchements « retardés »
� On n ’exécute les branchements qu ’au cycle EX du pipeline:� pas de contrôle = pas de prédiction de branchement� pas de contrôle = pas d ’annulation d ’instruction en cours
� Les slots entre le branchement et la connaissance de sonrésultat doivent être remplis avec des instructionsindépendantes du branchement: « branch delay slots »
Aussi utilisés dans les premiers ISA RISC (Sparc, MIPS)
106
Branchements retardés
� Sur le TM1000 le branch « delay slot » des branchements estde 3 cycles:
5 x 3 + 4 = 19 instructions à trouver !
b suiteadd r1,r2,r3…
suite:
b suiteadd r1,r2,r3…
suite:
add r1,r2,r3b suitenop...
suite:
add r1,r2,r3b suitenop...
suite:
107
VLIW: architecture pour lesapplications embarquées
� Pas de possibilités de compatibilité binaire d ’une génération àl ’autre
� Efficace sur les codes réguliers (boucle), peu efficace sur lesapplications general-purpose (trop de branchements)
� « Cost-effective »:� pas de contrôle:
• moins de surface de silicium• moins de consommation• temps de conception et mise au point réduit
108
Superscalaire : les problèmes
� Parallélisme d'instructions limité:� 3 à 8 instructions par cycle� Le fichier de registres:
• le nombre de ports augmentent : chemin critique
� La fourniture des instructions
� La gestion des dépendances de données
� Les branchements.
109
//isme d ’instruction et« general-purpose »
Les processeurs superscalaires
110
superscalaire « naturel » →→→→ 1995
� les unités fonctionnelles existantes dans les microprocesseursne sont pas dupliquées:� ALU� Unité flottante� Accès à la mémoire� Unité de séquencement
� → DEC 21064, IBM Power, Power601� Certaines unités fonctionnelles dupliquées :
� TI SuperSparc : 2 ALUs� MIPS R8000, IBM Power2 : 2 opérateurs flottants, 2 accès
au cache
111
Le degré superscalaire
� Difficile à définir:� « performance qu’on est certain de ne pas
dépasser »� 4 inst / cycles sur presque tous les processeurs
existants� 6 inst / cycles sur Itanium� 8 inst / cycles sur le (ex-futur) Alpha 21464:
� projet abandonné en juin 2001� 16 -32 en 2012 ? :=)
112
Exécution dans l’ordre ou dansle désordre
� Respecter l’ordre du programme ou non:� Ah! Si toutes les latences étaient connues
statiquement,…� Les « partisans » de l ’ordre:
� UltraSparc 3, Itanium� Le compilateur doit faire le travail
� Les « partisans » du désordre:� Alpha 21264, Pentium III et 4, Athlon, Power
(PC), HP-PA 8500
113
Pourquoi l’exécution dansl’ordre
� simple à mettre en œuvre� moins de transistors� moins de temps de développement� horloge rapide (discutable)
� pipeline moins profond� le compilateur « voit » tout:
� la micro-architecture� le programme
Même philosophie que VLIW
114
Le compilateur voit « tout »
� Au sein d’un bloc de base !� (bloc de base: suite d ’instructions non séparée par un
branchement ou une étiquette)� le compilateur est capable de réordonnancer les
instructions pour les lancer en //
� On peut appliquer des techniques logicielles pour dépasser lafrontière d’un bloc de base:� déroulage de boucle, pipeline logiciel, hyperbloc, ..
115
Pourquoi l’exécution dans ledésordre
� l ’ILP statique est limité dans les codes nonréguliers
� le compilateur ne « voit » pas tout:�latences inconnues à la compilation�(in)dépendances inconnues à la
compilation:• sur la mémoire
� pas besoin de recompiler�hum !!
116
Le compilateur ne « voit » pas tout
� Latences inconnues à la compilation:� accès à la mémoire: 1 ou 10 ou 100 cycles
� (In)dépendances mémoires:� Le compilateur ne peut prendre que des décisions
conservatrices
� « Perdu » après quelques branchements:� explosion combinatoire� explosion de la taille de code
117
Exécution dans le désordre (1)
� Principe :�exécuter les instructions dès que :
opérandes disponibles et unitésfonctionnelles disponibles
� Mise en œuvre :�une grande fenêtre d'instructions où on
choisit les instructions exécutables (80 surAlpha 21264, plus de 100 sur Pentium 4)
118
Exécution dans le désordre (2)
� Le séquencement consiste à :� Lire les instructions en //� Marquer les dépendances� Renommer les registres� Dispatcher vers les unités fonctionnelles� Attendre ..
� La gestion des dépendances prend de la place etdu temps : pipeline profond
119
Renommage de registres:ou comment enlever les fausses dépendances (1)
� Aléas WAW et WAR sur les registres peuvent être évitées parrenommage dynamique des registres.
120
Renommage de registres:ou comment enlever les fausses dépendances (2)
� Plus de registres physiques que de registres logiques dansl ’ISA
� Maintenir une liste de registres physiques disponibles
� Affecter un nouveau registre physique à chaque nouvelleécriture de registres
� Libérer les registres après leur dernière utilisation
121
Renommage de registres:ou comment enlever les fausses dépendances (3)
1:Op R6, R7 -> R52:Op R2, R5 -> R63:Op R6, R3 -> R44:Op R4, R6 -> R2
1:Op L6, L7 -> res12:Op L2, res1 -> res23:Op res2, L3 -> res34:Op res3,res2 -> res4
4 new free registers
+Old map table
1:Op P6, P7 -> RES12:Op P2, RES1 -> RES23:Op RES2, L3 -> RES34:Op RES3,RES2 -> RES4
New map table
122
Dépendances mémoires
� pour exécuter une écriture sur la mémoire, on abesoin de la donnée à écrire
� en dehors de toute information, toute lecturemémoire est potentiellement dépendante de touteécriture mémoire précédente
� solution (provisoire):� Calcul des adresses dans l'ordre du programme� Dépassement des écritures par les lectures avec
détection des aléas
123
Dépendances mémoires (2)
� Solution provisoire:� Exécution optimiste dans le désordre� Réparation si la dépendance existe� Pb: coût de la réparation
� Solution émergente: la prédiction de dépendancessur la mémoire� Moshovos et Sohi, Micro'30, décembre 1997� Chrysos et Emer, ISCA ’26, juin 1998
124
Et les interruptions ?
125
Les interruptions
� L ’exécution d ’un processus peut être interrompue par un événement externe(préemption du système, signal extérieur, ..) ou interne (traitement d ’uneexception).
� Mais le résultat du programme ne doit pas (en général ) dépendre dutraitement de l’interruption:� Le traitement d ’une interruption nécessite de pouvoir à tout instant être
capable de définir et sauver un état cohérent de la machine:• Program Counter• Registres• Mémoire
� Sur les processeurs exécutant dans l ’ordre, relativement simple mais sur lesprocesseurs exécutant dans le désordre !!
126
Exécution dans le désordre:Savoir « défaire »
� Mauvaise prédiction de branchement� Mauvaise anticipation d'indépendance� Interruption, exception
� Valider dans l’ordre du programme� Ne rien faire de définitif dans le désordre
127
Savoir « défaire »
� Une copie du fichier de registres est miseà jour dans l'ordre du programme
� ou� Une <<carte>> registres logiques-registres
physiques est sauvegardée
� Les écritures en mémoire sont faites à lavalidation
128
Organisation des unités fonctionnelles
129
Unités fonctionnelles centralisées:une fenêtre d’instruction unique
Register File
Functional Units X instructions choisies à l’exécution dans toute la fenêtre
Pb majeur: implémenter le choix X parmi N
130
Design en clusters: N fenêtresd ’instrustions
C0 C1 C3C2
Les instructions sont réparties entre les clustersdans les étages amont
+ Sélection des instructionssimplifiée
- équilibrage de charge
131
Semi-unifié: fenêtres d ’instructions partype d ’instructions
Ld/St ALU1 BRALU2
132
Petit retour sur le pipeline
133
Le pipeline: de plus en plusprofond
� Plus on stresse l'horloge, moins on en fait en uncycle.
� 1 cycle = traversée d’une ALU + rebouclage� Communications intra-CPU de + en + longues:
� plusieurs cycles pour traverser le composant� Le contrôle est de + en + complexe:
� plus d’instructions en //� plus de spéculation
134
Quelques profondeurs depipeline
� 12-14 cycles sur l’Intel Pentium III� 10-12 cycles sur l’AMD Athlon� 7-9 cycles sur l’Alpha 21264� 9 cycles sur l’UltraSparc
� 10 cycles sur l’Itanium (juin 2001)� 20 cycles sur le Pentium 4 (fin 2000)
� Et ça ne va pas s’améliorer !!
135
Retour au jeu d’instruction
136L ’IA64: un jeu d’instruction« general-purpose »pour le //isme d’instructions
� parallélisme explicite entre les instructions (à laVLIW)
� Support pour l’exécution spéculative
� Compatibilité assurée par le matériel
137
Le jeu d’instruction EPIC IA64(Explicitly Parallel Instruction Computing)
� EPIC IA64 =� RISC� + plus de registres (128 entiers, 128 flottants)� + 3 instructions codées en 128 bits� + 64 registres de prédicats� + dépendances gérées par le matériel� + (?) Advanced Loads
� officiellement le compilateur gère le parallélisme d’instructions,� mais la compatibilité est assurée par le matériel
138
IA 64
� L’angoisse de la page blanche !?� -Support matériel au pipeline logiciel
• Rotating registers: numéro logique de registre calculé ?• Gestion de boucle: compteurs spécialisés ?
� -Fenêtres de registres: à taille variable!� -Pas d’adressage basé� -adressage post-incrémenté� - (?) Advanced Loads
139
Intel PentiumPro (2, 3) ou comments’abstraire du jeu d’instruction
140
De la difficulté du superscalaire sur les jeuxd'instruction non réguliers
� Les difficultés liées au jeu d'instructions:
� Taille d'instructions variables (1 à 15 bytes)� Plusieurs occupations successives d'une même ressource� Nombre d'itérations inconnu sur certaines instructions� Temps d'exécution imprévisible pour certaines instructions
141
Intel PentiumPro: la solution adoptée
� Une constation :� les jeux d'instruction RISC sont plus simples à pipeliner et
exécuter en parallèle
� La solution :� exécuter du "code " RISC !
� Comment ?� Le décodage des instructions est remplacée par une
traduction en pseudo-code RISC
142
Intel PentiumPro
� MEM + REG → MEM:� 4 microoperations (RISC-like)
� La plupart des instructions sont traduites en 1 à 4microopérations en un cycle
� Certaines instructions ne peuvent pas être traduites en unnombre fixé de microopérations (boucles, instruction flottantestranscendantales , ..) :� traduites en plusieurs cycles
� 3 traducteurs en parallèles (1 complexe + 2 simples)
143
Intel PentiumPro
� Les microopérations venant de différentes instructions sontexecutées dans le désordre comme sur les processeurssuperscalaires out-of-order RISC�
� renommage de registres� stations de réservations ..� Buffer de réordonnancement� Jusqu'à 5 microopérations par cycle.
144
Pentium 4 et Trace cache: juste uncoup plus loin
� Pourquoi retraduire les instructions x86 à chaque nouvelleutilisation ?� Perte de temps� Consommation électrique
� Idée simple mais logique:� Mémoriser les µopérations dans un cache: le Trace Cache
145
Jeu d’instruction: est-ceimportant ?
� 32 ou 64 bits:�vers l’abandon (ou la mutation !) d’x86�AMD x86-64 !
� Les performances:�et x86 ? :=)�en flottant !!�à technologie égale ?
146
Jeu d’instruction: est-ceimportant (2) ?
� x86: traduction en µOpérations� 4 cycles perdus !� Ou utilisation d’un trace cache
• (on mémorise les µOpérations )� x86 pas assez de registres flottants� Alpha 21264: 2 opérandes 1 résultat
� le + performant des RISCs� Mort commerciale
� Itanium: l’IA 64 dans l’ordre� 800 Mhz en 0.18 µ� Alpha 21164 700 Mhz 0.35µ (1997)
147
Jeu d’instruction: est-ceimportant (3) ?
� Pour x86 NON:
transistor
micro-architecture
jeu d’instructions (ISA)
compilateur
langagelogiciel
matériel
Traduction en µµµµopérations
148
Jeu d’instruction: est-ceimportant (4) ?
� IA 64:� Bien pour le calcul régulier� Prochaines implémentations dans le désordre:
• Un grand mystère ?
� Les processeurs enfouis:� minimiser la couche de traduction� taille, consommation, coût de développement
149
Des erreurs qui ont coûté cher (1)
� L’absence d’accès mémoire octet ou 16 bits sur le jeu Alpha(1992)
� Résultait d ’une mauvaise analyse de l’utilisation des octets
Ecriture d un octet: 4 instructions1. Lecture du mot de 32 bits englobant2. Décalage de l’octet3. Merge de 2 mots de 32 bits4. Ecriture du mot de 32 bits
150
Des erreurs qui ont coûté cher (2)
� L’introduction du CMOV sur l ’Alpha 21164 (1994):� jolie idée pour un processeur exécutant dans l’ordre
� Seule instruction à 3 opérandes sur l ’Alpha 21264 (1998):
In-Order:If R1=0 then R3=R2Out-of-Order:If P1=0 then newP3= P2 else newP3=OldP3
151
Pourrait coûter cher:IA64 et l’exécution dans le désordre
� IA64 a été conçu pour l ’exécution dans l ’ordre etessentiellement pour le code régulier:� exécution conditionnelle de toutes les instructions� support spécial pour l’exécution des boucles� fenêtre de registres tournantes:
• le numéro logique du registre est calculé� instructions avec jusqu’à 5 opérandes et 4 résultats
152
La hiérarchie mémoire
153
La mémoire
� Plus une mémoire est grande, plus son temps d’accès est long� 3 types de mémoire
� banc de registres• peu d’entrées, temps d’accès court (cycle), plusieurs ports
� mémoire dynamique (DRAM)• mémorisation d’une charge sur une capacité, 1 transistor par bit• grande densité d’intégration (16-64 Mbits)• temps d’accès long: 50-100 ns• utilisé comme mémoire principale
� mémoire statique (SRAM)• mémorisation par bouclage de 2 portes: 1-4 Mbits• cher• temps d’accès court: 5-10 ns
154
Latence mémoire
� La latence mémoire n’est pas seulement constituée par letemps d’accès DRAM� traduction d’adresse� traverser les broches du processeur et le bus externe� multiplexage si plusieurs bancs mémoires
� Latence mémoire principale: 100-200 ns� à 1 GHz, ça fait 100 à 200 cycles CPU
� problème !!
155
Les caches
� La mémoire est:� bon marché et lente ou� chère et rapide.
� Les caches : donner l'illusion d'une mémoire globale rapide.
� Principe: utiliser les propriétés de localité temporelles etspatiales des applications
156
Principes de fonctionnement d'uncache
� Le cache est une petite mémoire rapide dont le contenu est uneimage d'un sous-ensemble de la mémoire.
� Lors d'une référence à la mémoire, la requête est:
� 1.) présentée au cache� 2.) si la donnée absente alors la requête est présentée à la
mémoire principale (ou à un second niveau de cache).
157
Cache: principe de mise en œuvre
lignes de cacheétiquette (tag) =identificateur de ligne
Load &A
Si l’adresse de la lignecontenant A se trouve dansla table des étiquettes, ladonnée est dans le cache
Espace mémoire
A
158
De l'importance de la hiérarchiemémoire
� Exemple :� 4 instructions/cycle,� 1 accès mémoire par cycle� 10 cycles de penalité sur le cache secondaire� 100 cycles pour la mémoire� 2% de défauts d'instructions L1, 4% de défauts données
L1, 1 référence sur 4 en défaut sur L2
� Pour exécuter 400 instructions : 520 cycles !!
159
Transferts mémoire-cache
� Le temps d ’accès à un bloc de K mots:� T = a + (K-1) b
� Le temps d'accès au premier mot est plus long:� envoi de l'adresse + retour� Structure des mémoires RAM dynamiques
� On n'attend pas la fin du transfert complet des mots avantd'utiliser un mot du bloc chargé:� le mot en défaut est en général chargé en premier
160
Placement des données dans lescaches
� Chaque bloc ne peut être chargé qu'à une seule place dans lecache: cache� DIRECT MAPPED ou à correspondance directe.
� Chaque bloc peut être chargé à n'importe quelle place dans lecache:� FULLY ASSOCIATIVE ou totalement associatif.
� Chaque bloc ne peut être chargé qu'à un nombre limité deplaces (ensemble ou SET):� SET ASSOCIATIVE ou associatif par ensembles.
161
Cache direct-mapped
162
Cache set-associatifs
163
Cache fully-associatifs
164
Remplacer un bloc
� Lorque l'ensemble est plein, quel bloc rejeter en mémoire ?� RANDOM: les candidats sont choisis de manière aléatoire� LRU: Least Recently Used
� Random:� plus simple à mettre en oeuvre
� LRU:� meilleur en général� effets bizarres
165
Ecrire
� Toute écriture doit être répercutée dans la mémoire:� Tout de suite: WRITE THROUGH� ou plus tard: WRITE BACK ( quand le bloc est évincé du
cache)� WRITE BACK:
� moins de trafic sur la mémoire� problème de cohérence entre la mémoire et le cache
� WRITE THROUGH:� trafic important vers la mémoire
166
Quelle taille de bloc ?
� Blocs longs:� bénéficie de la localité spatiale� réduit le nombre de blocs et perd de la place
� Blocs courts:� nombreux défauts sur des blocs contigus
� Expérimentalement :� 16 - 64 bytes pour les caches 8-32 Kbytes
167
Plusieurs niveaux de caches
� Une hiérarchie de caches:� des capacités de plus en plus grandes� des temps d'accès de plus en plus longs.
� L2 devenu la règle générale:� sur le composant ou sur le même module que le processeur� temps d ’accès: 7-15 cycles
168
Plusieurs niveaux de cache (2):memoire - processeur - L2
169
Plusieurs niveaux de cache (3):memoire - L2 - processeur
170
Problème d’inclusion
� doit-on assurer que toute donnée présente dans le cache depremier niveau est aussi présente dans le cache de secondniveau?� Mémoire - processeur - L2 : non
• L ’architecture des années 90� Mémoire - L2 - processeur : oui
• Aujourd’hui généralisé: le processeur ne voit pas lestransactions sur le bus.
171
Un défaut de cache n’arrête pas(complètement) le processeur
� Cache non-bloquant:� en présence d’un défaut on envoie la requête vers le niveau
suivant et on continue !
� Préchargement:� on anticipe les prochaines requêtes (par matériel ou par
logiciel)
172
Quelques paramêtres
� Intel Pentium : 2 * 8K bytes, 2-way, 60 (1993)-233 Mhz (1997)� MIPS R4400 : 16K Inst + 16K data, DM, 100 (1992) 250 Mhz (1996)� Alpha 21164 : 2* 8K (DM) + L2 96 Kbytes (3-way) 266 (1995) Mhz
700 Mhz (1998)� Intel Pentium III: 2* 16K, 4-way, 1 Ghz (2000)+ L2 256-512K-1M� Alpha 21264 : 2 * 64 Kbytes (2-way), 500 Mhz (1997) 1 Ghz (2001)
� Amd Athlon: 2*64K, 2-way, 1,4 Ghz (2001) + 256K L2� Intel Pentium 4: 8K + trace cache + 256K L2, 2 Ghz (2001)
� Intel Itanium: 2 * 16K + 96 K L2 (+ 1-4M L3), 800 Mhz (2001)
173
Caches primaires:tendance générale
� 1-2 cycles pour lecture ou écriture� multiples accès par cycle� non-bloquant� associatif faible degré
� Restera petit !� Une exception: HP-PA 8500
174
Caches secondaires : tendancegénérale
� Il n’est plus question de s’en passer !� Généralisation on-chip ou sur le module� Accès pipeliné
� latence courte : 7-12 cycles� bus 128 bits, devrait s’élargir� temps de cycle: 1-3 cycles processeurs
� La contention sur le cache L2 devient un goulotd’étranglement
175
Mémoire virtuelle
� L ’adresse virtuelle est calculée par le programme. Cette adresse est traduite àtravers une table de pages en adressse physique� permet de faire cohabiter plusieurs processus� permet de « voir » un espace d’adressage plus grand que celui par la
mémoire physique� convertir les adresses logiques en adresses physiques
� en général, combinaison de techniques matérielles et logicielles� l’unité de mémoire sur laquelle on travaille = page mémoire� mécanisme de pagination
• les pages qu’on ne peut pas stocker en DRAM sont stockées surdisque
• on utilise une table des pages pour faire la translation page logique /physique
• pour accéder à une page qui se trouve sur disque, on la recopie enDRAM et on met à jour la table des pages
176
Pagination
� Tailles de page typiques: 4 Ko-8Ko-64Ko� Table des pages indexée avec le numéro de page logique -> fournit un numéro
de page physique� La table des pages est stockée en DRAM, dans une zone ne nécessitant pas
de translation� exemple: espace logique sur 32 bits, pages 4 Ko (12 bits d’offset), soit 220
pages logiques� Si on devait consulter la table des pages pour chaque accès mémoire, le temps
de traductions serait dominant� On utilise un TLB (translation look-aside buffer)
� TLB = cache de traduction d’adresses intégré sur le processeur� contient un sous-ensemble de la table des pages� typique: 64/128 entrées, fully-associative
177
TLB
Exemple: adresses logiques 32 bits, pages de 4 Ko, TLB 64 entrées
numéro de page logique offset page12 bits20 bits
64 numéros depages physiques +
qq bits de statut
64 tags =numéros de page
logique
adresselogique
numéro de page physique offset pageadressephysique
12 bits
TLB
178
Défauts de TLB
� Gestion par matériel (x86) ou logiciel (SparcV9, Alpha, MIPS)� Logiciel: sur un défaut de TLB, une exception est générée� Matériel: déroule un automate
� Servir un défaut de TLB:� le système consulte la table des pages� si la page est présente en mémoire, le système met le TLB à jour
puis rend la main au programme• latence: quelques dizaines à quelques centaines de cycles
� si la page n’est pas présente c’est un défaut de page• latence: centaines de milliers de cycles (accès disque)
179
Mémoire virtuelle et caches
� adresses virtuelles ou physiques pour l ’accès au cache?� Adresse virtuelle
• pb des synonymes sur les pages accessibles en écriture– des pages virtuelles distinctes projetées sur la même
page physique– plusieurs copies de la même donnée dans le cache
� Adresse physique• accès au TLB avant d’accès au cache ..
� Souvent:• cache L1 données: adresse virtuelle /tag physique• cache L1 instructions: tag physique• cache L2: adresse physique / tag physique
180
Index virtuel / tags physiques
� Permet l’accès au cache et au TLB en //� lecture du cache avec l’adresse virtuelle� l’accès TLB se fait en parallèle avec l’indexage du cache� la comparaison sur les tags s’effectue avec l’adresse physique
� Chemin critique:� L ’accès au TLB
• besoin de l ’adresse physique pour la comparaison des tags
181
Adresse physique / Tag physique
� Une petite astuce pour faire la traduction en //:� utiliser l ’offset comme index !
182
La mémoire principale
� Loin, trop loin du processeur:� 100-150 ns de temps d ’accès� plusieurs centaines d’instructions
� Temps d ’accès:� défaut L1 + logique vers L2� défaut L2 + logique vers le bus mémoire� bus mémoire� composant mémoire� et retour
183
la mémoire principale sur lebus système
184
Mémoire principale et débit.
� Problème de débit aussi:� Largeur du bus: 8-16 bytes� Structures des composants mémoires:
• accès séquentiel plus rapide qu ’accès aléatoire� Débit des composants mémoires:
• Entrelacement des bancs (mais plus de logique àtraverser)
� Fréquence du bus:• Seulement une fraction du cycle processeur
185
Mémoire principale en connexiondirecte
186
Mémoire principale en connexiondirecte (2)
� Connexion directe:� pas d ’arbitrage� bus courts: fréquences élevées (jusqu à 800
MHz)� utilisation de composants mémoire spécialisés
(Rambus)
� Mais difficile d ’implémenter la cohérence de caches
187
Un processeur récent: l ’Alpha 21264
(bien documenté par le constructeur !)
188
l’Alpha 21264
� COMPAQ / DEC� Disponible depuis fin 1998
� Quelques caractéristiques technologiques� transistors : 15 Millions (6 M logique, 9 M caches)� fréquence : 700 MHz (0.25 micron) -> 1 Ghz (0.18 micron)� puissance dissipée : 75 W (2 V)
� Marché visé� stations de travail, serveurs
189
21264: caractéristiques générales
� adresses logiques sur 64 bits� pipeline de 7 étages pour les instructions de calcul entier� processeur superscalaire out-of-order de degré 4� cache de données 64 Ko 2-way SA write-back (ligne 64 octets)� cache d’instructions 64 Ko 2-way SA (ligne 64 octet)� TLB données et TLB instructions de 128 entrées chacun� bus cache secondaire 128 bits� bus système 64 bits� 4 ALUs et 2 unités flottantes
� 2 des ALUs peuvent calculer les adresses load/store, et 2 load/store peuvent accéderau cache par cycle
� au maximum 6 instructions peuvent s’exécuter simultanément (4 int + 2 flottantes)
190
21264: disposition sur silicium
cache d’instructionset prédicteur de
ligne
cache dedonnées
D-TLB (dupliqué)contrôlecache
donnéesgén.PCpréd br
div/sqrt
fp add
reg fp
fp mulfp map interface
L2
tamponload/store
I-TLB
tamponamorç
fp
ALU
ALU
ALU
ALU
ROB
tamponamorç
int
int map
regint
regint
bus load/store
191
Le pipeline du 21264
charg. extrait renom. lance lit reg exec écrit int
lit reg adresse cache 1 cache 2
lit reg FP 1 FP 2 FP 3 FP 4
PC répare
écrit int
écrit fp
pénalité mini si branch mal prédit: 7 cycles
attente éventuelle
calculentier
load/store
calculflottant
lectureligne
extrait bloc/ transit
insert dansfenêtre
1 2 3 4 5 6 7
5 6 7 8 9
5 6 7 8 9 10
load-use: +2 cycleson peutlancer ?
écrit fp
10transit
load-use: +3 cycles
192
21264: prédiction et chargement
� Étage 0: prédiction de ligne� chaque ligne du cache d’instructions comporte un pointeur vers la prochaine ligne de cache (index et
prédiction de banc 0/1) (accès < 1 cycle)� on commence la prédiction de branchement
• rem: prédicteur hybride pour les conditionnels (cf. transparent 115)� Étage 1: chargement et génération PC
� on charge la ligne prédite à l’étage précédent et les 2 tags ayant le même index que la ligne (cache2-way SA)
� la prédiction de branchement commencée au cycle précédent est utilisée pour générer le PC(complet) du bloc en cours de chargement
� comparaison d’index: si désaccord entre étages 0 et 1, c’est le prédicteur de branchement qui« gagne »: on recharge la ligne (bulle dans le pipeline)
• sauf pour les sauts indirect qui ne sont pas des retours� Étage 2: comparaison du PC avec les 2 tags chargés à l’étage précédent
� 2 bulles si mauvaise prédiction de banc� détection éventuelle d’un cache miss
193
21264: prédiction et chargement
Cache 2-waySA
préd.ligne
génération PC
compare index
bloc d’instructions
tags bancs0 et 1
prédhyb
préd. ligne tags
compare tags
PC
Bloc BBloc A
préd. br.
Bloc CÉtage 0Étage 1Étage 2
194
Clusters du 21264
80 registresphysiques (int)
ALU 1 ALU 2
80 registresphysiques (int)
ALU 3 ALU 4
+1 cycle
195
21264: tampons d’adresses
� En fait, séparé en 2 tampons: un tampon de load et un tampon de store de 32entrées chacun
� Les instructions dans chaque tampon sont ordonnées� on associe à tout load/store une entrée dans le tampon d’adresses
correspondant
� Le tampon de store comporte également les données à écrire� les store peuvent s’exécuter OOO mais écrivent dans le tampon de store� les données du tampon sont recopiées dans le cache au retirement, dans
l ’ordre séquentiel
� L ‘ ordre total des load/store est maintenu par matériel entre les deux tampons
196
21264: exécuter les load sans attendre
� Les load peuvent s’exécuter dans le désordre vis à vis des store
� Quand un load accède au cache, on consulte en // le tampon de store� si un store plus ancien a écrit à la même adresse, c’est la donnée dans le
tampon de store qui est mise sur le bus et qui est envoyée au load
� Si un store s’exécute et qu’on trouve qu’un load plus récent a déjà accédé à lamême adresse, le load et les instructions suivantes sont effacées du processeurpuis rechargées� comme une mauvaise prédiction de branchement: on essaie d’éviter� une table de 1k * 1 bits, indexée avec le PC du load, permet de prédire si le
load dépend d’un store ou pas� si on prédit qu’il sera dépendant, on attend que tous les store antérieurs au
load soient exécutés
197
21264: défauts de cache
� 8 défauts de cache de données peuvent être en cours de résolution� Les requêtes peuvent être servies dans le désordre� Sur un miss, la ligne remplacée (si modifiée depuis qu’elle est dans le
cache) est mise dans un tampon de 8 lignes en attente d’écriture versle cache L2
� miss L1 / hit L2:� latence minimum de résolution = 12 cycles (SRAM 6 cycles + 4
cycles de remplissage + 2 cycles pour l ’instruction)� bande passante bus: 16 octets pour 1.5 cycles CPU
� miss L2� latence typique: 160 ns (DRAM 60 ns)
• 96 cycles CPU à 600 MHz� bande passante bus système: 8 octets pour 1.5 cycles CPU
198
Le monoprocesseur à usage général
Synthèse pour aujourd’hui et problèmes pour demain
199
Les tendances (1)
� plus d'instructions par cycle ?� au delà d'un bloc de base par cycle ?� 4 en 1990, 6 en 2001� pas beaucoup de changement en apparence
� mais exécution dans le désordre:� de plus en plus de prédictions de branchement et
spéculation sur l ’indépendance des accès mémoires� pipeline de séquencement très long:
� de moins en moins de fonctionalités par cycle� temps de transit proportionnellement + grand� pénalité de mauvaise prédiction de branchement ?
200
Les tendances (2)
� Caches premier niveau multiport, non-bloquants, accédés en 1-2 cycles:� compromis temps d ’accès, taille, associativité
� Cache second niveau pipeliné non-bloquant :� latence 10-15 cycles� débit 16-32 octets par cycle
� Vers les mémoires en connexion directe
201
Doubler le degré: pas si simple !
� Problème de performance:� juste pas assez d ’instructions indépendantes� prédicteurs de branchement pas assez précis
� suivant les sources:• 20-50 % de performances en plus
� Problème de mise en œuvre:� ce n ’est pas simplement dupliquer les unités fonctionnelles
202
Doubler le degré superscalaire (2)
� Unités fonctionnelles� Surface de silicium: 2x
� consommation: 2x
� même latence
� Registres :� Surface de silicium : 8x� consommation: 3-4x� accès plus long
� Cache L1:� 2 fois plus de ports� pb sur surface,
consommation et tempsd’accès
� Réseau de bypass:� multiplexeurs plus larges
>2x� communications plus
lointaines
203
Le problème des registres
� Besoin d’un registre physique par instruction « en vol »� plus de 100 instructions en vol sur le Pentium 4� 80 sur l ’Alpha 21264
� Besoin de plus de registres physiques quand degrésuperscalaire augmente:� > 256 si degré 8 et pipeline profond
� Organisé en fichier de registres:� physiquement toutes les unités fonctionnelles y lisent leur(s)
opérande(s) et écrivent leur(s) résultat(s)
204
La surface du fichier de registres
205
Fichier de registres distribué4 copies identiques32 Watt (x 3.2)5 cycles (+1)256 x 960 w2 x W (x10)
Fichier de registres centralisé40 Watt (x 4)7 cycles (+3)256 x 768 w2 x W (x 8)
Centralisé 4 voies
10 Watt
4 cycles
128 x 192 w2 x W
Degré 8 contre degré 4100nm, 5 Ghz ( 2003-2004)
8 voies
206
Et demain ?
207
Que faire avec un milliard detransistors ou plus?
� monoprocesseur + exécution spéculative
� Le parallélisme de processus:�multiprocesseur à mémoire partagée�processeur SMT
208
Un monoprocesseur +exécution spéculative
� superscalaire 16 ou 32 voies� hyperspéculation:
� branchements, dépendances, données ..
� Les défis:� la qualité de la prédiction� les temps de communication sur le composant� la contention sur les structures:
• caches , registres, ...
209
Le //isme de processus:à la croisée des chemins
� Le parallélisme « gros grain » arrive sur lecomposant
� Un multiprocesseur on-chip ?• IBM Power 4 ( fin 2001)
� Simultaneous Multithreading ?• Compaq Alpha 21464
– Abandonné en juin 2001• Pentium 4 est SMT
210
Un multiprocesseur on-chip
� Mettre un multiprocesseur sur un mêmecomposant:�Réplication simple�Partage de cache L2 et de l ’accès
mémoire
� Mais la performance sur un processus ?
211
multiprocesseur on-chip:IBM Power 4 (2001)
� Marché visé: les serveurs
� 2 processeurs superscalaire 4 voies sur uncomposant:� cache secondaire partagé
� 4 composants sur un même MCM (multichip module)� bande passante énorme sur le MCM
212
La vision du programmeur
213
Simultaneous Multithreading(SMT)
� Les UFs d’un processeur superscalairessont sous-utilisées
� SMT:� Partager les UFs d’un processeur superscalaire
entre plusieurs processus� Avantages:
� 1 processus a toutes les ressources s ’il est seul� partage dynamique des structures (caches,
prédicteurs, UFs) quand plusieurs processus
214
SMT: Alpha 21464(annulé en juin 2001)
� Un processeur superscalaire 8 voies� Performance ultime sur un processus
� Si multiprocessus, 4 processus se partagentles unités fonctionnelles:�Surcoût pour ce partage 5-10 %
215
La vision du programmeur
216
Le SMT: les avantages
� Partage dynamique des ressources
� Tolérance à la latence mémoire
� Thread d ’un même programme:� communication ultra-rapide:
• données partagées dans le cache L1 !� Préchargement implicite:
• données, mais aussi instructions et prédiction
217
SMT: la difficulté
Il faut implémenter un processeur superscalaire très large
218
Le processeur de l ’an 2010 ?
� Jeu d'instruction x86+ ?�extension pour mode 64 bits
� (Multi ?) Superscalaire 10 voies SMT
� Exécution dans le désordre très aggressive
219
La vision du programmeur !
220
Les grandes questions
� Saura-t-on maitriser la complexitédu design?�Temps de mise au point�consommation électrique
� Qui saura programmer cesmonstres ?
