跳转到正文
Retep's
返回

[TIL] Triton 线性布局

编辑文章

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

Triton LinearLayout

与 TileLang 类似,Triton 张量是逻辑张量,编程发生在块层面。简单的一次 tl.dot,底层由多个线程协作实现,每个线程持有部分元素。在降级到 LLVM IR 前,编译器必须回答:每个元素属于哪个寄存器、lane、warp 和 CTA?

Triton 的 LinearLayout 为这个问题提供统一表示,它是如下函数:

(register, lane, warp, block) → (tensor dimension 0, tensor dimension 1, ...)

若 L(register=2, lane=7, warp=1) = (12, 7),这个硬件位置就存放逻辑张量元素 [12, 7]。

线性布局

最初我以为它类似仿射映射,其实不同。仿射映射使用普通整数运算:

(i, j) → (4*i + j + 3, j floordiv 2)

LinearLayout 将坐标视为位向量,表示二元域 GF(2) 上的线性映射。在这个只有 {0, 1} 的空间中,加法是 XOR,系数乘法是 AND。线性性质为:

L(x XOR y) = L(x) XOR L(y)

可以这样理解加法:

该模型自然表示位排列、广播、warp/lane 分布、MMA fragment 和 XOR 共享内存 swizzle。维度大小通常要求为 2 的幂,且没有常数偏移:L(0) = 0。基址和偏移另行建模。

基向量表示

核心数据成员为:

// LinearLayout.h
llvm::MapVector<
  StringAttr,
    std::vector<std::vector<int32_t>>
> bases;

它将维度名映射到基向量列表,最内层向量包含各输出维度的坐标。考虑输入 lane、warp 与输出 row、col:

lane bit 0: L(lane=1, warp=0) = (1,1)
lane bit 1: L(lane=2, warp=0) = (2,2)
warp bit 0: L(lane=0, warp=1) = (0,1)
warp bit 1: L(lane=0, warp=2) = (0,2)

对应结构概念上为:

bases["lane"] = {{1, 1}, {2, 2}};
bases["warp"] = {{0, 1}, {0, 2}};

它描述的线性布局是:

L(lane, warp) = (lane, lane XOR warp)

可以看到 lane 已经对应行坐标。列坐标满足:

只保存四个值就定义了完整的 4×4 输入空间。MapVector 支持按维度名查找,同时保留确定的由次到主维度顺序,方便打印、重塑和矩阵转换。

LinearLayout::apply

// LinearLayout.cpp
SmallVector<std::pair<StringAttr, int32_t>>
LinearLayout::apply(ArrayRef<std::pair<StringAttr, int32_t>> ins) const {
  assertDimsEqualIgnoringOrder(llvm::make_first_range(ins), getInDimNames());

  SmallVector<std::pair<StringAttr, int32_t>> ret;
  for (StringAttr outDim : getOutDimNames()) {
    int32_t outVal = 0;
    for (auto &[inDim, val] : ins) {
      for (int i = 0; i < getInDimSizeLog2(inDim); i++) {
        if (val & (1 << i))
          outVal ^= getBasis(inDim, i, outDim);
      }
    }
    ret.push_back({outDim, outVal});
  }
  return ret;
}

基本逻辑为:

for each output coordinate:
  for each input coordinate:
    for each bit in this input coordinate:
      if this bit is set:
        output coordinate xor with that base vector (as contribution)

输入可视为基向量的系数。例如 (3, 2) 概念上对应 3 * base_0 + 2 * base_1,但 GF(2) 要逐位处理:用 AND 检查系数位,用 XOR 合并选中的基向量。这就得到 val & (1 << i) 和 outVal ^= getBasis(inDim, i, outDim);。AND 在这里是在选择哪些基向量参与,因此:

(0, 1) and (base_00 xor base_01)
xor
(1, 1) and (base_10 xor base_11)

实际上应理解为:

(0 * base_00) xor (1 * base_01)
xor
(1 * base_01) xor (1 * base_11)

来看一个例子,目标输入为:

lane = 3 = 0b11
warp = 2 = 0b10

val & (1 << i) 检查输入的第 i 位。置位表示对应 GF(2) 系数为一,需要加入该基向量。lane=3 的第 0、1 位选择:

(1,1) XOR (2,2) = (3,3)

warp=2 只有第 1 位选择:

(0,2)

合并所有选中基向量得到:

(3,3) XOR (0,2) = (3,1)

所以:

L(lane=3, warp=2) = (row=3, col=1)

实现分别计算每个输出坐标:

row = 1 XOR 2 XOR 0 = 3
col = 1 XOR 2 XOR 2 = 1

这就是 GF(2) 上的矩阵向量乘法,直接使用矩阵列进行计算,无需物化完整矩阵。

Blocked 布局示例

考虑以下 GEMM 布局:

#blocked = #ttg.blocked<{
  sizePerThread = [1, 1],
  threadsPerWarp = [1, 32],
  warpsPerCTA = [4, 1],
  order = [1, 0]
}>

对于 32×32 张量,其 LinearLayout 大致为:

register bases: (4,0), (8,0), (16,0)
lane bases:     (0,1), (0,2), (0,4), (0,8), (0,16)
warp bases:     (1,0), (2,0)

覆盖范围为:

8 registers/thread × 32 lanes × 4 warps = 1024 = 32×32

对于 (register=5, lane=3, warp=2):

register 5 = 0b101 → (4,0) XOR (16,0) = (20,0)
lane     3 = 0b011 → (0,1) XOR (0,2)   = (0,3)
warp     2 = 0b010 → (2,0)

result = (20,0) XOR (0,3) XOR (2,0) = (22,3)

该寄存器持有逻辑张量元素 [22,3]。

满射、单射与广播

构造函数调用 checkInvariants,检查基向量大小、输出维度是否为 2 的幂、坐标是否合法,并按需检查满射。

每个逻辑张量元素至少由一个硬件位置表示时,布局是满射;没有两个硬件位置映射到同一元素时,布局是单射。Triton 使用 f2reduce 行化简,依据 GF(2) 矩阵的秩计算这些性质:

bool isSurjective() const {
  return rank == getTotalOutDimSizeLog2();
}

bool isInjective() const {
  return rank == getTotalInDimSizeLog2();
}

布局不必是单射。零基向量表示广播。如果全部 warp 基向量都是零,改变 warp ID 不会改变逻辑坐标,即多个 warp 复制相同值。

组合布局

LinearLayout 支持若干代数操作:

由于线性函数完全由基向量确定,复合非常直接:

for (each basis of this)
  newBasis = outer.apply(basis);

invertAndCompose:推导数据移动

invertAndCompose 是内存和布局转换降级的核心。假设:

R: (register, lane, warp) → tensor coordinate
S: shared-memory offset   → tensor coordinate

要为某个寄存器值求共享内存地址,需要:

(register, lane, warp)
  ──R──> tensor coordinate
  ──S⁻¹─> shared offset

通过以下方式计算:

R.invertAndCompose(S)

布局可能包含广播,因此未必存在普通逆。实现会求解 GF(2) 线性方程组,选择合适的伪逆。可参考 LinearLayout::invertAndCompose 以及 LinearLayoutTest.cpp 中的针对性测试。

从布局到 LLVM IR

生成 LLVM IR 的核心函数是 applyLinearLayout,下面看看其实现:

SmallVector<std::pair<StringAttr, Value>>
applyLinearLayout(Location loc, RewriterBase &rewriter,
                  const LinearLayout &layout,
                  ArrayRef<std::pair<StringAttr, Value>> indices) {
  auto b = TritonLLVMOpBuilder(loc, rewriter);
  // Notice that we assert dim names has the same order of indices, not only size equal
  // this is because we will do concat later, and we need each dim to be aligned
  assert(layout.getNumInDims() == indices.size());
  assert(llvm::equal(layout.getInDimNames(), llvm::make_first_range(indices)));
  // Trivial layout
  if (layout.getNumOutDims() == 0) {
    return {};
  }

  // Manually constant-fold the layout where possible.
  SmallVector<std::pair<StringAttr, int32_t>> constantIns;
  SmallVector<std::pair<StringAttr, Value>> nonConstantIns;


  /*
    Here, we collect constant input and non-constant input (SSA value)
    for example, (register=3, lane=%a, warp=%b)
    constantIns = [("register", 3), ("lane", 0), ("warp", 0)]
    nonConstantIns = [("lane", %a), ("warp", %b)]
  */
  for (auto [inDimName, idx] : indices) {
    APInt constant;
    if (matchPattern(idx, m_ConstantInt(&constant))) {
      constantIns.push_back({inDimName, constant.getSExtValue()});
    } else {
      constantIns.push_back({inDimName, 0});
      nonConstantIns.push_back({inDimName, idx});
    }
  }

  // Compute constant part of the output and wrap it as values

  /*
    Here, we initialize output. 
    For all constant inputs, apply the layout to fold the constant output
  */
  Value zero = b.i32_val(0);
  SmallVector<std::pair<StringAttr, Value>> outIndices;
  for (auto [outDimName, constant] : layout.apply(constantIns)) {
    if (constant == 0)
      outIndices.push_back({outDimName, zero});
    else
      outIndices.push_back({outDimName, b.i32_val(constant)});
  }

  if (nonConstantIns.size() == 0) {
    return outIndices;
  }


  /*
    Here, we compute the non-constant input.
    Suppose nonConstantIns = [("lane", %a), ("warp", %b)]
    we concat them together by x = %a | %b (using the first for loop)
    then concat the corresponding non-const basis with layout.sublayout into matrix
    Run matrixVectorProd for bitwise AND to produce (x & matrix)
    Finally, use xor to generate the final output for that dim
  */
  SmallVector<StringAttr> inDimNames;
  // Concatenate input
  Value x = b.i32_val(0);
  int shift = 0;
  for (auto [inDimName, idx] : nonConstantIns) {
    inDimNames.push_back(inDimName);
    x = b.or_(x, b.shl(idx, b.i32_val(shift)));
    shift += layout.getInDimSizeLog2(inDimName);
  }

  for (auto &[outDimName, outIdx] : outIndices) {
    // Apply flattened sublayout for this output
    auto matrix = layout.sublayout(inDimNames, outDimName).flattenIns();
    auto out = triton::gpu::matrixVectorProd(b, matrix, x);
    outIdx = b.xor_(outIdx, out);
  }

  return outIndices;
}

编辑文章
分享文章:

上一篇
Composable Kernel Language:用 MLIR 实现基于内存效应的 GPU Kernel 组合
下一篇
[TIL] IREE 编译流水线导读