掌握NoC路由算法的基本概念、分类和设计原则，理解XY路由和自适应路由的工作原理和Verilog实现。
路由算法决定了数据包从源节点到目的节点的路径选择策略。它是NoC性能的关键决定因素——好的路由算法能均衡网络负载、降低延迟、避免死锁；差的路由算法可能导致拥塞热点甚至网络死锁。
XY路由是最简单也最常用的NoC路由算法。它先沿X方向(东/西)路由到目的列，再沿Y方向(南/北)路由到目的行。路径完全由源和目的坐标决定，与网络状态无关。
优点：实现简单(只需比较坐标)；保证无死锁(路径单调)；确定性延迟可预测。
缺点：不能绕开拥塞区域；对热点流量模式不公平；所有同类通信走相同路径，无法负载均衡。
自适应路由允许数据包根据当前网络状态(拥塞程度、缓冲区占用等)选择路径。分为最小自适应(只选最短路径中较空闲的)和非最小自适应(允许绕远路避开拥塞)。
死锁是NoC最严重的问题之一——多个数据包循环等待对方释放资源，导致网络永久阻塞。路由算法必须保证无死锁。XY路由通过先X后Y的单调性，破坏了循环等待条件。
路由算法通过破坏循环等待来避免死锁。常见方法：①维序路由(XY)保证单调性；②虚拟通道打破通道依赖图中的环；③限制转弯(如West-First)。
// XY路由算法实现
module xy_router #(
parameter X_WIDTH = 3,
parameter Y_WIDTH = 3,
parameter DATA_WIDTH = 32
)(
input logic clk,
input logic rst_n,
input logic [X_WIDTH-1:0] my_x,
input logic [Y_WIDTH-1:0] 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,
output logic [2:0] route_out // 0=L,1=E,2=W,3=N,4=S
);
always_comb begin
if (pkt_dst_x > my_x)
route_out = 3'd1; // 东
else if (pkt_dst_x < my_x)
route_out = 3'd2; // 西
else if (pkt_dst_y < my_y)
route_out = 3'd3; // 北
else if (pkt_dst_y > my_y)
route_out = 3'd4; // 南
else
route_out = 3'd0; // 本地
end
assign pkt_ready = 1'b1;
endmodule// 自适应路由 - 根据拥塞选择路径
module adaptive_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,
input logic [3:0] east_cong, west_cong,
input logic [3:0] north_cong, south_cong,
output logic [2:0] route_out
);
logic need_x = (pkt_dst_x != my_x);
logic need_y = (pkt_dst_y != my_y);
logic can_east = (pkt_dst_x > my_x);
logic can_west = (pkt_dst_x < my_x);
logic can_north = (pkt_dst_y < my_y);
logic can_south = (pkt_dst_y > my_y);
always_comb begin
route_out = 3'd0;
if (need_x) begin
if (can_east && east_cong < 4'h8)
route_out = 3'd1;
else if (can_west && west_cong < 4'h8)
route_out = 3'd2;
else if (need_y) begin
if (can_north && north_cong < 4'h8) route_out = 3'd3;
else if (can_south && south_cong < 4'h8) route_out = 3'd4;
else route_out = can_east ? 3'd1 : 3'd2;
end
end else if (need_y) begin
if (can_north) route_out = 3'd3;
else route_out = 3'd4;
end
end
assign pkt_ready = 1'b1;
endmoduleXY路由和自适应路由模块均通过Verilator验证。
| 特性 | XY路由 | 维序路由 | 最小自适应 | 非最小自适应 |
|---|---|---|---|---|
| 路径确定性 | 完全确定 | 完全确定 | 部分确定 | 不确定 |
| 死锁自由 | ✅天然 | ✅天然 | 需VC | 需VC |
| 负载均衡 | 差 | 差 | 中 | 好 |
| 实现复杂度 | 极低 | 低 | 中 | 高 |
| 面积开销 | 极小 | 小 | 中 | 大 |
练习1：在4×4 Mesh中，列出从(1,2)到(3,0)的XY路由路径。
练习2：实现West-First路由算法的Verilog模块。
练习3：证明XY路由在Mesh拓扑下不会产生死锁。
你已掌握NoC路由算法的核心原理！
路由算法的分类不仅仅是"确定性"vs"自适应"这么简单。根据不同的维度，可以构建更精细的分类体系：
| 类型 | 定义 | 典型算法 |
|---|---|---|
| 确定性 | 路径完全由源/目的决定 | XY, YX, 源路由 |
| 部分自适应 | 部分路径可选，部分固定 | West-First, Negative-First, Odd-Even |
| 完全自适应 | 所有路径可选 | Duato, 基于VC的自适应 |
| 类型 | 约束 | 优势 | 劣势 |
|---|---|---|---|
| 最小路由 | 只走最短路径 | 延迟低 | 绕行能力弱 |
| 非最小路由 | 允许绕远 | 负载均衡好 | 延迟可能增大 |
2D Mesh中共有8种转弯(4顺时针+4逆时针)。不同转弯模型禁止不同组合：
评估路由算法需要考虑以下指标和流量模式：
简单系统(核数<16)：用XY路由，简单可靠
中等系统(核数16-64)：用转弯模型(West-First)，适度自适应
大规模系统(核数>64)：用2-VC自适应路由，充分负载均衡
实时系统：用确定性路由，保证延迟可预测
路由算法最终要映射到硬件电路。不同的路由算法在硬件实现上有不同的面积和延迟特征：
XY路由只需两个比较器(比较X坐标和Y坐标)和一个优先级编码器。硬件开销极小：
// XY路由硬件实现面积估算
// 2个8-bit比较器: 2 × 50μm² = 100μm²
// 优先级编码器: 30μm²
// 总计: ~130μm²
// 关键路径: 比较器延迟 ≈ 0.3ns自适应路由除了基本路由逻辑外，还需要：拥塞信息接收(4×4-bit)、比较逻辑(4路比较)、选择逻辑。面积约为XY路由的3-5倍。
为了验证路由正确性，需要在路由器中添加可观测和可控制的设计：
验证路由算法的正确性是NoC设计中最关键的一步。以下是系统化的验证方法：
对每一对源-目的组合，发送一个测试包，追踪其完整路径，验证路径与路由算法一致。对于XY路由，验证路径是否先X后Y。
同时注入多个需要经过相同输出端口的包，验证仲裁器工作正常且无数据丢失。测试用例：
定义路由覆盖率 = 被测试到的(源,目的,方向)三元组 / 所有可能的三元组。目标覆盖率>95%。
本课涵盖了NoC设计的核心知识点。以下是关键概念的快速参考：
掌握这些概念是深入理解NoC设计的基础。建议结合Verilog代码实践，加深理解。