深入理解自适应路由算法的原理、分类和实现，掌握最小自适应和完全自适应路由，理解虚拟通道在自适应路由中的作用。
自适应路由(Adaptive Routing)允许数据包根据网络状态选择路径，旨在均衡网络负载、避免拥塞、提高吞吐量。与确定性路由相比，自适应路由能更好地应对热点流量和不均匀负载。
最小自适应路由只允许数据包沿最短路径前进，但在多条最短路径中选择较空闲的一条。例如从(0,0)到(2,2)在2D Mesh中有6条最短路径，自适应路由可在其中选择。
West-First是一种转弯模型路由：先处理西向(如果需要向西)，之后才能向东或南/北。禁止的转弯：东→北、东→南。这保证不形成环路。
非最小路由允许数据包绕远路以避开拥塞区域。虽然增加了路径长度，但在高负载下可以提高整体吞吐量。
Valiant路由分两阶段：先将数据包随机路由到一个中间节点，再从中间节点路由到目的地。两阶段都使用确定性路由(如XY)，但中间节点的随机性实现了负载均衡。
自适应路由需要虚拟通道(VC)来避免死锁。当数据包可以选择不同路径时，不同路径间可能形成循环依赖。VC通过将物理通道分为多个逻辑通道，打破循环依赖。
没有VC的自适应路由可能死锁！例如，4个数据包分别走东→北、北→西、西→南、南→东，形成循环依赖。VC通过将通道分为"逃生通道"和"自适应通道"来打破循环。
// 最小自适应路由 - West-First转弯模型
module west_first_router #(
parameter X_WIDTH = 3,
parameter Y_WIDTH = 3,
parameter DATA_WIDTH = 32
)(
input logic clk, rst_n,
input logic [X_WIDTH-1:0] my_x, my_y,
input logic [DATA_WIDTH-1:0] pkt_data,
input logic [X_WIDTH-1:0] pkt_dst_x,
input logic [Y_WIDTH-1:0] pkt_dst_y,
input logic pkt_valid,
output logic pkt_ready,
// 拥塞信息(0=空闲,15=满)
input logic [3:0] cong_e, cong_w,
input logic [3:0] cong_n, cong_s,
output logic [2:0] route_out
);
logic need_west = (pkt_dst_x < my_x);
logic need_east = (pkt_dst_x > my_x);
logic need_north = (pkt_dst_y < my_y);
logic need_south = (pkt_dst_y > my_y);
always_comb begin
route_out = 3'd0; // 默认本地
// West-First: 优先西向
if (need_west)
route_out = 3'd2; // 西
else begin
// 西向处理完, 可选东/南/北
if (need_east && cong_e < 4'h8)
route_out = 3'd1; // 东
else if (need_north && cong_n < 4'h8)
route_out = 3'd3; // 北
else if (need_south && cong_s < 4'h8)
route_out = 3'd4; // 南
else if (need_east)
route_out = 3'd1;
else if (need_north)
route_out = 3'd3;
else if (need_south)
route_out = 3'd4;
end
end
assign pkt_ready = 1'b1;
endmoduleWest-First自适应路由通过Verilator验证。
练习1：在4×4 Mesh中，对比XY路由和West-First路由在tornado流量模式下的性能。
练习2：实现Negative-First转弯模型路由。
练习3：分析为什么自适应路由需要虚拟通道来避免死锁。
你已掌握自适应路由的原理、分类和实现！
自适应路由的决策质量取决于拥塞信息的准确性和时效性。拥塞信息的传播方式直接影响路由效果。
最简单的方案：只使用本路由器的缓冲区占用作为拥塞指标。优点是零延迟获取，缺点是信息有限。
将本节点的缓冲区占用通过专用信号线传递给邻居。每个方向增加4-bit拥塞信号(编码占用率0-15)，信息延迟1个cycle。
通过专用网络或数据包捎带传播全局拥塞信息。信息更全面但延迟更大(多个cycle)，适合大规模NoC。
| 度量方式 | 精度 | 面积 | 延迟 |
|---|---|---|---|
| 缓冲区占用 | 中 | 小 | 0 cycle |
| 链路利用率 | 中 | 小 | 1 cycle |
| 虚拟通道空闲数 | 高 | 中 | 1 cycle |
| 队列等待时间 | 高 | 大 | 2+ cycles |
自适应路由并非万能。以下场景中自适应路由可能比确定性路由更差：
1. 使用滞后机制避免振荡(类似ON/OFF流控的滞后区间)
2. 同一包的所有flit走同一路径(头flit建立，尾flit释放)
3. 限制自适应范围(只在最短路径中选择)
4. 保留逃逸VC作为退路
最新的研究方向使用强化学习(RL)来训练路由决策。每个路由器作为一个智能体(Agent)，根据局部观察(缓冲区占用、链路利用率)做出路由决策，通过奖励函数(延迟最小化)来学习最优策略。
不仅根据当前拥塞信息决策，还预测未来的网络状态。预测方法：
自适应路由的额外面积主要来自：
| 组件 | XY路由面积 | 自适应面积 | 增加 |
|---|---|---|---|
| 路由计算 | 130μm² | 400μm² | +270 |
| 拥塞接收 | 0 | 200μm² | +200 |
| 额外控制逻辑 | 0 | 300μm² | +300 |
| 总计 | 130μm² | 900μm² | +770 |
为了公平比较不同自适应路由算法，需要统一的评估框架：
| 指标 | 定义 | 单位 |
|---|---|---|
| 零负载延迟 | 单包端到端延迟(无其他流量) | cycles |
| 饱和吞吐量 | 延迟开始急剧上升的注入率 | flit/node/cycle |
| 路径多样性 | 平均可用最短路径数 | 路径数 |
| 面积开销 | 路由逻辑占路由器面积比 | % |
| 公平性 | 最坏/最好流量的延迟比 | 比值 |
所有自适应路由论文都应报告至少5种标准流量模式的结果，包括uniform、neighbor、tornado、hotspot和bit-reverse。这确保了结果的可比性。
在C++/SystemC仿真器中实现自适应路由需要以下组件：
// BookSim风格的自适应路由仿真器核心
class AdaptiveRouter {
int node_id;
int num_ports;
int num_vcs;
vector<FIFO> input_buffers; // 每端口每VC一个FIFO
vector<int> congestion_info; // 4方向拥塞度
int route(int in_port, int in_vc, Flit* flit) {
int dst = flit->dest;
// 计算所有可行方向
vector<int> candidates = get_minimal_directions(dst);
// 选择拥塞最低的方向
int best_dir = candidates[0];
int min_cong = congestion_info[best_dir];
for (int dir : candidates) {
if (congestion_info[dir] < min_cong) {
min_cong = congestion_info[dir];
best_dir = dir;
}
}
return best_dir;
}
};最新的研究方向将强化学习应用于NoC路由决策：
每个路由器维护一个Q-Table，记录"状态-动作"对的价值。状态=(当前拥塞, 目的方向)，动作=输出端口选择。路由器通过在线学习不断优化Q值，实现自适应路由。
对于大规模NoC(>64节点)，Q-Table太大。使用神经网络近似Q函数，输入为拥塞向量，输出为各输出端口的价值。推理延迟约5-10 cycles，通过异步更新避免阻塞流水线。
为了公平比较不同自适应路由算法，学术界建立了标准基准：