論文ノートライブラリに戻る
arXiv 2023ICLR 2024言語モデルと Transformer論文ノート

FlashAttention-2

GPU が暇そうだ

原論文

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

論文の著者

Tri Dao

発表先
ICLR 2024国際会議
arXiv への初回投稿
arXiv:2307.08691
この論文を引用 · BibTeX

引用情報はリンク先の論文の版に対応し、原論文の著者を記載しています。

@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}
}
このページの内容

FlashAttention は tiling、online softmax、recomputation を使い、attention 行列が HBM を何度も往復する問題を解いた。メモリ使用量が大きく減り、計算も速くなった。

ところが GPU の仕事表を開くと、様子がおかしい。

どうして……

こんなに暇なのだろう?

問題を定義する

GPU の中では、仕事を二段階に分けている。

GPU には同時に働ける Streaming Multiprocessor(SM)が多数ある。プログラムはスレッドを thread block にまとめて SM に渡す。block の中ではさらに warp に分かれ、通常は一組 32 スレッドで動く。

SM を工場、thread block を仕事の指示書、warp を実際に働く班だと思えばよい。

第一世代の FlashAttention は主に batch size × attention head 数に応じて仕事を割り当てる。論文の A100 には 108 個の SM がある。batch size が 1、head が 8 個なら、thread block は 8 個しかない。

108 の工場に、指示書は 8 枚。

残りの 100 は? ひとまず昼寝でもするしかなさそうだ。

さらに系列を長くしても、8 枚の指示書が分厚くなるだけで、稼働する工場の数は増えない。論文によれば、第一世代の演算スループットは理論上のピークの 25~40% にとどまる。GPU にはまだ余力がある。

しかも、それだけではない。

Tensor Cores は行列積が得意だが、softmax には行列積以外の演算も多い。簡単そうな演算でも実行効率は行列積よりずっと低く、全体を遅くする。また、第一世代では一つの block 内の warp が K,VK,V を分担し、計算後に shared memory を通じて部分結果を交換し、同期してまとめる。

ここまでの問題を整理しよう。

SM の間では仕事の数が少なすぎる。warp の間では仕事の分け方がよくない。

それなら仕事を細かく切って、もっと多くの SM を同時に動かせばよいのでは?

しかし attention はそう簡単に分けられない。softmax の一行では正規化の情報を共有する必要がある。逆伝播では、別々の block が同じ勾配に値を足すこともある。大きく切れば GPU が暇になり、細かく切りすぎれば皆が互いを待つ。

全員に仕事を渡しつつ、会議ばかりにならない切り方はあるだろうか?

FlashAttention-2 が解こうとするのはこの問題だ。

解決方法

著者は前向き計算の仕事を二段階で分け直し、thread block ごとに別々の query 行を渡したうえで、一つの block 内でも warp ごとに別々の query 行を担当させる。そう分けた後も、各行の softmax を最後まで計算できなければならない。一行を追いながら見ていこう。

行ごとに仕事を渡す

まず表に出てくる三つの文字を確認しておくと、QQ は「何を探すか」、KK は照合する手がかり、VV は最後に取り出す内容だ。attention のスコアを表で考えると、横の行が QQ、縦の列が KK、各マスは両者を組み合わせたスコアになる。

softmax は行に沿って計算する。同じ行のスコアは分母を共有するが、別の行には別の分母がある。そこで著者は、一組の行を丸ごと一つの thread block に任せる。その block が必要な K,VK,V の小さなブロックを順に読み、自分の行の出力を完成させる。

原論文の Figure 2 を見よう。左図では一色が query 行の一組、つまり一人の worker(thread block)の仕事を表す。白いマスは causal mask によって計算を省く部分だ。文章を生成するとき、前の単語は未来の単語を見られないので、表の右上が空白になる。

原論文 Figure 2 の抜粋。arXiv:2307.08691v1、PDF 8 ページ。

一人目の worker が最初の行の組を計算し、二人目は次の組を計算する。両者が同じ K,VK,V のブロックを読むことはあっても、softmax の途中結果を交換する必要はない。先ほどの batch が 1、head が 8 個の例に戻ろう。各 head は独立した attention 計算だ。その query 行をそれぞれ 16 組に分ければ、8 枚の指示書は 8×16=1288\times16=128 枚になる。16 は分担を示すための仮の数で、実際の組数はブロックサイズによる。要点は、系列が長くなれば並列に実行できる仕事も増やせることだ。

右図では、なぜ列に沿って分けるのだろう? 逆向き計算では dQ,dK,dVdQ,dK,dV、つまり Q,K,VQ,K,V に戻す勾配を求める。一つの K,VK,V ブロックには、多くの query 行から寄与が集まる。一列を一人の worker に任せれば、その列の dK,dVdK,dV を手元で蓄積できる。

一方、dQdQ には複数の列から寄与が届く。worker は atomic add を使って dQdQ に足し、同時書き込みで値が失われないようにする。前向きでは各自が出力行を担当し、逆向きでは各自が K,VK,V の勾配を担当する。

割り算は最後に

query 行を任された worker も、K,VK,V はブロックごとに読まなければならない。しかし softmax の分母は、行のスコアをすべて見終えるまで確定しない。ブロックが来るたびに途中の出力を割ればよい? それもできるし、第一世代はそうしていた。ただし、次のブロックにもっと高いスコアがあれば、値を再びスケーリングして割り直す。

小さな数字で計算してみよう。

一行のスコアを [3,1][3,1] と [4,2][4,2] の二つに分け、対応する VV を [1,0][1,0] と [3,2][3,2] とする。指数の値が大きくなりすぎないよう、今までの最大スコア mm を基準にする。割る前の指数の和 ℓ\ell と重み付き和 UU も持っておく。

FlashAttention-2 の Algorithm 1 を基に DOCSAID が作成。二つのスコアブロックを処理し、最後に一度だけ O = U / ℓ を計算する。

図の最初のブロックを見よう。最大スコアは 33 なので、ℓ1=e3−3+e1−3=1+e−2≈1.1353\ell_1=e^{3-3}+e^{1-3}=1+e^{-2}\approx1.1353。重み付き和は U1=1×1+e−2×0=1U_1=1\times1+e^{-2}\times0=1。第一世代ならここで途中の出力 U1/ℓ1≈0.8808U_1/\ell_1\approx0.8808 を計算する。第二世代は ℓ1\ell_1 と U1U_1 を持つだけで、まだ割らない。

二つ目のブロックには、より高いスコア 44 がある。古い値は 33 を基準にしていたので、基準を 44 にそろえるために ℓ1,U1\ell_1,U_1 に e3−4=e−1e^{3-4}=e^{-1} をかける。新しいブロックを足すと、ℓ2=e−1ℓ1+1+e−2≈1.5530\ell_2=e^{-1}\ell_1+1+e^{-2}\approx1.5530、U2=e−1U1+3+2e−2≈3.6386U_2=e^{-1}U_1+3+2e^{-2}\approx3.6386 となる。二つとも読み終えて初めて O=U2/ℓ2≈2.3429O=U_2/\ell_2\approx2.3429 と割る。行全体で softmax を直接計算しても、答えは同じだ。

これを一般の形で書くため、SjS_j を新しく読んだスコアのブロック、VjV_j をそれに対応する value とし、プライムでこのブロックを読んだ後の状態を表す。

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}

式の前半にある em−m′e^{m-m'} が、図の e−1e^{-1} に当たる。古い分母と重み付き和を新しい最大値の基準に合わせる係数だ。後半では新しいスコアの指数を ℓ′\ell' に、その VjV_j による重み付きの寄与を U′U' に足す。

実際の attention では VjV_j はベクトルの組で、UU もベクトルになる。図では手計算しやすいように一つの数を使った。それぞれの query 行が自分の m,ℓ,Um,\ell,U を保ち、すべて読み終わってから O=U/ℓO=U/\ell を出す。

逆向き計算では attention の重みを再計算する。そのため著者は、一行につき正規化用の数 L=m+log⁡ℓL=m+\log\ell を一つだけ保存する。eL=emℓe^L=e^m\ell なので、スコア SijS_{ij} の重みは Pij=eSij−LiP_{ij}=e^{S_{ij}-L_i} と書ける。スコアの再計算は必要だが、重みの行列全体を残す必要も、mm と ℓ\ell を別々に保存する必要もない。

数回の割り算を省く意味はあるのだろうか? 論文によれば、A100 の理論スループットは FP16/BF16 の行列積で 312 TFLOPs/s、通常の FP32 演算で 19.5 TFLOPs/s だ。後者を減らせば、Tensor Cores が得意な行列積により多くの時間を使える。

warp の持ち場も変える

thread block を増やせば、より多くの SM に仕事が回る。次は一つの block の中を開き、warp を見よう。原論文の Figure 3 では、オレンジの破線が warp ごとに分けたデータ、青の破線がすべての warp から使えるデータを表す。

原論文 Figure 3 の抜粋。arXiv:2307.08691v1、PDF 9 ページ。

左では四つの warp が同じ QQ を見て、K,VK,V の一部ずつを受け取る。計算が終わっても、それぞれが持つのは同じ出力行の一部分だ。完成させるには部分結果を shared memory に書き、ほかの warp を待ち、読み出して合わせる。論文では split-K と呼ぶ。

右では分け方を逆にする。どの warp も K,VK,V を使え、QQ を四つに分ける。一つ目の warp は自分の出力行を作り、二つ目は次の行を作る。出力行の担当が決まっているので、前向き計算では同じ行をつなぎ合わせるための shared memory 会議がいらない。逆向き計算には勾配間の依存が残るため、一部の同期は必要だ。

二段階の分担がつながった。一つの head の query 行をより多くの block に配り、block の中でも warp に分ける。各行の softmax で割るのは最後だけだ。

考察

まず attention だけを測る

原論文の Figure 4(a) は、A100 80GB SXM4 で causal mask を使わず、head の幅を 64 とした attention の前向きと逆向きの合計を比べている。横軸は系列長、縦軸は論文の FLOPs の式から換算したスループット(TFLOPs/s)だ。同じ設定なら棒が高いほど速い。オレンジが第一世代、紫が第二世代を表す。

原論文 Figure 4(a) の抜粋。arXiv:2307.08691v1、PDF 10 ページ。

8k では第一世代が 110、第二世代が 175 TFLOPs/s で、比は 175/110≈1.59175/110\approx1.59 倍。16k では 110 と 176 になる。右端の PyTorch に付いた OOM は、この設定でメモリが足りなかったことを表す。

著者はこの図で一回の測定の token 総数を 16k に固定したので、系列を長くするほど batch は小さくなり、この点が冒頭の問題につながる。8k の batch は 2、16k では 1 だ。

この図では head が 32 個ある。16k のとき、第一世代が batch と head から割り当てる仕事は 1×32=321\times32=32 組だけで、A100 の SM は 108 個ある。query 行も別々の block に分ければ、この不足を補える。

次に学習全体を測る

attention の層が速くなった。モデル全体はどうだろう? 原論文の Table 1 では、8 枚の A100 で GPT 系モデルを学習し、FlashAttention を使わない場合、第一世代、第二世代を比べている。1.3B と 2.7B はパラメータ数、2k と 8k は token で数えた文脈長だ。表の同じ行なら、GPU 一枚あたりの TFLOPs/s が高いほど学習スループットも高い。

原論文 Table 1 の抜粋。arXiv:2307.08691v1、PDF 12 ページ。

まず 1.3B の二行を横に読もう。文脈長 2k では第一世代が 189、第二世代が 196 TFLOPs/s で、約 4% の向上。8k では 170 から 220 へ、約 29% の向上だ。2.7B の 8k でも 175 から 225 へ、約 29% 上がる。同じ行で FlashAttention を使わない場合は 80 なので、第二世代はその約 2.8 倍だ。

この表では、短い文脈の伸びは小さく、長い文脈の学習では利益が大きい。系列に沿って並列の仕事を増やす理由とも合っている。

最後に、最高値 225 TFLOPs/s は、著者によって 72% の model FLOPs utilization に換算されている。108 個の SM の利用率は別のハードウェア指標だ。表の TFLOPs/s はモデルの FLOPs 推定値を所要時間で割ったものだ。先行研究の数え方に従い、その式では causal mask によって省かれるスコア表の約半分を差し引いていない。同じ行の条件で学習スループットを比較するための数値として読もう。

結論

第一世代の FlashAttention が解いたのは、データを運びすぎる問題だった。第二世代は、仕事をどう配るかに取り組む。

query の系列に沿って thread block を増やし、より多くの SM を同時に働かせる。warp の分担を変えてデータの受け渡しを減らし、online softmax の計算順序を変えて行列積以外の演算も一部省く。

この設計は後に PyTorch SDPA や Hugging Face の高速化の選択肢にもなった。ただし、密な attention の計算量は今も系列長の二乗に比例し、A100 に最適な分担が H100 や B200 でも最適とは限らない。

では、全員が忙しそうなら、生産ライン全体にも無駄はないのだろうか?

次回は H100 の出番だ。