2.1.1 BSW wavefront

在论文 Table 1 里，BSW 那一行写的 “Last 2 Wavefronts”，意思是：计算当前波前（wavefront）上的所有单元格时，只需要用到前两个波前的结果。这描述的是 DP 表的依赖距离，也是硬件能并行计算的关键。

---

1. 什么是 wavefront？

在二维 DP 表中，每个单元格用 $(i,j)$ 表示，$i$ 是行号，$j$ 是列号。
如果按行或按列顺序计算，每个格子依赖左边、上边、左上角，无法大规模并行。

但是，如果换一种顺序：沿着反对角线计算，情况就不一样了。

反对角线满足：

$i + j = \text{常数}$

例如：

• $i+j=0$：$(0,0)$
• $i+j=1$：$(1,0), (0,1)$
• $i+j=2$：$(2,0), (1,1), (0,2)$
• $i+j=3$：$(3,0), (2,1), (1,2), (0,3)$

每一条这样的反对角线，就叫一个 wavefront（波前）。

在 DP 表中，同一条 wavefront 上的单元格之间没有依赖关系，所以可以同时计算。
这就是“波前并行”（wavefront parallelism）。

---

2. 为什么同一 wavefront 可以并行？

以 BSW 的 $H(i,j)$ 为例，它的递推大致是：

$$H(i,j)=\max\{0,\ H(i-1,j-1)+S(X(i),Y(j)),\ E(i,j),\ F(i,j)\}$$

其中：

• $H(i-1,j-1)$：左上角，属于 $i+j-2$ 这条 wavefront；
• $H(i-1,j)$：上边，属于 $i+j-1$ 这条 wavefront；
• $H(i,j-1)$：左边，属于 $i+j-1$ 这条 wavefront。

再看 $E(i,j)$ 和 $F(i,j)$：

• $E(i,j)$ 依赖 $H(i-1,j)$ 和 $E(i-1,j)$，它们都在 $i+j-1$ 这条 wavefront；
• $F(i,j)$ 依赖 $H(i,j-1)$ 和 $F(i,j-1)$，它们也都在 $i+j-1$ 这条 wavefront。

所以，要计算 wavefront $k = i+j$ 上的所有单元格，只需要：

• wavefront $k-1$ 的数据；
• wavefront $k-2$ 的数据。

这就是“Last 2 Wavefronts”的含义：当前波前只依赖最近的两个波前。

---

3. 画个图更直观

假设有一个 4×4 的 DP 表，坐标如下：

      j=0   j=1   j=2   j=3
i=0   (0,0) (0,1) (0,2) (0,3)
i=1   (1,0) (1,1) (1,2) (1,3)
i=2   (2,0) (2,1) (2,2) (2,3)
i=3   (3,0) (3,1) (3,2) (3,3)

按 $i+j$ 分组：

• $i+j=0$：$(0,0)$
• $i+j=1$：$(1,0), (0,1)$
• $i+j=2$：$(2,0), (1,1), (0,2)$
• $i+j=3$：$(3,0), (2,1), (1,2), (0,3)$
• $i+j=4$：$(3,1), (2,2), (1,3)$
• $i+j=5$：$(3,2), (2,3)$
• $i+j=6$：$(3,3)$

每一条斜线就是一个 wavefront。
计算 $i+j=3$ 这一波时，只需要 $i+j=2$ 和 $i+j=1$ 的数据。
计算 $i+j=4$ 时，只需要 $i+j=3$ 和 $i+j=2$ 的数据。
以此类推。

---

4. 在 BSW 中，带状区域如何影响 wavefront？

BSW 是 banded 的，只计算 $|i-j| \le w$ 范围内的单元格。
所以每个 wavefront 并不是完整的反对角线，而是被限制在带状区域内的那一小段。

例如，如果 $w=1$，那么：

• wavefront $i+j=2$ 只包含 $(1,1)$ 附近几个格子；
• 更远的格子不计算。

但依赖关系不变：当前波前仍然只依赖前两个波前。

---

5. 为什么这对 GenDP 硬件加速很重要？

因为“只依赖前两个波前”意味着：

1. 数据可以流水化：PE 阵列按波前推进，当前波前算完，数据传给下一个 PE，形成 systolic 流水线。
2. 存储需求小：不需要保存整个 DP 表，只需要保留最近两个波前的数据。GenDP 用 FIFO 和寄存器在相邻 PE 之间传递这些数据。
3. 并行度高：同一条波前上的多个单元格可以映射到多个 PE 同时计算。
4. 适合带状 BSW：带状区域进一步缩小波前长度，减少无效计算。

论文里说 BSW “Last 2 Wavefronts”，就是在强调它的依赖距离很短，非常适合做波前并行和 systolic array 加速。

---

6. 一句话总结

Wavefront 就是 DP 表中同一条反对角线 $i+j=\text{常数}$ 上的单元格集合。
“Last 2 Wavefronts” 表示当前波前只依赖前两个波前，因此可以按波前流水并行计算。
BSW 正是利用这种短依赖距离，在 GenDP 的 PE 阵列上高效并行执行。