Comment un GPU exécute 32 threads en
même temps
Pipeline IFL/IIL/RASL, divergence de flow et SIMT stack, SIMT deadlock, ordonnancement des warps, Operand Collector : tout ce qui se passe vraiment a l'interieur d'un coeur SIMT moderne.
Maxime J22 min de lecture
Un doute sur votre exposition ?
On audite votre surface d'attaque externe et on vous dit ce qui est exploitable.
Parler à un pentesterPrerequis
- Comprendre le fonctionnement d'un CPU : unites de calcul (ALU = Arithmetic Logic Unit, IFU = Integer Function Unit, SFU = Special Function Unit, FPU = Floating Point Unit), pipelining et execution speculative, caches
- Introduction aux GPUs
- Modele de programmation GPU
Hello ! o/
Dans cette section on va etudier l'architecture et la microarchitecture des GPUs modernes : les coeurs SIMT (Single Instruction Multiple Threads) qui implementent le calcul, et le systeme de memoire GPU.
Aujourd'hui les GPUs executent des dizaines de milliers de threads concurrents, donc il est necessaire d'avoir une architecture qui puisse tenir ce nombre de threads. On pourrait se dire que le systeme de cache est inutile car il y a deja des emplacements memoire sur le GPU qui offrent un acces tres rapide, mais la memoire cache GPU permet de reduire le nombre d'acces hors-GPU, donc par exemple sur la RAM (memoire vive) ou le DD (Disque Dur, memoire virtuelle).
Le pipeline GPU : IFL, IIL, RASL
Comme le CPU, le GPU execute une instruction dans un pipeline. Le pipeline GPU peut etre divise en 2 grandes parties : le SIMT front-end et le SIMD (Single Instruction Multiple Data) back-end. Ce pipeline consiste en 3 boucles qui agissent ensemble : IFL (Instruction-Fetch Loop), IIL (Instruction-Issue Loop) et RASL (Register-Access Scheduling Loop).
Voici comment chaque boucle se decompose :
| Boucle | Etapes | Role |
|---|---|---|
| IFL | Fetch, I-Cache, Decode, I-Buffer | Charge et decode les instructions depuis la memoire |
| IIL | I-Buffer, Scoreboard (Table des marques), Issue, SIMT Stack | Selectionne et emet les instructions prets a etre executees |
| RASL | Operand Collector (OC), ALU, MEM | Collecte les operandes depuis les banques de registres, execute, acces memoire |
Une seule boucle : le cycle de base
Considerons d'abord une seule boucle. A chaque cycle, le hardware selectionne un warp. L'IP/PC (Instruction Pointer / Program Counter) du warp doit acceder a la memoire de l'instruction pour trouver la prochaine instruction, comme dans un CPU. Une fois l'instruction fetchee, elle est decodee pour comprendre son opcode et les registres qu'elle utilise, a partir du fichier de registre (qui fait partie de l'Operand Collector).
En parallele de la lecture du fichier de registre, les valeurs du masque d'execution SIMT sont determinees. C'est ce qui aide les threads dans leur flow de controle : tous les threads n'ont pas le meme flot de controle, le masque permet de savoir lesquels executent reellement l'instruction courante.
Une fois qu'on a toutes les informations (masque d'execution + registres sources), l'execution procede en SIMD : une seule instruction, plusieurs donnees.
Les unites d'execution
Dans un GPU moderne on trouve plusieurs types d'unites de calcul. Certaines sont specialisees pour reduire la latence de fonctions specifiques :
| Unite | Role | Exemple |
|---|---|---|
| ALU | Operations arithmetiques et logiques generales | add, mul, and, or |
| FPU | Calcul en virgule flottante | fadd, fmul, fma |
| IFU | Operations sur les entiers | iadd, imad |
| SFU | Fonctions speciales accelerees materiellement | sin, cos, reciprocal, SHA-1 |
| Tensor Core | Operations matricielles rapides (Volta+) | GEMM, convolutions IA |
Generalement ces ALU se regroupent par nombre de threads dans un warp : 32 pour Nvidia, 64 pour AMD. Mais ce n'est pas obligatoire : si on les regroupe par 16 unites, on peut augmenter la frequence (au prix d'une consommation d'energie plus elevee) et pipeliner leur execution.
Modele d'execution SIMT et SIMT Stack
Les GPUs modernes reposent sur le modele d'execution SIMT. Le but : donner au programmeur l'illusion que chaque thread s'execute de maniere independante. Dans nos GPUs modernes, ca se fait par la combinaison d'une unite de prediction traditionnelle et d'une pile de predicats de masques : la SIMT Stack.
Cette combinaison aide l'execution SIMT dans 2 situations :
- Le flow de controle imbrique : quand le flow de controle d'un thread depend d'un autre.
- Sauter des calculs quand tous les threads d'un warp ne prennent pas un chemin de flow de controle particulier. Ca evite de calculer les divergences de certaines branches.
Structure de la SIMT Stack
La pile SIMT contient un registre TOS (Top Of Stack) qui represente le sommet de la pile, avec 3 entrees par niveau :
- Re-convergence : l'adresse ou les threads se regroupent apres leurs flots de controle respectifs.
- Prochaine divergence : l'adresse du prochain point de branchement.
- Masque : un ensemble de bits (un bit par thread du warp), ou
1signifie "ce thread execute ce chemin" et0signifie "ce thread est masque sur ce chemin".
Divergence de warp
SIMT Deadlock
On va maintenant etudier le SIMT deadlock et des architectures sans pile SIMT : comment notre coeur SIMT fonctionne quand on a des problemes de synchronisation, par exemple un thread au point de re-convergence alors que d'autres sont encore dans leurs flots de controle divergents.
Le probleme : mutex dans un warp
Voici le code problematique :
A : *mutex = 0;
B : while (!atomicCAS(mutex, 0, 1)) ;
C : // Section critique
atomicExch(mutex, 0);La ligne A initialise une variable partagee : un mutex a 0 pour indiquer que le lock est disponible. Sur la ligne B, chaque thread d'un warp execute l'operation atomicCAS (Compare-And-Swap) sur l'adresse memoire contenant le mutex. Dans un CAS : on lit le mutex, on le compare au 2e operande (ici 0). Si la valeur du mutex est 0, le CAS le met a jour avec le 3e operande (ici 1).
Les acces memoire sont concurrents donc serialises : un seul thread verra le mutex a 0, les autres le verront a 1 (la valeur aura ete swappee par le premier thread). Dans la pile SIMT, un seul thread prend un flot de controle different car les autres doivent attendre que le mutex repasse a 0. La section C est un point de re-convergence, mais chaque thread y ira de facon sequentielle : jamais 2 threads n'executent C simultanement.
C'est le SIMT deadlock : chaque thread est dependant de l'autre. Le thread qui tient le mutex ne peut pas avancer car les autres threads du warp (qui attendent en boucle) font partie du meme warp et bloquent l'emission des instructions.
Solution : BPM, BS, TS
Comme solution a ce probleme, on a le BPM (Barrier Participation Mask) : un masque qui traque quel thread d'un warp participe a un SIMT deadlock ou a une barriere de convergence. Associe a ca, deux autres champs :
- BS (Barrier State) : indique quels threads ont atteint un etat de barriere de convergence.
- TS (Thread State) : pour chaque thread du warp, son etat : pret a executer, bloque a une barriere de convergence, ou fini.
Instructions ADD, WAIT, YIELD
Plusieurs instructions permettent la detection du SIMT deadlock :
| Instruction | Declenchement | Effet sur BS / BPM |
|---|---|---|
| ADD | A chaque divergence | Met a jour BPM pour enregistrer les threads qui divergent |
| WAIT | A chaque re-convergence | Met a jour BS quand un thread atteint le point de re-convergence |
| YIELD | Cas speculatif | Speculatif, nous n'en discutons pas ici |
Ces instructions ADD et WAIT changent le BS, qui change le BPM, ce qui permet de traquer les SIMT deadlocks.
Architecture Volta (Nvidia)
Ordonnancement des warps
On retrouve dans le GPU la meme question que pour le CPU pour optimiser l'execution de code : comment et dans quel ordre executer les warps ?
Si on doit attendre qu'un warp finisse de s'executer pour en executer un autre, ca augmente considerablement la latence. Dans un monde ideal on peut cacher cette latence en utilisant un systeme de multithreading a grain fin avec le meme principe que le pipeline CPU : par exemple une fois l'IF (Instruction Fetch) fini, on refait une IF pour ne pas perdre de temps. Mais ca demande au thread d'avoir ses propres registres, ce qui est tres couteux.
Si on augmente le nombre de warps, ca diminuera le nombre de coeurs par puce et augmentera considerablement la taille du fichier de registre. Il y a aussi la solution du CCWS (Cache-Conscious Warp Scheduling) qui dit que lorsque les threads accedeant a des donnees disjointes menent a des structures de donnees complexes, il serait mieux pour un thread donne d'etre repetitivement selectionne pour maximaliser la localite. La selection de warps est donc problematique en termes d'optimisation.
Pipeline a 2 boucles et le Scoreboard
Ajoutons un nouveau niveau de complexite : ne pas savoir si l'instruction suivante depend d'une ancienne instruction qui n'a pas fini de s'executer. Si on a ces informations, on pourrait reduire le nombre de warps pour executer plus d'instructions. Pour ca, les GPUs implementent l'I-Buffer : les instructions sont placees apres l'acces au cache, ce qui aide a la detection des dependances.
Scoreboard (Table des marques)
Les CPUs utilisent un tableau de marque (scoreboard) : un tableau de bits representant chaque operande et sa completion par rapport aux instructions non completees. Ca permet d'eliminer les dependances de nom et introduit le besoin de logique associative et des stations de reservation. Les GPUs utilisent une execution "in-order" des tableaux de marque, ce qui evite les problemes de hazard sur read-after-write et write-after-write.
C'est simple sur un seul thread. Mais sur un warp c'est different : avec au moins 128 registres par warp et 64 warps par coeur, le tableau de marque demande 8 192 bits pour etre implemente.
Le probleme d'une execution multi-threadee "in-order" : une fois une instruction completee, les prochaines doivent sonder le tableau des marques. Sonder le tableau des marques necessite au moins 4 operandes, donc 256 lectures pour permettre a tous les warps de continuer. C'est tres couteux.
Solutions possibles :
- Reduire le nombre de warps pouvant sonder la table des marques a chaque cycle (reduit le parallelisme).
- Solution courante : mettre un cardinal de la table des marques de 3 ou 4 et mettre en place une instruction NOR qui attend que chaque bit de la table des marques soit a 0 pour executer l'instruction.
Pipeline a 2 boucles : fonctionnement
Dans une architecture a deux boucles :
- La premiere boucle selectionne un warp pour l'I-Buffer, verifie le PC et accede a la prochaine instruction (dans le cache).
- La seconde boucle selectionne une instruction dans l'I-Buffer qui n'a plus aucune dependance et l'ajoute a l'execution.
Le meme warp est donc utilise pour plusieurs operations en parallele.
Pipeline a 3 boucles : l'Operand Collector
Dans un systeme a 3 boucles : cacher la latence GPU necessite beaucoup de warps par coeur. Pour supporter le switch de warp cycle par cycle, il faut un grand fichier de registre (de l'ordre de 256 KB par exemple).
L'implementation naive d'un fichier de registre necessite un port par operande par instruction emise par cycle. Une maniere de reduire la taille : simuler un grand nombre de ports en utilisant des banques de memoires a port unique. C'est la structure appelee OC (Operand Collector), introduite par l'architecture Fermi de Nvidia.
Banques de registres
Le probleme des banques : quand une operation demande par exemple une lecture sur R5 et R1 (tous deux dans la banque 1), ca cree un conflit et demande 2 cycles pour acceder aux donnees. Et si toutes les operations utilisent une seule banque, le principe devient totalement inefficace.
L'Operand Collector en detail
L'OC contient des CU (Collection Units) qui vont enlever ce conflit. Leur principe est similaire a la station de reservation dans l'algorithme de Tomasulo : l'arbitre selectionne les operandes de sorte qu'il n'y ait pas de conflits dans un cycle donne, tout en considerant le WB (Write-Back).
Le probleme WAR (Write After Read)
Le seul probleme connu de l'OC : il n'y a pas d'ordre d'execution entre les differentes instructions, ce qui peut engendrer le probleme de WAR (Write After Read). Une instruction ecrit sur un registre avant qu'une instruction precedente l'ait lu.
Solutions proposees :
- Permettre a seulement une instruction de collecter les operandes dans l'OC un par un. Ca reduirait de 10% les performances de l'OC selon les etudes.
- Pour proposer du parallelisme dans l'OC : un "bloomboard" pour traquer les lectures de registres.
- Architecture Maxwell de Nvidia : introduction d'une "barriere de dependance a la lecture" geree par des instructions de controle, evitant les hazards WAR pour certaines instructions.
Hasards structurels et replay d'instructions
Dans le pipeline GPU il y a aussi des gestions de hasards structurels. Par exemple, l'etape de lecture de registre peut ne plus avoir d'OCU (Operand Collector Units) disponibles. La majorite des hasards structurels sont relies a la memoire systeme : une seule instruction memoire executee par un warp peut etre decoupee en une multitude d'operations et peut utiliser a plein potentiel la portion du pipeline.
Dans un pipeline CPU, la solution est de commencer a executer les instructions suivantes non dependantes. Mais dans un systeme multi-threade c'est moins apprecie pour deux raisons :
- La taille du fichier de registre et le nombre d'etapes dans le pipeline GPU pour supporter un pipeline graphique peut impacter le chemin critique.
- Caler une instruction derriere un warp peut decaler les instructions d'autres warps en cas de synchronisation (comme sur l'architecture Pascal).
Pour eviter ces problemes, les GPUs implementent une sorte d'instruction a rejouer. C'est utilise dans certains CPUs pour reparer les predictions speculatives : quand une instruction ne peut pas s'executer (ressource non disponible, dependance non resolue), elle est remise en file pour etre re-essayee plus tard, sans bloquer le reste du pipeline.
Replay vs. stall
Synthese : les 3 boucles ensemble
Sources : General-Purpose Graphics Processor Architecture (Aamodt, Fung, Rogers) ; SIMT Deadlock (Ahmed, UBC) ; Basic Concepts in GPU Computing (Hao Gao)
Veille sécurité
La suite, une fois par mois
Ce qui bouge vraiment sur la surface d'attaque externe, NIS2 et la sécurité applicative, écrit par le pentester qui signe ces articles. Un envoi par mois, désinscription en un clic.
Votre adresse ne sert qu'à cet envoi. Voir la politique de confidentialité.