Evaluation de la quantité de travail (in)utile dans l’exécution des programmes

Soutenance de stage de DEASoutenance de stage de DEA

Évaluation de la quantité de travail utile dansÉvaluation de la quantité de travail utile dansl’exécution des programmesl’exécution des programmes

Stage encadré par P. MichaudStage encadré par P. Michaud

et effectué par B. Vidalet effectué par B. Vidal

Projet CAPSProjet CAPS

DéfinitionDéfinition

• Une instruction dynamique est utile siUne instruction dynamique est utile si

- Elle produit un résultat émis en sortieElle produit un résultat émis en sortie

- Elle produit un résultat utilisé comme opérande Elle produit un résultat utilisé comme opérande d’une instruction utiled’une instruction utile

- C’est un branchementC’est un branchement

2

3

BibliographieBibliographie

• Différentes définitions du travail inutileDifférentes définitions du travail inutile

- Valeurs mortes dynamiquesValeurs mortes dynamiques G. Sohi & A. ButtG. Sohi & A. Butt

ASPLOS X - oct. 2002ASPLOS X - oct. 2002

- Écritures silencieusesÉcritures silencieuses M. Lipasti, K. Lepak & G. BellM. Lipasti, K. Lepak & G. Bell

IEEE, vol. 50, No. 11 - nov. 2001IEEE, vol. 50, No. 11 - nov. 2001

- Évaluation de l’ensemble du travail inutile Évaluation de l’ensemble du travail inutile après exécutionaprès exécution

La méthode utilisée [1]La méthode utilisée [1]

• Exemple simpleExemple simple

3

La méthode utilisée [1]La méthode utilisée [1]

• Exemple simpleExemple simple

3

La méthode utilisée [1]La méthode utilisée [1]

• Exemple simpleExemple simple

3

La méthode utilisée [1]La méthode utilisée [1]

• Exemple simpleExemple simple

3

La méthode utilisée [1]La méthode utilisée [1]

• Exemple simpleExemple simple

3

La méthode utilisée [1]La méthode utilisée [1]

• Exemple simpleExemple simple

3

La méthode utilisée [1]La méthode utilisée [1]

• Exemple simpleExemple simple

3

La méthode utilisée [1]La méthode utilisée [1]

• Exemple simpleExemple simple

3

La méthode utilisée [1]La méthode utilisée [1]

• Exemple simpleExemple simple

3

La méthode utilisée [2]La méthode utilisée [2]

• Graphe de dépendance de donnéeGraphe de dépendance de donnée

- Construction au cours de l’exécutionConstruction au cours de l’exécution

- Relier les instructions dépendantesRelier les instructions dépendantes RegistresRegistres MémoireMémoire

• Parcours du grapheParcours du graphe

- Sources (sorties ou branchements)Sources (sorties ou branchements)

- Marquage des instructions utilesMarquage des instructions utiles

4

OptimisationOptimisation

• Réduction du grapheRéduction du graphe

- Suppression des nœuds certifiés utilesSuppression des nœuds certifiés utiles A mesure que le programme se dérouleA mesure que le programme se déroule Un nœud utile ne peut devenir inutileUn nœud utile ne peut devenir inutile

- Suppression des nœuds certifiés inutilesSuppression des nœuds certifiés inutiles Une instruction n’est accessible depuis aucune Une instruction n’est accessible depuis aucune

ressourceressource Système de ramasse-mietteSystème de ramasse-miette

5

OptimisationOptimisation

5

OptimisationOptimisation

• Réduction du grapheRéduction du graphe

- Suppression des nœuds certifiés utilesSuppression des nœuds certifiés utiles A mesure que le programme se dérouleA mesure que le programme se déroule Un nœud utile ne peut devenir inutileUn nœud utile ne peut devenir inutile

- Suppression des nœuds certifiés inutilesSuppression des nœuds certifiés inutiles Une instruction n’est accessible depuis aucune Une instruction n’est accessible depuis aucune

ressourceressource Système de ramasse-mietteSystème de ramasse-miette

5

Mise en œuvreMise en œuvre

• SaltoSalto

- Récupérer des informations statiquesRécupérer des informations statiques

- Instrumenter du code assembleurInstrumenter du code assembleur Insérer des instructionsInsérer des instructions

• Au cours de l’exécutionAu cours de l’exécution

- Récupérer des informations dynamiquesRécupérer des informations dynamiques Ordre d’exécutionOrdre d’exécution Adresses des accès à la mémoireAdresses des accès à la mémoire État du systèmeÉtat du système

6

Instrumentation [1]Instrumentation [1]

• Exemple simpleExemple simple

7

Instrumentation [1]Instrumentation [1]

• Exemple simpleExemple simple

7

Instrumentation [1]Instrumentation [1]

• Exemple simpleExemple simple

7

Instrumentation [1]Instrumentation [1]

• Exemple simpleExemple simple

7

Instrumentation [1]Instrumentation [1]

• Exemple simpleExemple simple

7

Instrumentation [2]Instrumentation [2]

• Différentes phasesDifférentes phases

- Sauvegarde du contexteSauvegarde du contexte

- Création de la structure de donnéeCréation de la structure de donnée

- Traitement des opérandesTraitement des opérandes

- Traitement des résultatsTraitement des résultats

- Parcours du graphe si nécessaireParcours du graphe si nécessaire

- Restauration du contexteRestauration du contexte

8

VérificationVérification

• Ré-exécution du même programme avec Ré-exécution du même programme avec les mêmes données en entréeles mêmes données en entrée

- Saut des instructions inutilesSaut des instructions inutiles

• Vérification que les deux exécutions sont Vérification que les deux exécutions sont équivalenteséquivalentes

9

RésultatsRésultats

• Tests effectués sur GZIP et GUNZIPTests effectués sur GZIP et GUNZIP

- Sans optimisation de compilationSans optimisation de compilation Entre 1 et 11 % de travail inutile en moyenneEntre 1 et 11 % de travail inutile en moyenne

- Avec optimisations de compilationAvec optimisations de compilation Entre 10 et 12 % de travail inutile en moyenneEntre 10 et 12 % de travail inutile en moyenne

- Dépend du type de traitementDépend du type de traitement CompressionCompression DécompressionDécompression

- Dépend du fichier traitéDépend du fichier traité

10

Analyse [1]Analyse [1]

11

GZIP sur un fichier texte de 2 KoSans optimisation de compilation

Nombre d’instructions dynamiques

No

mb

re d

’in

stru

ctio

ns

inu

tile

s

Analyse [2]Analyse [2]

• Phase d’initialisationPhase d’initialisation ≈ ≈ 50 % de travail inutile50 % de travail inutile

• Cœur de l’algorithme de compressionCœur de l’algorithme de compression

- Sans optimisation de compilationSans optimisation de compilation ≈ ≈ 7 % de travail inutile7 % de travail inutile

- Avec optimisations de compilationAvec optimisations de compilation ≈ ≈ 10 % de travail inutile10 % de travail inutile

12

Analyse [3]Analyse [3]

• Exemple d’initialisationExemple d’initialisation

prev_match = match_start;. . .

if (prev_length>=MIN_MATCH && match_length<=prev_length) {

check_match(strstart-1, prev_match, prev_length); . . .

}

Affectation inutile dans 95 % des casAffectation inutile dans 95 % des cas

13

Analyse [4]Analyse [4]

• Au cœur de l’algorithmeAu cœur de l’algorithme

- « Dictionnaire »« Dictionnaire »

- Insertion d’un nouvel élément (chaîne)Insertion d’un nouvel élément (chaîne)

- Recherche de redondanceRecherche de redondance

- Comparaison progressiveComparaison progressive Lazy evaluation mechanismLazy evaluation mechanism

- Insertion d’éléments n’apparaissant qu’une foisInsertion d’éléments n’apparaissant qu’une fois Travail inutileTravail inutile

14

ConclusionConclusion

• Quantifier le travail inutileQuantifier le travail inutile

- Proportion non négligeable dans GZIPProportion non négligeable dans GZIP

• Comprendre d’où il provientComprendre d’où il provient

- AlgorithmeAlgorithme Inhérent à l’algorithmeInhérent à l’algorithme Du à une implémentation « naïve »Du à une implémentation « naïve »

- CompilationCompilation

• Éviter ce travailÉviter ce travail

- Outil d’aide au programmeurOutil d’aide au programmeur

15