跳转到正文
Retep's
返回

[Book Club] TileLang:连接现代神经网络 Kernel 的可编程性与性能

编辑文章

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

TileLang

本文将 TileLang 论文与代码联系起来阅读。所有源码位置均基于提交 69bc43e2cfbc38976b0c5e1c4b2299b66e8970ee。

1. 源码导读

首先看看 TileLang 的完整编译生命周期。

捕获

TileLang 有两条前端捕获路径:使用 @T.prim_func 静态编译,或使用 @tilelang.jit 即时编译。

在 TileLang 中,我们写:

with T.Kernel(blocks, threads=threads) as bx:
   acc_o = T.alloc_fragment(...)

这里调用的是 tilelang/language 下的 TileLang API。T.Kernel(...) 通过 tilelang/language/kernel.py:267 的 _ffi_api.KernelLaunch 创建带有 block 和 thread 绑定的 kernel 启动 frame,进而调用 src/ir.cc 中的 KernelLaunch 完成初始化。

# tilelang/language/kernel.py
def Kernel(
    *blocks: int | tirx.PrimExpr,
    threads: int | list[int] | tuple | None = None,
    cluster_dims: int | tuple[int, int, int] | list[int] | None = None,
    is_cpu: bool = False,
    prelude: str | None = None,
):

编译 kernel 时,TileLang 遍历代码的 AST 并将其转换为 TIR。脚本式 @T.prim_func 路径使用 TVM parser(tilelang/language/parser/entry.py:37)。eager JIT 路径使用 Builder,它持有 IRBuilder、进入 tirx.prim_func frame,最终返回 PrimFunc(tilelang/language/eager/builder.py:168、:193、:236)。 @tilelang.jit 用 JITImpl 封装这一过程,在运行时获取 TIR 并创建 JITKernel(tilelang/jit/__init__.py:390、tilelang/jit/kernel.py:59)。

# tilelang/language/eager/builder.py
class Builder(BaseBuilder):
    def __init__(self):
        self.frames: list[AnyFrame] = []
        self.ir_builder = IRBuilder()
        self.name_inside_frame: dict[str, AnyFrame] = {}
        self.macro_arg_annot = {}
        self.out_idx = []
        self.out_tensor_cnt = 0

    @contextmanager
    def prim_func(self, name):
        thread_local_storage.builder = self
        clear_let_values()
        try:
            with self.ir_builder, self.with_frame(tirx.prim_func()):
                tirx.func_name(name)
                yield
            if self.eager_jit != "phase1" and len(self.out_idx) != self.out_tensor_cnt:
                raise RuntimeError("Not all tensor allocated from `T.empty` are returned")
        finally:
            clear_let_values()
            del thread_local_storage.builder

    def get(self) -> PrimFunc:
        return self.ir_builder.get()

需要编译的内容分为三类:

编译过程中,TileLang 自动调优器会应用布局推荐,这是论文强调的核心贡献之一。入口在 tilelang/carver/template/base.py,也可以在用户代码中显式使用:

roller_hints = carve_template.recommend_hints(topk=topk)
...
config["block_M"] = block_m
config["block_N"] = block_n
config["block_K"] = hint.rstep[0]
config["num_stages"] = hint.pipeline_stage
config["thread_num"] = block_rows * block_cols * 32

它综合输入输出形状、依赖分析和硬件规格生成优化布局。生成的配置成为降级前代码的一部分,并在编译时具体化。

with T.Kernel(..., threads=thread_num):
   # block_M gets the recommendation on compilation
   A_shared = T.alloc_shared((block_M, block_K), dtype)

优化

得到 IR 后,需要优化并生成机器码。编译进入 JITKernel._compile_and_create_adapter,开启 TVM PassContext,并调用 tilelang.lower(tilelang/jit/kernel.py:204、:246)。lower_to_host_device_ir 绑定目标、执行语义检查,然后运行 LowerAndLegalize 和 OptimizeForTarget(tilelang/engine/lower.py:274、:300)。这两个阶段是 TileLang 的核心部分。

# tilelang/engine/lower.py
# Before lowering, do semantic check
PreLowerSemanticCheck(mod)

# Phase 1: Lower and legalize the IR
mod = LowerAndLegalize(mod, target)

# Phase 2: Optimize the IR for the target
mod = OptimizeForTarget(mod, target)

host_mod = tirx.transform.Filter(_is_host_call)(mod)
device_mod = tirx.transform.Filter(_is_device_call)(mod)

LowerAndLegalize 完成从前端到低层表示的转换:添加包装、合法化负索引、检查并行循环、简化表达式、推导归约布局、按需进行 warp specialization、规划并注入软件流水线、执行 LayoutInference、降级 tile-op、合法化向量化与内存访问,再次简化(tilelang/engine/phase.py:143)。LowerTileOp 调用操作的 Lower 方法,将带类型的 tile-op 转换为低层 TIR(src/transform/lower_tile_op.cc:1132)。GEMM 等自定义操作通过 tl.gemm.lower 降级,具体后端生成 tensor core 宏 TIR(src/op/gemm.cc:185、tilelang/tileop/gemm/__init__.py:18、tilelang/cuda/op/gemm/gemm_mma.py:71)。

# tilelang/engine/phase.py
# Run pipeline planning and software-pipeline rewriting before layout
# inference so inferred layouts see the final pipelined structure directly.
mod = tilelang.transform.PipelinePlanning()(mod)
mod = tilelang.transform.InjectSoftwarePipeline()(mod)
mod = tilelang.transform.Simplify()(mod)

# Infer memory layouts for fragments and shared memory
mod = tilelang.transform.LayoutInference()(mod)
LayoutVisual(mod)

# Lower high-level tile operations to low-level operations
mod = tilelang.transform.LowerTileOp()(mod)

随后 OptimizeForTarget 面向目标硬件进行整理:TMEM/共享屏障降级、分配规划、展平、向量化、存储改写、循环展开、allreduce 降级、LDG/STG 与 Hopper intrinsic 降级、主机与设备拆分、共享内存合并、同步和 fence 注入、packed API、kernel 启动降级以及持久化 block 变换(tilelang/engine/phase.py:231)。

论文特别强调的另一项优化是布局推导。它作为 LowerAndLegalize 中的 LayoutInference pass 注册于 tilelang/transform,调用 src/transform/layout_inference.cc 的 C++ API。推导所需的 FTG 由 BufferUseDefCollector 隐式构建(:108)。 Collect 按存储 Var 记录缓冲区,扫描函数体,将每个 tile-op 或并行循环加入 infer_list_(:480、:544、:662)。fragment 缓冲区构成图的边:addToUseList 将每个 fragment 映射到使用它的 tile-op 索引(:642)。共享相同数据 Var 的别名缓冲区记录在 buffer_data_to_buffers_ 中,并一起传播布局(:169、:398)。

代码生成

合法化和优化完成后,lower 通过 device_codegen_without_compile 生成设备源码,或通过 device_codegen 生成编译后的运行时模块(tilelang/engine/lower.py:232),从而支持不同后端。CUDA 使用 target.build.tilelang_cuda 或不编译的变体(:237);主机代码使用 LLVM 或 TileLang C host codegen(:198)。对于 tvm_ffi,设备代码由注册的 CUDA 回调调用 NVCC 编译(:103)。对于 nvrtc 后端,adapter 包装生成的源码,将其编译成可加载 CUDA 库,获取 kernel handle,并暴露面向 PyTorch 的可调用对象(tilelang/jit/adapter/nvrtc/adapter.py:27)。

下面深入讨论 TileLang 的两项核心贡献。

2. Tile 推荐

Tile 推荐通过为操作建模,优化数据放置和计算安排,也可以理解为依据 roofline 模型进行优化。

Time=max⁡i,j(MemoryTrafficiBandwidthi,ComputationjPerformancej)+tintrinsicTime = \max_{i,j}(\dfrac{MemoryTraffic_i}{Bandwidth_i}, \dfrac{Computation_j}{Performance_j}) + t_{intrinsic}

where i indexes memory hierarchy levels (e.g., HBM, L2, L1), j indexes compute unit types (e.g. tensor cores, CUDA cores, SFUs), and tintrinsict_{intrinsic} accounts for inherent overheads such as kernel launch latency and loop prologue/epilogue costs.

The implemented recommendation system is tilelang/carver. Public templates such as MatmulTemplate build an equivalent TE/TIR tensor representation, which will then be used for analysis on operation shape, reduction axes and tensorization opportunities/memory traffic.

Recommendation Data Flow

The recommendation path is intentionally separate from the TileLang program that will eventually be compiled. A template first builds an equivalent TE/TIR view of the operation. Carver analyzes that view, emits Hint objects, and the caller materializes one hint back into the TileLang kernel’s meta-parameters.

Problem shape and dtypes
M, N, K, transposes, heads, seq length
        |
        v
Template
MatmulTemplate / FlashAttentionTemplate
        |
        v
Equivalent PrimFunc or output graph
TE placeholders, compute, reduce axes
        |
        v
Tensorization detected?
        |
        +-- yes --> TensorCorePolicy
        |           MMA/WGMMA/TCGEN-aware constraints
        |
        +-- no  --> DefaultPolicy
                    CUDA-core heuristic schedule
        |
        v
Candidate Hint list
        |
        v
User/autotuner config
block_M, block_N, block_K, thread_num, num_stages, rasterization
        |
        v
TileLang kernel source
T.Kernel / alloc_shared / alloc_fragment / T.Pipelined
        |
        v
LowerAndLegalize + OptimizeForTarget

对于普通 GEMM,最终选中的 Hint 几乎可以逐项映射到 kernel 元参数:

Carver HintTileLang kernel 参数或用途
hint.block = [BM, BN]block_M、block_N,每个 CTA 的输出 tile
hint.rstep = [BK]block_K,每个流水线步骤加载的归约分片
hint.warp = [WM, WN]tensor core 的 warp tile 形状,用于推导线程配置
hint.thread = […]不使用 tensor core 时的 CUDA core 线程划分
hint.pipeline_stageT.Pipelined(…, num_stages=…)
hint.use_async异步拷贝流水线偏好
hint.rasterization_plan可选的 blockIdx 重映射,改善 L2 局部性
hint.cached_tensors预期驻留于共享内存的张量
hint.pass_context静态共享内存合并等降级选项

重要的边界是:Carver 本身不会改写用户 kernel。它推荐静态参数,benchmark/autotune 代码随后用这些参数实例化 TileLang 程序,再进入降级。

硬件模型

模型基于启发式规则,并非学习得到。硬件特性来自 TileDevice 实现。CUDA 记录共享内存容量、SM 数量、warp 大小、寄存器容量、事务大小、近似带宽和可用 tensor 指令形状(tilelang/carver/arch/cuda.py:124)。 DefaultPolicy.emit_config 构造候选 tile,估计访存量、共享内存用量、寄存器用量、block 驻留数和执行 wave 数,再按 (traffic + 1) * num_wave 排序(tilelang/carver/roller/policy/default.py:72、:96、:537)。 归约步长根据合并访存和事务大小的启发式规则选择(:241)。block 大小则结合 warp 大小和 SM 划分评分(:202、:599)。

# tilelang/carver/roller/policy/default.py
def emit_config(self, topk: int) -> list[Hint]:
    base_tile = self.get_base_tile()
    if base_tile is None:
        return []

    rstep_map = {node: self._assign_reduce_step(node) for node in self.ordered_nodes}
    smem_tile_condidates = self.dfs_smem_tile(base_tile, rstep_map)
    results = []
    for td in smem_tile_condidates:
        if not self.check_tile_shape_isvalid(td):
            continue

        self._expand_reduce_axis(td)
        for codegen_dicts in self.assign_block_size(td):
            if isinstance(codegen_dicts, dict) and len(codegen_dicts) == 1:
                results.append(list(codegen_dicts.values())[0])
# tilelang/carver/roller/policy/default.py
def prio(td: TileDict):
    return (td.traffic + 1) * td.num_wave

候选搜索可以看作在约束条件下,对输出 tile 大小进行最佳优先扩展:

Base tile
minimum tile that reduces redundant compute
        |
Assign initial rstep
coalescing/transaction heuristic
        |
Expand output tile factors
DFS/PriorityQueue over factors and {2,4,8,16,32}
        |
Compute TileDict
        |
Propagate tile to producer nodes
node.propagate_inputs / node.propagate_outputs
        |
Estimate global traffic
coalesced HBM reads and writes
        |
Estimate shared memory
node footprint + BestFit lifetime allocator
        |
Fits smem cap?
        |
        +-- no  --> reject
        |
        +-- yes --> Estimate registers
                    2 * max(tile elems * dtype bits / 32)
                         |
                    Fits reg cap?
                         |
                         +-- no  --> reject
                         |
                         +-- yes --> Estimate residency
                                     block_per_SM = min(smem, regs, sm partition)
                                          |
                                     Estimate waves
                                     ceil(grid_size / (block_per_SM * SMs))
                                          |
                                     Priority
                                     (traffic + 1) * num_wave
                                          |
                                     Expand reduce axis if smem budget allows
                                          |
                                     Assign block size / thread or warp tile
                                          |                 
                                     Emit Hint

评分体现了两种权衡:

# tilelang/carver/roller/policy/default.py
td.traffic, td.tile_map = self._compute_memory_traffic(output_tile)
td.smem_cost, td.cached_tensors_map = self._compute_shared_memory_usage(td)
if td.smem_cost > self.arch.smem_cap:
    td.valid = False
    return td
output_shape = self.output_nodes[0].get_space_dim()
td.grid_size = int(np.prod([(y + x - 1) // x for x, y in zip(output_tile, output_shape)]))
reg_usage = int(2 * max([np.prod(td.get_tile(node)) * node.get_dtype().bits / 32 for node in self.ordered_nodes]))
if reg_usage > self.arch.reg_cap:
    td.valid = False
    return td
td.block_per_SM = min(
    self.arch.max_smem_usage // max(td.smem_cost, 1),
    self.arch.reg_cap // max(reg_usage, 1),
    self.arch.sm_partition,
)
td.num_wave = int(np.ceil(td.grid_size / int(td.block_per_SM * self.arch.compute_max_core)))

Tensor core

TensorCorePolicy 加入 tensor core 专用规则:不同架构的流水线阶段和异步拷贝默认值、K 步长为 wmma_k 的倍数、tensor intrinsic 形状合法性、warp tile 分配以及共享内存限制(tilelang/carver/roller/policy/tensorcore.py:30、:86、:206、:262)。

# tilelang/carver/roller/policy/tensorcore.py
if self.arch.compute_capability in {"sm_80", "sm_90", "sm_90a"}:
    self.pipeline_stage = 2
else:
    self.pipeline_stage = 1
use_async_copy = self.prim_func_node.get_tag("use_async_copy")
if use_async_copy:
    self.use_async_copy = use_async_copy
else:
    if self.arch.compute_capability in {"sm_80", "sm_90", "sm_90a"}:
        self.use_async_copy = True
    else:
        self.use_async_copy = False

对于 tensor core GEMM,推荐器还必须保证宏 tile 与 intrinsic fragment 兼容:

Output tile [block_M, block_N]
+-----------------------------------------------+
| CTA computes one C tile                       |
|                                               |
|  +--------------+--------------+-----------+  |
|  | warp tile    | warp tile    | ...       |  |
|  | [warp_M,N]   | [warp_M,N]   |           |  |
|  +--------------+--------------+-----------+  |
|  | warp tile    | warp tile    | ...       |  |
|  +--------------+--------------+-----------+  |
|                                               |
| Each warp tile is an integer multiple of      |
| the selected MMA/WGMMA/TCGEN intrinsic shape. |
+-----------------------------------------------+

Reduction slice [block_K]
+--------------------+      +--------------------+
| A_shared BM x BK   |  x   | B_shared BN x BK   |
| staged per pipe    |      | staged per pipe    |
+--------------------+      +--------------------+

Pipeline depth multiplies the live shared-memory footprint.

对于 FlashAttentionTemplate,Carver 并不直接分析最终的 online-softmax kernel 体。模板将核心计算表示为由两个 tensorized matmul 节点组成的小图,并连接它们:

Q: [B*H, S_q, D]  ----+
                      |
               +-------------+
K: [B*H,       | MMA0: QK^T  |
   S_kv, D] -->| space:      |
               | [B*H,S_q,   |
               |  S_kv]      |
               | reduce: D   |
               +-------------+
                      |
                      | edge: score tile shape
               +-------------+
V: [B*H,       | MMA1:       |
   S_kv, D] -->| Score * V   |
               | space:      |
               | [B*H,S_q,D] |
               | reduce:     |
               | S_kv        |
               +-------------+
                      |
               O: [B*H, S_q, D]

借助这张图,DefaultPolicy/TensorCorePolicy 可以同时计算两个 matmul 节点间的 tile 传播、临时存储生命周期和访存量,而不是分别为每次 matmul 评分。

我的理解是,要让 Tile 推荐和自动调优帮助自己的 kernel 开发,还需要实现自定义模板,或复用现有公开模板。

此外,编译器还有独立于 Carver 的逐操作硬件调优。例如,CUDA GEMM 指令选择在合法时为 Blackwell 使用 TCGEN05、为 Hopper 使用 WGMMA,否则使用 MMA(src/backend/cuda/op/gemm.cc:265)。warp 划分由 GemmWarpPolicy、warp 数和矩阵尺寸启发式决定(:117、:187、:289)。

// src/backend/cuda/op/gemm.cc
if (AllowTcgen5Mma(op, target)) {
  return kCudaTCGEN05;
}
if (AllowWgmma(op, block_size, target)) {
  return kCudaWGMMA;
}
return kCudaMMA;

3. 布局推导

布局推导在 LowerAndLegalize 中执行,位于 tile-op 降级之前(tilelang/engine/phase.py:203)。pass 入口是 src/transform/layout_inference.cc:1288 的 LayoutInference。

它先读取 T.annotate_layout/layout_map 中的用户标注(:759),再执行四步:

  1. 对在 tile-op 外使用的未确定 fragment 缓冲区赋予完全复制布局(:372、:895)。
  2. 对全部操作执行一次严格推导(:383)。
  3. 沿缓冲区使用关系,以 BFS 队列执行普通推导(:393)。
  4. 按连通分量搜索执行自由推导(:396、:1030)。
// src/transform/layout_inference.cc
// step 0: set fully replicated layout for floating fragment buffers
for (const auto &[buffer, thread_bounds] : floating_fragment_buffers_) {
  if (layout_map.count(buffer))
    continue;
  auto frag =
      Fragment::FullyReplicated(buffer->shape, thread_bounds->extent);
  layout_map.Set(buffer, frag);
}

// step 1: infer strict layout
for (int i = 0; i < num_infer; i++) {
  RunInferStep(i, InferLevel::kStrict, false, layout_map, strict_layout_map,
               q, in_queue);
}

// step 2: infer common layout with BFS
FinishInferQueue(InferLevel::kCommon, layout_map, strict_layout_map, q,
                 in_queue);
// step 3: relax constraints to free and re-run
InferInFreeMode(layout_map, strict_layout_map);

结果以 attr::kLayoutMap 附着到每个 block;并行循环获得 attr::kParallelLoopLayout 和可选谓词(src/transform/layout_inference.cc:1222、:1250)。 后续 LowerTileOp 消费这些标注,重映射缓冲区形状和索引(src/transform/lower_tile_op.cc:40、:1009、:1178、:1281)。

推导图的结构

LayoutInference 在访问 TIR 函数体时隐式构图。节点是可推导操作,边是被多个操作使用的 fragment 缓冲区。共享相同数据 Var 的别名缓冲区会绑定在一起,使某个视图推导出的布局可以传播到其他视图。

BufferUseDefCollector

Tile op / Parallel loop #0
        |
        | fragment buffer A_local
        v
Tile op / Parallel loop #1
        |
        | fragment buffer C_local
        v
Tile op / Parallel loop #2

Derived indexes:

fragment buffer A_local ----> use_list_[A_local] = [0, 1]
fragment buffer C_local ----> use_list_[C_local] = [1, 2]
alias buffer view ----------> buffer_data_to_buffers_[var]

alias buffer view shares the same data Var as C_local, so layout updates can
propagate between the two views when their shapes are compatible.

infer_list_ 定义了 pass 的工作列表范围。缓冲区获得新布局后,use_list_[buffer] 中的每个操作都可以再次执行 InferLayout,因为其局部约束此时可能已经可解。

Start
  |
  v
Seed layouts
  - explicit annotations
  - floating fully replicated fragments
  |
  v
Strict inference
  - run each op once at kStrict
  - record strict_layout_map
  |
  v
Common inference
  - BFS from newly inferred buffers
  - propagate through use_list_
  |
  v
Free inference
  - build connected components
  - try each op as root
  - choose the plan with minimum fragment registers
  |
  v
Annotate IR
  - attach kLayoutMap to blocks
  - attach kParallelLoopLayout to loops
  |
  v
LowerTileOp

从整体看,三个推导层次分别回答不同问题:

Level     Main question                         Typical source of constraints
-------   ------------------------------------  --------------------------------
Strict    What layout must this op use?          GEMM/MMA shared/register layout
Common    What layout follows from neighbors?    copy/parallel/reduce propagation
Free      What layout is legal and cheapest?     synthesized loop partitions,
                                                minimum fragment register count

根据论文,布局推导分为三个子类。

严格布局推导

严格推导与具体操作相关,处理硬件敏感约束。例如,GEMM 严格推导通过 tl.gemm.infer_layout 委托给 Python(src/op/gemm.cc:229、tilelang/tileop/gemm/__init__.py:12)。CUDA MMA 为共享内存操作数返回 swizzle 布局,为寄存器操作数返回 MMA store/load fragment 布局(tilelang/cuda/op/gemm/gemm_mma.py:42)。WGMMA 和 TCGEN05 根据连续维度大小选择 full/half/quarter bank swizzle 或线性布局(tilelang/cuda/op/gemm/gemm_wgmma.py:28、tilelang/cuda/op/gemm/gemm_tcgen05.py:46)。累加器布局来自 tensor core emitter 的 make_mma_store_layout。

CUDA MMA 可能保留已有共享内存布局以避免冲突;WGMMA/TCGEN05 则始终设置严格共享布局(src/op/gemm.cc:237、src/backend/cuda/op/gemm.cc:305)。这就是 tensor core 原语的操作专用约束的具体实现。

在严格阶段,硬件指令为原本抽象的 fragment 缓冲区施加约束:

Inputs to strict GEMM inference:

target + block_size
MMA / WGMMA / TCGEN05
        |
        v
tl.gemm.infer_layout
        |
        +--> shared operand layout for A
        |    swizzle or existing layout
        |          |
        |          v
        |      A_shared ----+
        |                   |
        +--> shared operand layout for B
        |    swizzle or existing layout
        |          |
        |          v
        |      B_shared ----+--> tl.gemm --> C_local
        |                                      ^
        +--> accumulator fragment layout       |
             mma store/load layout -----------+
// src/op/gemm.cc
LayoutMap GemmNode::InferLayout(const LayoutInferArgs &T,
                                InferLevel level) const {
  if (completed_)
    return {};
  LayoutMap results;
  if (const auto f = Function::GetGlobal("tl.gemm.infer_layout")) {
    auto inferred_layouts = Downcast<LayoutMap>(
        (*f)(GetRef<Gemm>(this), T.target, T.thread_bounds));
    auto block_size = *as_const_int(T.thread_bounds->extent);
    String gemm_inst = getGemmInstructionKey(block_size, T.target);
    bool reuse_existing_shared_layout =
        ResolveGemmImpl(T.target).reuse_existing_shared_layout(gemm_inst);

普通布局推导

论文把布局推导描述为受约束的传播算法,普通推导就是 BFS 传播阶段。缓冲区获得布局时,使用它的所有 tile-op 都加入队列(src/transform/layout_inference.cc:296)。ParallelOpNode::InferLayout 尝试从已有布局的源 fragment 推导循环布局,优先考虑没有复制的写入和读取,并遵循显式循环标注(src/op/parallel.cc:357、:397)。随后根据循环布局补全其他相关缓冲区的布局(:490)。

InferLayout(op)
        |
        | returns {buffer: layout}
layout_map
        |
        | propagate aliases sharing the same data Var
use_list_
        |
        | find ops that touch the newly layouted buffer
BFS queue
        |
        | enqueue dependent op ids
InferLayout(dependent op)
        |
        | rerun at kCommon with a richer layout_map
...
// src/transform/layout_inference.cc
// Push back into BFS queue
for (int idx : use_list_[buffer]) {
  ICHECK_GE(idx, 0)
      << "Index in use_list_ for buffer " << buffer << " is negative.";
  ICHECK_LT(idx, num_infer)
      << "Index in use_list_ for buffer " << buffer
      << " out of range: " << idx << " >= " << num_infer << ".";

  EnqueueWithPriority(idx, q, in_queue, cur_infer_id, layout_map);
}

归约是结构化传播的典型例子。ReduceOp 在严格模式下不进行推导,但在普通或自由模式下,会移除源 fragment 的归约维度,将它折叠到复制维度,从而得到目标 fragment 布局(src/op/reduce.cc:169、:233)。

Source fragment layout over [M, N, K]
        reduce over K
              |
              v
Destination fragment layout over [M, N]

The removed K dimension is not discarded entirely: its work is folded into
replication so the destination layout still describes which threads own the
post-reduction values.

自由布局推导

自由推导处理仍未确定的连通分量。InferInFreeMode 使用并查集,按操作共享 fragment 缓冲区的关系,以及别名缓冲区共享存储 Var 的关系构建连通分量(src/transform/layout_inference.cc:1039)。对于每个分量,它逐个尝试将成员作为推导根,运行自由推导,捕获布局或规范化失败,并按 fragment 输出形状总大小评分,将其视为寄存器数量(:1090、:1113、:1143)。最终选择寄存器最少的方案(:1163),因此更接近穷举搜索。

// src/transform/layout_inference.cc
// Compute the total register number for this layout
int64_t reg_num = 0;
for (const auto &[buffer, layout] : tmp_layout_map) {
  if (auto frag = layout.as<Fragment>()) {
    int64_t frag_reg_num = 1;
    for (auto i : frag.value()->OutputShape()) {
      auto pci = as_const_int(i);
      ICHECK(pci != nullptr)
          << "Can not use non-constant range to "
             "iterate over a fragment/local "
             "buffer. Non-constant shape expr is: "
          << i
          << ". This is possibly because you use symbolic shape when "
             "accessing a fragment/local buffer.";
      frag_reg_num *= *pci;
    }
    reg_num += frag_reg_num;
  }
}
// Update the best plan if this one uses fewer registers
if (reg_num < min_reg_num ||
    (reg_num == min_reg_num &&
     attempt_infer_root < min_reg_num_infer_root)) {

在 ParallelOpNode 中,没有源布局时,自由模式可以通过 ComputePlanCandidate 和循环划分合成布局,并在由缓冲区推导的候选与由计划推导的候选之间选择(src/op/parallel.cc:413)。

自由阶段被放在最后,因为其限制最少。只有严格推导和普通传播仍未确定全部 fragment 布局时,才处理对应连通分量:

Unresolved connected component
ops connected by fragment buffers
        |
Pick attempt root
        |
Run root InferLayout at kFree
        |
BFS propagate kFree updates
        |
All component buffers resolved?
        |
        +-- no  --> Try another root
        |             |
        |        Pick attempt root
        |
        +-- yes --> Normalize layouts and count registers
                    |
               Lowest register count?
                    |
                    +-- no  --> Try another root
                    |
                    +-- yes --> Keep as best plan
                                  |
                           Commit best layout_map updates

因此,自由推导能够补全约束不足的用户代码,却不会直接采用遇到的第一个合法映射:每次成功的根节点尝试都根据 fragment 布局输出形状总大小评分,以此近似衡量寄存器压力。


编辑文章
分享文章:

上一篇
[TIL] 多头注意力
下一篇
[TIL] 学习笔记:卷积