跳转到正文
Retep's
返回

[TIL] 学习笔记:Softmax Attention

编辑文章

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

Softmax Attention

今天我写了一个 Triton attention kernel:

out = softmax(Q @ K.T / sqrt(d)) @ V

看起来就是两次矩阵乘法,中间夹着 Softmax。真正棘手的是 Softmax。

对于一行 query,attention 的计算为:

scores = Q[row] @ K.T
weights = softmax(scores)
out[row] = weights @ V

Softmax 会形成全行依赖。即使只计算一个输出权重,也需要整行的最大值和分母:

softmax(x_i) = exp(x_i - max(x)) / sum_j exp(x_j - max(x))

因此不能看完一个 key tile、归一化后就继续前进,那样得到的只是局部 Softmax,而不是所有 key 上的真实 Softmax。每行 query 都必须遍历所有 key,输出才能最终确定。

one query row

K block 0      K block 1      K block 2      ...      K block n
---------      ---------      ---------               ---------
 scores         scores         scores                  scores
    \              |              |                       /
     \             |              |                      /
      +------------+--------------+----------------------+
                   |
          one row-wide softmax
                   |
              final output row

这个 kernel 通过流式遍历 K 和 V 块处理这一问题,不保存完整的 M x N 分数矩阵,而是为每行 query 维护运行中的最大值、指数和以及输出累加器。

Program 布局

row_pid = tl.program_id(0)
col_pid = tl.program_id(1)

m_indexes = row_pid * M_BLOCK + tl.arange(0, M_BLOCK)
v_indexes = col_pid * d_BLOCK + tl.arange(0, d_BLOCK)

启动 grid 为:

grid = (triton.cdiv(M, M_BLOCK), triton.cdiv(d, d_BLOCK))

每个 Triton program 负责:

本版本中:

M_BLOCK = 16
N_BLOCK = 64
d_BLOCK = 128

也就是每个 program 计算最终输出的一个 [16, 128] tile。

grid 第一维在 query 行之间并行,第二维在输出特征列之间并行。各 program 写入不同的输出 tile,因此可以独立执行。

output O: [M, d]

                 d dimension
          col_pid=0        col_pid=1        col_pid=2
        +--------------+--------------+--------------+
row 0   | program      | program      | program      |
block   | row_pid=0    | row_pid=0    | row_pid=0    |
        +--------------+--------------+--------------+
row 1   | program      | program      | program      |
block   | row_pid=1    | row_pid=1    | row_pid=1    |
        +--------------+--------------+--------------+
row 2   | program      | program      | program      |
block   | row_pid=2    | row_pid=2    | row_pid=2    |
        +--------------+--------------+--------------+

Each box writes one [M_BLOCK, d_BLOCK] output tile.

需要维护的状态

running_sum = tl.zeros([M_BLOCK], dtype=tl.float32)
running_max = tl.full([M_BLOCK], float("-inf"), dtype=tl.float32)
out_acc = tl.zeros([M_BLOCK, d_BLOCK], dtype=tl.float32)
scale = 1 / tl.sqrt(d + 0.0)

对于块中的每行 query,维护:

处理完某个 key 前缀后,不变量为:

running_sum[i] = sum_j exp(score[i, j] - running_max[i])
out_acc[i, :] = sum_j exp(score[i, j] - running_max[i]) * V[j, :]

这就是运行中指数和的用途。它并没有省去每个 QK 分数的计算,而是减少扫描中的归一化工作和访存量。无需保存全部分数、单独启动 Softmax 再重新读取;分母在逐块扫描时增量构建。

after block 0:
  running_max = max(scores_0)
  running_sum = sum(exp(scores_0 - running_max))

after block 1:
  running_max = max(old_running_max, max(scores_1))
  running_sum = rescaled_old_sum + sum(exp(scores_1 - running_max))

after block 2:
  same update again

计算一块分数

for nn in tl.range(0, tl.cdiv(N, N_BLOCK)):
    n_indexes = nn * N_BLOCK + tl.arange(0, N_BLOCK)
    n_mask = n_indexes < N
    acc = tl.zeros((M_BLOCK, N_BLOCK), dtype=tl.float32)

外层循环遍历所有 key。单个 program 内,这个循环不能直接并行,因为一行的 Softmax 依赖全部 key 块。我们逐块处理并更新运行统计量。

在每个 key 块内计算:

acc = Q_block @ K_block.T

点积本身又沿特征维度分块:

for dd in tl.range(0, tl.cdiv(d, d_BLOCK)):
    d_indexes = dd * d_BLOCK + tl.arange(0, d_BLOCK)

    cur_q = tl.load(Q + M_offsets, mask=M_mask, other=0.0)
    cur_k = tl.load(K + K_offsets, mask=K_mask, other=0.0)

    acc += tl.dot(cur_q, tl.trans(cur_k)) * scale

由此得到分数 tile:

acc.shape == [M_BLOCK, N_BLOCK]

tl.dot 是并行计算的部分。program 中多个 lane 协作完成分块矩阵乘法,Triton 将其降级为高效 GPU 指令。在 NVIDIA GPU 上,合适的形状和数据类型可以使用 tensor core 矩阵乘法指令。看起来像 Python 的块操作,实际上由多个线程协同执行。

这些循环会展开吗?

通常不会自动完全展开。

M_BLOCK、N_BLOCK、d_BLOCK 都是 tl.constexpr,因此 program 内部的形状是编译期常量,有利于生成固定大小的向量加载、归约和点积。

但循环边界使用运行时值:

tl.cdiv(N, N_BLOCK)
tl.cdiv(d, d_BLOCK)

N 和 d 是普通运行时参数,Triton 无法对所有可能输入完全展开循环,所以生成的程序中仍有实际循环。如果把它们改为编译期常量,或者以其他方式让边界在编译期已知,编译器就有更大的展开空间。

需要区分:

Softmax 之前的掩码

acc = tl.where(m_mask[:, None] & n_mask[None, :], acc, float("-inf"))

矩阵乘法的补齐值可以是零,但 Softmax 中补齐的分数必须为 -inf。

如果无效 key 的分数保留为 0.0,它可能改变行最大值,或向分母加入 exp(0),从而改变概率分布。使用 -inf 时,补齐分数的贡献为:

exp(-inf) = 0

因此不会影响结果。

在线 Softmax

计算一块分数后,将其合并到整行统计量:

current_max = tl.max(acc, axis=-1)
new_running_max = tl.maximum(current_max, running_max)
alpha = tl.exp(running_max - new_running_max)

weights = tl.exp(acc - new_running_max[:, None])
incre = tl.sum(weights, axis=1)

running_sum = tl.fma(running_sum, alpha, incre)
running_max = new_running_max

这是流式形式的 log-sum-exp 技巧。

设原最大值为 m_old,加入新块后变成 m_new。旧分母以 m_old 为基准:

sum_old = sum(exp(score_old - m_old))

为了和新块合并,先把它变换到新坐标系:

sum_old * exp(m_old - m_new)

这就是 alpha。

然后加上新块的贡献:

sum(exp(score_new - m_new))

合并后的分母为:

running_sum =
    old_sum * exp(old_max - new_max)
    + new_sum
old state, measured at old_max
  old_sum
  old_out_acc
        |
        | multiply by alpha = exp(old_max - new_max)
        v
old state, measured at new_max
  old_sum * alpha
  old_out_acc * alpha
        |
        | add current block contribution
        v
new state
  running_sum
  out_acc

因此 kernel 可以沿 N 流式执行。Softmax 仍需要整行信息,但无需把整行都保存在内存中。

在同一次遍历中乘以 V

kernel 还会立刻将当前未归一化权重应用到 V:

cur_v = tl.load(V + v_offsets, mask=V_mask)
weighted_v = tl.dot(weights, cur_v)
out_acc = tl.fma(out_acc, alpha[:, None], weighted_v)

思路与更新分母相同。

如果行最大值发生变化,旧输出累加器也必须重新缩放:

old_out_acc * exp(old_max - new_max)

然后加上新 key 块的贡献:

weights @ V_block

这样 running_sum 和 out_acc 始终处于相同坐标系,最后只需归一化一次:

out_acc /= running_sum[:, None]

哪些部分并行,哪些部分串行?

可以从几个层次来看。

在整个 grid 上,各 program 并行:

单个 program 内,块操作并行执行:

单个 program 内,key 扫描是串行的:

for nn in tl.range(0, tl.cdiv(N, N_BLOCK)):

循环必须按顺序访问 key 块,因为每轮都会更新 running_max、running_sum 和 out_acc。

底层中,一个 Triton program 大致映射到类似 CUDA 线程块的执行资源。GPU 启动多个 program,由调度器分配到 SM。每个 program 通过若干 warp 执行;某个 warp 等待内存时,SM 可以执行其他就绪 warp,从而隐藏延迟。

这里的串行,指一个输出 tile 对 key 块存在循环携带依赖。GPU 仍可以同时运行许多其他输出 tile。

GPU view

SM 0:  program A  -> scans K blocks 0, 1, 2, ...
SM 1:  program B  -> scans K blocks 0, 1, 2, ...
SM 2:  program C  -> scans K blocks 0, 1, 2, ...
SM 3:  program D  -> scans K blocks 0, 1, 2, ...

Inside each program, the scan over K blocks is ordered.
Across programs, many output tiles run at the same time.

为什么融合,而不是 GEMM + Softmax + GEMM?

未融合版本的概念很清楚:

S = Q @ K.T
P = softmax(S)
O = P @ V

使用优化 kernel 后,两次 GEMM 都可以很快。问题在于物化的 attention 矩阵 S 或 P。

对于以下形状:

Q: [M, d]
K: [N, d]
V: [N, d]
S/P: [M, N]
O: [M, d]

独立 kernel 路径需要通过 HBM 搬运大量中间数据:

  1. GEMM 读取 Q、K,写出包含 M * N 个元素的 S。
  2. Softmax 读取 S、写出 P,并且往往要为最大值、求和和归一化多次扫描每行。
  3. 第二次 GEMM 读取 P、V,写出 O。
unfused path

Q, K -> GEMM -> S in HBM -> softmax -> P in HBM -> GEMM with V -> O
                  ^                         ^
                  |                         |
          huge intermediate          huge intermediate

fused path

Q block, K block -> score tile -> online softmax -> apply V block -> O tile
                       |
                       +-- stays temporary, then gets discarded

即使 GEMM 已优化,M x N 矩阵仍然很大。例如:

M = 4096
N = 4096
d = 128

则 S 包含:

4096 * 4096 = 16,777,216 elements

使用 fp16 时,一个矩阵约为 32 MB。写分数、读分数、写概率、读概率,已经带来约 128 MB 中间流量,还没算 Q、K、V、O 本身。Softmax 如果多次扫描 S,流量还会继续增加。

步骤未融合时的 S/P 中间流量融合时的 S/P 中间流量
写出分数 SM * N 个元素0 次全局写入
为 Softmax 读取分数M * N 个元素0 次全局读取
写出概率 PM * N 个元素0 次全局写入
为 P @ V 读取概率M * N 个元素0 次全局读取

对于 4096 x 4096 的 fp16 矩阵,每次完整扫描约为 32 MB,四次就是约 128 MB 的额外 HBM 流量。

融合 kernel 不把 S 或 P 写入全局内存,而是计算一个分数 tile,更新在线 Softmax 状态,将权重应用到 V,然后丢弃该分数 tile。

从运行成本看,瓶颈发生了变化:

这对 attention 尤其重要,因为 Softmax 附近往往受内存带宽限制。分数矩阵太大,无法留在片上,物化会引入 HBM 流量和 kernel 启动边界。融合则让短期使用的临时分数 tile 留在寄存器或片上内存中。

当前实现还有一个限制:grid 使用 col_pid 按输出列划分,所以当 d > d_BLOCK 时,不同列 program 会为不同的 V 列 tile 重复计算相同的 QK.T 分数。d <= 128 时只有一个输出列 tile,没有这个问题;更大的 d 则会浪费计算。进一步优化时需要更仔细地选择 tile,或改用其他策略避免过多重复计算。

主要收益已经很明确:融合 kernel 用流式在线 Softmax 取代大型物化中间矩阵,这正是 FlashAttention 类 kernel 的核心思想。

完整代码

import torch
import triton
import triton.language as tl


@triton.jit
def softmax_attention(
    Q,
    K,
    V,
    M,
    N,
    d,
    out,
    Q_stride_M,
    Q_stride_d,
    K_stride_N,
    K_stride_d,
    V_stride_N,
    V_stride_d,
    out_stride_M,
    out_stride_d,
    M_BLOCK: tl.constexpr,
    N_BLOCK: tl.constexpr,
    d_BLOCK: tl.constexpr,
):
    # tiled gemm
    row_pid = tl.program_id(0)
    col_pid = tl.program_id(1)
    m_indexes = row_pid * M_BLOCK + tl.arange(0, M_BLOCK)

    # this col_indexes is for final V multiplication, not the initial gemm
    v_indexes = col_pid * d_BLOCK + tl.arange(0, d_BLOCK)
    m_mask = m_indexes < M
    v_mask = v_indexes < d

    running_sum = tl.zeros([M_BLOCK], dtype=tl.float32)
    running_max = tl.full([M_BLOCK], float("-inf"), dtype=tl.float32)
    out_acc = tl.zeros([M_BLOCK, d_BLOCK], dtype=tl.float32)
    scale = 1 / tl.sqrt(d + 0.0)

    # we need to iterate through all columns (compute one complete row) to get the softmax
    # but this can be unrolled when compiled
    for nn in tl.range(0, tl.cdiv(N, N_BLOCK)):
        n_indexes = nn * N_BLOCK + tl.arange(0, N_BLOCK)
        n_mask = n_indexes < N
        # block gemm accumulator
        acc = tl.zeros((M_BLOCK, N_BLOCK), dtype=tl.float32)
        # this dd is for QK inner dimension tiling
        for dd in tl.range(0, tl.cdiv(d, d_BLOCK)):
            d_indexes = dd * d_BLOCK + tl.arange(0, d_BLOCK)
            d_mask = d_indexes < d
            M_offsets = (
                Q_stride_M * m_indexes[:, None] + Q_stride_d * d_indexes[None, :]
            )
            # do a transpose on the fly
            # this might happen to be efficient for since both are row major right not lol
            K_offsets = (
                K_stride_N * n_indexes[:, None] + K_stride_d * d_indexes[None, :]
            )

            M_mask = m_mask[:, None] & d_mask[None, :]
            K_mask = n_mask[:, None] & d_mask[None, :]
            # load
            cur_q = tl.load(Q + M_offsets, mask=M_mask, other=0.0)
            cur_k = tl.load(K + K_offsets, mask=K_mask, other=0.0)

            # partial sum, normalization on the fly to avoid overflow
            acc += tl.dot(cur_q, tl.trans(cur_k)) * scale
        # acc is an M_BLOCK * N_BLOCK gemm result
        # mask the overflow to -inf so that the alpha can be computed correctly
        acc = tl.where(m_mask[:, None] & n_mask[None, :], acc, float("-inf"))
        # run max on column, getting M_BLOCK * 1 maximum per row
        current_max = tl.max(acc, axis=-1)
        # compare with the running max and update the running_max
        new_running_max = tl.maximum(current_max, running_max)
        # alpha on updating the running_sum given the update on running_max
        alpha = tl.exp(running_max - new_running_max)  # the diff

        # compute increment to running_sum on this N_BLOCK
        weights = tl.exp(acc - new_running_max[:, None])
        # directly sum because all the denomiators are new_running_max
        incre = tl.sum(weights, axis=1)

        # running_sum = running_sum * alpha + incre
        running_sum = tl.fma(running_sum, alpha, incre)
        running_max = new_running_max

        # gemm with V.
        # N is now the inner dimension (M_BLOCK, N_BLOCK) * (N_BLOCK * d_BLOCK)
        v_offsets = n_indexes[:, None] * V_stride_N + v_indexes[None, :] * V_stride_d
        V_mask = n_mask[:, None] & v_mask[None, :]
        cur_v = tl.load(V + v_offsets, mask=V_mask)

        # dot the weights now, will normalize with running_sum later
        weighted_v = tl.dot(weights, cur_v)
        # the accumulator for gemm with V, also need to correct the error
        out_acc = tl.fma(out_acc, alpha[:, None], weighted_v)

    # the running sum is correct now
    out_acc /= running_sum[:, None]

    out_offsets = m_indexes[:, None] * out_stride_M + v_indexes[None, :] * out_stride_d
    out_mask = m_mask[:, None] & v_mask[None, :]
    tl.store(out + out_offsets, out_acc, mask=out_mask)


# Q, K, V, output are tensors on the GPU
def solve(
    Q: torch.Tensor,
    K: torch.Tensor,
    V: torch.Tensor,
    output: torch.Tensor,
    M: int,
    N: int,
    d: int,
):
    M_BLOCK = 16
    d_BLOCK = 128
    N_BLOCK = 64

    grid = (triton.cdiv(M, M_BLOCK), triton.cdiv(d, d_BLOCK))
    Q_stride_M, Q_stride_d = Q.stride()
    K_stride_N, K_stride_d = K.stride()
    V_stride_N, V_stride_d = V.stride()
    out_stride_M, out_stride_d = output.stride()

    softmax_attention[grid](
        Q=Q,
        K=K,
        V=V,
        out=output,
        M=M,
        N=N,
        d=d,
        Q_stride_M=Q_stride_M,
        Q_stride_d=Q_stride_d,
        K_stride_N=K_stride_N,
        K_stride_d=K_stride_d,
        V_stride_N=V_stride_N,
        V_stride_d=V_stride_d,
        out_stride_M=out_stride_M,
        out_stride_d=out_stride_d,
        M_BLOCK=M_BLOCK,
        d_BLOCK=d_BLOCK,
        N_BLOCK=N_BLOCK,
    )

编辑文章
分享文章:

上一篇
[TIL] TileLang EP-01:初探
下一篇
[TIL] 学习笔记:Softmax