Upload
benjamin-vidal
View
77
Download
3
Embed Size (px)
DESCRIPTION
Soutenance de stage de DEA - sujet de recherche : Evaluation de la quantité de travail (in)utile dans l’exécution des programmes
Citation preview
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