Optimisation de code et parallélisme

Travaux pratiques: "Catch the Speedup"

L'objectif ce ces travaux pratiques est d'améliorer les perfomances d'un code C qui transforme des images, à la fois le coeur de la transformation (ce qui dans le code C que vous verrez ci-dessous est mesuré entre start_counter() et get_counter(), pour la version x86 et des appels à clock() dans le cas générique) et le traitement global de toutes les images (mesuré simplement avec time).

À priori, on ne connait pas la manière la plus rapide de faire tourner ce code: le gagnant de ce concours "Catch the Speedup" sera celle ou celui qui a obtenu la meilleure accélération du code.

Le code optimisé obtenu avec les différentes étapes sera à rendre à la fin de cette séance de travaux pratiques, ainsi qu'un tableau récapitulatif partant du temps initial sans optimisation, indiquant pour chaque nouvelle version le nouveau temps et l'accélération obtenue (speed-up).

Préliminaires

  1. Récupérer le code C et le compiler sur votre machine avec GCC, LLVM ou un autre compilateur C de votre choix.
  2. La compilation du code se fait avec la commande 
    make
    si vous êtes sous Linux (ou WSL2) ou macOS avec processeur Intel, ou avec 
    make -f Makefile.clock
    si vous être sous macOS avec processeur Arm.
  3. Récupérer les données image.
  4. Exécuter le code compilé précédemment de la façon suivante: 
    time ./transform_image $IMAGES/transfo.txt
    où IMAGES est une variable d'environnement qui pointe vers le répertoire où se trouvent les images récupérées précédemment: 
    export IMAGES=chemin-vers-les-images
    L'exécution devrait afficher quelque chose comme: 
    image1.pgm courbe1.amp 5 image1_t.pgm
image1.pgm: 5617 x 3684 = 20693028 pixels
1909743856.000000 clock cycles.
image2.pgm courbe2.amp 5 image2_t.pgm
image2.pgm: 5227 x 3515 = 18372905 pixels
1651530808.000000 clock cycles.
image3.pgm courbe3.amp 5 image3_t.pgm
image3.pgm: 6660 x 9185 = 61172100 pixels
6592744002.000000 clock cycles.
image4.pgm courbe4.amp 4 image4_t.pgm
image4.pgm: 3381 x 4914 = 16614234 pixels
1252728815.000000 clock cycles.
image5.pgm courbe5.amp 7 image5_t.pgm
image5.pgm: 3226 x 3255 = 10500630 pixels
1119565617.000000 clock cycles.
image6.pgm courbe6.amp 6 image6_t.pgm
image6.pgm: 3677 x 3677 = 13520329 pixels
1163077323.000000 clock cycles.
image7.pgm courbe7.amp 9 image7_t.pgm
image7.pgm: 3264 x 4896 = 15980544 pixels
1183738944.000000 clock cycles.
image8.pgm courbe8.amp 5 image8_t.pgm
image8.pgm: 1757 x 2636 = 4631452 pixels
443741534.000000 clock cycles.
image9.pgm courbe9.amp 7 image9_t.pgm
image9.pgm: 2498 x 3330 = 8318340 pixels
639985780.000000 clock cycles.
image10.pgm courbe10.amp 9 image10_t.pgm
image10.pgm: 3024 x 3024 = 9144576 pixels
572600880.000000 clock cycles.
TOTAL: 16529457559.000000 clock cycles.

real	0m57.843s
user	0m50.297s
sys	0m1.763s
  5. Lire le code et comprendre ce qu'il fait.

Machine de développement

La machine 51.159.179.226 vous permet de développer sur architecture x86_64 avec un processeur AMD EPYC 7413, avec 8 coeurs disponibles sur les 24 du processeur et 48 Go de RAM, et un GPU NVIDIA L4 avec 24 Go de RAM. Les outils de développements utiles comme GCC, OpenMP et Cuda sont installés, ainsi qu'un accès aux compteurs de performance via perf.

Pour utiliser cette machine, vous pouvez vous logguer avec SSH:

ssh LOGIN@51.159.179.226

votre LOGIN étant la première lettre de votre prénom suivi de votre nom (votre enseignant a positionné sur votre compte la clef SSH que vous lui aviez envoyé en début d'année).

Les données des images sont sous /home/gasilber/data_images.tar.gz. Vous pouvez recopier ce fichier sur votre compte. Pour récupérer le code initial, vous pouvez faire sur votre compte: 

git clone https://github.com/gasilber/tp_optim.git

L'utilisation de perf permet de récupérer des informations intéressantes sur l'exécution du code: 

perf stat -d ./transform_image ../data_images/transfo.txt
Performance counter stats for './transform_image ../data_images/transfo.txt':

            8584.55 msec task-clock                       #    0.999 CPUs utilized
                31      context-switches                 #    3.611 /sec
                0      cpu-migrations                   #    0.000 /sec
            49014      page-faults                      #    5.710 K/sec
        20159236922      cycles                           #    2.348 GHz                         (86.03%)
        412579279      stalled-cycles-frontend          #    2.05% frontend cycles idle        (86.09%)
        55870446625      instructions                     #    2.77  insn per cycle
                                                    #    0.01  stalled cycles per insn     (86.07%)
        10479414028      branches                         #    1.221 G/sec                       (84.71%)
            24832877      branch-misses                    #    0.24% of all branches             (85.56%)
        20810467797      L1-dcache-loads                  #    2.424 G/sec                       (85.90%)
        639224674      L1-dcache-load-misses            #    3.07% of all L1-dcache accesses   (85.65%)
          LLC-loads
          LLC-load-misses

        8.594129613 seconds time elapsed

        8.139940000 seconds user
        0.442236000 seconds sys

Variante: convolution

La fonction sharpen() présente dans le code transfo.c n'est pas utilisée. Elle permet d'améliorer la netteté de l'image: vous pouvez l'ajouter aux traitements effectués pour rendre le code plus difficile à optimiser.

Optimisations

À chaque modification, relancer le code et mesurer le gain obtenu. Garder trace de chaque version de votre code avec le gain obtenu (idéalement, créez un nouveau répertoire dans tp_optim avec votre code modifié). Recommandations:

  1. Utiliser moins de fonctions
  2. Mieux utiliser la mémoire (localité)
  3. Utiliser moins de boucles
  4. Vous pouvez vous aider de perf (si vous êtes sous Linux) pour analyser plus finement le comportement de votre code. Sous WSL2, vous pouvez suivre ces instructions pour installer perf. Sous macOS, l'outil Instruments de XCode permet d'obtenir des informations équivalentes.

Parallélisation(s)

Avant de vous lancer dans l'implémentation, identifiez de manière abstraite les portions de code qui pourraient être parallélisées et réfléchissez à une modification des algorithmes utilisés.

Voici des pistes de parallélisation, qui peuvent être complémentaires:

  1. Vectorisation: utiliser les instructions vectorielles, soit en optimisant l'assembleur "à la main", soit en utilisant les intrinsics x86 présents dans GCC, soit en utilisant les bons paramètres du compilateur. Cette étape nécessitera certainement d'aider le compilateur en lui présentant des boucles "facilement" vectorisables. Vérifiez également que GCC génère du code correspondant à votre machine. La documentation Intel sur l'optimisation de code pour architecture x86-64 donne de nombreuses pistes d'optimisation.
  2. Multithreads: utiliser OpenMP pour obtenir une version du code utilisant plusieurs threads. Mesurer le gain obtenu en fonction du nombre de threads utilisés.
  3. Multiprocessus: modifier le code en utilisant plusieurs processus. On peut imaginer ici que l'on utilise des processus en parallèle où chaque processus s'occuperait d'une image. Ainsi, on pourra chercher ici à améliorer le temps pris par le traitement des dix images à la suite (se rappeler de fork()). Vous pouvez augmenter le nombre d'images (en ajoutant les vôtres ou en dupliquant plusieurs fois la même) si vous voulez tester votre code quand le nombre d'images est plus grand.
  4. GPU: utiliser CUDA afin d'obtenir une version du code fonctionnant sur un processeur graphique.