5 Parallel Delta method

第 5 节 THE PARALLEL DELTA METHOD 精读

这一节是 Rank-1 方法的改进版，专门针对 Local LTDP（LLTDP） 问题。核心思想一句话：

不存每个格子的绝对值，存相邻格子的差（delta）；只重算受错误 delta 影响的那部分格子，而不是整列重算。

下面逐块拆解。

---

5.0 为什么需要 Delta 方法：Rank-1 的不足

回顾第 4 节 Rank-1 方法的 fix-up 循环：

for i in (lp+1..rp) {
  pred[i] = A_i ★ s;
  s = A_i ⊙ s;
  if (s is parallel to s[i]) break;
  s[i] = s;
}

问题：fix-up 时，整列（整个阶段）的所有格子都要重算，哪怕只有少数几个格子的值错了。

对于 LLTDP 问题（LCS、Needleman-Wunsch），每个格子只依赖 3 个局部邻居。一个错误 delta 只会影响它"下游"的一小部分格子，不需要整列重算。Delta 方法就是利用这个局部性，把重算范围缩小到"受影响的那部分"。

---

5.1 Delta 方法（顺序版）：不存绝对值，存差值

1. LLTDP 的定义

The Delta method works for Local LTDP (LLTDP) problems. Figure 1(b) shows an example of an LLTDP where the dependencies for cell $C_{i,j}$ are the three local neighbors: $C_{i - 1,j}$ , $C_{i,j - 1}$ , and $C_{i - 1,j - 1}$.

LLTDP = LTDP + 局部依赖。每个格子只依赖上、左、左上三个邻居：

C_{i-1,j-1}   C_{i-1,j}
C_{i,j-1}     C_{i,j}     ← 只依赖这三个

In general, an LLTDP recursive function is given by

$$C_{i,j} = \max \left\{ \begin{array}{l}C_{i - 1,j} + w_{i,j}^{1}\\ C_{i,j - 1} + w_{i,j}^{2}\\ C_{i - 1,j - 1} + w_{i,j}^{3}, \end{array} \right. \quad (4)$$

$w^1,w^2,w^3$ 是三个常数，由输入决定，与格子的值无关。LCS 里它们分别是 $0,0,\delta_{i,j}$；Needleman-Wunsch 里是匹配分数和罚分。

对比 Viterbi：Viterbi 每个格子依赖前一列的所有格子，不是局部的，所以不能用 Delta 方法。

2. Delta 的定义

The Delta method computes $\delta_{i,j} = C_{i,j} - C_{i,j - 1}$ and $\Delta_{i,j} = C_{i,j} - C_{i,j - 1}$ instead of actually computing $C_{i,j}$ .

注意：论文原文这里有个笔误，$\Delta_{i,j}$ 应该是垂直 delta：

$$\delta_{i,j} = C_{i,j} - C_{i,j-1} \quad\text{（水平 delta，与左邻居的差）}$$ $$\Delta_{i,j} = C_{i,j} - C_{i-1,j} \quad\text{（垂直 delta，与上邻居的差）}$$

图示（论文 Figure 6(a)）：

C_{i-1,j-1}  --δ_{i-1,j}-->  C_{i-1,j}
     |                            |
   Δ_{i,j-1}                   Δ_{i,j}
     |                            |
     v                            v
C_{i,j-1}   --δ_{i,j}----->  C_{i,j}

• $\delta_{i-1,j}=C_{i-1,j}-C_{i-1,j-1}$：上边两个格子的水平差。
• $\Delta_{i,j-1}=C_{i,j-1}-C_{i-1,j-1}$：左边两个格子的垂直差。
• $\delta_{i,j}=C_{i,j}-C_{i,j-1}$：当前格与左邻居的水平差（输出）。
• $\Delta_{i,j}=C_{i,j}-C_{i-1,j}$：当前格与上邻居的垂直差（输出）。

3. Lemma 5.1：delta 只依赖相邻的两个 delta

LEMMA 5.1. $\delta_{i,j}$ , $\Delta_{i,j}$ , and $\text{pred}_{i,j}$ can be computed given the values of $\delta_{i,j - 1}$ and $\Delta_{i - 1,j}$ and using recursive function 4.

这是 Delta 方法的核心引理。它说：

• 要算 $\delta_{i,j}$ 和 $\Delta_{i,j}$，不需要知道任何格子的绝对值。
• 只需要两个输入 delta：$\delta_{i-1,j}$（上边的水平差）和 $\Delta_{i,j-1}$（左边的垂直差）。

4. 证明（论文原文的展开）

In Figure 6(a), assume that the value of $C_{i - 1,j - 1}$ is $x$ and, consequently, the values of $C_{i,j - 1}$ and $C_{i - 1,j}$ will be $x + \delta_{i - 1,j}$ and $x + \Delta_{i,j - 1}$ , respectively.

设 $C_{i-1,j-1}=x$。由 delta 定义：

• $C_{i-1,j}=C_{i-1,j-1}+\delta_{i-1,j}=x+\delta_{i-1,j}$
• $C_{i,j-1}=C_{i-1,j-1}+\Delta_{i,j-1}=x+\Delta_{i,j-1}$

Using the recursive function 4,

$$C_{i,j} = \max \{x + \delta_{i - 1,j} + w_{i,j}^{1},x + \Delta_{i,j - 1} + w_{i,j}^{2},x + w_{i,j}^{3}\}.$$

代入公式 (4) 的三个分支：

• 从上邻居：$C_{i-1,j}+w^1=(x+\delta_{i-1,j})+w^1=x+(\delta_{i-1,j}+w^1)$
• 从左邻居：$C_{i,j-1}+w^2=(x+\Delta_{i,j-1})+w^2=x+(\Delta_{i,j-1}+w^2)$
• 从左上邻居：$C_{i-1,j-1}+w^3=x+w^3$

Let $K = \max \{\delta_{i - 1,j} + w_{i,j}^{1},\Delta_{i,j - 1} + w_{i,j}^{2},w_{i,j}^{3}\}$ , and as a result, $C_{i,j} = x + K$ .

把 $x$ 从 max 里提出来（因为 $x$ 与三个分支的选择无关）：

$$C_{i,j}=x+\max\{\delta_{i-1,j}+w^1,\ \Delta_{i,j-1}+w^2,\ w^3\}=x+K$$

关键：$K$ 只依赖两个输入 delta 和常数 $w$，与 $x$ 无关。

Therefore, $\delta_{i,j} = C_{i,j} - C_{i,j - 1} = x + K - (x + \Delta_{i,j - 1}) = K - \Delta_{i,j - 1}$ which is a constant.

$$\delta_{i,j}=C_{i,j}-C_{i,j-1}=(x+K)-(x+\Delta_{i,j-1})=K-\Delta_{i,j-1}$$

$x$ 被消掉了！$\delta_{i,j}$ 只依赖 $K$ 和 $\Delta_{i,j-1}$，而 $K$ 只依赖两个输入 delta。所以：

$$\delta_{i,j}=f_\delta(i,j,\delta_{i-1,j},\Delta_{i,j-1})$$

同理：

$$\Delta_{i,j}=C_{i,j}-C_{i-1,j}=(x+K)-(x+\delta_{i-1,j})=K-\delta_{i-1,j}$$ $$\Delta_{i,j}=f_\Delta(i,j,\delta_{i-1,j},\Delta_{i,j-1})$$

The arg max in the computation of $K$ is independent of $x$ and it corresponds to the same arg max in the computation of $C_{i,j}$ . Therefore, $pred_{i,j}$ is constant given the values of $\delta_{i,j - 1}$ and $\Delta_{i - 1,j}$ .

前驱也独立于 $x$：$K$ 的 argmax 就是 $C_{i,j}$ 的 argmax，因为加 $x$ 不改变谁最大。所以 $pred_{i,j}$ 也只依赖两个输入 delta。

5. 直观理解

类比：你不需要知道海拔的绝对值，只需要知道"相邻两点的海拔差"，就能推出整个地形。Delta 方法就是把"绝对高度"换成"相对坡度"。

关键洞察：LLTDP 的递推是"加常数 + 取 max"，加常数不影响 max 的选择。所以绝对基准 $x$ 被完全消掉，只剩差值在传播。

6. 顺序 Delta 算法（图 7）

1 SeqDelta(int delta δ_{0,1}... δ_{0,n-1}, int Δ_{1,0}... Δ_{n-1,0}) {
2   int δ_{1..n-1,0..n-1}, Δ_{0..n-1,1..n-1};
3   for j in (1..n-1) {
4     for i in (1..n-1) {
5       δ_{i,j} = f_δ(i,j,δ_{i-1,j},Δ_{i,j-1});
6       Δ_{i,j} = f_Δ(i,j,δ_{i-1,j},Δ_{i,j-1}); }}
7   return δ_{0..n-1,0..n-1}, Δ_{0..n-1,0..n-1}; }

输入：顶边和左边的初始 delta（$\delta_{0,1},\ldots,\delta_{0,n-1}$ 和 $\Delta_{1,0},\ldots,\Delta_{n-1,0}$）。这些是边界条件。

双重循环：按行、列顺序计算每个格子的两个 delta。

和普通 DP 的区别：

• 普通 DP 算 $C_{i,j}$（绝对值）。
• Delta 方法算 $\delta_{i,j},\Delta_{i,j}$（差值），每个格子算两个值。

为什么值得：差值范围小。LCS 的 delta 只有 0/1，Needleman-Wunsch 的 delta 在 $[-d,\max m+d]$ 范围内。范围小 → 可以用更小的数据类型 → SIMD 一次处理更多格子。

---

5.2 并行 Delta 方法概览

1. 列划分

The set of deltas are distributed column-wise with one column of $\Delta s$ replicated at the boundaries, as shown in Figure 8(b).

把表格按列分给 $P$ 个处理器。每个处理器负责一段连续的列。相邻处理器共享一列 $\Delta$（边界列），用于通信。

图示（Figure 8(b)）：

P_0 负责: 列 0..k
P_1 负责: 列 k..2k     （列 k 与 P_0 共享）
P_2 负责: 列 2k..3k    （列 2k 与 P_1 共享）

2. 两个阶段

The parallel Delta method consists of two phases: (1) a random phase and (2) a fix-up phase.

阶段 1（random phase）：

• $P_0$ 从真实边界条件开始。
• 其他处理器 $P_1,P_2,\ldots$ 的第一列 $\Delta$ 随机初始化（但必须 all-non-zero，见 4.5 节）。
• 所有处理器同时计算自己负责的列。

阶段 2（fix-up phase）：

• 逐轮修正。第 1 轮：$P_1$ 用 $P_0$ 的真实 $\Delta$ 修正自己的第一列，$P_2$ 暂时不动。第 2 轮：$P_2$ 用 $P_1$ 修正后的 $\Delta$ 修正自己。
• 每轮只重算受影响的那些格子，不是整列。

3. Observation 5.2：随机初始化也能产生很多正确 delta

OBSERVATION 5.2. Starting with random (and perhaps incorrect) initial $\Delta s$ in the first column of a processor leads to many correct deltas on subsequent columns.

核心观察：即使第一列 $\Delta$ 全错，往后算几列，很多 delta 会自动变正确。

为什么？ 论文的解释：

Assume that in Figure 6(a), both $\delta_{i - 1,j}^{\prime} \neq \delta_{i - 1,j}$ and $\Delta_{i,j - 1}^{\prime} \neq \Delta_{i,j - 1}$ , but $pred_{i,j} = pred_{i,j}^{\prime} = \{i - 1,j\}$ .

假设两个输入 delta 都错了，但恰好前驱选对了（都选了"从上邻居来"）。那么：

$$C_{i,j}^{\prime}=C_{i-1,j}^{\prime}+w^1,\quad C_{i,j}=C_{i-1,j}+w^1$$

两式相减：

$$\Delta_{i,j}^{\prime}=C_{i,j}^{\prime}-C_{i-1,j}^{\prime}=w^1=C_{i,j}-C_{i-1,j}=\Delta_{i,j}$$

输出 delta 正确！ 因为只要前驱选对，delta 就等于那个分支的常数 $w$，与输入 delta 错没错无关。

Hence, using incorrect input deltas may lead to correct output deltas. Also, correct deltas lead to more correct deltas because of Lemma 5.1.

两个效应：

1. 错误的输入 delta 可能产生正确的输出 delta（只要前驱选对）。
2. 正确的输入 delta 一定产生正确的输出 delta（Lemma 5.1）。

所以错误会逐渐被"洗掉"，正确区域会逐渐扩大。

4. Lemma 5.3：正确路径之后全正确

LEMMA 5.3. If there is a path of solid red correct deltas from the top row of the table to the bottom of the table in a processor, the rest of the deltas after that path are solid red correct deltas.

图示（Figure 8(b)）：红色实线 = 正确 delta，蓝色虚线 = 错误 delta。

如果从顶行（初始化正确）到底行有一条全红路径，那么这条路径右边的所有 delta 都正确。

证明：

The top-row deltas are always correct since they are a part of initialization. Therefore, because of Lemma 5.1, all deltas that come immediately after the path are all correct.

• 顶行 delta 是初始化给的，正确。
• 沿着正确路径走，每一步的两个输入 delta 都正确（一个来自上方正确路径，一个来自左方正确路径）。
• 由 Lemma 5.1，输出 delta 也正确。
• 归纳：路径之后全正确。

直观：正确性像"水流"一样从顶行往下流，一旦某条路径打通，右边就全被"淹没"成正确的。

5. fix-up 的逐轮推进

第 1 轮（Figure 8(c)）：

• $P_0$ 空闲（它本来就正确）。
• $P_1$ 拿到 $P_0$ 最后一列的真实 $\Delta$，修正自己第一列。修正后，$P_1$ 内部出现正确路径，后面的 delta 自动变正确。
• $P_2$ 暂不动（还没拿到 $P_1$ 的修正值）。

第 2 轮（Figure 8(d)）：

• $P_0,P_1$ 空闲。
• $P_2$ 拿到 $P_1$ 修正后的最后一列，修正自己第一列。

一般规律：$P_i$ 需要 $i-1$ 轮 fix-up。

每轮工作量递减：因为正确区域越来越大，需要重算的格子越来越少。第 1 轮 $P_1$ 要重算较多格子，第 2 轮 $P_2$ 要重算的格子更少（因为 $P_1$ 已经帮它修正了一部分）。

---

5.3 并行 Delta 方法实现（图 9）

1. 初始化（第 1–12 行）

1  ParDelta(int δ_{0,1,...}, δ_{0,n-1}, int Δ_{1,0,...}, Δ_{n-1,0}) {
2    int δ_{1,...n-1,0,...n-1}, Δ_{0,...n-1,1,...n-1};
3    int Δ'_{0,...n-1,2,...P};
4    //Initialization
5    //The start (S_p) and end (E_p) column of deltas for processor p
6    ∀p: S_p = n/P*(p-1); E_p = n/P*p;
7    //Initializing the first column of deltas
8    parallel for p in (2..P) {
9      local s = S_p;
10     for i in (1..n-1) {
11       Δ_{i,s} = random();
12       Δ'_{i,p} = Δ_{i,s};
13     }

逐行：

• 第 6 行：和 Rank-1 一样，划分列范围。$S_p$ 是起始列，$E_p$ 是结束列。
• 第 8–12 行：处理器 $2$ 到 $P$ 的第一列 $\Delta$ 随机初始化。
  • Δ_{i,s}：当前值。
  • Δ'_{i,p}：保存随机初始值，fix-up 时用来比较"哪些变了"。

注意：$P_1$ 不参与随机初始化，因为它的第一列就是 $P_0$ 的最后一列，是真实的。

2. Random phase（第 13–22 行）

14   //Random phase
15   parallel for p in (1..P) {
16     for j in (S_p+1, ..., E_p) {
17       if (j == E_p)  //Sync before updating the next column
18         ------------ barrier ------------
19       for i in (1..n-1) {
20         δ_{i,j} = f_δ(i,j,δ_{i-1,j},Δ_{i,j-1});
21         Δ_{i,j} = f_Δ(i,j,δ_{i-1,j},Δ_{i,j-1});
22       }

逐行：

• 第 15 行：所有处理器并行。
• 第 16 行：遍历自己负责的每一列 $j$。
• 第 17–18 行：当算到最后一列 $E_p$ 时，先 barrier，确保前一个处理器已经把它最后一列（即当前处理器的第一列）算完。
• 第 19–22 行：对每一行 $i$，用 Lemma 5.1 算两个 delta。

依赖关系：算 $\delta_{i,j}$ 需要 $\delta_{i-1,j}$（同列上一行）和 $\Delta_{i,j-1}$（前一列同一行）。同一列内，行与行之间有依赖（需要上一行的 $\delta$），所以内层循环 $i$ 必须顺序。

并行粒度：不同处理器处理不同列，列与列之间只通过边界列通信。

3. Fix-up phase（第 23–55 行）

23   //Fix-up phase
24   for iter in (2..P) {
25     parallel for p in (iter..P) {
26       local s = S_p;
27       //The work list for the current iteration to recompute
28       local workQueue1;
29       //The work list for the next iteration to recompute
30       local workQueue2;
31       //Identifying Δ_s that are different in the first column
32       for i in (1..n-1) {
33         if Δ_{i,s} != Δ'_{i,p} {
34           workQueue1.add(i);
35           Δ'_{i,p} = Δ_{i,s};
36         }
37       }

逐行：

• 第 24 行：iter 从 2 到 $P$。第 iter 轮，处理器 $iter$ 到 $P$ 参与。
  • 第 2 轮：$P_2,\ldots,P_P$ 参与（$P_1$ 已修正）。
  • 第 3 轮：$P_3,\ldots,P_P$ 参与。
  • 以此类推。
• 第 25 行：并行处理参与本轮的所有处理器。
• 第 28–30 行：两个工作队列。
  • workQueue1：当前列需要重算的行号。
  • workQueue2：下一列需要重算的行号。
• 第 32–36 行：比较第一列的新 $\Delta$ 和之前保存的 $\Delta'$。不一样的行号加入 workQueue1（这些行的输出 delta 可能变了，需要重算）。

37       //Iterating through column that processor p owns
38       for j in (S_p+1, ..., E_p) {
39         if (j == E_p)
40           ------------ barrier ------------
41         //Only recompute the ones from the working list
42         while workQueue1.size() {
43           local i = workQueue1.pop();
44           //If output deltas are different,
45           //add them for fix up in iteration j+1
46           local int Δ_temp = f_Δ(i,j,δ_{i-1,j},Δ_{i,j-1});
47           if Δ_{i,j} != Δ_temp {
48             Δ_{i,j} = Δ_temp;
49             workQueue2.add(i);
50           }
51           local int δ_temp = f_δ(i,j,δ_{i-1,j},Δ_{i,j-1});
52           if δ_{i,j} != δ_temp {
53             δ_{i,j} = δ_temp;
54             if i < n-1 {
55               workQueue1.add(i+1);
56             }
57           }
58         }
59         swap(workQueue1, workQueue2);
60       }

逐行：

• 第 38 行：遍历自己负责的列。
• 第 39–40 行：到最后一列时 barrier，等前一个处理器更新边界。
• 第 42 行：只处理 workQueue1 里的行号（不是整列重算）。
• 第 43 行：取出一个行号 $i$。
• 第 46–50 行：算新的 $\Delta_{i,j}$。如果和旧值不同：
  • 更新 Δ_{i,j}。
  • 把 $i$ 加入 workQueue2（下一列的同一行也要重算，因为 $\Delta_{i,j}$ 是下一列 $j+1$ 的输入）。
• 第 51–57 行：算新的 $\delta_{i,j}$。如果和旧值不同：
  • 更新 δ_{i,j}。
  • 把 $i+1$ 加入 workQueue1（同一列的下一行也要重算，因为 $\delta_{i,j}$ 是下一行 $i+1$ 的输入）。
• 第 59 行：workQueue1 和 workQueue2 交换，进入下一列。

关键逻辑：

• $\Delta$ 变化影响下一列 → 加入 workQueue2。
• $\delta$ 变化影响下一行 → 加入 workQueue1（当前列继续处理）。
• 这样"错误"沿着依赖关系精确传播，只重算真正受影响的格子。

---

5.4 Delta 方法 vs Rank-1 方法

1. 论文的对比

The parallel LTDP algorithm only relies on Lemma 5.3, and the fix-up phase is more coarse grained than the parallel Delta method. In the Rank-1 method, every processor similarly starts with a random initialization, but in the fix-up phase, all deltas for every column are recomputed until a column with all correct Δs is reached.

Rank-1 的 fix-up：

• 整列重算，直到某列全部正确。
• 粗粒度。

Delta 的 fix-up：

• 只重算 workQueue 里的格子。
• 细粒度。
• 利用 Lemma 5.1 精确追踪"哪些格子受影响"。

Because of Lemma 5.3, after such a column, the rest of the deltas are correct and there is no need for recomputation.

Rank-1 为什么粗：它不知道哪些格子错了，只能整列重算，直到发现"这一列全对了"才停。

Delta 为什么细：它用 workQueue 精确知道哪些格子受影响，只重算那些。

2. 性能预期

Therefore, the parallel Delta method is an improvement to the Rank-1 method and the expectation is that the Delta method is never slower than the Rank-1 method for LLTDP problems. Specially in the cases where it takes a lot of columns to converge to rank 1, the Delta method should be significantly faster.

预期：

• Delta 方法永远不会慢于 Rank-1（对 LLTDP）。
• 收敛慢的情况下，Delta 显著更快。

第 7.4 节实验验证：

• LCS：Delta 比 Rank-1 快 5–15 倍（128 核）。
• Needleman-Wunsch：Delta 比 Rank-1 快 2–10 倍（128 核）。

3. 为什么 Delta 方法不能用于非 LLTDP

Figure 1(a) shows an LTDP example that is not local, and the dependencies for a cell come from all the cells of the previous stage. This structure of an LTDP problem prevents us from applying the Delta method.

Viterbi、Smith-Waterman 不是 LLTDP：

• 每个格子依赖前一列的所有格子，不是局部邻居。
• Delta 方法的 Lemma 5.1 要求"只依赖两个相邻 delta"，非局部问题不满足。
• 所以 Viterbi 和 Smith-Waterman 只能用 Rank-1 方法，不能用 Delta 方法。

---

本节逻辑链总结

Rank-1 的 fix-up 整列重算，太粗
  ↓
LLTDP 的格子只依赖 3 个局部邻居
  ↓
定义 delta（相邻格子的差），不存绝对值
  ↓
Lemma 5.1：delta 和 pred 只依赖两个输入 delta，与绝对基准无关
  ↓
并行策略：列划分 + 随机初始化 + 逐轮 fix-up
  ↓
Observation 5.2：随机初始化也能产生很多正确 delta（前驱选对时）
  ↓
Lemma 5.3：一旦出现全正确路径，后面全正确
  ↓
fix-up 用 workQueue 精确追踪受影响格子，只重算子集
  ↓
性能：Delta 永远不慢于 Rank-1，收敛慢时快 5–15 倍

---

最容易踩的坑

1. $\Delta_{i,j}$ 的定义。论文原文写的是 $C_{i,j}-C_{i,j-1}$，这是笔误。正确是 $C_{i,j}-C_{i-1,j}$（与上邻居的差）。看 Figure 6(a) 的箭头方向就清楚了。

2. delta 是"两个值"。每个格子算两个 delta（水平 $\delta$ 和垂直 $\Delta$），计算量是普通 DP 的 2 倍。但 delta 范围小，SIMD 效率高，实际更快。

3. Lemma 5.1 的关键是"消掉 $x$"。加常数不影响 max，所以绝对基准 $x$ 被消掉，只剩差值传播。这是 Delta 方法成立的数学根基。

4. 随机初始化也能产生正确 delta。不是"随机全错就一直错"，而是"前驱选对时输出自动正确"。这是 Observation 5.2 的核心。

5. workQueue 的两个方向。$\Delta$ 变化影响下一列（workQueue2），$\delta$ 变化影响下一行（workQueue1）。搞混了会导致漏算或死循环。

6. fix-up 逐轮推进。第 iter 轮只有处理器 iter 到 $P$ 参与。$P_1$ 第 1 轮就修完，$P_2$ 第 2 轮修完，以此类推。不是所有处理器每轮都参与。

7. Delta 方法只适用于 LLTDP。Viterbi 和 Smith-Waterman 不是 LLTDP，只能用 Rank-1。LCS 和 Needleman-Wunsch 是 LLTDP，可以用 Delta。

8. "永远不慢于 Rank-1"是预期，不是定理。论文说 "the expectation is"，实验验证了，但没有形式化证明。理论上 workQueue 管理有开销，极端情况下可能不划算。

9. barrier 在最后一列。第 18 行和第 40 行的 barrier 只在 j == E_p 时执行，确保边界列同步。其他列不需要 barrier，因为处理器之间不共享。

10. Delta 方法不计算绝对值。最终只得到 delta 表，不得到 $C_{i,j}$ 表。如果需要绝对值，要额外从边界积分回去。但很多应用（如 LCS 的路径回溯）只需要 delta 和 pred，不需要绝对值。

---

一句话总结第 5 节

LLTDP 问题（LCS、Needleman-Wunsch）的格子只依赖 3 个局部邻居，可以改存"相邻格子的差"（delta）而非绝对值；Lemma 5.1 证明 delta 和 pred 只依赖两个输入 delta，绝对基准被完全消掉；并行版按列划分，非首处理器随机初始化第一列，随机阶段就能产生大量正确 delta（前驱选对时输出自动正确），fix-up 阶段用 workQueue 精确追踪受影响的格子，只重算子集而非整列；对 LLTDP，Delta 方法永远不慢于 Rank-1，收敛慢时快 5–15 倍。

---

下一步进入 第 6 节 LTDP EXAMPLES。这一节把四个实际问题（Viterbi、LCS、Smith-Waterman、Needleman-Wunsch）逐一映射到 LTDP 框架，需要重点理解：

• Viterbi：为什么取 log 后变成 LTDP；为什么要加一个额外阶段把答案挪到第 0 个位置；为什么不是 LLTDP。
• LCS：两种分组方式（反对角线 vs 行/列）；为什么是 LLTDP；delta 为什么只有 0/1。
• Needleman-Wunsch：和 LCS 的异同；delta 范围为什么是 $[-d,\max m+d]$。
• Smith-Waterman：0 项如何改变收敛性质；为什么要加"running maximum"子问题。

这一节是"理论到实践"的桥梁，理解四个例子怎么套进 LTDP 框架，对理解第 7 节的实验至关重要。