Méthodologie de placement d’algorithmes de traitement d’images sur architecture massivement parallèle

Le GPU est une architecture initialement dédiée au calcul pour applications graphiques. Les nombres de publications scientifiques annuelles à son sujet,  montre une popularité en constante hausse ces dernières années. Son application au calcul scientifique généraliste intitulé, General-purpose Processing on Graphics Processing Units (GPGPU), a de même connu un fort essor jusqu’en 2014. Les publications de la communauté scientifique à ce sujet tendent depuis à diminuer lentement. Pourtant, le GPU est couramment cité pour les applications de calcul intensif, où il est présenté comme une architecure de choix du fait de sa forte puissance de calcul. publiée par Nvidia, met en avant le nombre d’unités de calcul des GPUs.

Aujourd’hui, le GPU est couramment relié à d’autres sujets tels que l’intelligence artificielle, les réseaux de neurones, le machine learning ou encore le deep learning. Mais le GPU est aussi massivement utilisé dans le domaine de la finance et plus précisément sur un sujet d’actualité très médiatisé, celui des crypto monnaies. Cette devise virtuelle que l’on «mine», nécessite une puissance de calcul élevée. La masse de calcul produite génère alors une valeur lucrative. Cependant, afin d’optimiser le rendement des ces opérations financières, l’efficience énergétique de l’architecture utilisée revêt un aspect important. Le GPU étant un bon candidat à ce sujet, il est fait état en 2018 d’une pénurie des GPUs liée à l’eldorado des crypto monnaies. Suivant le marché de l’offre et de la demande, une hausse des prix de ces processeurs est actuellement redoutée.

Dans le domaine industriel et plus particulièrement dans l’embarqué, nous retrouvons le GPU dans les équipements automobiles. Celles-ci sont développées par plusieurs grands constructeurs du monde automobile tels qu’Audi, Mercedes, Tesla, Toyota, Volvo ou encore Volkswagen. Tesla, en particulier, utilise un GPU pour analyser l’environnement du véhicule et offrir des fonctions de pilotage automatique voire de conduite totalement autonome. Cependant, pour arriver à un tel niveau d’avancée technologique et surtout un niveau de fiabilité indispensable, il est nécessaire de travailler sur une quantité et une qualité suffisante de données. Ce point explique le nombre élevé de capteurs inclus dans les voitures modernes. Par exemple, le model S chez Tesla propose de série une unique caméra. En option, la fonction de pilotage automatique requiert l’utilisation de trois caméras supplémentaires, tandis que la conduite autonome nécessite encore quatre caméras de plus, portant le total à huit caméras embarquées. À cet ensemble vient s’ajouter les autres senseurs non vidéo tels que les capteurs de type LIght Detection And Ranging (LIDAR).

L’héritage des GPUs

Une «étrange maladie» a touché nos processeurs au début du 21ème siècle. Alors que leurs performances étaient jusque là sans cesse améliorées, un effet de plafonnement est venu opérer. La structure même des Central Processing Unit (CPU)s ne permettait alors plus d’augmenter leurs fréquences de fonctionnement. La solution pour contourner ce problème a été de multiplier les cœurs de calculs au sein des processeurs. La scalabilité de ces derniers était alors rendue possible par l’exploitation du parallélisme. Cependant, alors que nous étions aveuglés par des performances calculatoires toujours plus élevées, les performances des transferts de données n’ont pas connu la même évolution. Hennessy et Patterson dans leur ouvrage de référence [75] font référence à ce constat. Afin de palier à cette contrainte, de nouveaux ensembles d’instructions tels que MultiMedia eXtension (MMX), Streaming SIMD Extensions (SSE) puis Advanced Vector Extensions (AVX) ont été ajoutés aux jeux d’instructions des CPUs. Ces instructions, à l’origine prévues pour les applications multimédia, permettent d’exploiter des unités de calculs vectoriels dont le but est de regrouper une ou plusieurs opérations sur un même bloc de données consécutives. Au sein de la taxynomie de Flynn [60], cette approche architecturale est de type Single Instruction on Multiple Data (SIMD).

Dans le domaine du rendu graphique, l’application récurrente de certains patterns, ainsi qu’une augmentation sans fin des volumes de données à traiter, ont engendré la création de processeurs dédiés à l’accélération graphique. C’était le début des GPUs. Leur ambition était d’accélérer les temps de rendu pour atteindre le temps réel, mais aussi d’améliorer la qualité de rendu des scènes tri–dimensionelles pour le domaine des jeux vidéo. Ce marché très porteur a permis aux industriels de faire progresser le concept des GPUs basé sur une approche vectorielle pour arriver à une architecture massivement parallèle de type Single Instruction Multiple Thread (SIMT). Ces capacités calculatoires se comptent en teraflops pour plusieurs centaines, voire milliers, de cœurs de calcul tandis que la bande passante mémoire se compte en centaines de giga-octets par seconde.

Les différents acteurs 

En 2018, trois principaux acteurs sont présents dans le domaine des GPUs. Intel, Nvidia et Advanced Micro Devices (AMD) se partagent l’héritage d’un passé où les GPUs n’étaient utilisés que dans l’unique but d’accélérer les calculs de rendu de scènes en trois dimensions. Avec l’avènement des GPUs intégrés dans les architectures embarquées telles que les smartphones et les tablettes tactiles, d’autres acteurs sont venus s’ajouter dans le cadre de ce marché de niche exclusivement. Dans le domaine du High Performance Computing (HPC), en novembre 2017, la gamme Tesla de Nvidia se retrouve en concurrence avec le Xeon Phi d’Intel, dans les dix premiers super-calculateurs du classement top500 [10].

Intel
L’entrée d’Intel dans le domaine des GPUs remonte à 1998 avec son processeur graphique Intel740. S’en suivront une seconde génération intitulée Extreme Graphics au tout début des années 2000 puis plusieurs générations liées à l’architecture Intel Graphics Media Accelerator (Intel GMA). Il faudra cependant attendre la génération Intel HD Graphics, en 2013, pour avoir une utilisation de type GPGPU. Cependant, la stratégie d’Intel est d’intégrer dans le même System On Chip (SOC) que ses CPU  un GPU servant à la fois pour les rendus graphiques mais aussi pour effectuer du calcul vectoriel en partageant un même espace mémoire. Ce choix stratégique explique le leadership d’Intel en terme de GPUs vendus. Cependant, ces unités, appelées Integrated Graphics Processor (IGP), sont optimisées pour une faible consommation énergétique au prix d’une puissance de calcul modérée. Afin de palier ce problème, la série de GPUs Iris Graphics est venue renforcer l’offre d’Intel. Il s’agit de la même base architecturale que la série Intel HD mais paramétrée pour apporter une puissance de calcul supérieure. La série Iris Pro Graphics embarque en supplément une mémoire interne dont la taille est de l’ordre de 100MB. Enfin, en 2017, avec l’architecture Coffee Lake, la dénomination des IGP Intel HD a été modifiée par Ultra HD. Avec au plus un peu moins de 600 cœurs de calcul et une mémoire interne de 100MB, l’ensemble de ces solutions ne permet pas d’atteindre à génération égale le niveau de performance des GPUs dédiés de Nvidia ou d’AMD. Ce constat s’explique par le choix d’Intel d’utiliser une approche architecturale fondamentalement différente. Ce choix puise ses origines dans l’architecture Larrabee qui s’avèrera être un échec à cause de sa complexité de mise en œuvre. Elle permettra cependant de poser les bases de l’architecture Xeon Phi dédiée au calcul vectoriel haute performance. Cette architecture en concurrence avec les GPGPUs est en réalité une architecture manycores de type x86 basée sur une topologie en anneau et utilisant massivement des instructions de type SIMD comme l’AVX 512. Celle-ci est donc, en toute logique, fortement impactée par la problématique de coalescence dans ses accès aux données mémoire.

AMD / ATI

Initialement spécialisées dans les CPUs à architecture x86, les solutions graphiques proposées par AMD sont issues de l’héritage d’Array Technologies Incorporated (ATI), suite à son rachat en 2006. On retrouve principalement les solutions GPUs d’AMD dans le domaine des jeux vidéos, notamment avec les consoles de jeux Playstation 4 de Sony et Xbox One de Microsoft. Nintendo a longtemps employé les solutions graphiques d’AMD dans ses consoles de jeux vidéos. Cependant, en 2017, l’entreprise a décidé de changer de stratégie en utilisant l’architecture Tegra X1 de Nvidia pour sa console Switch. L’architecture TeraScale est la première de type GPGPU grâce à la libération du pipeline graphique fixe. Trois générations se succéderont. L’approche architecturale est basée sur un jeu d’instruction de type Very Long Instruction Word (VLIW) et SIMD. L’architecture Graphics Core Next (GCN) qui a succédé en 2011 à l’architecture TeraScale, connaîtra en 2019 sa 6ième génération intitulée Navi. GCN se différencie de son aînée par l’utilisation d’un jeu d’instructions de type Reduced Instruction Set Computer (RISC) et SIMD ce qui la classifie au final comme une architecture SIMT et la rapproche ainsi des architectures de son concurrent Nvidia.  Pour le domaine du HPC, AMD propose une gamme Fire Pro comparable à la gamme Tesla chez Nvidia. Concernant le domaine de l’embarqué, AMD propose un Accelerated Processing Unit (APU) intégrant un CPU et un GPU basé sur les architectures TeraScale puis GCN dans un unique SOC. Les deux processeurs partagent alors le même espace mémoire. C’est ce modèle de processeur qui est utilisé dans les solutions pour consoles de jeux proposées par AMD.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport-gratuit.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Introduction générale
1 Contexte
1.1 L’héritage des GPUs
1.2 Les différents acteurs
1.2.1 Intel
1.2.2 AMD / ATI
1.2.3 Nvidia
1.2.4 Autres acteurs
1.3 Architecture générale des GPUs
1.3.1 Le flot calculatoire
1.3.2 Le flot de données
1.3.3 Le flot d’instructions
1.4 Interfaces de programmation pour GPU
1.4.1 OpenGL
1.4.2 Direct Compute / Direct3D
1.4.3 Cuda
1.4.4 OpenCL
1.4.5 BrookGPU
1.4.6 ATI Stream / CTM
1.4.7 AMD Mantle
1.4.8 Vulkan
1.4.9 Apple Metal
1.4.10 Conclusion
1.5 Le GPU en traitement d’images
1.5.1 OpenCV
1.5.2 GpuCV
1.5.3 CUDA NPP
1.5.4 ArrayFire
1.5.5 Intel IPL
1.5.6 CLIPP
1.5.7 Matlab Parallel Computing Toolbox
1.5.8 DSLs de traitement d’images
1.5.9 OpenVX
1.5.10 Conclusion
1.6 Conclusion
2 État de l’art : placement sur GPU
2.1 Transformation par annotation de directives
2.1.1 HMPP
2.1.2 hiCUDA
2.1.3 OpenMP
2.1.4 “OpenMP C to CUDA”
2.1.5 OpenMPC
2.1.6 Mint
2.1.7 GPSME
2.1.8 OpenACC
2.1.9 PGI Accelerator
2.2 Transformation automatique de code
2.2.1 C-to-CUDA
2.2.2 PIPS et Par4All
2.2.3 PPCG
2.2.4 R-Stream
2.2.5 Togpu
2.3 Squelettes algorithmiques
2.3.1 SkePU/SkePU2
2.3.2 SkelCL
2.3.3 Thrust
2.3.4 Bones
2.4 Optimiseurs GPU
2.4.1 CUDA-Lite
2.4.2 Optimiseur de placement de code GPU
2.4.3 GPUCC
2.5 Conclusion
3 Méthodologie de placement
3.1 Analyses de code statique
3.1.1 Identification des appels de fonction
3.1.2 Identification des boucles
3.1.3 Identification des accès aux espaces mémoire
3.1.4 Identification des branchements
3.1.5 Identification des blocs de base
3.1.6 Construction de la représentation spinale du programme
3.1.7 Analyse des boucles
3.1.8 Analyse des fonctions d’accès mémoire
3.1.9 Analyse des dépendances
3.1.10 Catégorisation des boucles
3.1.11 Complétion de la représentation spinale
3.2 Analyses de code dynamique
3.3 Conditions nécessaires au placement sur GPU
3.3.1 Critère 1 : Structure et profondeur du nid de boucles d’un kernel
3.3.2 Critère 2 : Taille des domaines d’itération
3.3.3 Critère 3 : Empreinte mémoire
3.3.4 Sélection d’un kernel
3.4 Amélioration de la quantité de code placé sur GPU
3.4.1 Fusion de boucles
3.4.2 Fission ou distribution de boucles
3.4.3 Coalescing
3.4.4 Index set splitting
3.4.5 Strip mining
3.4.6 Tiling
3.4.7 Interchange
3.4.8 Unrolling
3.4.9 Les réductions parallèles
3.4.10 Conclusion
3.5 Préparation avant la génération de code
3.5.1 Ordonnancement des instances de threads
3.5.2 Déplacement de blocs inter-boucles GPU
3.5.3 Normalisation des espaces d’itération
3.5.4 Linéarisation des accès mémoire
3.6 Génération de code pour GPU
3.6.1 Outlining des kernels cuda
3.6.2 Allocation des tableaux
3.6.3 Création des communications hôte/accélérateur
3.6.4 Génération des appels de kernel
3.7 Mécanisme de validation/invalidation de kernels
3.8 Conclusion
Conclusion générale

Rapport PFE, mémoire et thèse PDFTélécharger le rapport complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.