Skip to main content

3 PE Array vs Paper

PE_Array.sv 与论文的对应关系

下面把 PE_Array.sv 的每个部分和论文（TALCO Algorithm 1、Figure 7、Section IV）逐一对应。

一、整体框架对应​

论文概念论文位置PE_Array 中的实现
TALCO-Align 单元Fig. 6PE_Array 模块整体
PE 阵列Fig. 7agenerate for 实例化的 NUM_PE 个 PE
Systolic 阵列Fig. 7asystolic_array_connections 中的连接
Phase 1 / Phase 2Algorithm 1 line 14–20past_marking 信号区分
MarkerAlgorithm 1 line 10marker 输入信号
Convergence pointerAlgorithm 1 line 21CH_PE、CI_PE、CD_PE
Reduction treeFig. 7areduction_tree_max、reduction_tree_value
Traceback LogicFig. 7atraceback 模块
收敛检测Algorithm 1 line 25convergence_detected 信号
下一个 tile 起点Algorithm 1 line 37query_next_tile_addr、ref_next_tile_addr

二、状态机与 Algorithm 1 的对应​

2.1 外层循环：多个 tile​

WAIT → READ_PARAM → SET_PARAM → STREAM_REF_START → STREAM_REF → ... → TB → EXIT
状态论文中的动作Algorithm 1 行号
WAIT等待下一个 tileline 4
READ_PARAM加载参数—
SET_PARAM初始化 tile 起点分数line 6 Sprev ← Smarker
STREAM_REF_START初始化 PE 阵列line 7 TBTile ← 2-D matrix
STREAM_REFPhase 1 或 Phase 2 计算line 9 AlignScore(...)
STREAM_REF_CONTINUE切换到下一个 block—
DONE当前 tile 计算完成line 37 tb.append(AlignTraceback(...))
TBTracebackline 37
EXIT准备下一个 tileline 38 i ← i+M

2.2 内层循环：Phase 1 和 Phase 2​

logic past_marking;
always @(posedge clk ) begin
    past_marking<=curr_ad_idx>marker+1;
end
信号论文中的阶段
!past_markingPhase 1：j - i < M（Algorithm 1 line 14）
past_markingPhase 2：j - i >= M（Algorithm 1 line 20）

curr_ad_idx 就是论文中的 frontier 索引 jj。

三、PE 阵列与论文 Figure 7a 的对应​

3.1 PE 阵列的 systolic 连接​

generate
    for (i = 1; i < NUM_PE; i = i + 1)
    begin: systolic_array_connections
        assign init_in[i] = (STATE==STREAM_REF_CONTINUE)?0:init_out[i-1];
        assign ref_in[i]  = ref_out[i-1];
        assign ref_idx_in[i] = ref_idx_out[i-1];
        assign query_idx_in[i] = query_idx_out[i-1];
        assign H_PE_prev[i] = H_PE[i-1];
        assign I_PE_prev[i] = I_PE[i-1];
        assign CH_PE_prev[i] = CH_PE[i-1];
        assign CI_PE_prev[i] = CI_PE[i-1];
    end
endgenerate

对应论文 Figure 7a 中：

  • PE 之间的箭头（ref_in/out、H_PE_prev、I_PE_prev）；
  • 每个 PE 把结果传给下一个 PE。

3.2 Figure 7b 的 Query blocking​

PE #(
    ...
    .PE_IDX(i),
    ...
) pe_affine (...)
  • 每个 PE 绑定一个 PE_IDX，对应 Figure 7b 中不同的 PE 处理不同的 query 行；
  • 图中颜色区分不同 PE 计算的格子，代码中用 PE_IDX 区分。

四、Reduction Tree 与论文的对应​

4.1 最大分数归约​

reduction_tree_max # (
    .PE_WIDTH(PE_WIDTH),
    .SEL_WIDTH(REF_LEN_WIDTH+2+REF_LEN_WIDTH+QUERY_LEN_WIDTH),
    .NUM_PE(NUM_PE),
    .LOG_NUM_PE(LOG_NUM_PE)
    ) rd_tree_max (
        .to_sel(max_val_to_sel),
        .array(H_PE),
        .reduction_value(rd_value),
        .selected(selected_idx)
);

对应论文 Section IV：

"A running maximum score (HmaxH_{max}) is maintained in a systolic fashion."

rd_value 就是 HmaxH_{max}，selected_idx 是对应的坐标。

4.2 收敛检测归约​

reduction_tree_value # (...) rd_tree_M (
    .array(CH_PE),
    .reduction_value(H_rd_value),
    .reduction_bool(H_converged_this_block)
);

reduction_tree_value # (...) rd_tree_I (
    .array(CI_PE),
    .reduction_value(I_rd_value),
    .reduction_bool(I_converged)
);

reduction_tree_value # (...) rd_tree_D (
    .array(CD_PE),
    .reduction_value(D_rd_value),
    .reduction_bool(D_converged)
);

对应论文 Section IV：

"A reduction tree is used to determine if all NPEN_{PE} pointers computed by NPEN_{PE} PEs in each cycle for the subset of the wavefront in the current stripe have converged to the same cell."

三个 reduction tree 分别检查 H、I、D 状态的收敛指针。

五、收敛检测与 Algorithm 1 的对应​

5.1 收敛条件​

assign H_converged = H_converged_this_block &&
    H_converged_prev_block &&
    past_marking &&
    (!not_last_droped_in_prev_block || H_rd_value == CH_PE_prev_block_pipe);

对应论文 Algorithm 1 line 25：

"if all pointers in ConvPrcurr point to a marker cell"

5.2 收敛确认​

assign this_ad_converged =
    H_converged &&
    CID_prev_block &&
    I_converged &&
    D_converged &&
    (I_rd_value==H_rd_value||I_rd_value==CONV_DONT_CARE||H_rd_value==CONV_DONT_CARE) &&
    (D_rd_value==H_rd_value||D_rd_value==CONV_DONT_CARE||H_rd_value==CONV_DONT_CARE);

对应论文 Algorithm 1 line 25：

"if all pointers in ConvPrcurr point to a marker cell"

5.3 收敛检测​

assign convergence_detected = C5 && (STATE==STREAM_REF) && init_out[0] && (!init_n || !last_PE_not_droped) && !lower_bound_check;

对应论文 Algorithm 1 line 25–27：

if all pointers in ConvPrcurr point to a marker cell then
    C_tb ← C_x
    break

六、Phase 1 与 Algorithm 1 的对应​

6.1 Phase 1 存储 traceback 指针​

assign tb_bram_wr_en_next = init_out[0] && (was_stream_ref || (STATE==STREAM_REF)) && (!past_marking);

对应论文 Algorithm 1 line 15：

TBTile[j-i] ← Prf
  • !past_marking 表示还在 Phase 1；
  • tb_bram_data_in <= dir_out 把 PE 阵列的 4-bit 指针写入 traceback BRAM。

6.2 Phase 1 结束条件​

always @(posedge clk ) begin
    if(rst)
        last_tile<=0;
    else if(STATE==TB&&start_tb_from_xdrop)
        last_tile<=1; 
end

对应论文 Algorithm 1 line 16–18：

if j has reached the end of the alignment then
    Cib ← Clast
    break

七、Phase 2 与 Algorithm 1 的对应​

7.1 Phase 2 传播 convergence pointer​

assign prev_block_to_write = {this_ad_converged, H_converged, CH_PE[NUM_PE - 1], CI_PE[NUM_PE - 1], H_PE[NUM_PE - 1], I_PE[NUM_PE - 1], ad_max_score_next};

对应论文 Algorithm 1 line 21：

ConvPrcurr ← redirect(Prf, ConvPrprev)

prev_block_to_write 保存了当前 frontier 的 convergence pointer，写入 score_bram 供下一个 block 使用。

7.2 Phase 2 存储 convergence pointer​

sft_reg #(.BW(CONV_SCORE_WIDTH),.DEPTH(3)) score_wr_delay(
    .clk(clk),
    .en(1),
    .in(prev_block_to_write),
    .out(score_bram_data_in));
  • 对应论文 Algorithm 1 line 21：ConvPrcurr ← redirect(Prf, ConvPrprev)；
  • score_bram 存储的是 convergence pointer，不是 traceback pointer。

7.3 Phase 2 终止条件​

assign convergence_detected = C5 && (STATE==STREAM_REF) && init_out[0] && (!init_n || !last_PE_not_droped) && !lower_bound_check;

对应论文 Algorithm 1 line 25：

if all pointers in ConvPrcurr point to a marker cell then
    C_tb ← C_x
    break

八、Marker 与 Algorithm 1 的对应​

8.1 Marker 信号​

input  logic [LOG_MAX_TILE_SIZE : 0] marker,

对应论文 Algorithm 1 中的 marker fMf_M。

8.2 Marker 与 anti-diagonal 比较​

always @(posedge clk ) begin
    past_marking<=curr_ad_idx>marker+1;
end
  • curr_ad_idx 是当前 anti-diagonal 索引；
  • 当 curr_ad_idx > marker + 1 时，past_marking = 1，表示进入 Phase 2。

对应论文 Algorithm 1 line 10：

if j-i = M-1 then Reached Marker

8.3 Marker 初始化​

在 PE.sv 中：

if (ref_idx + query_idx == marker - 1) begin
    CH_score = {ref_idx, 2'b11};
    ...
end
else if (ref_idx + query_idx == marker) begin
    CH_score = {ref_idx, 2'b00};
    CI_score = {ref_idx, 2'b01};
    CD_score = {ref_idx, 2'b10}; 
end

对应论文 Algorithm 1 line 11：

ConvPrprev ← A unique id for each cell in Scurr

九、Traceback 与 Algorithm 1 的对应​

9.1 Traceback 启动​

wire start_tb_from_xdrop;
assign start_tb_from_xdrop = global_max_ad_idx <= (marker+2);
  • 如果最大分格子出现在 marker 附近，说明是 X-Drop 剪枝，不是收敛；
  • 对应论文 Algorithm 1 line 28–29：
else if f has reached the end of the alignment then
    Cib ← ConvPrlatt
    break

9.2 Traceback 起点​

assign query_next_tile_addr = start_tb_from_xdrop ? global_max_query_idx : conv_query_idx;
assign ref_next_tile_addr = start_tb_from_xdrop ? global_max_ref_idx : conv_ref_idx;
assign next_tile_init_state = start_tb_from_xdrop ? 0 : conv_tb_state;
  • 如果从 X-Drop 开始，用全局最大分格子；
  • 如果从收敛点开始，用 conv_query_idx、conv_ref_idx、conv_tb_state；
  • 对应论文 Algorithm 1 line 26：C_tb ← C_x。

9.3 Traceback 实例化​

traceback #(...) tb (
    .clk(clk),
    .rst(rst),
    .tb_start(tb_start), 
    .start_query_idx(query_next_tile_addr),
    .start_ref_idx(ref_next_tile_addr),
    .start_tb_state(next_tile_init_state),
    ...
);

对应论文 Algorithm 1 line 37：

tb.append(AlignTraceback(TBTile, Cib))

十、下一个 tile 起点与 Algorithm 1 的对应​

10.1 下一个 tile 的起点​

assign query_next_tile_addr = start_tb_from_xdrop ? global_max_query_idx : conv_query_idx;
assign ref_next_tile_addr = start_tb_from_xdrop ? global_max_ref_idx : conv_ref_idx;
assign next_tile_init_state = start_tb_from_xdrop ? 0 : conv_tb_state;

对应论文 Algorithm 1 line 37–38：

tb.append(AlignTraceback(TBTile, Cib))
i ← i+M

10.2 Marker 分数初始化​

always_ff @( posedge clk ) begin
    if(STATE==STREAM_REF_START)
        H_init <= (block || init_state != 3) ? -INF : gap_open_in;
    else if(STATE==STREAM_REF)
        H_init <= (block || init_state != 3) ? -INF : boundary_init_H_score_next;
end

对应论文 Algorithm 1 line 6：

Sprev ← Smarker

10.3 分数连续​

assign diag_delayed = score_bram_loaded_first ? H_prev_block : ...;
  • diag_delayed 是上一个 block 的最后一行的 H 分数；
  • 用于下一个 block 的对角线初始化；
  • 对应论文 Algorithm 1 line 6 中"用 marker 分数初始化下一个 tile"。

十一、X-Drop 剪枝与论文的对应​

11.1 X-Drop 条件​

assign last_PE_not_droped = (H_PE[NUM_PE-1]+xdrop_value) >= ad_max_score;

对应论文 Section IV：

"A stripe calculation terminates when scores of all cells along a column drop below (Hmax−X)(H_{max} - X)"

  • H_PE[NUM_PE-1] 是最右 PE 的 H 分数；
  • ad_max_score 是当前最大分数 HmaxH_{max}；
  • xdrop_value 是 XX；
  • 条件等价于 H+X≥HmaxH + X \geq H_{max}。

11.2 X-Drop 终止​

C3 = (!not_last_droped_in_prev_block) && init_0_delayed && (rd_value + xdrop_value < ad_max_score);

对应论文 Section IV 中的剪枝条件。

十二、Block 与论文的对应​

12.1 Block 的概念​

block 不是论文中的显式概念，而是硬件为了处理 X-Drop 动态带子而引入的。

概念论文硬件
TileAlgorithm 1 中的外层循环单元TALCO_XDrop 的输入
Block论文未显式提及PE_Array 内部切分
FrontierAlgorithm 1 中的 fjf_j一个 anti-diagonal
Wavefront论文中的 wavefront一个 stripe（NUM_PE 个格子）

12.2 Block 切换​

STREAM_REF_CONTINUE: begin
    block <= 1; 
    start_idx <= lower_bound_value;
    ref_bram_addr <= lower_bound_value;
    ref_idx_in[0] <= lower_bound_value;
    curr_ref_length <= lower_bound_value;
    query_idx_in[0] <= curr_query_length;
    block_count <= block_count + 1;
    score_bram_wr_en <= 0;
end
  • 对应论文中 tile 内部的循环继续；
  • Block 之间通过 lower_bound_value 衔接。

十三、内存与论文的对应​

论文内存硬件实现
M×BmaxM \times B_{max} traceback 指针tb_bram
BmaxB_{max} 分数H_PE、I_PE、D_PE
Convergence pointerCH_PE、CI_PE、CD_PE
score_bram存储跨 block 的 convergence 信息和分数

论文 Section III：

"the maximum memory required for a single tile in TALCO is O(M×Bmax+log⁡2(Bmax)×Bmax)\mathcal{O}(M \times B_{max} + \log_2(B_{max}) \times B_{max})"

对应的硬件：

  • tb_bram 存 M×BmaxM \times B_{max} 个 4-bit 指针；
  • score_bram 存跨 block 的 convergence pointer。

十四、总结表格​

论文PE_Array 代码
Algorithm 1 外层循环WAIT → ... → TB → EXIT 状态机
Algorithm 1 内层循环STREAM_REF 状态
Phase 1（j-i < M）!past_marking
Phase 2（j-i >= M）past_marking
Marker fMf_Mmarker 信号
Sprev ← SmarkerH_init、diag_delayed
TBTile[j-i] ← Prftb_bram_data_in <= dir_out
ConvPrcurr ← redirect(...)prev_block_to_write、score_bram
all pointers point to a marker cellconvergence_detected
C_tb ← C_xquery_next_tile_addr、ref_next_tile_addr
AlignTraceback(TBTile, C_tb)traceback 模块
i ← i+MEXIT 状态
HmaxH_{max}ad_max_score
X-Drop 剪枝last_PE_not_droped、C3
收敛检测reduction_tree_value
最大分数归约reduction_tree_max
PE 阵列generate for 实例化的 NUM_PE 个 PE
Systolic 连接systolic_array_connections

一句话总结：

PE_Array.sv 是论文 Algorithm 1 的硬件实现。状态机对应外层/内层循环，past_marking 对应 Phase 1/Phase 2 分界，三个 reduction tree 对应收敛检测，traceback 模块对应 AlignTraceback，query_next_tile_addr 和 ref_next_tile_addr 对应下一个 tile 的起点。Block 是硬件为处理动态 X-Drop 带子而引入的额外切分，论文中未显式提及，但通过 diag_score 和 score_bram 保证了分数和收敛信息的连续性。