GetTiebreak

本页所有地址均适用于 libtpu-0.0.40-cp314 wheel 中的 libtpu.so（build-id 89edbbe81c5b328a958fe628a9f2207d，构建 libtpu_lts_20260413_b_RC00）。其他版本会不同。.text VMA 等于文件偏移（基址 0xe63c000）；.rodata VMA 等于文件偏移（基址 0x84a0000）。所有地址都是 VMA。下面的每个符号、偏移和 .rodata 字符串都存在于完整符号二进制中，并已与 IDA 反编译交叉核对。

摘要

accel_ssw::deepsea::slice_builder::TwistedTorusTopology::GetTiebreak（0x20b41320）是 routing 侧的消歧器：给定一个 vertex 和一组等最小距离候选路由，它选择唯一的规范路由。距离层（Get Distances）已经剪枝到最短 hop 集；当该集合包含多个成员时，两条最小距离路径会打平，GetTiebreak 会应用确定性的逐 twist-shape 规则打破平局，使路由表在不同机器上可复现。它是在物理芯片坐标空间中，对 jellyfish GetReplicaPair3DOnTwistedTorus 在设备 ID 空间所做日期线选择的类比；但它是另一个类上的独立机制，并且消费候选向量，而不是计算折叠。

tiebreak 规则由单个字段控制，即 twist-shape 判别量 this[+0xe8]（由 Init，0x20b3e5e0 设置）：1 = k*k*2k、2 = k*2k*2k、3 = k*2k*nk。tiebreaking length 是 K，即最小维度大小，在函数入口通过对拓扑 dim-sizes 向量 this[+0x10..+0x18] 做 std::min_element 计算得到。规则中的每次比较都针对 ±K，而 k*2k*nk 形状中的字面 nK 从不会到达 GetTiebreak 分支：Init 的 DropDimension 会在 tiebreak 之前把它折叠为 3-D twist，因此唯一的字面 n 距离数学位于上游 GetDistance。这就是页面标题所说的 "literal-nK ordering"：排序规则字面上就是 seam 维度上的 ±nK（= ±K）坐标测试，而 K 是它唯一会比较的长度。

GetTiebreak 先按 this[+0xe8] 分派，然后（对 k*2k*2k）按候选数量分派；候选数量编码 vertex 的几何类别：6 个候选 ⇒ k*k*2k（任意 vertex）；4 ⇒ corner，3 ⇒ mid，2 ⇒ edge，均针对 k*2k*2k。本页记录 comparator、三个子规则（对称路由成员资格、按 parity 旋转的 corner、±K edge 测试与 max|coord| < K mid 选择）、定位每条路径的五个错误字符串，以及该规则如何通过为每个 (src, dst) 选择一条规范 seam 路由来消除 K_2K_2K 组分配歧义。

对于重新实现，其契约是：

tiebreaking length 是 K = std::min(dim_sizes)。 在入口处通过对 dim-sizes 向量 this[+0x10..+0x18] 做 SIMD 展开的 min_element 计算一次；它是每个 ±K 比较以及 k*k*2k ±tb 路由所依据的长度。GetTiebreak 内部没有逐 vertex 距离重算；它只操作候选向量和 K。
形状判别量 this[+0xe8] ∈ {1,2,3} 选择规则。 1 和 2 被处理；3（k*2k*nk）在这里不可能出现（由 Init 归约为 3-D twist），因此会像任何非 twist 拓扑一样落入 Invalid-vertex 错误。
候选数量就是 vertex 类别。 对 k*2k*2k，等最小路由数量（4/3/2 = corner/mid/edge）选择子规则；对 k*k*2k，数量必须恰好为 6，否则调用报错。
五个不同且逐字节精确的错误字符串定位每条路径 到源代码行；重新实现必须同时复现成功路由和精确的失败分类。


入口点	`TwistedTorusTopology::GetTiebreak` `0x20b41320`（`twisted_torus_topology.cc`）
ABI	`rdi`=`StatusOr` sret, `rsi`=`this`, `rdx`=`const Coordinates& vertex`, `rcx`=`const vector<Coordinates>& candidates`（mangled `…GetTiebreakERKN8superpod7routing11CoordinatesERKNSt3__u6vectorIS5_…E`）
返回	`StatusOr<Coordinates>` = 所选规范路由，或五种错误之一
Tiebreaking length	入口处的 `K = std::min_element(this[+0x10..+0x18])`（`v117`）
形状判别量	`this[+0xe8]` ∈ {`1`=kk2k, `2`=k2k2k, `3`=k2knk} — 由 `Init` `0x20b3e5e0` 设置
候选数量 = vertex 类别	`kk2k`: ==6 · `k2k2k`: 4=corner / 3=mid / 2=edge
Coordinates	`sizeof = 0x1c`（28 B）；`[+0]`=ndims，`[+4+4·i]`=int32 coord；`GetCoordinate` `0x20c0b800`，`ManhattanNorm` `0x20c0ba00`，`operator==` `0x20c0bac0`
置信度	HIGH（基于 `this[+0xe8]` 的分派、候选数量门控、`std::min` K、全部五个错误字符串、`±K`/parity-rotate comparator 均已由反编译验证），除非某行/标注另有说明

1. GetTiebreak 所处位置

ICI slice 的静态路由表按每个 (src_chip, dst_chip) 对回答：一次传输会走哪一串物理链路。生成器首先找到最小 hop 距离（GetDistances → GetDistanceFromOrigin 0x20b42980），它会产出一组等最小距离候选路由（每轴 hop signature 的 vector<Coordinates>）。在普通 torus 上通常只有一条最短路径；在 twisted torus 上，+K-mod-2K seam 会创造对称替代路径，因此一个 vertex 经常有 2、3、4 或 6 条等最小路由。路由表必须是确定性的，因此每次、每台机器上都必须以相同方式打破平局，这就是 GetTiebreak 的全部工作。

text

GetStaticPath / route-table generation                       (../routing/get-static-path.md)
  └─ GetDistances 0x20b420e0  → vector<Coordinates> candidates   (equal-minimum routes)
       └─ if |candidates| > 1:
            GetTiebreak 0x20b41320  → ONE canonical Coordinates   (this page)
                 ├─ this[+0xe8]==1 (k*k*2k):  build ±tb route, assert ∈ candidates
                 ├─ this[+0xe8]==2 (k*2k*2k): count-dispatch corner/mid/edge → ±K route
                 └─ else:                     Invalid-vertex error
```text

`GetTiebreak` 是 `const`（它读取 `this` 字段，但不修改拓扑），并且**不会重新生成距离**；它接收已经剪枝过的候选向量和标量 `K`。判别量 `this[+0xe8]` 和 dim-sizes 向量 `this[+0x10..+0x18]` 都由拓扑构造时的 `Init`（`0x20b3e5e0`）填充。所选路由就是 route-cache codec 作为键的路由，也是 [emission 层](../routing/get-static-path.md) 编程进 per-link 表的路由。

> **注意 —** 这是 twisted torus 的 *routing* 半边，而不是 *collective* 半边。jellyfish `TwistedTorusND`（[2 阶段 Replica-Group 构造](replica-group-2phase.md)）回答“每个 core 与谁规约”；`TwistedTorusTopology::GetTiebreak` 回答“在两个已经于距离上打平的芯片之间，字节由哪些物理链路承载”。两个类描述同一个 `+K` seam；混淆它们会得到一个知道伙伴但不知道链路的调度。见 [章节地图](overview.md#2-the-twistedtorus-class-family)。

---

## 2. 形状判别量 — `this[+0xe8]`（在 `Init` 中设置）

`TwistedTorusTopology::Init(absl::Span<const int> dims, bool)`（`0x20b3e5e0`）把 3-D twisted 几何分类为三种形状之一，并把结果存入 `this[+0xe8]`（反编译为 `*((_DWORD*)this + 58)`；`58·4 = 232 = 0xe8`）。分类器统计有多少轴等于短尺寸 `K`（`numK`），以及有多少轴等于双倍尺寸 `2K`（`num2K`）：

```c
function TwistedTorusTopology::Init(this, dims, flag):      // 0x20b3e5e0
    ndims = this[+0x8]
    if ndims != 3: ... (no twist arm; GetTiebreak later falls to Invalid-vertex)
    K  = min over dims                            // the short axis size
    numK  = count(dim == K)                        // count loop
    num2K = count(dim == 2*K)                      // count loop
    if      numK  == 2:  this[+0xe8] = 1           // k*k*2k  — line 730
    else if num2K == 2:  this[+0xe8] = 2           // k*2k*2k — line 734
    else if num2K == 1:  this[+0xe8] = 3           // k*2k*nk — line 738
        nK_dim = wmemchr(dims, nK)                 // 0x211ac220 — index of the nK axis
        this[+0x130] = nK_dim ; this[+0x134] = 1   // line 750 ([+0x134]=1: nK recorded
        DropDimension(this, nK_dim)                //   0x20b3f4e0 — reduce to a 3-D twist)
    this[+0xe0] = route-cache-enabled bool

三处赋值已在第 730 / 734 / 738 行由反编译验证；wmemchr（0x211ac220）和 this[+0x134]=1 存储（第 750 行）确认了 nK 轴记录。slice-shape 支持由 .rodata 字符串 "TPU twisted torus only supports k*k*2k and k*2k*2k and k*2k*nk slice shapes."（0xa020458）定位。

`this[+0xe8]`	形状	`numK` / `num2K`	会到达 `GetTiebreak` 分支吗？
`1`	`kk2k`	2 / 1	是 — 6 候选对称路由路径（§4）
`2`	`k2k2k`	1 / 2	是 — 按数量分派的 corner/mid/edge 路径（§5）
`3`	`k2knk`	1 / 0（一个 nK 轴）	否 — `DropDimension` 已归约它；落入 Invalid-vertex（§6）

易错点 — k*2k*nk（字面 n > 2）形状从不会到达 GetTiebreak 分支。Init 会记录 nK 轴索引（this[+0x130]）并在任何 tiebreak 运行前通过 DropDimension 把几何归约为 3-D twist，因此调用 GetTiebreak 时，归约后形状的判别量实际上是 1 或 2。字面 n 距离处理，也就是长轴真正为 n 倍的唯一位置，位于 GetDistance / GetDistanceFromOrigin，不在这里。反编译中没有 this[+0xe8]==3 分支，从字节层面确认了这一点：判别量为 3 会直接落入 Invalid-vertex 错误。因此 "literal-nK ordering rule" 是归约后 twist 上的 ±K comparator，而不是依赖 n 的比较。

3. Comparator：tiebreaking length `K`

GetTiebreak 做的第一件事是计算 tiebreaking length。它是 K，最小维度大小，通过对拓扑 dim-sizes 向量 this[+0x10]（begin）… this[+0x18]（end）做 std::min_element 得到。反编译显示出标准 libc++ min_element 形态：SIMD/按 8 展开的扫描（0x20b41380 处的 v8 += 8 循环，第约 150-246 行）加标量尾部，最终把最小值留在 v117（下面各处均作为 K 使用）：

function GetTiebreak(this, vertex, candidates) -> StatusOr<Coordinates>:   // 0x20b41320
    K = min_element(this[+0x10] .. this[+0x18])      // v117 = the "tiebreaking length"
    shape = this[+0xe8]                               // v119[58]
    if shape == 1:  return TieBreak_kk2k(K, vertex, candidates)    // §4
    if shape == 2:  return TieBreak_k2k2k(K, vertex, candidates)   // §5
    return InvalidVertexError(vertex, this)           // §6
```text

`K` 是 twist 路由在短轴上行走的规范 hop 距离。错误字符串会把它打印为 *"tiebreaking length"* 和 *"expected distance"*：§4 和 §5 中的每个 comparator 都会把候选坐标与 `±K` 比较。

> **怪癖 —** `GetTiebreak` 每次调用都会从 dim-sizes 向量重新计算 `K`，而不是读取缓存的 `min_dim_` 字段；它**不会**复用 collective 半边存储的 `this[+0x5f8]` 风格标量。两个半边是不同的类（`slice_builder::TwistedTorusTopology` 与 `jellyfish::TwistedTorusND`）；routing 类把尺寸保存在 `[+0x10..+0x18]` 向量中并内联归约它。重新实现者不能假设两个半边共享一个 `K` 字段。

| 字段 | 偏移（`this`） | 反编译表达式 | 含义 |
|---|---|---|---|
| ndims | `+0x8` | `v119[2]` | 维度数量（twist 为 3） |
| dim-sizes begin / end | `+0x10` / `+0x18` | `min_element` operands | `std::min` 归约为 `K` 的向量 |
| 形状判别量 | `+0xe8` | `v119[58]` | 1/2/3（§2） |
| route-cache enabled | `+0xe0` | — | bool；设置时 memoise tiebreak 结果 |
| nK-axis index / valid | `+0x130` / `+0x134` | — | 由 `Init` 为 shape 3 设置（§2） |

`Coordinates` 操作数布局（已与 `GetCoordinate` `0x20c0b800`、`ManhattanNorm` `0x20c0ba00`、`operator==` `0x20c0bac0`、ctor-from-`Span` `0x20c0b1e0` 交叉核对）：`[+0]` = int32 ndims，`[+4 + 4·i]` = 最多 6 个内联 int32 坐标，`sizeof = 0x1c`（28 字节，即候选向量步幅，下面的 `28LL * count` 和 `+= 28` 遍历）。

---

## 4. `k*k*2k` 路径 — `this[+0xe8] == 1`，6 个候选

该路径由**恰好 6 个候选**门控（`a4[1] == &byte_6`，即 `candidates.size() == 6`，第 252 行）。规则是：构造*对称期望路由*，即包含 `ndims` 个 int、每个为 `±tb` 的 `Coordinates`，并断言它是 6 个等最小候选之一；匹配时返回它。

```c
function TieBreak_kk2k(K, vertex, candidates):     // inline block @ line 252
    if candidates.size() != 6: goto InvalidVertex   // line 252 gate
    norm = ManhattanNorm(vertex)                     // 0x20c0ba00 (= Σ|coord|), v22, line 256
    ndims = this[+0x8]                                // v24
    // the "tb" fold:  (norm/2) reduced modulo ((K % ndims == 0) + ndims - 1)
    tb_index = (norm/2) % ( (K % ndims == 0) + ndims - 1 )    // v25, line 261
    expected = Coordinates(ndims ints, all 0)        // operator new + memset 0, line 264
    sign = (norm & 1) ? -K : +K                      // v27, lines 267-269 (norm even ⇒ +K)
    expected[tb_index] = sign                         // line 270 — the lone ±K seam coord
    for cand in candidates:                           // stride 28, lines 277-284
        if cand == expected:                          // Coordinates::operator==
            return OK(cand)                            // copy to sret, *a1 = 1 (line 293)
    return Error("…k*k*2k twisted torus vertex %s, expected distance %s "
                 "is not in its minimum route sets.")  // 0xa000dba, line 515 (=0x203)

反编译（第 256-304 行）确认了每一步：第 256 行调用 ManhattanNorm；第 261 行做模 tb 约简（v22 / 2 % (((int)v117 % (int)v24 == 0) + v119[2] - 1)，其中 v117 = K、v24 = ndims）；第 262-271 行构建零填充的 Coordinates；第 267-269 行选择 (v23 & 1) ? -K : +K 符号（v23 = norm & 0xff；v27 默认为 -K，当 norm 为偶数时覆写为 +K）；第 277-284 行以 operator== 搜索候选（步幅 28）。匹配时将所选候选复制到 sret 并设置 *a1 = 1（OK 状态）；无匹配时，第 311 行的 MakeErrorImpl<13> 触发，字符串为 "When applying tiebreaking rule for k*k*2k twisted torus vertex %s, expected distance %s is not in its minimum route sets."（0xa000dba，源第 515 行）。

注意 — k*k*2k 规则是成员资格验证，不是搜索并排序：规范路由在查看候选列表之前已经完全由 (norm, K, ndims) 决定，循环只确认这个确定性路由确实是距离层产出的六条候选之一。如果不是，那就是距离生成器与 tiebreak 规则之间的一致性失败，因此错误措辞是 "is not in its minimum route sets."。如果重新实现者的 GetDistances 与这个 ±tb 构造不一致，就会触发这个精确错误。

5. `k2k2k` 路径 — `this[+0xe8] == 2`，按数量分派

对 k*2k*2k，规则按候选数量分派，而候选数量就是 vertex 的几何类别：4 = corner，3 = mid，2 = edge。这些数量比较已由反编译验证：candidates.size()（a4[1]）与 &dword_0 + 2（==2，第 376 行）、+3（==3，第 459 行）、+4（==4）比较；任何其他数量都会落入 Invalid-vertex。

function TieBreak_k2k2k(K, vertex, candidates):
    n = this[+0x8]                                   // ndims
    switch candidates.size():                           // not separate symbols —
        case 4:  return Corner(K, n, vertex, candidates)   // inline block @ line 592
        case 3:  return Mid(K, n, candidates)              // inline block @ line 459
        case 2:  return Edge(K, vertex, candidates)        // inline block @ line 376
        default: goto InvalidVertex
```text

### 5.1 Corner（4 个候选）

corner 规则首先找到**行走距离较短的维度**，即某个维度 `d`，所有候选在该维度上的 `|coord|` 最大值 `< K`；然后按从 vertex 计算出的 parity **旋转**到另一个维度 `d'`，并选择 `d'` 坐标等于 `±K` 的候选（符号由同一个 parity bit 决定）。

```c
function Corner(K, n, vertex, candidates):           // inline block @ line 592
    // 1. find winning dim d: max|cand.coord(d)| over candidates < K
    for d in 0 .. n-1:                                // lines 622-659
        max_abs = 0
        for cand in candidates:                       // lines 633-651
            max_abs = max(max_abs, |cand.coord(d)|)
        if max_abs < K: break                          // line 653 — dim d wins (v33 = d)
    else:
        return Error("…corner vertex %s, did not find a dimension whose "
                     "travelling distances are all less than tiebreaking length %d…")
                     // 0xa01debc, source line 610
    // 2. rotate to d' by the per-other-dim parity
    parity = XOR over dims != d of ( (vertex.coord(dim) >> 1) & 1 )   // v76, line 764
    d'     = (d + parity + 1) mod n                    // line 665: (v33 + v76 + 1) % v75
    // 3. select candidate whose coord(d') == ±K (sign by vertex parity bit)
    target = (vertex.parity & 1) ? -K : +K             // lines 670-672 (v102 & 1; +K when parity even)
    for cand in candidates:                            // lines 676-...
        if cand.coord(d') == target: return OK(cand)
    return Error("…corner vertex %s, expected distance %d on dimension %d "
                 "is not found among the candidates.")  // 0xa01dfed, source line 602

反编译锚点：第 643-647 行的 max|coord| 累积，第 653 行的 max_abs < K 维度胜出测试（v35 < (int)v117），第 764 行的 parity v76 ^= ((unsigned)v108 >> 1) & 1，第 665 行的旋转 (v33 + v76 + 1) % v75，以及第 670-672 行的 (v102 & 1) ? -K : +K 目标。两个 corner 错误逐字节精确：找不到胜出维度 → 0xa01debc（MakeErrorImpl<13>，源第 610 行）；旋转后找不到匹配候选 → 0xa01dfed（源第 602 行）。

怪癖 — corner 规则不会选择短维度 d 本身，而是选择 d' = (d + parity + 1) mod n，即一个由其他维度 second bit 的 parity 选出的不同维度。这个确定性旋转用于消除接触两个 2K 轴的 corner 芯片中哪个双倍轴承载 +K seam 的歧义：天真的“选择短维度”重新实现会把 corner 路由到错误轴上，并选择另一条（仍然距离合法的）候选，从而静默产生一个不同但合法的路由表，不再匹配 reference cache。该旋转所消歧的确切物理对角线已追踪到其算术，但尚未绑定到 (+K,+K) seam orientation，置信度 MEDIUM。

5.2 Edge（2 个候选）和 Mid（3 个候选）

function Edge(K, vertex, candidates):                // count==2 (a4[1] == &dword_0+2)
    cand = candidates[0]                              // v50
    for d in 0 .. ndims-1:                            // lines 382-457
        target = (vertex.parity & 1) ? -K : +K        // v51 = -K default, flipped to +K when (v115 & 1)==0
        if cand.coord(d) == target: return OK(cand)    // lines 406-413
    goto InvalidVertex                                 // line 457 — no match falls to 0xa085c3a (§6)
    // (a GetCoordinate failure inside the loop propagates that status
    //  with AddSourceLocationImpl at source lines 677 / 678, lines 395 / 450)

function Mid(K, candidates):                          // count==3 (a4[1] == &dword_0+3)
    for cand in candidates[0..2]:                      // up to 3 candidates, lines 461-561
        max_abs = max over cand's dims of |coord|      // v46 / v63 / v89
        if max_abs < K: return OK(cand)                // first under K wins (LABEL_163)
    return Error("…edge vertex %s, did not find a route whose traveling "
                 "distances are less than tiebreaking length %d for all "
                 "dimensions among its candidates.")   // 0xa01ddf5, source line 651
```text

**edge** 路径（count==2）遍历 `candidates[0]` 的各维度，并在 `coord(d) == ±K` 时选择它，符号由 vertex parity bit 决定（`v115 & 1`，第 407 行；`v51 = -(int)v117`，第 381 行）。若没有维度匹配，该路径会落入通用 **Invalid vertex** 错误（`0xa085c3a`，第 457 行 `goto LABEL_117`），*不是* `0xa01ddf5` 字符串；这里出现的 `677` / `678` 源行是 `AddSourceLocationImpl` 包装器，只会在 `GetCoordinate` 本身出错时触发。**mid** 路径（count==3）最多遍历三个候选，并返回第一个最大 `|coord|` 低于 `K` 的候选（`v46`/`v63`/`v89 < K`，`LABEL_163`）；只有当*没有*候选合格时，它才会在源第 651 行发出 `0xa01ddf5` 的 "edge vertex" 字符串（扫描中的 `GetCoordinate` 失败会在源第 643 行传播）。

| 数量 | vertex 类别 | 规则（规范路由） | 成功 | 失败字符串 / 行 |
|---|---|---|---|---|
| 6 | （任意，`k*k*2k`） | 构造对称 `±tb` 路由，断言 ∈ candidates | copy + `*a1=1` | `0xa000dba` / 515 |
| 4 | corner | 维度 `d`：`max\|cand\|<K`；旋转 `d'=(d+parity+1)%n`；`coord(d')==±K` | OK(cand) | `0xa01debc` 610；`0xa01dfed` 602 |
| 3 | mid | ≤3 个候选中第一个 `max\|cand\|<K` ⇒ select | OK(cand) | `0xa01ddf5`（"edge vertex" 文本）/ 651 |
| 2 | edge | `cand.coord(d)==±K`（vertex-parity 符号） | OK(cand) | 落入 `0xa085c3a`（Invalid vertex） |
| — | invalid | — | — | `0xa085c3a` / Invalid vertex |

（`tb`/`K` = `std::min` 维度大小 = "tiebreaking length" = `v117`。`parity` = 在其他维度上对 `((vertex.coord(otherdim) >> 1) & 1)` 做 XOR。）

> **易错点 —** vertex 类别**不是**芯片携带的属性，而是 `candidates.size()`，即*距离生成器*为该 vertex 产出的等最小路由数量（`k*k*2k` 为 6；`k*2k*2k` 上 corner/mid/edge 为 4/3/2）。如果重新实现让 `GetDistances` 发生轻微偏差，比如对 reference 视为 corner 的芯片发出 3 个候选，就会分派到*错误*子规则，并选择不同路由或触发错误错误。因此 corner/edge/mid 分类存在于距离生成器中，而 `GetTiebreak` 是它的严格消费者。决定数量的逐 orientation 距离公式已定位（`GetDistances` `0x20b420e0` 通过 `CheckBoundary` `0x20bf5800` + `GetDistanceFromOrigin` `0x20b42980`），但尚未字段级解码，见 §8。

---

## 6. Invalid-vertex fallthrough

任何形状 `∉ {1, 2}`（到达此 vtable slot 的非 twist 拓扑，或本应由 `Init` 归约的判别量为 `3` 的 `k*2k*nk`）——或者在 `k*2k*2k` 内部候选数量 `∉ {2, 3, 4}`，或者 count==2（edge）候选的各维都没有命中 `±K`——都会落入通用错误（`LABEL_117`，第 345 行的 `FormatPack`）：

```c
    // shape not 1 or 2, or unsupported candidate count
    return Error("Invalid vertex %s in topology %s for algorithmic "
                 "tiebreaking rule.")                  // 0xa085c3a, line 345

错误会通过拓扑的虚 Format 字符串化 topology（第 339 行，+0x28 处的 (*(*(_QWORD *)this + 40))(…) vtable 分派）。这是兜底错误；在正确分类的 twist 中不可达，因此若判别量 3 到达这里，就表明 Init（§2）中的 DropDimension 归约没有运行。

7. tiebreak 如何消除 `K_2K_2K` 组分配歧义

k*2k*2k tiebreak（§5）使 K_2K_2K 路由表变得确定且 seam 一致。collective 半边通过把设备 ID 经由对角 (+K, +K) twist 折叠（GetReplicaPair3DOnTwistedTorus，其中 num_max_dims == 2），构建 K_2K_2K reduce-scatter / all-gather replica groups；这个折叠告诉每个 core 与谁规约。但两个成组芯片之间的字节必须穿过物理 ICI 链路，在双倍轴 twist 上，一个 (src, dst) 对经常有多条等最小路径，每个 2K 轴一条。如果路由表任意选择，同一 replica group 中的两颗芯片可能穿过不同链路集合，重新引入 twist 本来要打破的链路环。

GetTiebreak 的 k*2k*2k 规则消除了这种自由度。corner 规则的 parity rotation d' = (d + parity + 1) mod n 会确定性选择接触两个双倍轴的 corner 芯片上，哪个 2K 轴承载 +K seam；这是 replica-group 折叠在设备 ID 空间作出的同一个对角选择，现在在芯片坐标空间中执行。edge 和 mid 规则把 ±K 路由固定在单个相关双倍轴上。由于规则是 vertex 和 K 的纯函数，K_2K_2K 组中的每颗芯片都会以相同方式解析平局，因此 per-link 路由表是一条连贯的 twisted ring，而不是顺时针与逆时针 seam 的混合。随后所选规范路由会被 memoised（this[+0xe0] cache-enabled，通过 GetDistanceFromCache 0x20b40fa0），并交给 emission 层。

注意 — 这是 collective 侧 K_2K_2K 组构造的 routing 侧镜像。replica-group 构造器使用 R = 2K（两个双倍轴）并通过 (+K,+K) 对角折叠成员；GetTiebreak 独立地从候选数量和 parity rotation 为路由表重新推导相同的对角 seam 选择。二者必须一致：如果重新实现者用一种 seam 约定构建 group，又用另一种 seam 约定构建 route，就会得到一个伙伴关系与链路相矛盾的调度。见 2 阶段 Replica-Group 构造（R = 2K 双倍轴 prologue）。

8. 尚未解决的问题

候选路由生成器。 GetTiebreak 消费等最小路由的 vector<Coordinates>，并且只从其大小读取 vertex 类别（6 / 4 / 3 / 2）。负责按 orientation 决定该数量的生成器，即 GetDistances（0x20b420e0，通过 CheckBoundary 0x20bf5800 和 GetDistanceFromOrigin 0x20b42980 行走逐轴 wrap mask），已经定位，但其逐 orientation 的 n 倍距离公式尚未字段级解码。这是剩余的字面 nK 距离数学。MEDIUM。见 Get Distances。
k*2k*nk（shape == 3）字面 nK 处理。 已确认它从不会到达 GetTiebreak 分支（没有 this[+0xe8]==3 分支；Init 的 DropDimension 会归约它）。GetDistance / UnboundedWalk（0x20b40680）中的 n > 2 距离处理，即长轴上的 +K-mod-nK seam，尚未单独解码。MEDIUM。
corner parity-rotation 几何。 d' = (d + parity + 1) mod n 且 parity = XOR((coord>>1)&1)（对其他维度）已由字节确认，但为什么是这个特定旋转（它在两个双倍轴上消除哪条物理对角线的歧义，并与 replica-group 折叠的 (+K,+K) seam orientation 关联）只追踪到算术层面，尚未追踪到几何意图。MEDIUM。
route-cache 路径。 GetDistanceFromCache（0x20b40fa0）+ kRouteCacheSet（0x22011f88）—— tiebreak 结果大概在这里以 Coordinates 对为键 memoised，但 cache key/value 格式及其与 emission 层的交互尚未解码。LOW。见 route cache codec。

9. 函数与字符串映射

符号 / 字符串	地址	作用
`TwistedTorusTopology::GetTiebreak`	`0x20b41320`	tiebreak 规则；入口、`std::min` K、形状分派
`TwistedTorusTopology::Init`	`0x20b3e5e0`	设置 `this[+0xe8]` 形状判别量（1/2/3）
`TwistedTorusTopology::GetDistances`	`0x20b420e0`	候选路由生成器（vertex 类别来源）
`TwistedTorusTopology::GetDistanceFromOrigin`	`0x20b42980`	输入候选数量的逐轴距离行走
`TwistedTorusTopology::GetDistanceFromCache`	`0x20b40fa0`	路由 memoisation（`this[+0xe0]` cache bool）
`Coordinates::GetCoordinate`	`0x20c0b800`	`[+0]`=ndims，`[+4+4·i]`=coord
`Coordinates::ManhattanNorm`	`0x20c0ba00`	`Σ\|coord\|` — `kk2k` `tb` 输入
`Coordinates::operator==`	`0x20c0bac0`	候选 ↔ 期望路由比较（步幅 28）
`"…kk2k twisted torus vertex %s, expected distance %s is not in its minimum route sets."`	`0xa000dba`	kk2k 不在集合中错误（第 515 行）
`"…k2k2k twisted torus's edge vertex %s, did not find a route whose traveling distances are less than tiebreaking length %d…"`	`0xa01ddf5`	"edge vertex" 错误，由 count==3（mid）路径发出（源第 651 行）
`"…k2k2k twisted torus's corner vertex %s, did not find a dimension whose travelling distances are all less than tiebreaking length %d…"`	`0xa01debc`	corner no-dim 错误（源第 610 行）
`"…k2k2k twisted torus's corner vertex %s, expected distance %d on dimension %d is not found among the candidates."`	`0xa01dfed`	corner no-match 错误（源第 602 行）
`"Invalid vertex %s in topology %s for algorithmic tiebreaking rule."`	`0xa085c3a`	shape∉{1,2} / bad-count fallthrough
`"TPU twisted torus only supports kk2k and k2k2k and k2knk slice shapes."`	`0xa020458`	shape-support 分类器字符串

交叉引用

Twist 算法（本节）

Twisted Torus — 章节地图 — 子系统地图；K/2K 形状门控和双类拆分（routing vs collective）
Shape Folds — 此 tiebreak 在芯片坐标空间镜像的 K_K_2K / K_2K_2K / K_2K_NK 坐标折叠目录
2 阶段 Replica-Group 构造 — tiebreak 使其 seam 与路由一致的 K_2K_2K（R = 2K）reduce-scatter / all-gather 组
GetReplicaPair3DOnTwistedTorus — 设备 ID 空间中的 (+K,+K) 对角折叠；此 routing 侧规则的 collective 侧类比
TwistedTorusND::BuildStrategy — 逐 color 的 K↔2K seam phase order

相邻章节

Get Distances — 产生此规则所消歧等最小候选集的 twist-adjusted distance vector
Get Static Path — 消费所选规范路由的 route-table 构造
返回索引

GetTiebreak ​

摘要 ​

1. GetTiebreak 所处位置 ​

3. Comparator：tiebreaking length K ​

5. k*2k*2k 路径 — this[+0xe8] == 2，按数量分派 ​

5.2 Edge（2 个候选）和 Mid（3 个候选） ​

7. tiebreak 如何消除 K_2K_2K 组分配歧义 ​

8. 尚未解决的问题 ​

9. 函数与字符串映射 ​

交叉引用 ​

Twist 算法（本节） ​

相邻章节 ​