第14课：虫孔交换

1. 虫孔交换流控回顾

虫孔交换是NoC中最常用的交换+流控组合。数据包被切分为flit序列，头flit建立路径，体flit和尾flit沿同一路径流水传输。流控的关键问题：路径建立时机、阻塞处理、路径释放时机。

2. 路径建立与释放

虫孔交换的路径建立是隐式的：头flit每经过一跳，该跳的交叉开关连接就被锁定，直到尾flit通过才释放。这种"锁定-释放"机制简单高效，但导致阻塞传播。

2.1 路径状态机

3. 阻塞管理

当头flit被阻塞时，整条路径上的flit都停止移动。这导致：①缓冲区被占用；②交叉开关连接被锁定；③链路空闲。解决方法包括虚拟通道和 speculation。

4. Verilog实现

// 虫孔交换路由器 - 完整路径管理
module wormhole_router #(
    parameter DATA_WIDTH = 32,
    parameter NUM_PORTS  = 5,
    parameter DEPTH      = 4
)(
    input  logic                  clk, rst_n,
    input  logic [X_WIDTH-1:0]    my_x, my_y,
    // 输入端口
    input  logic [DATA_WIDTH-1:0] in_data  [0:NUM_PORTS-1],
    input  logic [1:0]            in_flit_type [0:NUM_PORTS-1],
    input  logic [X_WIDTH-1:0]    in_dst_x [0:NUM_PORTS-1],
    input  logic [Y_WIDTH-1:0]    in_dst_y [0:NUM_PORTS-1],
    input  logic                  in_valid [0:NUM_PORTS-1],
    output logic                  in_ready [0:NUM_PORTS-1],
    // 输出端口
    output logic [DATA_WIDTH-1:0] out_data  [0:NUM_PORTS-1],
    output logic                  out_valid [0:NUM_PORTS-1],
    input  logic                  out_ready [0:NUM_PORTS-1]
);
    localparam X_WIDTH = 3;
    localparam Y_WIDTH = 3;

    // 路径状态
    typedef enum logic [1:0] {
        PATH_IDLE, PATH_ACTIVE, PATH_BLOCKED
    } path_state_t;

    path_state_t path_state [0:NUM_PORTS-1];
    logic [$clog2(NUM_PORTS)-1:0] path_output [0:NUM_PORTS-1];

    // XY路由计算
    logic [2:0] route_out [0:NUM_PORTS-1];
    always_comb begin
        for (int p = 0; p < NUM_PORTS; p++) begin
            if (in_dst_x[p] > my_x) route_out[p] = 3'd1;
            else if (in_dst_x[p] < my_x) route_out[p] = 3'd2;
            else if (in_dst_y[p] < my_y) route_out[p] = 3'd3;
            else if (in_dst_y[p] > my_y) route_out[p] = 3'd4;
            else route_out[p] = 3'd0;
        end
    end

    // 路径管理状态机
    always_ff @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            for (int p = 0; p < NUM_PORTS; p++) begin
                path_state[p]  <= PATH_IDLE;
                path_output[p] <= 0;
            end
        end else begin
            for (int p = 0; p < NUM_PORTS; p++) begin
                case (path_state[p])
                    PATH_IDLE: begin
                        if (in_valid[p] && in_flit_type[p] == 2'b00) begin
                            path_output[p] <= route_out[p];
                            path_state[p]  <= PATH_ACTIVE;
                        end
                    end
                    PATH_ACTIVE: begin
                        if (in_flit_type[p] == 2'b10 && in_valid[p])
                            path_state[p] <= PATH_IDLE;
                    end
                    PATH_BLOCKED: begin
                        if (out_ready[path_output[p]])
                            path_state[p] <= PATH_ACTIVE;
                    end
                endcase
            end
        end
    end

    // 输出选择
    for (genvar p = 0; p < NUM_PORTS; p++) begin : gen_out
        assign out_data[p]  = in_data[p];
        assign out_valid[p] = in_valid[p] && (path_state[p] != PATH_IDLE);
        assign in_ready[p]  = out_ready[p];
    end
endmodule

5. 练习

5. 虫孔交换的详细时序分析

理解虫孔交换的精确时序对性能优化至关重要。

5.1 头flit延迟分解

头flit经过一跳的延迟由以下部分组成：

头flit单跳延迟 = 4-6 cycles（取决于流水线深度）

5.2 体flit的流水线行为

头flit建立路径后，后续体flit像流水一样通过路由器。每个cycle一个flit通过一个路由器：

5.3 阻塞时的时序

当头flit在某跳被阻塞(下游缓冲区满)：

5.4 虫孔交换的面积模型

虫孔交换的面积优势来自极小的缓冲区需求：

6. 虫孔交换的工业实践

虫孔交换是工业NoC中最主流的交换技术。以下是实际产品中的应用案例：

6.1 Intel Mesh NoC

Intel从Skylake开始使用Mesh NoC替代Ring Bus。Mesh路由器使用虫孔交换+3阶段流水线(BW+RC/SA→SA→ST)，头flit延迟约3 cycles/hop。

6.2 虫孔交换的典型配置

6.3 虫孔交换的优化技巧

• Smart缓冲区：空缓冲区时直接旁路，节省1 cycle
• 路径预分配：头flit到达前预分配输出端口
• 推测传输：头flit到达时立即开始传输(不等待分配完成)
• 优先级通道：为高优先级包保留一条VC

7. 虫孔交换在GPU NoC中的应用

GPU是最典型的NoC应用场景之一。NVIDIA的GPU使用虫孔交换+多VC的Mesh NoC：

7.1 NVIDIA GPU NoC架构

NVIDIA从Volta架构开始使用Mesh NoC连接SM(流处理器)和L2缓存分区。路由器使用4条VC，分别承载不同类型的流量。

7.2 GPU特有的流控需求

• 高吞吐量：GPU需要持续的内存带宽，NoC必须支持高吞吐
• Burst流量：warp的内存访问呈burst模式
• All-Reduce：集合通信需要高带宽的环/树路径

7.3 GPU NoC的优化策略

针对GPU流量特征的优化：自适应路由(均衡负载)、加宽链路(128bit+)、深缓冲(8-16 flit)、多级仲裁(iSLIP)。

8. 虫孔交换的完整性能分析

虫孔交换的性能可以用以下数学模型预测：

8.1 零负载延迟模型

头flit经过H跳的延迟：

T_head = H × T_router

其中T_router是单跳路由器延迟(4阶段=4 cycles)。

包总延迟(假设包长L个flit)：

T_total = T_head + (L-1) × 1 (体flit流水传输)

8.2 拥塞延迟模型

在高负载下，排队延迟占主导：

T_congested = T_total × (1 / (1 - ρ))

其中ρ是链路利用率(0到1之间)。当ρ→1时延迟→∞(饱和)。

8.3 多VC下的延迟改善

增加VC可以有效降低排队延迟：

• 0-VC：阻塞传播导致链路空闲，吞吐量低
• 1-VC：即无VC(虫孔)，与0-VC相同
• 2-VC：阻塞时另一VC可用，吞吐量提升40%
• 4-VC：进一步改善，但收益递减

9. 虫孔交换的变体与创新

在标准虫孔交换基础上，研究者提出了多种改进变体：

9.1 优先级虫孔交换

为不同优先级的数据包分配不同的VC。高优先级包可以抢占低优先级包的路径(通过VC切换)。在实时系统中特别有用。

9.2 分布式虫孔交换

传统的虫孔交换是集中式控制(路由器管理路径)。分布式方案让每个flit独立做出转发决策，不锁定路径。消除了阻塞传播问题，但增加了每flit的路由开销。

9.3 虫孔交换与Speculation

在虫孔交换中，头flit可以推测性地同时请求VC和开关，如果都成功则节省1 cycle。成功率约85%，在高性能路由器中广泛应用。

附录：本课关键概念速查

本课涵盖了NoC设计的核心知识点。以下是关键概念的快速参考：

• 片上网络(NoC)：用路由器+链路替代总线的片上互联架构
• 路由器：5端口交换节点，包含缓冲/路由/仲裁/交叉开关
• 虚拟通道(VC)：物理链路的逻辑分割，用于避免死锁和提升吞吐
• 信用流控：通过信用计数器精确管理缓冲区资源
• XY路由：先X后Y的确定性路由，天然无死锁
• 虫孔交换：头flit建立路径，后续flit流水传输
• Round-Robin仲裁：轮转优先级，保证公平性
• 交叉开关：N×N全连接互连矩阵

掌握这些概念是深入理解NoC设计的基础。建议结合Verilog代码实践，加深理解。