返回論文筆記資料庫
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,成功解決了注意力矩陣反覆進出 HBM 的問題。不僅大幅降低記憶體用量,運算速度也跟著提升了不少。

但是打開 GPU 的工作清單一看,發現不太對勁。

怎麼......

這傢伙這麼閒啊?

定義問題

大家都知道 GPU 裡有兩層分工。

GPU 裡有許多可以同時工作的 Streaming Multiprocessor(SM)。程式把執行緒組成 thread block,交給 SM 執行;block 內再分成 warp,每組通常有 32 條執行緒。

簡單來說,SM 是工廠,thread block 是工作訂單,warp 則是實際幹活的小組。

第一代 FlashAttention 主要依照 batch size × attention heads 分配工作。以論文中的 A100 為例,GPU 有 108 個 SM,假設 batch size = 1、attention heads = 8,就只有 8 個 thread blocks。

108 間工廠,只發出 8 張訂單。

剩下的 100 間呢?就先躺著睡一會兒吧,還能幹嘛?

序列越長,還只會讓這 8 張訂單越來越厚,卻不會增加工廠的開工數量。作者在論文指出,第一代的運算吞吐量只有理論峰值的 25–40%,距離 GPU 的真正實力還差得遠。

不僅如此。

首先,GPU 的 Tensor Cores 擅長矩陣乘法,softmax 卻需要不少非矩陣乘法(non-matmul)運算。這些運算看似簡單,執行效率卻遠不如矩陣乘法,反而拖慢整體速度。其次,第一代在 block 內讓不同 warp 分別處理 K、V 的部分資料,算完又得透過 shared memory 交換結果、同步與合併。

整理一下目前的問題:

SM 之間,工作分得太少;warp 之間,工作又分得不好。

那如果我們就把工作切得更細,讓更多 SM 同時執行呢?

偏偏 attention 沒這麼好拆。softmax 的每一列需要共同的正規化資訊;反向傳播時,不同區塊又可能需要累加到同一份梯度。切得太大,GPU 閒著;切得太碎,大家忙著互相等候。

究竟該怎麼切,才能讓所有人都有事做,卻又不用整天開會?

這就是 FlashAttention-2 要解決的問題。

解決問題

作者把前向工作改從兩個地方切,不同 thread block 各管一組 query 列;同一個 block 裡,不同 warp 也各管自己的 query 列。這樣切完,還得讓每列的 softmax 能獨立算到底。

沿著列切工作

先認一下表上的三個字母,QQ 是「想找什麼」,KK 是拿來比對的線索,VV 是最後要取出的內容。把注意力分數想成一張表,橫列是 QQ,直欄是 KK,每一格是兩者配對的分數。

softmax 沿著橫列計算,所以同一列的分數要共用分母;不同橫列卻各有自己的分母。作者因此把整組橫列交給一個 thread block,讓它依序讀取需要的 K,VK,V 小塊,完成這組列的輸出。

來看原論文的 Figure 2。左圖一種顏色是一組 query 列,也就是一個 worker(thread block)的工作;白色格子因為因果遮罩而不用計算。生成文字時,前面的字不能看到未來的字,於是整張表的右上角空了出來。

原論文 Figure 2 局部,arXiv:2307.08691v1 PDF 第 8 頁。

第一組 worker 算第一組列,第二組算第二組列;兩組都可能讀到同一塊 K,VK,V,但不用交換 softmax 的中間結果。回到前面 1 個 batch、8 個 head 的例子,每個 head 是一份獨立的注意力計算。假設每份的 query 列再切成 16 組,就能從 8 張工作訂單變成 8×16=1288\times16=128 張。這只是派工示意,實際切幾組要看區塊大小;重點是序列變長時,工作組數終於也能增加。

右圖為什麼又改成直欄?因為反向傳播要算 dQ,dK,dVdQ,dK,dV,也就是傳回 Q,K,VQ,K,V 的梯度。一個 K,VK,V 小塊會受到許多 query 列影響;讓一個 worker 負責一欄,就能把這一欄的 dK,dVdK,dV 在自己手上累積完。

dQdQ 則會從不同欄收到貢獻,這些 worker 必須用 atomic add 把數值加回去,確保同時寫入時不會互相覆蓋。前向各管自己的輸出列,反向各管自己的 K,VK,V 梯度。

除法留到最後

一個 worker 接下 query 列後,仍要分批讀完 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 自製:四個分數分兩塊處理,只有最後一步計算 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' 中加進新分數的指數,在 U′U' 中加進對應 VjV_j 的加權和。

一般情況的 VjV_j 是一組向量,所以 UU 也是向量;圖上用單一數值,方便我們手算。每組 query 列都能這樣維護自己的 m,ℓ,Um,\ell,U,讀完才輸出 O=U/ℓO=U/\ell。

反向傳播要重算注意力權重,作者只替每列保存一個正規化數字 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。

少除幾次,對 GPU 有什麼幫助?

作者在論文中列出 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,等大家算完,再讀出來合併;論文稱作 split-K。

右邊把方向反過來,K,VK,V 讓各組 warp 取用,QQ 切成四份。第一組 warp 產生自己的輸出列,第二組產生下一組。既然輸出列各有主人,前向就不必為了拼同一列而開那場 shared memory 協調會。反向仍有梯度依賴,需要部分同步。

到這裡,兩層分工接起來了。一個 head 的不同 query 列派往更多 block;進了 block,再把列分給不同 warp。每列內部的 softmax 則只在最後相除。

討論

先看注意力本身

原論文的 Figure 4(a) 比較 A100 80GB SXM4 上的注意力前向加反向,設定是沒有因果遮罩、每個 head 寬度為 64。橫軸是序列長度;縱軸 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 時 batch 為 1。

在這張圖的 32 個 head 設定下,第一代到了 16k 只有 1×32=321\times32=32 組按 batch 與 head 派出的工作,面對 A100 的 108 個 SM。沿 query 列再分 block,正好補上這種情況缺少的平行工作。

再看整場訓練

注意力這一層快了,整個模型呢?原論文 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 恰好有 72% 在上班。表格的 TFLOPs/s 是按模型運算量公式與耗時換算的;該公式沿用當時文獻慣例,計算因果注意力時沒有扣掉遮罩略去的約半張分數表,它能用來比較表中同條件的訓練速度。

結論

第一代 FlashAttention 解決了資料搬太多的問題,第二代則開始研究工作怎麼分配。

它沿著 query 的序列維度派出更多 thread blocks,讓更多 SM 同時開工;重新安排 warp 的工作,減少彼此交換資料的麻煩;再調整 online softmax 的計算順序,省下部分非矩陣乘法運算。

這套設計後來也走進 PyTorch SDPA 與 Hugging Face 的加速選項。不過,密集 attention 的計算量仍隨序列長度呈平方成長,而且 A100 上的最佳分工,到了 H100、B200 未必還是最佳解。

最後,所有人都在忙,就代表整條產線沒有浪費時間嗎?

下一篇繼續,換 H100 上場。