GetDistances
本页所有地址均适用于
libtpu-0.0.40-cp314-cp314-manylinux_2_31_x86_64wheel 中的libtpu.so（构建libtpu_lts_20260413_b_RC00，build-id89edbbe81c5b328a958fe628a9f2207d）。该二进制带有完整 C++ 符号；.textVMA == 文件偏移，因此下面每个0x20b…地址都是 VMA。其他版本会有所不同。
摘要
GetDistances 是 slice-builder twisted torus 的候选路由生成器：给定源坐标和目标坐标，它返回二者之间所有最小曼哈顿距离路由，形式为有符号逐轴位移向量的 vector<Coordinates>。它是路径生成器（GetStaticPath、RandomizedToroidalWildFirstPaths）消费的几何核心：它们拿到一个距离向量，选择一个轴顺序，并把它打包成 hops。本页负责距离端：TwistedTorusTopology::GetDistances @ 0x20b420e0（生成器）、TwistedTorusTopology::GetDistanceFromOrigin @ 0x20b42980（逐轴 toroidal-with-twist 距离），以及让 torus 成为 twisted 而非 plain 的 seam table。
熟悉的参考系是教科书式环面距离：在大小为 S 的环上，两点之间的距离是 min(forward, backward)，其中一个方向会跨过 seam（±S）。3-D torus 对每个轴独立执行这一点；选择在哪些轴上绕回就是符号选择，因此一个节点最多有 2^(#wrappable-axes) 条候选路由，并且最短路可能在其中多条之间并列。GetDistances 精确枚举这个幂集：它为每个组合构建一个 Polarity 向量（POSITIVE = 向前 wrap，NEGATIVE = 向后 wrap，NONE = 不 wrap），通过 GetDistanceFromOrigin 计算得到的位移，取 ManhattanNorm，并保留所有并列最小的位移。返回集合的大小就是 vertex class — corner / edge / mid — 供 twist tiebreaker（twist/get-tiebreak）分派使用。
与 plain torus 唯一的差异是 twist seam。在一个加倍（长度 2K）轴上，跨越 wrap 边不会回到伙伴轴上的相同位置，而是会偏移 +K，也就是 replica-group 构造同样使用的 (+K,+K) 对角折叠。GetDistanceFromOrigin 用逐 wrap 的 seam carry 串起这一点：当某个轴 wrap 时，它会把逐轴偏移向量（seam[d]，来自 this+0x108）加入运行中的累加器，并按每个轴大小取模折叠。这就是完整的 nK-shape 故事：长 nK 轴只是另一个具有 dimsize = nK 和自身 seam 条目的维度；没有特殊 case 分支，这也是 tiebreaker 不需要特殊分支的原因。
对重新实现而言，契约是：
- 候选枚举（
GetDistances）：wrap-mask popcount、2^m上限且≥2但<2时设为1的 Polarity 循环、最小曼哈顿 keep-all-ties 规则，以及向vector<Coordinates>的有序插入。 - 逐轴 toroidal-with-twist 距离（
GetDistanceFromOrigin）：有符号delta = c − accum[d]、由 Polarity 门控的±dimsize[d]wrap、wrap 触发条件，以及 seam carryaccum[j] = (seam[d][j] + accum[j]) mod dimsize[j]。 - seam table（
this+0x108）：在Init中构建的vector<vector<int>>，每轴一个内部 vector，编码加倍轴 wrap 在伙伴轴上诱发的+K对角偏移。
| 生成器 | TwistedTorusTopology::GetDistances @ 0x20b420e0（vtable +0xc0） |
| 逐轴距离 | TwistedTorusTopology::GetDistanceFromOrigin @ 0x20b42980 |
| 单距离消费者 | TwistedTorusTopology::GetDistance @ 0x20b408e0（vtable +0xb8） |
| 范数 / 比较 | Coordinates::ManhattanNorm @ 0x20c0ba00 · operator< @ 0x20c0ba40 |
| Seam / 大小 / 顺序 | this+0x108 seam · this+0x10 dim-sizes · this+0x40 dim-order · this+0xf0 wrap-mask |
| Polarity 枚举 | NONE=0, POSITIVE=1, NEGATIVE=2 (accel_ssw::deepsea::proto::Polarity) |
| Coordinates | int32 ndims @+0, ≤6 int32 coords @+4..+0x18, sizeof = 0x1c |
| 源文件 | platforms/accel_ssw/deepsea/slice_builder/friends/twisted_torus_topology.cc |
注意 — 两个 vtable slot 只差一个字母，且不可互换。
vtable+0xc0是GetDistances（复数）——本页的候选集合生成器。vtable+0xb8是GetDistance（单数）——GetStaticPath调用的 cache-aware 单个距离。若相邻页面称“GetStaticPath调用GetDistances（vtable+0xb8）”，那是用复数 sibling 的名字命名单数 slot；逐字节精确的区别见 §GetDistance。
GetDistances — 候选路由生成器
用途
GetDistances(src, dst) 返回一个 StatusOr<vector<Coordinates>>：在 twisted torus 上，从 src 到 dst 达到最小曼哈顿距离的所有有符号逐轴位移向量集合。plain mesh 中每对节点只有一条最短路径；torus 中每种逐轴 wrap 选择都有一条，twist 又会让其中几种 wrap 选择在最小值上并列。该集合是下游 tiebreaker 和 path packer 的输入：生成器回答“多远，以及有多少种同样好的方式”；消费者回答“选哪一种，以及通过哪个 hop 顺序”。
入口点
TwistedTorusTopology::GetDistances (0x20b420e0) ── vtable+0xc0, candidate-set generator
├─ Topology::CheckBoundary(src) (0x20bf5800) ── line 390, both src and dst must be in-bounds
├─ Topology::CheckBoundary(dst) (0x20bf5800) ── line 391
├─ Coordinates::Subtract(src, dst) (0x20c0bfc0) ── line 394, raw mesh delta (boundary-validated)
├─ vtable[+0x98](src, raw_delta) ── line 395, normalize coord into dim range
├─ popcount(wrap_mask[this+0xf0]) ── #wrappable axes → combo count
├─ for each Polarity combination:
│ └─ GetDistanceFromOrigin(dst, polarity, wrap) ── line 444 (0x20b42980)
│ └─ ManhattanNorm (0x20c0ba00) ── keep all equal-minimum vectors
└─ vector<Coordinates>::emplace (operator< 0x20c0ba40) ── sorted insert of each tying vector算法
function GetDistances(this, src, dst): // 0x20b420e0
if !CheckBoundary(src): return Error(line 390) // 0x20b42106
if !CheckBoundary(dst): return Error(line 391) // 0x20b4211b
raw = Coordinates::Subtract(src, dst) // 0x20b42137, line 394 — plain mesh delta
base = this->vtable[0x98](src, raw) // 0x20b42174, line 395 — fold into dim range
// (base is the "from-origin" coord passed below)
wrap = this->wrap_applies // this+0xf0, vector<bool>: which axes may wrap
m = popcount(wrap.bits) // 0x20b42210 (bt; adc) — #wrappable axes
n_combos = (1 << m) < 2 ? 1 : (1 << m) // 0x20b42404 (shl; cmp $2; cmovl $1)
best = 0x7FFFFFFF // 0x20b4242e — min Manhattan norm so far
routes = [] // vector<Coordinates>
for combo in 0 .. n_combos-1: // outer bound is 1<<ndims, see GOTCHA
// Build the per-axis Polarity span for this combination.
pol = new Polarity[ndims] // 0x20b42470
for axis a in 0 .. ndims-1:
pol[a] = _bittest(combo, a) ? NEGATIVE : POSITIVE // (bit ? 2 : 1) — set for every axis
// Build the wrap-applies bitset that gates the seam carry, masking out non-wrappable axes.
wmask = bitset(ndims) // 0x20b424d0-ish
for axis a in 0 .. ndims-1:
wmask[a] = wrap[a] && pol_combo_selects(a) // only axes in this combo wrap
dc = GetDistanceFromOrigin(base, pol, wmask) // 0x20b42671, line 444
norm = ManhattanNorm(dc) // 0x20b426aa — Sigma |coord|
if norm < best: // 0x20b426af
best = norm
routes = [dc] // reset to the new minimum
else if norm == best:
routes.emplace_sorted(dc) // 0x20b4278e, operator< (0x20c0ba40)
free(pol)
return routes // |routes| == vertex class size陷阱 — 组合计数有两个不同边界，它们不是同一个值。内部 accept/reject 循环以
n_combos = max(1<<popcount, 1)为上限（当1<<m < 2，即没有轴 wrap 时设为1，0x20b42404）。但外部循环继续条件会重新加载ndims，并比较combo >= (1 << ndims)（0x20b4244c/0x20b42460区域），不是1 << m。如果重新实现让两个边界都由 popcount 驱动，在wrappable < ndims的拓扑上会迭代过少的组合；如果都由ndims驱动，则会在不可 wrap 的轴上构建冗余 Polarity span（无害——这些轴会得到pol = POSITIVE/NEGATIVE，但wmask[a] = 0，因此不会触发 wrap）。安全解读是：构建2^ndims个 Polarity span，但只有wrap_appliesbit 置位的轴才实际 wrap；重复位移向量会在 keep-all-ties 集合中折叠，因为operator<对它们给出相同排序。怪癖 — 生成器在 Polarity 循环之前会计算一个
Coordinates::Subtract（0x20b42137，第 394 行）——也就是 plain mesh delta——然后通过vtable+0x98（第 395 行）将其归一化为base坐标，作为传给GetDistanceFromOrigin的实际参数。因此，逐轴距离是从归一化 mesh delta 开始计算的，而不是直接从dst重新计算；Polarity 循环随后在其上重新引入 wrap。这与直觉上的“每个组合重新计算一次”相反，并且对精确匹配 wrap 算术很重要——GetDistanceFromOrigin看到的是已经逐轴缩减到[0, dimsize)的坐标，它的delta = c − accum会相对零初始化的累加器运行。
keep-all-ties 集合
结果是一个等最小距离路由集合，而不是单个距离。best 从 INT32_MAX（0x20b4242e）开始；严格更小的 norm 会把 routes 重置为单元素 vector，相等的 norm 会通过 Coordinates::operator<（字典序，0x20c0ba40）有序插入。因此最终 vector<Coordinates> 是按位移排序并去重的。
|routes| | Vertex class | 形状 | 消费者 |
|---|---|---|---|
6 | symmetric mid | k*k*2k | get-tiebreak corner/edge/mid 分派 |
4 | corner | k*2k*2k | （同上） |
3 | mid | k*2k*2k | （同上） |
2 | edge | k*2k*2k | （同上） |
注意 — 上面的
|routes|→ vertex-class 映射，是 twist tiebreaker 用来选择单条规范路由的计数；逐字节精确的 class 边界属于该页面。本页负责说明为什么集合具有该基数（2^(#wrap-axes)并列结构），而不是负责选择。具体计数的置信度：HIGH（锚定于 tiebreaker 页面）。
函数映射
| 函数 | 地址 | 作用 |
|---|---|---|
TwistedTorusTopology::GetDistances | 0x20b420e0 | 候选集合生成器（vtable +0xc0） |
TwistedTorusTopology::GetDistanceFromOrigin | 0x20b42980 | 逐轴 toroidal-with-twist 距离 |
Coordinates::ManhattanNorm | 0x20c0ba00 | Σ|coord|（vpabsd + horizontal add） |
Coordinates::operator< | 0x20c0ba40 | 有序集合的字典序 |
Coordinates::Subtract | 0x20c0bfc0 | 归一化之前的 plain mesh delta |
Topology::CheckBoundary | 0x20bf5800 | src 和 dst 的边界内守卫 |
GetDistanceFromOrigin — 逐轴 toroidal-with-twist 距离
用途
给定一个（归一化）坐标、一个逐轴 Polarity span 和一个 wrap-applies bitset，GetDistanceFromOrigin 会产生一个有符号位移向量：每个轴上先是直接 delta，在所选 polarity 跨越该轴 seam 时可选地用 ±dimsize wrap，并通过 twist seam carry 把加倍轴 wrap 串到伙伴轴上。这个函数区分了 twisted torus 和 plain torus；在 plain torus 上，seam table 为空，carry 是 no-op。
入口点
TwistedTorusTopology::GetDistanceFromOrigin (0x20b42980)
├─ Topology::CheckBoundary(coord) (0x20bf5800) ── line 702
├─ alloc accum[ndims], res[ndims] (memset 0) ── two int32 arrays
├─ for i in dim_order[this+0x40]:
│ ├─ Coordinates::GetCoordinate(coord, dim) ── line 713 (0x20c0b800)
│ ├─ delta = c - accum[dim] ── signed
│ ├─ Polarity[dim] gate → ±dimsize[dim] ── wrap fwd/back
│ └─ seam carry: accum[j] = (seam[dim][j]+accum[j]) % dimsize[j]
└─ Coordinates(res, ndims) ── line 713/error line 702算法
function GetDistanceFromOrigin(this, coord, pol, wmask): // 0x20b42980
if !CheckBoundary(coord): return Error(line 702) // 0x20b429a9
ndims = this->ndims // this+0x8
accum = new int[ndims]; memset(accum, 0) // 0x20b429dd — running carry per axis
res = new int[ndims]; memset(res, 0) // 0x20b429f1 — output displacement per axis
for i in 0 .. ndims-1: // walk axes in DIMENSION ORDER
dim = this->dim_order[i] // this+0x40 base, this+0x48 count (0x20b42a28)
c = coord.GetCoordinate(dim) // 0x20b42a4c, line 713
a = accum[dim] // current carry for this axis
delta = c - a // 0x20b42a74 — signed direct distance
res[dim] = delta
wrapped = false
switch pol[dim]: // [pol + dim*4] (0x20b42a81)
POSITIVE(1): if c < a: // 0x20b42a95
res[dim] = delta + dimsize[dim] // wrap forward; this+0x10 (0x20b42a9e)
wrapped = true
NEGATIVE(2): if c > a: // 0x20b42ada
res[dim] = delta - dimsize[dim] // wrap backward (0x20b42ae2)
wrapped = true
// NONE(0): res[dim] stays the direct delta
// A third wrap trigger: an axis flagged wrappable whose endpoints coincide.
if !wrapped && wmask[dim] && c == a: // 0x20b42aXX (bittest wmask; cmp c,a)
wrapped = true // seam carry still fires (degenerate wrap)
if wrapped and seam[dim] is non-empty: // seam = this+0x108[dim], stride 0x18
for j in 0 .. ndims-1: // thread the twist onto every axis
accum[j] = (seam[dim].data[j] + accum[j]) % dimsize[j] // 0x20b42b3f / 0x20b42b98
accum[dim] = c // 0x20b42b.. — this axis's carry := c
return Coordinates(res, ndims) // 0x20b42c34陷阱 — seam-carry 的模数按
dimsize[j]折叠，也就是目标轴j的大小，不是按 wrapping 轴dim的dimsize[dim]折叠。反编译非常明确：模数操作数位于j循环内，是dimsize_base[this+0x10] + 4*j（0x20b42b3f/0x20b42b98），由内层计数器索引。如果重新实现按 wrapping 轴的大小折叠整个 carry，会静默破坏每个大小不同于dim的伙伴轴；在k*2k*nk形状上，这几乎就是全部伙伴轴。逐字节精确读法是mod dimsize[j]。怪癖 — 坐标从参数（
coord/GetDistances传入的归一化base）读取，并且累加器会按维度顺序向前串起 carry：accum[dim]只有在 seam carry 已经改变伙伴轴的accum[j]之后，才会被设置为c（0x20b42b..）。因此，早序轴上的 wrap 会移动后序轴测量 delta 的参考点。这种顺序耦合就是 twist：各轴并不独立；如果不按dim_order访问，就会得到不同（错误）的位移。
为什么 nK 不需要特殊 case
对于 k*2k*nk 形状，长 nK 轴只是 dim_order 中的另一个条目，具有 dimsize = nK 和自己的 seam 向量 seam[nK_axis]。逐轴循环会像用 ±2K wrap 2K 轴一样，用 ±nK wrap 它，并通过 seam[nK_axis][j] 将 seam carry 串到伙伴轴上。这个函数里没有 nK 专用分支，相应地，tiebreaker 中也没有 [+0xe8]==3 分支：全部 nK 依赖都在这里，位于 dimsize[nK_axis] 和 seam 偏移中。唯一把 nK 轴特殊处理的位置在上面的 GetDistance 中，它可以在约化 3-D twist 上计算之前丢弃 nK 轴。
函数映射
| 函数 | 地址 | 作用 |
|---|---|---|
TwistedTorusTopology::GetDistanceFromOrigin | 0x20b42980 | 逐轴距离 + seam carry |
Coordinates::GetCoordinate | 0x20c0b800 | 从坐标读取轴 dim |
Coordinates::Coordinates(int*, n) | 0x20c0b1e0 | 从 res[] 构造结果 Coordinates |
seam table — this+0x108
用途
seam table 让 torus 成为 twisted。它是位于 this+0x108（计数 this+0x110）的 vector<vector<int>>，每个轴一个内部 vector，每个内部 vector 长度为 ndims。seam[d] 是跨越轴 d 的 wrap 边时加入运行累加器的偏移向量：在 plain torus 上它全为零（wrap 会回到相同的伙伴轴位置），但在加倍（2K）轴上，它记录 +K 对角线，也就是 replica-group 构造使用的相同 (+K,+K) 折叠（twist/get-replica-pair-3d）。
构造（在 Init 中）
function Init(this, dim_sizes, twisted): // 0x20b3e5e0
...
this->wrap_applies.assign(ndims, ...) // this+0xf0 (line 149, 0x20b3e604)
this->seam.assign(ndims, vector<int>{}) // this+0x108 (lines 167-168, 0x20b3e681)
// classify axes: an axis of even size >=2 is "doubled" (size == 2K) via K = size/2 (idiv 0x20b3ea37)
for each doubled axis d: // fill loop 0x20b3ea90
for each partner doubled axis j: // 0x20b3eaa4
this->seam[d][j] = +K // the +K diagonal twist (0x20b3eafc)
// wrap bits for doubled axes are also set here (this+0xf0[d] |= 1) (0x20b3e870-ish)注意 — 填充的结构（通过
size==2K测试检测加倍轴、向seam[d][j]写入伙伴轴，以及设置this+0xf0上的 wrap bit）已在Init中逐字节确认。精确的逐(d,j)seam 值矩阵——对于每种k*k*2k/k*2k*2k/k*2k*nk朝向，哪个轴把+K、+2K或0carry 到哪个轴——只读到了它的+K对角算术，没有按朝向穷尽制表。carry 消费者（上面的GetDistanceFromOrigin）已完整解码；供给它的表在形状上是 HIGH 置信度，在完整逐朝向值矩阵上是 LOW。请把seam[d][j]视为“轴dwrap 在轴j上诱发的 twist 偏移”，这是从Init的+K填充推断出的，而不是完整制表的常量矩阵。
| 字段 | 偏移 | 类型 | 含义 |
|---|---|---|---|
ndims | +0x8 | int32 | 轴数；约束每个逐轴循环 |
| dim-sizes | +0x10 / +0x18 | vector<int> base / count | 每轴大小 = wrap 模数 dimsize[a] |
| dim-order | +0x40 / +0x48 | vector<int> base / count | GetDistanceFromOrigin 中的轴访问顺序 |
| wrap-applies | +0xf0 / +0xf8 | vector<bool> base / bitcount | 哪些轴可 wrap；popcount → combo count |
| seam | +0x108 / +0x110 | vector<vector<int>> base / count | 每轴 +K twist 偏移列表 |
GetDistance — cache-aware 单距离 {#getdistance--the-cache-aware-single-distance}
用途
GetDistance @ 0x20b408e0（vtable +0xb8）是 GetStaticPath 和 route emitter 调用的该几何逻辑的消费者。它返回一个距离，而不是候选集合：它首先查询嵌入的预计算 route cache，只有在逐 pair cache miss 时才回退到现场 metric（上面的 GetDistances / GetDistanceFromOrigin 机制）。这里仅在边界处记录它——cache 机制位于 toroidal-route-cache，路径打包位于 get-static-path。
算法
function GetDistance(this, src, dst): // 0x20b408e0, vtable+0xb8
if this->cache_enabled: // BYTE[this+0xe0]==1 (0x20b40900)
r = GetDistanceFromCache(src, dst) // 0x20b40fa0 — embedded ToroidalRouteCache
if r is ok: return r // cache HIT → cached distance, done
// per-pair cache MISS: fall through to the live metric (0x20b40922)
if this->alt_cache_ptr && this->nK_valid: // [this+0x120]!=0 && BYTE[this+0x134] (0x20b40968)
// k*2k*nk shape: drop the nK axis, compute on the reduced 3-D twist
src' = DropDimnesion(src, this->nK_dim) // [this+0x130] (0x20b40988)
dst' = DropDimnesion(dst, this->nK_dim)
...compute on the reduced coordinates...
return the single twisted-torus distance (the GetDistances min-norm route)注意 — 逐 pair cache-miss 回落到现场 metric 的结构已逐字节确认：
GetDistanceFromCache（0x20b40fa0）返回后，GetDistance会根据StatusOrok-bit 分支（0x20b40922），并在查找不 ok 时继续到LABEL_8——现场计算。这不同于InitRouteSolution中的整体 cache miss，后者会以"Cannot find route cache: "硬错误退出，且没有现场 fallback（见toroidal-route-cache）。单个缺失的(src,dst)pair 会降级到现场 metric；slice shape 缺失的 baked cache 文件会中止 bring-up。置信度：HIGH（fall-through 分支逐字节确认；内联 live-recompute 函数体已追踪到该分支，但没有逐行解码每种 cache 类型）。陷阱 —
DropDimnesion拼写（一个字母转置）是二进制中的真实符号（accel_ssw::deepsea::slice_builder::(anonymous namespace)::DropDimnesion@0x20b3f4e0，调用于0x20b40999）。请按原样 grep；不要“修正”它。
与消费者的关系
| 组件 | 从这里取得什么 | 页面 |
|---|---|---|
GetStaticPath | GetDistance（vtable +0xb8）、单条 min-norm 距离，然后打包 hops | get-static-path |
RandomizedToroidalWildFirstPaths | torus-reduced 距离，然后执行避障多路径搜索 | randomized-toroidal-wildfirst |
| twist tiebreaker | |GetDistances result| 作为 corner/edge/mid vertex class | twist/get-tiebreak |
| route cache | 每个 (src,dst) chip-id pair 存储的 distance-vector 值 | toroidal-route-cache |
GetDistances 产生集合；消费者各自按不同策略把它约化为一条路由：确定性 DOR（GetStaticPath）、避障搜索（WildFirst），或预计算查找（cache）。seam-and-wrap 数学由三者共享；只有选择策略不同。
交叉引用
- 路由概览 — 此距离 metric 播种的 route-generation → cache → emission 流水线（阶段 1）
- Get Static Path — 确定性单路径消费者；调用
GetDistance（vtable+0xb8）并打包DirectionHops - Randomized Toroidal WildFirst — 同一 torus 距离的避障多路径消费者
- Toroidal Route Cache —
GetDistance在回退到此现场 metric 前读取的预计算 cache - Create Routing Schedule — 正交的 net_router 每步骤 DMA 调度（不同于这里的 auto-route 距离）
- Twisted Torus — twist 几何；seam table 编码的
(+K,+K)折叠，以及消费|GetDistances|的 tiebreaker