Apache TVM TIRx CUDA 归约原语(Reduction Tile Primitive)完全指南:local / shared / SM100 packed 三变体的调度、算法与代码生成

原创2026-09-22 17:25:151,652 阅读
文章标签:模型编译深度学习推理引擎

Apache TVM TIRx CUDA 归约原语(Reduction Tile Primitive)完全指南:local / shared / SM100 packed 三变体的调度、算法与代码生成

本篇技术指南围绕 Apache TVM 仓库中 TIRx 前端的 reduction tile primitive 展开,系统讲解其在 CUDA 后端上为 sum / max / min 三种归约操作注册的 local、shared 以及 SM100+ packed_add_sum / 3input_maxmin 五类 dispatch 变体:它们的注册优先级、接受条件(谓词门控)、底层算法、生成的 TIRx IR 与 CUDA 代码,以及输入如何改变代码生成路径。读完本文,你将掌握如何在 TIRx 脚本中编写单线程、CTA 协同、warp shuffle 乃至 SM100 打包指令级的多类归约内核,并理解 dispatch 在背后如何选择实现。

一、概览:reduction 原语与 dispatch 变体

reduction tile primitive 覆盖三种归约操作:sum、max、min,即沿指定 axes 对源张量做归约,输出到目标张量。在 TIRx 脚本中以 Tx.sum(B, A, axes=..., accum=...)、Tx.max(...)、Tx.min(...) 的形式调用,其中 accum 控制是否将结果与目标旧值合并(累加/取并)。

在 CUDA 后端,reduction.rst 记录了完整的变体注册表:

变体(Variant) 优先级(Prio) Lowering 说明
reduction/local 10 local 缓冲区源/目标;线程内顺序归约(可选 warp shuffle)
reduction/shared 10 shared 缓冲区源/目标;自适应组大小的 __shfl_xor 规约树
reduction/sm100_packed(即 packed_add_sum / 3input_maxmin) 20 CUDA SM100+ 线程级 fp32 ≥8 元素:打包 add.f32x2 / max3/min3 指令

几个关键机制点:

  • 优先级语义:local 与 shared 以优先级 10 注册,彼此通过操作数存储作用域(operand storage scope)区分——源和目标都在 local 作用域走 local 变体,都在 shared* 作用域走 shared 变体。SM100+ 的 packed_add_sum(针对 sum)与 3input_maxmin(针对 max/min)以优先级 20 注册,因此会优先于 local 命中。
  • 命名澄清:实现文件与子页面把 packed_add_sum 和 3input_maxmin 归为一组称为 "SM100 packed paths",但 sm100_packed 本身并不是 dispatch 名称,真正的 dispatch 变体名是 packed_add_sum 与 3input_maxmin。这一点在 sm100_packed.rst 中有明确说明。

dispatch 的注册基础设施位于 python/tvm/tirx/operator/tile_primitive/dispatcher.py(register_dispatch 与 predicate),三份实现源码则位于 python/tvm/backend/cuda/tile_primitive/reduction/ 目录下(local.py、shared.py、sm100_packed.py 及公共工具 utils.py)。

二、变体一:reduction → local(local 缓冲区归约)

2.1 接受条件

local 变体在源和目标都是 local 缓冲区时降低一次归约。其注册片段见 local.py:

@register_dispatch(op_name, "cuda", variant="local", priority=10, when=[
    predicate("storage_scope", _match_reduction_storage_scope, expected_scope=["local"]),
    predicate("local_valid", validate_reduction_local),
])

对操作数的具体要求(详见 local.rst):

属性 要求
target / priority cuda;优先级 10
操作数作用域 src 和 dst 均在 local,且 dtype 相等
exec scope thread(顺序、线程本地);warp / warpgroup 要求有效的非 swizzle TileLayout。warp 作用域下 laneid shard→replica 模式会自动选中专用 shuffle 路径;否则 thread_reduce=True 可选的为通用路径加 shuffle。warpgroup 作用域拒绝 thread_reduce=True
shape thread 作用域下谓词不检查 axes,也不比较 src/dst 尺寸;轴分析与循环构建在 emit 阶段进行。宽作用域视图归约要求空间布局维度匹配;归约维度在 dst 中 local extent 为 1

从源码看,validate_reduction_local 除了检查 src.scope() == "local" 与 dtype 匹配外,对 warp/warpgroup 作用域还要求:布局为 TileLayout 且非 swizzle;warp 作用域下先尝试 _analyze_shuffle_reduce 识别 laneid shard→replica 模式;随后通过 get_local_region 验证线程本地区域可解析、线程轴步长非零、replica 中不含线程轴,并用 _validate_reduction_layout 校验 src/dst 空间维度结构一致、归约维在 dst 中 local extent 为 1。

2.2 演示程序:单线程 4 元素归约

以下示例来自 test_reduction.py(thread-wise 路径):单个线程把 4 个元素的 float32 local 向量归约为标量。

@Tx.prim_func
def test_func(A_ptr: Tx.handle, B_ptr: Tx.handle):
    A = Tx.match_buffer(A_ptr, [4], "float32", layout=TileLayout(S[(4,)]))
    B = Tx.match_buffer(B_ptr, [1], "float32", layout=TileLayout(S[(1,)]))
    Tx.device_entry(); Tx.cta_id([1]); Tx.thread_id([1])
    A_local = Tx.alloc_buffer([4], "float32", scope="local")
    B_local = Tx.alloc_buffer([1], "float32", scope="local")
    for i in Tx.serial(4): A_local[i] = A[i]
    Tx.tile.sum(B_local, A_local, accum=False)     # reduction local dispatch
    B[0] = B_local[0]

注意:由于元素数 4 < 8,该调用不会进入 sm100_packed 的 packed_add_sum / 3input_maxmin 快速路径,而是停留在 local 变体(SM100+ 打包路径要求 ≥8 个元素)。

2.3 算法:三条路径

local 变体的实现入口是 reduction_local_impl,按 exec scope 与布局模式分三条路径:

路径 A:线程级顺序归约(_emit_reduction_local_thread_wise)

对输出位置做空间循环,每个位置先初始化为运算的恒等元(sum→0、max→-inf、min→+inf,除非 accum),再对源做归约循环累加。源码中的骨架(local.py)对应文档伪代码:

for spa in Tx.serial(spatial_len):
    if not accum: dst[spa] = identity
    for red in Tx.serial(reduction_len):
        dst[spa] = op(dst[spa], src[spa, red])

该路径不涉及任何跨线程通信。

路径 B:专用 shard→replica shuffle(_gen_warp_shuffle_reduce)

当源布局具有整跨度的 laneid shard(数据分布在 lanes 之间)、目标布局具有 2 的幂 laneid replica(结果广播到 lanes)时,实现让每个 lane 复制其对应的本地值,然后按 replica 宽度应用 Tx.cuda.warp_reduce。识别逻辑在 _analyze_shuffle_reduce:要求布局非 swizzle、源 laneid shard 跨度恰为 32(全 warp)、目标 laneid replica 宽度为 2 的幂且在 1~32 之间。该路径自动选择,与 thread_reduce 无关,且不会先运行通用 local-axis 循环;它也不分支 accum 参数,直接用 shuffle 结果覆写目标。

路径 C:通用 warp/warpgroup 视图路径(_emit_reduction_local_view)

将源在 local 归约轴上的元素归约到每个目标位置。warp 作用域下,thread_reduce=True 会额外发出使用 __activemask() 的显式 tvm_warp_shuffle_xor 步骤;warpgroup 作用域仅支持本地部分(thread_reduce=True 会被拒绝,见 validate_reduction_local)。accum=True 且带 shuffle 时,会先把旧 dst 值存入临时 local 缓冲区,归约+shuffle 后再合并(local.py)。

2.4 生成的 TIRx IR 与 CUDA

对 4 元素线程归约(op=sum),生成的 TIRx IR 为:

for spa in Tx.serial(1):
    dst[...] = Tx.float32(0)
    for red in Tx.serial(4):
        dst[...] = dst[...] + src[...]        # op = sum

对应的 CUDA 代码:

for (int red = 0; red < 4; ++red)
  B_local_ptr[0] = B_local_ptr[0] + A_local_ptr[red];

文档说明该路径已在 sm_100a 上验证,满足 B == sum(A)。

2.5 输入如何改变算法

输入 效果
op sum → +,max → max,min → min(连同各自的恒等元;映射表见 utils.py)
exec scope thread → 顺序;匹配 warp shard→replica 布局 → 专用 warp_reduce;否则 warp/warpgroup 走通用 local view 路径,仅 thread_reduce=True 时带可选 warp shuffles
axes / shape 决定 spatial 与 reduction 循环的界限
accum thread-wise 与通用 view 路径按上文方式复用旧 dst 值;专用 shard→replica 路径忽略该标志

三、变体二:reduction → shared(shared 缓冲区归约)

3.1 接受条件

shared 变体在源和目标都是 shared 内存时生效。注册片段见 shared.py:

@register_dispatch(op_name, "cuda", variant="shared", priority=10, when=[
    predicate("storage_scope", _match_reduction_storage_scope, expected_scope=["shared*"]),
    predicate("shared_valid", validate_reduction_shared),
])
属性 要求
target / priority cuda;优先级 10
操作数作用域 src 和 dst 均在 shared*,dtype 相等
exec scope cta / warpgroup / warp(shuffle 树)或 thread(顺序)
线程绑定 存在 threadIdx.x 且为 1-D(无 threadIdx.y/z)。校验器不测试是否可被所选 shuffle 组大小整除
shape dst 大小等于源的 spatial extent(非归约维度乘积)

validate_reduction_shared 源码印证了上述约束:拒绝多维线程绑定(含 threadIdx.y/z),并通过 Analyzer 证明 dst 元素数等于源 spatial 维度乘积。

3.2 演示程序:32 线程 CTA 按行归约

把 4×8 的 float32 shared tile 沿轴 -1 归约为 4 向量(同样出自 test_reduction.py):

@Tx.prim_func
def test_reduction(A_ptr: Tx.handle, B_ptr: Tx.handle):
    A = Tx.match_buffer(A_ptr, (4, 8), "float32", layout=TileLayout(S[(4, 8)]))
    B = Tx.match_buffer(B_ptr, (4,),  "float32", layout=TileLayout(S[(4,)]))
    Tx.device_entry(); Tx.cta_id([1]); Tx.thread_id([32])
    A_smem = Tx.alloc_buffer((4, 8), "float32", scope="shared", layout=TileLayout(S[(4, 8)]))
    B_smem = Tx.alloc_buffer((4,),  "float32", scope="shared", layout=TileLayout(S[(4,)]))
    Tx.tile.cta.copy(A_smem, A); Tx.cuda.cta_sync()
    Tx.tile.cta.sum(B_smem, A_smem, axes=(-1,), accum=False)   # reduction shared dispatch
    Tx.cuda.cta_sync()
    Tx.tile.cta.copy(B, B_smem)

3.3 算法:自适应组大小的 shuffle 树

实现入口 reduction_shared_impl 在 cta/warpgroup/warp 作用域走 _emit_reduction_shared_cta,在 thread 作用域走顺序循环。CTA 级算法分两步:

步骤 1:选择组大小。 group_size = min(next_power_of_2(reduction_len), 32, thread_cnt)。本例中 reduction_len = 8,故 group_size = 8。每组 8 个 lane 协作归约一行,CTA 并行处理 4 行。源码(shared.py)还保证 group_size >= 1,shuffle 步数 n_shuffles = log2(group_size)(group_size=1 时为 0),空间并行度 spatial_par = thread_cnt // group_size。

步骤 2:Gather + shuffle 树。 每个 lane 把自己的归约轴切片加载进寄存器,然后执行 log2(group_size) 次 shfl_xor(掩码 1, 2, 4)折叠组内结果;每组 lane 0 写入结果,随后同步:

mask = Tx.tvm_warp_activemask()
for i in range(n_shuffles):                       # n_shuffles = log2(group_size)
    thread_data[0] = op(thread_data[0],
                        Tx.tvm_warp_shuffle_xor(mask, thread_data[0], 1 << i, group_size, 32))

同步原语按作用域选择:warp 用 warp_sync,warpgroup 用 warpgroup_sync(8),cta 用 cta_sync(shared.py)。thread 作用域则退化为与 local 相同的顺序循环。写入目标时,accum=True 会以 if_then_else 把旧 dst 值与归约结果合并(shared.py)。

3.4 生成的 TIRx IR 与 CUDA

生成的 TIRx IR(3 次 shuffle,宽度 8):

thread_data[0] = thread_data[0] + Tx.tvm_warp_shuffle_xor(Tx.tvm_warp_activemask(), thread_data[0], 1, 8, 32)
thread_data[0] = thread_data[0] + Tx.tvm_warp_shuffle_xor(Tx.tvm_warp_activemask(), thread_data[0], 2, 8, 32)
thread_data[0] = thread_data[0] + Tx.tvm_warp_shuffle_xor(Tx.tvm_warp_activemask(), thread_data[0], 4, 8, 32)

对应 CUDA:

thread_data_ptr[0] = thread_data_ptr[0] + __shfl_xor_sync(__activemask(), thread_data_ptr[0], 1, 8);
thread_data_ptr[0] = thread_data_ptr[0] + __shfl_xor_sync(__activemask(), thread_data_ptr[0], 2, 8);
thread_data_ptr[0] = thread_data_ptr[0] + __shfl_xor_sync(__activemask(), thread_data_ptr[0], 4, 8);

已在 sm_100a 上验证满足 B[r] == sum(A[r, :])。注意 shuffle 宽度 8 是组大小而非全 warp 宽度。

3.5 输入如何改变算法

输入 效果
op sum → + shuffle 树;max/min → 相应合并操作
reduction length / thread count 决定 group_size = min(next_pow2(reduction_len), 32, thread_cnt),从而决定 shuffle 步数;spatial_par 用整数除法 thread_cnt // group_size
exec scope cta/warpgroup/warp → shuffle 树(不同同步);thread → 顺序循环
accum True 时把归约结果与旧 dst 合并

四、变体三:reduction → SM100 packed 快速路径

4.1 接受条件(谓词门控)

packed_add_sum(对应 sum)与 3input_maxmin(对应 max/min)是 CUDA SM100+ 的快速路径,优先级 20,因而抢占 local。两者都接受线程作用域内、从 1-D float32 向量(至少 8 个元素)归约为标量的操作。注册谓词(sm100_packed.py)全部满足才会命中,否则 dispatch 拒绝并回落到 local:

@register_dispatch(op_name, "cuda", variant=variant_name, priority=20,
    when=[
        predicate("exec_scope", exec_scope_ok, expected_scopes=["thread"]),
        predicate("local_scope", _local_scope_match),       # src & dst local
        predicate("dst_len", _dst_len_ok, expected_len=1),  # reduce to scalar
        predicate("src_ndim", _src_ndim_ok, expected_ndim=1),
        predicate("dtype", _dtype_ok, expected_dtype="float32"),
        predicate("sm_version", sm_version_ok, min_version=100),
        predicate("reduction_len", _reduction_len_ok, min_len=8),
    ])
属性 要求
target / priority cuda sm_100+;优先级 20(胜过 local)
exec scope 仅 thread
操作数 src 与 dst 均 local、均为 float32;dst 长度为 1;src 为 1-D 且元素数 ≥ 8
axes 该变体的谓词不检查 reduce_axes;实现折叠整个 1-D 源区域

注意最后一点:与 local/shared 不同,SM100 packed 路径不关心 axes 参数,它总是折叠完整的 1-D 源区域。

4.2 演示程序:单线程 32 元素求和

在 sm_100a 目标上单线程对 32 元素 float32 local 向量求和(来自 test_reduction.py 的 test_reduction_local_optimized_packed_add_sum,参数化 reduction_len ∈ {8, 16, 64, 128, 256, 9, 17, 63, 65, 100}):

@Tx.prim_func
def test_func(A_ptr: Tx.handle, B_ptr: Tx.handle):
    A = Tx.match_buffer(A_ptr, [32], "float32", layout=TileLayout(S[(32,)]))
    B = Tx.match_buffer(B_ptr, [1], "float32", layout=TileLayout(S[(1,)]))
    Tx.device_entry(); Tx.cta_id([1]); Tx.thread_id([1])
    A_local = Tx.alloc_buffer([32], "float32", scope="local")
    B_local = Tx.alloc_buffer([1], "float32", scope="local")
    for i in Tx.serial(32): A_local[i] = A[i]
    Tx.tile.sum(B_local, A_local, accum=False)     # -> packed_add_sum
    B[0] = B_local[0]

target = tvm.target.Target({"kind": "cuda", "arch": "sm_100a"})

对应的 max/min 测试 test_reduction_local_optimized_3input_maxmin 结构相同,仅将 Tx.sum 换成 Tx.max/Tx.min,目标同样为 SM100+(测试带有 skipif(not env.has_cuda_compute(10)) 守卫,即要求计算能力 ≥ 10.0)。

4.3 算法:打包指令归约

sum(packed_add_sum)。 维护 8 宽的 float32 累加器。先把前 8 个元素装入累加器;此后每来一个 8 元素块,用四条 add.f32x2(每条同时加两个 float2 lane)成对并入;剩余部分用标量循环处理;最后用三次 add.f32x2 把累加器折叠 8 → 4 → 2 → 1。源码 _emit_reduction_local_thread_packed_add_sum 展示了细节:由于 add.f32x2 的操作数是 .b64 寄存器对,每次打包加法都伴随 mov.b64 打包/解包:

# final tree (8 -> 4 -> 2 -> 1); mov.b64 packs/unpacks the float2 lanes
Tx.ptx.mov.b64(acc, local_sum[0], local_sum[1])
Tx.ptx.mov.b64(rhs, local_sum[2], local_sum[3])
Tx.ptx.add.rn.ftz.f32x2(acc, acc, rhs)
Tx.ptx.mov.b64(local_sum[0], local_sum[1], acc)
# ... same for local_sum[4:8], then fold the two halves together ...
dst[...] = local_sum[0] + local_sum[1]

accum=True 时,旧 dst 值被并入第一个累加器槽位(local_sum[0] = src[src_base] + dst[...])。

max / min(3input_maxmin)。 使用 4 宽累加器,用 max3.f32 / min3.f32 指令三元素一折。源码 _emit_reduction_local_thread_3input_maxmin 中,reduce3_name 由 op 类型决定("max" 或 "min"),同一 max/min 助记符按操作数个数被 ISA(9.7.3.12 节)解析为三源指令。处理 8 元素块时以 T.unroll(4) 展开四条三输入折叠;余数部分用标量 op_func 处理;最后把 4 个临时值两两合并并再经一次三输入折叠得到结果。

4.4 生成的 TIRx IR 与 CUDA

生成的 TIRx IR(8→4→2→1 树):

Tx.ptx.mov.b64(acc, local_sum[0], local_sum[1])
Tx.ptx.mov.b64(rhs, local_sum[2], local_sum[3])
Tx.ptx.add.rn.ftz.f32x2(acc, acc, rhs)                             # ... the 8->4->2->1 tree
Tx.ptx.mov.b64(local_sum[0], local_sum[1], acc)

对应的 CUDA 形式:

// packed pairwise add: two float lanes per instruction
"add.rn.ftz.f32x2 %0, %1, %2;"
// call: tvm_builtin_ptx_add_rn_ftz_f32x2(acc, acc, rhs);
//   with acc / rhs packed by tvm_builtin_ptx_mov_pack_b32x2_b64_u64_f32(...)
//   and unpacked by  tvm_builtin_ptx_mov_unpack_b32x2_b64_f32_u64(...)

文档说明已在 sm_100a 上对 32 元素向量验证 B == sum(A)。

4.5 输入如何改变算法

输入 效果
op sum → add.f32x2 打包树;max/min → max3.f32/min3.f32 三输入折叠
reduction length 决定 8 元素块(sum)/块的循环次数与标量余数循环;必须 ≥ 8
accum True 时把旧 dst 值折叠进第一个累加器槽位
门控外的一切 非 fp32、2-D src、dst 长度 > 1、SM100 之前、或元素 < 8 → dispatch 拒绝,由 local 在其要求满足时接管

五、测试验证与运行方式

仓库在 tests/python/tirx/operator/tile_primitive/cuda/reduction/test_reduction.py 中提供了覆盖上述全部路径的端到端 GPU 测试:

  • test_reduction_shared:CTA 级 shared 归约,参数化覆盖多种 shape/axes 组合(含归约首维、末两维、中间维、非 2 的幂尺寸、带偏移切片),并对 op_type ∈ {sum, max, min}、dtype ∈ {float32, float16}、accum ∈ {False, True} 全组合验证,参考结果用 NumPy 的 sum/max/min(axis=axes) 计算;
  • test_reduction_shared_subscope:shared 归约在 cta/warpgroup/warp 子作用域下的行为;
  • test_reduction_local_thread_wise / test_reduction_local_view_basic / test_reduction_local_view_complex:local 变体的线程级与视图路径(后者参数化 n_groups、n_warps、shuffle 等);
  • test_reduction_local_optimized_3input_maxmin / test_reduction_local_optimized_packed_add_sum:SM100 打包路径,packed_add_sum 覆盖多种归约长度(含非 2 的幂 9、17、63、65、100)与 accum;
  • test_reduction_op_warp_shuffle 系列:warp 作用域下的 laneid shard→replica shuffle 路径,含多元素、交错/置换存储布局、多 warp 循环等变体;
  • test_reduction_warpgroup_wg_local_layout:warpgroup + wg_local_layout 组合。

这些测试统一使用 tvm.compile(mod, target=target, tir_pipeline="tirx") 把 TIRx PrimFunc 编译到 CUDA,再在 GPU 上执行并与 NumPy 参考结果比对(tvm.testing.assert_allclose,容差 atol=1e-5)。运行需要 CUDA 环境(测试带 @pytest.mark.gpu 与 skipif(not env.has_cuda()) 守卫),SM100 打包路径还需计算能力 ≥ 10.0(env.has_cuda_compute(10) 守卫)。

六、总结与实践要点

  • 按作用域自动分派:local 与 shared 变体共享优先级 10,由操作数存储作用域区分;把缓冲区声明为 scope="local" 或 scope="shared" 即决定了走哪条路径,无需手动指定变体名。
  • SM100+ 自动提速:在满足门控条件(thread 作用域、local 缓冲区、float32、1-D、≥8 元素、dst 长度 1)时,sum/max/min 会自动命中优先级 20 的 packed_add_sum/3input_maxmin,使用 add.f32x2、max3.f32/min3.f32 打包指令,每个指令折叠 2~3 个值。
  • axes 的语义差异:local/shared 变体严格遵循 axes 参数选择归约维度;SM100 packed 路径忽略 axes,总是折叠整个 1-D 源区域。
  • accum 的行为差异:thread-wise 与通用 view 路径、shared 路径都会复用旧 dst 值;local 的专用 shard→replica shuffle 路径忽略 accum;SM100 packed 路径把旧值并入首个累加器槽位。
  • 命名注意:sm100_packed 仅是文档分组名,真正的 dispatch 变体名是 packed_add_sum 与 3input_maxmin。

进一步深入可阅读 reduction.rst 及其三个子页面 local.rst、shared.rst、sm100_packed.rst,实现源码位于 python/tvm/backend/cuda/tile_primitive/reduction/,dispatch 框架见 python/tvm/tirx/operator/tile_primitive/dispatcher.py。

登录后查看全文
tvm