ICI 路由 — 章节地图
地址适用于来自 libtpu-0.0.40-cp314 wheel 的 libtpu.so。其他版本会有差异。二进制：
extracted/libtpu-0.0.40-cp314-cp314-manylinux_2_31_x86_64/libtpu/libtpu.so（build-id89edbbe81c5b328a958fe628a9f2207d，buildlibtpu_lts_20260413_b_RC00；.textVMA == file offset，base0xe63c000）。下面所有符号都存在于完整符号二进制中；demangled 名称和地址已与 IDA 反编译交叉校验。
摘要
本页是 ICI 路由子系统的地图：这一层为 3-D torus 上每个（源芯片，目标芯片）对决定一次传输所走的 ICI 链路 hop 精确序列。路由位于 collective 栈（决定每个 color 的 ring schedule）和 ICI fabric（搬运字节）之间：collective emitters 告诉路由“这个 core 发给那个 core”；路由回答“从哪个 SerDes port 出去，经过哪些中间芯片”。具体来说，它生成每芯片一张静态路由表，在 slice bring-up 时安装一次，之后由片上 routing engine 按索引查询；没有运行时 reroute。
这个子系统有两个逻辑上不同、但容易混淆的输出，所以本节的核心组织思路是把它们分开。第一个是 resilient ICI route table（accel_ssw::deepsea::slice_builder）：一张 per-link auto-routing table，对整个 slice 回答“给定目标芯片，走哪个输出链路”，由 *ToroidalWildFirstPaths 算法围绕故障链路生成一次，并安装为 PerLinksRoutingTable。第二个是 per-collective net_router schedule（xla::jellyfish::net_router）：一个显式的 per-step、per-direction DMA 程序，回答“在 step k、ICI port d 上，这个 core 执行 src→dst DMA”，由 CreateRoutingScheduleLiteral 编译成一个 s32[N] 常量，并由 EmitRoutingCode 重放。两者正交，运行在不同 namespace 中；二者都终止于 ICI DMA 层。
本页记录：（1）从 replica groups 到已安装表和运行时 schedule 的 端到端路由流水线；（2）两类路由族：新生成的 toroidal paths（PopulateUnoptimizedRouteCache）与预计算的 ToroidalRouteCache 查询；（3）InitRouteSolution 核心处的 cache-vs-generate 决策。每个算法都有自己的同级页面；本页只链接它们，不重复其字节级推导。Collectives、twisted-torus geometry 和 barriers 是同级 sections，可从 交叉引用 进入。
对重新实现而言，路由子系统的契约是：
- generator class hierarchy：一个
RoutingTableGenerator抽象基类，配套 factory（RoutingTableGeneratorFactory）选择 NHop 与 limited-ICI routing、parallel unicast generator（ParallelRoutingTableGenerator），以及拥有InitRouteSolution/GetStaticPath(s)的 resilient*Topology家族。 - resilient path generator
*ToroidalWildFirstPaths：先做 minimal dimension-order routing，再围绕周期性 fault lattice 进行一次 one-hop “wild-first” detour，验证 fault-freedom，并标记 dateline-symmetry phase。 - route cache：
ToroidalRouteCachebinarypb schema、其CompressedToroidalRouteCachewrapper、RouteCacheDeduplicatorcache-key lookup，以及三个嵌入式 cache sets。 - runtime hand-off：
StaticPathdirection sequence 如何变成PerLinksRoutingTablerow 和 DMA-descriptor routing-table index，以及 net_router schedule literal 如何按每 core、每 step 重放。
| Resilient namespace | accel_ssw::deepsea::slice_builder（route table，bring-up time） |
| net_router namespace | xla::jellyfish::net_router（per-collective schedule，compile time） |
| Generator base / factory | RoutingTableGenerator @0x1fbd72e0 · RoutingTableGeneratorFactory::CreateGenerator @0x1fbd3dc0 |
| Resilient orchestrator | ResilientToroidalTopology::InitRouteSolution @0x1fbdf8a0 |
| Live path generator | RandomizedToroidalWildFirstPaths::PathsWithFaults @0x1fbea380 · NonRandomizedToroidalWildFirstPaths::Paths @0x1fbe6ae0 |
| Cache lookup | RouteCacheDeduplicator::Find @0x20b59000 → ToroidalRouteCache::Create @0x20b5d6e0 |
| Schedule literal | net_router::CreateRoutingScheduleLiteral @0x13822400 → EmitRoutingCode @0x13819ca0 |
| Routing model | Static、per-chip、3-D torus 上的 dimension-order；无运行时 reroute |
1. 端到端路由流水线
collective 的 traffic pattern 在任何字节移上链路之前，会经过六个概念阶段。阶段 1–2 属于 collective 栈，记录在 Collectives 中；阶段 3–6 属于本节。route table（阶段 3–5，bring-up 时安装一次）和 route schedule（按每个 collective instance 编译的 net_router program）之间的划分，是最重要的结构事实，并在 §1.1 中单独展开。
replica groups (HLO ReplicaGroup device lists)
│ [collectives §1.3] ReplicaGroupsOnNDPlane → physical chip coords on the torus
▼
[1] inter-node distances GetDistances(src,dst) ── per-dim signed torus-reduced vector
│ (topology vtable+0xb8; twist-adjusted for _twisted shapes)
▼
[2] path generation one of two families (§2):
│ (A) toroidal WildFirst — minimal DOR first, then wild-first detour around faults
│ (B) precomputed ToroidalRouteCache lookup
▼
[3] per-hop routing schedule PathFromDistance → ordered Direction[] (strict dimension order)
│ + HalfwayDirections / UpdateSymmetryForHalfway (dateline phase)
▼
[4] DMA route-table emission Direction[] → PerLinksRoutingTable row {output_link_index, next_hop_chip_id}
│ installed via Master::SetRoutingTable (bring-up only)
▼
[5] net_router runtime two consumers of the installed table:
(a) auto-route: DMA descriptor carries dest chip id → on-chip routing engine indexes the table
(b) explicit: EmitRoutingCode replays the per-step CreateRoutingScheduleLiteral programNOTE — 阶段 1–4 每个 slice 在 bring-up 时只运行一次，并产出一张静态表；这个 build 中没有动态重路由。故障链路通过提前围绕它生成路径来处理（§3），而不是在运行时响应。这就是整个子系统“静态但感知故障”的原因：容错完全存在于生成中，从不在 datapath 中。
1.1 两个输出，一个章节：route table vs route schedule
路由子系统会物化两个 artifact，重新实现者不得将它们合并：
| 方面 | Resilient route table | net_router route schedule |
|---|---|---|
| Namespace | accel_ssw::deepsea::slice_builder | xla::jellyfish::net_router |
| 回答的问题 | “dest chip → 哪条 output link”（per-link auto-route） | “step k，direction d → DMA src_ptr→dst_ptr”（显式程序） |
| 构建时机 | slice bring-up 时一次 | 每个 collective instance 编译时 |
| Generator | *ToroidalWildFirstPaths / ToroidalRouteCache | CreateRoutingSchedule @0x1381c6a0 |
| 存储为 | 每芯片 PerLinksRoutingTable（安装到硬件） | s32[N] xla::Literal 常量（ConstantMapper Type 5） |
| 消费者 | 片上 routing engine（按 dest chip id 索引） | EmitRoutingCode @0x13819ca0（每 step 重放 4 个方向） |
| 单页文档 | Route-Table Generation、Toroidal Route Cache | Create Routing Schedule、Net-Router Pipeline |
两者最终都落到 ICI：EmitRoutingCode 发出的 per-step RoutingTableStartDma 携带 DMA descriptor，其 routing field 由已安装的 per-link table 解析。schedule 提供每 step/direction 的 (src_ptr, dst_ptr)；route table 为该 descriptor 提供 multi-hop link path。descriptor layout 见 ICR Node-Fabric DMA 和 NF Descriptor，DMA 层见 ICI fabric 章节。
1.2 Generator class hierarchy
resilient route table 由一个以抽象 RoutingTableGenerator 为根的小型 class family 生成。factory 从 routing mode 选择具体 generator；resilient generator 是若干 *Topology 之一，实现共享的 InitRouteSolution / GetStaticPath(s) interface。
RoutingTableGenerator (abstract) 0x1fbd72e0 (ctor) / GeneratesDeadlockFreeTables 0x1fbd5f60
├─ RoutingTableGeneratorFactory
│ ├─ CreateGenerator 0x1fbd3dc0 ── selects the concrete generator
│ ├─ IsNHopRouting 0x1fbd3fa0 ── classic N-hop routing mode
│ └─ IsLimitedIciRouting 0x1fbd3fe0 ── limited-ICI-routing mode (net_router schedule)
├─ ParallelRoutingTableGenerator 0x1fbd4ae0 (ctor)
│ ├─ Generate 0x1fbd4b60 ── parallel route-table build
│ ├─ CreateUnicastRoutingTables 0x1fbd5340/ CreateSrcDestUnicastRoutingTables 0x1fbd5640
│ └─ RouteTargetCache::{GetPath 0x1fbd42c0, PopulatePath 0x1fbd4360, PopulateLinks 0x1fbd4680}
└─ *Topology (own InitRouteSolution / GetStaticPath(s)):
├─ Topology::{InitRouteSolution(base), GetStaticPath 0x20bf7820, GetStaticPaths 0x20bf78c0}
├─ ResilientToroidalTopology::{InitRouteSolution 0x1fbdf8a0, GetStaticPath 0x1fbe1ce0, GetStaticPaths 0x1fbe1e20}
└─ TwistedTorusTopology::{InitRouteSolution 0x20b3f7c0, GetStaticPath 0x20b407c0} (see ../twist/overview.md)NOTE —
GetStaticPath（单数）和GetStaticPaths（复数）都是真实入口点，且不能互换。在 randomized policy 下，一个 (src,dst) class 映射到一组等成本路径，因此单数 accessor 会 hard-error（“GetStaticPath… is not defined whenrandomized_pathsis enabled, useGetStaticPaths(plural)”，.rodata@0xa11432f）。把复数 accessor 重新实现为 canonical one；单数只是便捷形式，仅对 non-randomized（单个StaticPath）policy 有效。见 Get Static Path。
2. 两类路由族
两类族都是同一个 path-generation algorithm 的实现；差别只在交付方式。Family B 是生产 fast path；family A 是 live fallback。二者之间的决策见 §3。
2.1 Family A — 新生成的 toroidal paths（*ToroidalWildFirstPaths）
当没有预计算 cache 匹配 slice 的 fault pattern 时，PopulateUnoptimizedRouteCache @0x1fbe0a20 在 bring-up 时运行 live generator。它实例化两个 policy classes 之一，并为每个 chip pair 调用 Paths(src,dst)：
function PopulateUnoptimizedRouteCache(): // 0x1fbe0a20
if randomized_paths:
gen = CreateRandomized(...) // 0x1fbe0a20 +0x160 → RandomizedToroidalWildFirstPaths
else:
gen = CreateNonRandomized(...) // 0x1fbe0a20 +0x230 → NonRandomizedToroidalWildFirstPaths
for each (src, dst) chip pair:
paths = gen.Paths(src, dst) // build the per-pair route(s)
// "Unoptimized" = correct (deadlock-free, fault-avoiding) but not load-balanced like the baked tables每对上的算法简述如下（完整推导见 Randomized Toroidal WildFirst）：计算 torus-reduced distance（Get Distances）；构造 minimal dimension-order path（PathFromDistance @0x1fbeea20）；如果该 path 避开 periodic fault lattice（IsFaultFreeLink @0x1fbede40 —— 每维 coord mod symmetry == fault_coord mod symmetry 测试，反编译确认为每个 axis 上 v12 % v29 == v15 % v29，再加 Direction::IsSame 匹配），则接受。否则进入 wild-first loop：走一次刻意非最短的 hop，将剩余部分按 dimension order 路由，验证 fault-freedom，并给路径打上 dateline-symmetry phase。randomized policy 保留所有 fault-free wild paths（作为 RandomHop set 发出）；non-randomized policy 只保留第一个（作为单个 StaticPath 发出）。
QUIRK — “Randomized” 不是运行时 PRNG。它是一个确定性的 multi-path policy：generator 发出一组等成本 wild-first candidates，runtime 通过确定性 hash 在它们之间分散 traffic。选择被按 cache 记录为
RouteSchemeoneof variant（RandomHopvsStaticPath），而不是在运行时播种。wild-first detour 和 periodic-fault model 记录在 Randomized Toroidal WildFirst 中。
2.2 Family B — 预计算 ToroidalRouteCache 查询
生产 fast path 加载一张预烘焙 route table，而不是现场生成。嵌入式 caches 是同一 WildFirst algorithm 的离线输出，提前为每个受支持的（fault symmetry、fault count、fault dimension、slice shape、twist）tuple 运行。在 cache hit 时，ToroidalRouteCache::Create @0x20b5d6e0 解压并将匹配的 binarypb lower 成内存中的 per-link table。schema、decompression wrapper 和 binarypb codec 都在同级页面：
- Toroidal Route Cache —
ToroidalRouteCacheConfigs → ToroidalRouteCache → RouteScheme {StaticPath, RandomHop}message hierarchy 和ToroidalRouteCache::Create的 cache-key signature。 - Route-Cache Codec — packed direction-code encoding（
element_size_in_bits，每个 packedDirection的 bit-width）。 - Route-Cache Decompress —
Decompress(CompressedToroidalRouteCache)@0x20b63320，on-disk inflate step。 - Route-Cache Dedup —
RouteCacheDeduplicator::Find@0x20b59000和(fault dimensions, symmetry, twist, dimension sizes)cache key。
GOTCHA — 两类族的输出并非逐字节相同。baked cache 是离线 load-balanced；live
PopulateUnoptimizedRouteCache结果正确但未优化（函数名中的字面 “Unoptimized”）。重新实现者如果落到 live generator，会得到 deadlock-free、fault-avoiding routes，但这些 routes 可能在 wild axis 上承载比 baked tables 更多的 traffic：功能正确，却是可测的性能悬崖。刚好错过 baked shape 的 fault pattern 会静默走这条慢路径。
3. cache-vs-generate 决策
ResilientToroidalTopology::InitRouteSolution @0x1fbdf8a0 是在两类族之间做决定的 orchestrator。它在 topology discovery 之后、bring-up 时调用一次。反编译 control flow（743 行；引用关键行）准确如下：
function InitRouteSolution(): // 0x1fbdf8a0
// dedup = GetCacheDeduplicator(generation): a per-generation switch (line 260)
// selects ONE of three lazily-constructed static deduplicator instances,
// each combining the common kRouteCacheSet with at most one generation set.
switch generation: // HIDWORD(v90)
case 4: dedup = gf_deduplicator // 6acc60406 / TPU7x generation
UpdateDeduplicator(dedup, kRouteCacheSet) // line 283
UpdateDeduplicator(dedup, k6acc60406RouteCacheSet) // line 295
case 2: dedup = vf_deduplicator // viperfish
UpdateDeduplicator(dedup, kRouteCacheSet) // line 618
UpdateDeduplicator(dedup, kViperfishRouteCacheSet) // line 632
case 1: dedup = pf_deduplicator // pufferfish (default)
UpdateDeduplicator(dedup, kRouteCacheSet) // line 668
key = ToFaultyDimensions(discovered_faults) // cache key from the fault pattern
cache = RouteCacheDeduplicator::Find(key) // line 335 — 0x20b59000
if cache found: // PATH B — cache hit (fast path)
table = ToroidalRouteCache::Create(Decompress(cache)) // line 470 — 0x20b5d6e0
else: // PATH A — cache miss (live fallback)
table = PopulateUnoptimizedRouteCache() // line 354 — 0x1fbe0a20
CreateIciResilientFaults(symmetric_fault_set) // line 204 — record faults for telemetry/install
install table (PerLinksRoutingTable, Master::SetRoutingTable)
// if any (src,dst) has no fault-free path → "No route solution for topology %s." (.rodata 0xa02af1b)NOTE — dedup population 是按 generation 的。 内联
GetCacheDeduplicator(int)内的一个switch选择三个惰性构造 static instances 之一；不存在加载所有 sets 的单一 deduplicator。gf_deduplicator（case 4 ——6acc60406/ TPU7x generation）加载kRouteCacheSet+k6acc60406RouteCacheSet；vf_deduplicator（case 2 —— viperfish）加载kRouteCacheSet+kViperfishRouteCacheSet；pf_deduplicator（case 1 —— pufferfish/default）只加载kRouteCacheSet。kRouteCacheSet是每个 generation 共享的 common base；generation-specific set 叠加在其上。k6acc60406RouteCacheSet这个名称只出现在GetCacheDeduplicator的CHECKstrings 中，而不是独立的nmdata symbol。置信度：HIGH。见 Toroidal Route Cache。
3.1 per-generation deduplicators 及其 cache sets
GetCacheDeduplicator(int) 按 generation enum switch，并返回三个惰性构造 static deduplicator instances 之一。每个 deduplicator 将 common kRouteCacheSet 与至多一个 generation-specific set 组合起来：
| Deduplicator（switch case） | Generation | 加载的 cache sets | Set-2 lambda |
|---|---|---|---|
pf_deduplicator (case 1) | pufferfish（default） | 仅 kRouteCacheSet | —（base via RouteCacheDeduplicator::Create） |
vf_deduplicator (case 2) | viperfish | kRouteCacheSet + kViperfishRouteCacheSet | RouteCacheDeduplicator::CreateResilientViperfish |
gf_deduplicator (case 4) | 6acc60406 / TPU7x | kRouteCacheSet + k6acc60406RouteCacheSet | inlined sub @0x1fbe4140（symtab 中未命名） |
kRouteCacheSet 是每个 generation 都加载的共享 base set；generation-specific set 只为 viperfish 和 6acc60406 generation 叠加在其上。三个 sets 中，只有 kRouteCacheSet @0x21f57380 和 kViperfishRouteCacheSet @0x21f57440 解析为独立 nm data symbols；k6acc60406RouteCacheSet 是从反编译中的 CHECK strings 恢复出来的（它折叠在 GetCacheDeduplicator 后面）。
更老的 generations（jellyfish / dragonfish）没有自己的 resilient cache set：在这些 generation 上，故障链路不能被绕过；fault-symmetry gate 会失败，bring-up 会失败或 reshape（gate 和 chip-isolation path 见 Route-Table Generation）。嵌入式 descriptive inventory 将 caches 键控为 route_cache_symmetry_4_4_4_fault_num_{1,2,4}_fault_dim_{x,y,z}_<XxYxZ>[_twisted].binarypb；完整 inventory 和 cache-key dimensions 见 Route-Cache Dedup 与 Toroidal Route Cache。
3.2 Chip isolation — 没有路由时
这个决策可能彻底失败。不存在“隔离一个芯片并继续”；slice 会被移除。三种 failure modes 都表现为 util::Status error：
| Failure | Cause | Surfaced as |
|---|---|---|
| Broken super-pod symmetry | fault set 不在干净的周期 lattice 上 | MakeErrorImpl<3>（“ICI resiliency only supports … super-pod fault symmetry”，.rodata @0x8583f60） |
| Gate failure | slice size 在某个 dim 中不是 fault symmetry 的倍数 | MakeErrorImpl<3>（“The topology size must be a multiple of the fault symmetry”，.rodata @0x84b314b） |
| No path for some (src,dst) | generator/cache 没有找到 fault-free route | “No route solution for topology %s.”（.rodata @0xa02af1b） |
支撑这三者的 fault-symmetry gate 和 periodic-fault lattice 推导见 Route-Table Generation。
4. 路由如何馈入 collective emitters
路由在 bring-up 时产出 per-link auto-route table；collective emitters 随后以两种方式使用它。两个消费者都是 net_router runtime。
4.1 Auto-route — 已安装的 per-link table
对 auto-routing path，按每个 (src,dst) 得到的 StaticPath direction sequence 被编译进每芯片 PerLinksRoutingTable：每个 hop 的 Direction 变成一个 output_link_index（0..3 SerDes port）和一个 next_hop_chip_id。DMA 时，descriptor 只携带 destination chip id 和 core coords；片上 routing engine 索引已安装表，以 auto-route 1..N hops。对 limited-ICI fast path，(src,dst) pair 通过 net_util::MapSrcDstCoreToRoutingTableIndex 映射到 routing-table index；该 index 就是 cache 中的 RouteScheme index。descriptor routing field 和 table row layout 见 Unicast Route Emission、NF Descriptor 和 ICR Node-Fabric DMA。
4.2 Explicit schedule — net_router route program
Limited-ICI-routing collectives（AllGather、AllToAll、CollectivePermute）会编译一个独立于 auto-route table 的显式 per-step DMA program。CreateRoutingScheduleLiteral @0x13822400 将其构建为一个 s32[N] xla::Literal：
N = ChipBounds.X · ChipBounds.Y · num_steps · 4 + 4 (·4 = 4 ICI directions; +4 = trailing pad record)
record(core_id, step) = core_id · num_steps + step (core_id = TpuCoreLocation::Id, row-major)
literal[record·4 + d] = SerializeAction(actions_for_core[core_id][d]) (d ∈ {0,1,2,3} = kAllDirections)
each int32 element (SerializeAction @0x13829300):
bits 0..12 src_ptr.index (13b, kActionAddressIndexSize)
bits 13..14 src_ptr.type (2b, PointerType)
bits 15..27 dst_ptr.index (13b)
bits 28..29 dst_ptr.type (2b)
bit 30 active marker (+0x40000000; element == 0 ⇒ no DMA on this core/step/port)经 full-text caller xref 和反编译确认，三个直接 producer 是 CollectivePermuteEmitter::GenerateConstants、AllGatherEmitter::GenerateConstants 和 AllToAllEmitterBase::CreateAllToAllRoutingScheduleTable。runtime replay 是 EmitRoutingCode @0x13819ca0：每个 core 计算自己的 base record index（GetLimitedIciRoutingTableIndex），读取 4 个 direction columns（GetRoutingTableElement ×4），并围绕 per-step sync flags 发出 RoutingTableStartDma / WaitForDmaInFlight / StartPrefetchIfNeeded。字节精确的完整推导见 Create Routing Schedule 和 Net-Router Pipeline。
GOTCHA — AllReduce 不是
CreateRoutingScheduleLiteral的直接 caller：full-text xref 只找到 AllGather、AllToAll 和 CollectivePermute。AllReduce 通过EmitRoutingCode的直接CreateRoutingSchedule@0x13819d53（runtime、non-literal path）到达 per-step program，而不是 compiled Type-5 literal。因此 Type-5 literal 只属于 AG/A2A/CP。置信度：HIGH。QUIRK — schedule literal 和 route table 回答不同问题，重新实现者必须两者都构建。literal 的元素编码 (src_ptr, dst_ptr)：一个 core 在一个 step 的一个 port 上 DMA 经过的 buffer pointers；它完全不说明字节会穿过哪些物理芯片。该 multi-hop link path 来自 §1–§3 的 route table。混淆二者会得到一个知道发送什么、却不知道路由到哪里去的程序。
相关组件
| 组件 | 关系 |
|---|---|
| Collectives | 消费者 — 阶段 1–2（replica groups → torus mesh）馈入路由；collectives 使用 route table/schedule |
| Twisted Torus | TwistedTorusTopology::InitRouteSolution @0x20b3f7c0 — twisted-shape route family；twist 调整 GetDistances |
| Barriers | Per-step sync flags（AllocateScopedSflag）给 schedule 的 DMA 排序；barrier InfoTables 共享 SMEM read path |
| ICI fabric | 路由最终驱动的 DMA 层；descriptor routing field 由已安装 per-link table 解析 |
交叉引用
Route table — generation and the resilient algorithm
- Route-Table Generation — resilient generator entry、fault-symmetry gate、periodic-fault lattice、chip isolation
- Randomized Toroidal WildFirst — minimal-DOR-first + wild-first detour、randomized vs non-randomized policy
- Get Static Path —
GetStaticPath（单数）vsGetStaticPaths（复数）accessors - Get Distances —
GetDistancestorus-reduced signed distance vector（twist-adjusted）
Route table — cache
- Toroidal Route Cache —
ToroidalRouteCacheConfigs/RouteSchemeschema、ToroidalRouteCache::Createcache key - Route-Cache Codec — packed direction-code encoding（
element_size_in_bits） - Route-Cache Decompress —
Decompress(CompressedToroidalRouteCache)inflate - Route-Cache Dedup —
RouteCacheDeduplicator::Find和 cache-key dimensions、嵌入式 inventory
Route schedule and runtime
- Create Routing Schedule —
CreateRoutingScheduleLiteral/SerializeAction、per-step DMA program - Net-Router Pipeline —
EmitRoutingCodereplay、per-core base index、4-direction read - Unicast Route Emission —
Direction[]→PerLinksRoutingTablerow、routing-table index - NF Descriptor — table 所解析的 DMA descriptor routing field
- ICR Node-Fabric DMA — per-step schedule 驱动的 node-fabric DMA