4 reduction tree

Reduction Tree 原理与代码解析

一、Reduction Tree 的实现原理

1.1 什么是归约树

归约树（Reduction Tree）是一种并行归约结构，用二叉树的方式把 $N$ 个输入逐步两两合并，最终得到一个结果。

常见的归约操作：

操作	输出
求最大值（max）	最大值 + 对应索引
求最小值（min）	最小值 + 对应索引
求和（sum）	总和
判断相等（all-equal）	是否全部相同

1.2 为什么用树形结构

假设有 $N = 16$ 个输入，要找最大值。

串行做法：一个一个比较，需要 15 次比较，延迟 15 个周期。

树形做法：

Level 0:  16 个输入
Level 1:  8 对比较 → 8 个结果
Level 2:  4 对比较 → 4 个结果
Level 3:  2 对比较 → 2 个结果
Level 4:  1 对比较 → 1 个结果

只需要 $\log_2(16) = 4$ 层，每层可以并行，总延迟 4 个周期。

1.3 树形结构图

以 $N = 8$ 为例：

Level 0:  [a0] [a1] [a2] [a3] [a4] [a5] [a6] [a7]
            \  /      \  /      \  /      \  /
Level 1:    [b0]      [b1]      [b2]      [b3]
              \      /            \      /
Level 2:       [c0]                [c1]
                  \              /
Level 3:            [d0]

• 每一层的元素个数减半；
• 第 $j$ 层有 $2^{\log_2 N - j - 1}$ 对比较；
• 总共 $\log_2 N$ 层。

1.4 在 TALCO 中的作用

TALCO 需要两种归约：

1. 找最大分数：reduction_tree_max，用于维护 $H_{\max}$ 和定位最大分格子；
2. 判断收敛：reduction_tree_value，用于检查所有 PE 的 convergence pointer 是否全部相同。

---

二、reduction_tree_max 逐行解析

2.1 模块声明

module reduction_tree_max #(
        parameter PE_WIDTH = 16,
        parameter SEL_WIDTH = 16,
        parameter NUM_PE = 4,
        parameter LOG_NUM_PE = 2
    )(
        input   logic [SEL_WIDTH - 1: 0] to_sel [0: NUM_PE - 1],
        input   logic signed [PE_WIDTH - 1: 0] array [0: NUM_PE - 1],
        output  logic signed [PE_WIDTH - 1: 0] reduction_value,
        output  logic [LOG_NUM_PE - 1: 0] idx,
        output logic [SEL_WIDTH - 1: 0] selected
    );

参数：

参数	含义
PE_WIDTH	要比较的值的位宽
SEL_WIDTH	伴随数据的位宽（比如坐标、收敛指针）
NUM_PE	输入个数，必须是 2 的幂
LOG_NUM_PE	树的层数 = $\log_2(NUM\_PE)$

端口：

端口	含义
to_sel[NUM_PE]	每个输入携带的伴随数据
array[NUM_PE]	要比较的值（有符号）
reduction_value	最大值
idx	最大值在原始数组中的索引
selected	最大值对应的伴随数据

作用：在 array 中找最大值，同时输出它对应的 to_sel 和 idx。

2.2 局部信号

    logic local_stop;

已声明但从未使用，属于冗余声明。

2.3 Generate 循环结构

    genvar i,j;
    generate
        for ( j = 0; j < LOG_NUM_PE; j = j + 1 ) begin: rt_level
            for ( i = 0; i < 2**(LOG_NUM_PE - j - 1); i = i + 1 ) begin: rt_iter

逐行解释：

• genvar i, j：generate 循环变量。
• 外层 for (j = 0; j < LOG_NUM_PE; j++)：遍历每一层。
• 内层 for (i = 0; i < 2**(LOG_NUM_PE - j - 1); i++)：遍历该层的每一对。
• begin: rt_level 和 begin: rt_iter 给每个 generate 块命名，便于层次化引用。

以 NUM_PE=4, LOG_NUM_PE=2 为例：

层 j	对数 $2^{\log N - j - 1}$	i 的取值
0	$2^{2-0-1} = 2$	i = 0, 1
1	$2^{2-1-1} = 1$	i = 0

2.4 每对比较的局部信号

                logic signed [PE_WIDTH - 1: 0] value1;
                logic signed [PE_WIDTH - 1: 0] value2;
                logic signed [SEL_WIDTH - 1: 0] sel_value1;
                logic signed [SEL_WIDTH - 1: 0] sel_value2;
                logic signed [SEL_WIDTH - 1: 0] selected_val;
                logic signed [PE_WIDTH - 1: 0] out;
                logic [LOG_NUM_PE - 1: 0] idx1;
                logic [LOG_NUM_PE - 1: 0] idx2;
                logic [LOG_NUM_PE - 1: 0] max_idx;

信号	含义
value1, value2	两个待比较的值
sel_value1, sel_value2	两个值对应的伴随数据
selected_val	胜者的伴随数据
out	胜者的值
idx1, idx2	两个值在原始数组中的索引
max_idx	胜者的索引

注意：sel_value1/2 和 selected_val 声明为 signed，但它们只是数据容器，不需要有符号。这是一个小瑕疵，不影响功能。

2.5 第 0 层：从输入数组取数

                if(j == 0) begin
                    assign value1 = array[ i * 2 ];
                    assign value2 = array[ i * 2 + 1 ];
                    assign sel_value1=to_sel[ i*2 ];
                    assign sel_value2=to_sel[ i*2 +1 ];
                    assign idx1 = i * 2;
                    assign idx2 = i * 2 + 1;
                end

逐行解释：

• 第 0 层的输入直接来自模块端口 array 和 to_sel；
• value1 = array[i*2]：取第 $2i$ 个元素；
• value2 = array[i*2+1]：取第 $2i+1$ 个元素；
• sel_value1/sel_value2：对应位置的伴随数据；
• idx1 = i*2、idx2 = i*2+1：原始索引。

例子（NUM_PE=4）：

i	value1	value2	idx1	idx2
0	array[0]	array[1]	0	1
1	array[2]	array[3]	2	3

2.6 第 j 层（j>0）：从前一层取数

                else begin
                    assign value1 = rt_level[ j - 1 ].rt_iter[ i * 2 ].out;
                    assign value2 = rt_level[ j - 1 ].rt_iter[ i * 2 + 1 ].out;
                    assign sel_value1 = rt_level[ j - 1 ].rt_iter[ i * 2 ].selected_val;
                    assign sel_value2 = rt_level[ j - 1 ].rt_iter[ i * 2 + 1 ].selected_val;
                    assign idx1 = rt_level[ j - 1 ].rt_iter[ i * 2 ].max_idx;
                    assign idx2 = rt_level[ j - 1 ].rt_iter[ i * 2 + 1 ].max_idx;
                end

逐行解释：

• 通过层次化引用 rt_level[j-1].rt_iter[k] 访问前一层第 $k$ 对比较的结果；
• value1 = ...out：前一层的胜者值；
• sel_value1 = ...selected_val：前一层的胜者伴随数据；
• idx1 = ...max_idx：前一层的胜者索引。

关键：这里的 idx1、idx2 已经是原始数组中的索引，不是当前层的局部索引。这是因为第 0 层已经把索引设为 i*2，后续层只是把这个索引向上传递。

2.7 比较逻辑

                assign selected_val=($signed(value1) > $signed(value2)) ? sel_value1:sel_value2;
                assign out = ($signed(value1) > $signed(value2)) ? value1 :value2;
                assign max_idx = ($signed(value1) > $signed(value2)) ? idx1 :idx2;

逐行解释：

• 三行都用同一个条件 $signed(value1) > $signed(value2)；
• $signed(...) 强制按有符号数比较，因为分数可能是负数；
• 如果 value1 > value2，选 value1、sel_value1、idx1；
• 否则选 value2、sel_value2、idx2。

注意：使用 > 而不是 >=，所以平局时选右边的（value2）。这是一种确定性的平局策略。

2.8 最终输出

        assign reduction_value = rt_level[LOG_NUM_PE - 1].rt_iter[0].out;
        assign idx = rt_level[LOG_NUM_PE - 1].rt_iter[0].max_idx;
        assign selected= rt_level[LOG_NUM_PE - 1].rt_iter[0].selected_val;
    endgenerate
endmodule

• 最顶层只有一个元素：rt_level[LOG_NUM_PE-1].rt_iter[0]；
• 从它取出 out、max_idx、selected_val 作为模块输出。

---

三、reduction_tree_value 逐行解析

3.1 模块声明

module reduction_tree_value #(
        parameter PE_WIDTH = 16,
        parameter NUM_PE = 4,
        parameter LOG_NUM_PE = 2
    )(
        input   logic [PE_WIDTH - 1: 0] array [0: NUM_PE - 1],
        output  logic [PE_WIDTH - 1: 0] reduction_value,
        output logic reduction_bool
    );

端口：

端口	含义
array[NUM_PE]	输入数组
reduction_value	归约结果值
reduction_bool	所有值是否相同（或 DONT_CARE）

作用：检查所有输入是否相同。如果有 DONT_CARE，则不参与比较。

3.2 局部参数

    logic local_stop;
    parameter CONV_DONT_CARE=0;

信号	含义
local_stop	已声明但未使用，冗余
CONV_DONT_CARE	特殊标记值，0 表示"不参与比较"

3.3 Generate 结构

    genvar i,j;
    generate
        for ( j = 0; j < LOG_NUM_PE; j = j + 1 ) begin: rt_level
            for ( i = 0; i < 2**(LOG_NUM_PE - j - 1); i = i + 1 ) begin: rt_iter

与 reduction_tree_max 完全相同的结构。

3.4 每对比较的局部信号

                logic [PE_WIDTH - 1: 0] value0;
                logic [PE_WIDTH - 1: 0] value1;
                logic [PE_WIDTH - 1: 0] value2;
                logic bool0;
                logic bool1;
                logic bool2;

信号	含义
value1, value2	两个待比较的值
value0	结果值
bool1, bool2	两个输入的"到目前为止是否收敛"标志
bool0	结果标志

注意：这里没有 idx，因为 reduction_tree_value 不关心索引。

3.5 第 0 层：从输入数组取数

                if(j == 0) begin
                    assign value1 = array[ i * 2 ];
                    assign value2 = array[ i * 2 + 1 ];
                    assign bool1 = 1'b1;
                    assign bool2 = 1'b1;
                end

• 第 0 层的输入直接来自 array；
• bool1 和 bool2 初始化为 1'b1，表示"叶节点默认收敛"。

3.6 第 j 层：从前一层取数

                else begin
                    assign value1 = rt_level[ j - 1 ].rt_iter[ i * 2 ].value0;
                    assign value2 = rt_level[ j - 1 ].rt_iter[ i * 2 + 1 ].value0;
                    assign bool1  = rt_level[ j - 1 ].rt_iter[ i * 2 ].bool0;
                    assign bool2  = rt_level[ j - 1 ].rt_iter[ i * 2 + 1 ].bool0;
                end

• 从上一层取 value0 和 bool0；
• bool1、bool2 表示前一层两个子树的收敛状态。

3.7 核心比较逻辑

                wire dontcare1=value1==CONV_DONT_CARE;
                wire dontcare2=value2==CONV_DONT_CARE;
                assign value0 = dontcare1?value2:value1;
                assign bool0=(dontcare1||dontcare2||value1==value2)&&bool1&&bool2;

逐行解释：

第一行：dontcare1 = (value1 == 0)，判断 value1 是否是 DONT_CARE。

第二行：dontcare2 = (value2 == 0)，判断 value2 是否是 DONT_CARE。

第三行：value0 = dontcare1 ? value2 : value1

• 如果 value1 是 DONT_CARE，选 value2；
• 否则选 value1。

第四行：bool0 = (dontcare1 || dontcare2 || value1 == value2) && bool1 && bool2

收敛条件（三选一，且两个子树都收敛）：

条件	含义
dontcare1	value1 是 DONT_CARE，不参与比较
dontcare2	value2 是 DONT_CARE，不参与比较
value1 == value2	两个值相同

再加上 && bool1 && bool2：两个子树的内部也必须都已经收敛。

3.8 真值表

value1	value2	bool1	bool2	value0	bool0
DONT_CARE	DONT_CARE	1	1	DONT_CARE	1
DONT_CARE	$x$	1	1	$x$	1
$x$	DONT_CARE	1	1	$x$	1
$x$	$x$（相同）	1	1	$x$	1
$x$	$y$（不同）	1	1	$x$	0
$x$	$y$（不同）	1	0	$x$	0
$x$	$y$（不同）	0	1	$x$	0

结论：

• 只要有 DONT_CARE，就视为"收敛"（不参与比较）；
• 两个都非 DONT_CARE 时，必须相等才收敛；
• 只要任一子树的 bool 为 0，最终 bool0 也为 0。

3.9 最终输出

        assign reduction_bool  = rt_level[LOG_NUM_PE - 1].rt_iter[0].bool0;
        assign reduction_value = rt_level[LOG_NUM_PE - 1].rt_iter[0].value0;
    endgenerate
endmodule

• 从最顶层取出 bool0 和 value0；
• reduction_bool 表示所有输入是否全部相同（或 DONT_CARE）；
• reduction_value 是归约后的代表值。

---

四、两个模块的对比

特性	reduction_tree_max	reduction_tree_value
目的	找最大值	判断全部相同
比较方式	> 比较大小	== 比较相等
输出	最大值 + 索引 + 伴随数据	值 + 收敛标志
伴随数据	有（to_sel）	无
平局处理	选右边	相等即收敛
DONT_CARE	无	有（0 表示不参与）

---

五、注释掉的备选实现

//            for ( j = LOG_NUM_PE - 1; j <= 0; j = j - 1 ) begin: rt_level_up
//                ...
//            end

这段是迭代式的树遍历实现，用 local_i 追踪从根到叶的路径。
它被注释掉，说明最终选择了 generate 展开版。

区别：

• Generate 版：每层独立展开，适合综合工具；
• 注释版：迭代式，代码更紧凑，但依赖变量更新，不易综合。

---

六、设计中的潜在问题

6.1 CONV_DONT_CARE = 0 可能与真实值冲突

如果某个格子的收敛指针恰好是 0（例如 marker 上 ref_idx=0 的 H 状态），它会被误判为 DONT_CARE。

实践中：

• Marker 通常在非零反对角线上；
• 即使发生，bool0 仍然会正确判断为收敛；
• 但 reduction_value 可能返回另一个值。

6.2 signed 声明的滥用

logic signed [SEL_WIDTH - 1: 0] sel_value1;

sel_value 只是数据容器，不需要 signed。虽然不影响功能，但语义上不准确。

6.3 local_stop 未使用

logic local_stop;

两个模块都有这个未使用的信号，可以删除。

6.4 平局策略

reduction_tree_max 用 > 而不是 >=，平局时选右边。这在 TALCO 中是可接受的，但如果需要选最左边的最大值，应改为 >=。

---

七、一句话总结

reduction_tree_max 用 generate 展开的二叉树并行找最大值，同时输出对应的索引和伴随数据；reduction_tree_value 用同样的结构判断所有输入是否相等，支持 DONT_CARE 标记。两者都在 $\log_2(NUM\_PE)$ 层内完成归约，是 TALCO 中维护 $H_{\max}$ 和检测收敛的核心硬件结构。