View
104
Download
0
Category
Preview:
Citation preview
17-21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Analyse et Optimisation de code
Optimisation CompilateurOptimisation manuelle
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Optimisation séquentielle
Principes généraux
Architecture des processeurs, évolution les 30 dernières années
Architecture de la mémoire
Quelques techniques d’optimisations
Méthodologie proposée
Optimisation du compilateur
Timing et profiling
Quelques méthodes d’optimisation “manuelle”
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Méthodologie conseillée
Valider le 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
17 – 21 Octobre 2005 Formation Continue - CNRS 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,…)
Cache performance
Optimisations principales
Utilisation du parallélisme d’instructions Software pipelining Inlining Analyse Interprocédurale Optimisation des accès mémoire Optimisation de boucles
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Structure du compilateur
Front-end: Objectifs:
Analyse syntaxique et logique du programme, Transformation en un code intermédiaire prêt à
l’optimisation Dépendances:
Langage dépendant, Machine indépendante
Optimisation Haut-Niveau Objectifs: Transformations de boucles, inlining,… Dépendances
Quelques dépendances avec le langage Très dépendant de l’architecture (cache, ISA,…)
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Structure du compilateur (suite)
Optimisation globale Objectifs: optimisations globales et locales +
allocation des registres … Dépendances:quelques dépendances avec
l’architecture (nb registres,…) Génération de l’exécutable
Objectifs: Sélection des instructions (ISA) Optimisations adaptées à l’architecture de la
machine Dépendances:
Indépendant du langage Fortement dépendant de la machine
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Options de baseCompilateur INTEL
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=0,…3
-O0: désactive les optimisations -O1 : optimisation des performances tout en préservant la taille
du code. Adaptée à de gros codes comprenant de nombreux branchements et des boucles peu volumineuses
-O2 : par défaut en l’absence de –g. Gestion globale du code, spéculation, prédiction...
-O3 : -O2 + optimisation plus “agressives” concernant les accès mémoire et la gestion des boucles
-fast : active toutes les optimisations -O3 et –ipo sur tout le code
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Compilateur INTEL: -02
Option recommandée dans la plupart des cas Gestion globale du code Software pipelining Prédiction Spéculation Élimination du code non utilisé Allocations des registres globaux Traitement de la récursivité …
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Compilateur INTEL: -03
-O2 + « High Level Optimisations » High Level Optimisations (HLO)
Gestion des boucles (loop interchange, loop fusion, loop unrolling,…)
Prefetching Scalar replacement …
Adaptée aux applications utilisant de grandes boucles de calculs flottants, et de gros jeux de données
Peut modifier les résultats, les modifications ne respectent pas toujours la norme IEEE
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Compilateur INTEL: -fast
Méthode simple pour utiliser toutes les optimisations du compilateur -O3 -ipo (Analyse interprocédurale) -static: édition de liens avec les bibliothèques
partagées Certaines options peuvent être désactivées
Ex: -O0, -unroll0, -IPF_fltacc-, -IPF_fma-,…
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Désactiver des optimisations
-O0: désactive toutes optimisations -g: l’option d’optimisation par défaut devient –
O0 -mp: ne retient que les optimisations qui ne
provoquent pas de pertes de précision dans les calculs flottants (conforme aux standards ANSI et IEEE)
-nolib_inline: désactive l’inlining des fonctions intrinsèques
…
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Rapport d’optimisation - INTEL
-opt_report: génère un rapport d’optimisation -opt_report_file <fich>: dans le fichier « fich » Sur STTERR sans option –opt_report_file
-opt_report_level{min|med|max}: niveau de précision du rapport (min par défaut)
-opt_report_routine [substring]: génère un rapport sur Toutes les routines dont le nom contient substring Toutes les routines en l’absence de substring
-opt_report_phase <phase> : spécifie le type d’optimisation à analyserphase: ipo,hlo,ilo,ecg,all
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Arithmétique flottante (INTEL)
-mp Options: limite les optimisations sur le calcul flottant pour conserver la précision déclarée
-ftz[-] : « flush to zero » underflow [désactive] automatiquement à ON avec –O3 sur
Itanium et –O2 sur IA32 ex: ifort –O3 –ftz- -o prog prog.f
-fpen {n=0,1,3}: contrôle les « exceptions handling »
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Arithmétique flottante (Itanium)
-IPF_fltacc[-] : active [désactive] des optimisations qui peuvent affecter la précision des calculs flottants
IPF_fma[-] : active [désactive] l’utilisation des instructions MADD
IPF_fp_speculationfast : « agressives » spéculations sur les opérations arithmétiques
IPF_fp_speculationsafe : « conservatives » spéculations sur les opérations arithmétiques
IPF_fp_speculationoff : désactives les spéculations sur les opérations arithmétiques
IPF_fp_speculationstrict :désactives les spéculations sur les opérations arithmétiques
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Software Pipelining - INTEL
Options de base d’optimisation
-O1 ne fait pas de software pipelining (préserve la taille du code)
-O2 (par défaut) et –O3 fait du software Pipelining
= > augmente le temps de compilation
Aide au compilateur:directives de compilation
!DEC$ SWP ou !DEC$ NOSWP avant la boucle
!DEC$ LOOP COUNT [n]
!DEC$ DISTRIBUTE POINT:
!DEC UNROLL[n]
Le rapport d’optimisation (-opt_report) indique ou le software pipelining a été utilsé
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Software Pipelining – INTELExemple
!DEC$ SWP
do i=1,n
if (c(i) .eq. 0) then
b(i)=a(i)+1
else
b(i)=a(i)/c(i)
endif
enddo
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Contrôle de l’Inlining - INTEL
Par le compilateur: -O2: inlining des fonctions intrinsèques
-O3: inlining de certaines fonctions utilisateur
-Minline: active l’inlining
-Minline=name:FUNC
Minline=size:NNN
Compromis entre : La taille du code La fréquence des appels
Par une directive #pragma inline (id,…) ou #pragma noinline(id,…) en C et C++
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
IPA – compilateur Intel
Phase de compilation Stocke une représentaion intermédiaire (IR) du code
source dans le module objet ( mock objet file ) L’IR contient des informations qui seront utilisées
pour l’optimisation Phase d’édition de liens
Dernière phase de compilation IPA sur tous les fichiers qui contiennent une IR Effectue la compilation individuelle en utilisant les
informations stockées dans les IR Edition de liens
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
IPA – compilateur Intel
Options: -ip: sur un seul fichier -ipo: sur plusieurs fichiers -O0: pour désactiver l’IPA
Commandes ifort –ipo –c a.f90 b.f90 c.f90 puis
ifort –o prog a.o b.o c.o ifort –o prog a.f b.f c.f
-auto_ilp32 sur les processeurs Itanium Nécessite une analyse inter-procédurale
Le compilateur utilisera des pointeurs 32 bits si l’application utilise un espace qui le permet
-auto_ilp32 et -ipo
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Alignement des données
-align <mot-clè> : alignement sur les frontières naturelles des composants d’un common, d’un type dérivé ou d’une structure d’enregistrement common: alignement sur les frontières multiples de 4
Bytes dcommon: alignement sur les frontières multiples de 8
Bytes sequence, record…
-align recnbyte (-Zp[n]) alignement des composants d’une structure sur n des frontières de n bytes
-align : alignement naturel des variables figurant dans un common
…
17 – 21 Octobre 2005 Formation Continue - CNRS 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
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Transformations de boucles - INTEL
Effectuées par le compilateur : -O3 Directives de compilation aide le compilateur pour la
gestion des dépendances 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)
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Automatique prefetching
Réduire la latence des accès mémoire
Options du compilateur: -prefetch avec –O3
Procédure intrinsèque: MM_PREFETCH
Directives de compilation: !DEC$ PREFETCH <données> et NOPREFETCH
Exemple
...!DEC$ NOPREFETCH c
!DEC PREFETCH a do i=1,n
b(i)=a(c(i))+1 enddo ...
ifort –O3 –prefetch ...prog.f
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Aider le compilateur Recherche des dépendances
Dépendances entre les itérations d’une boucle Options de compilation: -ivdep_parallel Directive de compilation: !DIR$ IVDEP
Exemple:!DIR$ IVDEP
do j=1,na(b(j))=a(b(j))+1
enddo
ifort –O3 –ivdep_parallel … prog.f
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Optimisation spécifique à un processeur Intel
Pentium -tpp5: génère du code pour Pentium -tpp6: génère du code pour Pentium Pro II/III -tpp7: génère du code pour Pentium 4 -xi : génère du code - support pentium ProII -xW : génère du code – Pentium 4 extensions -xK : génère du code – SSE extensions
Itanium -tpp1: génère du code pour Itanium(Merced) -tpp2: génère du code pour Itanium(MacKinley)
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Profile-Guided Optimizations (PGO)
Compilation +Instrumentalisation du
codeifort –prof_gen a.f
Exécution du code instrumentéa.out
Feedback Compilationifort –prof_use …a.f
Exécutable instrumenté
a.out
Fichier dynamique contenantles informations de profilingxxxxxx.dyn
Code optimisé
Utilise le fichier xxxxxx.dyn et Crée le fichier dynamique d’informations : pgopti.dpi
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Options recommandées - INTEL
Intel Pentium Pro II/III – AMD Athlonifort/icc/icpc -O3 –ipo –tpp6 –axiK….
Intel Pentium 4 /Xeonifort/icc/icpc -O3 –ipo –tpp7 -axiKW
Intel Itanium (Merced)ifort/icc/icpc -O3 –ipo –tpp1 -ftz
Intel Itanium (McKinley)ifort/icc/icpc -O3 –ipo –tpp2 -ftz
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Optimisations Manuelles
Appels de sous-programmes Utilisation des “macros” en C/C++ Inlining Traitement des branches Elimination de sous-expressions Conversion de types ...
17 – 21 Octobre 2005 Formation Continue - CNRS 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
17 – 21 Octobre 2005 Formation Continue - CNRS 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
Conseils: Éviter un nombre faible d’appels à une petite routine Modularité indispensable pour le développement de gros
codes compactes et compréhensibles
17 – 21 Octobre 2005 Formation Continue - CNRS 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
éviterCOMMON /UTIL/KDO K=1,1000
IF (K .EQ. 1) CALL AUX
ENDDO K variable de
common: le compilateur stocke en mémoire et recharge K à chaque itération
Conserver k comme variable locale
17 – 21 Octobre 2005 Formation Continue - CNRS 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 automatiquement, certains compilateurs fortran également.
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
INLINING
Concernent les fonctions de taille plus importante que les macros
Selon 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)
17 – 21 Octobre 2005 Formation Continue - CNRS 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
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Branchement à l’intérieur d’une boucle
parameter (small=1.E-20)
do i=1,n
if (abs(a(i)) .ge. small) then
b(i)=b(i)+a(i)*c
endif
enddo
=> Éliminer le test pour permettre le software pipelining
17 – 21 Octobre 2005 Formation Continue - CNRS 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
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Expression conditionnelle indépendante
DO I=1,N
DO J=1,N
IF (B(J,I) .GT. 1.0) A(J,I)=A(J,I)+B(J,I)*C
ENDDO
ENDDO
Indépendance des itérations
=> Unrolling ou exécution en parallèle possible
17 – 21 Octobre 2005 Formation Continue - CNRS 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
ENDDO
Utiliser les procédés de récupération d’erreur (standard IEEE ) – option à la compilation
17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry
Autres obstacles Conversion de type Eviter les expressions de type caractère dans les
expressions conditionnelles Effectuer 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 tableau On a pas toujours intérêt à le remplacer par une variable
scalaire
17 – 21 Octobre 2005 Formation Continue - CNRS 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
17 – 21 Octobre 2005 Formation Continue - CNRS 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