返回論文筆記資料庫
arXiv 2022NeurIPS 2022語言模型與 Transformer論文筆記

FlashAttention

重算比較快

原始論文

FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness

論文作者

Tri Dao · Daniel Y. Fu · Stefano Ermon · Atri Rudra · Christopher Ré

發表版本
NeurIPS 2022會議
arXiv 首次提交
arXiv:2205.14135
引用此論文 · BibTeX

引用資料對應所連結的論文版本,作者為原論文作者。

@misc{transformersflashattention2022,
  title = {{FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness}},
  author = {Tri Dao and Daniel Y. Fu and Stefano Ermon and Atri Rudra and Christopher Ré},
  year = {2022},
  eprint = {2205.14135},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2205.14135}
}
本頁內容

寫程式時,我們直覺會把算過的結果先存起來,下次直接拿來用,總比重新算一次划算。

這個直覺到了 GPU 上,怎麼好像不太對啊?

GPU 算得很快,但把結果存進記憶體、之後再讀回來,也要花時間。不僅如此,那些搬來搬去的時間,甚至比重新算一遍還久!

本篇論文的作者注意到了這個問題,所以試著在 Attention 上換一種做法,把計算拆成小塊,減少資料來回搬運;反向傳播需要中間結果時,就在 GPU 的高速記憶體裡重新算。

對,你沒看錯!

算完直接丟棄,之後有需要的時候,重新算。

定義問題

先看下圖。四個位置彼此打分,得到 4×4=164\times4=16 格;八個位置變成 8×8=648\times8=64 格。長度加倍,表格面積變四倍。圖中只畫了一個樣本、一個注意力頭;「頭」先當成一組獨立計分的向量就好。

每一列代表「這個位置」對整段序列的評分。分數還要經過 softmax,把每個分數 xx 變成 exe^x(ee 約為 2.718),再除以這一列的 exe^x 總和,權重才會加起來等於 1。後面計算輸出時,分數高的位置就占較大的比重。

一般實作會把整張分數表寫進 GPU 的大記憶體 HBM,讀回來做 softmax,再把權重表寫回去。序列長 2048 時,光是一個注意力頭的一張表就有 419 萬格;用半精度存約 8 MiB(約 8.4 MB)。模型若有多個頭、多個樣本,還要乘上去。

GPU 晶片內另有 SRAM,容量小得多,但資料送到運算單元的速度快得多。作者想把眼前需要的一小塊放進 SRAM,算完就走,不讓完整的分數表和權重表在 HBM 來回。

只是 softmax 要求同一列的所有位置共用一個分母。你若只看前半列,算出一組加起來為 1 的權重;後半列出現更大的分數時,前半列的權重該怎麼改?

解決問題

先認識這三張表

把一段文字送進注意力層後,每個位置會得到三個向量,QQ 是拿來查詢的 query,KK 是接受比對的 key,VV 是最後要依權重彙整的內容 value。假設序列有 NN 個位置,每個頭的向量長度是 dd,標準密集注意力寫成:

S=QKT∈RN×N,P=softmax⁡(S/d),O=PV.S=QK^\mathsf{T}\in\mathbb{R}^{N\times N},\qquad P=\operatorname{softmax}(S/\sqrt d),\qquad O=PV.

沿著其中一列走,一個 query 跟所有 key 打分,除以 d\sqrt d 避免向量變長時分數容易偏大;softmax 把分數變成權重,再拿這些權重對 value 做加權平均。最後留下的 OO 是輸出。麻煩的是中途的 SS 和 PP,每張都有 N2N^2 格。

FlashAttention 把 Q,K,VQ,K,V 切塊。原論文 Figure 1 畫的就是這件事:

原論文 Figure 1 中央局部,PDF 第 2 頁。

左邊是 QQ、上方是 KK、右邊是 VV。橘色小格表示這次搬進 SRAM 的資料;虛線框是原本可能整張寫進 HBM 的注意力表。紅箭頭沿 K,VK,V 的資料塊前進,藍箭頭沿 QQ 的資料塊前進。每碰到一組,就算一小格分數並更新輸出。所有 query 還是會遇到所有 key,省的是保存與搬運整張中間表,沒有少算那些配對。

四個分數,分兩次算

假設一列已經除過 d\sqrt d 的分數是 [3,1,4,2][3,1,4,2],對應的 value 在某一個維度是 [1,0,3,2][1,0,3,2]。四個位置一次看完,輸出是:

O=e3⋅1+e1⋅0+e4⋅3+e2⋅2e3+e1+e4+e2≈2.3429.O=\frac{e^3\cdot1+e^1\cdot0+e^4\cdot3+e^2\cdot2}{e^3+e^1+e^4+e^2}\approx2.3429.

現在把前兩個、後兩個分開算。為免 exe^x 太大,每組先減去自己的最大分數 mm。同一組分數都減去同一個數,softmax 的分子和分母會一起縮放,最後答案不變。我們只需留下最大值 mm、指數總和 ℓ\ell,以及還沒除以 ℓ\ell 的加權和 ν\nu。

左邊 [3,1][3,1] 減去 3,指數變成 [1,e−2][1,e^{-2}];所以 ℓ=1+e−2≈1.1353\ell=1+e^{-2}\approx1.1353,搭配 value [1,0][1,0] 得到 ν=1\nu=1。右邊 [4,2][4,2] 減去 4,也得到 ℓ≈1.1353\ell\approx1.1353,但 value 是 [3,2][3,2],所以 ν=3+2e−2≈3.2707\nu=3+2e^{-2}\approx3.2707。

兩邊各自都算對了,卻不能把 ν\nu 直接相加。左邊用 3 當基準,右邊用 4;直接相加等於把兩邊最高分當成一樣高。於是改用 4 當共同基準,把左邊的 ℓ\ell 和 ν\nu 都乘上 e3−4e^{3-4}:

ℓ=e−1(1.1353)+1.1353≈1.5530,ν=e−1(1.0000)+3.2707≈3.6386,O=ν/ℓ≈2.3429.\begin{aligned} \ell&=e^{-1}(1.1353)+1.1353\approx1.5530,\\ \nu&=e^{-1}(1.0000)+3.2707\approx3.6386,\\ O&=\nu/\ell\approx2.3429. \end{aligned}

答案回到一次看完四格的 2.34292.3429。第三塊來了,就把剛才合併的 (m,ℓ,ν)(m,\ell,\nu) 當作「前面所有塊」,照樣更新。這就是 online softmax,不存整列分數,也能讓不同小格共用最後那個分母。實際的 value 有 dd 個維度,所以 ν\nu 是向量;每列要帶著走的資料仍遠小於整張表。

訓練時,真的再算一次

前向計算從輸入走到輸出,現在不用保存整張權重表 PP。但訓練還有反向步驟,模型要算出各參數該往哪裡調,會再次用到注意力權重。FlashAttention 走到哪一格,就從 Q,KQ,K 和前向留下的正規化資料重算那一格。

回到開場那個直覺。重算會增加乘加運算,卻省去把整張 PP 寫入 HBM、再從 HBM 讀回來的時間。論文的 Theorem 2 也把這筆交換寫成資料存取量。標準做法是 Θ(Nd+N2)\Theta(Nd+N^2),分塊後是 Θ(N2d2/M)\Theta(N^2d^2/M);MM 是 SRAM 能容納的數值個數,條件是 d≤M≤Ndd\le M\le Nd。Θ\Theta 看的是長度增加時的成長趨勢,不計固定倍數。

公式告訴我們有機會少搬資料,但整趟到底有沒有跑比較快?

討論

算得更多,等得更少

來看原論文 Figure 2 左圖。作者在 A100 上測注意力的前向加反向,序列長 1024、每頭向量長 64、16 個頭、一次處理 64 個樣本,有 padding mask、沒有 dropout。

原論文 Figure 2,NeurIPS 2022,PDF 第 6 頁。
Figure 2一般注意力FlashAttention
算術量66.6 GFLOPs75.2 GFLOPs
HBM 讀寫35.3 GB4.4 GB
時間35.1 ms11.7 ms

GFLOPs 是十億次浮點運算,GB 是搬運的資料量,ms 是千分之一秒。依序讀這三列,算術量增加約 13%;HBM 讀寫量剩約八分之一;時間則從 35.1 ms 降到 11.7 ms。重算花掉的時間,確實比省下的搬運少。

中圖則顯示,塊從 64 加到 256,搬運與時間大致一起下降;加到 512,時間沒有照比例再降。SRAM 容量和 GPU 上怎麼排工作,都會影響最合適的塊大小。

序列拉長後呢?原論文 Figure 3 左邊量時間,右邊量注意力使用的記憶體:

原論文 Figure 3,NeurIPS 2022,PDF 第 9 頁。

右圖的 FlashAttention 曲線大致隨長度直線增加;一般做法的中間表則跟 N2N^2 一起長。在論文所測設定下,注意力記憶體最多差到 20 倍。不過左圖的時間仍快速上升,因為 query 和 key 的配對一個都沒少。右圖延伸到 64K 的棕線是近似方法 Linformer,別把它誤看成一般密集注意力。

注意力快了,整個模型會快多少?原論文 Table 1 的 BERT-large 提供一個答案:

原論文 Table 1 摘錄,NeurIPS 2022,PDF 第 7 頁。

達到同一訓練目標,時間從 20.0±1.520.0\pm1.5 分鐘降到 17.4±1.417.4\pm1.4 分鐘。模型還有別的層,因此整場訓練的降幅小於剛才注意力內核的降幅;這個對照也讓 Figure 2 的數字有了落地的位置。

換張卡,答案還一樣嗎?

我們也用 RTX 4090 看了一次。讓同一張卡做同樣的注意力計算,一邊用 PyTorch eager 分三步算,一邊用 v1.0.9 的 Triton 分塊前向內核;只改序列長度。設定是 fp16、一次兩個樣本、8 個頭、每頭向量長 64,沒有遮罩或 dropout;預熱後取 30 次計時的中位數。額外記憶體從 Q,K,VQ,K,V 已備好的時候開始算。

序列長度PyTorch eager分塊內核速度比額外峰值:eager / 分塊
5120.0501 ms0.0781 ms0.64×18.0 / 1.06 MiB
10240.1341 ms0.1044 ms1.28×68.0 / 2.13 MiB
20480.9533 ms0.2007 ms4.75×264.0 / 4.25 MiB

512 個位置時,分塊反而慢;到了 2048,少搬大表才壓過分塊本身的成本。這裡只量前向,反向和整個模型的訓練速度要回到論文的實驗看。

結論

回頭看第一代的設計,最值得學習的地方有兩個。

首先,算術量不是速度的全部。在論文中的 A100 實驗裡,FlashAttention 多做了約 13% 的運算,Attention 的前向與反向總時間卻從 35.1 ms 降到 11.7 ms,只剩三分之一。關鍵在於,HBM 讀寫量從 35.3 GB 降到了 4.4 GB。多算一些,換來少搬很多,非常划算。

其次,中間結果可以「需要時再算」。online softmax 讓不同小格的結果能正確接起來;反向傳播則利用保留下來的輸出與 softmax 統計量,在 SRAM 裡重新計算需要的注意力權重,省掉保存整張權重表的開銷。完整的 Attention 照樣算,但計算順序與資料保存方式換了,速度和記憶體用量就跟著改善。

不過,第一代也還沒把 GPU 的算力充分用起來。softmax 更新時的縮放與正規化,仍有可以省下的非矩陣運算;工作主要沿著 batch 和 head 分配,當兩者數量較少時,GPU 就可能有一部分算力閒著。即使在同一個 thread block 裡,不同 warp 也得透過 shared memory 交換、合併中間結果,付出額外的讀寫與同步成本。

資料已經搬得少了,能不能再把工作分得更好,讓 GPU 少等一點、多算一點?

我們先喝杯咖啡,回來接著看。