Eh GPU, qu’est-ce qui se passe avec ma matrice ?

What's happening with my matrix, GPU?

Un guide doux pour comprendre comment les GPU effectuent la multiplication de matrices

La multiplication de matrices ; le Saint Graal des réseaux de neurones profonds et des géants de la compréhension du langage moderne. En tant que MLEs ou scientifiques des données, nos doigts sont trop rapides pour taper tf.matmul ou torch.matmul et nous ne regardons jamais en arrière. Mais ne me dites pas que vous n’avez jamais eu une infatuation de milliseconde pour savoir ce qui pourrait arriver à cette matrice lorsque elle entre dans le GPU ! Si c’est le cas, vous êtes au bon endroit. Joignez-vous à moi dans un voyage à travers les fascinantes complexités à l’intérieur d’un GPU.

Je vais vous expliquer comment ces puissances de calcul broient les chiffres. Vous apprendrez trois choses impressionnantes et peu connues que les GPUs font, lorsqu’ils se retrouvent face à face avec des matrices. À la fin de ce billet de blog, vous aurez une bonne compréhension de la façon dont la multiplication de matrices fonctionne à l’intérieur des GPUs.

GEMM : Un vrai joyau 💎 pour un GPU

GEMM ou multiplication de matrices généralisée est le noyau qui est exécuté lorsque les GPUs effectuent la multiplication de matrices.

C = a (A.B) + b C

• Si l’art est la façon dont nous exprimons notre humanité, où se situe l’IA ?
• Analyse de performance et optimisation de modèle PyTorch
• Maîtriser la gestion de configuration en apprentissage automatique avec Hydra.

Ici, a et b sont des scalaires, A est une matrice de dimension MxK, B est une matrice de dimension KxN, et donc C est une matrice de dimension MxN. C’est aussi simple que ça ! Vous vous demandez peut-être pourquoi cette addition à la fin existe. Il s’avère que c’est un motif assez courant pour les réseaux de neurones (par exemple, ajouter un biais, appliquer ReLU, ajouter des connexions résiduelles).

Astuce #1 : Le produit externe est hors de ce monde 👽

Si on vous demande d’écrire un algorithme de multiplication de matrices à partir des premiers principes, voici ce que vous ferez (à moins que vous ne soyez doté d’un GPU à la place d’un cerveau, ce qui économiserait de l’argent pour un MLE !).

for (int i = 0; i < M; ++i)    for (int j = 0; j < N; ++j)        for (int k = 0; k < K; ++k)             C[i][j] += A[i][k] * B[k][j];

Voici une animation qui montre ce que cela fait.

Mais saviez-vous que les GPUs détestent cette implémentation 🤔 ? Pour comprendre pourquoi c’est le cas, vous devez comprendre l’architecture de la mémoire GPU,

Pour toutes les comparaisons et les spécifications, j’utiliserai les spécifications de la GPU Nvidia A100.

Un GPU a trois niveaux de mémoire principaux,

• Mémoire globale ou HBM (ce que vous appelez généralement la mémoire GPU et ce que vous voyez lorsque vous exécutez nvidia-smi)
• Mémoire partagée (une mémoire locale qui est dédiée à un seul processeur de flux [ou SM] et partagée entre les threads qui s’exécutent dans cet SM)
• Registres (alloués individuellement aux threads pour effectuer leur charge de travail)

Voici à quoi cela ressemble,

La première chose à noter est que la mémoire partagée (appelée SRAM à partir de maintenant) est bien plus petite que la HBM, sans parler des registres. Votre matrice ne va donc pas rentrer dedans (dans la plupart des cas). Si nous revenons à notre animation, pour une seule ligne de A, toutes les colonnes de B doivent être récupérées, et le processus doit être répété pour toutes les lignes de A. Cela signifie que le GPU doit effectuer de nombreuses lectures pour calculer la sortie. La HBM (~1,5 To/s) est plusieurs ordres de grandeur plus lente que la SRAM (~19 To/s).

Pour mettre cela en chiffres, disons que vous voulez multiplier une matrice 10x20 et une matrice 20x30, vous devez lire les colonnes de B 10x30=300 fois. Y a-t-il une meilleure façon de faire cela ?

Il s’avère qu’un simple tour de passe-passe peut faire beaucoup de chemin ici ! Il suffit de changer l’ordre des boucles, de sorte que k devienne la boucle externe. Et vous avez terminé ! 😮

for (int k = 0; k < K; ++k)     for (int i = 0; i < M; ++i)        for (int j = 0; j < N; ++j)            C[i][j] += A[i][k] * B[k][j];

Nous n’avons pas touché au calcul réel, seulement à l’ordre des boucles, donc nous devrions obtenir le même résultat qu’auparavant. Voici à quoi ressemble maintenant la multiplication de matrices !

Vous voyez, nous apportons seulement une colonne de A et une rangée de B à la fois et ne regardons jamais en arrière. Cela nécessite beaucoup moins de lectures que la mise en œuvre d’origine. La seule différence est que nous calculions le produit intérieur entre deux vecteurs auparavant, maintenant nous calculons le produit extérieur.

Mais malgré tout, nous avons besoin de toute la matrice C dans la SRAM, ce qui pourrait être trop grand pour tenir dans la SRAM. Que fait CUDA alors ? Cela nous amène au deuxième tour de passe-passe.

Tour de passe-passe n°2 : Diviser et conquérir (et accumuler)

Pas de panique ! Je ne vais pas vous bombarder avec des mathématiques complexes ou des algorithmes Leetcode. La chose principale à garder à l’esprit est qu’une matrice est une disposition 2D de tuiles individuelles. L’animation suivante rend justice à ce que j’essaie d’expliquer.

Le résultat du bloc vert 💚 est la bande claire bleue de A 💙 et la bande claire jaune de B 💛. Pour aller plus loin, pour calculer la sortie, vous pouvez apporter un bloc de cette bande A et un bloc de la bande B à la fois, calculer la sortie et accumuler le résultat dans la boîte verte.

Cela nous donne un cadre flexible où nous pouvons charger une tuile de taille arbitraire (ou de bloc) de A et B et toujours calculer la réponse finale. Nous ne devons pas nous arrêter là, nous pouvons continuer à diviser le problème en problèmes encore plus petits. c’est-à-dire que la matrice est divisée en tuiles, les tuiles sont divisées en fragments, et les fragments en valeurs individuelles.

Ceci se prête bien à l’architecture d’exécution de processus dans un GPU. Il y a trois couches dans une exécution de kernel dans un GPU. Pour simplifier, nous dirons qu’un SM exécute un seul bloc de thread (bien qu’en pratique, ils les exécutent simultanément, pour réduire quelque chose connu sous le nom d’effet de queue).

• Threads
• Warps (une collection de 32 threads)
• Blocs de threads (une collection de plusieurs warps)

Le nombre exact de threads dans un bloc de threads dépend d’une architecture spécifique. Par exemple, un A100 a les spécifications suivantes.

• Maximum de 2048 threads par SM
• Maximum de 1024 threads par bloc
• Maximum de 32 blocs de threads par SM

Encadré #2: Magie de la puissance de 2

En revenant au tuilage, il a été constaté (heuristiquement) qu’une tuile de matrice de taille 256x128 par bloc de thread donne une efficacité raisonnable pour la plupart des problèmes. C’est donc une taille de tuile commune utilisée par CUDA.

Vous avez peut-être entendu parler d’une meilleure pratique consistant à garder la taille du lot, la taille de la dimension cachée en puissances de deux. C’est là que cela vient! Lorsque les dimensions de votre matrice sont des puissances de deux, elle sera entièrement divisible en un ensemble de tuiles sans reste. Sinon, cela rend votre code moins efficace.

Les calculs GPU sont plus efficaces lorsque les dimensions de votre matrice sont en puissance de 2

Que se passe-t-il lorsque ce n’est pas une puissance de 2?

Encadré #2: Quantification de tuiles

Il se produit un effet connu sous le nom de quantification de tuiles. En d’autres termes, si vous avez une dimension de rangée de tuiles de 128 mais que votre matrice a 257 éléments dans une rangée, vous aurez besoin non pas de deux, mais de trois tuiles dans une rangée (c’est-à-dire 256+1). Cela est illustré ci-dessous.

Le problème avec cela est que le bloc de threads effectue la même quantité de calcul indépendamment des données utiles qui y résident. Ainsi, vous enlevez la possibilité de faire des calculs utiles à votre GPU, ce qui conduit à des inefficacités.

Un effet similaire est connu sous le nom de quantification d’onde, où la matrice est surdimensionnée et les SM ne peuvent pas tous la contenir en même temps. Ensuite, le GPU doit effectuer le calcul en 2 “vagues”. Cependant, cela est moins préoccupant pour les GPU modernes car ils tirent parti de la concurrence pour réduire la quantification d’onde.

La quantification de tuiles se produit lorsqu’un bloc de threads doit répandre des données partiellement, la quantification d’onde se produit lorsque les SM doivent répandre des données.

Astuce #3: Un est meilleur que deux

La dernière astuce est la fusion de kernel. Plus souvent qu’autrement, il est plus rapide de faire toutes les opérations dans un seul kernel que d’avoir deux kernels appelés l’un après l’autre. Pourquoi? Parce qu’un kernel doit écrire les données sur HBM et l’autre doit les lire à nouveau. Nous avons déjà parlé de la lenteur de cette opération. Une meilleure approche consiste simplement à combiner les deux opérations en une seule. Voici quelques exemples:

• matmul + biais + relu
• convolution + biais + relu
• batchnorm + relu

Comme on peut le voir ici (je suis sûr que Pytorch a un glossaire similaire), il existe de nombreux noyaux fusionnés offerts par TensorFlow qui combinent les opérations commodes en un seul noyau. En code, cela signifie quelque chose comme ceci,

for (int m = 0; m < M; m += Mtile)     for (int n = 0; n < N; n += Ntile)        for (int k = 0; k < K; ++k)            float tmp = 0            for (int i = 0; i < Mtile; ++i)                for (int j = 0; j < Ntile; ++j)                     int row = m + i;                    int col = n + j;                    tmp += A[row][k] * B[k][col];                    // Faire d'autres choses                    C[row][col] = tmp

En d’autres termes, nous chérissons notre variable tmp jusqu’à ce que nous ayons fini tous nos calculs. Alors seulement nous écrirons le résultat de retour dans C.

Conclusion

Voilà, c’est tout. J’espère que cette excursion dans les méandres d’un GPU vous a plu. Si vous êtes intéressé par la version audio-visuelle, voici le lien vers ma vidéo YouTube.

Pour récapituler, nous avons discuté de trois choses qui rendent les GPUs vraiment rapides pour la multiplication de matrices.

• Les GPUs abandonnent la mise en œuvre plus conviviale du produit intérieur de matmul et adoptent la mise en œuvre plus efficace en lecture du produit extérieur de matmul
• Les GPUs divisent les matrices en blocs plus petits (et les blocs en fragments) et répartissent la charge de calcul sur des blocs de threads, des warps et des threads.
• Les GPUs utilisent la fusion de noyaux pour regrouper les fonctionnalités fréquemment co-occurrentes, améliorant ainsi l’efficacité du GPU.

Si vous avez aimé cette histoire, n’hésitez pas à vous abonner à IPGirl, et vous recevrez des notifications de nouveau contenu de ma part, ainsi que l’accès complet à des milliers d’histoires de qualité d’autres auteurs.

Rejoignez IPGirl avec mon lien de parrainage – Thushan Ganegedara

En tant que membre d’IPGirl, une partie de vos frais d’adhésion est reversée aux auteurs que vous lisez, et vous avez un accès complet à chaque histoire…

thushv89.medium.com

Sauf indication contraire, toutes les images sont de l’auteur

Références :

• https://docs.nvidia.com/deeplearning/performance/dl-performance-matrix-multiplication/index.html
• https://developer.nvidia.com/blog/cutlass-linear-algebra-cuda/
• https://developer.nvidia.com/blog/nvidia-ampere-architecture-in-depth/

We will continue to update IPGirl; if you have any questions or suggestions, please contact us!