GenDP §3.1 — 4×4 PE Array DP Table Walkthrough
2D DP Table 映射规则(论文 §3.1):
• 每一行映射到一个 PE,PE 内静态存储该行的目标序列元素 X[i]。
• 查询序列元素 Y[j] 在 PE 阵列中流式传输。
• 每个单元格 H(i,j) 依赖三个邻居:H(i-1,j-1)(对角线,来自前一个 PE)、H(i-1,j)(上方,来自前一个 PE)、H(i,j-1)(左方,存储在 PE 内部)。
• 波前并行:同一条反对角线 i+j = k 上的单元格可以同时计算。
公式:H(i,j) = max(0, H(i-1,j-1) + S(X[i],Y[j]), H(i-1,j) - g, H(i,j-1) - g)
参数:match = +2,mismatch = −1,gap = 2。初始全部为 0。
边界 (i=0 或 j=0)
已计算
当前波前
依赖单元格