2.5.1 H-tree distribution

H-tree distribution 是一种在芯片上均匀分布时钟或广播信号的树形网络，因为形状像字母 H 而得名。它的核心思想是：从根节点出发，通过对称、等长的分支，把信号同时送到所有叶子节点，保证到达每个叶子的延迟几乎相同。

在 PanGaea 论文 4.2 节中，线性链阶段需要把 anchor 数据 $\{a_i : a_{i+15}\}$ 广播给所有 144 个 PE。为了让所有 PE 同时拿到相同数据、保持并行计算同步，就采用了 共享总线 + H-tree 分布。

1. H-tree 的基本结构

H-tree 是一种递归分形结构：

从中心根节点开始；
向左右分叉，形成“H”的横杠；
每个分支末端再向上下分叉，形成更小的“H”；
如此递归，直到到达所有叶子节点。

示意：

        ┌───┐
        │   │
    ┌───┘   └───┐
    │           │
┌───┘           └───┐
│                   │
PE  PE  PE  PE  PE  PE

实际芯片中，H-tree 会对称地覆盖整个 PE 阵列区域，每个叶子节点连接一个 PE 或一组 PE。

2. 为什么用 H-tree 做广播？

① 延迟均衡（低 skew）

H-tree 的每一级分支长度相等，从根到任意叶子的路径长度相同。
因此，信号到达所有 PE 的时间几乎一致，时钟偏斜（skew）极小。
对于需要所有 PE 同步接收同一份数据的广播操作，这一点非常关键。

② 驱动能力逐级增强

根节点只需要驱动第一级分支，后面的缓冲器逐级放大信号，驱动更大的负载。
这样可以避免单一驱动器直接驱动 144 个 PE 导致的延迟过大和信号衰减。

③ 规则对称，便于布局布线

H-tree 结构非常规则，容易在芯片版图上实现，占用面积可预测，适合大规模 PE 阵列。

④ 可扩展

增加 PE 数量时，只需增加树的层数，结构仍然保持对称和均衡。

3. H-tree 的典型应用

H-tree 最经典的应用是 时钟分布网络（clock distribution network）。
在同步数字芯片中，时钟需要同时到达所有触发器，H-tree 可以保证时钟偏斜最小，提高时序稳定性。
此外，它也用于：

全局广播信号；
电源/地分布；
复位信号分布；
多核/加速器中的全局控制信号。

论文引用的 [27] 就是 Eby G. Friedman 关于同步数字集成电路时钟分布网络的经典综述。

4. 在 PanGaea 中的具体作用

在线性链阶段：

锚点数据需要从 $PE_0$ 广播到所有 PE；
所有 PE 必须同时拿到相同的 $a_i$ 数据，才能并行计算不同的 $(i,j)$ 对；
使用 H-tree 分布，信号从根节点均匀分叉，逐级到达 144 个 PE；
这样每个 PE 几乎在同一时刻收到广播数据，避免等待和同步开销；
广播完成后，各 PE 独立计算，再通过垂直-水平归约得到全局最优 $j^*$ 。

所以，H-tree 在这里扮演的是 高效、低偏斜的广播网络，确保 PE 阵列能同步启动计算。

5. 优点与代价

优点：

延迟均衡，skew 小；
驱动能力强，适合大负载广播；
结构规则，易于物理实现；
可扩展性好。

代价：

布线资源占用较多；
根节点和缓冲器会增加功耗；
设计时需要仔细平衡每级分支长度和负载。

一句话总结

H-tree distribution 是一种对称、等长分支的树形广播网络，能让信号同时到达所有叶子节点，延迟均衡、偏斜极小。在 PanGaea 中，它被用来把 anchor 数据从 PE0 广播到全部 144 个 PE，保证线性链阶段并行计算同步、高效。

6. code example

下面是一个用 SystemVerilog 编写的 H-tree 分布网络示例。它通过递归实例化，将输入信号对称地广播到所有叶子节点，每个内部节点包含缓冲器并驱动四个子分支（左上、左下、右上、右下），直到达到指定深度。由于所有路径完全对称，叶子节点会在同一时刻收到信号，体现了 H-tree 的等延迟特性。

// ============================================================
// H-tree 分布网络
// 功能：从根节点输入，经过对称的 H 形分支，广播到所有叶子
// 深度 DEPTH，叶子数量 = 4^DEPTH
// 每个内部节点：缓冲输入，然后驱动四个子节点
// ============================================================
module htree #(
    parameter int DEPTH = 2  // 递归深度，默认 2 层，16 个叶子
)(
    input  logic                 clk_in,   // 根输入
    output logic [(4**DEPTH)-1:0] clk_out  // 扁平化的叶子输出
);

    generate
        if (DEPTH == 0) begin : gen_leaf
            // 叶子节点：直接输出
            assign clk_out[0] = clk_in;
        end else begin : gen_branch
            // 内部节点：四个缓冲器，分别驱动四个方向
            logic [3:0] buf_out;

            // 使用 Verilog 原语 buf 作为缓冲器（也可自定义缓冲模块）
            buf b0 (buf_out[0], clk_in);
            buf b1 (buf_out[1], clk_in);
            buf b2 (buf_out[2], clk_in);
            buf b3 (buf_out[3], clk_in);

            // 每个子树的输出宽度为 4^(DEPTH-1)
            localparam int SUB_SIZE = 4**(DEPTH-1);
            logic [SUB_SIZE-1:0] sub_out [0:3];

            // 递归实例化四个子 H-tree
            for (genvar i = 0; i < 4; i++) begin : gen_children
                htree #(.DEPTH(DEPTH-1)) child (
                    .clk_in  (buf_out[i]),
                    .clk_out (sub_out[i])
                );
            end

            // 将四个子树的输出拼接成最终输出
            // 顺序：子节点 3, 2, 1, 0（对应右下、右上、左下、左上，仅作扁平化）
            assign clk_out = {sub_out[3], sub_out[2], sub_out[1], sub_out[0]};
        end
    endgenerate

endmodule

测试平台示例（深度为 2，共 16 个叶子）：

module tb_htree;
    localparam int DEPTH = 2;
    logic                 clk_in;
    logic [(4**DEPTH)-1:0] clk_out;

    // 实例化 H-tree
    htree #(.DEPTH(DEPTH)) dut (
        .clk_in  (clk_in),
        .clk_out (clk_out)
    );

    initial begin
        clk_in = 0;
        #10;
        clk_in = 1;   // 信号跳变
        #10;
        clk_in = 0;
        #10;
        // 打印所有叶子输出，应全部同时变化
        $display("clk_out = %b", clk_out);
        $finish;
    end
endmodule

代码说明：

递归结构：htree 模块通过 generate 和参数 DEPTH 递归实例化自身。当 DEPTH=0 时到达叶子，直接输出；否则将输入缓冲后分给四个子节点。
对称分支：每个内部节点使用四个缓冲器（buf），分别对应 H-tree 的四个方向。缓冲器增强了驱动能力，并隔离了负载。
等长路径：由于每个分支的层次和缓冲器数量完全相同，从根到任意叶子的逻辑级数和布线长度在理想布局下是对称的，因此信号到达所有叶子的延迟一致。
扁平化输出：最终输出是一个宽度为 $4^{\text{DEPTH}}$ 的向量，每个位对应一个叶子节点。在物理设计中，这些位会映射到芯片上对称分布的叶子位置。
可扩展性：修改 DEPTH 参数即可生成不同规模的 H-tree。例如 DEPTH=3 会产生 64 个叶子。

这个例子对应了 PanGaea 论文中线性链阶段将锚点数据从 PE0 广播到全部 144 个 PE 的场景：H-tree 保证了广播信号同步到达，使所有 PE 能并行开始计算。

1. H-tree 的基本结构​

2. 为什么用 H-tree 做广播？​

① 延迟均衡（低 skew）​

② 驱动能力逐级增强​

③ 规则对称，便于布局布线​

④ 可扩展​

3. H-tree 的典型应用​

4. 在 PanGaea 中的具体作用​

5. 优点与代价​

一句话总结​

6. code example​