ARPO - IRISAARPO Architectures des processeurs superscalaires, VLIW et optimisations 2 L’interface...

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 ?