CreateRoutingSchedule
本页所有地址均适用于
libtpu-0.0.40-cp314wheel 中的libtpu.so（构建libtpu_lts_20260413_b_RC00，build-id89edbbe81c5b328a958fe628a9f2207d）。该镜像未剥离符号；反混淆后的符号名按原文逐字引用。.textVMA 等于文件偏移。其他版本会有所不同。
摘要
CreateRoutingSchedule 是 net_router collective emitter 内部的编译期跳数分配求解器。它的输入是一个扁平的 net_router::Transfer 记录列表，每条记录都是 {src_core, src_index, dst_core, dst_index} 四元组，表示某个 collective（AllGather、AllToAll、CollectivePermute）需要通过芯片间互连（ICI）实现的一次逻辑（源核心 → 目标核心）数据移动。它的输出是一个 Schedule：按步骤、按目标、按方向组织的 DMA Action 网格，后续 pass（CreateRoutingScheduleLiteral）会把它序列化为运行时重放的 Type-5 route literal。本页记录该转换中把生成路径变成路由调度的部分：跳数分配循环、每一跳的源/目标端点与缓冲区移交，以及为每一跳的地址种类打标签的 PointerType 枚举。
理解这个求解器，最好从它相对朴素环形遍历的差异入手。它不会按顺序为每个 transfer 发出一跳。相反，它在芯片坐标的 2-D torus 上运行一个由优先队列驱动的贪心维度序最短环形遍历：对每个 transfer，它计算能缩短到目标 torus 距离的候选罗盘方向，将 transfer 推入一个以剩余环距离为键的二叉堆，然后反复弹出最高优先级的 transfer，将其推进一跳，再重新推入，直到它到达目标。每一跳都会变成一个 Action，安装到调度中的 {destination-XY, step, direction} 单元。关键在于，这个遍历以固定延迟因子 3 进行软件流水化：某一跳在步骤 S 写入的缓冲区只能在步骤 S+3 读取，因此多跳路径会被有意分散到多个步骤，而不是紧密打包；同时会跟踪飞行中的 DMA，以串行化同一源块的复用。
每一跳的端点都用 net_router::PointerType 标记，这是一个 2-bit 枚举，恰好有三个有效值：kInput=0、kOutput=1、kAlloc=2。每个多跳中继 Action 都通过本地 kAlloc scratch 暂存；只有 collective 的终端端点会携带 kInput/kOutput。每个指针的地址在运行时由 RoutingCodeEmitter::GetDataPointerAddress 具体化；它会把类型边界检查到 [0,3)，并把 kAlloc 路由到本地 scratch 分配器，同时把 kInput/kOutput 延交给调用方提供的地址回调。
对重新实现而言，契约是：
Transfer和Schedule记录布局 — 16 字节 transfer 四元组、每目标的IterationInfo节点、SchedulingQueueKey堆元素，以及placement[transfer]调度记录。- 跳数分配循环 — 候选方向生成（沿每个 torus 轴选择最短绕行）、剩余距离最长优先的二叉堆、每方向 ±1 的 torus 步进，以及驱动流水线的三个延迟回调。
PointerType枚举 — 它的三个值、[0,3)运行时边界、'ioa'字符标签，以及GetDataPointerAddress如何把每种类型解析为地址。
| 入口点 | CreateRoutingSchedule(tpu::TpuTopology const&, absl::Span<Transfer const>) @ 0x1381c6a0 |
| TU（静默） | platforms/xla/service/jellyfish/lowering/net_router_emitter.cc（路径字符串 @ 0x8760f44） |
| 堆 push | std::__sift_up<_ClassicAlgPolicy, …$_0…, SchedulingQueueKey*> @ 0x13825f60（3 个调用点） |
| 流水线因子 | kPipelineFactor = 3（在 LogAndValidatePaths @ 0x13823dc0 中验证） |
| 方向枚举 | {N=0 (+Y), W=1 (-X), S=2 (-Y), E=3 (+X)} — 4 个罗盘端口 |
| PointerType 枚举 | {kInput=0 'i', kOutput=1 'o', kAlloc=2 'a'} — 2-bit，有效 [0,3) |
| 指针地址 | RoutingCodeEmitter::GetDataPointerAddress @ 0x13828220 |
| 输出消费者 | CreateRoutingScheduleLiteral @ 0x13822400 → Type-5 route literal |
| 证据等级 | 重新实现级 / 经 IDA 反编译 + 符号逐字节确认 |
Transfer 输入
用途
Transfer 是求解器调度的原子单元：把一个缓冲区槽位从源核心逻辑移动到目标核心的一次移动。各 collective 的 transfer 构建器（AllGather、AllToAll、CollectivePermute）会从 collective 的 replica-group / source_target_pairs 关系生成 vector<Transfer>；CreateRoutingSchedule 消费该 span，并且不关心它由哪个 collective 生成。Transfer 的生成，也就是 replica group 如何变成 transfer 集合，由 net-router pipeline 以及路径生成页面（get-static-path、randomized-toroidal-wildfirst）负责；本页从 Transfer 列表已经构建完成的位置开始。
布局
Transfer (16 bytes)
+0x00 int src_core physical core id of the source
+0x04 int src_index buffer / slot ordinal within the source
+0x08 int dst_core physical core id of the destination
+0x0c int dst_index buffer / slot ordinal within the destination
```text
入口循环读取 `Transfer+0x08`（`dst_core`）并将其解析为芯片坐标：
```c
function CreateRoutingSchedule(topology, transfers): // 0x1381c6a0
RET_CHECK !transfers.empty() // str "!transfers.empty()" @0x1381c70a (line ~702)
X = topology.ChipBounds.X // movslq topology+0x58
Y = topology.ChipBounds.Y // movslq topology+0x5c
x_wrap = topology+0xa0 & 1 // per-axis torus-wrap flag (X)
y_wrap = (topology+0xa2 << 16) & 0x100 // per-axis torus-wrap flag (Y)
for each transfer in transfers:
loc = topology.CoreForId(0, transfer.dst_core) // 0x1381c7aa
(dx, dy) = loc.chip_coordinates() // 0x1381c7b5 — destination XY
// group destination XYs into a std::map<XY, IterationInfo> scoreboard …注意 — 求解器工作在芯片坐标中，而不是 core id 中。各 collective 构建器会把物理 core id 写入
Transfer；CoreForId+chip_coordinates是通向环形遍历所操作的 2-D torus 的桥梁。反编译在两个位置（第 742–744 行和第 957–958 行）确认了CoreForId/chip_coordinates这一对调用。
函数映射
| 函数 | VMA | 作用 |
|---|---|---|
CreateRoutingSchedule | 0x1381c6a0 | 跳数分配求解器入口（约 0x5c00 字节） |
TpuTopology::CoreForId | —（调用于 0x1381c7aa） | core id → TpuCoreLocation |
TpuCoreLocation::chip_coordinates | —（调用于 0x1381c7b5） | location → torus XY |
每目标记分板
用途
开始遍历之前，求解器按目标 XY 将所有 transfer 分组到一个 std::map<XY, IterationInfo>。map 键是目标坐标；值收集所有朝向该坐标的 transfer（iteration 标签）。这个记分板是贯穿下面三个延迟回调的每步骤参数，也是堆比较器在计算剩余距离时索引的对象。
布局
net_util::XY (8 bytes) IterationInfo (0x40-byte node; new $0x40 @0x1381c952)
+0x00 int x +0x20 XY key {x@0x20, y@0x24}
+0x04 int y +0x28 InlinedVector<int,1> per-destination transfer/iteration tags
(SOO size field read/+=2 @0x1381c9a8/0x1381c9da)
```text
该 map 是红黑树；反编译显示 `__tree_balance_after_insert` @ `0x1381c99c` 以 `{x@0, y@4}` 对为键。`InlinedVector<int,1>` 使用小对象优化：单个标签内联存储，更多标签会溢出到堆上。
---
## 跳数分配循环
这是求解器的核心。它有三个阶段：候选方向生成、优先队列贪心调度，以及每方向 torus 步进。三者都在 `CreateRoutingSchedule` 反编译中逐字节确认。
### Direction 枚举
`net_router::(anon)::Direction` 是一个 4 值罗盘枚举。这些值由重定位后的 `char*` 方向名表 @ `0x21924ed8`（`.data.rel.ro`；四个 `R_X86_64_RELATIVE` 槽）逐字节确认，该表由 iteration logger 使用：
| dir | char | 名称 | torus 步进（jump table @ `0xae5dec8`，分派于 `0x13820b34`） |
|---|---|---|---|
| 0 | `'N'` | North (+Y) | `y' = (y + 1) mod Y` |
| 1 | `'W'` | West (-X) | `x' = (x + (X - 1)) mod X` |
| 2 | `'S'` | South (-Y) | `y' = (y + (Y - 1)) mod Y` |
| 3 | `'E'` | East (+X) | `x' = (x + 1) mod X` |
负向步进使用 `(dim - 1)` 加数技巧（`X-1` @ `-0x2a0(rbp)`，`Y-1` @ `-0x2a8(rbp)`），使 wrap-around decrement 在取模前保持非负。两个除数分别是 `ChipBounds.X`（E/W，`idivl` @ `0x13820b6a`）和 `ChipBounds.Y`（N/S，`idivl` @ `0x13820b51`）。
> **注意 —** 这把 Type-5 route literal 的四列绑定到具体罗盘：literal 的第 *k* 列就是 `{N,W,S,E}[k]` ICI 输出端口。列到端口的映射由 [route-table-generation](route-table-generation.md) 负责；本页负责命名这些列的枚举。
### 阶段 A — 候选方向（最短绕行）
对于每个 transfer 目标 XY，求解器会逐轴选择围绕 torus ring 的两种方向中*较短*的一种：
```c
// per-axis candidate-direction choice (decompile @ 0x1381d850..0x1381d942)
forward_x = (dst_x - src_x) mod X // idiv ChipBounds.X @0x1381d875
if src_x != dst_x:
if forward_x <= X / 2: candidate += E (dir 3) // cmp X/2 @0x1381d87b
else: candidate += W (dir 1)
forward_y = (dst_y - src_y) mod Y
if src_y != dst_y:
if forward_y <= Y / 2: candidate += N (dir 0)
else: candidate += S (dir 2)
RET_CHECK !directions.back().empty() // str "!directions.back().empty()" @line 2927
RET_CHECK directions.back().size() <= 4 // str "directions.back().size() <= 4" @line 2958半周长 X/2（-0x2c0(rbp)）和 Y/2（-0x2b8(rbp)）在 0x1381d12a/0x1381d143 处一次性设置。当某轴上 src == dst 时，该轴不贡献方向。结果是一个最多包含两个方向的 InlinedVector<Direction,4>，表示朝目标前进的最小跳数步进集合。这是 wild-first 最短路径（randomized-toroidal-wildfirst）在 net_router 中的类比，但它运行在 core/chip 网格上，并且是维度有序而非随机化的。
陷阱 — 比较是
forward <= dim/2，不是forward < dim/2。在偶数直径的环上，平局（forward == dim/2）会确定性地偏好正方向（E / N）。如果重新实现翻转这个平局规则，会生成不同但同样最优长度的调度，并且无法逐字节匹配 Type-5 literal。
阶段 B — 剩余距离最长优先的优先队列
每个 (destination, candidate-directions) 都会变成一个 SchedulingQueueKey（0x28 字节 = 一个 {step:int, …, InlinedVector<Direction,4>} payload），通过 std::__sift_up<_ClassicAlgPolicy, …$_0…> @ 0x13825f60 推入一个由 std::vector 支撑的二叉堆。反编译确认了三个 push 位置（第 1183、2528、5007 行）。比较器 $_0 按剩余环距离对 key 排序：
// SchedulingQueueKey comparator $_0 (inlined at __sift_up 0x13825f60)
remaining = 0
for each dir still in key.directions:
(dx, dy) = dst_xy[dir.id] - current_xy // per-dir target read @0x13826009
if x_wrap: rx = min(|dx|, X - |dx|) else rx = |dx| // ChipBounds.X @0x13826037, wrap bit @0x1382602b
if y_wrap: ry = min(|dy|, Y - |dy|) else ry = |dy| // ChipBounds.Y @0x1382606d, wrap bit 0xa2<<16 @0x13826065
remaining = max(remaining, rx + ry) // cmovg accumulate @0x13825ffc
// higher remaining → higher priority (longest-path-first / critical-path greedy)
```text
主循环弹出最高优先级的 transfer，按所选方向（阶段 C）推进一跳，安装对应的 `Action`，再把带有新坐标和缩小后候选集合的 transfer 重新推入，直到它到达目标。优先调度剩余路径最长者，可以避免关键路径被竞争相同端口的短 transfer 饿死。
> **怪癖 —** 排序*度量*（剩余环距离）和 `__sift_up` 方向已经逐字节确认，但 heap-pop 极性（严格最长优先还是最短优先）取决于主循环使用的 `pop_heap`/`sort_heap` 约定，反汇编没有钉死这一点。比较器的 `cmovg`/`max` 累积读起来是一个*按距离取最大*的堆，因此是“最长优先”；请把极性视为**高**置信度，把度量视为**确定**。
### 阶段 C — 每方向 torus 步进
推进一跳由 jump table @ `0xae5dec8`（4 个 int32 自相对偏移）完成，按 `Direction` 值索引，并在 `0x13820b34` 处分派。每个 case 都按上面的 Direction 表所示，在一个轴上以模 wraparound 方式将当前芯片坐标推进 ±1。所选方向同时也是这一跳的 `Action` 写入的**列**（四个每目标 `Action` 槽之一），因此方向既命名了下一个坐标，也命名了 literal 列。
---
## 每跳缓冲区移交
调度以离散事件模拟器的方式驱动。三个延迟的 `std::function<Status(map<XY, IterationInfo>&)>` 闭包实现每一跳的源/目标端点分配以及跳与跳之间的缓冲区移交。map 参数是每步骤的目标 XY 记分板；`$_1`/`$_2` 会忽略它（它们作用于捕获状态），它存在只是因为延迟回调 vector 需要同构类型。
### `$_4` — 将回调延迟到未来步骤
```c
function defer_at_step(extra_actions, index, cb): // 0x13825b60
// extra_actions = vector<optional<vector<function<…>>>>, element stride 0x20,
// optional has_value byte @+0x18
if index < extra_actions.size:
RET_CHECK extra_actions[index].has_value() // str "extra_actions[index].has_value()" @0xa171d66 (line 1681)
extra_actions[index].value.emplace_back(cb) // 32-byte std::function payload move @0x13825bba
else:
grow extra_actions to index+1, engaging empty optional<vector<function>> slots$_4 是延迟原语：“当模拟到达步骤 index 时运行回调 cb。”它是把多跳路径分散到多个步骤的唯一机制。两个调用点（0x13820ae8 用于 $_1，0x13820fd1 用于 $_2）也是它仅有的调用者。
$_1 — 缓冲区释放 / 飞行中跟踪（移交）
当某一跳的 DMA 落入目标 scratch 缓冲区时，$_1 会把该缓冲区标记为可供下一跳读取，并记录飞行中的 DMA，以便检测复用冲突：
function buffer_release(capture): // 0x13826dc0
// capture (0x28 POD): {Allocator-set-ptr@0, XY-key@8, deque-ctx@0x18, int available_at@0x20}
entry = FlatHashMap<XY, Allocator>.find_or_prepare_insert(set, &capture.XY) // 0x13826de1
available_at = capture.available_at + 1 // inc @0x13826e14
RET_CHECK available.empty() || available.back().second <= available_at // sorted by release step; str @0x8509fa3 (line 389)
RET_CHECK ptr.type == PointerType::kAlloc // str "ptr.type == PointerType::kAlloc" @line 390
RET_CHECK ptr.index.has_value() // str @0xa16fa09 (line 391)
RET_CHECK *ptr.index < size // str @0x8672033 (line 396)
RET_CHECK c_none_of(available, e -> e.first == *ptr.index) // NO double-release; str @0xa0f3a0c (line 395)
available.push_back((*ptr.index, available_at))
latest_dma_out.push_back(*ptr.index | (available_at << 32)) // deque<pair<int,int>>; __add_back_capacity @0x13826f4d
```text
两个不变量构成缓冲区移交：
- **可用性** — 缓冲区索引会添加到按释放步骤排序的每目标 XY `available` 列表中。某一跳只有在缓冲区出现在这个列表后才会读取它；这和流水线因子结合起来，就是下一跳会在 `kPipelineFactor` 步之后运行的原因。
- **飞行中串行化** — `(index, step)` 对会推入 `latest_dma_out` deque。冲突不变量 `!latest_dma_out.contains({src, block})`（在 `LogAndValidatePaths` 中检查）禁止在同一路径上从同一源块发起第二个 DMA，而前一个仍在飞行中。
> **怪癖 —** 这里跟踪的中继缓冲区**始终是 `kAlloc`** — `RET_CHECK ptr.type == PointerType::kAlloc`（字符串 `"ptr.type == PointerType::kAlloc"`，`net_router_emitter.cc` 第 390 行，会拒绝任何 `type != 2`）拒绝其他种类。collective 的真实输入/输出缓冲区（`kInput`/`kOutput`）不会进入飞行中跟踪器；只有中间 scratch 跳会进入。
### `$_2` — 提交每跳端点放置
当某一跳的端点固定后，`$_2` 会把 16 字节 `Action`（`{src_ptr, dst_ptr}` 四元组）写入此步骤到达的每个 transfer 的调度 `placement` 数组：
```c
function commit_placement(capture): // 0x13827760
// capture (0x30): {placement-ctx@0, InlinedVector<int,1> transfer_ids@8, Action16 payload@0x20}
for t in capture.transfer_ids:
RET_CHECK t < placement.size() // cmp @0x138277a7, ud2 @0x138277e0
RET_CHECK !placement[t].has_value() // place exactly once; str "placement[transfer].has_value()" @0xa171d88 (line 1753)
placement[t][0..0x10) = capture.Action16 // vmovups @0x138277c0
placement[t].has_value = 1 // movb $1,0x10 @0x138277c9这是每跳源/目标端点写入：16 字节 payload 是 Action 端点四元组（两个 Pointer），捕获的 int 列表是此步骤提交的 transfer id 集合。提交后的 Action 后续会落入 Type-5 literal 序列化的每 {core, step, direction} 槽中。
调度记录
placement[transfer] record (0x14 bytes = 5×4; laid 8-per-0xa0 block, memset @0x1381cac0)
+0x00 int src endpoint field
+0x04 int dst endpoint field
+0x08 byte (flag)
+0x0c int step
+0x10 byte has_value // set once by $_2; RET_CHECK !has_value before write
```text
```text
Schedule (returned)
+0x00 vector<Step> per-step Action grid
+0x08 int step_count
+0x10 int step_cap
+0x18 deque<pair<int,int>> latest_dma_out (in-flight DMAs)
+end FlatHashMap<XY, Allocator> per-destination buffer occupancy流水线因子
LogAndValidatePaths @ 0x13823dc0 会强制执行延迟窗口：last_location.back().second <= step - kPipelineFactor，其中立即数以 add $0xfffffffffffffffd（= step - 3）内联于 0x13824518。因此 kPipelineFactor = 3：某一跳在步骤 S 写入的缓冲区，只有在步骤 ≥ S+3 时读取才合法，用来建模 3 级 DMA 延迟。这就是多跳路径会分散到多个步骤而不是打包到连续步骤中的原因，也是 $_1 的 available_at 会相对写入步骤偏移的原因。验证器还会检查步骤单调性（str @0x85c67d1）和源链式连接（last_location.back().first == src_ptr，str @0x8596174）。
PointerType 枚举
用途
每个调度 Action 的每个端点都是一个 net_router::Pointer，它的 type 字段是 net_router::PointerType。该类型告诉运行时缓冲区位于哪个地址空间：collective 输入、collective 输出，或本地 scratch。该枚举是 2-bit 字段，恰好有三个有效值；值 3 会被拒绝。
值
| 值 | 字符标签 | 名称 | 在 GetDataPointerAddress 中的解析 |
|---|---|---|---|
| 0 | 'i' (0x69) | kInput | 调用方回调 function<LloMemoryAddress(PointerType, PointerType, LloValue*)>(0, …) |
| 1 | 'o' (0x6f) | kOutput | 调用方回调 (…)(1, …) |
| 2 | 'a' (0x61) | kAlloc | GetLocalDataAllocAddress @ 0x13828460（本地 scratch） |
| 3 | — ('?'/0x00) | （未定义） | 被 ScheckLt(type, 3) 边界拒绝 |
字符标签由 Pointer::ToString @ 0x13826c60 逐字节确认；它从 3 字节 literal 0x616F69（"ioa"）中打包标签，并选择 byte = (0x616F69 >> (8 * type)) & 0xff（反编译第 24 行：LOWORD(v14) = (unsigned __int8)(0x616F69u >> (8 * v4))，其中 v4 = *type）。名称 kAlloc 还由断言字符串 "type != net_router::PointerType::kAlloc"（在 $_1 中）逐字确认。值 0/1 的名称 kInput/kOutput 是结构性解读：GetDataPointerAddress 把值 0 和值 1 路由到外部输入/输出地址回调，把值 2 路由到本地 scratch；但没有从拼写出来的枚举器字符串中提取，因此置信度是 HIGH 而非 CERTAIN。
注意 —
Pointer除 type 外还携带一个可选index（ToString会先打印 type 字符，再通过to_string打印索引；如果索引不存在，则打印'?'（63）——反编译第 25–35 行）。该索引是在 type 所命名地址空间内的缓冲区/槽位序号。
解析地址
RoutingCodeEmitter::GetDataPointerAddress @ 0x13828220 会把 (PointerType type, index) 转换为 LloMemoryAddress：
function GetDataPointerAddress(builder, ptr_type, ptr_index, value, callback): // 0x13828220
ScheckGe(ptr_type, SimmU32(0)) // "Pointer type must be >= 0"; str @0x9fc5d68
ScheckLt(ptr_type, SimmU32(3)) // "Pointer type must be < 3"; str @0x9c15936
alloc_addr = GetLocalDataAllocAddress(...) // 0x13828460 — the kAlloc address
is_input = Predicated(SeqS32(ptr_type, SimmU32(0))) // type == 0 ?
in_addr = callback(0, …) // (*callback)(kInput, …) @ (a6+16)
sel0 = Phi(alloc_addr, in_addr) // pick alloc vs input
is_output = Predicated(SeqS32(ptr_type, SimmU32(1))) // type == 1 ?
out_addr = callback(1, …) // (*callback)(kOutput, …)
return Phi(sel0, out_addr) // pick (alloc|input) vs output
```text
地址会构造成 SSA `Predicated`/`Phi` 链（`LloRegionBuilder` IR），而不是运行时分支：它会具体化全部三个候选地址，并通过谓词在它们之间选择，因此同一份 emitted code 对三种类型都正确。反编译确认了两个 `SeqS32(type, 0)` / `SeqS32(type, 1)` 谓词、两次通过 `(*(callback+16))` 的回调间接调用，以及 `Phi` 选择。
> **陷阱 —** 边界是 `ScheckLt(type, 3)`，也就是有效范围只有 `[0, 3)` = `{0, 1, 2}`。如果重新实现允许一个 2-bit 字段的完整 `[0, 4)` 范围，就会接纳一个未定义的 value-3 指针；`GetDataPointerAddress` 会在运行时拒绝它，而 `ToString` 会把它打印成只有裸 `'?'` 索引标记、没有 type 字符的形式。
>
> **注意 —** route-schedule 的**中继** `Action` 在 `src_ptr` 和 `dst_ptr` 上都携带 `kAlloc`（每步骤 `$_1` 的 `RET_CHECK`）。`kInput`/`kOutput` 只出现在 collective 的*终端* `Transfer` 端点上，由调用方的地址回调在运行时解析。这些终端端点在哪里被标记为 `kInput` 还是 `kOutput`，位于各 collective emitter（AllGather / AllToAll / CollectivePermute）中，而不在 `CreateRoutingSchedule` 中；本页没有追踪该赋值。
---
## 序列化为 Type-5 Literal
`CreateRoutingScheduleLiteral` @ `0x13822400` 会运行 `CreateRoutingSchedule`，然后把得到的 `Schedule` 扁平化为一个平坦 `int32` 数组，并包装为 `xla::Literal`（运行时重放的 Type-5 route literal）。每个调度 `Action` 由 `SerializeAction` @ `0x13829300` 编码为一个打包 `int32`。
### `SerializeAction` — 打包 Action 位布局
```c
function SerializeAction(action): // 0x13829300
if action.dma.is_set: // *(action+56) == 1
RET_CHECK action.dma.src_ptr.index.has_value() // str "action.dma->src_ptr.index.has_value()" (line 301)
RET_CHECK *src_ptr.index < (1 << 13) // str "*action.dma->src_ptr.index < 1 << kActionAddressIndexSize" (line 302)
RET_CHECK action.dma.dst_ptr.index.has_value() // str "action.dma->dst_ptr.index.has_value()" (line 312)
RET_CHECK *dst_ptr.index < (1 << 13) // str "*action.dma->dst_ptr.index < 1 << kActionAddressIndexSize" (line 313)
return (src_ptr.index & 0x1FFF) // b0-12 13-bit source index
| ((src_ptr.type & 3) << 13) // b13-14 2-bit source PointerType
| ((dst_ptr.index << 15) & 0xFFF8000) // b15-27 13-bit dest index
| ((dst_ptr.type & 3) << 28) // b28-29 2-bit dest PointerType
+ 0x40000000 // b30 "DMA action" marker bit
return 0 // no-DMA action → 0该编码由单个 return 表达式逐字节确认（反编译第 37 行）： ((dst.type & 3) << 28) + (src.index & 0x1FFF | ((src.type & 3) << 13) | (dst.index << 15) & 0xFFF8000) + 0x40000000。 kActionAddressIndexSize = 13 由两个 < 1 << kActionAddressIndexSize 边界固定（MakeCheckOpString 调用中的 literal 除数 0x2000 = 1 << 13）。位字段图：
| 字段 | 位 | 宽度 | 掩码 / 位移 |
|---|---|---|---|
src_ptr.index | b0–12 | 13 | & 0x1FFF |
src_ptr.type | b13–14 | 2 | (& 3) << 13 |
dst_ptr.index | b15–27 | 13 | (<< 15) & 0xFFF8000 |
dst_ptr.type | b28–29 | 2 | (& 3) << 28 |
| DMA-action 标记 | b30 | 1 | + 0x40000000 |
空（no-DMA）action 编码为 0；因此 b30 标记可以区分活跃 DMA 和空槽。index 字段正是 Pointer::index 序号；type 字段是上文记录的 2-bit PointerType。
Literal 大小与记录索引
CreateRoutingScheduleLiteral 分配一个平坦 int32 缓冲区，并遍历每个 iteration × core，为每条记录写入四个 SerializeAction word（每个罗盘列一个）：
num_steps = schedule.iterations // v191
X = topology.ChipBounds.X // topology+88
Y = topology.ChipBounds.Y // topology+92
total_values = 4 * num_steps * X * Y + 4 // line 935: 4*v191*X*Y + 4
// header word [0] = num_steps, words [1..3] = 0
for step in [0, num_steps):
for core dma-chain at this step:
record = step + num_steps * core.Id() // line 982: v22 + v15*Id == core_id*num_steps + step
offset = 4 * record
RET_CHECK offset + 4 <= total_value_count // str "offset + kRoutingScheduleValuesPerRecord <= kTotalValueCount" (lines 491/680)
buf[offset+0..3] = SerializeAction(action[N/W/S/E]) // 4 columns; kRoutingScheduleValuesPerRecord = 4
```text
- **Literal 大小公式** — `4 * num_steps * X * Y + 4`（在第 935 行逐字节确认）。末尾的 `+ 4` 是 4-word header：word `[0]` 保存 `num_steps`，word `[1..3]` 被清零（第 949–952 行）。
- **记录索引** — `core_id * num_steps + step`（在第 982 行以 `step + num_steps * core.Id()` 逐字节确认）。记录以 core 为主序、step 为次序排列。
- **`kRoutingScheduleValuesPerRecord = 4`** — 每条记录有四个 `SerializeAction` word（第 983–986 / 1004–1007 行），由 `offset + kRoutingScheduleValuesPerRecord <= kTotalValueCount` RET_CHECK 约束。
| 函数 | VMA | 作用 |
|---|---|---|
| `CreateRoutingScheduleLiteral` | `0x13822400` | `Schedule` → 平坦 `int32` `xla::Literal` |
| `SerializeAction` | `0x13829300` | `Action` → 打包 `int32` |
| `EmitRoutingCode` | `0x13819ca0` | 在运行时消费调度的 route-code emitter |
`EmitRoutingCode` @ `0x13819ca0` 是运行时侧 emitter（它把 `GetDataPointerAddress` 回调贯穿下去，以具体化每个 `Pointer`）；其完整函数体记录在 [route-table-generation](route-table-generation.md) 中。
---
## 求解器流水线速览
| 阶段 | 函数 / 位置 (VMA) | 输出 |
|---|---|---|
| 收集目标 XY | `CreateRoutingSchedule` loop @ `0x1381c770` | `std::map<XY, IterationInfo>` 记分板 |
| 候选方向（最短环） | `@0x1381d850..0x1381d942` | 每目标一个 `InlinedVector<Direction,4>` |
| 构建 / push 优先队列 | `__sift_up<…$_0…>` @ `0x13825f60`（×3） | `SchedulingQueueKey` (0x28) 堆 |
| ↳ 距离比较器 | `$_0` @ `0x13825f60`（逐轴 `min(\|d\|, dim-\|d\|)`） | 剩余环距离键 |
| 每方向 torus 跳 | jump table @ `0xae5dec8` / `@0x13820b34` | 下一个芯片坐标（mod ChipBounds） |
| 将回调延迟到步骤 *k* | `$_4` @ `0x13825b60` | `extra_actions[step] += function` |
| 缓冲区释放 / 飞行中记录 | `$_1` @ `0x13826dc0` | `available` 列表 + `latest_dma_out` deque |
| 提交 `Action` 放置（按方向） | `$_2` @ `0x13827760` | `placement[transfer]` `Action` 槽 |
| 验证（流水线 / 源 / 步骤顺序） | `LogAndValidatePaths` @ `0x13823dc0` | `Schedule`（`kPipelineFactor=3`） |
| 将每个 `Action` 序列化为 int32 | `SerializeAction` @ `0x13829300` | 打包 word（`kActionAddressIndexSize=13`） |
| 将 `Schedule` 扁平化为 route literal | `CreateRoutingScheduleLiteral` @ `0x13822400` | `4*num_steps*X*Y+4` 个 int32 Type-5 literal |
| 解析指针地址（运行时） | `GetDataPointerAddress` @ `0x13828220` | `LloMemoryAddress`（scratch 或回调） |
---
## 交叉引用
- [路由概览](overview.md) — 此求解器所在的 route-generation → cache → emission 流水线
- [Net-Router 流水线](net-router-pipeline.md) — 向 `CreateRoutingSchedule` 供给 `Transfer` 集的各 collective 构建器
- [GetStaticPath 与 Multipod](get-static-path.md) — inter-pod 路径生成；上游路径来源
- [Randomized Toroidal WildFirst](randomized-toroidal-wildfirst.md) — 随机遍历路径类比；此求解器是维度序 torus 对应物
- [路由表生成](route-table-generation.md) — `CreateRoutingSchedule` 产生的 Type-5 route literal，以及列 → ICI 端口映射
- [片内描述符](../dma/intra-chip-descriptor.md) — 每步骤 DMA 描述符，其 routing 字段由调度的 `Action` 端点提供