Introduction à la programmation GPU - Part 1
Motivations
La programmation GPU a souvent mauvaise réputation auprès des développeurs. Elle est considérée comme très difficile, réservée à des spécialistes techniques souvent répartis dans des domaines de niches réclamant des performances accrues : Simulation en Calcul scientifique, Imagerie médicale, Dynamiques des Fluides, Protection de l’environnement, Calculs financiers en salle de marché ...
L’arrivée de la nouvelle librairie Microsoft C++ Accelerated Massive Parallelism (Microsoft C++ AMP) est sans aucun doute un évènement important pour la communauté des développeurs Microsoft. Naturellement, les développeurs .NET sont un peu déçus, car pour l’instant, il n’y a pas d’implémentation GPU pour le Framework .NET, planifiée du côté de Redmond, mais les équipes y réfléchissent. Cependant, si vous souhaitez développer en .NET sur GPU, la société Tidepowerd (https://www.tidepowerd.com/) fournit une belle implémentation .NET, avec sa librairie GPU.NET (http:/www.tidepowerd.com/product).
Pour une grande majorité des acteurs concernés par la programmation GPU, l’annonce de la nouvelle librairie Microsoft C++ AMP a suscité à la fois curiosité et étonnement. Pourquoi Microsoft annonce une nouvelle librairie pour traiter du calcul sur GPU alors que nVIDIA CUDA et OpenCL occupent déjà ce territoire ? La programmation GPU n’étant pas très populaire, je souhaitais vous présenter ces technologies à travers une série d’articles. L’objectif est de vous initier aux rudiments de ces technologies en utilisant systématiquement le même algorithme.
Dans cette introduction, je vous présenterai dans un premier temps les différentes technologies GPU que nous allons étudier : nVIDIA CUDA C, OpenCL et Microsoft C++ AMP. J’ai éliminé l’illustration avec l’API Microsoft Direct Compute (https://en.wikipedia.org/wiki/DirectCompute), car elle m’a semblé moins pertinente au regard de l’arrivé de la librairie Microsoft C++ AMP. Dans un second temps, je vous présenterai l’algorithme sélectionné pour toutes nos implémentations. Puis nous mesurerons sa performance en mode séquentiel. Enfin, nous terminerons cette introduction par l’utilisation de la librairie Microsoft Parallel Patterns Library (https://msdn.microsoft.com/en-us/library/dd492418.aspx), pour paralléliser notre code exemple sur CPU.
Pour éviter tout malentendu, la programmation GPU est particulièrement bien adaptée au parallélisme orienté donnée et non orienté tâche. En d’autres mots, si votre problème est dominé par un volume de données conséquent qui doit être traité par une unique méthode, alors vous pouvez tirer parti d’une solution orientée GPU. Sur la plateforme .NET la librairie PLINQ répond à cette caractéristique, mais en général toutes les boucles parallèles sont du parallélisme orienté données.
Présentation des différentes technologies
nVIDIA CUDA C
Le Framework nVIDIA CUDA (https://www.nvidia.com/object/cuda_home_new.html) connait un succès grandissant depuis sa sortie en 2007. Il fait aujourd’hui office de standard dans de nombreuses entreprises. Par exemple l’offre Microsoft HPC Server arrive avec une distribution nVIDIA CUDA afin de permettre aux développeurs d’implémenter des solutions hybrides, mélangeant par exemple les technologies MPI (https://en.wikipedia.org/wiki/Message\_Passing\_Interface), OpenMP (https://en.wikipedia.org/wiki/OpenMP) et nVIDIA CUDA C. L’objectif est naturellement de tirer le maximum de puissance des matériels disponibles sur chacun des nœuds d’une grille HPC. Aujourd’hui, il existe un véritable écosystème nVIDIA CUDA permettant de profiter de nombreuses librairies optimisées et déclinées sur différents langages. On y trouve aussi de l’outillage sophistiqué afin de profiler et de déboguer graphiquement sous Visual Studio, portant le développement GPU a une maturité proche du développement sur CPU. Par nature le code nVIDIA CUDA s’exécute exclusivement sur des matériels nVIDIA supportant l’architecture CUDA à la fois sous Windows, UNIX et MAC.
OpenCL
Dans un passé, plus récent, le standard ouvert OpenCL (Open Computing Language : https://www.khronos.org/opencl) supporté par le groupe khronos, a commencé à rencontrer un franc succès, car son indépendance vis-à-vis du matériel et de la plateforme d’exécution lui offre un atout que nVIDIA CUDA n’offre pas. En effet, OpenCL permet de produire un code source portable (OpenCL s’exprime en langage C), tout en acceptant de paralléliser des traitements sur CPU ou sur GPU ou bien les deux. Portable sur différents systèmes d’exploitation, différents types de cartes graphiques, OpenCL a de quoi séduire les plus exigeants.
Microsoft C++ AMP
La librairie Microsoft C++ AMP s’inscrit sur un autre terrain : elle est écrite nativement en C++ et supporte aussi la programmation parallèle sur GPU et CPU. En interne, elle repose sur DirectX (https://en.wikipedia.org/wiki/DirectX) et de ce fait, elle supporte un grand nombre de matériels. Cependant, sa vocation est de s’exécuter sur des systèmes d’exploitation Microsoft Windows à l’instar des librairies parallèles Microsoft C++ Parallel Patterns Library (PPL) et Asynchronous Agents Library (AAL) de Visual Studio 2010. Contrairement aux technologies précédentes, Microsoft C++ AMP, n’est pas encore finalisé. Cette nouvelle librairie viendra épouser l’écosystème de la prochaine version de Visual Studio. L’intention affichée par Microsoft est de démocratiser la programmation GPU en proposant un écosystème de développement simple et efficace. L’accent n’est donc pas placé sur « la performance à tout prix », mais sur « la facilité d’utilisation ». Enfin, Microsoft souhaite standardiser les spécifications de Microsoft C++ AMP afin que d’autres sociétés puissent implémenter librement les interfaces Microsoft C++ AMP sur d’autres plateformes plateforme.
Présentation de l’algorithme
S’il existe une version « Hello world » pour la programmation GPU, c’est sans aucun doute l’algorithme du produit matriciel (https://en.wikipedia.org/wiki/Matrix_multiplication). Cet exemple est très souvent repris en introduction des ouvrages ou des cours abordant la programmation GPU. Voici une déclinaison en langage C d’un produit matriciel engageant une matrice A et une matrice B carrées de taille size, engendrant la matrice C.
void MatrixMultiplyOrig(float** A, float** B, float** C, int size)
{
for (int i = 0; i < size; ++i) {
for (int j = 0; j < size; ++j) {
float sum = 0;
for (int k = 0; k < size; ++k) {
sum += A[i][k]*B[k][j];
}
C[i][j] = sum;
}
}
}
Implémentation du produit matriciel version séquentiel
Dans notre exemple nous disposons de deux matrices carrées A et B de taille size que nous allons parcourir à travers 3 boucles imbriquées où la plus interne va itérer la variable k sur les lignes de la matrice A et sur les colonnes de la matrice B, la variable i itère les colonnes de la matrice A et la variable j itère les lignes de la matrice B. Ainsi nous pouvons calculer le produit de chacune des valeurs de A et de B et engendrer toutes les valeurs dans la matrice C.
Bien que parfaitement correct, le code présenté ci-dessus n’est pas celui que l’on retrouve dans la littérature GPU. En effet, la carte graphique préfère manipuler des vecteurs plutôt que des structures comme des tableaux. Alors, comment passer d’une matrice à deux dimensions à un simple vecteur ?
Par exemple, prenons le cas de la matrice A, où nous avons coloré chaque ligne en une couleur différente.
Nous pouvons aligner chaque ligne de la matrice A[4,4] de manière à obtenir un long vecteur de 16. Appliquez ce principe à toutes matrices et modifiez légèrement l’algorithme initial, vous obtenez un code parfaitement compatible avec les technologies parallèles sur GPU. Le code ci-dessous représente le code adapté pour calculer sur des vecteurs.
static const int _SIZE = 1024;
float* _A;
float* _B;
float* _C;
Déclaration des matrices A, B et C
_A = new float[_SIZE *_SIZE];
_B = new float[_SIZE *_SIZE];
_C = new float[_SIZE*_SIZE];
for (int i = 0; i < _SIZE*_SIZE; ++i) {
_A[i] = 1;
}
for (int i = 0; i < _SIZE*_SIZE;; ++i) {
_B[i] = 1;
}
Le code d’initialisation des matrices A, B et C
void MatrixMultiply(float* A, float* B, float* C, int size)
{
for (int i = 0; i < size; ++i) {
for (int j = 0; j < size; ++j) {
float sum = 0;
for (int k = 0; k < size; ++k) {
sum += A[i * size + k] * B[k * size + j];
}
C[i * size + j] = sum;
}
}
}
Implémentation du produit matriciel version séquentiel compatible CPU
MatrixMultiply(_A, _B, _C, _SIZE);
Code d’appel de la méthode
for (int i = 0; i < _SIZE*_SIZE; ++i) {
sum += _C[i];
}
Calculer la valeur réduite du vecteur C
Pour nous bâtir une référence vis-à-vis de nos prochaines adaptations parallèles, je vous propose le résultat du temps d’exécution de cet algorithme pour des matrices de tailles 1024 * 1024, initialisées avec la valeur 1 pour chaque cellule. Le programme s’exécute en x64 en mode Release sur un Intel Core i7 2820 QM.
Compilation 64bit avec Visual C++
Si vous utilisez un projet Visual C++, et que vous souhaitiez passer votre projet en C++ de Win32 à x64, vous devez modifier la configuration de votre projet vous-même. Par défaut, les projets Visual C++ sont configurés en 32bit. Pour passer en 64bit vous devez passer par le Configuration Manager (Build-> Configuration Manager … ), et choisir dans la liste « Active solution platform »: x64. Vous pouvez appliquer cette modification pour tous vos modes de compilation Release et Debug.
Une fois votre projet activé sur la plateforme de votre choix, vous pouvez compiler le code exemple et le lancer en mode Release de préférence.
Le programme a tourné en 8 secondes et 455 centièmes, ce qui constitue notre valeur de référence.
Microsoft PPL et le produit matriciel
Afin de mieux apprécier les gains de performances de nos futures versions sur GPU, il est très tentant d’évaluer le gain obtenu en utilisant la librairie Microsoft Parallel Patterns Library (PPL). La librairie PPL est finalement très proche de la librairie Intel Threading Building Blocks (TBB) (https://threadingbuildingblocks.org), mais si vous utilisez Visual Studio 2010, vous disposez par défaut de cette librairie. Par exemple, si nous utilisons la méthode parallel_for (https://msdn.microsoft.com/en-us/library/dd505035.aspx), pour obtenir une version parallèle de notre algorithme, nous obtenons le code ci-dessous. Si la syntaxe des lambdas expressions ne vous est pas familière, vous trouverez quelques explications sur leurs usages sur ce lien https://blogs.msdn.com/b/vcblog/archive/2008/10/28/lambdas-auto-and-static-assert-c-0x-features-in-vc10-part-1.aspx.
void MatrixMultiplyParallelFor(float* A, float* B, float* C, int size)
{
for (int y = 0; y < size; ++y) {
parallel_for(0, size,[=](int x) {
float sum = 0;
for (int i = 0; i < size; ++i) {
sum += A[y * size + i] * B[i * size + x];
}
C[y * size + x] = sum;
});
}
}
Implémentation du produit matriciel version parallèle sur CPU avec la librairie Microsoft PPL et la méthode parallel_for
Le programme a tourné en 3 secondes et 448 centièmes, ce qui constitue un résultat raisonnable sur une machine contenant un processeur avec 4 cœurs physiques.
Nous pouvons tenter de gagner en performance en n'utilisant pas la méthode parallel_for, mais le type task_group de base de la librairie PPL.
void MatrixMultiplyTasks(float* A, float* B, float* C, int size)
{
task_group* task_groups = new task_group[size];
for (int i = 0; i < size; ++i) {
task_groups[i].run([=]() {
for (int j = 0; j < size; ++j) {
float sum = 0;
for (int k = 0; k < size; ++k) {
sum += A[i * size + k] * B[k * size + j];
}
C[i * size + j] = sum;
}
});
}
for (int i = 0; i < size; ++i) task_groups[i].wait();
delete [] task_groups;
}
Implémentation du produit matriciel version parallèle sur CPU avec la librairie Microsoft PPL et le type task_group.
Le code est un peu plus complexe, mais reste lisible.
Le programme a tourné en 2 secondes et 91 centièmes, ce qui est excellent, mais légèrement plus compliqué à implémenter. Les différences de performances entre les deux versions s’expliquent par la simplicité de la seconde implémentation au regard de méthode parallel_for qui est beaucoup plus complète sur la gestion d’erreurs potentielles ou la capacité à répartir la charge.
En conclusion
La programmation parallèle orientée données sur CPU est simple à mettre œuvre, mais peut être rapidement limitée par le nombre de cœurs disponibles. Avec cette dernière implémentation, nous sommes sans doute proches des performances maximums sur un processeur quad-cœurs. Et même si un temps d’exécution de 2 secondes peut sembler négligeable vis-à-vis d’une seule exécution, que peut-on dire si notre application engendre des millions de calculs à la fois. Sur des machines de type serveur, le nombre de cœurs peut être bien plus élevé, mais le cout des threads sous-jacents peut devenir rapidement pénalisant. Les architectures massivement multi-cœurs reposent sur des architectures matérielles complexes où des ilots de processeurs/cœurs se partagent la mémoire de la machine, on parle alors d’architecture matérielle type NUMA (https://en.wikipedia.org/wiki/Non-Uniform_Memory_Access). Le parallélisme orienté donnée est souvent touché par le phénomène appelé False Sharing (http:/en.wikipedia.org/wiki/False_sharing) qui peut engendrer des pertes de performances non négligeables. Nous sommes alors face à un problème que seules les GPU savent résoudre.
La prochaine fois, nous rentrerons dans le vif du sujet avec une solution reposant sur le Framework nVIDIA CUDA C. Nous verrons comment installer les outils CUDA C avec Visual Studio 2010. Puis nous étudierons l’architecture CUDA, vis-à-vis des capacités des cartes graphiques et des conséquences sur vos programmes.
A bientôt,
Bruno