第6课：确定性路由

1. 确定性路由概述

确定性路由(Deterministic Routing)是指数据包的路径完全由源地址和目的地址决定，不受网络状态影响的路由策略。确定性路由的最大优势是实现简单且天然无死锁。

2. 维序路由(Dimension-Order Routing, DOR)

维序路由是最经典的确定性路由。在n维Mesh中，数据包按照固定维度顺序逐维路由——先在维度0路由到目标坐标，再在维度1路由，依此类推。XY路由就是2D Mesh上的维序路由。

2.1 XY路由详解

XY路由规则：

• 如果dst_x > cur_x → 向东(East)
• 如果dst_x < cur_x → 向西(West)
• 如果dst_x = cur_x且dst_y > cur_y → 向南(South)
• 如果dst_x = cur_x且dst_y < cur_y → 向北(North)
• 如果dst_x = cur_x且dst_y = cur_y → 本地(Local)

2.2 XY路由死锁自由证明

XY路由保证无死锁的原理：所有数据包先X后Y，在通道依赖图(Channel Dependency Graph, CDG)中，不存在从Y方向通道回到X方向通道的依赖边，因此CDG是无环的，从而保证无死锁。

3. 源路由(Source Routing)

源路由在数据包的头部携带完整的路径信息——每个中间节点只需读取头部指定的输出端口，无需计算路由。优点是路由器极简，缺点是包头开销大。

4. Verilog实现

// 确定性XY路由 - 完整实现(含流水线)
module deterministic_xy_router #(
    parameter X_WIDTH    = 3,
    parameter Y_WIDTH    = 3,
    parameter DATA_WIDTH = 32,
    parameter DEPTH      = 4
)(
    input  logic                  clk, rst_n,
    input  logic [X_WIDTH-1:0]    my_x, my_y,
    // 5个输入端口 (L/E/W/N/S)
    input  logic [DATA_WIDTH-1:0] in_data  [0:4],
    input  logic [1:0]            in_flit_type [0:4], // 00=H,01=B,10=T
    input  logic [X_WIDTH-1:0]    in_dst_x [0:4],
    input  logic [Y_WIDTH-1:0]    in_dst_y [0:4],
    input  logic                  in_valid [0:4],
    output logic                  in_ready [0:4],
    // 5个输出端口
    output logic [DATA_WIDTH-1:0] out_data  [0:4],
    output logic                  out_valid [0:4],
    input  logic                  out_ready [0:4]
);
    // 路由计算: XY算法
    logic [2:0] route_decision [0:4];

    always_comb begin
        for (int p = 0; p < 5; p++) begin
            if (in_dst_x[p] > my_x)
                route_decision[p] = 3'd1; // 东
            else if (in_dst_x[p] < my_x)
                route_decision[p] = 3'd2; // 西
            else if (in_dst_y[p] < my_y)
                route_decision[p] = 3'd3; // 北
            else if (in_dst_y[p] > my_y)
                route_decision[p] = 3'd4; // 南
            else
                route_decision[p] = 3'd0; // 本地
        end
    end

    // 简化交叉开关: 直接连接(单输入→单输出)
    // 实际需要仲裁器处理多输入争同一输出
    for (genvar p = 0; p < 5; p++) begin : gen_passthrough
        assign out_data[p]  = in_data[p];
        assign out_valid[p] = in_valid[p];
        assign in_ready[p]  = out_ready[p];
    end
endmodule

4.2 源路由实现

// 源路由 - 路径在包头中指定
module source_router #(
    parameter DATA_WIDTH = 32,
    parameter PATH_WIDTH = 3,   // 每跳3bit指定端口
    parameter MAX_HOPS   = 8    // 最大跳数
)(
    input  logic                  clk, rst_n,
    input  logic [DATA_WIDTH-1:0] in_data,
    input  logic [PATH_WIDTH*MAX_HOPS-1:0] in_path,
    input  logic                  in_valid,
    output logic                  in_ready,
    output logic [DATA_WIDTH-1:0] out_data,
    output logic [PATH_WIDTH-1:0] out_port,
    output logic                  out_valid,
    input  logic                  out_ready
);
    // 路径移位寄存器
    logic [PATH_WIDTH*MAX_HOPS-1:0] path_reg;
    logic [PATH_WIDTH-1:0]          current_port;

    always_ff @(posedge clk or negedge rst_n) begin
        if (!rst_n)
            path_reg <= {PATH_WIDTH*MAX_HOPS{1'b0}};
        else if (in_valid && in_ready)
            path_reg <= {path_reg[PATH_WIDTH*MAX_HOPS-PATH_WIDTH-1:0],
                          {PATH_WIDTH{1'b0}}};
    end

    assign current_port = path_reg[PATH_WIDTH-1:0];
    assign out_port     = current_port;
    assign out_data     = in_data;
    assign out_valid    = in_valid;
    assign in_ready     = out_ready;
endmodule

5. 练习

6. 确定性路由的工程实践

在实际NoC设计中，确定性路由的选择和配置需要考虑多个工程因素：

6.1 维序路由的维度顺序选择

在2D Mesh中，XY和YX两种维序都是合法的。选择哪种取决于流量模式：

• 如果流量主要是水平方向(如行扫描图像处理) → 选XY(先X后Y)
• 如果流量主要是垂直方向(如列式数据库) → 选YX(先Y后X)
• 如果流量均匀 → 默认XY即可

6.2 源路由的路径计算

源路由需要在发送端计算完整路径。路径计算算法：

// 源路由路径计算函数(伪代码)
function compute_path(src_x, src_y, dst_x, dst_y):
    path = []
    // XY路由策略
    dx = dst_x - src_x
    if dx > 0:
        for i in range(dx): path.append(EAST)
    elif dx < 0:
        for i in range(-dx): path.append(WEST)
    dy = dst_y - src_y
    if dy > 0:
        for i in range(dy): path.append(SOUTH)
    elif dy < 0:
        for i in range(-dy): path.append(NORTH)
    return path

6.3 确定性路由的测试策略

验证确定性路由的关键测试用例：

• 所有源-目的对：N²种组合，验证路径正确性
• 边界节点：角落节点(0,0)和(N-1,N-1)的通信
• 相邻节点：最小跳数(1跳)的通信
• 对角线节点：最大跳数的通信
• 自环：源=目的(本地弹出)

6.4 路由表压缩

对于表路由，每个节点需要存储路由表。在k×k Mesh中，表大小为k²×⌈log₂5⌉ bit。可以通过以下方法压缩：

• 行列分解：将2D路由表分解为行表+列表，面积从O(N²)降至O(N)
• 默认路由：大部分路由使用XY默认值，只存储例外
• 区域编码：将目的地址空间分为区域，每个区域一个路由端口

7. 确定性路由的扩展：多维拓扑

在3D或更高维度的拓扑中，维序路由(DOR)的维度顺序选择更加重要。不同的维度顺序对应不同的CDG和性能特征。

7.1 3D Mesh中的XYZ路由

在3D Mesh(层/行/列)中，XYZ路由按固定顺序逐维路由：先X(层间)，再Y(行内)，最后Z(列内)。与2D相同，XYZ路由天然无死锁。

7.2 维度顺序对性能的影响

在3D Mesh中，有6种可能的维度顺序(XYZ/XZY/YXZ/YZX/ZXY/ZYX)。选择依据：

• 如果层间链路带宽最小 → 优先在层内路由(减少层间跳数)
• 如果某方向链路较长(延迟大) → 放在最后路由
• 默认选择XYZ(与2D的XY兼容)

7.3 确定性路由的故障处理

确定性路由的路径是唯一的，当链路或路由器故障时，无法绕行。处理方法：

• 路由表覆盖：在故障时更新路由表，绕过故障点
• 维度反转：将XY切换为YX(特定区域)
• 虚拟通道重新映射：使用VC实现故障绕行

8. 确定性路由的历史与发展

确定性路由是NoC中最古老也最可靠的路由策略。它的发展历程反映了NoC设计的演进：

8.1 早期阶段(2000-2005)

最早的NoC研究几乎全部使用XY路由，因为它最简单、最可靠。Dally和Towles的开创性论文(2004)就使用XY路由。

8.2 多样化阶段(2005-2010)

随着NoC规模增长(>16核)，XY路由的局限性显现。研究者提出各种转弯模型(West-First, Negative-First, Odd-Even)，在不牺牲死锁安全的前提下增加路径选择。

8.3 融合阶段(2010至今)

现代NoC采用确定性+自适应的混合策略：逃逸VC走确定性路由，自适应VC走灵活路由。Duato协议成为工业标准。

8.4 未来方向

新兴研究方向包括：机器学习辅助路由决策、面向AI工作负载的专用路由、3D NoC中的路由优化等。

9. 确定性路由的参数化Verilog实现

实现一个支持多种维序路由的可参数化路由器：

// 参数化维序路由器(支持任意维度顺序)
module parametric_dor_router #(
    parameter NUM_DIMS    = 2,       // 维度数
    parameter DIM_WIDTH   = 3,       // 每维坐标位宽
    parameter DATA_WIDTH  = 32,
    parameter DIM_ORDER   = 2'b01    // 01=XY, 10=YX
)(
    input  logic                  clk, rst_n,
    input  logic [DIM_WIDTH-1:0]  my_coords [0:NUM_DIMS-1],
    input  logic [DIM_WIDTH-1:0]  dst_coords [0:NUM_DIMS-1],
    input  logic [DATA_WIDTH-1:0] pkt_data,
    input  logic                  pkt_valid,
    output logic                  pkt_ready,
    output logic [2:0]            route_out
);
    // 按维度顺序依次路由
    always_comb begin
        route_out = 3'd0; // 默认本地
        case (DIM_ORDER)
            2'b01: begin // XY: 先X后Y
                if (dst_coords[0] != my_coords[0])
                    route_out = (dst_coords[0] > my_coords[0]) ? 3'd1 : 3'd2;
                else if (dst_coords[1] != my_coords[1])
                    route_out = (dst_coords[1] < my_coords[1]) ? 3'd3 : 3'd4;
            end
            2'b10: begin // YX: 先Y后X
                if (dst_coords[1] != my_coords[1])
                    route_out = (dst_coords[1] < my_coords[1]) ? 3'd3 : 3'd4;
                else if (dst_coords[0] != my_coords[0])
                    route_out = (dst_coords[0] > my_coords[0]) ? 3'd1 : 3'd2;
            end
        endcase
    end
    assign pkt_ready = 1'b1;
endmodule