Traitement de linformation Programmation massivement parallèle Arrière plan: Nvidia.frNvidia.fr Benoît Pencrec'h

Traitement de l’information

Programmation massivement parallèle

Arrière plan: Nvidia.frBenoît Pencrec'h

1 - Convolution matricielle et processeur graphique : un couple idéal 1.1 - Convolution et complexité arithmétique

1.2 - Les processeurs graphiques, une architecture taillée pour le calcul 1.3 - Un couple permettant une exécution hautement parallèle

2 - Implémentations et optimisations 2.1 - Programmer sur GPU avec l’API Cuda™

2.2 - Convolution 2D 2.3 - Convolution 2D optimisée 2.4 - Convolution 3D, une histoire de boucle…

3 - Résultats : qualité, performances et limites 3.1 - Qualité des résultats 3.2 - Benchmark des convolutions 2D et 3D 3.3 - Les transferts mémoires, goulot d’étranglement 3.4 - Un autre moyen d’exécuter la convolution : Fourrier

11/04/23 2Benoît Pencrec'h

Convolution et complexité arithmétiqueConvolution et complexité arithmétique

Convolution matricielle et processeur graphique : un couple

idéal

• La convolution mesure la quantité de chevauchement entre deux fonctions

Implémentations et optimisations Résultats : performances et limites

11/04/23 Benoît Pencrec'h 3

• Pour des termes de type discret elle s’exprime

• La convolution d’un pixel N d’une image I par un noyau K de rayon R s’exprime :



idéalImplémentations et optimisations Résultats : performances et

limites


Noyau

Pixel source

Pixel résultat

Schéma : université Harvay Mudd

http://fourier.eng.hmc.edu/e161/lectures/convolution/index.html







limites


• Pour une image de taille m . m et un noyau de taille n . n, la convolution demande n² . m² multiplications

• En 3D, la convolution requiert n³. m³ multiplications !

30 s pour convoluer une image 8192.8192 Px (noyau 9.9)

7 min 30 s pour convoluer un volume 1024.1024.1024 Px (noyau 3.3.3)




limites


• Il existe une solution pour diminuer le nombre de calculs :

abaisse le nombre de multiplications à 2n.m² en 2D et 3n.m³ en 3D

la séparation du noyau

Schémas : réalisation personnelle

Les processeurs graphiques, une architecture taillée pour le calculLes processeurs graphiques, une architecture taillée pour le calcul



limites


• Habituellement destinés aux rendus de scènes 3D (jeux vidéos, CAO, …)

• Gère moins d’instructions que le CPU mais possède une puissance de calcul brute bien plus importante

• Autrefois spécialisé dans la 3D, ils est devenu universel




limites


Puissance de calcul des GPU Nvidia vs CPU Intel

Graphe : nvidia programming guide

http://developer.nvidia.com/object/gpu_programming_guide.html

GPU




limites


CPU

Schémas : nvidia programming guide








limites


Stream Processor

• 1 thread

• Exécution séquentielle

• 2 ko de registres









limites


• 8 threads (bloc)

• Exécution parallèle

• 16 ko de mémoire partagée

SIMT(Single Instruction Multiple Threads)









limites


• plusieurs SIMT

• exécution parallèle

• mémoire globale

GPU Complet






Un couple permettant une exécution hautement parallèleUn couple permettant une exécution hautement parallèle



limites


• Pour exprimer leur puissance, les GPU requièrent des calculs indépendants

• La convolution possède cette particularité :

chaque pixel résultat est une somme de produits indépendante du résultat voisin

• L’utilisation de la convolution sur processeurs graphiques est donc pertinente

Programmer sur GPU avec l’API Cuda™Programmer sur GPU avec l’API Cuda™



limites


• CUDA™ Compute Unified Device Architecture

• API propriétaire apparue en 2006 avec l’architecture G80 (Ge force 8)

• Se présente comme une extension du langage C (compilateur spécifique NVCC)

• Permet d’écrire des fonctions C dénommées Kernels qui seront exécutées N fois en parallèle sur N différents threads




limites


• Chaque thread va effectuer une des additions• N additions seront exécutées simultanément

Kernel GPU Parallèle

Code CPU Séquentiel

// Kernel definition__global__ void VecAdd(float* A, float* B, float* C){int i = threadIdx.x;C[i] = A[i] + B[i];}

int main(){...// Kernel invocation with N threadsVecAdd<<<1, N>>>(A, B, C);}

Addition de vecteurs en Cuda

Extraits de code : nvidia programming guide








limites


• Pour simplifier l’exécution de tâches plus complexes, les threads bénéficient d’une hiérarchie bien définie.

• L’indice de thread (threadId) peux prendre une (thradId.x) deux (threadId.y) ou trois (threadId.z) dimensions.

• Apparaissent dès lors blocs de threads (blockId) à une deux ou trois dimension suivant la même structure.

• L’ensemble des blocs forment une grille de thread (1D ou 2D mais pas 3D) qui est ensuite envoyée au GPU




limites


Représentation de la grille de thread









limites


// Kernel definition__global__ void MatAdd(float A[N][N], float B[N][N],float C[N][N]){int i = threadIdx.x;int j = threadIdx.y;C[i][j] = A[i][j] + B[i][j];}

int main(){...int numBlocks = 1;dim3 threadsPerBlock(N, N);MatAdd<<<numBlocks, threadsPerBlock>>>(A, B, C);}

Addition de matrices en Cuda

Appel du kernel avec 1 bloc de N*N threads

Chaque thread du bloc exécute une addition

Extraits de code : nvidia programming guide



Convolution 2DConvolution 2D



limites


• On découpe l’image en blocs de 16*16 threads

• Chaque pixel résultat est calculé par un thread

• Un thread exécute séquentiellement les sommes / produits nécessaires au calcul d’un pixel résultat

• Tous les pixels résultats sont calculés en parallèle




limites

11/04/23 Benoît Pencrec'h 20Schémas : réalisation personnelle

• Il reste cependant un problème : les effets de bord




limites

11/04/23 Benoît Pencrec'h 21Schémas : réalisation personnelle

• solution : placer des zéros autour de l’image

• Dans le kernel on choisira de faire des tests sur les indices de thread (plus performant)

Convolution 2D optimiséeConvolution 2D optimisée



limites


l’exécution est divisée en deux passes (i.e. deux kernels)

Une passe horizontale qui traite des rangées de 16 pixels

Une passe verticale traite des colonnes 16 pixels

• Cette implémentation est basée sur l’exemple ConvolutionSeparable du SDK Nvidia™

• Première optimisation : utilisation de la convolution séparable

Convolution 2D optimiséeConvolution 2D optimisée



limites


• Deuxième optimisation : chargement de l’image directement dans la mémoire partagée du GPU (mémoire shared)

Sans mémoire shared Avec mémoire shared


Convolution 3D, une histoire de boucle…Convolution 3D, une histoire de boucle…



limites


Z slices

z

xy

Z slices

Schémas : réalisation personnelle

• Problème : on ne peux pas définir une grille de thread en 3D• Solution : On découpe le volume en slices traitées par nos kernels 2D




limites


• Cette méthode nécessite cependant d’adapter les kernels 2D

Le noyau étant 3D, les kernels doivent récupérer les valeurs des slices les entourant




limites

11/04/23 Benoît Pencrec'h 26Illustration : réalisation personnelle

noyaun-1

5

noyaun

10

noyaun+1

5

Slice volume n-1

Slice volume n+1

Slice volume n

Z

Slice volume n

20

Qualité des résultatsQualité des résultats



limites


La qualité (i.e la justesse) des résultats est constamment vérifiée par :

• Le calcul de la norme relative entre l’implémentation CPU et la version GPU (contrôle automatique)

• L’export des images et volumes résultats dans un fichier (contrôle visuel)

Image d’origine Image covoluée (Gauss) CPU Image covoluée (Gauss) GPU

Illustration: réalisation personnelle

Benchmark des convolutions 2D et 3DBenchmark des convolutions 2D et 3D



limites


Fabriquant et modèle

Nombre de cœurs

Fréquence des cœurs

CPU Intel Xeon L5320 4 2.5 GHz

GPU Nvidia Geforce GTX295

280 1.24 GHz

Système de test




limites


x2,5




limites


x3

Les transferts mémoires, goulot d’étranglementLes transferts mémoires, goulot d’étranglement



limites


x65 !

Les transferts mémoires, goulot d’étranglementLes transferts mémoires, goulot d’étranglement



limites


Un autre moyen d’exécuter la convolution : FourrierUn autre moyen d’exécuter la convolution : Fourrier



limites



Une expérience enrichissanteUne expérience enrichissante

•Cuda est un langage simple à mettre en œuvre donnant de bons résultats

•Au cours de ce stage j’aurai:•Acquis une bonne connaissance des GPU et de la programmation parallèle,•Appris à interfacer des fonctions C et CUDA avec Matlab,•Utilisé un outil de versionning de Code,•Familiarisé avec un OS libre,•Appris à développer sans IDE en utilisant l’outil Make et les makefiles,•Approfondi mes connaissances en langage C.

Sources Sources

• Index de la documentation Nvidia CUDASite : http://developer.nvidia.com/

•Université Harvay MuddSite : http://fourier.eng.hmc.edu/


Documents

Traitement de linformation Programmation massivement parallèle Arrière plan: Nvidia.frNvidia.fr Benoît Pencrec'h