XLU 合并与源总线分配

本页中的每个 opcode、地址、偏移、位位置和立即数，均从 libtpu-0.0.40-cp314 wheel 中的 libtpu.so 按字节精确读取（BuildID md5 89edbbe81c5b328a958fe628a9f2207d，781,691,048 字节，未剥离 — 完整 C++ 符号，nm -C 可解析每个方法）。.text 和 .rodata 的 VMA 等于其文件偏移；.data.rel.ro 的 VMA - 0x200000 = 文件偏移。其他 libtpu 构建会有所不同。

摘要

本页是 xla::jellyfish::LloXluGraphOptimizer 的成本半部分 — 四个用于决定放置的 pass，以及它们共同计价所依据的延迟模型。配套的 XLU Op 名册编目了 opcode，并从更高层次走读完整五阶段流水线；本页则深入三个读取成本的调度决策 — ComputeCombinablePairs、AssignXlu/AssignSourceBus、ReorderToShortenCriticalPath — 以及边权模型（LatencyTable::Create → PreXluAssignmentLatencyTable），该模型把按代际的延迟表转换为 XLU op 图的依赖边权重。

XLU（Cross-Lane Unit）是稀缺的多周期 TensorCore 引擎，与 MXU 从同一个 VectorExtended bundle 槽位发射。在把 cross-lane op 降低进 bundle 之前，优化器会重写它们的依赖图：它会融合相邻的相同 op（ComputeCombinablePairs），按累计成本最小原则把幸存者装箱到每代的 XLU 单元上（AssignXlu），用延迟加权的列表调度器重排它们以缩短每个单元的关键路径（ReorderToShortenCriticalPath），并且在 Pufferfish（v4）上把它们的操作数路由到 V0/V1/V2/V3 源总线（AssignSourceBus）。如果你熟悉 LLVM 的 modulo scheduler 和 SelectionDAG 关键路径启发式，那么这是针对单一资源类型的小型专用类比："priority" 是边际延迟，"machine model" 是按 (op,op) 的 LatencyBetween 表，核心技巧是 XLU↔XLU 边延迟会被 XLU 数量相除 — 这个并行度折扣使得一串 cross-lane reduce 在代际拥有更多 XLU 时变得更便宜。

本页按顺序记录：延迟边模型（LatencyTable::Create 注册表分发 + ceil(base / xlu_count) 的 PreXluAssignmentLatencyTable 包装器），因为其他所有 pass 都会读取它；合并谓词；贪心单元分配；重排列表调度器；以及带共享总线串行化 hazard 的源总线分配器。闭式边际成本函数 CyclesAddedByXluOperation 和按 XLU 的 PerXluOperations 状态结构记录在 XLU Reemit 成本中，并在此引用。

对于重新实现，契约是：

XLU 边权重：IsXluOp(from) && IsXluOp(to) ? ceil(base_LatencyBetween / xlu_count) : base_LatencyBetween，以及 IsXluOp opcode 集。
合并谓词：相等的元数据键 + tracker 就绪性 + 受关键路径界定；控制 op 永不融合。
AssignXlu：按累计 CyclesAddedByXluOperation 的贪心最小负载装箱；单元索引提交到 WORD[instr+0xb] 的 bits 8-10。
ReorderToShortenCriticalPath：按 XLU 的最大堆，以边际成本为键，XluOperationIsReady 门控，按 XLU 的完成时钟关键路径测试。
AssignSourceBus：HasVexSourceBuses 门控，SourceBusesForXlu(i) = {i, i+2}，贪心/显式总线绑定，以及共享总线的 UpdateEdge 串行化边。


优化器	`xla::jellyfish::LloXluGraphOptimizer::Optimize` @ `0x126cdb80`
合并	`ComputeCombinablePairs` @ `0x126d2480`（sret `vector<pair<variant,variant>>`）
单元分配	`AssignXlu` @ `0x126d3100`（贪心最小负载；要求 `xlu_count > 1`）
重排	`ReorderToShortenCriticalPath` @ `0x126d3460`（按 XLU 的最大堆列表调度器）
源总线	`AssignSourceBus` @ `0x126d70e0`（此构建中仅 Pufferfish）
边模型	`PreXluAssignmentLatencyTable::LatencyBetweenInternal` @ `0x126e0e40` — `ceil(base / xlu_count)`
基表	`LatencyTable::Create(TpuVersion)` @ `0x1c89fba0` — 注册表 `@0x225799f8` 分发
成本函数	`CyclesAddedByXluOperation` @ `0x126d22a0`（见 XLU Reemit 成本）
XLU 数量	`VectorIsa.xlu_count` = `DWORD[Target+0x4b0]`
位字段	`WORD[LloInstruction+0xb]`：单元 `bits 8-9`（+valid `10`），总线 `bits 11-12`（+valid `13`）
置信度	CONFIRMED（字节锚定），除非某行另有说明

边权重模型

目的

下面四个 pass 中的每个放置决策最终都会归结为一个问题：在同一个 XLU 上把 op B 放在 op A 之后要花多少周期？ 这个数是依赖图的边权重，而 XLU 优化器不会直接读取按代际的延迟表 — 它读取一个很薄的包装器 PreXluAssignmentLatencyTable，由它应用 XLU 并行度折扣。先记录这一点，因为它就是合并 DP、单元分配最小成本选择、重排堆优先级和源总线关键路径深度共同消费的成本。

成本模型分为两层，对应 CycleTable / Performance 拆分：一个由注册表分发选择的按代际基础 LatencyTable，以及 XLU 优化器围绕它建立的包装器。基础表回答"原始按 (op,op) 的延迟"；包装器只重写 XLU↔XLU 边。

基表 — LatencyTable::Create

LatencyTable::Create(TpuVersion)（@0x1c89fba0）是注册表分发，不是针对版本的 if 链。反编译中的字节精确内容：

// LatencyTable* LatencyTable::Create(TpuVersion version)   // @0x1c89fba0
LatencyTable* Create(int version) {
    VLOG(2) << "Creating latency table for deepsea version: " << version; // latency_table.cc:119
    CHECK(registry != nullptr);                  // @0x225799f8 ; "no latency tables registered" :120
    CHECK(version >= 0);                          // :122
    CHECK(version < registry->size());            // :123  (size = registry_word >> 1)
    factory = (*registry)[version].factory;       // slot stride 0x20, factory at [slot+0x18]
    CHECK(factory != nullptr);                    // :124  "no latency table for " << version
    return factory(&(*registry)[version]);        // call rax — builds the per-gen subclass
}
```text

注册表是全局 `registry` `@0x225799f8`，一个以 `TpuVersion` 为键的平坦 map；每个槽位为 `0x20` 字节，并在 `+0x18` 保存其工厂函数指针。返回对象是按代际的子类 — v2/v3 是 `LatencyTableJellyfish`（15 字段复制模型），VF/GL 是堆上 `MxuLatencyTable` 形式。`CrossXluOperationsDataDependencyTracker` 在 `[tracker+0xf8]` 保存这个基表，并把它（`r8` 参数）传给其内部 `LloDependencyGraph` 构造函数，作为图的边权重来源。

> **注意 —** `Create` 不执行任何 XLU 特定覆盖。tracker 的原始图边是标准的按代际延迟模型。XLU 折扣由下面的包装器*叠加*应用 — 因此重新实现者必须保持两个表分离：tracker 持有基表，优化器持有包装器。

### 包装器 — PreXluAssignmentLatencyTable

`LloXluGraphOptimizer::Optimize` 在 `AdjustEdgesBeforeXluAssignment` 之后立即在堆上构建一个 `PreXluAssignmentLatencyTable`（`new`，sizeof `0x28`）。其布局字节精确如下：

| offset | 字段 | 含义 |
|---|---|---|
| `+0x00` | vptr | `PreXluAssignmentLatencyTable` vtable（`@0x218e0950`） |
| `+0x08` | `i32` | `TpuVersion`（基础 `LatencyTable` 字段） |
| `+0x10` | ptr | `0`（基础 lazy buffer；在 dtor 中释放） |
| `+0x18` | `LatencyTable*` | **delegate** — 优化器先前的表（按代际基表） |
| `+0x20` | `i32` | **divisor** = `xlu_count` = `DWORD[Target+0x4b0]` |

它的 `LatencyBetweenInternal(from, to)`（`@0x126e0e40`）就是 XLU 边权重。反编译中字节精确如下（先用 switch 检查 `from.op`，再检查 `to.op`）：

```c
// PreXluAssignmentLatencyTable::LatencyBetweenInternal(LloValue* from, LloValue* to)  @0x126e0e40
long LatencyBetweenInternal(LloValue* from, LloValue* to) {
    if (IsXluOp(*(u16*)from) && IsXluOp(*(u16*)to)) {
        int raw = delegate->LatencyBetween(from, to);   // [this+0x18] base @0x1c89f820
        int div = xlu_count;                             // [this+0x20]
        return ceil_div(raw, div);                       // see ceil arithmetic below
    }
    return delegate->LatencyBetween(from, to);           // pass-through, all non-XLU edges
}

IsXluOp(op) 是两个 opcode 区段的并集，二者都能直接从 case 标签看到：

IsXluOp(op) =
    op ∈ {0x8b, 0x8c, 0xa6, 0xa7, 0xf5..0x101, 0x14f, 0x150, 0x154, 0x155}   // 21 XLU opcodes (switch cases)
  | (op <= 0x3b && _bittest64(0x0C40000000000000, op))                        // = {0x36, 0x3a, 0x3b}
```text

这 21 个 opcode 是 cross-lane reduce / permute / transpose 家族。位掩码区段 `0x0C40000000000000`（bits 54、58、59）正好再加入三个 — `{0x36, 0x3a, 0x3b}` = `kVectorPermute`/`kVectorRotate`/`kVectorBroadcastLane` — 因此 `IsXluOp` 覆盖 **24** 个 opcode。任何其他 opcode（整个 matmul/push/EUP 区段 `{0x8d..0x153}` 减去 XLU case，以及 `[0x36, 0x155]` 之外的所有内容）走透传分支。

`ceil` 是带符号修正的整数算术（字节精确 `@0x126e0e8b..0x126e0ed0`）：

```c
long ceil_div(int raw, int div) {        // div > 0 in practice (xlu_count >= 1)
    int q = raw / div;                    // truncating cdq/idiv
    if (q < 0) return q;                  // negative quotient: no round-up
    int bump = 1;
    if (raw <= div*q || div <= 0)         // remainder is zero (or div<=0 guard)
        bump = (div < 0 && raw < div*q);
    return q + bump;                      // = ceil(raw/div) for div>0
}

已按反编译语义中的示例验证：ceil(8/3)=3、ceil(88/4)=22、ceil(92/8)=12、ceil(105/2)=53、ceil(7/2)=4。

XLU↔XLU 边是按代际的基础延迟分摊到可用 cross-lane 单元上。当 xlu_count = 2 时，reduce 链边成本为 ceil(B/2) — 约为串行延迟的一半，因为两个 XLU 并行运行。这是整个优化器计价所依据的唯一折扣；下面所有内容都通过这个包装器读取 LatencyBetween。

VectorRawHazardCycles（@0x126e0e20）尾调用委托给基表且保持不变 — 包装器缩放的是依赖边，不是 raw-hazard cycles。xlu_count 本身来自 VectorIsa.xlu_count（proto 字段 #6），由 Target::Init（@0x1d60fc20）复制到 DWORD[Target+0x4b0]；相邻的 [Target+0x4ac] = mxu_count，[Target+0x4a8] = iar_count。

ComputeCombinablePairs — 融合分析

目的

两个相邻的 XLU op 如果对相同操作数执行相同 cross-lane 操作（例如两个馈入同一 permute pattern 的 sum-reduce），就能折叠为一次 cross-lane pass，只为 pattern 设置付费一次。ComputeCombinablePairs 找出这些融合并返回候选 pair；实际重写稍后由 ReemitReorderedCombinedXluOperations 完成。

入口点

text

LloXluGraphOptimizer::Optimize @0x126cdb80
  └─ CrossXlu Create (tracker #1, reverse=0)        ; data-dependency tracker over the XLU ops
  └─ ComputeCombinablePairs @0x126d2480  ── this pass
       ├─ CyclesAddedByXluOperation @0x126d22a0     ; per-op marginal cost (PreXlu table)
       ├─ GetRpuTransposeOperationKeyFrom @0x126d8520 ; RpuOperationMetadata extractor
       ├─ value_visitor __fmatrix @0x218e0898       ; variant-dispatched grouping
       │    ├─ $_0 TransposeTile @0x126dce40        ; TransposeTileMetadata bucket
       │    ├─ $_1 RpuOperation  @0x126dd0a0        ; RpuOperationMetadata bucket
       │    └─ $_2 XluControl    @0x2139b1c0        ; LogFatal — UNREACHABLE
       └─ XluOperationIsReady @0x126cd920           ; tracker readiness gate
```text

### 算法

`ComputeCombinablePairs`（`@0x126d2480`）接收 XLU-op 列表（`vector<variant<TransposeTile, RpuOperation, XluControlOperation>*>`）、跨区域 `from`/`to` 边界 `LloValue` pair，以及依赖 tracker，返回（sret）一个 `vector<pair<variant*,variant*>>`。

```c
// ComputeCombinablePairs(const vector<variant*>& xlu_ops, LloValue* from, LloValue* to,
//                        CrossXluOperationsDataDependencyTracker* tracker) -> vector<pair<variant*,variant*>>
function ComputeCombinablePairs(xlu_ops, from, to, tracker):
    N = xlu_ops.size()
    cycles[N], values[N], cummax[N] = new int64[N] each, memset 0   // @0x126d251f/255b/257f

    // PHASE A — per-op cost + value arrays (@0x126d24b9..)
    prev_op = null; prev_value = null
    for i in 0..N:
        op = xlu_ops[i]
        cur_value  = resolve_value(op)              // by variant idx @[op+0x40]
        values[i]  = cur_value.anchor               // [value+0x28]->[+0x10]
        cycles[i]  = CyclesAddedByXluOperation(prev_op, op, prev_value, cur_value, PreXlu_table)
        if op contributes: prev_op = op; prev_value = cur_value   // cmovne-advance

    // critical-path DP (triangular loop @0x126d2b30): cumulative-max of per-op cycles over windows
    for i in 0..N:
        for j from i downward:
            cummax[j] = max(cummax[j], cycles[j] + window_cost)

    // PHASE B — metadata grouping + pair emission (@0x126d2bf9..)
    rpu_map  : FlatHashMap<RpuOperationMetadata,      btree_set<long,256>>   // op INDICES per key
    xpo_map  : FlatHashMap<TransposeTileMetadata,     btree_set<long,256>>
    for i in 0..N:
        op = xlu_ops[i]
        visit(op):                                  // value_visitor __fmatrix @0x218e0898
          valueless (idx 0xff): skip
          TransposeTile  ($_0): key = {height, anchor, vxpose_mode, ...}    // bucket = xpo_map
          RpuOperation   ($_1): key = GetRpuTransposeOperationKeyFrom(op)   // bucket = rpu_map
          XluControl     ($_2): LogFatal "unexpected XluOperation type"     // :1750 — UNREACHABLE
        for prior_index in bucket[key]:
            if XluOperationIsReady(tracker, op) and cost_compatible(cummax):   // @0x126cd920
                emit pair {xlu_ops[prior_index], op}     // push_back @0x126d8880
                RemoveScheduledXluOperation(tracker, ...)  // @0x126ccfa0 — erase scheduled
        bucket[key].insert(i)
    return pairs

融合谓词

两个相邻 XLU op 融合为一个 cross-lane 操作，当且仅当以下三项都成立：

相同 variant 种类且相同元数据键。 对 RpuOperation，键为 {opcode, source-operand-0, source-operand-1}；对 TransposeTile，键为 {height, anchor, vxpose-mode, …}。相等的键会落入同一个 hash bucket。
较晚的 op 已由 tracker 判定就绪。 XluOperationIsReady(tracker, op)（@0x126cd920）在该 op 的入边计数为零时返回 true — 其所有前驱 XLU op 都已被调度（列表调度就绪性）。
合并会保持关键路径成本有界 — 即 CyclesAddedByXluOperation DP 数组（cycles[]/cummax[]）。

XluControlOperation op 永不融合：$_2 visitor 分支（@0x2139b1c0）是 __noreturn 的 LogMessageFatal("unexpected XluOperation type", llo_xlu_graph_optimizer.cc:1750)。

两个融合键

variant（idx）	键结构（字节精确）	提取器
`RpuOperation`（1）	`RpuOperationMetadata {u16 opcode@0, LloValue* op0@8, LloValue* op1@0x10 (gated u8@0x18==1)}`	`GetRpuTransposeOperationKeyFrom` @ `0x126d8520`
`TransposeTile`（0）	`TransposeTileMetadata {i32 height@0, i64@8, u16@0x10, u8 vxpose_mode@0x12, u8@0x13}`	在 `$_0` @ `0x126dce40` 中内联

GetRpuTransposeOperationKeyFrom（@0x126d8520）读取 value = [[RpuOp+0x10]+0x10]，设置 opcode = WORD[value]，并填充两个操作数身份：

// RpuOperationMetadata GetRpuTransposeOperationKeyFrom(RpuOperation& op)   @0x126d8520
key.opcode = WORD[value];
if (key.opcode == 0x3a) {                  // kVectorRotate — single from-end operand
    key.op0 = operand_at(value, count-1);  // [value-0x10]=count; [value+0xb]&3 = operand-from-end mask
    key.op1 = 0; key.has1 = 0;             // [out+0x18] = 0
} else {
    key.op0 = operands[0];                 // first source LloValue*
    key.op1 = operands[1]; key.has1 = 1;   // two source operands
}
```text

hasher 确认了字段布局：`RpuOperationMetadata` hash（`@0x126e1140`）是 `{u16@0, i64@8, then i64@0x10 only if u8@0x18==1}` 的 crc32；`TransposeTileMetadata` hash（`@0x126e1640`）是 `{i32@0, i64@8, u16@0x10, u8@0x12 (xor 0x1 = vxpose bool), u8@0x13}` 的 crc32。

> **陷阱 —** `btree_set<long>` bucket 保存的是 op **索引**，不是 op 指针，并且节点容量为 256（`btree_set<long, less, alloc, 256>`）。直接用指针作为键的朴素重新实现也能工作，但就绪性门控会在遍历中触发并从 tracker 中*擦除*已调度 op（`RemoveScheduledXluOperation` @ `0x126ccfa0`）— 谓词是有状态的，因此对同一列表跑两遍并非幂等。

---

## AssignXlu — 贪心最小负载单元分配

### 目的

融合之后，每个幸存的（可合并）op 都会被放置到按代际的某个 XLU 单元上。`AssignXlu` 是一个贪心装箱器：它把每个 op 放到当前累计成本最小的 XLU 上，从而平衡每个单元的关键路径。单元选择会立即提交到指令字中，因此重排和最终发射都能看到它。

### 算法

`AssignXlu(Span<pair<variant*,variant*> const> pairs)`（`@0x126d3100`）只在 `xlu_count > 1` 时有意义：它 `CHECK` `xlu_count >= 2`，否则 `LogFatal`（优化器源中的 line 0xa03）。它通过 `[[optimizer][0]+0x168]` 到达 `Target`，并读取 `xlu_count = DWORD[Target+0x4b0]`。

```c
// LloXluGraphOptimizer::AssignXlu(Span<pair<variant*,variant*> const> pairs)   @0x126d3100
function AssignXlu(pairs):
    CHECK(xlu_count >= 2)                              // line 0xa03 LogFatal otherwise
    rec[xlu_count] = new(xlu_count << 5), memset 0     // 0x20 B each; [rec+0]=running cost
    for p in pairs:                                    // stride 0x10
        // min-cost XLU pick (unrolled x4 @0x126d320d + remainder @0x126d32a0)
        chosen = argmin over u in 0..xlu_count of rec[u].cost      // cmovl keeps min + index
        $_0(p.first,  chosen)                          // write unit index into backing instrs
        if p.second: $_0(p.second, chosen)
        rec[chosen].cost += CyclesAddedByXluOperation(rec[chosen].prev, p.first,
                                                       anchor_from, anchor_to, PreXlu_table)
        rec[chosen].prev = p.first                     // [rec+0x18] = new prev op

$_0 lambda（@0x126db0a0）把所选单元索引写入每个底层 LloInstruction 的单元选择器字段：

RpuOperation（idx 1）：记录 [op+0x20] = xlu，并在该 op 的两条指令（[op+0x10]、[op+0x18]）上写入字段。
TransposeTile（idx 0）：记录 [op+0x34] = xlu，并在读集合 InlinedVector（[op+0x00]，count [op+0x08]）和写集合（[op+0x18]，count [op+0x20]）的每个元素上写入字段。

该字段写入与 LLO 发射验证器 ValidateAndSetXluAndSourceBus 字节相同：

// unit selector (XLU or MXU instance) — AssignXlu $_0 and ValidateAndSet*…
WORD[instr+0xb] = ((xlu & 3) << 8) | (WORD[instr+0xb] & 0xF8FF) | 0x400;   // bits 8-9 + valid bit 10
```text

`AssignXlu` 是该字段的**调度侧生产者**；`ValidateAndSetXluAndSourceBus`（XLU ops）/ `ValidateAndSetMxuAndSourceBus`（matmul-push ops）是发射侧验证器，会以匹配的 `CHECK(xlu < xlu_count)` 范围检查重新断言它。`AssignXlu` 在 `Optimize` 中由 `optimizer+0x28 == 1` 门控。

---

## ReorderToShortenCriticalPath — 列表调度器

### 目的

在每个 op 都已分配到 XLU 后，`ReorderToShortenCriticalPath` 会重排可合并 pair 列表，使每个 XLU 的关键路径尽可能短。它是一个教科书式的延迟加权列表调度器：就绪 op 按最长边际成本优先调度，因此支配某个 XLU 路径的链会最早提交。

### 入口点

```text
Optimize @0x126cdb80
  └─ CrossXlu Create (tracker #2, reverse=1)         ; rebuilt on the unit-assigned graph
  └─ ReorderToShortenCriticalPath @0x126d3460  ── this pass
       ├─ $_1 COMMIT          @0x126d8b60   ; erase from pending set, advance clock, write output
       ├─ $_2 READY + CP-test @0x126d90e0   ; XluOperationIsReady + completion-clock compare
       ├─ $_3 MARGINAL-COST   @0x126d9240   ; CyclesAddedByXluOperation on the op's XLU
       ├─ $_4 GROUP-RECORD    @0x126d93a0   ; (from,to)-keyed combinable-group map
       └─ pop_heap @0x126e1b40 / emplace @0x126d8980  ; the per-XLU max-heap

数据结构

ReorderToShortenCriticalPath(vector<pair<variant*,variant*>>* pairs, CrossXluOperationsDataDependencyTracker* tracker)（@0x126d3460）为每个 XLU 单元分配一个 PerXluOperations 状态结构（stride 0x60，alloc = 3*(xlu_count<<5)）。字段布局记录在 XLU Reemit 成本中；本 pass 读取的偏移如下：

offset	字段	角色
`+0x00`	`btree_set<long, less, alloc, 256>`	按 XLU 的待处理 op 索引集合
`+0x38`	`i64`	剩余运行周期累加器（待处理 op 的 Σ cost）
`+0x50`	`variant*`	此 XLU 上最后调度的 op（下一个 `CyclesAdded` 的 `prev`）
`+0x58`	`i64`	按 XLU 的完成时间时钟（关键路径前沿）

此外还有每个 op 的 cost[] 和 anchor[] 数组、一个 FlatHashMap<pair<LloValue*,LloValue*>, btree_set<long,256>> 可合并分组 map、按 XLU 的 priority_queue<pair<long,long>, vector<…>, less<>> 候选最大堆，以及重排后的输出 vector（通过 __assign_with_size 写回到 *pairs）。

算法

// LloXluGraphOptimizer::ReorderToShortenCriticalPath(vector<pair*>* pairs, tracker)   @0x126d3460
function ReorderToShortenCriticalPath(pairs, tracker):
    if xlu_count == 0 or pairs.empty(): return       // short-out
    per_xlu[xlu_count] = PerXluOperations (stride 0x60), each btree EmptyNode + zeroed

    // PHASE A — per-op preprocessing
    for i in 0..N:
        xlu = assigned_xlu(op_i)                      // WORD[instr+0xb]: (>>8)&3 gated by &0x400
        cost[i] = CyclesAddedByXluOperation(per_xlu[xlu].prev, op_i, anc_from, anc_to, PreXlu_table)
        per_xlu[xlu][+0x38] += cost[i]                // running cycles
        anchor[i] = op_i.anchor; per_xlu[xlu].pending.insert(i); group_map[(from,to)].insert(i)

    // PHASE B — list-scheduling loop
    while candidates remain:
        idx = top of the per-XLU max-heap          // less<(cost,index)> → longest marginal cost first
        // pre-test: only attempt a reorder when it can shorten this XLU's remaining path
        if heap_top_cost < per_xlu[xlu][+0x38]:      // cmp @0x126d494b ; jl skip
            ...
        {ready, frontier} = $_2(idx):                // @0x126d90e0
            ready = XluOperationIsReady(tracker, op_a) &&
                    (op_b ? XluOperationIsReady(tracker, op_b) : true)   // in-edge==0, @0x126cd920
            if not ready: return {false, 0}
            cp_cost = $_3(op_a)                       // marginal cost on its XLU @0x126d9240
            frontier = (per_xlu[xlu][+0x58] + cp_cost >= finish[idx])    // setge — the CP test
        if ready:
            $_1(idx):                                 // COMMIT @0x126d8b60
                write {op_a, op_b} into the output vector
                per_xlu[xlu].pending.erase(idx)       // btree erase @0x126ba360
                advance per_xlu[xlu][+0x58] clock; set per_xlu[xlu][+0x50] = op
                pop_heap                              // @0x126e1b40
        else:
            cost = $_3(op);  $_4(op)                  // re-price + group-record @0x126d93a0
            heap.emplace({cost, idx})                 // @0x126d8980
    *pairs = reordered output                          // __assign_with_size
```text

> **注意 —** 堆是以 `{marginal_cost, op_index}` 为键的 `less<pair<long,long>>`（最大堆），因此会最先弹出**最高**边际成本的就绪 op — 即最长延迟优先启发式。平局由 pair 的第二个元素打破（结构上读作 op-index；它是按 op-index 升序而非另一个优先级这一点为 LOW）。`$_2` lambda 在控制 op variant（`control != nullptr`，line 2532）上的 `LogFatal` 确认控制 op 也永远不会被重排 — 与它们永远不可合并一致。

### 两个 Tracker

`Optimize` 会构建 `CrossXluOperationsDataDependencyTracker` **两次**：一次（`reverse=0`）在 `ComputeCombinablePairs`/`AssignXlu` 之前，一次（`reverse=1`）在重排之前，因此重排的就绪性是针对**合并后、单元分配后**的依赖图计算的。两个消费者共享 `XluOperationIsReady` 谓词（入边计数 == 0）。

---

## AssignSourceBus — VEX 源总线分配器

### 目的

在具备 VEX 源总线的代际（此构建中仅 Pufferfish v4）上，每个 XLU op 的操作数必须被路由到四个读端口 V0/V1/V2/V3 之一。`AssignSourceBus` 按拓扑顺序遍历依赖图并把每个 cross-lane op 绑定到一条总线；每当两个 op 会在同一总线上冲突时，就插入一条串行化边。

### 入口点

```text
Optimize @0x126cdb80
  └─ [gate optimizer+0x28==1] AssignSourceBus @0x126d70e0  ── this pass
       ├─ HasVexSourceBuses()  vtable[+0x408]   ; gate — Pufferfish-only true
       ├─ NodesInTopologicalOrder(false) @0x1442b8c0
       ├─ SourceBusesForXlu(i) vtable[+0x518]    ; {i, i+2} on Pufferfish
       ├─ LloOpcodeUsesSourceBus @0x10c0d420     ; the 29-opcode gate
       ├─ LloOpcodeUsesMxu       @0x10a433e0     ; MXU vs pure-XLU split
       ├─ $_0 critical-path depth @0x126db4e0    ; latency-weighted level
       ├─ $_1 greedy free-bus     @0x126db6c0    ; non-MXU XLU ops
       └─ $_2 explicit bus bind   @0x126dbb80    ; MXU-indexed + shared-bus edge

HasVexSourceBuses 门控

整个 pass 由 Target::HasVexSourceBuses() 门控 — vtable 槽位 +0x408（反编译中为 +1032）。按代际（来自 Target vtable 的字节精确结果）：

Target（gen）	`HasVexSourceBuses()`	源总线 pass
`JellyfishTarget`（v2/v3）	`false`（`xor eax,eax`）@ `0x1d4904a0`	no-op
`PufferfishTarget`（v4）	`true`（`mov al,1`）@ `0x1d494b40`	活跃
`ViperfishTarget`（v5p）	`false` @ `0x1d49ae40`	no-op
`GhostliteTarget`（v6e）	`false` @ `0x1d497d00`	no-op

因此在 libtpu 0.0.40 中，VEX 源总线分配只对 Pufferfish 执行。

总线池 — SourceBusesForXlu

活跃时，该 pass 先遍历 xlu_count 个 XLU 单元并累计每个单元的总线数量，以确定总线池大小：

// @0x126d7aa9 — bus-pool sizing
total_buses = 0
for xlu in 0 .. DWORD[Target+0x4b0]:                 // xlu_count
    pool = Target->SourceBusesForXlu(xlu)             // vtable[+0x518]
    total_buses += pool.count >> 1                    // count-tag >> 1
```text

`SourceBusesForXlu(int)` 是抽象的 — base/JF/VF target 上为 `LogFatal "not implemented"`；只有 `PufferfishTarget`（`@0x1d494f20`）有具体函数体，字节精确为：`[ret+0x00]=4`（size-tag ⇒ 2 条总线），`[ret+0x08]=i`，`[ret+0x0c]=i+2`。因此 **XLU 单元 *i* 拥有源总线 `{i, i+2}`**；对于典型的 2-XLU 配置，XLU 0 拥有 `{0, 2}`，XLU 1 拥有 `{1, 3}` — V0/V1/V2/V3 读端口配对为 `(V0,V2)` 和 `(V1,V3)`，是一个深度为 `2*xlu_count` 的池。

> **怪癖 —** `{i, i+2}` 端口对映射是 **Pufferfish 特定**的。`AssignSourceBus` 的*机制*是代际泛化的（它调用虚函数 `SourceBusesForXlu`），但此二进制中唯一活跃的具体实现是 Pufferfish 的。一个假想的未来代际如果报告 `HasVexSourceBuses() == true`，会提供不同的映射；该映射不在此构建中（对任何其他代际为 LOW）。

### 按节点总线绑定

对于每个 opcode 满足 `LloOpcodeUsesSourceBus` 的拓扑节点，该 pass 会按 `LloOpcodeUsesMxu` 分支：

```c
// @0x126d7e60.. per-node binding
for node in NodesInTopologicalOrder():
    if not HasVexSourceBuses(): continue
    op = WORD[value+0x10]
    if not LloOpcodeUsesSourceBus(op): continue        // 29-opcode gate
    if LloOpcodeUsesMxu(op):                            // matmul-push 0x8f..0x96
        mxu = (WORD[value+0xb] >> 8) & 3                // gated by &0x400 → | 0x1_0000_0000
        $_2(mxu)                                        // bind explicit MXU-indexed bus
    else:                                               // pure XLU op
        extract operands (op-0x8b dispatch)
        $_1()                                           // greedily bind next free bus
    node_to_bus_map[node] = bus                         // find_or_prepare_insert @0x126c7b80

LloOpcodeUsesSourceBus（@0x10c0d420）对正好 29 个 opcode 返回 true（确认为字面 case 集）：

text

{0x36, 0x3a, 0x3b}        permute / rotate / broadcast-lane
{0x8b, 0x8c}              set-permute-pattern / set-segment-pattern
{0x8f .. 0x96}            8 matmul-push ops (the MXU operand path, UsesMxu)
{0xa6, 0xa7}              transpose / transpose-binary
{0xf5 .. 0x101}           13 cross-lane reduce / index / segment-reduce ops
{0x155}                   transpose-clear
```text

相对于 21-op 的 `IsXluOp` 集，这是 `IsXluOp` 减去三个 EUP op `{0x14f, 0x150, 0x154}`（它们使用 XLU 边模型但不使用 VEX 源总线），加上三个 permute/rotate/broadcast op `{0x36, 0x3a, 0x3b}`，再加上 8 个 matmul-push op `{0x8f..0x96}`。matmul-push op 通过源总线把操作数路由*进入* MXU；其余 op 经过 XLU/RPU 读端口。

### 关键路径深度 — $_0

`$_0` lambda（`@0x126db4e0`）计算每个节点的延迟加权深度，用于确定总线绑定优先级。它通过 `LloDependencyGraphEdgeMap` 外部 chunk 形式（`&3 == 3` 的间接边形式，`RemoveChunk` @ `0x1443b460`）遍历节点的前驱边，读取每个前驱的深度（`[pred+0x10]`）以及打包在边 map entry 高位中的**边延迟**（`entry >> 33`，即 `sar entry, 0x21`），并设置：

```c
node.depth[+0x10] = max over preds of (pred.depth + edge_latency);

边延迟是写入图中的 PreXluAssignmentLatencyTable（ceil/xlu_count）值 — 因此深度使用的计价与其他所有内容相同，都是 XLU 边模型。

共享总线 Hazard — $_2 / $_1

$_2(int slot) lambda（@0x126dbb80）把 op 绑定到显式（MXU/XLU 索引）总线并插入结构 hazard。字节精确如下：

// AssignSourceBus::$_2(int slot)   @0x126dbb80
function $_2(slot):
    CHECK(slot < bus_slots.count)                  // BUG()/ud2 otherwise
    s = bus_slots[slot]                             // 16-byte: [s+0]=value, [s+8]=node
    if (s.node != 0):                               // slot already holds a prior op
        lat = LatencyTable.LatencyBetween(s.value, this_value)   // @0x1c89f820 (optimizer table)
        CHECK(lat > 0)                              // line 2753 LogFatal w/ both ToString'd ops
        LloDependencyGraph::UpdateEdge(prev_node, this_node, lat)  // @0x14428b00 — SERIALIZE
    $_0(this_node)                                  // recompute depths
    s.value = this_value; s.node = this_node        // record the new occupant
```text

`$_1()`（`@0x126db6c0`）是非 MXU XLU op 的贪心空闲总线分配器：它把节点推入 worklist，在 `FlatHashMap<LloDependencyGraphNode*, int>`（`find_or_prepare_insert_large`）中记录 node→bus 分配，并重新运行 `$_0`。两条路径都使用相同的共享总线边机制。

> **陷阱 —** 分配到**同一**源总线的两个 XLU op 会获得一条全新的延迟加权依赖边（`UpdateEdge`，权重 = `LatencyBetween`），在该 V-port 上串行化它们。若重新实现者把源总线视为纯寄存器重命名提示，就会低估这个 hazard：总线是一种结构资源，共享它会在关键路径中产生真实边。`CHECK(lat > 0)` 是硬性不变量 — 零延迟共享总线边被视为 bug，而不是免费融合。

---

## LLO 指令位字段

`AssignXlu`（单元）和 `AssignSourceBus`（总线）都会写入 `WORD[LloInstruction + 0xb]`；LLO 发射验证器 `ValidateAndSetXluAndSourceBus` / `ValidateAndSetMxuAndSourceBus` 会重新断言同一字段。字节精确如下：

```text
WORD[LloInstruction + 0xb] (16-bit; byte 0xb low, byte 0xc high):
  bit  8-9   : XLU/MXU UNIT INDEX   (2-bit, {0..3})         ← AssignXlu $_0 / ValidateAndSet*…
  bit  10    : UNIT-ASSIGNED valid flag (the +0x400)        ← set together with the index
  bit  11-12 : SOURCE-BUS INDEX     (2-bit, {0..3})         ← ValidateAndSet*…SourceBus (PF only)
  bit  13    : SOURCE-BUS-ASSIGNED valid flag (the +0x2000) ← set together with the bus index

// source bus (Pufferfish only) — the second 2-bit field
WORD[instr+0xb] = ((bus & 3) << 11) | (WORD[instr+0xb] & 0xC7FF) | 0x2000;  // bits 11-12 + valid bit 13
```text

源总线字段保存原始 2-bit 索引 `{0..3}` — 它**不是** SparseCore `VexSourcePortEncoding` proto enum（后者是不同 datapath 上的 8 值、3-bit 编码，由身份 `VregReadPort → encoding` map 产生）。`{i, i+2}` 的 `SourceBusesForXlu` 池索引的是这个 2-bit TensorCore 字段；V0..V3/X-Y 子端口 `VexSourcePortEncoding` 是 SparseCore EUP mux — 二者关注点不同。`ValidateAndSetMxuAndSourceBus` twin 为 matmul-push op 设置相同两个字段，其中 `source_bus = mxu_index`（上面的显式 MXU 索引总线，即 `$_2` 路径），并带有类似的 `CHECK(mxu < mxu_count)`。

---

## 示例 — 两个 `kVectorAddReduceF32`（0xf7），Pufferfish v4，xlu_count = 2

1. **合并。** `ComputeCombinablePairs` 用 `RpuOperationMetadata{0xf7, src0, src1}` 为两个 reduce 建键（`0xf7 ≠ 0x3a`，所以是两个源操作数）。如果第二个已由 tracker 判定就绪（`XluOperationIsReady` — 它的源 producer 已调度）且位于 `cummax` DP 预算内，它们就在 RPU bucket 中碰撞 → `push_back {&R_a, &R_b}`（可合并为一个 cross-lane reduce pass）。
2. **边成本。** `CyclesAddedByXluOperation` 通过 `PreXluAssignmentLatencyTable` 为 reduce-result 边计价。如果按代际的基础 reduce-edge 延迟为 `B`，XLU↔XLU 边成本为 `ceil(B / 2)` — 串行延迟的一半，因为两个 XLU 并行运行。
3. **AssignXlu。** `xlu_count == 2`（≥ 2 OK）。最小成本选择会把该 pair 放到 XLU 0（平局 → index 0）。`$_0` 把 `unit = 0 | valid` 写入两个指令字（`WORD[+0xb] |= (0<<8) + 0x400`，`R_a.[+0x20] = 0`）。`rec[0].cost = ceil(B/2)`；第三个 op 会落到 XLU 1（现在负载最小）→ 负载均衡。
4. **重排。** tracker 在单元分配后的图上重建（`reverse=1`）。`ReorderToShortenCriticalPath` 把 `R_a`/`R_b` 以 `$_3 = ceil(B/2)` 为键入队；当 `XluOperationIsReady(R_a)` 且完成时钟测试通过时，`$_1` 提交：从 `per_xlu[0]` pending 中擦除，推进 `[+0x58] += ceil(B/2)`，并把 `{R_a,R_b}` 追加到输出。最大堆先弹出成本最长的就绪 op，因此支配 XLU 路径的 reduce 链会最早调度。
5. **AssignSourceBus。** `HasVexSourceBuses == true`。`LloOpcodeUsesSourceBus(0xf7) == true`，且不是 `UsesMxu` → `$_1()` 从 `SourceBusesForXlu(0) = {0,2}` 中贪心绑定一条空闲总线给融合后的 op。如果两个 reduce 落在同一总线上，`$_2`/`$_1` 共享总线路径会插入 `UpdateEdge(R_a→R_b, LatencyBetween)`，把它们在该 V-port 上串行化；否则它们使用不相交的 V-port 并保持并行。2-bit 总线索引写入 `WORD[+0xb]` 的 bits 11-13。

对比 matmul-push（`0x90`）：`LloOpcodeUsesSourceBus(0x90) == true` **并且** `LloOpcodeUsesMxu(0x90) == true` → 从 `WORD[value+0xb]` 读取 MXU instance，并由 `$_2(mxu_index)` 绑定显式 MXU 索引源总线。

---

## 尚未钉死的内容

- `ComputeCombinablePairs` 中精确的 `cummax` DP 接受阈值（三角循环 `@0x126d2b30`）：结构上解码为按窗口累计的每 op 周期 cumulative-max，并输入 visitor，尚未分离为一个闭式 accept/reject 不等式。MEDIUM。
- 重排堆的平局打破组成：确认 `less<pair<long,long>>` 以 `{cost, index}` 为键，但等成本 op 是按 op-index 升序还是另一个第二字段优先级来打破，是结构性读取。LOW。
- Pufferfish 之外任何代际的 `SourceBusesForXlu`：base/JF/VF 都是 `LogFatal "not implemented"`。此构建中只有 Pufferfish 报告 `HasVexSourceBuses == true`，所以 `{i, i+2}` 是唯一活跃映射。对任何假想未来代际为 LOW。
- int-bus-index → `VexSourcePortEncoding` ordinal：`AssignSourceBus` 使用不透明 bus int `{0..3}`；proto enum 属于单独的 SparseCore datapath。TensorCore 2-bit 字段是这些 pass 写入的唯一字段。
- `PreXluAssignmentLatencyTable` delegate（`[+0x18]`）在完整优化器流水线中的来源：它是优化器先前的 `[optimizer+0x8]` 表（链式包装）；链中的第一张表读作"先前的 +0x8"，未追踪到其在 `Run` 中的构造。MEDIUM。

---

## 交叉引用

- [XLU Op 名册](../isa/xlu-op-roster.md) — opcode 目录，以及更高层次的完整五阶段流水线；`IsXluOp` / classifier 范围和 reemit/slot-fit 几何。
- [XLU Reemit 成本](xlu-reemit-cost.md) — 闭式 `CyclesAddedByXluOperation` 和本页 pass 消费的 `PerXluOperations` 结构。
- [XLU 冲突惩罚表](xlu-conflict-penalty.md) — 延迟模型计入的非 MXU hazard 成本。
- [Transpose-Reservation 延迟](xpose-reservation-latency.md) — transpose 融合键背后的 `XposeXLUReservationLatency` / `VxposeMode` 几何。
- [CycleTable 家族](cycletable-family.md) — 成本模型的吞吐半部分；与 `LatencyTable::Create` 相同的按注册表 `Create`、`Performance` grid framing。
- [ResultFifo 和 ArchRegister](../isa/resultfifo-archregister.md) — `ComputeXluOperations`，它发射此优化器消费的 `variant<TransposeTile, RpuOperation, XluControlOperation>` 列表。

XLU 合并与源总线分配 ​

摘要 ​

边权重模型 ​

目的 ​

基表 — LatencyTable::Create ​

ComputeCombinablePairs — 融合分析 ​

目的 ​

入口点 ​

融合谓词 ​

两个融合键 ​

数据结构 ​

算法 ​

HasVexSourceBuses 门控 ​

总线池 — SourceBusesForXlu ​

共享总线 Hazard — $_2 / $_1 ​