Retour à la bibliothèque
arXiv 2023ICLR 2024Langage et TransformersNotes de lecture

FlashAttention-2

Le GPU se tourne les pouces

Article original

FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning

Auteurs de l’article

Tri Dao

Publication
ICLR 2024Conférence
Premier dépôt sur arXiv
arXiv:2307.08691
Citer cet article · BibTeX

La référence correspond à la version liée et cite les auteurs de l’article original.

@misc{transformersflashattention22023,
  title = {{FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning}},
  author = {Tri Dao},
  year = {2023},
  eprint = {2307.08691},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2307.08691}
}
Sur cette page

Grâce au découpage en blocs, au softmax en ligne et au recalcul, FlashAttention a évité à la matrice d'attention de faire sans cesse l'aller-retour avec la mémoire HBM. La consommation de mémoire a nettement baissé, et le calcul s'est aussi accéléré.

Mais lorsqu'on ouvre la liste des tâches du GPU, quelque chose cloche.

Comment ça...

il n'a presque rien à faire ?

Définir le problème

Dans un GPU, le travail se répartit à deux niveaux.

Un GPU possède de nombreux Streaming Multiprocessors (SM) capables de travailler en même temps. Le programme regroupe des threads dans un thread block qu'il confie à un SM. À l'intérieur d'un block, les threads sont répartis en warps, généralement de 32 threads chacun.

Imaginons les SM comme des usines, les thread blocks comme des ordres de fabrication et les warps comme les équipes à l'ouvrage.

La première génération de FlashAttention répartit principalement le travail selon le nombre de batchs × le nombre de têtes d'attention. L'A100 cité dans l'article possède 108 SM. Si la taille du batch est de 1 et qu'il y a 8 têtes, cela ne donne que 8 thread blocks.

Cent huit usines. Huit ordres de fabrication.

Et les cent autres ? Elles peuvent toujours faire la sieste.

Une séquence plus longue ne fait en outre qu'épaissir ces huit ordres, sans augmenter le nombre d'usines occupées. Selon l'article, la première génération n'atteint que 25 à 40 % du débit de calcul maximal théorique. Le GPU a donc encore beaucoup de ressources disponibles.

Et ce n'est pas tout.

Les Tensor Cores excellent dans les produits matriciels, alors que le softmax nécessite de nombreuses opérations qui n'en sont pas. Ces opérations, simples en apparence, s'exécutent beaucoup moins efficacement et ralentissent l'ensemble. De plus, dans un block de la première génération, différents warps se partagent K,VK,V, puis échangent leurs résultats partiels en mémoire partagée, se synchronisent et les réunissent.

Résumons le problème :

Entre les SM, il y a trop peu de travail distribué ; entre les warps, le travail est mal réparti.

Pourquoi ne pas découper davantage et faire travailler plus de SM à la fois ?

L'attention ne se laisse pas découper aussi facilement. Tous les scores d'une ligne du softmax ont besoin de la même information de normalisation. Durant la rétropropagation, plusieurs blocs peuvent aussi devoir contribuer au même gradient. Si les morceaux sont trop gros, le GPU attend ; s'ils sont trop petits, tout le monde attend ses voisins.

Comment donner du travail à chacun sans passer la journée en réunion ?

Voilà le problème que FlashAttention-2 cherche à résoudre.

Résoudre le problème

Les auteurs divisent le calcul avant à deux niveaux. Des thread blocks différents prennent chacun un groupe de lignes de requêtes ; au sein d'un block, différents warps prennent eux aussi leurs propres lignes. Il faut ensuite que chaque ligne puisse mener son softmax jusqu'au bout.

Répartir le travail par ligne

Commençons par les trois lettres du tableau des scores. La lettre QQ représente ce que l'on cherche, KK fournit les indices auxquels le comparer et VV contient ce que l'on récupérera finalement. Imaginez les scores d'attention comme un tableau dont les lignes viennent de QQ et les colonnes de KK, chaque case mesurant l'accord entre les deux.

Le softmax se calcule le long d'une ligne. Les scores d'une même ligne partagent donc un dénominateur, tandis que chaque autre ligne possède le sien. Les auteurs choisissent par conséquent de confier un groupe de lignes entières à un thread block. Celui-ci lit successivement les blocs de K,VK,V nécessaires et produit les sorties de ses lignes.

Regardons la Figure 2 de l'article. Dans le panneau de gauche, chaque couleur correspond à un groupe de lignes de requêtes confié à un worker (un thread block). Les cases blanches ne sont pas calculées à cause du masque causal. Pendant la génération de texte, un mot ne peut pas regarder les mots futurs : le coin supérieur droit du tableau reste donc vide.

Extrait de la Figure 2, arXiv:2307.08691v1, page 8 du PDF.

Le premier worker calcule le premier groupe de lignes, le deuxième calcule le suivant. Tous deux peuvent lire le même bloc de K,VK,V, sans devoir échanger les résultats intermédiaires de leur softmax. Dans l'exemple précédent d'un batch et de huit têtes, chaque tête réalise son propre calcul d'attention. Si l'on découpe ses lignes de requêtes en 16 groupes, les huit ordres de fabrication deviennent 8×16=1288\times16=128. Le nombre 16 ne sert qu'à illustrer la répartition ; le nombre réel dépend de la taille des blocs. Mais, quand la séquence s'allonge, les groupes de travail peuvent enfin se multiplier eux aussi.

Pourquoi le panneau de droite passe-t-il aux colonnes ? Le calcul arrière produit dQ,dK,dVdQ,dK,dV, les gradients renvoyés vers Q,K,VQ,K,V. Un bloc de K,VK,V reçoit des contributions de nombreuses lignes de requêtes. En confiant une colonne à un worker, on lui permet d'accumuler lui-même les dK,dVdK,dV de cette colonne.

En revanche, dQdQ reçoit des contributions de plusieurs colonnes. Les workers utilisent donc des additions atomiques pour mettre dQdQ à jour sans que des écritures simultanées s'écrasent mutuellement. À l'aller, chacun possède ses lignes de sortie ; au retour, chacun possède ses gradients de K,VK,V.

Diviser seulement à la fin

Même responsable de ses lignes, un worker doit lire K,VK,V bloc après bloc. Or le dénominateur du softmax n'est connu qu'après avoir vu tous les scores de la ligne. Peut-on diviser une sortie partielle après chaque bloc ? Oui, c'est ce que fait la première génération. Mais si le bloc suivant contient un score plus élevé, il faut remettre les valeurs à l'échelle, puis diviser de nouveau.

Essayons avec quelques nombres.

Découpons les scores d'une ligne en [3,1][3,1] et [4,2][4,2], avec pour valeurs VV respectives [1,0][1,0] et [3,2][3,2]. Pour maîtriser les exponentielles, prenons le plus grand score vu jusqu'ici, mm, comme référence. Gardons aussi la somme des exponentielles ℓ\ell et la somme pondérée UU, avant toute division.

Schéma DOCSAID d'après l'algorithme 1 de FlashAttention-2 : deux blocs de scores et une seule division finale, O = U / ℓ.

Commençons par le premier bloc du schéma. Son score maximal est 33, d'où ℓ1=e3−3+e1−3=1+e−2≈1.1353\ell_1=e^{3-3}+e^{1-3}=1+e^{-2}\approx1.1353. Sa somme pondérée vaut U1=1×1+e−2×0=1U_1=1\times1+e^{-2}\times0=1. À ce stade, la première génération calcule déjà une sortie partielle, U1/ℓ1≈0.8808U_1/\ell_1\approx0.8808. La seconde garde ℓ1\ell_1 et U1U_1 sans diviser.

Le deuxième bloc apporte un score plus élevé : 44. Les anciennes valeurs prenaient 33 comme référence. Pour tout ramener à la nouvelle échelle, on multiplie les anciens ℓ1,U1\ell_1,U_1 par e3−4=e−1e^{3-4}=e^{-1}. En ajoutant le nouveau bloc, on obtient ℓ2=e−1ℓ1+1+e−2≈1.5530\ell_2=e^{-1}\ell_1+1+e^{-2}\approx1.5530 et U2=e−1U1+3+2e−2≈3.6386U_2=e^{-1}U_1+3+2e^{-2}\approx3.6386. Ce n'est qu'une fois les deux blocs traités que l'on calcule O=U2/ℓ2≈2.3429O=U_2/\ell_2\approx2.3429. Un softmax calculé directement sur toute la ligne donne le même résultat.

Sous forme générale, SjS_j désigne un nouveau bloc de scores et VjV_j les valeurs correspondantes. L'apostrophe indique l'état après la lecture de ce bloc :

m′=max⁡(m,max⁡Sj),ℓ′=em−m′ℓ+∑eSj−m′,U′=em−m′U+eSj−m′Vj.\begin{aligned} m'&=\max(m,\max S_j),\\ \ell'&=e^{m-m'}\ell+\sum e^{S_j-m'},\\ U'&=e^{m-m'}U+e^{S_j-m'}V_j. \end{aligned}

Le facteur em−m′e^{m-m'} au début des mises à jour est le e−1e^{-1} de notre schéma, qui aligne l'ancien dénominateur et l'ancienne somme pondérée sur le nouveau maximum. Les autres termes ajoutent les exponentielles du nouveau bloc à ℓ′\ell' et leur contribution pondérée par VjV_j à U′U'.

Dans un vrai calcul d'attention, VjV_j contient des vecteurs : UU est donc lui aussi un vecteur. Le schéma utilise des nombres uniques pour permettre le calcul à la main. Chaque ligne de requêtes garde ses propres m,ℓ,Um,\ell,U, puis produit O=U/ℓO=U/\ell à la fin.

Le calcul arrière doit recalculer les poids d'attention. Les auteurs n'enregistrent qu'un nombre de normalisation par ligne, L=m+log⁡ℓL=m+\log\ell. Comme eL=emℓe^L=e^m\ell, le poids d'un score SijS_{ij} s'écrit Pij=eSij−LiP_{ij}=e^{S_{ij}-L_i}. Il faut encore recalculer les scores, mais pas conserver toute la matrice des poids ni stocker séparément mm et ℓ\ell.

Pourquoi économiser quelques divisions ? L'article donne pour l'A100 un débit théorique de 312 TFLOPs/s en produit matriciel FP16/BF16, contre 19,5 TFLOPs/s pour les opérations FP32 ordinaires. En réduisant ces dernières, on laisse davantage de temps aux produits matriciels dont les Tensor Cores sont spécialistes.

Réorganiser aussi les warps

Davantage de thread blocks donnent du travail à davantage de SM. Ouvrons maintenant l'un de ces blocks pour regarder ses warps. Dans la Figure 3, les contours orange en pointillés indiquent les données réparties entre warps ; les contours bleus désignent les données accessibles à tous.

Extrait de la Figure 3, arXiv:2307.08691v1, page 9 du PDF.

À gauche, quatre warps voient le même QQ, mais reçoivent chacun une partie de K,VK,V. Au bout du calcul, chacun ne possède qu'une partie des mêmes lignes de sortie. Pour obtenir les lignes complètes, ils écrivent leurs résultats partiels en mémoire partagée, attendent les autres, puis relisent et additionnent le tout. L'article appelle cette organisation split-K.

À droite, la répartition s'inverse, avec K,VK,V accessibles à tous les warps et QQ partagé en quatre. Le premier warp produit ses propres lignes de sortie, le deuxième produit les suivantes. Puisque chaque ligne a son responsable, le calcul avant n'a plus besoin d'une réunion en mémoire partagée pour la reconstituer. Les gradients du calcul arrière gardent certaines dépendances et nécessitent encore de la synchronisation.

Les deux niveaux de répartition se rejoignent ici. On distribue les lignes de requêtes d'une tête entre davantage de blocks, puis les lignes d'un block entre ses warps. Pour chaque ligne, la division du softmax attend la fin.

Discussion

D'abord, mesurer l'attention

La Figure 4(a) compare le calcul d'attention avant et arrière réunis sur une A100 80GB SXM4, sans masque causal et avec une dimension de tête de 64. L'axe horizontal donne la longueur de séquence. L'axe vertical donne un débit en TFLOPs/s, calculé à partir de la formule de FLOPs de l'article : à réglage égal, une barre plus haute signifie une exécution plus rapide. L'orange représente la première génération, le violet la deuxième.

Extrait de la Figure 4(a), arXiv:2307.08691v1, page 10 du PDF.

Pour une séquence de 8k, la première génération atteint 110 TFLOPs/s et la deuxième 175, soit 175/110≈1.59175/110\approx1.59 fois plus. À 16k, les valeurs sont 110 et 176 ; l'écart demeure. PyTorch porte la mention OOM tout à droite : la mémoire était insuffisante dans ce réglage.

Dans cette figure, les auteurs fixent à 16k le nombre total de tokens par essai, si bien que plus la séquence est longue, plus le batch est petit, ce qui renvoie à notre question de départ. À 8k, le batch vaut 2 ; à 16k, il vaut 1.

La figure utilise 32 têtes. À 16k, la première génération ne génère donc que 1×32=321\times32=32 travaux à partir du batch et des têtes, face aux 108 SM de l'A100. Découper également les lignes de requêtes en blocks apporte le travail parallèle qui manque alors.

Puis, mesurer tout l'entraînement

Une couche d'attention plus rapide, c'est bien. Et le modèle entier ? Dans la Table 1, les auteurs entraînent des modèles de type GPT sur huit A100 et comparent l'absence de FlashAttention, la première génération et la deuxième. Les mentions 1.3B et 2.7B correspondent au nombre de paramètres ; 2k et 8k sont les longueurs de contexte en tokens. À l'intérieur d'une même ligne, plus les TFLOPs/s par GPU sont élevés, plus le débit d'entraînement est grand.

Extrait de la Table 1, arXiv:2307.08691v1, page 12 du PDF.

Lisons horizontalement les deux lignes du modèle 1.3B. Pour un contexte de 2k, la première génération obtient 189 TFLOPs/s et la deuxième 196, soit environ 4 % de plus. À 8k, on passe de 170 à 220, soit environ 29 % de plus. Le modèle 2.7B à 8k passe lui aussi de 175 à 225, une hausse d'environ 29 %. Sans FlashAttention, la même ligne n'atteint que 80 : la deuxième génération est donc environ 2,8 fois plus rapide.

Dans ce tableau, le contexte court profite relativement peu du changement, alors que l'entraînement en contexte long y gagne davantage. Cela correspond à l'intérêt de créer des tâches parallèles le long de la séquence.

Enfin, les auteurs convertissent le maximum de 225 TFLOPs/s en 72 % de model FLOPs utilization. L’utilisation des 108 SM est une mesure matérielle distincte. Les TFLOPs/s de la table proviennent d'une estimation des FLOPs du modèle divisée par le temps écoulé. Conformément à une convention de la littérature, la formule ne retranche pas la moitié environ du tableau des scores évitée par le masque causal. Ces nombres permettent de comparer les débits d'entraînement dans les mêmes conditions.

Conclusion

La première génération de FlashAttention s'attaquait à l'excès de transferts de données. La deuxième se demande comment répartir le travail.

Elle lance davantage de thread blocks le long de la séquence de requêtes pour occuper plus de SM, réorganise les warps afin de réduire leurs échanges, puis change l'ordre des opérations du softmax en ligne pour économiser une partie des calculs hors produit matriciel.

Ce dispositif est ensuite devenu une option d'accélération dans PyTorch SDPA et chez Hugging Face. Toutefois, le volume de calcul de l'attention dense croît toujours comme le carré de la longueur de séquence, et la meilleure répartition sur A100 ne l'est pas nécessairement sur H100 ou B200.

Après tout, voir tout le monde occupé prouve-t-il que la chaîne entière ne perd pas de temps ?

Dans la prochaine note, place au H100.