1.4         Programmation d’un GPU

Le but initialement graphique des GPU a bien entendu dirigé les constructeurs à initialement proposer des langages destinés à ce type de calcul, c’est-à-dire dont les instructions utilisent les branchements matériels spécifiques, destinés à des opérations de type mult-add, largement utilisées en synthèse d’images. Même si d’autres langages plus généralistes ont depuis été présentés, le choix reste bien plus restreint sur GPU que sur CPU. On s’intéresse ici à faire un tour d’horizon non-exhaustif des langages existants sur GPU. En plus des langages bas niveau type Assembleur dont il ne sera pas fait mention dans cet exposé, manipulant directement le contenu de registres des unités programmables sur la carte, les langages de plus haut niveaux disponibles sur GPU se distinguent en deux grandes catégories : les Shading Languages, dont les instructions sont principalement destinées aux calculs graphiques, et ceux dont l’objectif est le calcul générique, que l’on nommera langages GPGPU.

1.4.1        Langages

1.4.1.1  Shading Languages

Ces langages ont pour point commun de proposer au développeur des jeux d’instructions spécifiques à la génération d’images, ils sont orientés matériel. Ils permettent d’écrire des shaders. Ceux ci seront exécutés par les unités matérielles spécifiques, Vertex Unit et Fragment Unit, ces deux types d’unités étant unifiés dans les dernières générations de cartes.

Cg, HLSL, GLSL
Ces trois langages, respectivement proposés par NVidia, Microsoft  et 3DLabs, ont été développés conjointement et sont donc très similaires. Ce sont les shading languages les plus usités. Les syntaxes et sémantiques proposées ont été délibérément fixées proches des instructions du C++, par soucis de simplicité. Les éléments qui ont effectivement motivé ce choix sont la portabilité entre différents systèmes d’exploitation et/ou modèles de GPU et la possibilité d’un développement rapide. Un compromis nécessaire entre ces éléments et une volonté de performance a amené ces langages à posséder des instructions exploitant directement les unités matérielles de la carte, proposées via une syntaxe de type C et permettant de réaliser les opérations de bases et d’autres plus spécifiques de la génération d’images de synthèse.
Ces langages sont compilables et multi programmes : le développeur doit écrire un shader pour chaque étage programmable du pipeline : Vertex Shader, Geometry Shader et Fragment Shader. Chacun a ses particularités, en particulier les types de données entrant et sortant. L’ensemble de ces shaders est encastré dans un code C++ englobant, pilotant la carte graphique. Les rares différences entre ces langages se résument à deux principaux points. Premièrement, ils ne supportent pas tous les mêmes API : HLSL est exclusivement utilisable avec DirectX, GLSL avec OpenGL, et Cg a la capacité d’utiliser les deux. Le second point est lié à la gestion des différents modèles de cartes : alors que GLSL ne propose pas de sous-ensemble d’instructions dédiés à chaque modèle, Cg et HLSL exploitent cette idée, sous la notion de profil.

Sh
Tout comme Cg, HLSL et GLSL, Sh, développé par le Computer Graphics Lab de l’University of Waterloo, est un langage encastré dans le C++, avec une syntaxe proche du C permettant d’écrire des shaders paramétrés. Il est à la fois orienté vers le calcul graphique et la programmation générique. Sa particularité la plus notoire est d’être basé sur le traitement de flux de données.
RapidMind est le successeur commercial de Sh, il est utilisé dans un nombre important de domaines nécessitant une certaine puissance : 3D, traitement de signaux, finance, etc.

1.4.1.2  Langages GPGPU

L’utilisation des shading languages pour de la programmation générique n’est pas des plus aisée. Le développeur les employant est contraint d’adapter ses algorithmes à un modèle de calcul basé sur des primitives géométriques et des textures, ce qui n’est pas toujours facile ni même possible. Des moyens pour programmer les GPU sans pour autant avoir besoin de connaissances en graphisme ont naturellement suscité un intérêt grandissant. Différents langages ont émergés de projets industriels ou universitaires.
Tous ces nouveaux langages ont comme dénominateur commun d’être de plus haut niveau que les shading languages, en proposant plus de possibilités et en se séparant totalement des notions graphiques : texture, shader, vertex ou fragment n’y ont plus de sens. Les plus importants langages GPGPU sont présentés dans la suite.

CUDA
CUDA, Compute Unified Device Architecture, est le dernier né des langages de NVidia, pouvant être utilisé à partir de la sixième génération de cartes graphiques de ce constructeur (architectures G80 et plus récentes). Quelques unes de ses particularités sont d’être encastré dans du code C++ en en définissant seulement quelques extensions, de mettre à disposition une mémoire partagée et rapide, ou de supporter différents types d’opérations scalaires, en particulier les opérations sur entiers et bit à bit. C’est aussi le premier langage à exploiter l’unification des shaders sur les architectures G80 de NVidia. Dans le domaine du traitement d’images, il est de plus en plus employé.

OpenCL
Le très récent OpenCL (Open Computing Language) a été annoncé par Apple au sein du Compute Working Group, formé par le Khronos Group (regroupant 3DLabs, Apple, AMD, NVidia, ARM, Ericsson et d’autres universitaires et industriels). Ces partenaires souhaitent mettre à disposition un langage open source, dans la veine d’OpenGL et OpenAL et ont pour ambition de faire d’OpenCL le standard libre pour le calcul GPGPU, avec les importants avantages d’être multiplateforme (cartes AMD/ATI et NVidia) et de permettre une programmation homogène.

BrookGPU, Brook+
BrookGPU est une implémentation GPU du langage Brook, tous deux développés par le Stanford University Graphics Lab. C’est un langage basé sur la gestion de flux de données. AMD/ATI a également proposé Brook+, une amélioration de BrookGPU pouvant être utilisé uniquement sur leurs cartes. Folding@home, projet mondial de calcul distribué simulant les repliements de protéines dans le but d’en tirer des solutions médicales, utilise en partie Brook+.

Scout
Proposé par le Los Alamos National Laboratory, Scout est un langage GPGPU destiné à l’analyse et à la visualisation scientifique, dont beaucoup de techniques sont basées sur l’utilisation de mappings, exprimés sous forme de fonctions mathématiques et transformant des données en image affichables. Scout a notablement été utilisé pour la simulation et la détermination de caractéristiques du courant côtier El Ninõ.

Accelerator
Microsoft Research a présenté Accelerator, destiné à simplifier la programmation GPGPU en fournissant un modèle de calcul parallèle accessible simplement à travers d’autres langages. Les opérations parallèles y sont compilées à la volée et optimisées pour les fragment shaders.

CGis
Le langage CGiS, développé par l’Universität des Saarlandes, est un autre langage parallèle, similaire à Brook et Accelerator, manipulant également des objets de type flux de données, mais se démarquant par l’absence de notion de kernel computationnel (équivalent de shader pour du calcul uniquement GPGPU), remplacé par un mécanisme de boucle globale forall, chère au calcul parallèle.

1.4.2        Modèle de programmation

La programmation GPGPU est basée sur quatre concepts principaux, que nous proposons d’expliciter. On évoque également deux autres façons, liées, d’interpréter la notion de complexité en calcul sur GPU.

1.4.2.1  Tableaux = Textures

Sur CPU, une des structures de données la plus utilisée est le tableau à une dimension (1D).
Les tableaux de dimensions supérieures sont représentés dans un tableau 1D, les données y étant stockées à la suite pouvant être accédés par des offset sur leurs indices.
En GPU, les données exploitables sont nécessairement stockées dans des textures (donc en deux dimensions). On y accède par leurs coordonnées. Pour y représenter des structures d’autres dimensions, il est utile de passer par une réorganisation vers un tableau 2D, transmis à la carte dans une texture.
Le GPU peut alors lire l’élément (i, j) du tableau en consultant le pixel (i, j) de cette texture.
Dans le cas d’un tableau 1D stocké dans une texture de taille N x N’, l’élément k a pour coordonnées dans la texture (k mod N, E( k/N )), où E(x) est la fonction partie entière de x.

Les tailles maximales pour les textures sont de 8192 x 8192 avec l’API DirectX, ou bien de 4096 x 4096 pour les versions moins récentes. Bien qu’il n’y ait a priori pas de contrainte sur le nombre de textures instanciées simultanément, c’est souvent la quantité de mémoire sur la carte qui va limiter ce nombre, s’élevant aujourd’hui jusqu’à 768Mo par carte grand public, ou 1Go pour des cartes professionnelles.
Chaque élément de texture peut contenir jusqu’à 4 scalaires (correspondant aux canaux rouge, vert, bleu et alpha d’un pixel à afficher). Les opérations scalaires se font simultanément sur ces 4 valeurs. Les types de scalaires utilisables pour les éléments de texture peuvent être entiers ou flottants. Ces éléments peuvent être vectoriels de dimension 1 à 4, voire matriciels de dimensions allant jusqu’à 4 x 4.

1.4.2.2  Kernel = Fragment Shader

La programmation parallèle a introduit la notion de kernel computationnel, brique calculatoire de base, équivalent d’une fonction mathématique, pouvant être appliqué à un ensemble de données de façon parallèle.
En programmation GPGPU, ces kernels sont les fragment shaders. Un tel shader comporte donc une suite courte d’instructions opérant sur une donnée (ou un petit ensemble de données). Il est à noter qu’aucun vertex shader ou geometry shader n’est en général implémenté. Il est possible de ne pas spécifier de shader, les unités de traitement correspondantes se comportant alors comme des passthrough, ne modifiant aucun attribut des données.

1.4.2.3  Calcul = Rendu graphique

Une fois le fragment shader implémenté, une fois l’environnement convenablement préparé (textures créées aux bonnes dimensions, données d’entrée envoyées à la mémoire GPU, paramètres supplémentaires assignés, environnement OpenGL ou DirectX correctement initialisé, etc.), l’exécution du calcul décrit dans le fragment shader se fait en utilisant la totalité du pipeline graphique, par invocation du rendu d’un simple rectangle de taille adaptée aux données de sortie. En effet, un tel rectangle rasterizé est comparable à une grille de taille fixée, structure la plus pratique à disposition pour la réalisation de calculs parallèles. Cela justifie la non-modification des sommets, et donc la non-utilisation des vertex et geometry shaders. Ces étapes sont résumées sur la Figure ci-dessous.
Le lancement d’un rendu avec un shader est également appelé passe du shader.

Les quatre sommets d’un rectangle sont passés à la carte via l’API de son choix. Le vertex shader et le geometry shader ne les modifient pas. Le rasterizer divise le rectangle en fragments. Chaque fragment est traité par un des fragment unit. Le résultat est enregistré dans une texture de sortie, de la taille du rectangle passé en entrée. Cette texture peut être réutilisée dans une passe ultérieure du fragment shader, ou bien être récupérée par le CPU.

1.4.2.4  Feedback

Lors d’un calcul destiné à faire un affichage à l’écran, l’image générée est stockée dans le framebuffer, buffer dédié à cet effet. Pour un calcul GPGPU, le résultat du calcul n’est pas stocké dans ce framebuffer, mais dans une texture, par un moyen technique nommé Render-To-Texture.
Cette texture peut alors être utilisée comme donnée d’entrée pour une passe ultérieure, permettant ainsi de segmenter tout algorithme à implémenter en GPU en différentes passes. Lorsqu’un algorithme nécessite plusieurs passes successives, une astuce simple et classique, appelée ping-pong, est d’utiliser une paire de textures, une pour l’entrée de l’algorithme, une pour sa sortie, que l’on permute entre chaque rendu. Cela permet de ne pas avoir à transférer les données du GPU vers le CPU et réciproquement entre chaque passe.

1.4.2.5  Complexité GPGPU

La complexité d’un algorithme parallèle GPU se mesure différemment d’un algorithme séquentiel classique. On peut vouloir se reposer sur le nombre total de fragments à calculer, on parle alors de complexité en fragment C_f. On peut également vouloir déterminer le nombre de rendus nécessaires pour obtenir le résultat final, c’est alors la complexité en rendus C_r.
Ces deux complexités sont liées par un facteur multiplicatif, la première étant égale à la seconde multipliée par la taille N des données : C_f = C_r x N.

1.4.3        Contraintes matérielles

Connaître le modèle de programmation des GPU n’est pas suffisant pour produire un programme efficace et optimisé. Il est également nécessaire de prendre en compte les contraintes imposées par l’architecture matérielle des cartes graphiques.

1.4.3.1  Accès mémoire

Aptitude à supporter les opérations de Gather et Scatter
Sur GPU, les processeurs sont capables de retrouver en mémoire des informations ailleurs que sur le pixel i₀ sur lequel ils s’exécutent, ils sont donc capables de gather. Ce procédé est nécessaire pour la mise à jour de valeurs en fonction de celles des voisins spatiaux, par exemple. Par contre, le scatter leur est impossible, ils ne peuvent pas modifier un autre pixel que i₀. Matériellement, les processeurs des GPU ne permettent pas le scatter, celui-ci étant beaucoup plus difficile à implémenter de par la conception des fragments, ayant chacun une localité dans la texture de sortie et ne pouvant donc pas être adressé indirectement en écriture.
Cette restriction implique d’importantes incommodités de programmation, en particulier dans l’adaptation d’algorithmes devant propager des données dans différents endroits de la mémoire, par exemple pour des mises à jours de valeurs en fonction d’une certaine connectivité. Le développeur est alors amené à utiliser diverses astuces : redéfinition de l’algorithme en plusieurs passes GPU, utilisation du vertex shader et/ou du geometry shader comme outil de scatter ; taguer les données avec les adresses mémoires et faire un rendu simple pour ensuite trier selon ces adresses ; reformuler le problème et les algorithmes en termes de gather.
De plus, les toutes dernières générations de cartes graphiques, en particulier à partir des GeForce 8, autorisent nativement les opérations de scatter avec certains langages (comme CUDA), par une refonte de l’organisation des processeurs et de la mémoire.

Texture Indirection
Une texture indirection est une lecture dans une texture à des coordonnées dépendant d’un calcul ou d’une autre lecture dans une texture. Le nombre de texture indirections successives par programme est limité, voire très limitée sur les anciennes cartes ATI, pour des raisons internes au développement des cartes. La création de structures de type look-up table, ou table de correspondance, est ainsi parfois incommode.

1.4.3.2  Bande passante

L’envoi des données au GPU ainsi que le retour des résultats sont des opérations couteuses en temps. Bien que la communication entre la carte graphique et le reste du système soit assurée par des ports dédiés (actuellement AGP et PCI Express), cela reste insuffisant par rapport à la rapidité d’échanges d’informations entre la mémoire de la carte et ses processeurs, faisant de la communication entre CPU et GPU le goulet principal.
De plus, les ports AGP ont le désavantage d’être asymétrique, le temps GPU vers CPU étant plus long que son contraire. Il est alors important de minimiser ces transferts, en conservant les données dans la mémoire de la carte le plus longtemps possible. Ceci est d’autant plus avantageux lorsque le CPU n’a pas à attendre le résultat d’une passe GPU.

1.4.3.3  Autres

D’autres difficultés liées au matériel existent, bien que moins embarrassantes aujourd’hui.

Taille des programmes
Avec la norme Pixel Shader 2.0, le nombre d’instruction par shader était limité à 96. Ce plafond est passé à 65535 avec la norme Pixel Shader 3.0. Ces quotas étaient parfois très vite atteints, après déroulages de boucles, restreignant les développeurs. La norme actuelle, utilisée par les cartes graphiques récentes (sixième génération et plus), Pixel Shader 4.0, autorise des shaders de taille quelconque. Néanmoins, lors du développement d’un programme devant également s’exécuter sur d’anciennes générations de cartes, il est important de prendre en compte ces limitations.

Formats et précisions
En interne, les formats et la précision des données ne sont pas constants entre les générations de cartes. Les générations plus anciennes proposent des calculs sur flottants en 16bits, voire 8bits, et les plus récents sur 32bits, flottants ou entiers (en particulier Geforce 8 et plus récents). Une fois encore,  un développeur souhaitant exécuter un programme sur différentes cartes devra s’assurer de la compatibilité des formats de données utilisés par son programme avec ceux disponibles sur la génération de cartes utilisée.