跳转到正文
Retep's
返回

[Book Club] FlashAttention:具备 IO 感知的快速、省内存精确注意力

编辑文章

本文由英文原文翻译。代码、公式与技术名称保留原文。

论文:FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness,Dao 等,2022。

论文的核心观点很简单:

Attention 慢,不仅因为浮点运算多,也因为在 GPU 各级内存之间搬运了太多数据。

FlashAttention 保持精确 Softmax attention 的数学计算,但改变计算顺序:不在 HBM 中物化完整注意力矩阵,而是逐 tile 计算,将临时值保留在片上。

标准注意力

对于单个注意力头:

S=QKTS = QK^T P=softmax(S)P = \text{softmax}(S) O=PVO = PV

其中:

问题在于中间矩阵:

S,P∈RN×NS, P \in \mathbb{R}^{N \times N}

长序列下,N×NN \times N 非常大。标准实现将 SS 写到 HBM,为 Softmax 读回,再将 PP 写到 HBM,最后读回 PP 与 VV 相乘。

因此 GPU 花了大量时间搬运中间矩阵。

内存层次

论文关注三个层次:

关键差距在 SRAM 和 HBM 之间。SRAM 很快,但容不下完整的 N×NN \times N 注意力矩阵;HBM 放得下,但读写昂贵。

所以目标是:

尽量减少 HBM 读写。

这就是论文所谓的 IO 感知:算法设计不仅考虑浮点运算,也围绕数据搬运展开。

为什么精确注意力可以流式计算?

起初,Softmax 看起来需要 SS 的完整一行:

softmax(xi)=exi∑jexj\text{softmax}(x_i) = \frac{e^{x_i}}{\sum_j e^{x_j}}

为保证数值稳定,通常减去行最大值:

softmax(xi)=exi−m∑jexj−m\text{softmax}(x_i) = \frac{e^{x_i - m}}{\sum_j e^{x_j - m}}

其中:

m=max⁡jxjm = \max_j x_j

似乎必须看过全部分数才能计算最终输出。FlashAttention 使用在线 Softmax,避免保存每个分数。

每行维护两个运行值:

新分数块到来时,计算:

mnew=max⁡(mold,mblock)m_{new} = \max(m_{old}, m_{block})

旧分母以 moldm_{old} 缩放,新分母必须采用 mnewm_{new},因此先重新缩放旧值:

ℓnew=emold−mnewℓold+∑x∈blockex−mnew\ell_{new} = e^{m_{old} - m_{new}}\ell_{old} + \sum_{x \in block} e^{x - m_{new}}

这是关键修正项。新块出现更大最大值时,旧部分和相应缩小。

输出累加器同样需要修正:

Onew=emold−mnewOold+∑xj∈blockexj−mnewVjO_{new} = e^{m_{old} - m_{new}}O_{old} + \sum_{x_j \in block} e^{x_j - m_{new}}V_j

最后:

O=OaccℓO = \frac{O_{acc}}{\ell}

这样就无需保存完整的分数行或概率行。

FlashAttention 前向传播

标准实现执行:

Q, K, V are in HBM

1. compute S = QK^T
2. write S to HBM
3. read S from HBM
4. compute P = softmax(S)
5. write P to HBM
6. read P from HBM
7. compute O = PV
8. write O to HBM

FlashAttention 改为分块执行:

for each K,V tile:
    load K tile into SRAM
    load V tile into SRAM

    for each Q tile:
        load Q tile into SRAM
        load current output state for this Q tile

        compute score tile QK^T
        update online softmax max m
        update online softmax denominator l
        update output accumulator O

        write updated output state back to HBM

分数 tile 是临时的,只需在片上存活到在线 Softmax 状态更新完毕。

论文算法 1 在两次 tile 更新之间,为每行保存三项:

它不保存:

这就是主要的内存节省来源。

简单示例

假设一行分数被分为两块:

x=[1,2,3,4]x = [1, 2, 3, 4]

第 1 块:

x(1)=[1,2]x^{(1)} = [1, 2]

则:

m1=2m_1 = 2 ℓ1=e1−2+e2−2\ell_1 = e^{1 - 2} + e^{2 - 2}

第 2 块:

x(2)=[3,4]x^{(2)} = [3, 4]

新的最大值为:

m2=4m_2 = 4

旧分母以最大值 2 为基准,因此需要重新缩放:

ℓ2=e2−4ℓ1+e3−4+e4−4\ell_2 = e^{2 - 4}\ell_1 + e^{3 - 4} + e^{4 - 4}

这等于四个分数一起计算时的稳定 Softmax 分母:

e1−4+e2−4+e3−4+e4−4e^{1 - 4} + e^{2 - 4} + e^{3 - 4} + e^{4 - 4}

所以在线 Softmax 与普通 Softmax 结果相同,却无需保留全部分数。

复杂度分析

浮点运算量

FlashAttention 与标准精确 attention 的主要数学运算相同:

O(N2d)O(N^2d)

论文并不声称改善稠密 attention 浮点运算量的渐进复杂度,改进的是数据搬运。

主要矩阵乘法仍然为:

此外,还需对 N2N^2 个分数执行 Softmax。只要 dd 不特别小,主导项仍是 O(N2d)O(N^2d)。

HBM 访问量

论文给出的标准 attention 访问量为:

O(Nd+N2)O(Nd + N^2)

次 HBM 访问。

NdNd 项来自读写 QQ、KK、VV、OO;N2N^2 项来自物化注意力矩阵。

FlashAttention 将 HBM 访问量降为:

O(N2d2M)O\left(\frac{N^2d^2}{M}\right)

其中 MM 是 SRAM 大小。

直观理解:

关键比较是:

standard attention:
    pays for the full N x N matrix in HBM

FlashAttention:
    pays for tiled Q, K, V, O movement
    avoids storing S and P

论文还证明,在如下 SRAM 大小范围内,IO 复杂度是最优的:

d≤M≤Ndd \le M \le Nd

因此,在该范围和论文模型下,算法不仅实践中更快,其 HBM 访问量在渐进意义上也是最优的。

反向传播

训练还需要反向传播。朴素实现可能保存前向的完整注意力矩阵 PP 供反向复用,FlashAttention 也避免了这一点。

前向只保存:

反向逐 tile 重算所需的 QKTQK^T 分数和 Softmax 概率,用额外计算换取更低内存开销。现代 GPU 上,这通常很划算,因为计算往往比 HBM 搬运便宜。为简化讨论,本文不展开反向数学推导。

块稀疏注意力

论文将思路扩展到块稀疏 attention。稠密 attention 中,每个 query token 都关注每个 key token,对应完整矩阵:

A∈RN×NA \in \mathbb{R}^{N \times N}

块稀疏 attention 将矩阵划分成块,部分激活、部分跳过。设块大小为 BB,则注意力矩阵包含:

NB×NB\frac{N}{B} \times \frac{N}{B}

个块。

定义块 mask:

Mij={1if query block i attends to key block j0otherwise\mathcal{M}_{ij} = \begin{cases} 1 & \text{if query block } i \text{ attends to key block } j \\ 0 & \text{otherwise} \end{cases}

如果 Mij=0\mathcal{M}_{ij} = 0,整个分数块都被忽略。对于相应 QQ tile,kernel 无需加载该 K,VK,V tile,也无需计算其分数。

四个块的示例:

dense mask:

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

causal block mask:

1 0 0 0
1 1 0 0
1 1 1 0
1 1 1 1

local block mask:

1 1 0 0
1 1 1 0
0 1 1 1
0 0 1 1

从块粒度看,因果 attention 会屏蔽未来块,因此具有块稀疏结构;局部 attention 只关注邻近块,也具有块稀疏结构。

简化伪代码如下:

def block_sparse_flash_attention(Q, K, V, block_mask, B):
    """
    Q, K, V: [N, d]
    block_mask: [N / B, N / B]
        block_mask[i][j] = 1 means query block i attends to key/value block j
    B: block size along sequence length
    """
    N, d = Q.shape
    num_blocks = N // B
    O = zeros_like(Q)

    for q_block_id in range(num_blocks):
        q_start = q_block_id * B
        q_end = q_start + B
        Q_block = Q[q_start:q_end]

        # Online softmax state for this query block.
        running_max = full([B], -inf)
        running_sum = zeros([B])
        output_acc = zeros([B, d])

        for kv_block_id in range(num_blocks):
            if block_mask[q_block_id][kv_block_id] == 0:
                continue

            kv_start = kv_block_id * B
            kv_end = kv_start + B
            K_block = K[kv_start:kv_end]
            V_block = V[kv_start:kv_end]

            scores = Q_block @ K_block.T

            block_max = max(scores, axis=1)
            new_max = maximum(running_max, block_max)

            old_scale = exp(running_max - new_max)
            weights = exp(scores - new_max[:, None])

            running_sum = running_sum * old_scale + sum(weights, axis=1)
            output_acc = output_acc * old_scale[:, None] + weights @ V_block
            running_max = new_max

        O[q_start:q_end] = output_acc / running_sum[:, None]

    return O

关键一行为:

if block_mask[q_block_id][kv_block_id] == 0:
    continue

continue 跳过整个 attention tile。其余部分仍与 FlashAttention 相同:计算分数 tile,更新在线 Softmax 状态,再丢弃分数 tile。

若 ss 表示非零块比例,论文给出的块稀疏 FlashAttention HBM 访问量为:

O(Nd+N2d2Ms)O\left(Nd + \frac{N^2d^2}{M}s\right)

s=1s = 1 时退化为稠密 FlashAttention;s<1s < 1 时加载和计算的 tile 更少。

带来两个收益:

代价是,除非稀疏 mask 恰好匹配模型需要的注意力模式,否则块稀疏 attention 属于近似计算。


编辑文章
分享文章:

上一篇
[TIL] TileLang 逐元素操作与向量化
下一篇
[TIL] 多头注意力