← 首頁 Attention

FlashAttention:IO-aware 的精確注意力

Tri Dao 等,2022 · 旁白動畫的文字版,章節和動畫一一對應

FlashAttention 算出的結果和標準注意力完全一樣,它不是近似。它只改變計算的順序:用分塊加上 online softmax,讓 N×N 的中間矩陣不用寫回 HBM。

旁白動畫整理中,之後會放在這裡。

1. 注意力在算什麼

用 A、B、C、D 四個 token 示範。每個 token 分別乘上 WQ、WK、WV,各自得到一個 q、k、v 向量。

這些向量的長度叫做 d。在多頭注意力裡,d 是每個 head 的維度,通常是 64 或 128。

S = QKT / √d

S 是一個 4×4 的分數格子。看 C 那一列:C 的 q 和每個 k 做點積,得到分數 [1, 3, 2, 5]。

P = softmax(S)

每一列各自做 softmax。C 那一列變成 [0.015, 0.112, 0.041, 0.831],權重越大,格子顏色越深。

O = PV

oC = 0.015·vA + 0.112·vB + 0.041·vC + 0.831·vD。

真實模型有 N 個 token(N 就是 context length),S、P 都是 N×N。N = 4096 時,就是 4096 × 4096 ≈ 1,677 萬個數字。如果每個數字用 FP16 表示,佔 2 個 byte,光是一個 head 的 S 就要 32 MB。

C 這一列的數字 [1, 3, 2, 5],就是後面 softmax 和 online softmax 兩節用的同一個例子。

2. 標準注意力

GPU 有兩種記憶體:HBM(顯存)很大但比較慢;SRAM 在運算單元旁邊,很快但很小。標準注意力的運算和搬運順序是:

  1. 從 HBM 讀 Q、K,在 SRAM 算 S = Q·KT(S=分數)。
  2. 把 S 寫回 HBM。
  3. 把 S 讀回來做 softmax,得到 P = softmax(S)(P=softmax 之後的權重)。
  4. 把 P 寫回 HBM。
  5. 讀 P、V,算 O = P·V。
  6. 把 O 寫回 HBM。

每算完一步,結果就得搬回 HBM,下一步再讀回來。S 和 P 這兩個 N×N 的大矩陣佔掉了大部分的讀寫量,瓶頸在搬資料,不在運算。

3. S 的一塊怎麼算

先看形狀。Q 是 N 乘 d:一共有 N 個 token,在這個 head 裡,每個 token 用一個長度為 d 的向量表示。K 的轉置是 d 乘 N。兩個相乘之後,S 就是 N 乘 N。d 只有 64 或 128,所以 S 比 Q 和 K 大得多。

以 N = 4096 為例:Q 是 4096 × d,KT 是 d × 4096,S 是 4096 × 4096。

接著把 Q 的橫條往下移到 Q[128:256, :],直條不動,算出 S[128:256, :128]。這時 Kᵀ[:, :128] 又被讀了一次。

這裡先介紹一下 SM。SM 是 GPU 裡的運算單元,H100 有 132 個。每個 SM 都有自己的 SRAM,而 L2 cache 是所有 SM 共用的,大約 50 MB。

SM 1(自己的 SRAM)  SM 2(自己的 SRAM)  ⋯  SM 132(自己的 SRAM)
                 ↑ 各自從 L2 拿
           L2 cache(所有 SM 共用,約 50 MB)
                 ↑ 只讀一次
                HBM

不同的 Q 塊由不同的 SM 同時計算,讀的是同一份 K。K 從 HBM 只讀一次進 L2,各 SM 再從 L2 拿,不用每個都回 HBM 讀。

4. 最棘手的問題

分塊之後,我們一次只算出 S 的一小塊。但是 softmax 必須等這個 token 對每一個 token 的分數都算出來,才能夠計算。

看 S 的第一列:只有 S₁₁ 算出來了,K₂ 到 K₃₂ 都還沒算。而 softmax 需要 Q₁ 這一整列:

Pj = esj − m / Σk esk − m

一般的 softmax 怎麼算

從 S 拿出一列,就是 1 個 query 對 4 個 key,分數 [1, 3 | 2, 5],每個視窗 2 個 key。value 用 [10, 20, 30, 40] 代替向量。

key0123合計
分數 s1325
es − 50.01830.13530.04981.00001.2034
P(÷ 1.2034)0.0150.1120.0410.8311.000

O = 0.015×10 + 0.112×20 + 0.041×30 + 0.831×40 = 36.88。

減掉最大值是為了避免 es 溢位,結果不變。

要注意的是,softmax 之後乘上 V,只是把權重和 V 做加權加總,本身沒有什麼難度。所以 FlashAttention 會把這一步一起做:每算出一塊權重,就馬上乘上對應的 V,累加起來,不用等整列的 softmax 都算完。

5. Online softmax

分塊時一次只看一個視窗,邊看邊維護三個值:最大值 m、分母 ℓ、輸出累加 o。每看到一個新視窗,先修正舊的,再加上新的:

變數更新公式看完視窗 2 時代入的值
m(最大值)mnew = max(mold, 這個視窗的最大分數)5
c(修正係數)c = emold − mnewe3−5 ≈ 0.135
ℓ(分母)ℓnew = c · ℓold + Σ es − mnew0.154 + e2−5 + e5−5 = 1.203
o(輸出累加)onew = c · oold + Σ es − mnew · v2.89 + e2−5·30 + e5−5·40 = 44.38

全部看完:輸出 = o ÷ ℓ = 44.38 ÷ 1.203 = 36.88,跟一次看完整列的答案一樣。修正之後,視窗 1 的長條高度就等於上一節的 es − 5。

6. 分塊=不重疊的滑動視窗

把 S 畫成一張大圖,用 128×128 的視窗不重疊地滑過去,每個位置都會被滑到一次。每一列是一塊 Q:Q₁=token 0–127、Q₂=token 128–255、⋯、Q₃₂=token 3968–4095;每一欄是 K₁、K₂、⋯、K₃₂。

視窗沿著第 1 列滑動,每格在 SRAM 裡算完就丟掉,結果累加到 O₁。每個視窗在 SRAM 裡做的事:

步驟計算意義
①Sij = Qi·KjT / √d分數
②mnew = max(m, rowmax(Sij))更新最大值
③Pij = exp(Sij − mnew)softmax 分子
④ℓ = c·ℓ + rowsum(Pij)分母
⑤Oi = c·Oi + Pij·Vj加權 V
⑥Oi = Oi / ℓ → 寫回 HBM整列做完才做一次

其中 c = em − mnew 是修正係數。整列滑完後,O₁ 寫回 HBM 一次,其他列也一樣。

跟一般滑動視窗唯一的差別

同一列的視窗屬於同一塊 Q₁,結果要合併成同一個 O₁,靠的就是 online softmax。

7. 搬運量比較

條件:N = 4096 個 token(S 是 4096 × 4096)、d = 128、每塊 128 個 token、FP16、只算一個 head。

另外比較佔用的 HBM 空間,這跟搬運量是兩回事:標準做法要存 S 和 P(64 MB),FlashAttention 是 0。

8. 推論的兩個階段

LLM 生成文字分兩個階段:

PrefillDecode
Q 的長度4096 個 token1 個 token
S 的大小4096 × 40961 × 4096
瓶頸N×N 的中間結果每一步都要讀完整份 KV cache

9. Prefill:每一列交給一個 SM

沿用第 3 節的 S 方陣。每一列 Q 塊交給一個 SM(SM 1、SM 2、⋯、SM 32),各自從左到右掃過 K₁ 到 K₃₂,所有列同時進行。

一個 head 有 32 列,32 個 head 就是 32 × 32 = 1024 份工作,132 個 SM 全部忙得過來。

10. Decode:S 縮成一條細線

Decode 時 Q 從 4096 列縮成只剩 1 列,也就是新的那個 token,S 跟著壓扁成一條 1 × 4096 的細長條。

這一整條只能交給一個 SM,它要從頭到尾讀完 4096 個 K、V。32 個 head 只有 32 份工作,132 個 SM 裡只有 32 個在做事,100 個閒著。

11. Flash-Decoding:改切 KV

Q 切不動,就改切 KV:把 1 × 4096 這條切成 4 段,4 個 SM 同時計算。32 × 4 = 128 份工作,132 個 SM 裡有 128 個亮起來。

每段各自算出 (m, ℓ, o),最後用第 5 節的修正係數合併:

m = max(ma, mb)
ℓ = ema − m·ℓa + emb − m·ℓb

o 的合併方式和 ℓ 一樣。用同一個例子:一段負責 [1, 3],另一段負責 [2, 5],兩段同時算,最後合併出來還是 36.88。

online softmax 依序算是 FlashAttention,平行算再合併就是 Flash-Decoding,兩者用的是同一個公式。

時間方法重點
2022FlashAttention-1分塊加 online softmax,不把 N×N 寫回 HBM
2023 年 7 月FlashAttention-2改變迴圈順序(外層跑 Q),沿著序列長度平行化,讓 SM 用得更滿
2023 年 10 月Flash-Decodingdecode 時 Q 只有 1 個 token,改成切 KV 來平行化
2024FlashAttention-3針對 H100 的新硬體特性重寫

12. 總結

  1. 不把 N 乘 N 的 S 和 P 存下來,額外的記憶體從 O(N²) 降到 O(N)。
  2. HBM 的讀寫大幅減少,實際速度快了好幾倍。
  3. 它切的是計算的順序,不是每個 token 看的範圍。
  4. 它是精確計算,不是近似,答案和標準注意力完全一樣。
  5. 關鍵就是兩件事:分塊,也就是不重疊的視窗,再加上 online softmax。

參考資料