片上网络的性能和可靠性很大程度上取决于路由算法和流控机制的设计。路由算法决定了数据包从源节点到目的节点的路径选择策略，而流控机制则确保网络资源的有效利用并防止拥塞。本章将深入探讨NoC中的各种路由算法，从简单的确定性路由到复杂的自适应路由，分析死锁问题及其解决方案，并详细介绍虚拟通道、信用流控等关键技术。通过学习本章内容，您将掌握设计高效、无死锁的片上网络所需的核心知识。
确定性路由算法的特点是对于给定的源-目的节点对，路径是唯一确定的。这类算法实现简单、硬件开销小，但可能导致负载不均衡。
XY路由是2D Mesh网络中最常用的确定性路由算法。数据包首先沿X维度（水平方向）路由到目标列，然后沿Y维度（垂直方向）路由到目标节点。
算法伪代码：
function XY_route(current, destination):
if current.x < destination.x:
return EAST
else if current.x > destination.x:
return WEST
else if current.y < destination.y:
return NORTH
else if current.y > destination.y:
return SOUTH
else:
return LOCAL
特点分析：
| 延迟公式：对于Manhattan距离为d的两节点，跳数 = | Δx | + | Δy |
YX路由与XY路由相反，先沿Y维度路由，再沿X维度路由。这种算法可以与XY路由结合使用，通过交替使用来平衡网络负载。
YX路由示意图（4x4 Mesh）：
Source (0,0) → Destination (3,2)
YX路径：
(0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (3,2)
↑Y ↑Y →X →X →X
XY路径对比：
(0,0) → (1,0) → (2,0) → (3,0) → (3,1) → (3,2)
→X →X →X ↑Y ↑Y
West-First是部分自适应路由算法，属于Turn Model的一种。基本规则是：如果需要向西路由，必须首先完成所有向西的移动。
Turn Model基础： 在2D Mesh中，有8种可能的转向：
West-First禁止两个转向：EN和NW，从而避免死锁。
West-First决策树：
1. 如果目的地在西边：
- 必须先向西路由到目标列
2. 到达目标列后：
- 可以自适应选择向北或向南
3. 如果目的地在东边：
- 可以自适应选择先向东或先向南/北
自适应度分析：
自适应路由算法根据网络状态动态选择路径，能够绕过拥塞区域和故障节点，提高网络性能。
Odd-Even路由基于Turn Model，通过限制在奇数列和偶数列的不同转向来避免死锁。
核心规则：
Odd-Even转向限制示意：
偶数列(0,2,4,...)：
N
↑
W ← · → E 禁止：E→N, E→S
↓
S
奇数列(1,3,5,...)：
N
↑
W ← · → E 禁止：N→W, S→W
↓
S
自适应性分析：
从(0,0)到(3,3)的可能路径数：
- XY路由：1条路径
- Odd-Even路由：6条路径（部分受限）
- 完全自适应：20条路径（C(6,3)）
完全自适应路由允许使用所有最短路径，需要额外机制防止死锁。
Duato’s Protocol： 将虚拟通道分为两类：
虚拟通道分配：
总共4个VC：VC0, VC1, VC2, VC3
- VC0：逃逸通道（XY路由）
- VC1-VC3：自适应通道
路由决策流程：
1. 检查自适应通道（VC1-3）的可用性
2. 选择负载最轻的方向
3. 如果所有自适应通道都忙：
- 使用逃逸通道VC0
- 强制XY路由
基于本地或全局拥塞信息动态调整路由决策。
本地拥塞度量：
拥塞度 = α × 缓冲区占用率 + β × 链路利用率
其中：α + β = 1
缓冲区占用率 = 已用缓冲区 / 总缓冲区
链路利用率 = 忙碌周期数 / 总周期数
RCA（Regional Congestion Awareness）算法：
1. 收集1跳邻居的拥塞信息
2. 构建区域拥塞图
3. 使用Dijkstra算法计算最小拥塞路径
4. 每N个周期更新一次（N=100~1000）
死锁是NoC设计中的关键挑战，必须通过精心设计的机制来预防或处理。
Coffman条件（四个必要条件）：
死锁示例（4节点环）：
A ← B
↓ ↑
D → C
每个节点的缓冲区都满了：
- A持有D→A的数据，等待A→B的缓冲区
- B持有A→B的数据，等待B→C的缓冲区
- C持有B→C的数据，等待C→D的缓冲区
- D持有C→D的数据，等待D→A的缓冲区
1. 维度序路由（Dimension-Ordered Routing）：
通过强制路由顺序打破循环依赖
- XY路由：总是先X后Y
- 证明：不可能形成循环，因为Y→X的转向被禁止
2. 虚拟通道方法：
通道依赖图（CDG）无环设计：
- 为每个虚拟通道分配等级
- 只允许从低等级向高等级转换
- 或在同等级内使用确定性路由
示例（2个VC）：
VC0: 用于X维度路由
VC1: 用于Y维度路由
规则：从VC0到VC1单向转换
3. 泡沫流控（Bubble Flow Control）：
确保网络中始终有空闲缓冲区（"泡沫"）
规则：只有当下游有≥2个空闲缓冲区时才发送
效果：防止网络完全饱和，留有调度空间
当预防机制过于保守时，可以允许死锁发生但及时检测和恢复。
超时检测机制：
for each packet p:
if p.wait_time > THRESHOLD:
suspected_deadlock = true
initiate_detection_protocol()
THRESHOLD = f(网络大小, 平均延迟)
典型值：10 × 网络直径 × 周期时间
渐进式恢复策略：
Level 1: 误杀最小化
- 使用替代路径（如果存在）
- 临时启用受限转向
Level 2: 选择性丢包
- 识别死锁环中优先级最低的包
- 将其重定向到逃逸网络
Level 3: 激进恢复
- 清空死锁区域所有缓冲区
- 触发端到端重传
虚拟通道（VC）技术通过在物理通道上复用多个逻辑通道，提高链路利用率并支持死锁避免。
基于流量类别：
4个VC的典型分配：
VC0: 控制消息（最高优先级）
VC1: 缓存一致性请求
VC2: 数据响应
VC3: 尽力而为流量
优先级：VC0 > VC1 > VC2 > VC3
基于虚拟网络：
将NoC划分为多个逻辑子网：
- 请求网络：VC0-1
- 响应网络：VC2-3
- 每个子网独立无死锁
拍卖式分配（Auction-Based）：
每个输入端口"竞标"输出VC：
1. 计算出价 = f(队列长度, 等待时间, 优先级)
2. 输出端口选择最高出价者
3. 分配VC使用权限（时间片）
出价函数：
bid = α × queue_len + β × wait_time + γ × priority
其中：α=0.4, β=0.4, γ=0.2
自适应VC分配：
根据网络负载动态调整VC数量：
if (load < 30%):
active_VCs = 2 # 省电模式
elif (load < 70%):
active_VCs = 4 # 平衡模式
else:
active_VCs = 8 # 高性能模式
统一缓冲区 vs 独立缓冲区：
独立缓冲区架构：
VC0: □□□□ (4 flits)
VC1: □□□□ (4 flits)
VC2: □□□□ (4 flits)
VC3: □□□□ (4 flits)
总计：16 flits，固定分配
统一缓冲区架构：
共享池：□□□□□□□□□□□□□□□□ (16 flits)
动态分配给需要的VC
优点：更高的缓冲区利用率
缺点：需要更复杂的管理逻辑
信用管理：
每个VC维护信用计数器：
credits[vc_id] = buffer_size[vc_id]
发送flit时：
if credits[vc] > 0:
send_flit()
credits[vc]--
收到信用返回时：
credits[vc]++
流控机制确保发送方不会向接收方发送超过其处理能力的数据，是NoC可靠运行的基础。
信用流控是NoC中最常用的流控机制，通过信用计数器跟踪下游缓冲区可用空间。
基本原理：
初始化：
上游.credits = 下游.buffer_size
发送过程：
1. 检查：if (credits > 0)
2. 发送：send_flit(); credits--
3. 等待：wait_for_credit_return()
接收过程：
1. 接收：receive_flit()
2. 处理：process_flit()
3. 返回：send_credit_return()
信用返回延迟分析：
往返时间（RTT）= t_forward + t_process + t_credit_return
其中：
- t_forward: flit传输延迟（1周期）
- t_process: 路由器处理延迟（2-3周期）
- t_credit_return: 信用返回延迟（1周期）
最小缓冲区需求：
B_min = ⌈RTT / flit_cycle⌉ + 1
优化技术：
时序优化： 原始：|–传输–|–处理–|–返回–| 优化：|–传输–|–处理–| |–预测返回–| 节省：25-30%的RTT
2. **信用累积（Credit Accumulation）：**
批量返回信用而非逐个返回 阈值策略： if (pending_credits >= BATCH_SIZE || timer >= MAX_DELAY): send_accumulated_credits()
BATCH_SIZE = 4 # 典型值 MAX_DELAY = 8 # 周期
### 2.5.2 背压机制（Backpressure）
背压是一种从下游向上游传播拥塞信息的机制。
**On/Off背压：**
简单的二值信号：
状态机： OFF → ON: buffer_occupancy > HIGH_THRESHOLD ON → OFF: buffer_occupancy < LOW_THRESHOLD
HIGH_THRESHOLD = 0.8 × buffer_size LOW_THRESHOLD = 0.5 × buffer_size
**多级背压：**
4级背压示例： Level 0: 0-25% 满 → 全速发送 Level 1: 25-50% 满 → 75%速率 Level 2: 50-75% 满 → 50%速率 Level 3: 75-100% 满 → 停止发送
实现：使用2位信号线 00: Level 0 01: Level 1 10: Level 2 11: Level 3
### 2.5.3 混合流控策略
**ACK/NACK协议：**
结合信用流控和重传机制：
优点：低负载时延迟更低 缺点：高负载时重传开销大
适应性切换： if (network_load < 30%): use_optimistic_mode() else: use_credit_based_mode()
**弹性缓冲区（Elastic Buffers）：**
使用FIFO链实现可变深度缓冲：
空闲：□ → □ → □ → □ 部分：■ → ■ → □ → □ 满载：■ → ■ → ■ → ■
弹性传输协议：
服务质量（QoS）机制确保关键流量获得必要的网络资源，满足延迟和带宽需求。
服务等级定义：
Class 0 (GT - Guaranteed Throughput):
- 硬实时要求
- 预留带宽
- 最高优先级
- 例：中断、同步信号
Class 1 (BE+ - Best Effort Plus):
- 软实时要求
- 优先调度
- 例：音视频流
Class 2 (BE - Best Effort):
- 无时间要求
- 尽力而为
- 例：批处理数据
流量标记：
Packet Header扩展（8位QoS字段）：
[7:6] 服务等级（2位）
[5:3] 优先级（3位）
[2:0] 流ID（3位）
标记规则：
- CPU请求 → Class 0, Priority 7
- GPU纹理 → Class 1, Priority 4
- DMA传输 → Class 2, Priority 1
严格优先级（Strict Priority）：
调度逻辑：
for priority in [7, 6, 5, 4, 3, 2, 1, 0]:
if queue[priority].not_empty():
return queue[priority].dequeue()
问题：低优先级饿死
解决：加入老化机制
加权轮询（Weighted Round Robin）：
权重分配：
Queue_0: weight = 4 # 40%带宽
Queue_1: weight = 3 # 30%带宽
Queue_2: weight = 2 # 20%带宽
Queue_3: weight = 1 # 10%带宽
调度周期：4+3+2+1 = 10个时隙
时隙分配：[0,0,0,0,1,1,1,2,2,3]
赤字轮询（Deficit Round Robin）：
每个队列维护赤字计数器：
struct Queue {
deficit_counter = 0
quantum = 100 # 字节
}
调度算法：
1. queue.deficit_counter += queue.quantum
2. while (queue.head.size <= queue.deficit_counter):
send(queue.dequeue())
queue.deficit_counter -= packet.size
3. 移至下一队列
时分复用（TDM）槽位分配：
16时隙TDM表：
Flow_A: [0,4,8,12] # 25%带宽
Flow_B: [1,5,9,13] # 25%带宽
Flow_C: [2,6,10,14] # 25%带宽
BE流量: [3,7,11,15] # 25%带宽
槽位大小 = 64字节
周期 = 16 × 64 = 1024字节
速率限制（Rate Limiting）：
令牌桶算法：
- 令牌生成速率：r tokens/秒
- 桶容量：b tokens
- 发送条件：tokens >= packet_size
漏桶算法：
- 固定输出速率：r bytes/秒
- 缓冲区大小：b bytes
- 溢出处理：丢弃或标记
参数配置示例：
高优先级：r=10Gbps, b=1MB
中优先级：r=5Gbps, b=512KB
低优先级：r=1Gbps, b=128KB
ECN（Explicit Congestion Notification）：
拥塞检测：
if (queue_occupancy > ECN_THRESHOLD):
packet.ecn_flag = 1
ECN_THRESHOLD = 0.7 × queue_size
源端响应：
if (received_packet.ecn_flag == 1):
reduce_injection_rate(0.5)
start_recovery_timer()
自适应注入率控制：
AIMD算法（加性增乘性减）：
- 无拥塞：rate += α（线性增加）
- 检测拥塞：rate *= β（乘性降低）
典型参数：
α = 0.1 × max_rate / RTT
β = 0.5
稳定性条件：
α × RTT < 2 × (1 - β) × buffer_size
NVSwitch是NVIDIA设计的高带宽、低延迟交换芯片，用于连接多个GPU，支持NVLink协议。第三代NVSwitch提供64个NVLink 4.0端口，总带宽达到13.6 TB/s。
NVSwitch内部架构：
┌─────────────────────────────────┐
│ Crossbar Core │
│ (64×64 全交叉开关矩阵) │
├─────────────────────────────────┤
│ Port 0 │ Port 1 │...│ Port 63 │
├─────────┼─────────┼───┼─────────┤
│ PHY │ PHY │...│ PHY │
└─────────┴─────────┴───┴─────────┘
关键参数：
- 端口数：64个NVLink 4.0
- 每端口带宽：100 GB/s（双向）
- 总交换容量：6.4 TB/s
- 端口到端口延迟：< 300ns
- 路由表容量：256K条目
自适应喷洒（Adaptive Spray）路由：
将大消息分散到多条路径传输：
1. 消息分片：
Message(1MB) → Chunks(64KB × 16)
2. 路径选择：
for each chunk:
path = select_least_congested_path()
send_chunk(path)
3. 路径评分算法：
score = α/利用率 + β/排队延迟 + γ/历史性能
其中：α=0.4, β=0.4, γ=0.2
负载均衡哈希：
5元组哈希路由：
hash = CRC32(src_gpu, dst_gpu, flow_id, msg_id, chunk_id)
path_index = hash % num_available_paths
selected_path = path_table[path_index]
优点：同一流的包走相同路径，保序
缺点：可能造成局部热点
自适应路由与全局负载感知：
三级拥塞信息收集：
Level 1 (本地)：每个端口的队列深度
Level 2 (邻居)：1跳邻居的拥塞状态
Level 3 (全局)：整个fabric的热点图
更新周期：
- Level 1: 每10ns
- Level 2: 每100ns
- Level 3: 每1μs
路由决策：
if (local_congestion > HIGH):
use_global_info()
elif (local_congestion > MEDIUM):
use_neighbor_info()
else:
use_local_info()
动态缓冲区分配：
共享缓冲池管理：
Total Buffer = 32MB
Static Allocation = 8MB (128KB × 64 ports)
Dynamic Pool = 24MB
动态分配策略：
if (port.priority == HIGH):
max_dynamic = 1MB
elif (port.priority == MEDIUM):
max_dynamic = 512KB
else:
max_dynamic = 256KB
故障检测与隔离：
链路健康监控：
- CRC错误率阈值：10^-12
- 重传率阈值：10^-6
- 心跳超时：100μs
故障处理状态机：
HEALTHY → DEGRADED → FAILED → ISOLATED
↓
RECOVERING → TESTING → HEALTHY
自适应重路由：
快速路径切换：
1. 检测到链路故障
2. 标记路径不可用
3. 更新路由表（<1μs）
4. 重定向进行中的传输
备用路径预计算：
for each (src, dst) pair:
primary_paths = compute_k_shortest_paths(k=4)
backup_paths = compute_disjoint_paths(k=2)
store_in_routing_table()
本章系统介绍了片上网络中的路由算法和流控机制，这些是NoC设计的核心技术：
关键概念回顾：
关键公式总结：
题目1：XY路由路径计算 在8×8的2D Mesh网络中，计算从节点(2,3)到节点(6,1)的XY路由路径，并计算总跳数。
题目2：虚拟通道防死锁 设计一个2个虚拟通道的分配方案，使得4节点环形网络无死锁。画出通道依赖图。
题目3：信用流控计算 链路传输延迟1周期，路由器处理3周期，信用返回1周期。若链路带宽为1 flit/cycle，计算维持满带宽所需的最小缓冲区大小。
题目4：Odd-Even路由分析 证明Odd-Even路由算法在2D Mesh中是无死锁的。提示：分析所有可能的转向限制组合。
题目5：自适应路由性能建模 给定4×4 Mesh，均匀随机流量，每个节点注入率λ=0.3 flits/cycle。比较XY路由和完全自适应路由的饱和吞吐量。假设无限缓冲区。
题目6：QoS调度设计 设计一个支持3个服务等级的调度器：
要求防止饿死并保证公平性。
题目7：NVSwitch扩展性分析 分析NVSwitch在连接256个GPU时的扩展挑战。考虑多级拓扑、路由复杂度、故障概率。
题目8：新型路由算法设计（开放题） 设计一种新的自适应路由算法，结合机器学习预测流量模式。描述算法框架、训练方法和部署策略。
陷阱：假设部分自适应路由总是优于确定性路由
陷阱：忽视路由算法与拓扑的匹配
陷阱：过度依赖超时检测
陷阱：虚拟通道数量越多越好
陷阱：信用计数器溢出
陷阱：忽略信用返回路径拥塞
陷阱：静态优先级导致饿死
陷阱：过激的拥塞控制