FlashAttention:IO-aware 的精確注意力
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 是一個 4×4 的分數格子。看 C 那一列:C 的 q 和每個 k 做點積,得到分數 [1, 3, 2, 5]。
每一列各自做 softmax。C 那一列變成 [0.015, 0.112, 0.041, 0.831],權重越大,格子顏色越深。
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 在運算單元旁邊,很快但很小。標準注意力的運算和搬運順序是:
- 從 HBM 讀 Q、K,在 SRAM 算 S = Q·KT(S=分數)。
- 把 S 寫回 HBM。
- 把 S 讀回來做 softmax,得到 P = softmax(S)(P=softmax 之後的權重)。
- 把 P 寫回 HBM。
- 讀 P、V,算 O = P·V。
- 把 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, :],從 KT 取出直條Kᵀ[:, :128],兩者相乘,得到 S 左上角的一塊S[:128, :128]。 - 這一格是 128 個 query 乘 128 個 key 的小矩陣,d 這一維完整保留。
- N = 4096 時,每一邊會切成 32 塊,S 就是 32 × 32 格。
接著把 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₁ 這一整列:
- m=整列的最大值,要看完整列才知道。
- Σ=整列的總和(分母),也要看完整列。
一般的 softmax 怎麼算
從 S 拿出一列,就是 1 個 query 對 4 個 key,分數 [1, 3 | 2, 5],每個視窗 2 個 key。value 用 [10, 20, 30, 40] 代替向量。
| key | 0 | 1 | 2 | 3 | 合計 |
|---|---|---|---|---|---|
| 分數 s | 1 | 3 | 2 | 5 | |
| es − 5 | 0.0183 | 0.1353 | 0.0498 | 1.0000 | 1.2034 |
| P(÷ 1.2034) | 0.015 | 0.112 | 0.041 | 0.831 | 1.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 − mnew | e3−5 ≈ 0.135 |
| ℓ(分母) | ℓnew = c · ℓold + Σ es − mnew | 0.154 + e2−5 + e5−5 = 1.203 |
| o(輸出累加) | onew = c · oold + Σ es − mnew · v | 2.89 + e2−5·30 + e5−5·40 = 44.38 |
- 視窗 1
[1, 3]:目前看到的最大值是 3,我們把它記成 m。ℓ = e1−3 + e3−3 = 1.135,o = e−2·10 + e0·20 = 21.35。 - 視窗 2
[2, 5]:發現新的最大值 5。舊的權重要乘上修正係數 e3−5 ≈ 0.135,先得到 0.135 × 1.135 = 0.154,再加上第二個視窗的貢獻。
全部看完:輸出 = 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。
- 標準注意力:讀 Q、K,寫 S 32 MB、讀 S 32 MB,寫 P 32 MB、讀 P 32 MB,讀 V、寫 O。S、P 那四段佔了大部分。
- FlashAttention 帳面上:Q 和 O 各 1 MB,中間是「讀 K、V × 32 次」,每一次代表一塊 Qᵢ 重讀一次 K、V,合計 66 MB。
- 考慮 L2 cache:32 塊 Qᵢ 在不同的 SM 上同時跑,讀的是同一份 K、V,第一次從 HBM 讀進 L2,之後都從 L2 拿,約 4 MB。這是理想情況的估算。
另外比較佔用的 HBM 空間,這跟搬運量是兩回事:標準做法要存 S 和 P(64 MB),FlashAttention 是 0。
8. 推論的兩個階段
LLM 生成文字分兩個階段:
- Prefill:整段 prompt(例如 4096 個 token)一次送進模型,同時把 K、V 存進 KV cache。S 是 4096 × 4096,FlashAttention 主要加速的就是這裡。
- Decode:之後每一步只生成 1 個新 token。它只有 1 個 q,要和 KV cache 裡全部的 K 做注意力,所以 S 只有 1 × 4096。
| Prefill | Decode | |
|---|---|---|
| Q 的長度 | 4096 個 token | 1 個 token |
| S 的大小 | 4096 × 4096 | 1 × 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 節的修正係數合併:
o 的合併方式和 ℓ 一樣。用同一個例子:一段負責 [1, 3],另一段負責 [2, 5],兩段同時算,最後合併出來還是 36.88。
online softmax 依序算是 FlashAttention,平行算再合併就是 Flash-Decoding,兩者用的是同一個公式。
| 時間 | 方法 | 重點 |
|---|---|---|
| 2022 | FlashAttention-1 | 分塊加 online softmax,不把 N×N 寫回 HBM |
| 2023 年 7 月 | FlashAttention-2 | 改變迴圈順序(外層跑 Q),沿著序列長度平行化,讓 SM 用得更滿 |
| 2023 年 10 月 | Flash-Decoding | decode 時 Q 只有 1 個 token,改成切 KV 來平行化 |
| 2024 | FlashAttention-3 | 針對 H100 的新硬體特性重寫 |
12. 總結
- 不把 N 乘 N 的 S 和 P 存下來,額外的記憶體從 O(N²) 降到 O(N)。
- HBM 的讀寫大幅減少,實際速度快了好幾倍。
- 它切的是計算的順序,不是每個 token 看的範圍。
- 它是精確計算,不是近似,答案和標準注意力完全一樣。
- 關鍵就是兩件事:分塊,也就是不重疊的視窗,再加上 online softmax。
參考資料
- FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness(Dao 等,2022)
- FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning(Dao,2023)
- Flash-Decoding for long-context inference(Stanford CRFM,2023)
- FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precision(Shah 等,2024)