17-21 Octobre 2005 Formation Continue - CNRS Laurence Viry Analyse et Optimisation de code Techniques doptimisation

17-21 Octobre 2005 Formation Continue - CNRS Laurence Viry

Analyse et Optimisation de code

Techniques d’optimisation

17 – 21 Octobre 2005 Formation Continue - CNRS Laurence Viry

A faire

Vérifier: Multi-threading bib sun (F roch) Utilisation des caches L3


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”


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


Algorithmes Performants

Les Mflops est un mauvais indice de performance d’un code

Deux 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


Techniques d’optimisation

Inlining Analyse interprocédurale Accès mémoire

Réutilisation du cache Stride minimum Copie …

Réduction des TLB misses Alignement des données

Optimisation de boucles


Compilateur: génération de code (rappel)

1ère phase: analyse syntaxique et logique Transformation en un code intermédiaire prêt

à l’optimisation 2ème phase: Optimisation Haut Niveau

(HLO: transformations de boucles, inlining,..) 3ème phase: Optimisations globales et

locales, allocation des registres… 4ème phase: Génération du code en tenant

compte des spécificités de l’architecture du(des) processeurs.


Software Pipelining

Le compilateur ne fait pas toujours du Software Pipelining par défaut

augmente le temps de compilation Performant sur les boucles vectorisables Moins 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


Inlining

Remplace l’appel d’une procédure par le code de cette procédure

Inté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.


Inlining

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


Analyse Interprocédurale (IPA)

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


IPA (suite)

Analyse plusieurs procédures simultanément

Renvoie la plupart des actions d’optimisation du compilateur juste avant l’édition de liens

Compilations en plusieurs phases Contrôle la façon dont les procédures et les fonctions

interagissent ente elles Principales actions:

Inlining automatique Désactive la récursivité ...


IPA (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,

…


IPA (suite)

Inconvénients:

augmente le temps global compilation/édition de liens

augmente la taille de l’exécutable

peut modifier sensiblement les résultats


Optimisation des accès mémoire

Minimiser le stride

Fortran: stockage par colonneParcourt d’un tableau 2D par l’index le plus à gauche

C : stockage par ligneParcourt d’un tableau 2D par l’index le plus à droite

Regroupement de données

Optimisation par copie

Alignement « naturel » des données

Optimisation des boucles


Réutilisation du cache: stride

Stride égal à 1 (Fortran) do i=1,n

do j=1,n a(i,j)=b(i,j) enddo

enddo

do j=1,n do i=1,n

a(i,j)=b(i,j) enddo

enddo

sera modifié


Réutilisation du cache (suite)

Regrouper les données utiliséesdo i,1,n

j=index(i) d=d+sqrt(x(j)*x(j) + y(j)*y(j) + z(j)*z(j)

enddo

do 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


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 dû à la copie

Préférer le " Cache Blocking " lorsque c’est possible


Recouvrement des latences d’accès aux données

Par le système pour les faibles latences: Caches primaires

Caches 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


Alignement des données

Alignement « naturel »: lorsque l’adresse est un multiple de la taille de la donnée

Le compilateur effectue en général cet alignement.

Mauvais alignement dans le cas de l’instruction EQUiVALENCE et dans les COMMON en Fortran

Conseils:

Commencer par les données numériques de plus grande taille suivies par les non numériques

Utiliser les options d’alignement du compilateur …


Optimisationde boucles

Unrolling

Boucles imbriquées

Loop interchange

Références mémoire

Blocking

Out-OF-Score


Loop Unrolling

Diminue l’overhead dû à la gestion des boucles

Favorise le parallélisme du processeur (pipelining)

Mais nécessite une boucle de préconditionnement


Les 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


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:


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


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


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


Algorithme de Gauss – DS20 / ES45Influence de la taille du cache


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


Multiplication de matrices

=

Accès:Bloc C : 1foisBloc A : nb colonnes de CBloc B : nb lignes de A

C A

B


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


IEEE 754 binary floating point arithmetic

Transformation non conforme avec IEEE 754do i=1,n tmp=1/c

b(i)=a(i)/c par do i=1,nenddo 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 resources hardware impose parfois de modifier l’ordre des opérations (pipelining…)

Suivre le standard IEEE 754


Optimisations Numériques

Précision Architecture 32bits: ~7 décimales Architecture 64bits: ~13 décimales

128bits – options du compilateur: ~30décimales diminution des performances (~50%)utilité de cette précisions ?

MADD instruction (ISA du processeur) Accélère les codes d’algèbre linéaire N’adhère pas totalement à la norme IEEE Perte de précision possible


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


Efficacité des Entrées/Sorties

Utiliser autant que possible des fichiers non

formattés

Écrire la globalité d’un tableau ou d’une chaîne

de caractères plutôt qu’élément par élément

Écrire le tableau dans son ordre naturel

Utiliser la technique de bufferisation pour

minimiser le nombre d’appels à des E/S

Pour MPI, utiliser MPI-IO


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


Utiliser des codes déja optimisés Bibliothèques constructeur

HP/COMPAQ: CXML (DXML) IBM : ESSL SGI : SCSL SUN: Performance Library …

Bibliothèques domaine public – portable BLAS (1 2 3) LAPACK: algèbre linéaire FFTW : transformée de Fourier ATLAS PETSC GOTO (BLAS) …

Bibliothèques commerciales NAG IMSL


Utiliser des codes déjà optimisésServeur Alpha : ES45

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 : libcxmlp.a


Utiliser des codes déjà optimisésSGI: ALTIX 350

SCSL () et SCSLXXX (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: séquentielle et parallèle séquentielle : -lscs , –lscs_i8 parallèle (multi-thread): -lscs_mp , –lscs-i8_mp


Utiliser des codes déjà optimisésSUN: cluster de V40Z (quadri-procs)

SUN Performance Library (version séquentielle) 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 ...

Utilisation -xlic_lib=sunperf parallèle (multi-thread à verifier ):

Documents

17-21 Octobre 2005 Formation Continue - CNRS Laurence Viry Analyse et Optimisation de code Techniques doptimisation