Personal tools
You are here: Home Calcul Technique Documentation IBM cluster p575 (Power5) Techniques d'optimisation
Document Actions

Techniques d'optimisation

Optimisation de codes Fortran sur architecture scalaire

Techniques d'optimisation

  • Choix des algorithmes
  • Librairies scientifiques
  • Outils de développement
  • Opérations flottantes
  • Hiérarchie mémoire
  • Optimisations de boucles
  • Unrolling des boucles
  • Optimisations mémoire
  • Dimensions des tableaux
  • Optimisations des E/S

  • Introduction

    Pour optimiser un code de calcul, il faut tenir compte de l'architecture sur laquelle ce dernier sera exécuté. Le facteur le plus pénalisant en terme de performances est le manque de données au niveau du processeur, i.e. les données nécessaires à la réalisation des opérations ne sont pas présentes au voisinage du processeur et il faut alors aller les chercher en mémoire et donc les attendre, d'où une perte de temps et de performances. La figure suivante présente le parcours des données de la mémoire vers les registres du processeurs.

    compilateur Cliquer pour voir une image GIF (27ko).

    La seconde figure présente les temps d'accès (moyens) vers ces différentes zones mémoires, c'est-à-dire les temps nécessaires pour ramener les données de la zone mémoire vers le processeur :

    compilateur Cliquer pour voir une image JPEG (35ko).

    Il y a plusieurs directions à suivre pour optimiser un code, par exemple :

    Retour au début de la page.


    Choix des algorithmes

    Il faut utiliser des algorithmes efficaces, c'est le facteur le plus important en terme d'optimisation. Il existe de nombreux ouvrages d'algorithmique, mais aussi les publications dans les revues scientifiques. On peut ainsi profiter de l'expérience des autres.

    Retour au début de la page.


    Librairies scientifiques

    Les librairies sont des ensembles de sous-programmes testés, validés et optimisés qui permettent d'économiser facilement du temps CPU (outre le temps et les efforts de développement ....). Il est donc recommandé de les utiliser. Pour les fonctions mathématiques usuelles, on peut linker avec la librairie mathématique optimisée (-lmass et -lmassv) au lieu de celle prise par défaut (-lm).

    De même, pour l'algèbre linéaire avec BLAS ou LAPACK, ... Ces bibliothèques portables sont incluses (au moins en partie) dans les librairies optimisées par IBM qui s'appellent ESSL et PESSL. Une version complète de LAPACK est aussi installée.

    Retour au début de la page.


    Outils d'aide au développement

    Une fois le code débogué et validé, on cherche à l'optimiser en déterminant les zones consommatrices du CPU au sein du source. Pour cela, on utilise les outils d'analyse de performances comme gprof. On travaille sur un code compilé avec le meilleur niveau d'optimisation par rapport aux pertes de précision (par exemple -qhot -O3 -qarch=auto -qtune=auto -qstrict ... voire -O3 -qstrict).

    Retour au début de la page.


    Opérations en virgule flottante

    Les opérations qui coûtent le plus cher à effectuer sont les opérations en virgule flottante. Elles sont effectuées par les unités arithmétiques (FPU). L'instruction de calcul de base est la multiplication / addition (FMA pour Floating-point Multiply and Add) en double précision avec ses variantes comme la multiplication/soustraction et celles au signe près (il y a aussi les variantes en simple précision).
    Une addition, soustraction ou multiplication (pas la division), seule, utilise les mêmes composants matériels qu'une multiplication / addition et prend le même temps pour être effectuée. Plusieurs FMA indépendantes qui se succèdent peuvent ainsi être pipelinées ( i.e. insérée dans une file avec traitement à la chaine) dans les unités FPU. Cela ne concerne pas la division qui est traitée à part, par une unité particulière. Cela concerne ausi les racines carrées. Il est donc recommandé de limiter ce genre d'opérations. Le tableau suivant récapitule les caractéristiques de ces optérations :
     
    Instruction Simple précision
    (nombre de cycles horloge)
    Double précision
    (nombre de cycles horloge)
    Pipelinées ?
    fma 6 6 oui
    fdiv 32 32 non
    fsqrt 38 38 non

    Il est important de remplacer des opérations coûteuses par des opérations moins chères là où elles sont répétées, comme dans l'exemple suivant en mettant une multiplication à la place d'une division :
     

    la boucle suivante ....
    x = value
    DO i = 1, n
       y (i) = z (i) / x
    END DO
    ... peut ainsi être remplacée par ....
    x = 1.0_rp / value
    DO i = 1, n
       y (i) = z (i) * x
    END DO

    Il faut noter que cela n'est plus conforme à la norme IEEE puisque les erreurs d'arrondi ne sont plus les mêmes mais cela permet des gains substantiels à faible coût en général.
    De même, multiplier coûte plus cher qu'additionner.

    Il faut aussi éviter les conversions de type inutiles : éviter les conversions implicites et utiliser des constantes de type approprié.
     

    L'initialisation suivante ...
    REAL U (10)

    DO i = 1, 10
       U (i) = 1
    END DO

    ... doit être remplacée par  ...
    REAL(rp) U(10)

    DO i = 1, 10
       U (i) = 1.0_rp
    END DO

    Enfin, il faut éliminer les exceptions flottantes : elles entrainent un surcoût de gestion (en plus des erreurs éventuelles), voir les options de déboguage .

    Retour au début de la page.


    Hiérarchie mémoire

    Pour obtenir un taux élevé d'occupation des unités de calcul flottant (et donc approcher la puissance crête du processeur), il est impératif de faire disparaitre les temps de latence dûs à l'absence des données au niveau des caches : les données doivent résider dans le cache de niveau 1 (L1).
    La page consacrée à la description matérielle du processeur détaille la hiérarchie mémoire et les caractéristiques des trois niveaux de cache.
    La grande bande passante entre les deux niveaux de cache L1 et L2 est suffisante pour alimenter les unités de calcul flottant. Mais une différence importante réside dans le temps de transfert d'une donnée entre les registres et le cache L1 d'une part et les registres et le cache L2 d'autre part. Dans le premier cas il est de 4 cycles d'horloge, dans le second de 14 cycles.
    La recommandation de base est de bloquer les données dans le cache L2 et d'organiser l'accès des données pour le cache L1. Il est aussi important d'augmenter le débit entre la mémoire et les registres en favorisant le data prefetch streaming (qui repose sur des caractéristiques du processeur Power4). Cela consiste à créer des flux de données. Pour cela, on peut faire la fusion de boucles.
    Les deux boucles suivantes ...
    DO I = 1, N
       S = S + A(I) * B(I)
    END DO
    DO I = 1, N
       R(I) = C(I) + D(I)
    END DO
    ... peuvent être remplacées par  ...
    DO I = 1, N
       S = S + A(I) * B(I)
       R(I) = C(I) + D(I)
    END DO
     
     
    On peut aussi augmenter les performances en utilisant la méthode de la bisection :
    Le produit scalaire standard ...
    S = 0.0_rp
    DO I = 1, N
       S = S + A(I) * B(I)
    END DO
     
     
     
     
     
    ... et sa version modifiée ...
    N2 = ISHFT (N,-1) ! i.e. N2=N/2
    S0 = 0.0_rp
    S1 = 0.0_rp
    DO I = 1, N2
       S0 = S0 + A(I) * B(I)
       S1 = S1 + A(N2+I) * B(N2+I)
    END DO
    IF ( 2*N2 /= N ) S1 = S1 + A(N)*B(N)
    S = S0 + S1

    Dans le cas où les données viennent de plus loin que le cache L2, les performances de la boucle peuvent être améliorées de 20% mais la longueur minimale d'efficacité est alors multipliée par 2 : elle doit faire au moins 220. L'effet inverse est aussi possible s'il y a trop de streams : plus de 8 peut se révéler néfaste.

    Autre exemple :

    La boucle suivante ...
    REAL A1(N), A2(N), A3(N), A4(N), A5(N)
    REAL B1(N), B2(N), B3(N), B4(N), B5(N)
    REAL C1(N), C2(N), C3(N), C4(N), C5(N)

    DO I = 1, N
       C1(I) = A1(I) * B1(I)
       C2(I) = A2(I) * B2(I)
       C3(I) = A3(I) * B3(I)
       C4(I) = A4(I) * B4(I)
       C5(I) = A5(I) * B5(I)
    END DO

      ... peut être remplacée par  ...
    REAL(rp) A(5,N), B(5,N), C(5,N)
     
     

    DO I = 1, N
       C(1,I) = A(1,I) * B(1,I)
       C(2,I) = A(2,I) * B(2,I)
       C(3,I) = A(3,I) * B(3,I)
       C(4,I) = A(4,I) * B(4,I)
       C(5,I) = A(5,I) * B(5,I)
    END DO


    Le gain est double : on n'utilise plus que 3 streams au lieu des 15 précédents. On utilise mieux le cache L1 puisque toutes les données amenées (16 réels double précision par data cache miss) sont utilisées complètement en un peu plus de 3 itérations au lieu d'occuper 15 lignes de cache et demander 16 itérations pour les traiter.

    Concernant les data prefetch streaming, ceux-ci ne fonctionnent que dans la page mémoire où ils sont initiés : la fin de la page les arrêtent, il faut en recréer pour la suite des données dans la page adjacente. La taille des pages mémoire est 4 kilo-octets, soit 4096 octets ou encore 512 réels double précision, ce qui casse très vite les performances. Il existe d'autes pages, les large pages (grandes pages) qui font 16Mo chacune. La moitié de la mémoire de chaque noeud est vue comme des large pages.
    Pour une application d'hydrodynamique dont l'algorithmique repose sur la méthode itérative Bi-CGStab, l'utilisation des larges pages et la transformation précédente appliquée à la structure de données ont permis un gain d'environ 40 % du temps CPU consommé.

    Cela est très intéressant pour les codes consommateurs de mémoire, i.e. ceux qui balayent de grands tableaux de données. Pour cela, on ajoute l'option -qlargepage lors de la compilation pour que l'optimisation soit faite en vue d'utiliser les larges pages et l'option -blpdata lors de l'édition de liens du programme, voir les pages des compilateurs XLF et XLC.

    Remarque :
    les options -qlargepage et -blpdata sont ajoutées par défaut à la compilation et à l'édition des liens sur les noeuds p575 du CRIHAN. Pour les applications, non compilées au CRIHAN, il faut modifier l'exécutable avec la commande :
    ldedit -blpdata executable

    Remarque :
    Il est important de toujours valider les performances des modifications en mesurant le temps ou en faisant du profilage.

    Retour au début de la page.


    Optimisations des boucles

    En général, les boucles sont responsables d'une grande partie du temps d'exécution. Pour gagner en performance, on peut appliquer les modifications suivantes :
    1. réduire le pas entre les éléments accédés : un stride de 1 est souhaitable,
    2. utilser des data prefetch streaming (voir la hiérarchie mémoire)
    3. adapter les dimensions pour l'associativité du cache L1 (voir les dimensions des tableaux multidimensionnels),
    4. faire du cache blocking (voir les optimisations mémoire)
    5. en cas de boucles imbriquées, il faut réduire les boucles extérieures,
    6. enlever les opérations invariantes, i.e. éviter un travail qui n'est pas nécessaire :
    7. la boucle suivante ...
      DO j = 1, n
         i = 3
         work (j) = ...
      END DO
      ... doit être remplacée par ...
      i = 3
      DO j = 1, n
         work (j) = ...
      END DO
    8. fusionner les boucles ayant les mêmes bornes d'utilisation : diminuer les frais de gestion de boucles et offrir des opportunités pour les optimiseurs,
    9. les boucles suivantes ....
      DO i = 1, n
         FOO
      ENDDO

      DO j = 1, N
         BAR
      ENDDO

      ... peuvent être fusionnées ....
      DO i = 1, n
         FOO
         BAR
      END DO

       
       

    10. optimiser les opérations sur les nombres flottants (remplacer les opérations coûteuses par des opérations moins chères).

    Retour au début de la page.


    Unrolling des boucles

    Pour obtenir de bonnes performances sur les boucles, celles-ci doivent être FMA-bound, i.e. le nombre de cycles d'horloge pour les instructions autres que les FMA (essentiellement les load/store de/vers la mémoire) doit être inférieur au nombre de cycles des FMA, de telle sorte qu'il puisse y avoir recouvrement par les FMA (FMA pour Floating-point Multiply and Add). Il est bien sûr nécessaire que les FMA soient un minimum indépendantes les unes des autres pour que ce soit efficace.

    La boucle interne

    La technique de base pour exécuter de nombreuses FMA indépendantes, i.e. qu'elles puissent être mises dans les pipelines et traitées est l'unrolling de la boucle interne (unrolling pour déroulement). Bien que cela peut être fait à la main, c'est en général inutile car le compilateur peut le faire de manière fiable et efficace. De plus, si on déroule à la main, le compilateur risque de le faire aussi ensuite, ce qui peut provoquer des pertes de performances en saturant les registres disponibles (utilisation de l'option -qnounroll pour l'inhiber), soit 32.

    La boucle externe

    Dans le cas où la boucle interne est load/store-bound (par opposition à FMA-bound), il peut être possible d'améliorer grandement les performance en augmentant le ratio FMA / (load-store) dans cette boucle. Cela n'est possible que dans le cas de ré-utilisation de données et la technique de base est souvent l'unrolling de la boucle externe.
    A titre d'exemple, prenons la boucle suivante :
    DO i = 1, n
      DO j = 1, n
         y (i) = y(i) + x(j)*a(j,i)
      END DO
    END DO

    Cette boucle est déjà bien structurée puisque la boucle interne a un incrément de 1 et qu'il s'agit d'une réduction (y(i) est une constante). Cela signifie que le nombre de loads/stores nécessaires dans la boucle interne est minimal puisque y(i) n'occupe qu'un registre et reste en place jusqu'à la fin de la boucle interne. Un itération de la boucle interne ne demande donc que deux loads et zéro store. La situation serait bien pire si on permutait les deux boucles.
    Cependant, cette boucle est load/store-bound puisqu'il y a plus de load/store que de FMA et les performances de la boucle seront donc limitées par le débit de l'unité load/store. Le compilateur va réussir à dérouler la boucle interne sur j, ce qui contribue à la remplir avec des FMA indépendantes. Cependant cela ne va pas améliorer le ratio FMA - load/store. On a alors :
    DO i = 1, n, 4
      s0 = 0.0_rp
      s1 = 0.0_rp
      s2 = 0.0_rp
      s3 = 0.0_rp

      DO j = 1, n
         s0 = s0 + x(j  )*a(j  ,i)
         s1 = s1 + x(j+1)*a(j+1,i)
         s2 = s2 + x(j+2)*a(j+2,i)
         s3 = s3 + x(j+3)*a(j+3,i)
      END DO

      y(i) = y(i) + s0 + s1 + s2 + s3
    END DO


    Pour chaque FMA que l'on ajoute dans la boucle interne, on impose deux loads.

    La solution, dans ce cas, est le déroulement de la boucle externe sur i. Dans notre situation, le compilateur le fera peut-être avec l'option mais il est préférable de le faire à la main. La version ci-dessous montre les boucles imbriquées avec la boucle externe déroulée 4 fois (attention si n n'est pas un multiple de 4 !).
    DO i = 1, n, 4
      s0 = y(i)
      s1 = y(i+1)
      s2 = y(i+2)
      s3 = y(i+3)

      DO j = 1, n
         s0 = s0 + x(j)*a(j,i)
         s1 = s1 + x(j)*a(j,i+1)
         s2 = s2 + x(j)*a(j,i+2)
         s3 = s3 + x(j)*a(j,i+3)
      END DO

      y(i)   = s0
      y(i+1) = s1
      y(i+2) = s2
      y(i+3) = s3
    END DO


    Le ratio FMA - load/store est meilleur puisque l'élément x(j) est ré-utilisé trois fois dans la boucle interne. Pour quatre itérations dans la version originale, on passe de 8 loads à 5 (et on fait 4 FMA). Le ratio passe asymptotiquement de 2 à 1.

    Les scalaires temporaires s0, s1, s2, s3 sont très importants. En effet, pour une variable un peu plus complexe que des scalaires indicés, le compilateur risque de ne pas voir qu'il s'agit d'un scalaire constant au sein de la boucle et il peut alors générer un grand nombre de loads/stores inutiles. De manière générale, ce type de codage (remplacer des éléments de tableaux par des scalaires dans une boucle) améliore le travail du compilateur. Il faut toutefois éviter de le faire à outrance.

    Retour au début de la page.


    Optimisations mémoire

    1. aligner les données en mémoire (plus rapide car minimise les accès mémoire),
    2. optimiser les accès mémoire : accéder aux tableaux de la même façon qu'ils sont stockés. En Fortran les tableaux sont stockés par colonne, en C par ligne :
    3. DO i = 1, n

         DO j = 1, n

            A (i,j) = B (i,j) lent
            C (j,i) = D (j,i) rapide
         END DO
      END DO

      for (i=1; i<(n+1); i++)
      {
          for (j=1; j<(n+1); j++)
          {
             A[i][j] = B[i][j];  rapide
             C[j][i] = D[j][i];  lent
          }
      }
    4. utiliser des algorithmes qui ont une approche locale des variables : maximiser le travail sur des ensembles de données contiguës, minimiser la navigation aléatoire dans de gros volumes de données (adressage indirect : A (TAB(i) ) ).
    5. utiliser des algorithmes "par bloc" pour maximiser la gestion du cache : travailler sur des blocs de mémoire qui rentrent dans le cache de données mais pas le tableau complet. C'est particulièrement utile dans le cas d'opérations matricielles. Cela permet d'augmenter sensiblement les performances du cache si :
      • le nombre d'itérations >> le nombre de données utilisées
      • les boucles imbriquées sont permutables
      • la taille du bloc est inférieure à la taille du cache disponible
      Les deux boucles suivantes ...
      DO j = 1, n
       

          DO i = 1, m
       

               ...
       
       

          END DO
       

      END DO

      peuvent être arrangées comme suit
      DO j1 = 1, n, jblock
          j2 = min (j1 + jblock - 1, n)

          DO i1 = 1, m, iblock
          i2 = min (i1 + iblock - 1, m)

              DO j = j1, j2
                 DO i = i1, i2
                     ...
                 END DO
              END DO

          END DO
      END DO

      Si on note nb_tab le nombre de tableaux impliqués (tous de mêmes dimensions n et m), on peut évaluer iblock et jblock comme suit :
      nb_bloc * iblock * jblock * sizeof(real) < 0.9 * taille du cache en octets

      Le compilateur xlf ne sait malheureusement pas appliquer cette technique dite du cache blocking. Un peu de travail de re-écriture est alors nécessaire et peut apporter un gain très important.

    6. en C, utiliser la librairie de gestion rapide de la mémoire; un malloc rapide se trouve dans libmalloc{.a.so} en linkant avec -lmalloc, (configuration à l'aide de mallopt, voir sa manpage),
    7. réduire les frais de gestion lorsque l'on alloue de nombreux petits blocs de données : il est préférable d'allouer une portion suffisante de mémoire puis de la redistribuer).
    Le but est à chaque fois de donner des opportunités pour l'optimisation d'une boucle, permettre un réarrangement des opérations pour une meilleure efficacité (maximiser l'utilisation des registres).


    Dimensions des tableaux multidimensionnels

    Les dimensions des tableaux multidimensionnels ne doivent pas être des puissances de 2. Les caches sont des zones mémoire où les données sont stockées à l'aide d'adresses. Ces adresses sont calculées par modulo à partir des adresses initiales des données en mémoire. Comme les caches ont une dimension égale à une puissance de 2, manipuler des tableaux avec des dimensions en puissance de 2 risque d'entrainer de grosses pertes de performances dûes au cache thrashing, i.e. le cache est rafraichi en permanence car les données nécessaires au processeur ont les mêmes adresses dans le cache et s'éliminent les unes les autres.

    Retour au début de la page.


    Optimisations des E/S (entrées/sorties)

    Les entrées / sorties consistent en les lectures et écritures vers l'écran ou des fichiers. Elles ralentissent le code et il est préférable de ne pas le surcharger en dehors de la phase de déboguage et de validation. La plupart du temps passé durant les E/S ne sont pas du temps cpu et les écritures vers les ports d'E/S ne sont pas synchrones par défaut, i.e. le processus continue de travailler pendant que les E/S sont réalisées.
    D'une manière générale, il est préférable de :
    1. éviter les répertoires surpeuplés, mais d'utiliser des chemins d'accès courts : cela réduit les temps de recherche du répertoire,
    2. éviter les fichiers temporaires et de garder les données en mémoire,
    3. rediriger les E/S du terminal (clavier/écran) car plus lentes que les E/S fichier.
    Il y a deux types d'E/S : les formatées et les non formatées. Une E/S formatée traduit toutes les données sous forme de caractères durant l'opération. Cette opération consomme du temps cpu. L'instruction d'écriture contient un descripteur qui impose un format pour la présentation des données. Une E/S non formatée transfère les données sans les éditer et donc la représentation des données est la même que celle en mémoire. Les E/S non formatées (fichier binaire) sont beaucoup plus rapides que les E/S formatées (facteur pouvant aller jusqu'à 6). Mais elles ont l'inconvénient d'être architecture - dépendantes. Les données non formattées présentes sur Illiac8 sont directement réutilisables sur le cluster IBM car les deux fabricants (SGI et IBM) utilisent le même standard.
    En Fortran, il faut utiliser les noms de tableaux plutôt que de passer par des listes :
    WRITE (20) ( A(I), I = 1, N )
    à remplacer par
    WRITE (20) A
    De même, il faut bannir les sorties de la forme :
    DO i = 1, N
       WRITE (20) U (i)
    ENDDO

    Il est aussi préférable d'appeler plutôt les fonctions C comme dans l'exemple suivant (gain environ 20%) :

    foo.f bar.c
    PROGRAM WRITEA #include <stdio.h>
    INTEGER   A void cwrite_ (int*a)
    CALL INIT (A) {
    CALL CWRITE (A) printf ("%d", *a);
    }
    END

    La compilation est réalisée de la manière suivante :

    cc -c bar.c
    f90 foo.f90 bar.o -o foobar
    Les données sont lues et écrites sur le disque par bloc de taille de lbsize octets. Par défaut, lbsize est égale à la taille d'un secteur du disque arrondie à la puissance inférieure de 2. Une lecture peut être inférieure à lbsize s'in n'y a pas assez d'octets contigus dans la portion de fichier accédée. Un bloc entier sera lu ou écrit si un seul octet est demandé. Les blocs sont temporairement mis dans un cache en mémoire puis transférés sur le disque occasionnellement.

    Powered by Plone CMS, the Open Source Content Management System

    This site conforms to the following standards: