MXU 分配 Bin-Packer

地址适用于 libtpu-0.0.40-cp314 wheel 中的 libtpu.so（BuildID md5 89edbbe81c5b328a958fe628a9f2207d，781,691,048 字节，未剥离符号 -- nm -C 可解析下文每个符号）。.text/.rodata VMA == 文件偏移；.data.rel.ro VMA - 0x200000 == 文件偏移。decompile 的源码行字符串引用 platforms/xla/service/jellyfish/mxu_latency_balancing.cc。其他版本会不同。

摘要

AssignMxusForSequenceGroup 是决定每个 matmul sequence-group 运行在哪个物理 MXU quadrant 上的 pass。一个 jellyfish TensorCore 最多有四个物理 MXU 实例；一个 fused HLO 会产生许多 MxuSequence latch/matmul 链，它们必须分散到这四个 unit 上，避免某一个 unit 成为吞吐瓶颈。这个 pass 是一个贪心 min-makespan bin-packer：它按顺序遍历 sequence，用“添加该 sequence 会让该 unit 多付出多少 busy cycle”给每个候选 MXU 打分，把 sequence 分配到 resulting maximum-latency 最小的 unit，然后运行一个 rebalance 阶段，通过把工作从负载最高的 unit 上搬走进行 hill-climb，直到负载收敛到平衡目标。

熟悉的参考框架是 LLVM 的 MachineScheduler resource-aware list scheduler，但这里专门针对一个 functional unit，并作为放置 pass 而不是排序 pass 运行。list scheduler 会推进 issue cursor 并跟踪 ProcResource counter；而这个 pass 为每个物理 MXU 保留一个 MxuStat -- 一个运行中的 occupancy timeline 加上放在那里的 sequence 的有序 map -- 并用与 packetizer 测试新 op 是否适合 hazard slot 相同的 interval-extension 算术为每次放置定价。bin-packer 最小化的 cost 是 makespan：最忙 MXU 的 latency，它汇总了 MxuLatencyTable::GetLatencyBetween 和 XluConflictPenaltyTable 为相邻 op 之间定价的 structural stall。

该 pass 有两个模式，由一个环境 flag 选择。发布默认是 flat 模式：所有 sequence 是一个 group，一次性跨全部四个 MXU 平衡。可选开启的 latency-balanced 模式按 sequence 写入的 matrix-result-buffer (MRB) 地址对子 group 分组，构建一个 LloDependencyGraph，使 makespan 能计入 inter-sequence MRB-accumulate 顺序，然后独立平衡每个 MRB group。两个模式最终都会进入同一个 AssignMxusForSequenceGroupInternal bin-packer。

重新实现时，契约是：

public dispatcher AssignMxusForSequenceGroup：env-flag gate（MxuLatencyBalancingUseSequenceDependencies）、flat path（copy span -> 一次 Internal 调用），以及按 MRB key 的 linked_hash_map grouping path（每个 group 一次 Internal 调用）。
bin-packer AssignMxusForSequenceGroupInternal：包含 num_mxus 个 unit 的 vector<MxuStat>、贪心选择循环（PASS 1），以及迭代式 rebalance 循环（PASS 2）。
两个 cost function：MxuStat::LatchLatencyChangeAfterAdding（c + x - y2 interval-extension delta）和 MxuStat::LatencyChangeIfMoveTo（move-makespan delta）。
与非 MXU hazard model 的交互：packer 汇总的逐 sequence base latency 如何通过共享的 LatencyBetween edge model 折入 XluConflictPenaltyTable cross-lane stall。


Public dispatcher	`xla::jellyfish::AssignMxusForSequenceGroup` @ `0x10f753c0`
Bin-packer (Internal)	`xla::jellyfish::(anon)::AssignMxusForSequenceGroupInternal` @ `0x10f77ca0`
Env gate	`MxuLatencyBalancingUseSequenceDependencies` @ `0x1d6b9c80`（env 字段 `+0xbe8`，`AutoOr<bool>`，默认 OFF）
PASS-1 cost	`MxuStat::LatchLatencyChangeAfterAdding(int, long, long)` @ `0x10f7f3e0`
PASS-2 cost	`MxuStat::LatencyChangeIfMoveTo(int, MxuStat const&, long)` @ `0x10f7fb40`
Rebalance callback	`...Internal::$_1::operator()(long)` @ `0x10f7db60`
逐 seq base latency	`xla::jellyfish::CycleTableInstruction(LloInstruction*)` @ `0x1c89ca80`
MRB sub-group 大小	`xla::jellyfish::ExpectedMatresesPerMatmul(LloInstruction*)` @ `0x145005e0`
结果容器	`InlinedVector<MxuAssignment, 4>`（4 = 物理 MXU quadrant）
源文件	`platforms/xla/service/jellyfish/mxu_latency_balancing.cc`
置信度	CONFIRMED（字节锚定），除非某行另有说明

Public Dispatcher

AssignMxusForSequenceGroup(int num_mxus, Span<unique_ptr<MxuSequence>> sequences, CycleTable const&, optional<MapView<LloInstruction*, long>>) @ 0x10f753c0 是入口点。num_mxus 作为 arg1 从调用者传入（MxuAssigner::LatchLhs / AccumulateIntoMrb，后者会传递它并用 mxu_accumulation.cc:1812 的 "num_mxus must be non-negative." 错误校验 num_mxus >= 0）；它是逐 generation 的物理 MXU-quadrant 数。（UNVERIFIED：具体 Target MXU-count getter vtable slot 及其 jellyfish 值四，在此调用链中没有钉到字节偏移 -- num_mxus 作为已经解析好的 int 进入 AssignMxusForSequenceGroup。）dispatcher 先执行两个 CHECK，然后按 env flag 分支：

double AssignMxusForSequenceGroup(int num_mxus, MxuSequence** seqs, size_t n, ...):  // sub_10F753C0
    CHECK(n > 0);                              // mxu_sequences.size() > 0      (line 987)
    CHECK(seqs[0]->matmuls.size() > 0);        // front()->matmuls.size() > 0   (line 988)
    if (!MxuLatencyBalancingUseSequenceDependencies(env)):     // DEFAULT path, flag OFF
        // flatten the Span<unique_ptr<MxuSequence>> into a mutable MxuSequence*[]
        MxuSequence** flat = new MxuSequence*[n];
        for (i = 0; i < n; ++i) flat[i] = seqs[i].get();
        AssignMxusForSequenceGroupInternal(num_mxus, flat, n, cycle_table, ...);   // ONE flat group
        free(flat);
    else:                                       // latency-balanced path, flag ON
        … build per-MRB-address sub-groups (below) …
```text

> **NOTE --** 函数的 IDA 返回类型是 `double`，makespan 跟踪也使用 XMM scratch，但调用者消费的结果是提交到每个 `MxuSequence` 中的逐 sequence MXU id（通过 `set_mrb_address_unrestricted` 和 `MxuStat::SequenceInfo` map），不是返回寄存器。`double` 是共享 XMM spill slot 导致的 decompiler artifact；该 pass 本质上是带副作用的 `void`。

### Env gate

`MxuLatencyBalancingUseSequenceDependencies` @ `0x1d6b9c80` 读取 `TpuCompilationEnvironment + 0xbe8`（`+3048`）处的 `AutoOr<bool>`，当每个 compilation 字段为 null 时回落到全局默认 proto，并用 `AutoOr<bool>::FromProtoOrDie` 解析：

```c
bool MxuLatencyBalancingUseSequenceDependencies(env):           // sub_1D6B9C80
    p = *(AutoProto**)(env + 3048);
    if (!p) p = &AutoProto_globals_;            // fall back to default proto
    v = AutoOr<bool>::FromProtoOrDie(p);
    return (~v & 0x101) == 0;                    // true only when both AUTO+VALUE bits agree

(~v & 0x101) == 0 测试是标准 AutoOr “显式 true”惯用法 -- 该 flag 是 AUTO 默认的 tri-state，在 v0.0.40 上解析为 OFF（见 TpuCompilationEnvironment 和 Environment Variables）。所以发布路径是 flat single-group bin-pack；MRB sub-grouping 是 opt-in。

Flat path -- 一个 group

当 flag 为 OFF 时，dispatcher 把 Span<unique_ptr<MxuSequence>> 复制到一个堆分配的 MxuSequence*[]（decompile 中表现为 growing-vector copy，operator new / memcpy / free），对整个列表调用一次 bin-packer，然后释放临时数组。每个 sequence 都与每个 MXU 竞争；packer 会把它们作为整体同时平衡到四个 unit 上。

Latency-balanced path -- 逐 MRB sub-group

当 flag 为 ON 时，dispatcher 按 sequence 写入的 matrix-result-buffer address 分组，使累加到同一 MRB chunk 的 sequence 一起平衡（并最终 co-locate 到一个 MXU 上，以保持它们的 accumulate 顺序）。分组是一个 absl::linked_hash_map<LloInstruction*, linked_hash_set<MxuSequence*>>，通过 lazy_emplace 构建，key 是 LloInstruction::mrb_address()：

// balanced path (flag ON)
linked_hash_map<LloInstruction*, ...> groups;
mrb = 0;
for (seq : sequences):
    for (matmul : seq->matmuls):
        addr = matmul->mrb_address();
        groups.lazy_emplace(addr);                       // sub_10F755E0
        matmul->set_mrb_address_unrestricted(mrb);
        // size the MRB chunk this matmul consumes:
        k = LloInstructionPushesToResultFifo(matmul);
        if (num_result_fifos() > 0):
            mpm = matreses_per_matmul();                 // vtable +0x5e0
            k = mpm * ceil_div(k, mpm);                  // round up to a full matres group
        mrb += k;
    … for each matres of the seq, re-key by mrb_address and bump mrb by ExpectedMatresesPerMatmul …
// then, per MRB-address group:
AssignMxusForSequenceGroupInternal(num_mxus, group_seqs, n, cycle_table, dep_view);
```text

该路径还会构造一个 `LloDependencyGraph`（在 region 的 flattened LLO 上调用 `LloDependencyGraph::Create`，每个 non-trivial op 调 `AddNode`）和一个 `LatencyTable`，使逐 group 平衡能为 inter-sequence dependency edge 定价；`MapView<LloInstruction*, long>` optional argument 把该 dependency-cycle view 传入 bin-packer。`ExpectedMatresesPerMatmul` @ `0x145005e0` getter（matmul data format + `Target[+0x5f8]` matreses-per-matmul）为每个 MRB sub-group 定大小，而 `CHECK(data->sequence == incoming_data->sequence)`（"vdwg blocking two sequences, which is not expected"，`mxu_latency_balancing.cc:550`）守卫 `dwg`（double-weight-gate）cross-sequence aliasing。

> **GOTCHA --** 不同 MRB-address group 会**独立**平衡，各自调用一次 `Internal`。两个处在*不同* MRB group 的 sequence 即使相对 MXU 1 会过度订阅 MXU 0，也可能都落在 MXU 0 上，因为没有一次单独的 balance 会同时看到两个 group。flat path 没有这个盲点 -- 这也是它成为默认路径的部分原因。选择 ON path 的重新实现必须接受 group-local optimality，而不是 global optimality。

---

## Bin-Packer -- `AssignMxusForSequenceGroupInternal`

`AssignMxusForSequenceGroupInternal(int num_mxus, Span<MxuSequence*>, CycleTable const&, optional<MapView<...>>)` @ `0x10f77ca0`（anonymous namespace）是核心。两个 dispatcher 路径都汇入这里。

### 状态 -- `vector<MxuStat>`

packer 分配一个含 `num_mxus` 个 entry 的 `vector<MxuStat>`。每个 `MxuStat`（decompile 在 select loop 中显示每 entry 为 40 字节 stride，即 `5` 个 qword）跟踪两件事：

- 一个**运行中的逐 MXU latency**（该 unit 的累计 makespan -- select loop 在 entry 开头读取、rebalance loop 会修改的 `long`），以及
- 一个有序的 **`btree_map<int, MxuStat::SequenceInfo>`**，记录放在该 MXU 上的 sequence，以 latch/sequence index 为 key（贯穿 cost function 和 merge/rebalance node ops 出现的 `absl::container_internal::btree<map_params_impl<int, MxuStat::SequenceInfo>>`）。

`+0xb` "valid" byte 和 `+0xa` "node count" byte 在 cost function 中 gate btree-node walk。最终 placement 会 materialize 为一个 `InlinedVector<MxuAssignment, 4>` -- inline capacity **4** 是 bake 进类型的物理 MXU-quadrant 数（`EmplaceBackSlow` 实例化中的 `...MxuAssignment, 4ul, ...`），与 `CollectAndTransformSequencesPerMxu` 使用的 `std::array<MxuState, 4>` 匹配。

> **NOTE --** `MxuStat` 字段角色（哪个 `long` 是 running latency、哪个是 accumulated busy interval、确切的 `SequenceInfo` body）是从两个 cost function 和 btree node 算术的访问模式中 FUNCTIONALLY 重建的，而不是来自源码 layout。下面的 cost 算术逐字节精确；字段命名是 INFERRED。（置信度：算术 HIGH，字段标签 INFERRED。）

### PASS 1 -- 贪心分配

packer 按顺序遍历 sequence。逐 sequence base cost 是 [CycleTable](../cost/cycletable-family.md) instruction latency `CycleTableInstruction(seq)` @ `0x1c89ca80`。对每个 sequence，它给每个 MXU 打分，并保留产生最小 resulting makespan 的那个。select loop（`@0x10f784d0` 区域，decompile 行约 929-954）逐字节精确：

```c
// PASS 1: for each MxuSequence S (dependency order), base = CycleTableInstruction(S)
best_max  = INT64_MAX;        // v78 — running minimum of the candidate makespans
best_mxu  = -1;               // v76/v84 — chosen MXU index
found     = 0;               // v75  — set when a strictly-better MXU is seen
for (idx = 0; idx < num_mxus; ++idx):
    delta = mxus[idx].LatchLatencyChangeAfterAdding(idx, S.latch_ptr, S.latch_latency, base);  // sub_10F7F3E0
    cand  = running_latency_base(idx) + delta + mxus[idx].head_latency;   // v82 + *(entry-3)
    if (best_max <= cand) best_mxu = idx;        // cmovle — tie keeps the lower idx
    if (best_max >  cand) found = 1;             // a strictly smaller candidate exists
    if (best_max >= cand) best_max = cand;       // cmovge — track the minimum makespan
assign S → best_mxu;
mxus[best_mxu].insert(S);     // SequenceInfo into the btree, bump running latency

关键是候选 cand 是把 S 加到 MXU idx 后的 makespan：该 unit 当前 running latency 加上 marginal busy-cycle increase delta。picker 最小化它，因此 sequence 会落到增长最少的 unit 上 -- 这是教科书式的贪心 min-makespan placement（LPT/list-scheduling 变体）。cmovle/cmovge 对同时跟踪 minimum 和 chosen index；平局保留第一个（低 index）MXU。

PASS 1 cost -- `LatchLatencyChangeAfterAdding`

MxuStat::LatchLatencyChangeAfterAdding(int idx, long latch_ptr, int latch_latency, long base) @ 0x10f7f3e0 返回把新 latch/matmul 插入此 MXU time-sorted sequence map 时的 marginal busy-cycle increase。它在 btree<int, SequenceInfo> 中定位插入邻居（对 18-DWORD/72-byte node stride 的 a3 < *v7 walk），读取邻居的 end/free/busy timestamp，并计算一个 clamp 后的 interval extension。尾部（decompile 行 167-177）逐字节精确：

// this = MxuStat*; a2 = latch_ptr (u8*); a3 = new_start key (int); a4 = latch_latency; a5 = start
long MxuStat::LatchLatencyChangeAfterAdding(u8* a2, int a3, long a4, long a5):  // sub_10F7F3E0
    // locate the sorted-by-time neighbour of key `a3` in sequences_ (btree walk);
    // CHECK(latch_latency == prev_it->second.latch_latency)   if exact key match  (line 236)
    //   free  = neighbour slot +10  (v15)
    //   busy  = neighbour slot  +9  (v10)
    c  = max(0, a4  - free);             // a4 − v15, clamp at 0   → v21
    x  = max(0, busy - a5);              // v10 − a5, clamp at 0   → v22
    y2 = max(0, busy - free);            // v10 − v15, clamp at 0  → v23
    return c + x - y2;                   // interval extension
```text

`c + x - y2` 是把新 op 接入其 slot 时 MXU occupied interval 增长的额外 cycle 数：`c` 是新 op 超过先前 free point 的距离，`x` 是 next-busy interval 与新 start 的重叠，`-y2` 移除已经计入的 interval。这就是贪心 picker 加到该 unit running latency 上形成 `cand` 的 increase-in-makespan-delta。

### PASS 2 -- 迭代式 Rebalance

贪心 pass 之后，一个 outer loop（decompile 中 `while(1)` @ line 1133）向平衡负载 hill-climb。每次迭代：

1. 计算 **balance target** `ceil(total_latency / num_mxus)`（行 1136-1160），
2. 扫描所有 `num_mxus` unit，找出**负载最低**（`min`）和**负载最高**（`max`）的 MXU（行 1174-1196），
3. 如果负载最高的 unit 已经达到 target，则**停止**（`LABEL_378`，行 1203），
4. 否则选择一个 sequence 从 max unit 搬到 min unit，给该 move 打分，并在它降低 makespan 时提交。

move score 使用 `MxuStat::LatencyChangeIfMoveTo`；commit 会修改两个 unit 的 running latency（decompile 行 1530-1531：`*max_mxu -= LatencyChangeIfMoveTo(...)` 然后 `*min_mxu += delta`），并在两个 btree 中重新 key 被移动的 sequence。verbosity >=2 的 VLOG 会跟踪每次 commit：

```text
mxu_latency_balancing.cc:686   "max mxu latency: <N> on mxu<M>"
mxu_latency_balancing.cc:758   "DECISION: moving <N> matmuls on sequence <S> from <A> to <B>"

NOTE -- PASS 2 是迭代式 rebalance，而不是单次 swap pass。 它是一个每轮重新计算 min/max MXU 和 ceil(total/num_mxus) target 的 outer loop，直到负载最高的 unit 达到 balance target（LABEL_378 exit）为止。重新实现不能把它压成一次 swap。（置信度：CONFIRMED。）

PASS 2 cost -- `LatencyChangeIfMoveTo`

MxuStat::LatencyChangeIfMoveTo(int seq_key, MxuStat const& src, long n_matmuls) @ 0x10f7fb40 返回把一个 sequence 移到 this（target）MXU 的 makespan delta。它在 target 的 sequences_ btree 中定位该 sequence（CHECK(it != sequences_.end())，mxu_latency_balancing.cc:267），通过 vtable call（*(_QWORD*)(reg+16)，CycleTable instruction lookup，line 218）汇总被移动 matmul 的逐 instruction CycleTable latency 来重新定价，然后把它折入与 PASS 1 相同的 clamp interval-extension 算术，最后在 source unit 上调用 LatchLatencyChangeAfterAdding（line 254）以计入被腾出的 slot。双分支尾部（行 232-253）：

long LatencyChangeIfMoveTo(int seq_key, MxuStat const& target, long n):   // sub_10F7FB40
    // gather the moved matmuls' CycleTable latencies → sum `v29`
    // free=v45, busy=v46, prev_free=v48, next_busy_after=v47 from the btree neighbours
    g = max(0, next_busy_after - free);                  // v35
    if (sum == free):                                    // v29 == v45
        a = max(0, busy - prev_free);                    // v37
        b = max(0, next_busy_after - prev_free);         // v38
        delta = free + g + a - b;                        // v39
    else:
        delta = (sum + g) - max(0, sum + next_busy_after - free);   // v40 − v41
    LatchLatencyChangeAfterAdding(target.head, target.head_ptr, seq_key, busy, sum);  // re-price source
    return delta;
```text

`max(0, ...)` clamp 与 PASS 1 的 `c + x - y2` 形状呼应；逐 matmul 重新汇总让一个*多 matmul* sequence 能作为整体移动，并依据 destination 的 timeline 重新定价，而不是简单平移。

---

## Bin-Packer 产生和消费什么

输出是每个 `MxuSequence` 一个物理 MXU id，记录在 `MxuStat::SequenceInfo` btree 中，并提交到 sequence（balanced path 上的 `set_mrb_address_unrestricted` 写入；flat path 上的 `MxuAssignment` inlined-vector）。该 id 是下游 [MRB Chain Allocator](mrb-chain-allocator.md) 和 [MRB FIFO / MSR Placement](mrb-fifo-msr-placement.md) 的输入，它们把逐 MXU sequence list 转换成具体 matrix-result-buffer chunk 和 MSR latch address；随后 [LLO Bundle Packing](llo-bundle-packing.md) pass 调度 latch/matpush/matres op，其 ordering 依赖该 placement，而 [Latch Assignment / Overrun](latch-assignment-overrun.md) 会解决 placement 隐含的逐 MXU latch slot conflict。

packer 汇总的 latency -- 逐 sequence `CycleTableInstruction` base，以及 ON path 上来自 `MapView` 的 dependency-edge weight -- 由共享的 `LatencyBetween` edge model 产生。该 model 是三路分发：true-dependency edge 收取 base op latency；MXU∧MXU edge 收取 [`MxuLatencyTable::GetLatencyBetween`](../cost/mxu-latency-overview.md) reservation recurrence；非 MXU cross-lane edge 收取 [`XluConflictPenaltyTable`](../cost/xlu-conflict-penalty.md) structural hazard。

### XLU conflict penalty 如何与 placement 交互

bin-packer 不直接读取 `XluConflictPenaltyTable`。交互是**间接但真实的**：当两个 cross-lane（reduce / transpose / permute）op 在**同一个 MXU 实例**上背靠背 issue 且没有 true data dependency 时，`XluConflictPenaltyTable` 会在 `LatencyBetweenInternal` 中把 cross-lane FIFO-drain stall 定价为一个 `MAX`-reduced edge latency。该 stall 会抬高 packer 汇总的逐 sequence latency，而且 -- 关键的是 -- penalty 是**逐 MXU-instance**的（表的第三个索引是 `mxu_id & 3`，value reader 会 `CHECK` 两个 op 在同一个 MXU 上）。因此 packer 选择的 placement 会决定*两个有冲突的 cross-lane op 是否真的共享一个 MXU*：

- 如果 packer 把两个 XLU-conflicting sequence 放在**同一个** MXU 上，它们的 `LatencyBetween` edge 会携带完整 `XluConflictPenaltyTable` stall（例如在 Viperfish 上，`kTransposeB32 -> kReduceB32` conflict 最高可达 105 cycles -- 一次完整 XLU drain），抬高该 unit 的 makespan。
- 如果把它们分散到**不同** MXU 上，same-MXU `CHECK` 会短路 -- 此模型中没有 cross-instance XLU conflict -- 两个 sequence 都不支付该 penalty。

因此 min-makespan 目标会隐式地*避免 co-locate XLU-conflicting sequence*：把它们放在一起会通过抬高的 `LatencyBetween` weight 提高 candidate makespan，所以贪心 picker 和 rebalance pass 都倾向于分开它们。这与 MXU reservation matrix 对 matmul-on-matmul structural hazard 的作用相同 -- bin-packer 通过汇总这些表定价出的 latency 来尊重两个 hazard table，而不是自己查询它们。

> **NOTE --** bin-packer 对 XLU（以及 MXU）hazard table 的感知程度取决于传给它的 latency view。在 **flat**（默认）路径上，逐 sequence cost 是裸的 `CycleTableInstruction` base -- inter-sequence `LatencyBetween` edge（包括 XLU conflict）**不会**汇总进 placement，因为 flat path 不传 dependency `MapView`。只有 **ON**（MRB-grouped）路径会构建 `LloDependencyGraph`，其 edge 把 `XluConflictPenaltyTable` / `MxuLatencyTable` stall 带入 makespan。因此上面描述的 hazard-aware placement 是 ON-path 行为；默认路径按原始逐 sequence latency 平衡，并依赖下游 bundle packer 吸收剩余 conflict。（置信度：CONFIRMED -- flat path 的单次 `Internal` 调用传入空 optional `MapView`。）

---

## Worked Example

六个独立 bf16 matmul sequence，四个 MXU，每个 sequence base 约 212 cycles（来自 [per-opcode cycle constants](../cost/per-opcode-cycle-constants.md) 的逐 opcode matmul latency）。

**PASS 1（贪心）。** Sequence 一次放置一个。前四个进入 MXU 0-3（每个空 unit 都以 `cand = 212` 平局；平局保留最低 index，但随后每个空 unit 都严格更小，所以它们填充 0,1,2,3）。第五个在四个 unit 上的得分都是 `cand ≈ 2*212 = 424`，落到 MXU 0（第一个 minimum）。第六个落到 MXU 1。最终负载：`{2, 2, 1, 1}` sequence -> 两个已加载 unit 上的 makespan 约 424 cycles。

**PASS 2（rebalance）。** balance target 是 `ceil(6*212 / 4) = 318`。负载最高的 unit（MXU 0 为 424）超过它，但把它的两个 sequence 之一移动到一个只有一个 sequence 的 unit（212 -> 424）并不会降低 *max*（只是交换哪个 unit 是 424），所以 `LatencyChangeIfMoveTo` 报告没有改进，循环到达 `LABEL_378` “already at target / no improving move” exit。最终 placement 为 `{2, 2, 1, 1}`。

**XLU-conflict variant。** 假设六个 sequence 中有两个各自以 transpose-B32 op 结束，并喂给一个 cross-lane reduce-B32 op（一个 `kTransposeB32 -> kReduceB32` XLU conflict）。在 **ON** path 上，它们之间的 `LloDependencyGraph` edge 携带 `XluConflictPenaltyTable` Viperfish penalty（取决于 MXU 实例为 88-105 cycles）。如果 packer 把二者都放到 MXU 0，该 unit 的 makespan 会跳高约 100 cycles；转而评分会把它们放到不同 MXU，在那里 same-MXU `CHECK` 短路，二者都不支付 stall。min-makespan 目标会自动把它们分开。

---

## 交叉引用

- [MxuSequence / SequenceInfo](mxu-sequence-struct.md) -- bin-packer 放置的 `MxuSequence` 记录（latch + matmuls + matreses），以及 balanced path 上提交所选 placement 的 `set_mrb_address_unrestricted` 写入。
- [MRB Chain Allocator](mrb-chain-allocator.md) -- 下一个 pass：使用本 pass 分配的 MXU id，把逐 MXU sequence list 转换成 matrix-result-buffer accumulation chain。
- [MRB FIFO / MSR Placement](mrb-fifo-msr-placement.md) -- `MxuAssigner::LatchLhs` / `AccumulateIntoMrb`，从 `Target` 解析 `num_mxus` 并把 assignment 消费为具体 FIFO/MSR address 的调用者。
- [LLO Bundle Packing](llo-bundle-packing.md) -- forward bundle scheduler，其 latch ordering 依赖此 placement。
- [Latch Assignment / Overrun](latch-assignment-overrun.md) -- assignment 下游的逐 MXU latch-slot conflict resolution。
- [XLU Conflict-Penalty Table](../cost/xlu-conflict-penalty.md) -- 逐 `(XluInstrType, XluInstrType, vxpose)` cross-lane structural-hazard matrix，其 stall 会抬高此 pass 最小化的 makespan；这是 placement 隐式尊重的非 MXU hazard。
- [MXU Latency Overview](../cost/mxu-latency-overview.md) -- `MxuLatencyTable::GetLatencyBetween`，为 packer 汇总的 matmul push 之间 structural stall 定价的 MXU-on-MXU reservation recurrence。
- [Transpose-Reservation Latency](../cost/xpose-reservation-latency.md) -- `XposeXLUReservationLatency`，XLU conflict reader 可以路由到的动态 height/width transpose-reservation 路径。
- [CycleTable Family](../cost/cycletable-family.md) -- `CycleTableInstruction`，bin-packer 汇总的逐 sequence base latency。
- [MXU Slot](../isa/slot-mxu.md) -- 构成 `MxuSequence` 的 latch / matpush / matmul / matres instruction family。
- [MXU Op Hold-Issues Stall](../cost/mxu-opholdissues-stall.md) -- 逐 MXU reservation occupancy 如何被 issue-stall 逻辑消费。
- [TPU Scheduling Pipeline](overview.md) -- 此 MXU/MRB placement pass 位于 HLO latency-hiding scheduler 和 LLO bundle packer 之间的位置。
- [TpuCompilationEnvironment](../config/tpu-compilation-environment.md) · [Environment Variables](../config/env-vars.md) -- gate flat 与 MRB-grouped balancing 的 `MxuLatencyBalancing` env 字段（`+0xbe8`）。

MXU 分配 Bin-Packer ​

摘要 ​

Public Dispatcher ​

Flat path -- 一个 group ​

Latency-balanced path -- 逐 MRB sub-group ​

PASS 1 cost -- LatchLatencyChangeAfterAdding ​

PASS 2 cost -- LatencyChangeIfMoveTo ​