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/language/eager/ast.py中的DSLMutator改写为相应 TIR 分支指令。如果分支在编译期即可确定,例如if block_m == 128,只保留实际执行的分支。 - Python 基础值:通常作为元值处理,只有参与 TIR 表达式时才需要降级,因此大部分不会生成底层代码。
- TileLang API:例如
T.alloc_fragment,按tilelang/language/allocate.py等文件中的规则转换为自定义 TIR。C++ 侧通过src/op/operator.h:172的TIR_REGISTER_TL_TILE_OP注册 tile-op,再通过src/op/operator.cc:34的ParseOperator从 intrinsic 调用还原带类型的TileOperator。
编译过程中,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 模型进行优化。
where i indexes memory hierarchy levels (e.g., HBM, L2, L1), j indexes compute unit types (e.g. tensor cores, CUDA cores, SFUs), and 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 Hint | TileLang 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_stage | T.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
评分体现了两种权衡:
- 小 tile 往往降低每 CTA 的共享内存和寄存器压力,提高 occupancy,但会增加
grid_size,可能带来更多执行 wave。 - 大 tile 能通过复用减少全局访存,但如果共享内存或寄存器压力降低了驻留数,就会被排除或扣分。
# 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),再执行四步:
- 对在 tile-op 外使用的未确定 fragment 缓冲区赋予完全复制布局(
:372、:895)。 - 对全部操作执行一次严格推导(
:383)。 - 沿缓冲区使用关系,以 BFS 队列执行普通推导(
:393)。 - 按连通分量搜索执行自由推导(
: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 布局输出形状总大小评分,以此近似衡量寄存器压力。