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)
可以这样理解加法:
0 + 0 = 0,0 xor 0 = 0。0 + 1 = 1,0 xor 1 = 1。1 + 1 = 10,1 xor 1 = 0,因为单比特空间中不保留进位。
该模型自然表示位排列、广播、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 已经对应行坐标。列坐标满足:
1 xor 0 = 12 xor 0 = 20 xor 1 = 10 xor 2 = 2
只保存四个值就定义了完整的 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 支持若干代数操作:
compose(outer):将outer应用于当前每个基向量,构造outer ∘ this。operator*:形成跨维度的类似直和的乘积,不是函数复合。transposeIns、transposeOuts、reshapeIns、reshapeOuts:重组命名维度及其位。sublayout:限制输入和输出维度。divideLeft、divideRight:分解兼容的布局。
由于线性函数完全由基向量确定,复合非常直接:
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;
}