Skip to main content

TALCO

TALCO: Tiling Genome Sequence Alignment using Convergence of Traceback Pointers

PDF

Code -

Memory-constant parallel computing​

Take advantage of the “convergence” phenomenon of traceback pointers—multiple backtracking paths eventually meet at a single cell. This allows us to identify a definite point along the tile boundary, ensuring that the partitioned computation yields results identical to those obtained via a full comparison.

Leveraging the “different paths leading to the same outcome” property of path backtracking, complex global problems can be broken down into smaller, independently solvable sub-problems.

1. TALCO XDrop​

DP​

Fill in the score matrix + record the optimal source pointer for each cell + backtrack from the endpoint along the pointers.

  • NW (Needleman-Wunsch) requires a global alignment; even if only a small portion in the middle of two sequences is similar, NW still forces an alignment at both ends, potentially resulting in numerous gaps.
  • Smith-Waterman：SW compares only the most similar subsequence between the two sequences.

DP-PE illustration

DP-PE

TALCO adaptive​

TALCO adapts based on data, with less redundancy when convergence (phase 2) is fast and more redundancy when convergence is slow, but never at the expense of correctness.

The number of frontiers calculated in Phase 2 is not fixed but determined dynamically by the data: the faster convergence, the fewer frontiers computed, resulting in less redundancy and higher efficiency. These Phase 2 frontiers are recalculated in the next tile, representing redundant computation, yet they ensure consistency with the results of the full banded algorithm.

Architecture​

Architecture

DP XDrop​

XDrop illustration

XDrop

对于H score, 由于阵列是 systolic 的，PE[0] 分数最高，PE[NUM_PE-1] 分数最低（近似），所以只需检查最后一个 PE。 score<Hmax−Xscore < H_{max} - X

assign xdrop_flag = (H_PE[NUM_PE-1] + xdrop_value) < ad_max_score;

ad_max_score 是目前为止HmaxH_{max}在当前 block 内保持，用于判断剪枝。当 xdrop_flag = 1时，表示整行被 X-Drop 剪枝。第一次xdrop_flag从1 -> 0时，H_PE[NUM_PE-1]的 reference index 即为下一个block的起点。接着从0 -> 1则该block结束计算。

D 不跨 block 继承：D 状态在每个 block 开始时强制为 -INF，因为它可以通过 H 状态重新产生（开 gap），不需要跨 block 传递。

lower_bound_value 是“第一个未被剪枝的行”。在它之前的行都被 X-Drop 剪枝了。如果 block 2 从 lower_bound_value 开始，它需要的 D(lower_bound_value - 1, j) 来自被剪枝的行。这些行的分数低于 ad_max_score - xdrop_value，其 D 值即使存在也不可靠，不应该被继承。

X-Drop 的核心假设是：最优路径不会经过被剪枝的区域。如果最优路径真的需要延续之前的 D 状态，那么它经过的行分数一定不会低于剪枝阈值，也就不会被剪枝。因此，在 block 边界丢弃 D 的 extend 路径，不会影响最优对齐。

convergence​

convergence illustration

convergence

reduction tree​

reduction tree illustration

reduction tree

traceback​

traceback illustration

traceback

给定一个起始单元（由收敛检测或 X-Drop 最大分数确定），沿着 traceback_bram 中存储的方向指针，逐步回溯到比对起点 (0,0)，同时输出每一步的移动方向。

起始cell:

  • 收敛点: （ifHmax‘>=Hmaxif H^`_{max} >= H_{max})
  • HmaxH_{max} 所在的cell: （ifHmax‘<Hmaxif H^`_{max} < H_{max})

traceback_bram_data: {dir[PE0],dir[PE1],...,dir[PE15]}

回溯过程中需要追踪四个量：

logic [LOG_NUM_PE-1:0] query_pe_idx;      // 当前在哪个 PE 内 (0 ~ NUM_PE-1)
logic [TB_ADDR_WIDTH-1:0] cur_blk_idx;    // 当前在哪个 block
logic [REF_LEN_WIDTH-1:0] curr_ref_idx;   // 当前参考索引
logic [1:0] cur_tb_state;                 // 当前状态 (H=0, D=1, I=2)

当 query_pe_idx 下溢时，说明跨越了一个 PE 组，需要切换到更早的块；

从traceback_bram读出的数据， 包含 NUM_PE 个 PE 的指针，每个 4 位：

assign tb_ptr_read = tb_bram_data_out[query_pe_idx*4 +: 4];
assign {insert_extend, delete_extend, h_move} = tb_ptr_read;

2. TALCO WFAA​