6 LTDP Examples

第 6 节 LTDP EXAMPLES 精读

这一节把四个实际问题逐一映射到 LTDP 框架。目标是回答：

这四个问题凭什么属于 LTDP？怎么分组？为什么有的能用 Delta 方法，有的不能？

下面逐个拆解，最后做对比总结。

---

一、Viterbi：取 log 后变成 LTDP，但不是 LLTDP

1. 问题背景

The Viterbi algorithm [Viterbi 1967] finds the most likely sequence of states in a (discrete) hidden Markov model (HMM) for a given sequence of $n$ observations.

给定观测序列，在 HMM 中找最可能的状态路径。递推式在 Figure 1(a)：

$$p_{i,j} = \max_k \big(p_{i-1,k} \cdot t_{k,j}\big) \cdot e_j(o_i)$$

其中：

• $p_{i,j}$：解释前 $i$ 个观测、且第 $i$ 步在状态 $j$ 的最可能路径的概率。
• $t_{k,j}$：从状态 $k$ 转移到状态 $j$ 的概率。
• $e_j(o_i)$：在状态 $j$ 观测到 $o_i$ 的发射概率。

2. 为什么不能直接套 LTDP

LTDP 要求递推是热带线性的（max 和 +）。但 Viterbi 的递推是概率的乘法和 max：

$$p_{i,j} = \max_k(p_{i-1,k}\cdot t_{k,j})\cdot e_j(o_i)$$

这是"乘法 + max"，不是"加法 + max"，不符合公式 (1)。

3. 取 log 的变换

But applying a logarithm on both sides to the recurrence equation brings it to this form. By transforming the Viterbi instance into one that calculates log-probabilities instead of probabilities, we obtain an LTDP instance.

对两边取 log：

$$\log p_{i,j} = \max_k\big(\log p_{i-1,k} + \log t_{k,j}\big) + \log e_j(o_i)$$

关键变换：

原式	取 log 后
概率乘法 $a\cdot b$	log 加法 $\log a+\log b$
max	max（不变，log 单调）
概率	log 概率

现在递推是"加法 + max"，正好是热带半环的矩阵-向量乘法。令：

$$s_i[j]=\log p_{i,j},\quad A_i[j,k]=\log t_{k,j}+\log e_j(o_i)$$

则：

$$s_i[j]=\max_k(s_{i-1}[k]+A_i[j,k])$$

这就是 LTDP 公式 (1)。

4. 额外阶段 $n+1$：把答案挪到第 0 个位置

Invoking the LTDP parallel algorithm in Figure 4 requires one additional transformation. The algorithm assumes that the solution to LTDP is given by the first subproblem in the last stage $n$. To account for this, we introduce an additional stage $n + 1$ in which every subproblem is the maximum of all subproblems in stage $n$.

问题：Viterbi 的答案是 $\max_j p_{n,j}$（最后一列的最大值），不是 $p_{n,0}$。但第 3 节的顺序算法和 Rank-1 方法都假设"答案在最后阶段的第 0 个位置"。

解决：加一个额外阶段 $n+1$，每个子问题都是阶段 $n$ 的最大值：

$$s_{n+1}[j]=\max_k s_n[k]\quad\forall j$$

这样 $s_{n+1}[0]=\max_k s_n[k]$ 就是答案。

用矩阵表示：$A_{n+1}$ 是一个全 0 矩阵（热带半环里 0 是乘法单位元）：

$$(A_{n+1}\odot\vec{s}_n)[j]=\max_k(0+s_n[k])=\max_k s_n[k]$$

所以阶段 $n+1$ 的每个子问题都等于阶段 $n$ 的最大值，第 0 个位置就是答案。

5. 为什么 Viterbi 不是 LLTDP

The Viterbi algorithm is not an LLTDP since the dependence edges are not local and they cross. Therefore, the Delta method is not applicable.

LLTDP 要求每个格子只依赖 3 个局部邻居。但 Viterbi 中，状态 $j$ 可以依赖前一阶段的任何状态 $k$（HMM 的转移矩阵通常是稠密的，或至少不是局部的）。依赖边"交叉"，不是局部邻居。

后果：

• Viterbi 不能用 Delta 方法（第 5 节）。
• Viterbi 只能用 Rank-1 方法（第 4 节）。

6. Viterbi 的 LTDP 属性总结

属性	值
是否 LTDP	✅（取 log 后）
是否 LLTDP	❌（依赖非局部）
可用并行方法	Rank-1 方法
额外处理	加阶段 $n+1$（全 0 矩阵）把答案挪到第 0 位

---

二、LCS：两种分组方式，LLTDP，delta 只有 0/1

1. 问题背景

LCS finds the longest common subsequence of two input strings $A$ and $B$.

递推式（Figure 1(b)）：

$$C_{i,j}=\max\begin{cases} C_{i-1,j}\\ C_{i,j-1}\\ C_{i-1,j-1}+\delta_{i,j} \end{cases}$$

其中 $\delta_{i,j}=1$ 若 $A[i]=B[j]$，否则 $0$。

2. 分组方式 1：反对角线

In the first approach, the stages correspond to antidiagonals, such as the stage consisting of $z_{1}$s in Figure 10(a). This stage depends on two previous stages (on $x_{1}$s and $y_{1}$s) and does not strictly follow the rules of LTDP.

反对角线分组（Figure 10(a)）：

      j=0  1  2  3
i=0    x1 y1 z1 ...
i=1    y1 z1 ...
i=2    z1 ...

同一反对角线（如所有 $z_1$）的格子互不依赖，可以并行。

问题：反对角线 $z_1$ 依赖两个前驱反对角线（$x_1$ 和 $y_1$），不满足 LTDP"只依赖前一阶段"的条件。

解决：定义重叠的反对角线对：

One way to get around this is to define stages as overlapping pairs of antidiagonals, like stage $x - y$ and stage $y - z$ in Figure 10(a). Subproblems $y_{1}$s are replicated in both stages, allowing stage $y - z$ to depend only on stage $x - y$.

• 阶段 1 = $x\cup y$（两条反对角线）。
• 阶段 2 = $y\cup z$（两条反对角线）。
• $y$ 在阶段 1 和阶段 2 中重复出现。
• 阶段 2 只依赖阶段 1（因为 $z$ 依赖 $x,y$，而 $x,y$ 都在阶段 1 中）。

这样满足 LTDP 条件。

3. 分组方式 2：行（或列）

In the second approach, the stages correspond to the rows (or columns) as shown in Figure 10(b). The recurrence needs to be unrolled to avoid dependencies between subproblems within a stage.

行分组（Figure 10(b)）：每一行是一个阶段。

问题：$C_{i,j}$ 依赖 $C_{i,j-1}$，这是同一行内的依赖，不满足"只依赖前一阶段"。

解决：展开递推。$C_{i,j}$ 依赖 $C_{i,j-1}$，$C_{i,j-1}$ 又依赖 $C_{i,j-2}$……最终 $C_{i,j}$ 可以写成只依赖第 $i-1$ 行的形式。展开后，$A_i[j,k]$ 编码"从第 $i-1$ 行第 $k$ 个位置到第 $i$ 行第 $j$ 个位置"的最优路径权重。

代价：展开后矩阵 $A_i$ 可能变稠密，计算量增加。但换来严格的 LTDP 形式。

4. 宽度限制 $w$

Some applications of LCS, such as the diff utility tool, are only interested in solutions that are at most a width $w$ away from main diagonal... For these applications, the recurrence relation can be modified such that $C_{i,j}$ is set to $-\infty$ whenever $|i - j| > w$.

带宽限制：只计算主对角线附近宽度 $w$ 的带状区域，带外设为 $-\infty$。

好处：

• 减少内存（不需要存整个表）。
• 减少计算量。

坏处：

• 阶段变小（每行只有 $w$ 个格子），波前并行的并行度降低。
• 这正是本文"跨阶段并行"的用武之地：阶段小，波前并行不够，需要跨阶段并行补充。

5. LCS 是 LLTDP

LCS is an LLTDP problem as it can be checked from Figure 10. Therefore, the parallel Delta method from Section 5.2 can be applied.

LCS 每个格子只依赖上、左、左上三个邻居，是局部的，所以是 LLTDP。

两种方法都可用：

• Rank-1 方法：需要定义阶段（反对角线对或行分组）。
• Delta 方法：直接用局部性，存 delta。

6. delta 只有 0/1

One can show that deltas in the LCS problem are either 1 or 0. This allows compactly representing the deltas as a sequence of bits [Hyyro 2004].

LCS 的 $C_{i,j}$ 是整数，相邻格子的差 $\delta_{i,j}=C_{i,j}-C_{i,j-1}$ 只能是 0 或 1（因为 LCS 长度每次最多增加 1）。

好处：delta 可以用1 个 bit 表示，SIMD 一次处理 64/128 个格子，效率极高。这是第 7.3.4 节 LCS 基线用 bit-parallelism 的原因。

7. LCS 的 LTDP 属性总结

属性	值
是否 LTDP	✅（两种分组方式）
是否 LLTDP	✅（局部依赖）
可用并行方法	Rank-1 方法、Delta 方法
delta 范围	1，可用 bit 表示
特殊处理	反对角线对分组，或行分组 + 展开

---

三、Needleman-Wunsch：与 LCS 类似，LLTDP，delta 范围较大

1. 问题背景

This algorithm [Needleman and Wunsch 1970] finds a global alignment of two input sequences, commonly used to align protein or DNA sequences.

全局序列比对。递推式：

$$s_{i,j}=\max\begin{cases} s_{i-1,j}-d\\ s_{i,j-1}-d\\ s_{i-1,j-1}+m[i,j] \end{cases}$$

其中：

• $s_{i,j}$：前 $i$ 个字符和前 $j$ 个字符的最优比对分数。
• $m[i,j]$：匹配分数（相同字符为正，不同为负）。
• $d$：插入/删除罚分。

边界条件：$s_{i,0}=-i\cdot d$，$s_{0,j}=-j\cdot d$。

2. 与 LCS 的关系

Abstractly, one can think of LCS as an instance of Needleman-Wunsch for appropriate values of matching scores and insert/delete penalties.

LCS 是 NW 的特例：

• 匹配分数 $m[i,j]=\delta_{i,j}$（相同为 1，不同为 0）。
• 罚分 $d=0$。

但论文说"实现细节差异足够大，当作两个算法处理"。

3. NW 是 LLTDP

The Needleman-Wunsch algorithm is also an LLTDP problem as it can be checked from the formula.

和 LCS 一样，每个格子只依赖上、左、左上三个邻居，是 LLTDP。

两种方法都可用：

• Rank-1 方法（行分组或反对角线对分组）。
• Delta 方法（更优，见第 7.4 节）。

4. delta 范围

Similarly, one can show that deltas are in the range of $[- d \ldots (\max_{i,j} m[i,j] + d)]$, allowing compact representation.

delta 范围：$[-d,\ \max m+d]$。

为什么：

• 相邻格子的分数差不会超过"一次匹配的最大收益 + 一次罚分"。
• 范围有限，可以用较小的整数类型（如 8-bit 或 16-bit）表示。
• SIMD 一次处理更多格子。

对比 LCS：LCS 的 delta 只有 1（1 bit），NW 的 delta 范围更大（但仍有界），压缩率不如 LCS，但仍比存绝对值好。

5. NW 的 LTDP 属性总结

属性	值
是否 LTDP	✅
是否 LLTDP	✅
可用并行方法	Rank-1 方法、Delta 方法
delta 范围	$[-d,\ \max m+d]$，有界
与 LCS 关系	LCS 是 NW 的特例（$d=0$，$m=\delta$）

---

四、Smith-Waterman：0 项改变收敛性质，非 LLTDP

1. 问题背景

This algorithm [Smith and Waterman 1981] performs a local sequence alignment, in contrast to Needleman-Wunsch. Given two input strings, Smith-Waterman finds the substrings of the input that have the best alignment.

局部比对：找两个字符串中"最佳对齐的子串"，不要求全局对齐。

2. 递推式

$$s_{i,j}=\max\begin{cases} 0\\ s_{i-1,j}-d\\ s_{i,j-1}-d\\ s_{i-1,j-1}+m[i,j] \end{cases}$$

3. 与 NW 的关键区别：0 项

The key difference from Needleman-Wunsch is the 0 term in max, which ensures that alignments "restart" whenever the score goes to zero. Because of this term, the constants in $A_{i}$ matrices in Equation (1) need to be set accordingly.

0 项的作用：当分数降到 0 时，比对"重新开始"。这允许局部比对——只保留正分区域。

对 LTDP 的影响：$A_i$ 矩阵的常数需要相应设置（把 0 项编码进去）。

4. 0 项对收敛性质的巨大影响

This slight change has a significant difference from the convergence properties of Smith-Waterman as we will see later in Section 7.1.

这是本节最关键的观察。看第 7.1 节 Table I：

算法	收敛步数中位数
Smith-Waterman	8
Viterbi	30–46
Needleman-Wunsch	19,483–267,391
LCS	79,530–626,688（有时不收敛）

Smith-Waterman 收敛极快（8 步），比 NW 快几个数量级。

为什么：0 项让比对"重启"，所有最优路径都倾向于经过"重启点"（0 分格子）。这些重启点就像 4.7 节的高速公路 I-90——所有最优路径都经过同一个中间节点，所以部分乘积秩很快降到 1。

对比 NW：没有 0 项，最优路径可能分散在不同区域，没有"主干道"，秩收敛慢。

这个现象完美印证了 4.7 节的高速公路类比：最优解越"集中"，秩收敛越快。

5. 额外处理：running maximum 子问题

Also, the solution to Smith-Waterman requires finding the maximum of all subproblems in all stages and performing a predecessor traversal from that subproblem. To account for this in our LTDP formulation, we add one "running maximum" subproblem per stage that contains the maximum of all subproblems in the current stage and previous stages.

问题：Smith-Waterman 的答案是全表最大值（任意阶段、任意位置），不是最后一阶段的某个位置。

解决：每个阶段加一个 "running maximum" 子问题，记录"当前阶段及之前所有阶段的最大值"：

$$\text{running\_max}_i=\max(\text{running\_max}_{i-1},\ \max_j s_{i,j})$$

这样最后一个阶段的 running_max 就是全表最大值，可以把它放在第 0 个位置，满足"答案在最后阶段第 0 位"的假设。

6. 为什么 Smith-Waterman 不是 LLTDP

The Smith-Waterman algorithm is not an LLTDP, and therefore, the parallel Delta method is not applicable.

原因：running maximum 子问题依赖当前阶段的所有格子，不是局部依赖。所以整体不是 LLTDP。

后果：

• Smith-Waterman 不能用 Delta 方法。
• 只能用 Rank-1 方法。

注意：原始的 Smith-Waterman 递推（不含 running max）本身是局部的（上、左、左上 + 0）。但为了满足 LTDP 的"答案位置"要求，加了 running max 子问题，破坏了局部性。这是"规范化"的代价。

7. Smith-Waterman 的 LTDP 属性总结

属性	值
是否 LTDP	✅（加 running max 后）
是否 LLTDP	❌（running max 非局部）
可用并行方法	Rank-1 方法
收敛速度	极快（中位数 8 步），因为 0 项创造"主干道"
特殊处理	加 running maximum 子问题

---

五、四个问题的对比总结

维度	Viterbi	LCS	Needleman-Wunsch	Smith-Waterman
是否 LTDP	✅（取 log）	✅	✅	✅（加 running max）
是否 LLTDP	❌	✅	✅	❌
可用并行方法	Rank-1	Rank-1 + Delta	Rank-1 + Delta	Rank-1
分组方式	列	反对角线对 / 行	反对角线对 / 行	列
delta 范围	—	1（1 bit）	$[-d,\max m+d]$	—
收敛速度	中（30–46）	慢（有时不收敛）	慢（19k–267k）	极快（8）
额外处理	加阶段 $n+1$	宽度限制 $w$	宽度限制 $w$	加 running max
第 7 节实验	24× 加速	Delta 比 Rank-1 快 5–15×	Delta 比 Rank-1 快 2–10×	近线性加速

---

六、为什么这四个例子选得好

论文选这四个问题，覆盖了 LTDP 框架的不同角落：

1. Viterbi：非 LLTDP，需要取 log 变换，需要加额外阶段。代表"稠密依赖"类。
2. LCS：LLTDP，delta 极小（1 bit），有两种分组方式。代表"位并行友好"类。
3. Needleman-Wunsch：LLTDP，delta 有界但比 LCS 大。代表"一般局部比对"类。
4. Smith-Waterman：非 LLTDP（因 running max），但收敛极快。代表"0 项加速收敛"类。

覆盖的维度：

• LTDP vs LLTDP。
• 稠密依赖 vs 局部依赖。
• delta 极小 vs delta 有界。
• 收敛快 vs 收敛慢。
• 需要额外阶段 vs 需要 running max。

这样第 7 节的实验就能展示：方法在不同类型问题上都有显著加速，不是只对一个特例有效。

---

七、最容易踩的坑

1. Viterbi 取 log 不是可选，是必须。原递推是概率乘法，不取 log 就不是热带线性，不能套 LTDP。

2. Viterbi 加的阶段 $n+1$ 是全 0 矩阵。热带半环里 0 是乘法单位元，全 0 矩阵的作用是"取前一阶段的最大值"。

3. LCS 的反对角线分组需要"重叠对"。单条反对角线依赖两条前驱，不满足 LTDP；必须用 $x\cup y$、$y\cup z$ 这种重叠对，让 $y$ 重复出现。

4. LCS 行分组需要展开递推。同一行内有依赖，必须展开成只依赖前一行的形式，代价是矩阵变稠密。

5. LCS 的 delta 只有 0/1。这是 LCS 特有的，因为 LCS 长度每步最多 +1。NW 的 delta 范围更大。

6. Smith-Waterman 的 0 项是收敛加速的关键。0 项创造"重启点"，所有最优路径经过它，秩快速降到 1。这是 Table I 中 SW 中位数 8 步的原因。

7. Smith-Waterman 的 running max 破坏局部性。原始 SW 递推是局部的，但为了把答案放到固定位置，加了 running max 子问题，使它不再是 LLTDP。所以 SW 不能用 Delta 方法。

8. "LCS 是 NW 的特例"只是概念上。实现上 delta 范围、数据类型、bit-parallelism 都不同，论文当两个算法处理。

9. 宽度 $w$ 是双刃剑。减小 $w$ 省内存、省计算，但阶段变小，波前并行度降低。这正是本文跨阶段并行的动机。

10. 收敛速度与问题结构强相关。不是所有 LTDP 都收敛快。LCS 有时不收敛（Table I 中缺失项），NW 收敛慢，SW 极快。第 7 节会根据收敛速度解释加速比差异。

---

八、一句话总结第 6 节

Viterbi 取 log 后是 LTDP（非 LLTDP），加全 0 阶段把答案挪到第 0 位，只能用 Rank-1；LCS 是 LLTDP，可用反对角线对或行分组，delta 只有 0/1 可用 bit 表示，Rank-1 和 Delta 都可用；Needleman-Wunsch 是 LLTDP，delta 有界，Rank-1 和 Delta 都可用；Smith-Waterman 因 0 项收敛极快（中位数 8 步），但加 running max 后非 LLTDP，只能用 Rank-1。四个问题覆盖了 LTDP 框架的不同角落，为第 7 节的实验提供了全面的测试集。

---

下一步进入 第 7 节 EVALUATION。这一节是实验部分，需要重点理解：

• 7.1 秩收敛测量：Table I 怎么测的？为什么不同算法收敛步数差异巨大？
• 7.2 环境设置：Stampede 集群、共享内存机器。
• 7.3 四个基准的性能：Viterbi 24×、Smith-Waterman 近线性、NW 和 LCS 的 Delta vs Rank-1 对比。
• 7.4 Delta vs Rank-1：为什么 Delta 快 5–15 倍。
• 7.5 Wavefront vs LTDP：跨阶段并行 vs 阶段内波前的直接对比。

这一节的关键是理解"实验数据如何印证理论"：收敛速度（Table I）→ 加速比（Figures 11–15）→ 方法选择（Delta vs Rank-1 vs Wavefront）。