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行 query。d_BLOCK个输出列。
本版本中:
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,维护:
running_max:目前遇到的最大分数。running_sum:以该最大值为基准的 Softmax 分母。out_acc:同一基准下尚未归一化的 attention 输出。
处理完某个 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 无法对所有可能输入完全展开循环,所以生成的程序中仍有实际循环。如果把它们改为编译期常量,或者以其他方式让边界在编译期已知,编译器就有更大的展开空间。
需要区分:
- 块内数学运算具有静态形状,编译为向量化 GPU 代码。
- 扫描 key 块仍然是循环。
d为运行时值时,内部dtile 的扫描也仍然是循环。
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 并行:
- 不同
row_pid计算不同 query 行。 - 不同
col_pid计算不同输出特征列。 - 这些 program 可以同时在不同 SM 上执行。
单个 program 内,块操作并行执行:
tl.load加载一块元素。tl.max沿块中的行归约。tl.sum沿块中的行归约。tl.dot使用多个 lane 和指令计算矩阵乘法 tile。
单个 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 搬运大量中间数据:
- GEMM 读取
Q、K,写出包含M * N个元素的S。 - Softmax 读取
S、写出P,并且往往要为最大值、求和和归一化多次扫描每行。 - 第二次 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 中间流量 |
|---|---|---|
写出分数 S | M * N 个元素 | 0 次全局写入 |
| 为 Softmax 读取分数 | M * N 个元素 | 0 次全局读取 |
写出概率 P | M * N 个元素 | 0 次全局写入 |
为 P @ V 读取概率 | M * N 个元素 | 0 次全局读取 |
对于 4096 x 4096 的 fp16 矩阵,每次完整扫描约为 32 MB,四次就是约 128 MB 的额外 HBM 流量。
融合 kernel 不把 S 或 P 写入全局内存,而是计算一个分数 tile,更新在线 Softmax 状态,将权重应用到 V,然后丢弃该分数 tile。
从运行成本看,瓶颈发生了变化:
- 独立 kernel 需要支付高效 GEMM 计算,以及
S、P的大规模全局访存成本。 - 融合 kernel 的逐 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,
)