Optimisation dynamique logicielle des accès aux données par prédiction de Markov sur les pas en mémoire et préchargement. Implantation dans le compilateur

Optimisation dynamique logicielle des Optimisation dynamique logicielle des accèsaccès

aux données par prédiction de Markov sur aux données par prédiction de Markov sur les pas en mémoire et préchargement. les pas en mémoire et préchargement.

Implantation dans le compilateur Open64.Implantation dans le compilateur Open64.

Jean Christophe BeylerJean Christophe BeylerICPS/LSIIT Université de Louis Pasteur ICPS/LSIIT Université de Louis Pasteur

de Strasbourgde Strasbourg16/12/200416/12/2004

PlanPlan

PrésentationPrésentation Système dynamiqueSystème dynamique Modèle MarkovienModèle Markovien

Exemple d’implémentationExemple d’implémentation Création du modèleCréation du modèle Résultats expérimentauxRésultats expérimentaux Open64Open64 ConclusionConclusion

PrésentationPrésentation

Optimisation Optimisation statique:statique: Lors de la compilationLors de la compilation

Limitations des Limitations des optimisations statiquesoptimisations statiques

Paramètres inconnus lors Paramètres inconnus lors de la compilationde la compilation

Les défauts de cacheLes défauts de cache Techniques de Techniques de

préchargement simplespréchargement simples

PrésentationPrésentation Utilisation d’un Utilisation d’un

système dynamique:système dynamique: Exécution Exécution

d’optimisation d’optimisation pendant l’exécutionpendant l’exécution Solution matérielle :Solution matérielle :

Permet de repérer les Permet de repérer les défauts de cachedéfauts de cache

Plus rapide mais il y a Plus rapide mais il y a un coût en matérielun coût en matériel

Solution logicielle :Solution logicielle : PortablePortable ModelableModelable Plus lentPlus lent

Historique de systèmes Historique de systèmes logicielslogiciels

DynamoDynamo (Hewlett Packard) en 2000 (Duesterwald (Hewlett Packard) en 2000 (Duesterwald etet al.al.):): Optimise des portions du codeOptimise des portions du code TransparentTransparent

DeliDeli (Hewlett Packard) en 2002 (Duesterwald (Hewlett Packard) en 2002 (Duesterwald etet al.al.):): Optimise des portions du codeOptimise des portions du code 2 versions: Transparente et API2 versions: Transparente et API

Un autre optimiseur en 2002 (Chilimbi et Hirzel) : Un autre optimiseur en 2002 (Chilimbi et Hirzel) : Optimisation des accès mémoireOptimisation des accès mémoire Autonome et puissant mais que sous Autonome et puissant mais que sous WindowsWindows

Adore Adore en 2003en 2003 (Lu (Lu etet alal.):.): Optimisation des accès mémoire : insertions de Optimisation des accès mémoire : insertions de lfetch lfetch

(Itanium)(Itanium) Limité au cas des bouclesLimité au cas des boucles

Modèle MarkovienModèle Markovien

Analyse statistique d’une suite Analyse statistique d’une suite SS d’éléments d’éléments (des accès mémoire dans notre cas) (des accès mémoire dans notre cas)

Mise sous forme de couples Mise sous forme de couples (X,Y)(X,Y) où: où: XX et et YY sont des éléments de la suite sont des éléments de la suite XX précède précède YY

Mais aussi Mais aussi (S’,Y)(S’,Y) où: où: S’S’ est une sous suite de est une sous suite de SS Tous les éléments de Tous les éléments de S’S’ précèdent précèdent YY

Système dynamique Système dynamique logiciellogiciel

Propriétés générales :Propriétés générales : S’exécute en même temps que le programme cibleS’exécute en même temps que le programme cible PortablePortable Relativement légerRelativement léger Facile à utiliserFacile à utiliser

Propriétés spécifiques à ESODYP (Propriétés spécifiques à ESODYP (An Entirely An Entirely Software and Dynamic Data PrefetcherSoftware and Dynamic Data Prefetcher) :) : Modélise les comportements mémoiresModélise les comportements mémoires

En étudiant les sauts mémoires effectuésEn étudiant les sauts mémoires effectués Précharge les données dans le cachePrécharge les données dans le cache

Déroulement de notre Déroulement de notre modèlemodèle

1)1) Le programme cible envoie les Le programme cible envoie les accès mémoire au modèleaccès mémoire au modèle

2)2) Deux possibilités :Deux possibilités :1)1) Il modélise le comportement des accès Il modélise le comportement des accès

mémoires reçus mémoires reçus (phase de (phase de construction)construction)

2)2) Il exploite les données afin de prédire Il exploite les données afin de prédire et précharger les futurs accès et précharger les futurs accès (phase (phase de prédiction)de prédiction)

Structures de donnéesStructures de données

Le programme peut posséder plusieurs accès Le programme peut posséder plusieurs accès coûteuxcoûteux

Chaque séquence est probablement unique:Chaque séquence est probablement unique: Paramètres différents utilisés par le modèleParamètres différents utilisés par le modèle Réactions différentes du modèle par Réactions différentes du modèle par

rapport aux séquencesrapport aux séquences

Chaque séquence aura une structure de Chaque séquence aura une structure de données associéedonnées associée

Exemple concretExemple concret

TreeaddTreeadd du banc d’essai du banc d’essai OldenOlden

Création et parcours d’un arbre binaire Création et parcours d’un arbre binaire par la gauchepar la gauche

Modification du codeModification du code Plus de 90% du temps se déroule dans la Plus de 90% du temps se déroule dans la

fonction fonction TreeaddTreeadd Dans cet exemple, un accès nous Dans cet exemple, un accès nous

intéresse donc une seule structure est intéresse donc une seule structure est nécessairenécessaire

InitialisationInitialisation

Durée de constructionDurée de construction ProfondeurProfondeur DistanceDistance Erreurs maximumErreurs maximum

Code de la fonction Code de la fonction TreeaddTreeadd

int TreeAdd (t)int TreeAdd (t)register tree_t *t;register tree_t *t;{ { ... ...

tleft = t->left; tleft = t->left; t : donnée t : donnée intéressante àintéressante à

leftval = TreeAdd(tleft); leftval = TreeAdd(tleft); préchargerpréchargertright = t->right;tright = t->right;rightval = TreeAdd(tright);rightval = TreeAdd(tright);value = t->val;value = t->val;return leftval + rightval + value;return leftval + rightval + value;}}

Code de la fonction Code de la fonction TreeaddTreeadd

int TreeAdd (t)int TreeAdd (t)register tree_t *t;register tree_t *t; m1: structure de donnéesm1: structure de données{ { associéeassociée... ... #ifdef __MARKOV__#ifdef __MARKOV__ fct : pointeur de fonction,fct : pointeur de fonction,

m1->fct(m1,t);m1->fct(m1,t); permet de passer permet de passer l’informationl’information

#endif#endiftleft = t->left;tleft = t->left; t : donnée intéressante àt : donnée intéressante àleftval = TreeAdd(tleft);leftval = TreeAdd(tleft); préchargerpréchargertright = t->right;tright = t->right;rightval = TreeAdd(tright);rightval = TreeAdd(tright);value = t->val;value = t->val;return leftval + rightval + value;return leftval + rightval + value;}}

La fonction La fonction fctfctint TreeAdd (t)int TreeAdd (t)

register tree_t *t;register tree_t *t;{ { ... ... #ifdef __MARKOV__#ifdef __MARKOV__

m1->fct(m1,t);m1->fct(m1,t);#endif#endiftleft = t->left;tleft = t->left;leftval = TreeAdd(tleft);leftval = TreeAdd(tleft);

tright = t->right;tright = t->right;rightval = TreeAdd(tright);rightval = TreeAdd(tright);value = t->val;value = t->val;return leftval + rightval + return leftval + rightval +

value;value;}}

Pointeur de fonction Pointeur de fonction permet de permet de :: passer de la phase de passer de la phase de

construction à la phase de construction à la phase de prédictionprédiction

ParamètresParamètres1.1. Structure Structure m1m1 permettant permettant

de modifier de modifier fct fct et les et les autres donnéesautres données

2.2. La donnée qui est un La donnée qui est un élément de la séquence à élément de la séquence à étudierétudier

Chaque séquence possède Chaque séquence possède sa propre structuresa propre structure Paramètres différentsParamètres différents Phase différentePhase différente

RemarquesRemarques La plupart des optimiseurs :La plupart des optimiseurs :

S’intéressent aux adresses accédées :S’intéressent aux adresses accédées : Un programme accédant trop d’adresses distinctes Un programme accédant trop d’adresses distinctes

n’est pas parfaitement modélisablen’est pas parfaitement modélisable

Notre modèle :Notre modèle : S’intéresse aux sauts effectués :S’intéresse aux sauts effectués :

Permet de simplifier le modèle dans le cas de Permet de simplifier le modèle dans le cas de programmes ayant un comportement mémoire « programmes ayant un comportement mémoire « suffisamment constant »suffisamment constant »

Préchargement de plusieurs sauts en avance :Préchargement de plusieurs sauts en avance : Permettre au chargement de se finirPermettre au chargement de se finir Danger d’écrasement de donnéesDanger d’écrasement de données

Type de modèleType de modèle

Suite Suite récupérée récupérée : 1: 1 2 16 2 32 2 16 2 2 16 2 32 2 16 2 3232

Modèle statistique mais sous forme:Modèle statistique mais sous forme: De tableau?De tableau? De graphe?De graphe?

Un tableauUn tableau

11 2 16 2 32 2 16 2 322 16 2 32 2 16 2 32

11 22

22 16,3216,32

1616 22

3232 22

• Profondeur : 1

• Incertitude sur une des prédictions

Un tableauUn tableau

11 2 16 2 32 2 16 2 322 16 2 32 2 16 2 32

1,21,2 1616

2,162,16 22

16,216,2 3232

2,322,32 22

32,232,2 1616

• Profondeur : 2

• Prédiction plus fine

•Inconvénients avec des tableaux :

• Problèmes d’allocation

• Temps de recherche d’une suite

Création du grapheCréation du graphe

11 2 16 2 32 2 16 2 322 16 2 32 2 16 2 32

1

1

2

2

11

2

21


11 2 16 2 32 2 16 2 322 16 2 32 2 16 2 32

2

2 16

116

1


11 2 16 2 32 2 16 2 322 16 2 32 2 16 2 32

1

11

2

2

16

16

1

1

2

2

21

11

1

16

16

1

212

2

1

16

161


11 2 16 2 32 2 16 2 322 16 2 32 2 16 2 32

1

1

1

212

2

1

16

161


11 2 16 2 32 2 16 2 322 16 2 32 2 16 2 32

1 16

16

1

1

1

32

32

1

1

22

2

1

1

32

32

1

1

2

2

2

1

1

22

2

1

1

32

32

1

1


11 2 16 2 32 2 16 2 322 16 2 32 2 16 2 32

1 16

16 2

1

1

1

1 2

1

1

2 32

32

1

11

2

1

1

2 32

32

1

1

1


11 2 16 2 32 2 16 2 322 16 2 32 2 16 2 32

1 16

16 2

1

1

1

1

1

2

1

1

2 32

32

1

1

1

16

16

2

2

2

2

1

1

32

32

1

1

1

16

16

2

1

21

1


11 2 16 2 32 2 16 2 322 16 2 32 2 16 2 32

1

1

11

1

2

1

2

216

2

16

2

2

2

2 2

1

1

2 32

32

1

1

1

16

16

2

2


11 2 16 2 32 2 16 2 322 16 2 32 2 16 2 32

1

1

12

32 2

2

2

2

2

2 32

Début des prédictionsDébut des prédictions Temps de construction assez lourdTemps de construction assez lourd

Arrêt de la constructionArrêt de la construction Utilisation du modèle tant qu’il est efficaceUtilisation du modèle tant qu’il est efficace

Représente bien le comportementReprésente bien le comportement

Un programme possède plusieurs phases :Un programme possède plusieurs phases : Graphe spécifique à la phaseGraphe spécifique à la phase Reconstruction lorsque le nombre d’erreurs Reconstruction lorsque le nombre d’erreurs

consécutives est trop importanteconsécutives est trop importante

Equilibre entre trop de constructions et Equilibre entre trop de constructions et trop d’erreurstrop d’erreurs

2

232

1

2

1

2

2

232

2

2

1

1

3232

2

2

2

Phase de prédictionPhase de prédiction

2 16 1 48 2 162 16 1 48 2 16

2

16

16

2

1

1

12

2

Erreurs consécutives:

0

216

22

2232

2

2

1

216

1

2

2

2

32


2 16 1 48 2 162 16 1 48 2 16

2

16

2

1

1

12

2

32


0

2

32

16 2

2

232

2

2

2

2

2

32


2 16 1 48 2 162 16 1 48 2 16

2

16

2

1

1

12

2

32


0

2

1

16

1

1

1

1

16 2

2

232

2

2

2

2

2

32


2 16 1 48 2 162 16 1 48 2 16

2

16

21

12

2

32


2

1

2

1

1

2

1

1 16 2

2

232

2

2

2

2

2

32


2 16 1 48 2 162 16 1 48 2 16

2

16

21

12

2

32


2

2

2

3

2

1

1 16 2

2

232

2

2

2 2

32


2 16 1 48 2 162 16 1 48 2 16

2

16

1

12

2

32


2

3

2

0

2

2

216

Résultats sur Résultats sur Itanium-2Itanium-2

• treeadd : distance est importante

• ks : profondeur 2 est meilleure

• equake : distance trop grande peut faire baisser l’accélération

• mcf : meilleure optimisation

Résultats sur Résultats sur AMD Athlon AMD Athlon XP 2600+XP 2600+

•Raisons pour les différences:

• prefetch: instruction différente

• Différentes taille de lignes de cache:

• Itanium-2 : L2-D 128 octets

• Athlon XP 2600+: L2-D 64 octets

• Vitesse de programme

Remarques sur le Remarques sur le modélemodéle

Le modèle est:Le modèle est: PortablePortable RéalisteRéaliste Pas encore autonome et transparentPas encore autonome et transparent

Quatre critères à choisir:Quatre critères à choisir: Durée de constructionDurée de construction ProfondeurProfondeur Distance de préchargementsDistance de préchargements Erreurs maximum avant reconstructionErreurs maximum avant reconstruction

Il faut trouver les accès Il faut trouver les accès à la mainà la main

TransparenceTransparence Utilisation du compilateur Open64Utilisation du compilateur Open64

Compilateur Compilateur Open-Source Open-Source pour l’pour l’ItaniumItanium d’ d’IntelIntel Compile le C, C++ et le Fortran 90/95Compile le C, C++ et le Fortran 90/95

Permet d’implémenter un profileurPermet d’implémenter un profileur Première exécution pour déterminer les Première exécution pour déterminer les

accès intéressants accès intéressants Aide à choisir les accès intéressantsAide à choisir les accès intéressants Laisse juste la distance de préchargement à Laisse juste la distance de préchargement à

déterminerdéterminer

Open64Open64

back end(be, as)

linker(ld)

WHIRL(.B/.I)

obj(.o)

a.out/.so

Data Path Fork and Exec

driver(sgicc/sgif90/sgiCC)

front end + IPA(gfec/gfecc/mfef90)

Src(.c/.C/.f)

WHIRL: Winning Hierarchical Intermediate Representation Language

Open64Open64

Lower to High W.

gfec

gfecc

f90

LocalIPA

MainIPA

LNO

Inliner

WHIRL C

WHIRL fortran

Mainopt

Lowerall

lower I/O

LowerMid W

CG

.B

.I

-O3

.w2c.c

-IPA

.w2c.h

.w2f.f

-O0

-O2/O3

-phase: w=off

Very high WHIRL

High WHIRL

Mid WHIRL

Low WHIRL

Take either path

(only for f90)

La modification de La modification de Open64Open64

Modification de l’arbre syntaxiqueModification de l’arbre syntaxique Lors d’un chargementLors d’un chargement

Appel d’une fonction externe pour étudier le Appel d’une fonction externe pour étudier le comportement mémoirecomportement mémoire

Utilisant plusieurs paramètres différentsUtilisant plusieurs paramètres différents

Modification du code sourceModification du code source Ajout de deux appels: Ajout de deux appels: create_Markov_manager, create_Markov_manager,

stop_Markov_managerstop_Markov_manager Permet d’initialiser la mémoirePermet d’initialiser la mémoire Permet d’afficher les résultatsPermet d’afficher les résultats

Arbre syntaxiqueArbre syntaxique

Instructions précédentes

Prochaines instructions

Load A

Registre R = A

m->fct(m,R)

Load R

Avantage de Open64:

• Simple à mettre en œuvre

• API riche

Remarques:

• Version simplifiée

• Cas du if, boucle…

Et ensuite…Et ensuite…

On classe les résultats, conservant On classe les résultats, conservant ceux ayant les meilleurs résultats.ceux ayant les meilleurs résultats. Problème de:Problème de:

ClassementClassement SélectionSélection

Ces derniers seront insérés par le Ces derniers seront insérés par le compilateur pour permettre compilateur pour permettre d’obtenir des accélérations.d’obtenir des accélérations.

ConclusionsConclusions

L’utilisation de Open64 permetL’utilisation de Open64 permet De choisir les accès De choisir les accès potentielspotentiels et de et de

déterminer la profondeur de création, de déterminer la profondeur de création, de construction…construction…

Donc rendre transparent le modèleDonc rendre transparent le modèle Par contre, la distance de préchargement vis-Par contre, la distance de préchargement vis-

à-vis du temps est difficilement discernable.à-vis du temps est difficilement discernable. Perspectives:Perspectives:

Rendre le modèle plus efficaceRendre le modèle plus efficace Rendre le modèle de sélection plus Rendre le modèle de sélection plus intelligentintelligent

Documents

Optimisation dynamique logicielle des accès aux données par prédiction de Markov sur les pas en mémoire et préchargement. Implantation dans le compilateur