Une introduction CUDA


prcdentsommairesuivant

I. GPGPU

Les constructeurs ont dcid de crer des langages qui permettent d'exploiter les possibilits de ces processeurs graphiques. Ils n'ont pas t les seuls.

Par exemple, l'universit de Stanford a cr le BrookGPU, le tout premier langage, un driv du C, qui permet d'utiliser les API DirectX et OpenGL, ainsi que GLSL ou CG. L'avantage de ces solutions est qu'elles sont utilisables sur tous les GPU qui supportent DirectX et/ou OpenGL, c'est--dire la plus grande majorit d'entre eux, et la totalit ces dernires annes. Cependant, cette universalit se traduit aussi par un manque de performances par rapport d'autres librairies plus proches du matriel.

Ainsi, ATI a dvelopp Close to Metal, une librairie trs bas niveau. Cette librairie sera supple par Stream, mais cette dernire est plus spcifiquement dirige vers les processeurs FireStream, prvus pour le calcul.

Ensuite vient NVIDIA, avec CUDA, une technologie disponible sur toutes les cartes graphiques grand public depuis la srie des GeForce 8000 et sur tous les supercalculateurs Tesla.

II. CUDA

Ou Compute Unified Device Architecture.

C'est la rponse de NVIDIA aux demandes sans cesse croissantes de puissance de calcul. Cette librairie, dvoile en 2007, permet d'employer la puissance de calcul des GPU. Elle n'est que la partie logicielle du tout : il faut encore une carte graphique compatible.

CUDA supporte plusieurs langages : le C, le C++ et le Fortran. Vous pouvez donc utiliser conjointement ces trois langages dans vos fonctions et vos kernels.

Il existe dj quelques wrapper pour CUDA : PyCUDA, destin Python, ainsi que JCublas, JCufft et JCudpp, sans oublier CUDA lui-mme, avec jCUDA pour Java, sans oublier CuBLAS.Net, un wrapper de CuBLAS pour le CLR .Net.

CUDA est constitu d'un pilote, dj intgr aux ForceWare les plus rcents ; d'un runtime ; et de quelques librairies. CUDA est aussi un langage, driv du C (mais n'apportant que peu de modifications : 9 nouveaux mots cls, 24 nouveaux types et 62 nouvelles fonctions). Ces extensions ncessitent leur compilateur, lui aussi fourni.

CUDA est prvu pour s'excuter sur un GPU, mais il est aussi disponible sur CPU, en mulation. Les performances sont alors bien moindres, mais cela peut tre utile pour tester ses applications sans GPU compatible.

L'API CUDA est de haut niveau : vous ne vous occupez donc pas du GPU directement. CUDA en est une couche d'abstraction.

Voici, graphiquement reprsentes, toutes les composantes de CUDA et de son utilisation.

Les diffrentes composantes de CUDA

II-A. Pilote

  • Rle : transmettre les calculs de l'application au GPU ;
  • Distribution avec les ForceWare 178.08 et plus rcents ;
  • Inconvnient : pas d'automatismes.

II-B. Runtime

  • Rle : interface entre le GPU et l'application, en fournissant quelques automatismes ;
  • Distribution : en mme temps que le pilote ;
  • Inconvnient : impossibilit d'optimiser partir d'un certain point.

II-C. Bibliothques

Pour le moment, CUDA est livr avec CuBLAS et CuFFt, respectivement les implmentations de BLAS (une bibliothque d'algbre) et de la transformation rapide de Fourier (utilise en analyse de Fourier et en traitement du signal). La dernire n'est pas inspire d'une bibliothque prexistante.

Ces implmentations reprennent le fonctionnement des bibliothques originelles (CuBLAS), ou bien des algorithmes les plus performants (CuFFT) et les optimisent au maximum pour CUDA.

III. Un peu de vocabulaire

Nous allons continuer cette introduction avec un peu de vocabulaire inhrent la programmation avec CUDA.

L'hte est le CPU, c'est lui qui demande au priphrique (le GPU) d'effectuer les calculs.

Un kernel est une portion parallle de code excuter sur le priphrique. Chacune de ses instances s'appelle un thread.

Image non disponible

Une grille est constitue de blocs. Chaque bloc est constitu de threads.

Un bloc est un lment des calculs, dissociable d'autres blocs : les blocs ne doivent donc pas tre excuts dans un certain ordre : paralllement, conscutivement ou toute autre combinaison est possible. C'est pourquoi les threads ne peuvent communiquer qu'avec des threads du mme bloc.

Un warp est un ensemble de 32 threads, envoys ensemble l'excution et excuts simultanment. Quel que soit le GPU utilis, quel que soit la quantit de donnes traiter, dans n'importe quel cas, un warp sera excut sur deux cycles. On peut tre sr et certain qu'il le seront. Ceci pourra vous aider lors de la conception de vos algorithmes. Par exemple, Mark Harris, chercheur pour NVIDIA dans le rendu graphique en temps rel, fondateur du site GPGPU, utilise cette donne pour drouler ses boucles.

Un petit parallle avec le matriel. Un thread est excut par un processeur : posons donc l'galit entre le thread et le processeur. Ainsi, le bloc est le multiprocesseur, tandis que la grille reprsente l'entiret de la carte.

Le calcul htrogne est l'utilisation des deux types de processeur disponibles sur nos ordinateurs : les CPU et les GPU. Il s'agit donc d'utiliser le bon type de processeur pour la bonne tche.

Vous voici prt pour partir l'attaque !

IV. CPU et GPU

IV-A. Survol de quelques diffrences

La puissance de nos GPU n'a de cesse d'augmenter depuis quelques annes. un point qu'il est dsormais possible de les utiliser pour raliser des calculs autres que pour des jeux. En effet, parmi les CPU, un Intel Pentium 4 cadenc 3 GHz fournit 4,8 GFlops, un Intel Core 2 Duo E6750 (2,66 GHz), 14,2 GFlops ; chez les GPU, on change de catgorie : la GeForce 9800 GTX, 420 GFlops, pour 675 MHz seulement.

Cependant, ces diffrences normes s'expliquent trs facilement, explications dans ce tableau.

CPU (hors SIMD) GPU
Nombre de tches Une seule et unique Le plus grand nombre
Varit des tches Toutes possibles Restreinte
Subdivision de la tche Aucune : tout en un coup Maximale, pour mieux la rpartir sur les diffrentes units de calcul

Il ne faut pas oublier de prciser que les GPU prfrent travailler avec des vecteurs. Dans le cas contraire, les gains sont rellement minimes.

Les deux types de processeur travaillent de faon radicalement diffrente. L'emploi de GPU la place de CPU ne se fait donc pas en un tour de main : il faut repenser le calcul pour l'adapter au type de processeurs dsir. Si l'on ne change pas sa manire de penser, autant continuer de produire son lectricit la pomme de terre, qui permet quand mme de produire assez pour clairer quelques centimtres ; tandis que la centrale lectrique permet d'clairer des villes entires.

Pour le grand public, les prix se tiennent : un E6750 cote, actuellement, 140 € ; une 9800 GTX, 150 €. Leurs ditions professionnelles sont lgrement diffrentes : 1 500 $ pour un NVIDIA Tesla S870 plafonnant 2 Tflops, contre 200 000 $ pour un IBM BlueGene de mme puissance. Ici, on remarque bien l'un des grands avantages du GPGPU.

On peut considrer des racks de cartes Tesla comme des supercalculateurs. En effet, ce sont eux qui calculent. Cependant, un ou plusieurs CPU les orchestrent, en plus de leur donner la masse de travail.

Aussi, les GPU ont t, la base, destins et spcialiss pour des calculs intensifs. Ceci leur permet de rserver plus de transistors au traitement des donnes, au lieu de les utiliser pour le cache ou bien pour la gestion des flux d'entre ou de sortie.

Ainsi, un GPU doit tre constitu de beaucoup de processeurs pour ces calculs : un GPU comporte au strict minimum 32 processeurs (240 pour le T10, 128 en moyenne) et ce, depuis plus qu'un temps certain. Ces processeurs sont les quivalents des coeurs de nos CPU, qui en comportent, en moyenne, 2 depuis quelques annes et, dans les annes venir, 80. Nous sommes donc bien loin des GPU !

IV-B. Prcision des calculs

Les GPU actuels, avec CUDA, n'ont qu'une prcision FP32, sur 32 bits. Il faut se tourner vers les solutions d'ATI/AMD pour une prcision double sur 64 bits, ou bien vers des GPU plus chers, comme les Tesla ou les Quadro, ou bien rcents, comme tous les GPU bass sur le GT200 (GeForce GTX260 GTX295).

Tous les processeurs ne fonctionnent pas la mme prcision : sur les premires GeForce compatibles CUDA, tous sont FP32. Sur un T10, 8 units sont FP32 et une seule FP64. Chez AMD, pour 8 units FP64, il y a 4 units FP32.

Le peu d'units ddies au calcul double prcision sur les Tesla et autres explique leur faible puissance ce niveau de prcision, en comparaison de la simple prcision ou bien des solutions d'AMD. Ainsi, pour du calcul en haute prcision, les solutions NVIDIA tous publics ne sont pas encore au point (AMD ne propose plus de GPGPU pour la mme gamme).

Actuellement, tous les processeurs supportent la double prcision sur 64 bits.

Plus prcisment, NVIDIA met disposition la liste des carts avec les standards, ainsi que ses limitations.

  1. Les additions et soustractions sont souvent associes en une seule instruction ;
  2. La division et la racine carre sont implmentes par la rciproque, non conformment aux standards ;
  3. Pour la multiplication et l'addition, il n'est possible que d'arrondir vers le nombre pair le plus proche ;
  4. Il n'y a pas de possibilit d'arrondi configurable dynamiquement ;
  5. Il n'y a pas de signalisation de NaN (Not a Number) ;
  6. Il n'y a pas de mcanisme de dtection d'exception, qui sera masque selon les standards ;
  7. Les oprandes de source dnormalise tendent vers 0 ;
  8. Le rsultat d'une opration avec NaN est un NaN canonique de la forme 0x7fffffff ;
  9. En accord avec les standards, si un NaN est pass min() ou max(), l'autre sera retourn.

IV-C. GPU

IV-C-1. Mmoires

IV-C-1-a. Mmoire globale

CUDA est capable de lire et d'crire sur la mmoire embarque dans la carte graphique. Ces oprations portent, respectivement, les doux noms de gathering et de scattering.

Image non disponible

La mmoire globale est la mmoire utilisable de n'importe quel endroit de CUDA, avec les mmes performances la cl : cette mmoire n'est pas cache et il faut attendre 400 600 cycles avant d'y accder. Ce qui laisse un multiprocesseur inactif pendant ce temps.

Pourquoi une telle latence ?
La mmoire globale est, en gnral (dans tous les cas, jusqu' prsent), de la DRAM.
Cette mmoire est trs bon march : 1,50$ en septembre 2008, pour les intgrateurs ! Ceci lui permet d'tre utilise comme mmoire principale de nos ordinateurs.
De plus, elle se rvle compacte : on en fait tenir des Go sans problme sur des cartes !
Pourtant, cette mmoire a un problme et il s'agit de la latence. Elle monte sans problme jusqu' 30 ns, ce qui reprsente quand mme dj 30 cycles ! Et sans compter les bus entre le multiprocesseur et la mmoire.
Finalement, cette mmoire n'est pas cache.

IV-C-1-b. Mmoire locale

Cette mmoire est, l'instar de la mmoire globale, non cache et avec une latence trs leve.

Cette mmoire n'est utilise que pour certaines variables, qui y sont places automatiquement. En effet, certains tableaux, normalement placs dans les registres, sont trop grands : il leur faut donc un espace plus grand, qu'offre la mmoire locale.

IV-C-1-c. Mmoire constante

La mmoire constante est cache : la lecture depuis cette mmoire ne cote qu'un cycle. Pour tous les threads d'un demi-warp, la lecture depuis la mmoire constante est aussi rapide que depuis un registre, aussi longtemps que tous les threads lisent le mme emplacement mmoire. Le cot de lecture augmente linairement avec le nombre d'adresses diffrentes demandes par les threads. Il est recommand que tous les threads d'un warp utilisent la mme adresse et non seulement ceux de demi-warps, vu que les priphriques futurs le requerront pour un fonctionnement optimal.

Chaque multiprocesseur dispose d'une mmoire rserve aux constantes, d'une taille de 8 ko, dans le cas des GeForce 8800.

IV-C-1-d. Mmoire des textures

Cet espace mmoire est cach, le cot de la lecture est donc trs faible.

Cette mmoire est optimise pour un espace deux dimensions, ainsi, les threads d'un mme warp qui lisent des adresses proches auront des performances optimales.

Aussi, elle est prvue pour des demandes de flux avec une latence constante.

La lecture des mmoires du priphrique par le mcanisme des textures peut tre une alternative avantageuse la lecture depuis les mmoires globale ou constante.

Les textures seront approfondies plus tard, mais voici un avant-got.

Les textures permettent vraiment de simplifier le traitement d'images : elles permettent la mise en oeuvre de filtrages bilinaires et trilinaires trs facilement et l'accs alatoire ais aux pixels.

IV-C-1-e. Mmoire partage

Image non disponible

Cette mmoire est prsente sur le chipset, ce qui lui permet d'tre assez rapide, plus que la mmoire locale.
En fait, pour tous les threads d'un warp, accder cette mmoire est aussi rapide que d'accder un registre, tant qu'il n'y a pas de conflit entre les threads.

Pour permettre une bande-passante assez leve, la mmoire partage est divise en modules de mmoire, les banques, qui peuvent tre accde simultanment. Ainsi, n lectures ou critures qui tombent dans des banques diffrentes peuvent tre excutes simultanment dans un warp, ce qui permet d'augmenter sensiblement la bande passante, qui devient n fois plus leve que celle d'un module.

Cependant, si deux demandes tombent dans la mme banque, il y a un conflit de banques et l'accs doit tre srialis. Le matriel divise ces requtes problmatiques en autant de requtes que ncessaire pour qu'aucun problme n'ait lieu, ce qui diminue la bande passante d'un facteur quivalent au nombre de requtes total effectuer.

Pour des performances maximales, il est donc trs important de comprendre comment les adresses mmoires sont relies aux banques, pour pouvoir prvoir les requtes et, ainsi, minimiser les conflits.

Dans le cas d'un espace en mmoire partage, les banques sont organises pour que des mots successifs de 32 bits soient assigns des banques successives. Chaque banque a une bande passante de 32 bits tous les deux cycles d'horloge.

Pour le moment, un warp a une taille de 32 threads et il y a 16 banques.

Une requte en mmoire partage pour un warp est divise en deux : une partie pour le premier demi-warp, une autre, pour l'autre moiti. Ce qui a pour consquence qu'il ne peut y avoir de conflit entre chaque demi-warp. Les conflits seront dtaills plus tard.

Actuellement, la mmoire partage atteint un total de 16 ko, 1 ko pour chaque banque.

Pour rsumer ceci, voici un schma qui reprend l'essentiel des caractristiques prsentes ici.

Image non disponible

IV-C-1-f. Registres

Gnralement, l'accs un registre ne prend pas un seul cycle supplmentaire par instruction, mais des retards peuvent apparatre, suite aux dpendances de lecture aprs criture et des conflits qui peuvent se produire.

Les retards introduits pas les dpendances peuvent tre ignors, ds qu'il y a au moins 192 threads actifs par multiprocesseur, qui permettent de les cacher.

Le compilateur et l'organisateur des threads organisent les instructions pour des performances optimales, qui ncessitent d'viter les conflits avec les banques. Le meilleur moyen d'obtenir de bonnes performances est d'utiliser un multiple de 64 comme nombre de threads par bloc. Une application n'a strictement aucun moyen de contrler ces conflits.

Chaque multiprocesseur dispose de 8192 registres.

IV-C-1-g. Mmoire systme

Depuis les GT200 (GeForce GTX 260 295), il est dsormais possible d'utiliser la mmoire principale du systme, alias RAM, grce CUDA 2.2.

Les appels cette mmoire ne peuvent tre frquents : ils sont encore plus lents que les appels la mmoire locale (700 800 cycles de latence !). Mais la RAM est disponible, de nos jours, en quantits plus grandes que celle disponible sur nos GPU.

IV-C-2. Shaders

Les calculs demands CUDA sont, pour le moment, effectus sur les units de shaders, les processeurs les plus rapides sur les GPU. Par exemple, les GeForce 8800 GTX ont des units cadences 1,2 GHz.

Image non disponible

Chaque unit de traitement des shaders est, comme montr ci-dessus, constitue de Texture Processor Clusters (TPC).

Chacun de ces clusters est fait d'une unit de traitement des textures (TEX) et de deux units de traitement des flux (SM, Streaming Multiprocessor).

Vous n'avez pas vraiment besoin d'en savoir beaucoup plus pour pouvoir aborder CUDA. Cependant, si vous en voulez encore, faites-vous plaisir avec la section suivante !

IV-C-2-a. Plus de prcisions

Chacun de ces deux processeurs contient une interface qui code et dcode les instructions et qui les lance. Derrire l'interface, plusieurs units excutent les instructions. Les calculateurs fonctionnent deux fois plus vite que l'interface !

Ces calculateurs sont 8 units de calcul (SP) et 2 units superfonctionnelles (SFU).

chaque cycle, l'interface choisit un warp prt tre excut.

Pour excuter toutes les instructions des 32 threads, il faudra 4 cycles. Cependant, vu de l'interface, cela prendra 2 cycles.

Pour viter que l'interface reste inactive pendant un cycle, l'idal est d'alterner les types de warps : un premier pour les SP, un second pour les SFU.

IV-C-2-b. Limites

Un SM tant compos de 8 SP, on sera donc limit l'excution de 8 blocs en simultan. De plus, l'excution est limite 65536 blocs et 512 threads par bloc au total.

Vous n'avez pas encore eu un aperu du temps consacr au calcul en fonction des diffrents paramtres.

En faisant varier le nombre de blocs de calcul sur un mme problme, voici les rsultats que l'on peut obtenir, avec de simples oprations d'entre/sortie dans une table. Un bloc correspond un thread sur un CPU, que l'on peut affecter un coeur.

Variation du temps de calcul en fonction du nombre de blocs

Le processeur utilis ici est un simple coeur, ses performances en fonction du nombre de threads restent donc stables. S'il s'agissait d'un quad-core, le minimum serait situ 4 threads.

La carte graphique, une GeForce 8800 GTX, possde 16 processeurs, qui ne donnent leur pleine puissance qu' deux blocs chacun. NVIDIA recommande toutefois d'utiliser au moins une centaine de blocs, afin de pouvoir utiliser la puissance de chipsets plus rcents venir.

IV-D. CPU

Il excute uniquement les instructions dans l'ordre assign, sans paralllisation (sauf architectures multi-cores et multi-CPU, qui ncessitent quand mme une action la conception).

Les instructions sont aussi crites en mmoire, pour excution. Cependant, les donnes avec lesquelles il faudra travailler sont souvent dans la mme mmoire !

D'habitude, il ne travaille pas directement en mmoire : les donnes sont copies dans des registres puis manipules et enfin stockes en mmoire.

l'origine, CPU et mmoire partageaient les mmes frquences. Mais le premier a acclr et la seconde ne l'a pas rattrap : au point que, si les processeurs actuels lisaient directement dans la mmoire, ils ne seraient utiliss que 10% du temps.

IV-D-1. Mmoire cache

C'est pour cela que des caches ont t installs : il s'agit de petites quantits de mmoire, mais trs rapide, qui se place entre le CPU et la mmoire centrale. Ils ne sont utiliss que pour les instructions frquemment utilises et les donnes. Il en existe deux niveaux : L1 et L2, exceptionnellement un troisime, L3, sur les processeurs les plus chers (rservs gnralement aux serveurs).

Cependant, ces mmoires trs rapides ne sont pas prsentes en grande quantits sur nos CPU, vu leur prix : en moyenne, le mgaoctet de cache cote 100 fois plus cher que le mgaoctet de RAM ! Le cache fonctionne aussi 10 fois plus vite que la RAM, avec un temps d'accs de 5 10 fois infrieur.

Les caches sont utiliss de manire transparente par le matriel. Ils se font les mirroirs des donnes en mmoire. Ils transportent les donnes o elles sont ncessaires quand cela est demand. Ces donnes ne sont remplaces que quand des donnes plus urgentes arrivent.

Si les donnes demandes par le CPU sont disponibles sur le cache, celui-ci les lui envoie, le CPU ne doit pas attendre. Par contre, si elles ne le sont pas, la demande est effectue en aval, sur des mmoires plus lentes et le CPU doit attendre.

IV-D-2. Pipelines d'instructions

Supposons qu'un CPU prenne 3 cycles pour une multiplication de paire. Combien de temps prendra-t-il pour multiplier n paires ? Nous pourrions dire 3 n cycles. Il est possible de rduire ce nombre.

La multiplication aura lieu dans une ligne de production. Nous pouvons avoir plus d'une paire de nombres en calcul en mme temps. Dans ce cas, les multiplications prendront n + 2 cycles.

Image non disponible

Notre but, pour atteindre cette vitesse, est de garder le pipeline rempli.

Dans une architecture avec pipelines, il est prfrable d'avoir le moins possible de branches.

Moins de branches
Sélectionnez
do i=start,end
    a(i) = b * c(i)
end do
Moins de multiplications
Sélectionnez
do i=start,end
    if( c(i) == 0 )
        a(i) = 0
    else if( c(i) == 1 )
        a(i) = b
    else
        a(i) = b * c(i)
    end if
end do

IV-D-3. Excution superscalaire

Les CPU modernes ont plusieurs units de calcul, qui peuvent effectuer un nombre limit d'instructions en parallle.

Le matriel examine les instructions pour reprer des opportunits d'optimisation.

Le pipeline
Sélectionnez
i = i + 1;
j = j + 1;
a = b * c;

Les branches limitent ces opportunits et les units d'excution sont laisses en attente pendant l'valuation des conditions.

Les CPU essayent toutes sortes d'autres astuces, comme la prdiction de branches, l'excution spculative ou autres, dont le compilateur et le CPU s'occupent.


prcdentsommairesuivant

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

Copyright © 2009 Thibaut Cuvelier. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.