DOR 维度顺序路由
DOR（Dimension-Order Routing）是多维拓扑（Torus、Mesh）上的确定性静态路由策略：按固定维度顺序（如 X → Y → Z）逐维转发报文，每个维度的路由独立完成，到达目标维度坐标后再转向下一维度。
基本原理
在 $d$ 维 Torus 或 Mesh 拓扑中，每个节点的地址表示为 $(x_0, x_1, ..., x_{d-1})$。DOR 的路由决策：
- 检查当前维度 $k$（从维度 0 开始）
- 若当前维度坐标等于目标坐标，进入下一维度
- 否则沿当前维度朝目标方向移动一跳
以 3D Torus 中从 $(x_s, y_s, z_s)$ 到 $(x_d, y_d, z_d)$ 为例：
Phase 1: 移动 X 维度，直到 x == x_d
Phase 2: 移动 Y 维度，直到 y == y_d
Phase 3: 移动 Z 维度，直到 z == z_d
路径长度等于各维度坐标差之和（曼哈顿距离）。Torus 拓扑中，每个维度还需选择顺时针或逆时针方向（选择较短的方向）。
算法细节
无死锁保证
DOR 的无死锁性质依赖拓扑类型：
Mesh 上：天然无死锁，无需虚通道
Mesh 各维度无环绕链路，维度顺序约束可消除所有循环等待：
- 所有报文先在维度 0 移动，再在维度 1 移动，...
- 不存在"A 等待 B 释放 X 方向资源，B 等待 A 释放 Y 方向资源"的场景
- 证明：设报文在维度 $k$ 方向上移动，它不会再等待维度 $< k$ 的链路，所有等待维度 $> k$ 链路的报文都在维度 $k$ 的同侧，不构成循环
Torus 上：需要 dateline 虚通道（不可忽略）
Torus 每个维度首尾环绕，环绕链路引入新的通道依赖关系，单纯 DOR 在 Torus 上不保证无死锁。需要采用 dateline 机制：
- 每个维度设置一条 dateline（通常置于维度坐标 0 处的环绕链路）
- 报文经过 dateline 时强制切换到高优先级虚通道（VC1），此后不再使用 VC0
- 该机制打破了环形依赖链，使 Torus 上的 DOR 满足无死锁条件
参考：Dally & Seitz（1987）《Deadlock-Free Message Routing in Multiprocessor Interconnection Networks》，以及 torus.md §路由算法 中的 dateline 说明。
Torus 上的 DOR
Torus 的每个维度首尾相连形成环，DOR 在每个维度内选择最短方向（环绕距离 vs 直接距离）：
$\text{direction} = \begin{cases} +1 & \text{if } (x_d - x_s + N) \bmod N \le N/2 \\ -1 & \text{otherwise} \end{cases}$
集合通信与维度分解
DOR 为集合通信按维度分解提供了天然基础。以 3D Torus 上的 AllReduce 为例：
- X 维度 AllReduce：每行节点做 Ring AllReduce，所有行并行
- Y 维度 AllReduce：每列节点做 Ring AllReduce，所有列并行
- Z 维度 AllReduce：每纵列节点做 Ring AllReduce，所有纵列并行
每轮只在单维度通信，避免跨维度竞争。这是 Google TPU 集群在 3D Torus 上高效执行 AllReduce 的核心机制——XLA 编译器将 TP/DP/PP 分配到对应 Torus 维度，路由在编译时确定。
性能特性
| 指标 | 值 |
|---|---|
| 路径确定性 | 完全确定（相同源/目的对，路径唯一） |
| 死锁风险 | 无（维度顺序约束保证） |
| 有效带宽利用率 | 85-92%（通信模式与维度对齐时） |
| 延迟可预测性 | 高（路径长度固定） |
| 路径多样性 | 低（每个源-目的对只有一条路径） |
数值示例（4x4x4 Torus，DOR 从 $(0,0,0)$ 到 $(2,3,1)$）：
路径长度 = $|2-0| + |3-0| + |1-0| = 6$ 跳（曼哈顿距离），延迟确定性极高。
适用场景与局限
适用场景：
- Torus / Mesh 多维拓扑，特别是 2D/3D Torus
- 需要确定性延迟的工作负载
- 集合通信 pattern 能够与拓扑维度对齐的场景
- 代表系统：Google TPU v4/v5/v6/Ironwood（3D Torus + DOR）
局限：
- 路径多样性低：每个源-目的对只有一条路径，网络利用率受单条路径带宽限制
- 维度竞争：若工作负载的通信模式不与维度对齐（如跨维度的 AllToAll），会在某个维度产生热点
- 故障容错弱：绕过故障节点需要修改维度路由逻辑，不如 ECMP 灵活
- 不适合非规则拓扑：DOR 依赖拓扑的规则维度结构，Fat-tree、Dragonfly 等无法使用
选型建议：
- 拥有 Torus 拓扑且工作负载与维度对齐：DOR 是最优选择
- 拓扑不规则或需要高路径多样性：使用 ECMP 或自适应路由
- 需要在 Torus 上最大化带宽：可结合 OCS 动态重配拓扑，使 Twisted Torus 的 bisection bandwidth 提升 70%
参考资料
- TPU v4: An Optically Reconfigurable Supercomputer（ISCA 2023）- OCS + 3D Torus + DOR
- Dally & Towles, "Principles and Practices of Interconnection Networks"（Morgan Kaufmann, 2003）- DOR 理论基础