FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning
- 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}
}
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 , 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 représente ce que l'on cherche, fournit les indices auxquels le comparer et contient ce que l'on récupérera finalement. Imaginez les scores d'attention comme un tableau dont les lignes viennent de et les colonnes de , 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 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.
Le premier worker calcule le premier groupe de lignes, le deuxième calcule le suivant. Tous deux peuvent lire le même bloc de , 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 . 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 , les gradients renvoyés vers . Un bloc de 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 de cette colonne.
En revanche, reçoit des contributions de plusieurs colonnes. Les workers utilisent donc des additions atomiques pour mettre à 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 .
Diviser seulement à la fin
Même responsable de ses lignes, un worker doit lire 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 et , avec pour valeurs respectives et . Pour maîtriser les exponentielles, prenons le plus grand score vu jusqu'ici, , comme référence. Gardons aussi la somme des exponentielles et la somme pondérée , avant toute division.
Commençons par le premier bloc du schéma. Son score maximal est , d'où . Sa somme pondérée vaut . À ce stade, la première génération calcule déjà une sortie partielle, . La seconde garde et sans diviser.
Le deuxième bloc apporte un score plus élevé : . Les anciennes valeurs prenaient comme référence. Pour tout ramener à la nouvelle échelle, on multiplie les anciens par . En ajoutant le nouveau bloc, on obtient et . Ce n'est qu'une fois les deux blocs traités que l'on calcule . Un softmax calculé directement sur toute la ligne donne le même résultat.
Sous forme générale, désigne un nouveau bloc de scores et les valeurs correspondantes. L'apostrophe indique l'état après la lecture de ce bloc :
Le facteur au début des mises à jour est le 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 à et leur contribution pondérée par à .
Dans un vrai calcul d'attention, contient des vecteurs : 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 , puis produit à la fin.
Le calcul arrière doit recalculer les poids d'attention. Les auteurs n'enregistrent qu'un nombre de normalisation par ligne, . Comme , le poids d'un score s'écrit . Il faut encore recalculer les scores, mais pas conserver toute la matrice des poids ni stocker séparément et .
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.
À gauche, quatre warps voient le même , mais reçoivent chacun une partie de . 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 accessibles à tous les warps et 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.
Pour une séquence de 8k, la première génération atteint 110 TFLOPs/s et la deuxième 175, soit 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 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.
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.