DOR
Torus/Mesh 上按维度顺序转发如何保证无死锁
核心要点：
- 按固定维度顺序 X→Y→Z 逐维转发，每维独立完成
- Mesh 天然无死锁；Torus 需 dateline 虚通道打破环绕依赖
- 路径唯一、无路由表、转发开销极低（坐标减法）
- 集合通信按维度分解时与 DOR 完美对齐（Google TPU v4/v5 实战）
DOR（Dimension-Order Routing）是 Torus / Mesh 上的确定性静态路由策略：报文按固定维度顺序逐维转发，到达目标维度坐标后转入下一维度。维度顺序全网一致，这是无死锁保证的基础。
DOR 如何把多维路由问题降为一维问题？
核心问题：在 3D Torus 上从 $(x_s, y_s, z_s)$ 到 $(x_d, y_d, z_d)$，DOR 怎么避免维度间的耦合？
坐标寻址与维度分解
在 $d$ 维 Torus 或 Mesh 拓扑中，每个节点的地址表示为 $d$ 维坐标 $(x_0, x_1, \ldots, x_{d-1})$。DOR 将端到端路由问题分解为 $d$ 个独立的一维路由问题——依次在每个维度上移动，直到该维度坐标与目标一致，然后进入下一维度。
以 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
维度顺序固定且全网一致——所有交换机都按相同的维度顺序转发，这是 DOR 无死锁保证的基础。
Torus 上的方向选择
Torus 的每个维度首尾相连形成环（大小为 $N_k$），在维度 $k$ 内存在两条路径（顺时针和逆时针）。DOR 选择跳数较少的方向：
$$\begin{equation} \text{direction}_k = \begin{cases} +1 & \text{if } (x_d^{(k)} - x_s^{(k)} + N_k) \bmod N_k \le N_k/2 \\ -1 & \text{otherwise} \end{cases} \label{eq:route-dor-torus-direction} \end{equation}$$维度 $k$ 上的跳数为：
$$\begin{equation} h_k = \min\left((x_d^{(k)} - x_s^{(k)} + N_k) \bmod N_k,\; (x_s^{(k)} - x_d^{(k)} + N_k) \bmod N_k\right) \label{eq:route-dor-dim-hops} \end{equation}$$总路径长度等于各维度跳数之和：
$$\begin{equation} H = \sum_{k=0}^{d-1} h_k \label{eq:route-dor-total-hops} \end{equation}$$在 Mesh 中，每个维度没有环绕链路，方向唯一（从 $x_s^{(k)}$ 直接走向 $x_d^{(k)}$），跳数为 $|x_d^{(k)} - x_s^{(k)}|$。
转发流程是怎样的？
完整决策流程
报文到达交换机，当前坐标 (c0, c1, ..., c_{d-1})，目标坐标 (d0, d1, ..., d_{d-1})
|
v
从维度 k=0 开始检查
|
v
c_k == d_k ?
|
+-- 是 --> k = k+1，检查下一维度
| （若 k == d，报文到达目的地，交付本地）
|
+-- 否 --> 计算维度 k 上的方向（公式 eq:route-dor-torus-direction）
沿该方向转发到下一跳
（报文头中携带目标坐标，无需修改）
整个过程是无状态的——交换机仅根据报文头中的目标坐标和自身坐标做减法比较，不需要路由表查找，也不需要感知网络拥塞状态。
数值示例
场景：4x4x4 Torus，从 $(0, 0, 0)$ 到 $(2, 3, 1)$。
由 $\eqref{eq:route-dor-dim-hops}$ 计算各维度跳数：
- X 维度：正向 $(2-0) \bmod 4 = 2$，反向 $(0-2+4) \bmod 4 = 2$，取 $\min(2, 2) = 2$ 跳
- Y 维度：正向 $(3-0) \bmod 4 = 3$，反向 $(0-3+4) \bmod 4 = 1$，取 $\min(3, 1) = 1$ 跳（反向更短）
- Z 维度：正向 $(1-0) \bmod 4 = 1$，反向 $(0-1+4) \bmod 4 = 3$，取 $\min(1, 3) = 1$ 跳
由 $\eqref{eq:route-dor-total-hops}$ 总路径长度 = $2 + 1 + 1 = 4$ 跳。
逐跳路径：
(0,0,0) --X--> (1,0,0) --X--> (2,0,0) [X 维度完成]
--Y--> (2,0,0) --Y--> (2,3,0) [Y 维度: 反向1跳, 从0经环绕到3]
--Z--> (2,3,0) --Z--> (2,3,1) [Z 维度完成]
注意 Y 维度选择反向（从 0 经环绕链路到 3），仅需 1 跳而非正向的 3 跳。
平均路径长度
在 $d$ 维 Torus 中（每维大小 $N$），两个随机节点在维度 $k$ 上的期望跳数为：
$$\begin{equation} \mathbb{E}[h_k] = \begin{cases} N/4 & \text{(Torus, } N \text{ 为偶数)} \\ (N^2-1)/(4N) & \text{(Torus, } N \text{ 为奇数)} \\ (N^2-1)/(3N) & \text{(Mesh)} \end{cases} \label{eq:route-dor-avg-hops} \end{equation}$$$d$ 维总期望路径长度 $\mathbb{E}[H] = d \cdot \mathbb{E}[h_k]$。例如 4x4x4 Torus 的平均路径长度 = $3 \times 4/4 = 3$ 跳。
DOR 为什么不会死锁？
DOR 的无死锁性质依赖拓扑类型。
Mesh 上：天然无死锁
Mesh 各维度无环绕链路，维度顺序约束可消除所有循环等待：
- 所有报文先在维度 0 移动，再在维度 1 移动，...
- 不存在"A 等待 B 释放 X 方向资源，B 等待 A 释放 Y 方向资源"的场景
证明思路：为每条链路分配一个全序标号——维度 $k$ 的所有链路的标号大于维度 $k-1$ 的所有链路。DOR 保证报文只沿标号递增方向申请资源，因此不可能形成循环等待（Coffman 条件的"循环等待"被打破）。
Torus 上：需要 Dateline 虚通道
Torus 每个维度首尾环绕，环绕链路引入新的通道依赖环路，单纯 DOR 在 Torus 上不保证无死锁。
问题：在维度 $k$ 的环上，报文可能沿环绕方向从节点 $N-1$ 回到节点 $0$，形成资源申请的环路：节点 0 等待节点 1 的缓冲 -> 节点 1 等待节点 2 -> ... -> 节点 $N-1$ 等待节点 0（通过环绕链路）。
Dateline 机制：
- 每个维度在坐标 0 处的环绕链路设置一条 dateline
- 每个维度配置 2 条虚通道（VC0、VC1）
- 报文初始使用 VC0；当经过 dateline 时强制切换到 VC1，此后不再返回 VC0
- VC0 和 VC1 各自内部无环路（dateline 切断了环绕依赖），两层 VC 之间单向依赖（VC0 -> VC1），不构成循环
虚通道开销：$d$ 维 Torus 需要每维 2 条虚通道，总共 $2d$ 条 VC。3D Torus 需要 6 条 VC——这是可接受的硬件开销[1]。
死锁避免的一般理论
DOR + dateline VC 只是死锁避免技术的一个特例。互联网络死锁避免有更广泛的理论框架，理解这些理论有助于设计非 DOR 路由（如 Torus 上的自适应路由、不规则拓扑的路由）。
1. Coffman 条件：网络死锁的必要条件（与操作系统死锁条件一致）：
- 互斥（mutual exclusion）：缓冲区一次只能被一个 packet 占用
- 持有并等待（hold and wait）：packet 占用缓冲的同时申请下一跳缓冲
- 不可抢占（no preemption）：缓冲不会被强制释放
- 循环等待（circular wait）：存在缓冲依赖的环路
打破任一条件即可避免死锁。互联网络中通常打破"循环等待"——这正是 DOR 的策略（按维度有序申请）。
2. Turn Model（Glass & Ni, 1992）[2]：
通过禁止特定的"转弯"（turn）打破循环依赖。以 2D Mesh 为例，4 个方向产生 8 种可能转弯，每个 cycle 需要至少 4 个转弯，因此只需要禁止其中 1 个就能打破所有 cycle。代表算法：
| 模型 | 禁止的转弯 | 路径自由度 |
|---|---|---|
| XY routing | 所有 Y→X 转弯 | 退化为 DOR |
| West-First | 仅禁止 N→W 和 S→W | 高（仅去西方向有约束） |
| North-Last | 仅禁止 N→E 和 N→W | 高 |
| Negative-First | 仅禁止往负向的转弯 | 中 |
@tbl-route-dor-turn-models Turn Model 变体
West-First 等"部分约束"模型保留了远多于 XY routing 的路径多样性，同时不需要虚通道——这是 Mesh 上无 VC 自适应路由的基础。
3. Duato 协议（Duato, 1993）[3]：
Duato 给出了最小化 VC 数量的自适应路由死锁避免充分条件：
给定路由函数 $\mathcal{R}$ 使用的虚通道集合，若存在该集合的子集 $\mathcal{R}_{\text{esc}}$（escape channels）满足"任意 packet 都能在 $\mathcal{R}_{\text{esc}}$ 内找到到达目标的路径"，且 $\mathcal{R}_{\text{esc}}$ 自身无循环依赖，则整个路由系统无死锁。
直观含义：允许大部分流量走自适应通道（甚至产生循环依赖），但保留一组"逃生通道"作为后备——packet 在自适应通道堵塞时可以 fall back 到逃生通道，从而打破死锁。
应用：Torus 自适应路由（如 Cray T3D/T3E）按此原理设计——大部分时间走自适应通道获得均衡，少部分时间走 DOR escape channel 避免死锁。比单纯 DOR 多 1 条 VC（escape channel），换来路径多样性大幅提升。
4. Bubble Flow Control（Carrión et al., 1997）[4]：
针对 Torus 的另一种思路：在每个环上保留至少 1 个空闲缓冲（"bubble"），保证任意 packet 都能继续前进。不需要虚通道，仅靠流控规则就避免死锁。代价：缓冲利用率上限略低（少 1 个 slot 可用）。
应用：BlueGene/L 的 Torus 网络采用 bubble flow control。
选型比较
| 技术 | VC 数 | 路径多样性 | 工程复杂度 | 适用拓扑 |
|---|---|---|---|---|
| DOR（XY/Dimension-Order） | 1 + dateline（Torus 2） | 低 | 低 | Torus / Mesh |
| Turn Model | 1（多数变体） | 中-高 | 中 | Mesh（无环绕） |
| Duato + Escape VC | 自适应 + 1 escape | 高 | 中-高 | 任意（Torus / Dragonfly / 不规则） |
| Bubble FC | 0 | 中 | 中 | Torus |
@tbl-route-dor-deadlock-techniques 死锁避免技术对比
DOR 是"最简单 + 路径多样性最低"的端，Duato + Escape VC 是"复杂度可接受 + 路径多样性最高"的端，工程选择依工作负载特性而定。
DOR 如何配合集合通信的维度分解？
DOR 为集合通信按维度分解提供了天然基础。以 3D Torus 上的 AllReduce 为例：
- X 维度 AllReduce：每行节点做 Ring AllReduce，所有行并行
- Y 维度 AllReduce：每列节点做 Ring AllReduce，所有列并行
- Z 维度 AllReduce：每纵列节点做 Ring AllReduce，所有纵列并行
每轮只在单维度通信，避免跨维度竞争——维度 $k$ 的 Ring 通信不占用维度 $k' \neq k$ 的链路。
这是 Google TPU 集群在 3D Torus 上高效执行 AllReduce 的核心机制：XLA 编译器将 TP/DP/PP 分配到对应 Torus 维度，路由在编译时完全确定，无运行时开销。
维度分解的通信量等价性：将 $d$ 维 AllReduce（$N^d$ 个节点）分解为 $d$ 轮单维度 Ring AllReduce（每轮 $N$ 个节点），总通信量与直接在 $N^d$ 个节点上执行等价，但避免了跨维度链路竞争，实际吞吐显著更高。
DOR 的性能特性如何？
| 指标 | 值 |
|---|---|
| 路径确定性 | 完全确定（相同源/目的对，路径唯一） |
| 死锁风险 | 无（Mesh 天然无死锁；Torus 需 dateline VC） |
| 有效带宽利用率 | 85-92%（通信模式与维度对齐时） |
| 延迟可预测性 | 最高（路径长度由坐标差唯一确定） |
| 路径多样性 | 低（每个源-目的对只有一条路径） |
| 转发开销 | 极低（坐标减法，无需路由表查找） |
@tbl-route-dor-01 性能特性：指标、值
何时该用 DOR，何时不该？
适用场景：
- Torus / Mesh 多维拓扑，特别是 2D/3D Torus
- 需要确定性延迟的工作负载
- 集合通信 pattern 能够与拓扑维度对齐的场景
- 代表系统：Google TPU v4/v5/v6/Ironwood（3D Torus + DOR）[5]
局限：
- 路径多样性低：每个源-目的对只有一条路径，网络利用率受单条路径带宽限制
- 维度竞争：若工作负载的通信模式不与维度对齐（如跨维度的 AllToAll），会在某个维度产生热点
- 故障容错弱：绕过故障节点需要修改维度路由逻辑，不如 ECMP 灵活
- 不适合非规则拓扑：DOR 依赖拓扑的规则维度结构，Fat-tree、Dragonfly 等无法使用
选型建议：
- 拥有 Torus 拓扑且工作负载与维度对齐：DOR 是最优选择
- 拓扑不规则或需要高路径多样性：使用 ECMP 或自适应路由
- 需要在 Torus 上最大化带宽：可结合 OCS 动态重配拓扑，使 Twisted Torus 的 bisection bandwidth 提升 70%
Takeaway
| 知识点 | 核心结论 |
|---|---|
| DOR 选路 | 按固定维度顺序逐维转发；Torus 每维取 $\min$（正向，反向） 跳数 |
| Mesh 无死锁 | 维度全序约束打破循环等待（Coffman 条件） |
| Torus 死锁规避 | dateline + 2 VC，过 dateline 切换 VC，阻断环绕依赖 |
| 替代死锁理论 | Turn Model / Duato Escape VC / Bubble FC 给更高路径多样性 |
| 集合通信对齐 | $d$ 维 AllReduce 分解为 $d$ 轮单维 Ring，避免跨维度链路竞争 |
| 主要局限 | 路径唯一、路径多样性低；通信模式不对齐时维度热点 |
| 代表系统 | Google TPU v4/v5/v6/Ironwood（3D Torus + DOR） |
参考资料
- Dally & Seitz, Deadlock-Free Message Routing in Multiprocessor Interconnection Networks, IEEE TC, 1987. https://doi.org/10.1109/TC.1987.1676929
- Glass & Ni, The Turn Model for Adaptive Routing, ISCA 1992.
- Duato, A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks, IEEE TPDS, 1993.
- Carrión et al., A Flow Control Mechanism to Avoid Message Deadlock in k-ary n-cube Networks, HiPC 1997.
- Jouppi et al., TPU v4: An Optically Reconfigurable Supercomputer, ISCA 2023. https://arxiv.org/abs/2304.01433
延伸阅读
- Dally & Towles, Principles and Practices of Interconnection Networks, Morgan Kaufmann, 2003. https://dl.acm.org/doi/book/10.5555/572478