Optimisation de code et parallélisme

Georges-André Silber, École des mines de Paris

Cours

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()) et le traitement global de toutes les images (mesuré simplement avec time).

A 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.

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
    sir 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.

Optimisations

À chaque modification, relancer le code et mesurer le gain obtenu. Garder trace de chaque version de votre code avec le gain obtenu. Recommendations:

  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.

Parallélisation(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 cherche ici à améliorer le temps pris par le traitement des dix images à la suite. Se rappeler de fork().
  4. GPU: utiliser CUDA afin d'obtenir une version du code fonctionnant sur un processeur graphique.