View
115
Download
3
Category
Preview:
Citation preview
Analyse et Optimisation de code
Principes générauxProcesseur Alpha – Tru64 Unix
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Optimisation séquentielle
Méthodologie proposée
Principes généraux
Optimisation du compilateur
Timing and profiling
Quelques méthodes d’optimisation “manuelle”
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Méthodologie conseillée
Validité du programme à optimiser
Utiliser des codes déja optimisés ou s’y ramener
Utiliser des algorithmes performants
Analyser le code, et se concentrer sur les sections critiques
Utiliser les capacités d’optimiser du compilateur
Effectuer des modifications dans le code pour optimiser les sections critiques
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Principes Généraux
Architecture des processeurs– Augmenter le vitesse d’horloge des processeurs– Techniques de micro-architecture permettant
d’augmenter le nombre d’instructions par cycleMémoire– Mémoire hiérarchique (registre, cache,…)– Mémoire virtuelle et Paging– Optimisation des accès
Quelques techniques d’optimisation
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Architecture des processeursFréquence d’horloge
La fréquence de l’horloge détermine la durée d’un cycle
Chaque opération utilise un certain nombre de cycles
La fréquence d’horloge détermine les performances
La fréquence d’horloge est fonction de :– La technologie des semi-conducteurs– Le packaging– Les circuits– …
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Comment faire des processeurs plus rapides?
Augmenter la fréquence d’horloge (limites techniques, solution coûteuse)Permettre l’exécution simultanée de plusieurs instructions – Exécution en parallèle (duplication de composants
hardware, coûteux)– Pipelining (pas de duplication de composants
hardware)
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Architecture HPC
Processeur RISC– Instruction pipelining– Branchement reporté– Load/Store Architecture– …
Seconde génération de processeur RISC– Processeur superscalaire (pipes en parallèle)– Processeur « superpipelined » (profondeur des pipes)– Processeur LIW (parallélisme d’instructions logiciel)
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Architecture Alpha 21264
Architecture RISC– Software Pipelining– Mémoire Hiérarchique (registre, caches,mémoire principale)– Système de prédiction de branchement– Prefetching
Architecture Super-Scalaire – Modification de l’ordre de l’exécution des instructions– Exécution spéculative– …
Optimisation du parallélisme d’instructions
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Exécution spéculative
Exemple:LD R10,R2(R0) charger dans R10 à partir de la mémoire… 30 instructions de type différents(pas de FDIV)FDIV R4,R5,R6 R4=R5/R6R5 et R6 sont déjà dans les registres pour d’autres instructions
et FDIV est inutilisée Le calcul par FDIV peut commencer, le résultat sera placé
dans un espace temporaire Le calcul de R4 se fera sur un cycle, temps de récupération
du résultat
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Alpha 21264 Architecture
Super-s– 4 chargement d’instruction par cycle– 6 instructions par cycle
• 4 instructions entières• 2 instructions en virgule flottante
– 1 unité non bloquante “Load/Store”– 4 unités fonctionnelles entières 64 bits– 1 unité fonctionnelle addition virgule flottante 32/64 bits– 1 unité fonctionnelle multiplication virgule flottante 32/64 bits– unité fonctionnelle SQRT en virgule lottante– (prefetch: charge les données dans le cache avant leur utilisation– déplacement conditionnel remplace les branchements à l’intérieur des boucles
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Software Pipelining
Parallélisme d’instructions• Une opération s’exécute en plusieurs étapes
indépendantes par des éléments différents du processeur• Le pipelining consiste à exécuter simultanément des
étapes différentes d’ opérations différentes
Exemple: opération s’effectuant en 5 opérations
Charge l’instruction
Charge lesopérandes
ExécuteDécode Ecriture
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Software Pipelining (suite)
3 instructions simultanées dans le pipe
Décode Chargeopérandes Exécute Ecriture
Charge l’instruction Décode
Charge l’instruction
Charge l’instruction
EcritureExécuteChargeopérandes
ExécuteChargeopérandesDécode Ecriture
3 instructions en parallèle en 7 cycles (15 cycles en séquentiel
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Software Pipelining (suite)
Sans pipelining – résultat tous les deux cycles– pour un processeur 195Mhz:
97Mflops
Avec pipelining– Après l’initialisation du pipe: 1
résultat par cycle– pour un processeur 195Nhz:
195Mflops
En général, l’unrolling des boucles améliore le parallélisme d’instructions
do i=1,1000000t(i)=t(i)*t(I)
enddo
do i=1,1000000,2t(i)=t(i)*t(i)t(i+1)=t(i+1)*t(i+1)
enddo
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Pipelining: accès mémoire
L’accès mémoire est une fonction coûteuse en temps qui prend plusieurs cycles.
Utiliser le procédé de pipelining pour le superposer à d’autres fonctions du processeur
L’optimisation du compilateur peut réordonner les instructions pour favoriser ce procédé
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Accès Mémoire
Mémoire hiérarchique – Registres– Caches– Mémoire Virtuelle
Organisation des caches
Optimisation des accès mémoire
Outils d’analyse identifiant les problèmes de cache
Quelques exemples
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Mémoire hiérarchique (DS20-EV6)
Registres • Le processeur utilise uniquement les données dans les registres• Temps d’accès: 2ns
Deux niveaux de caches (sur certaines machines 3 niveaux)– Cache primaire (L1)
• Accès par bloc (ligne de cache): 32 bytes • Taille: 64KB• Temps d’accès: 2 à 3 cycles
– Cache secondaire (L2)• Accès par bloc : 128 bytes • Taille: 4MB• Temps d’accès : 10 à 15 cycles
Mémoire principale (DS20: taille 2.5GB/proc, latence: 220ns )
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Organisation des caches
Le cache est divisée en lignes de cache de n motsDirect-Mapped Cache– Chaque adresse mémoire est associée à une ligne de cache
Fully Associative Cache– Chaque adresse correspond à n’importe quelle ligne de
cacheN-way set-associative Cache (2-way et 4-Way)– Une adresse a une alternative de N lignes de cache
Instruction Cache
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Cache
Localité temporaire et spatiale des donnéesCache Hit– Fournit la donnée demandée à partir du cache
Cache miss– Récupère la donnée dans la mémoire principale– La stocke dans le cache– Fournit la donnée demandée à partir du cache
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Cache thrashing
parameter (max=1024*1024) dimension a(max),b(max),c(max),d(max) …… do i=1,max a(i)=b(i) + c(i)*d(i) enndo
Difficultés– les vecteurs sont alloués de façon contigue– Chaque vecteur à une taille de 4MB (taille du cache secondaire)
Deux méthodes pour corriger ce problème– redimensionner les vecteurs– introduire des variables entre les tableaux pour décaler les adresses
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Mémoire Virtuelle
Dernière couche de la hiérarchie mémoireRegistresCache L1…Cache LNMémoire principaleSWAP – disque
Chaque programme utilise un espace d’adressage logique en correspondance avec l’adressage physique pour l’accès aux données
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Pourquoi la mémoire virtuelle
Allocation mémoire – Espace mémoire divisé en pages pas forcément contigues– Simplifie l’allocation mémoire associé à un process
Code relocation– Map des adresses logiques identiques à chaque run
Pagination– Transfert des pages de la mémoire principale au disque en
fonction de l’utilisation – Disque dernier niveau de la hiérarchie mémoire (swap)
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Mémoire Virtuelle : Page
Les transferts de la mémoire virtuelle à la mémoire physique se font par pages
données
ProcessRegion Table
PageTable
Virtual Translation
Physical Address
Virtual addressLocation 1000
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
TLB (Translation Lookaside Buffer)
TLB : Cache contenant les informations nécessaires aux translations adresse virtuelle – adresse physiqueRéduit le coût des références mémoire
Taille du TLB limitéTLB misses: L’adresse n’est pas dans le TLB– Chercher l'information dans une page en mémoire– La page contenant la donnée est sur disque, générer
une nouvelle page en mémoire
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Page Faults
Scénario générant un page fault– Il n'existe pas de table concernant la page– La page a été restockée sur disque
Chaque programme génére des "page fault"Beaucoup de "page fauts"– Mémoire partagée par plusieurs process– Mémoire requise supérieure à la mémoire réelle disponible
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Techniques d’optimisation
Analyse interprocédurale InliningAccès mémoire– Réutilisation du cache
• Stride minimum• Copie• …
– Réduction des TLB missesOptimisation de boucles
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Analyse Interprocédurale
Par défaut: analyse du compilateur sur une seule procédure à la fois.Inconvénients: manque d’information
• pour analyser les dépendances,• pour mettre en évidence les constantes• mettre en évidence les variables jamais utilisées• traitement des variables à la frontière des procédures
OPTIMISATION CONSERVATIVE
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Analyse Interprocédurale (IPA)
Analyse plusieurs procédures simultanémentRenvoie la plupart des actions du compilateur juste avant l’édition de lienscompilations: 2 phases– phase sommaire : récupère les informations locales utilisées
ultérieurement par l’IPA– création de WHIRL objets dans “*.o” (fe)
Edition de liens– IPA: analyse et transforme les WHIRL objets– back-end du compilateur: crée les “relocatables objects”– édition de liens
Facile à mettre en œuvre: -pipeline ou –O5 (compilation)
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
source source
.o (whirl) .o (whirl)
.l .l
.o .o
IPA et Optimisation inter procédurale
Edition de Liens
Compilation: édition de liens:
fe fe
be be
...
...
...
...
a.out
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Analyse Interprocédurale(suite)
Intérets: permet des optimisations supplémentaires
– Software Pipelining,– Optimisation des boucles imbriquées,– Inlining,– réduction des conflits de cache(padding,…)– élimination des fonctions jamais utilisées– détection des noms globaux– …
Inconvénients:– augmente le temps global compilation/édition de liens– augmente la taille de l’exécutable – peut modifier sensiblement les résultats
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Inlining
Remplace l’appel d’une procédure par le code de cette procédureIntérets:– élimine l’overhead dû à l’appel (sauvegarde des registres, appel,
instructions de retour, …)– fournit un contexte plus large pour l’optimisation scalaire et de boucles.
Inconvénients:– Augmente le temps de compilation– Crée des problèmes d’allocation de registres plus complexes – augmente la taille du code
Critères d’Inlining:– fréquence des appels– taille de la procédure appelée
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Optimisation des accès mémoire
Stride– Fortran: stockage par colonne
Parcourt d’un tableau 2D par l’index le plus à gauche– C : stockage par ligne
Parcourt d’un tableau 2D par l’index le plus à droite
Regroupement de donnéesOptimisation par copieOptimisation des boucles
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Réutilisation du cache: stride
Stride égal à 1 (Fortran)do i=1,n
do j=1,na(i,j)=b(i,j)
enddoenddo
do j=1,ndo i=1,n
a(i,j)=b(i,j)enddo
enddo
sera modifié
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Réutilisation du cache (suite)
Regrouper les données utilisées dans une même section de coded=0do i,1,n j=index(i) d=d+sqrt(x(j)*x(j) + y(j)*y(j) + z(j)*z(j)enddo
d=0do i,1,n j=index(i) d=d+sqrt(r(1,j)*r(1,j) + r(2,j)*r(2,j) + r(3,j)*r(3,j)enddo
x,y et z seront regroupés dans un même tableau r
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Optimisation du cache par copie
Copie d ’une partie des données dans un tableau temporaire– taille du tableau < 64*taille_page– suffisamment petit: réutilisation des données du cache– ne peut être pris en charge par le compilateur
Performances: – diminue les " TLB misses »– " L1 et L2 misses " peuvent rester importants– Overhead du à la copie
Préférer le " Cache Blocking " lorque c ’est possible
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Recouvrement des latences d’accès aux données
Par le système pour les faibles latences: caches primaires et secondaires
data prefetch• pas intégrée aux langages C et Fortran• insérée automatiquement par le compilateur • Manuellement par le programmeur à l’aide d’une directive
pour certains compilateurs
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Optimisationde boucles
UnrollingBoucles imbriquéesLoop interchangeRéférences mémoireBlockingOut-OF-Score
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Loop Unrolling
Diminue l’overhead dû à la gestion des bouclesFavorise le parallélisme du processeurMais nécessite une boucle de préconditionnementLes boucles candidates à l’unrolling sont:– Un nombre « raisonnable » d’instructions à chaque itération
• Petit: overhead de la boucle de préconditionnement, sauf si le nombre d’itérations est constant
– Nombre d’instructions par itération important: augmente la taille du code et des accès mémoire
– Pas d’appel de procédures– Condition de branchement possible dans le cas de processeur
superscalaire (exécution conditionnel)– Boucle externe de boucles imbriquées dans certains cas
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Boucles imbriquées
Unrolling : Boucle interne et/ou boucle externe ?
– stride => favoriser la réutilisation des caches– Taille des boucles => favoriser les boucles à grand
nombre d'itérations – Traitement des boucles non récursives => augmente
le taux de parallélisme:
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Loop Interchange
Centrer l’activité sur les boucles les plus internes
Minimiser le stride
Nécessite une analyse de dépendance– Par l’utilisateur– Par le compilateur
Parallélisation automatique– Paralléliser sur la boucle externe – Unrolling sur la boucle interne
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Loop Interchange?
DO I=1,NDO J=1,N
A(J,I)=B(I,J)ENDDO
ENDDO
DO J=1,NDO I=1,N
A(J,I)=B(I,J)ENDDO
ENDDO
L’inversion des boucles ne résoud pas les problèmes d’accès
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Cache Blocking
Principes: minimiser les transferts – utiliser entièrement la ligne de cache– réutiliser au maximun les données dans le cache– minimiser le nombre de références différentes à des pages physiques (TLB
misses)
Méthode– découper les données en blocs tenant dans le cache – ajouter des boucles extérieures qui contrôlent la taille des blocs
Cas de la multiplication de grandes matrices:– 2 matrices découpées en blocs colonnes– 1 matrice en bloc ligne
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Cache Blocking
Exemple: multiplication de deux matricesdo j=1,n do i=1,m do k=1,p c(i,j)=c(i,j)+a(i,k)*b(k,j) enddo enddo enddo
m n p lda ldb ldc Scs MFLOPS----------------------------------------------------------------------------------------- 30 30 30 30 30 30 0.000162 333.9 200 200 200 200 200 200 0.056613 282.61000 1000 1000 1000 1000 1000 25.4311 78.6
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Multiplication de matrices
=
Accès:Bloc C : 1foisBloc A : nb colonnes de CBloc B : nb lignes de A
C A
B
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Fusionner les boucles
dimension a(n), b(n)do i=1,n a(i)=a(i)+alpha*b(i)enddodot=0.do i=1,n dot=dot+a(i)*a(i)enddo
dimension a(n), b(n)dot=0.do i=1,n a(i)=a(i)+alpha*b(i) dot=dot+a(i)*a(i)enddo
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Les pointeurs
Excellent outil pour construire et manipuler toute sorte de structure de données (listes, arbres,…)
MAIS
Inhibe certaines optimisations du compilateur par manque d’information.
==> Optimisation conservative
POURTANT
L’utilisation de structures de données appropriées peuvent améliorer les performances de certaines applications
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Méthodologie conseillée
Validité du programme à optimiser
Utiliser des codes déja optimisés ou s’y ramener
Utiliser des algorithmes performants
Analyser le code, et se concentrer sur les sections critiques
Utiliser les capacités d’optimiser du compilateur
Effectuer des modifications dans le code pour optimiser les sections critiques
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Utiliser des codes déja optimisés
Libfastm:
CXML (Compaq Extended Math Library) et CXMLP (version parallèle SMP)• versions optimisées des BLAS1, 2 et 3 (Basic Linear Algebra) • FFT 1,2 et 3-D • lapack (système linéaire et valeurs propres)• solveurs de systèmes creux• 2 versions:
– Une version séquentielle : libcxml.a– Une version parallèle de type SMP : lincxmlp.a
FFTWATLAS
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Algorithmes Performants
Les Mflops est un mauvais indice de performance d’un codeDeux algorithmes de multiplications de matrices– Même Mflops– Temps CPU très différents
En priorité à l’optimisation d’un code, s’assurer de la performance des algorithmes utilisés
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Mesures de performance
Mesure globale du temps et autres statistiquescommande UNIX "time"
Mesure du temps d'une partie de code
Fonctions explicites (C et Fortran) de mesure de temps
Analyse complète de performance du code
Outils de profiling: prof, gprof, pixie, …
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Mesure globale du temps
Time (commande de base UNIX) : time <commande>• Temps utilisateur, temps système, elapsed time• CPU time = Temps utilisateur + temps système
Propriétés• Résolution de l'ordre de 10ms• Un "system_time" disproportionné peut indiquer un disfonctionnement
– Nombre important de floatig-point exceptions– Nombre important de "page faults" ou de "misaligned memory access"
…• CPU time < elapsed time
– Partage de la machine– Grand nombre d'I/O– Largeur de bande requise > largeur de bande de la machine– Pagination et/ou swap important …
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Fonction TIME (CSH ou TCSH)
%time program14.9u 1.4s 0:19 83% 4+1060K 27+86io 47pf+0w
Temps utilisateur du processTemps system pris par le processElapsed timePourcentage d'utilisation
Quantité moyenne de mémoire partagée (Kb)Quantité moyenne de mémoire réelle non-partagée utilisée
Nombre de blocs en entrée
Nommbre de blocs en sortie
Fautes de pages
Nombre de swaps
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Fonctions explicites de mesure de temps
Appel explicite de sous-programmes à l'intérieur du code
Fonction system_clock()
Procédures de la norme Fortran90/95 (~10ms)– cpu_time()
– date_and_time()
Fonction etime (non standard): temps système, utilisateur et total
Hors standard : fonctions constructeurs
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Fonctions explicites de mesure de temps
Procédure system_clockreal :: timeInteger :: debut, fin, vitessecall system_clock(count=debut,count_rate=rate)…call system_clock(count=fin)time=float(fin-debut)/rate
Fonction etimereal :: actual, etime, tarray(2)actual=etime(tarray)Avec tarray(1) : temps utilisateur tarray(2) : temps du system etime : temps total
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Fonction dans la norme Fortran90/95
Procédure cpu_timereal :: time_debut, time_fincall cpu_time(time_debut)…call cpu_time(time_fin)Print*, "temps = ", time_fin – time_debut, " secondes"
Procédure date_and_time :integer :: date_time(8)character (len=12) :: real_clock(3)call date_and_time(real_clock(1), real_clock(2), real_clock(3),&
date_time)Voir "Fortran Language Reference Manual"
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Outils de profiling
Deux types de profiling :– PC Sampling :
• Prof : CPU-TIME• Gprof : CPU-TIME associé à un graphe des appels• Hiprof : CPU-TIME, graphe des appels, défaut de page,..;
– Basic-Bloc Counting : prof, pixie
Utilisation des Compteur Hardware : – uprofile et kprofile
Profiling Mémoire VirtuelleOptions de compilation de base pour le profiling: -g1 –O2
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Trois étapes pour le profiling
Instrumentation du programme – Par le compilateur: -p, –pg– Par le profiler : hiprof, pixie
Exécution du programme instrumentéFichier de données pour le profiler (mon.out,gmon.out,…)
Utilisation du profiler pour l'extraction et la lecture des résultats: prof, gprof, hiprof, pixie
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Hiprof (Tru64 Unix)
Permet l'utilisation de fréquence d'échantillonnage plus petite et le profiling au niveau de la ligne.Les librairies partagées peuvent être analyséesProfiling individuel des threads possibleIndépendant des ressources hardware et de l'architectureGénére une perte de performanceNe se retrouve pas sur tous les systèmes UNIX
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
PC-Sampling ( prof, gprof,hiprof)
Cpu_time profiling : option –p et profiler prof% f90 –g1 –O2 –p –o prog prog.f% prog => création du fichier mon.out% prof prog mon.out > prof.list (sortie par défaut à l'écran)
Cpu-time profiling + graphe des appels– Compilateur : option –pg et profiler gprof
% f90 –g1 –O2 -pg –o prog prog.f% prog => création du fichier gmon.out% prof prog gmon.out > prof.list (sortie par défaut à l'écran)
– profiler hiprof (pas d'option particulière): • Compiler le programme : f90 –g1 –O2 –o prog prog.f• Instrumentation du programme: hiprof prog => prog.hiprof• Exécution : ./prog.hiprof ou hiprof –run <options> prog• Affichage des résultats : hiprof –run –display <options> prog
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Listing: PC-Sampling
Each sample covers 8.00 byte(s) for 4% of 0.0244 seconds
%time seconds cum % cum sec procedure (file)
80.0 0.0195 80.0 0.02 square_ (matpower.f)
20.0 0.0049 100.0 0.02 square_mult_ (matpower.f)
%time : pourcentage de temps passé dans la routineseconds : temps en secondes passé dans la routinecum % : pourcentage de temps cumulécum sec : temps cumulé en secondes
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Basic-Bloc Counting (pixie,prof)
Compilation : f90 –g1 –O2 –o prog prog.fInstrumentation: pixie <options> prog
• Programme instrumenté: prog.pixie• Fichier d'adresses des blocs: prog.Addrs
Exécution: prog.pixie• Crée le fichier compteurs de blocs: prog.Counts
Extrait et affiche l'information de profiling• prof –pixie prog >prog_pixie.list
Réduire les informations fournies• -exclude <procédure>, -only <procédure>• -quit <n> : troncature du listing après n lignes
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
called/total parentsindex %time self descendents called+self name index called/total children
0.00 0.02 1/1 matrixpower_ [2][1] 100.0 0.00 0.02 1 matpower_ [1] 0.02 0.00 9/9 square_ [4] 0.00 0.00 1/1 square_mult_ [5]
-----------------------------------------------
0.00 0.02 1/1 main [3][2] 100.0 0.00 0.02 1 matrixpower_ [2] 0.00 0.02 1/1 matpower_ [1]
-----------------------------------------------
PC-SAMPLING + GRAPH
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
granularity: each sample hit covers 8 byte(s) for 4.00% of 0.02 seconds
% cumulative self self total time seconds seconds calls ms/call ms/call name 80.0 0.02 0.02 9 2.17 2.17 square_ [4] 20.0 0.02 0.00 1 4.88 4.88 square_mult_ [5] 0.0 0.02 0.00 1 0.00 24.41 matpower_ [1] 0.0 0.02 0.00 1 0.00 24.41 matrixpower_ [2]
Index by function name
[1] matpower_ [4] square_ [2] matrixpower_ [5] square_mult_
PC-SAMPLING + GRAPH
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Optimisation par FEEDBACK
Optimisation en deux compilations successivesCinq Etapes:
– Compilation avec –gen_feedback (pas d'optimisation): f90 –gen_feedback –o prog prog.f
– Instrumentation: pixie prog => prog.pixie, prog.Addrs– Exécution: prog.pixie => prog.Counts– Affichage : prof –pixie –feedback prog.feedback prog – Recompilation et optimisation du compilateur
f90 –O5 –fast –arch host –feedback prog.feedback –o prog prog.f
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Mémoire virtuelle
Utilisation de la zone de swap– Mémoire requise > mémoire physique de la machine– Partage des ressources entre plusieurs programme
Profiling – Comparer la mémoire requise à la mémoire physique
• Commande size : text, data, bss• Option du compilateur sur Tru64 Unix: -V• Ne tient pas compte de la pile et du tas
– Page faults: vmstat ( Berkeley S) et sar (System 5)
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Page faults
Global : vmstat 5Virtual Memory Statistics: (pagesize = 8192) procs memory pages intr cpu
r w u act free wire fault cow zero react pin pout in sy cs us sy id
4 258 131 166K 138K 14K 2M 193K 2M 0 187K 0 119 213 531 22 1 77
4 258 131 166K 138K 14K 3 17 18 0 29 0 3 115 299 50 0 50
4 258 131 166K 138K 14K 0 0 0 0 0 0 3 35 319 50 0 50
4 258 131 166K 138K 14K 0 0 0 0 0 0 2 28 294 50 0 50
Par programme / procédure: Profiler hiprof hiprof –run –display –faults matpower
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Compteurs HardwareCompteurs Hardware
Petits registres comptabilisant les occurrences d’événements associés à des fonctions du processeur – Instructions load/store– Opérations Floating Point– Nombre de cycles d’attente d’accès mémoire– Cache misses, TLB misses,…– …
Fournies des informations utiles à l’explication des manques de performance de certaines parties de codesLe suivi de ces événements permet d’affiner l’adaptation du code à l’architecture cible
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Compteur Hardware sur EV67 et EV7
Deux registres de compteur de performances pour compter les événements hardware 1 à 16 événements hardware par compteur– 2 événements: comptage exacte– plus de 2 événements: multiplexage par l’OS sur les 2
compteurs, estimation statistique
l’overflow d’un compteur provoque un “hardware trap”Dépend du type de processeur – inopérant sur EV6Profiler uprofile
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Pourquoi PAPI?
Les compteurs Hardware existent sur la plupart des processeurs
Les mesures de performances associées à ces compteurs varient suivant les processeurs
Ily a très peu d’API permettant de les utiliser et elles sont souvent peu documentées instables et parfois inutilisables
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
But de PAPI
Fournir une API portable, simple à utiliser pour accéder aux compteurs hardware sur la majorité des plate-formes HPCDéfinir des métriques de performances communes à un grand nombre de plate-formes fournissant des informations utiles à l’optimisation de codesEncourager les vendeurs à standardiser les interfaces et la sémantiques des compteurs hardware
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Laisser faire le compilateur
Idéallement, le compilateur optimise automatiquement le code.– Il n’a pas toujours assez d’informations (taille des données connue au run-
time,…)– excessive cache performance
Optimisations principales– Utilisation du parallélisme d’instructions (pipelining)– Software pipelining– Inlining– Analyse Interprocédurale– Optimisation de boucles
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Options de base: On, n=0,…5 (Tru64 Unix)
Plus n grand:– Plus l’optimisation est “sophistiquée” – Plus le temps de compilation est important– Plus la taille du code peut devenir grande
Options de base On, n=1,…5– Optimisations locales: -O1 et plus– Optimisation globale : -O2 et plus– Optimisation globales supplémentaires: -O3 – Analyse interprocédurale: -O4 (par défaut)– Transformation de boucles et software pipelining: -O5
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Autres options d’optimisation (Tru64 Unix)
Alignement des données dans les commons et les structure : -align <mot-clé> ou –fastCompromis précision rapidité: -math_library fast ou accurateContrôler l’inlining : -inline <mot-clé> (speed, size,manual…)Contrôler l’unrolling : -unroll num ou –O3 et plusIndiquer au compilateur la machine cible : -arch host ou –arch ev6 , –fast => -arch hostContrôle du Software Pipelining : -O5 ou –pipeline –tune <cible>Permettre toutes les transformations mathématiques valides, ne respecte pas la sémantique (IEEE 754 binary floating point arithmetic) -fp_reorder ou -fast
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Directives #pragma optimize (Tru64 Unix)
Permet de localiser l’optimisation du compilateurAvec le compilateur COptions de la directive– #pragma optimize <setting>
• level= 0,…5 => #pragma optimize level =5• unroll=n => #pragma optimize unroll =5• ..
– #pragma optimize save– #pragma optimize restore
Voir Programmer’s Guide
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Software Pipelining (Tru64 Unix)
Le compilateur ne fait pas de Software Pipelining par défaut = > augmente le temps de compilation
-pipeline ou –O5 (-pipeline + -transform_loops)Performant sur les boucles vectorisablesMoins performant sur les boucles:
• de grande taille• contenant des récurrences
N’est pas effectué sur les boucles:• contenant des appels de fonction• contenant des instructions goto
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Automatique prefetching
Options du compilateur Tru64 Unix: Software pipelining• -pipeline, • -O5 => software pipelining• Pas de directives #pragmas
Niveaux de prefetching plus ou moins “agressif” ( IRIX – SGI)
– de façon conservative– pour les grosses structures de données – pour une taille des données inconnue
Deux niveaux de prefetching (pas sur Tru64 Unix)– niveau 2: mémoire principale vers le cache secondaire – niveau 1: cache secondaire vers le cache primaire
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Contrôle de l’Inlining
Compilateur: -inline <mot-clé>-inline manual : uniquement les fonctions (-O2, -O3)-inline size : en fonction de la taille du code (-O1 et plus)-inline speed : quelque soit la taille et le nombre d’appels (-O4 et –O5)-inline all : toutes les fonctions et les routines si c’est possible
-inline none: supprime l’inlining des sous-programmes (-O3 et moins)Compromis entre :– La taille du code– La fréquence des appels
Directive #pragma inline (id,…) ou #pragma noinline(id,…) en C et C++
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
IEEE 754 binary floating point arithmetic
Exemple de transformation non conforme avec IEEE 754do i=1,n tmp=1/c
b(i)=a(i)/c par do i=1,n
enddo b(i)=a(i)*tmp
enddo
L’ordre des opérations peut provoquer des résultats numériques différents (arrondis, overflows…)
L’utilisation des ressources hardware impose parfois de modifier l’ordre des opérations (pipelining…)
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Rappel: Transformation de boucles
Les différents types de transformation de boucles– loop unrolling– Loop interchange– Padding– Loop Fusion or Fission– Cache blocking– Prefetching
La connaissances des techniques permet d ’aider le travail du compilateur
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Transformations de boucles (Tru64 Unix)
Effectuées par le compilateur avec les options :-transform_loops-O5
Optimisation de l’utilisation des caches, de la gestion des instructions Son action est suffisante pour la plupart des programmes Optimisation du compilateur inhibée par– Boucles sans compteur– Appel de sous-programmes ou de fonctions sans inlining– Condition de sortie non standard– Aliasing (pointeurs)
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Optimisation du Cache
Transformation de boucles: -O5 ou -transform_loops
Concentrée sur les boucles imbriquées et peut bénéficier de l’analyse interprocédurale: -O3 et -transform_loops
résoud de nombreux problèmes de cache, ne corrige pas une mauvaise conception du code
désactive les transformations de boucles peut parfois augmenter les performances –notransform_loops
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Obstacles à la performance
Ce qui contribue à l’overhead– Appel à une routine– Référence indirecte à la mémoire– Tests à l’intérieur d’une boucle– Conversion de type– Variables non utilisées– Tests trop verbeux
Ce qui restreint la capacité d’optimiser du compilateur– Appel à une routine– Référence indirecte à une procédure– Tests à l’intérieur d’une boucle– Pointeurs ambigus
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Appels de sous-programmes
Réduit la capacité du compilateur à optimiser– Pas de software pipelining– Gestion des variables externes et des commons lourde
Compromis entre:– La taille de la routine– Le nombre d’appels
Éviter un nombre faible d’appels à une petite routineModularité indispensable pour le développement de
gros codes compactes et compréhensibles
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Appel de procédures (suite)
Préférer DO I=1,N
A(I)=A(I)+B(I)*CENDDO
ÀDO I=1,N
CALL MADD(A(I),B(I),C)ENDDOSUBROUTINE MADD(A,B,C)
A=A+B*CRETURN
END
EviterCOMMON /UTIL/KDO K=1,1000
IF (K .EQ. 1) CALL AUXENDDO
– K variable de common: le compilateur stocke en mémoire et recharge K à chaque itération
– Conserver k comme variable locale
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Macros
Principalement utilisées en C: concerne surtout les petites fonctions
#define average(x,y)((x+y)/2)main (){ float q=100,p=500;
float a;a=average(p,q);…}
2 étapes:• Pré-compilation par cpp: remplace les macros par leur code• Compilation C ou Fortran
Le compilateur C effectue les deux étapes automatiqument, certains compilateurs fortran également.
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
INLINING
Concernent les fonctions de taille plus importante que les macrosSelon le compilateur, plusieurs méthodes– Spécifier les procédures concernées à la compilation– Mettre dans le code des directives– Laisser le compilateur faire le travail automatiquement
Compromis entre la taille du code et les performances(réutilisation optimale du cache instructions)
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Branchement
Méthode:– Réduire les branchements si c’est possible– Les sortir de certains blocs (boucles,…)
Branchement à l’intérieur d’une boucle– Invariant conditionnel dans la boucle– Condition sur l’index de boucle=> restructuration du code– Instruction conditionnelle indépendante => unrolling, exécution en
parallèle– Instructions conditionnelles dépendantes=> conservation de l’ordre– Réductions => Laisser faire le compilateur– Condition de transfert de contrôle
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Branchement à l’intérieur d’une boucle
parameter (small=1.E-20)do i=1,n
if (abs(a(i)) .ge. small) thenb(i)=b(i)+a(i)*c
endifenddo=> Éliminer le test pour permettre le software pipelining
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Invariant conditionnel dans la boucle
DO I=1,KIF (N .EQ. 0) THEN
A(I)=A(I)+B(I)*CELSE
A(I)=0.ENDIF
ENDDO
Préférer:IF (N .EQ. 0) THEN
DO I=1,K A(I)=A(I)+B(I)*C
ENDDOELSE
DO I=1,K A(I)=0.
ENDDOENDIF
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Expression conditionnelle indépendante
DO I=1,NDO J=1,N
IF (B(J,I) .GT. 1.0) A(J,I)=A(J,I)+B(J,I)*C
ENDDOENDDOIndépendance des itérations
=> Unrolling ou exécution en parallèle possible
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Condition de transfert de contrôle
DO I=1,NDO J=1,N
IF (B(I,J) .EQ. 0) THENPRINT*,I,JSTOP
ENDIFA(I,J)=A(I,J)/B(I,J)ENDDO
ENDDOUtiliser les procédés de récupération d’erreur fournit par le
standard IEEE – option à la compilation
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Autres obstacles
Conversion de typeEviter les expressions de type caractère dans les expressions conditionnellesEffectuer ses propres éliminations de sous-expressions– Le compilateur ne les reconnaît pas toutes– Ne gère pas celles qui contiennent des appels de fonctions
Effectuer ses propres déplacements de code– Partie invariante dans une boucle
Références multiples à un même élément de tableauOn a pas toujours intérêt à le remplacer par une variable
scalaire
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Elimination de sous-expressions
x=r*sin(a)*cos(b)y=r*sin(a)*sin(b)z=r*cos(a)
devienttemp=r*sin(a)x=temp*cos(b)y=temp*sin(b)z=r*cos(a)
Le compilateur ne fait pas l’élimination d’expression avec appel de fonction
14 Janvier 2002 CIMENT – MIRAGE Laurence Viry
Déplacement de code
DO I=1,NA(I)=A(I)/SQRT(X*X+Y*Y)
ENDDO
Devient
TEMP=1./SQRT(X*X+Y*Y)DO I=1,N
A(I)=A(I)*TEMPENDDO
Recommended