4 Parallel Rank-1 method

这一节是全文的核心。它要回答一个尖锐的问题：

第 3 节的顺序算法必须等阶段 $i-1$ 算完才能算阶段 $i$，怎么打破这个依赖？

答案分两步：

1. 理论上：矩阵乘法可结合，可以把 $A_n\cdots A_1$ 从中间切开并行算（4.1）。
2. 实际上：直接做矩阵-矩阵乘法开销太大，改用秩收敛，从任意初始向量出发，让多个处理器同时算不同阶段，事后再修正（4.2–4.4）。

下面逐节拆解。

---

4.1 打破阶段间数据依赖：为什么"直接并行"不实用

1. 论文的出发点

From Equation (2), we have

$$\bar{s}_n = A_n\odot A_{n - 1}\ldots A_2\odot A_1\odot \bar{s}_0.$$

最后一个阶段的解 $\bar{s}_n$，是从 $\bar{s}_0$ 连续乘 $n$ 个矩阵得到的。

2. 直接并行的思路

Standard techniques [Ladner and Fischer 1980; Hillis and Steele 1986] can parallelize this computation using the associativity of matrix multiplication. For instance, two processors can compute the partial products $A_n\odot \ldots \odot A_{n / 2 + 1}$ and $A_{n / 2}\odot \ldots \odot A_{1}$ in parallel and multiply their results with $\bar{s}_0$ to obtain $\bar{s}_n$.

利用 Lemma 2.1（结合律），把连乘切成两半：

处理器1:  A_n ⊙ ... ⊙ A_{n/2+1}  →  得到 M_右
处理器2:  A_{n/2} ⊙ ... ⊙ A_1    →  得到 M_左
然后:     s_n = M_右 ⊙ M_左 ⊙ s_0

两个处理器同时算左右两半，最后合并。理论上可行。

3. 为什么不可行

However, doing so converts a sequential computation that performs matrix-vector multiplications to a parallel computation that performs matrix-matrix multiplications. This results in a parallelization overhead linear in the size of the stages and thus requires a linear number of processors to observe constant speedups. In practice, the size of stages can easily be hundreds or larger and thus this is not practical on real problems and hardware.

核心矛盾：

操作	顺序算法	直接并行
做什么	矩阵 $\odot$ 向量	矩阵 $\odot$ 矩阵
计算量	$O(\text{矩阵大小})$	$O(\text{矩阵大小}^2)$
存储	只需存向量	需要存中间矩阵

具体算一下：

• 设阶段大小（向量维度）为 $w$，有 $n$ 个阶段。
• 顺序算法：每次矩阵-向量乘法 $O(w^2)$（稀疏时更少），总共 $O(n\cdot w^2)$。
• 直接并行：中间要算矩阵-矩阵乘法，每次 $O(w^3)$。

如果 $w=1000$，$w^3=10^9$，比 $w^2=10^6$ 大 1000 倍。即使并行，这个开销也吃掉了所有收益。

论文原话："requires a linear number of processors to observe constant speedups"——要看到常数加速，需要线性数量的处理器。实际中不可行。

4. 本节的关键贡献

The key contributions of this article are parallel methods that avoid the overhead of matrix-matrix multiplications.

本文方法：不真的做矩阵-矩阵乘法，而是利用秩收敛，从任意初始向量出发。

为此需要定义：

Partial Product. For a given LTDP instance, the partial product $M_{i \to j}$, defined for stages $j \geq i$, is given by

$$M_{i\to j} = A_{j}\odot \ldots A_{i + 1}\odot A_{i}.$$

Partial product determines how a later stage $j$ depends on stage $i$ as $\bar{s}_j = M_{i \to j} \odot \bar{s}_i$.

部分乘积 $M_{i\to j}$：从阶段 $i$ 到阶段 $j$ 的"累积变换"。它把阶段 $i$ 的解映射到阶段 $j$ 的解。

注意：$M_{i\to j}$ 是一个概念工具，实际算法不会真的把它算出来（否则又回到矩阵-矩阵乘法）。后面只用它的秩来论证。

---

4.2 秩收敛：本文的理论核心

1. 秩不增性质

Rank of the product of two matrices is not greater than the rank of the individual matrices:

$$\mathrm{rank}(A\odot B)\leq \min (\mathrm{rank}(A),\mathrm{rank}(B)). \quad (3)$$

这个我们上一轮已经推过。用"最小分解维数"定义，证明只用结合律：

• 若 $A=C\odot R$（$r$ 维分解），则 $A\odot B=C\odot(R\odot B)$，还是 $r$ 维分解。
• 所以 $\operatorname{rank}(A\odot B)\le r=\operatorname{rank}(A)$。
• 同理 $\operatorname{rank}(A\odot B)\le\operatorname{rank}(B)$。

2. 由秩不增推出单调不增

Equation (3) implies that for stages $k \geq j \geq i$,

$$\mathrm{rank}(M_{i \to k}) \leq \mathrm{rank}(M_{i \to j}) \leq \mathrm{rank}(A_i).$$

因为 $M_{i\to k}=M_{j\to k}\odot M_{i\to j}$，所以：

$$\operatorname{rank}(M_{i\to k})\le\operatorname{rank}(M_{i\to j})$$

含义：随着阶段往后推，部分乘积的秩只减不增。它从 $\operatorname{rank}(A_i)$ 开始，一路下降。

3. 秩收敛的假设

In effect, as the LTDP computation proceeds, the rank of the partial products will never increase. Theoretically, there is a possibility that the ranks do not decrease. However, we have only observed this for carefully crafted problem instances that are unlikely to occur in practice. On the contrary, the rank of these partial products is likely to converge to 1, as will be demonstrated in Section 7.1.

关键假设（经验性质，非定理）：

• 理论上，秩可能停在 2、3、……不降到 1。
• 但实际数据上，秩几乎总会降到 1。
• 第 7.1 节用实验测量了收敛步数（Table I）。

这是全文最重要的"经验假设"。整个并行算法的正确性和效率都依赖它。论文诚实地承认这不是严格保证，而是"实际中几乎总成立"。

4. 秩 1 意味着什么

Consider a partial product $M_{i \to j}$ whose rank is 1. Intuitively, this implies a weak dependence between stages $i$ and $j$.

秩 1 = 阶段 $i$ 对阶段 $j$ 的影响"很弱"。具体多弱？看下一句：

Instead of the actual solution vector, $\bar{s}_i$, say the LTDP computation starts with a different vector $\bar{t}_i$ at stage $i$. From Lemma 2.2, the new solution vector at stage $j$, $\bar{t}_j = M_{i \to j} \odot \bar{t}_i$, is parallel to the actual solution vector $\bar{s}_j = M_{i \to j} \odot \bar{s}_i$.

推导：

• 真实情况：$\bar{s}_j=M_{i\to j}\odot\bar{s}_i$
• 假设从错误初始向量出发：$\bar{t}_j=M_{i\to j}\odot\bar{t}_i$
• 若 $\operatorname{rank}(M_{i\to j})=1$，由 Lemma 2.2： $$M_{i\to j}\odot\bar{t}_i\parallel M_{i\to j}\odot\bar{s}_i$$ 即 $\bar{t}_j\parallel\bar{s}_j$。

结论：只要秩降到 1，不管阶段 $i$ 的初始向量是什么，阶段 $j$ 的解都平行于真实解。

5. 直观理解

Essentially, the direction of the solution vector at stage $j$ is independent of stage $i$. The latter stage only determines its magnitude. In the tropical semiring, where the multiplicative operator is $+$, this means that the solution vector at stage $j$ will be off by a constant if one starts stage $i$ with an arbitrary vector.

类比：

• 普通线性代数：秩 1 矩阵把任何输入映到同一条直线上，只是长度不同。
• 热带半环：秩 1 矩阵把任何输入映到同一个方向上，只是偏移量不同。

"方向"在热带半环里是什么？ 是向量各分量之间的相对差。给整个向量加一个常数，方向不变。所以：

从任意 $\bar{t}_i$ 出发，得到的 $\bar{t}_j$ 和真实 $\bar{s}_j$ 只差一个常数。

6. 为什么这能打破依赖

把 4.1 和 4.2 连起来：

1. 4.1：直接并行（矩阵-矩阵乘法）开销太大。
2. 4.2：如果秩收敛到 1，那么从任意初始向量出发，后面阶段的解方向正确，只是数值差常数。
3. Lemma 3.1：前驱乘积对平行向量不敏感，所以路径完全正确。

于是：让处理器 $P_2$ 从任意向量开始算它的阶段，不用等 $P_1$。只要 $P_2$ 的阶段足够长（能发生秩收敛），它算出的解方向就是对的。等 $P_1$ 算完后，再修正 $P_2$ 开头那些还没收敛的阶段。

这就是 Rank-1 方法的核心思想。

---

4.3 Rank-1 方法概览：三张图看懂

1. 图 3(a)：顺序算法

P_0:  s_0 → s_1 → s_2 → ... → s_a → ... → s_b → ... → s_n
                ↑              ↑              ↑
              P_a 等 s_a     P_b 等 s_b

• 一个处理器从头算到尾。
• 箭头表示"必须等前一个阶段算完"。

2. 图 3(b)：并行算法的第一遍（random phase）

P_0:  s_0 → s_1 → ... → s_a
P_a:  r_a → ... → s̄_b  （从任意 r_a 开始）
P_b:  r_b → ... → s̄_n  （从任意 r_b 开始）

• $P_0$ 从真实初始向量 $\bar{s}_0$ 开始。
• $P_a$ 从任意向量 $r_a$ 开始，不等 $P_0$。
• $P_b$ 从任意向量 $r_b$ 开始，不等 $P_a$。

图 3(b) 中：

• 深灰色：还没收敛的阶段，解完全错误。
• 浅灰色：已经收敛的阶段，解平行于真实解。

关键观察：$P_a$ 和 $P_b$ 开头的阶段是错的（深灰），但经过足够多阶段后，由于秩收敛，解变成平行于真实解（浅灰）。

3. 图 3(c)：fix-up 阶段

P_0:  s_0 → s_1 → ... → s_a
                        ↓ (传给 P_a)
P_a:  s_a → ... → s̄_b   （用 s_a 修正开头）
                        ↓ (传给 P_b)
P_b:  s̄_b → ... → s̄_n   （用 s̄_b 修正开头）

• $P_a$ 拿到 $P_0$ 算出的真实 $s_a$，用它重新算自己的阶段，修正开头那些错误的部分。
• $P_b$ 拿到 $P_a$ 修正后的 $\bar{s}_b$，重新算自己的阶段。

fix-up 后：每个阶段要么等于真实解，要么平行于真实解。

4. 为什么"平行"就够了

For LTDP, it is not necessary to compute the actual solution vectors. As parallel vectors generate the same predecessor products (Lemma 3.1), following the predecessors in Figure 3(c) will generate the same solution as following the predecessors in Figure 3(a).

最终目标是前驱路径，不是数值。 Lemma 3.1 保证平行向量前驱相同，所以：

• 不需要把 $\bar{s}_i'$ 修正成精确等于 $\bar{s}_i$。
• 只需要修正到平行于 $\bar{s}_i$。

这大大降低了 fix-up 的工作量。

---

4.4 并行 Forward 阶段：伪代码逐行拆解

1. 伪代码（修正 OCR 错误后）

1  Rank_1_Method(vector s0, matrix A1..An) {
2    vector s[1..n]; vector pred[1..n];
3    vector conv;
4    // proc p owns stages (lp..rp]
5    ∀p: lp = n/P*(p-1); rp = n/P*p;
6    // parallel forward phase
7    parallel.for p in (1..P) {
8      local s = (p == 1 ? s0 : nz);
9      for i in (lp+1..rp) {
10       pred[i] = A_i ★ s;
11       s = s[i] = A_i ⊙ s;
12     }
13     --barrier
14     do { // till convergence (fix up loop)
15       parallel.for p in (2..P) {
16         conv[p] = false;
17         // obtain final soln from prev proc
18         s = s[lp];
19         for i in (lp+1..rp) {
20           pred[i] = A_i ★ s;
21           s = A_i ⊙ s;
22           if (s is parallel to s[i]) {
23             conv[p] = true;
24             break;
25           }
26           s[i] = s;
27         }
28       }
29       --barrier
30       conv = ∧ conv[p];
31     } while (!conv);
32     // parallel backward phase is in Figure 5
33     return Backward_Par(pred);
34  }

2. 第 5 行：阶段划分

∀p: lp = n/P*(p-1); rp = n/P*p;

把 $n$ 个阶段平均分给 $P$ 个处理器。处理器 $p$ 负责阶段 $(l_p, r_p]$，即 $l_p+1$ 到 $r_p$。

例子：$n=100$，$P=4$：

处理器	$l_p$	$r_p$	负责阶段
1	0	25	1–25
2	25	50	26–50
3	50	75	51–75
4	75	100	76–100

注意：每个处理器负责的区间是左开右闭 $(l_p, r_p]$，所以相邻处理器共享边界（$P_1$ 的 $r_p=25$ 是 $P_2$ 的 $l_p=25$）。这个共享边界是后面通信的接口。

3. 第 8 行：初始向量

local s = (p == 1 ? s0 : nz);

• 处理器 1：从真实初始向量 $\bar{s}_0$ 开始。
• 其他处理器：从 nz（non-zero，全非零向量）开始。

nz 是任意向量，唯一要求是没有 $-\infty$ 分量（4.5 节解释原因）。

4. 第 9–12 行：第一遍计算（random phase）

for i in (lp+1..rp) {
  pred[i] = A_i ★ s;    // 算前驱
  s = s[i] = A_i ⊙ s;   // 算值，并存到 s[i]
}

• 和顺序算法的 Forward 完全一样，只是处理器 $p$ 只算自己负责的阶段。
• 额外：把每个阶段的解存到 s[i]，后面 fix-up 要用它比较。

这一遍是并行的：$P_1$、$P_2$、…、$P_P$ 同时算，互不等待。

5. 第 13 行：barrier

所有处理器等彼此完成第一遍计算。

6. 第 14–31 行：fix-up 循环

循环条件：while (!conv)，即所有处理器都收敛时退出。

每一轮迭代：

第 15–16 行：并行处理处理器 2 到 $P$（处理器 1 不需要 fix-up，因为它的初始向量是真实的）。

第 17 行：conv[p] = false，先假设没收敛。

第 18 行：s = s[lp]，从前一个处理器拿它最后一个阶段的解。这个解是前一个处理器已经修正过的（或者是第一遍算出的真实解）。

第 19–27 行：重新计算自己的阶段，但带提前终止：

for i in (lp+1..rp) {
  pred[i] = A_i ★ s;
  s = A_i ⊙ s;
  if (s is parallel to s[i]) {   // 检查是否收敛
    conv[p] = true;
    break;                        // 一旦收敛，停止
  }
  s[i] = s;                       // 更新存的值
}

关键逻辑：

• 每算一个阶段，检查新解 s 是否平行于第一遍存下的 s[i]。
• 如果平行，说明从这个阶段开始已经收敛了，后面的阶段也会收敛（秩不增），所以 break 提前退出。
• 如果不平行，说明还没收敛，继续算，并更新 s[i]。

为什么"平行"是收敛判据：如果新解平行于第一遍的解，说明第一遍算出的方向已经正确（只是数值差常数），后面再算也不会改变方向。这就是收敛。

第 29–30 行：barrier + conv = ∧ conv[p]，所有处理器都收敛才退出循环。

7. 收敛的数学依据

处理器 $p$ 负责阶段 $(l_p, r_p]$。它从 s[l_p] 出发（这是前一个处理器修正后的解，已经平行于真实解）。

• 如果存在 $k\in(l_p, r_p]$ 使得 $\operatorname{rank}(M_{l_p\to k})=1$，那么阶段 $k$ 收敛（Lemma 2.2）。
• 由秩不增，阶段 $k$ 之后的所有阶段也收敛。
• 所以 fix-up 只需修正 $k$ 之前的阶段，一旦到达 $k$ 就 break。

如果处理器 $p$ 的阶段太短，没有 $k$ 使秩为 1 呢？

conv[p] 保持 false，下一轮迭代继续。下一轮，处理器 $p$ 会拿到处理器 $p-1$ 修正后的解，相当于把搜索范围扩大到 $(l_{p-1}, r_p]$。如果还不够，再扩大。

最坏情况：fix-up 执行 $P-1$ 轮，退化成顺序算法。但论文说实际中通常一轮就够（第 7 节实验）。

8. 为什么第一遍要存 s[i]

When compared to the sequential algorithm in Figure 2, the Rank-1 method has to additionally store s[i] per stage required to test for convergence in the fix-up loop. If space is a constraint, then the fix-up loop can be modified to recompute s[i] in each iteration, trading compute for space.

• s[i] 用于比较"新解是否平行于旧解"。
• 存储开销：每个阶段存一个向量，共 $n$ 个向量。
• 如果内存不够，可以每轮重算 s[i]，用时间换空间。

9. 实现细节被隐藏

Important to note is that even though the previous discussion refers to partial products, the algorithm does not perform any matrix-matrix multiplications. Like the sequential algorithm, the presentation hides many implementation details in the $\star$ and $\odot$ operations (in lines 10, 11, 19, and 20). In fact, the Rank-1 method can reuse efficient implementations of these operations, including those that use wavefront parallelism, from existing sequential implementations.

关键：

• 伪代码里的 A_i ★ s 和 A_i ⊙ s 是黑盒，可以复用现有优化实现（Spiral、Farrar 等）。
• 算法不做矩阵-矩阵乘法，只做矩阵-向量乘法和前驱乘积。
• 阶段内可以用波前并行，与跨阶段并行叠加。

---

4.5 All-Non-Zero 不变性：为什么初始向量不能有 $-\infty$

1. 问题

A subtle issue with the correctness of the previous algorithm is that starting the LTDP computation midway with an arbitrary initial vector nz could produce a zero vector (one with all $\mathbb{O} = -\infty$ entries) at some stage. If this happens, all subsequent stages will produce a zero vector, resulting in an erroneous result.

危险：如果 nz 有 $-\infty$ 分量，某些阶段可能算出全 $-\infty$ 向量（论文叫"zero vector"）。一旦变成全 $-\infty$，后面所有阶段都是全 $-\infty$，结果完全错误。

为什么全 $-\infty$ 会传播：

热带矩阵乘法：

$$(A\odot\vec{s})[j]=\max_k(A[j,k]+\vec{s}[k])$$

如果 $\vec{s}[k]=-\infty$ 对所有 $k$，那么 $A[j,k]+(-\infty)=-\infty$，max 还是 $-\infty$。所以全 $-\infty$ 向量是"吸收态"，一旦进入就出不来。

2. 解决方案

To avoid this, we ensure that nz is all-non-zero; that is, none of its elements are $\mathbb{O} = -\infty$.

初始向量 nz 的每个分量都不能是 $-\infty$。论文叫这个性质 "all-non-zero"。

注意：这里的 "zero" 指的是热带半环的加法单位元 $-\infty$，不是普通的 0。普通 0 在热带半环里是乘法单位元 1，完全没问题。

3. Lemma 4.1：非平凡矩阵保持 all-non-zero

A transformation matrix $A$ is nontrivial if every row of $A$ contains at least one nonzero entry.

非平凡矩阵：每一行至少有一个非 $-\infty$ 的元素。

LEMMA 4.1. For a nontrivial transformation matrix $A$,

$$\vec{v}\text{ is all-non-zero} \Rightarrow A\odot \vec{v}\text{ is all-non-zero}.$$

证明：

$$(A\odot\vec{v})[i]=\max_k(A[i,k]+\vec{v}[k])$$

因为 $A$ 非平凡，第 $i$ 行存在某个 $k$ 使得 $A[i,k]\neq-\infty$。又因为 $\vec{v}$ 是 all-non-zero，$\vec{v}[k]\neq-\infty$。所以 $A[i,k]+\vec{v}[k]\neq-\infty$。max 中至少有一项不是 $-\infty$，所以结果不是 $-\infty$。

对每一行 $i$ 都成立，所以 $A\odot\vec{v}$ 是 all-non-zero。$\square$

4. 为什么可以假设矩阵非平凡

In Equation (1), the $j$ row of matrix $A_i$ captures how the subproblem $j$ in stage $i$ depends on the subproblems in stage $i - 1$. If all entries in this row are $-\infty$, then the subproblem $j$ is forced to be $-\infty$ for any solution to stage $i - 1$. Such trivial subproblems can be removed from a given LTDP instance.

如果某一行全是 $-\infty$，说明这个子问题不依赖前一阶段的任何子问题，它的值恒为 $-\infty$。这种"平凡子问题"可以直接从问题中删掉，不影响其他子问题。

所以可以安全假设：LTDP 实例的变换矩阵都是非平凡的。

5. 引理的局限

Here we rely on the fact that no element has an inverse under max, except $-\infty$. As such, this lemma is not necessarily true in other semirings.

关键依赖：在 max 运算下，只有 $-\infty$ 是"吸收元"（$\max(x,-\infty)=x$，但 $x+(-\infty)=-\infty$）。这个性质保证了"非 $-\infty$ + 非 $-\infty$ = 非 $-\infty$"。

在其他半环里（比如普通实数加法），这个引理不一定成立。这是热带半环的特殊性质。

---

4.6 并行 Backward 阶段

1. 为什么需要并行 Backward

In many applications, the forward phase overwhelmingly dominates the execution time, and parallelizing the backward phase is not necessary. If this is not the case, the backward phase can be parallelized using the same idea as the parallel forward phase as described later.

• 很多应用里 Forward 是瓶颈，Backward 很快，不需要并行。
• 但如果 Forward 和 Backward 都慢，可以用同样的秩收敛思路并行 Backward。

2. 两种 Backward 方式

One way to obtain this predecessor is by iteratively looking up the predecessor products pred[i] computed during the forward phase. Another way to obtain this is through repeated matrix multiplication as $M_{i \leftarrow n} \star \vec{s}_i$, where $M_{i \leftarrow n}$ is the backward partial product $A_n \odot \ldots \odot A_{i+1}$.

方式 1（顺序查表）：用 Forward 算好的 pred[i]，从后往前查。这是图 2 的方式。

方式 2（矩阵乘法）：用反向部分乘积 $M_{i\leftarrow n}=A_n\odot\cdots\odot A_{i+1}$，计算 $M_{i\leftarrow n}\star\vec{s}_i$。

秩收敛同样适用：$M_{i\leftarrow n}$ 的秩也会随 $i$ 减小而收敛到 1。

3. Lemma 4.2：秩 1 矩阵的前驱乘积所有元素相等

LEMMA 4.2. For a matrix A of rank 1 and any vector $\vec{v}$, all elements of $A \star \vec{v}$ are equal.

证明：

秩 1 矩阵 $A=\vec{c}\odot\vec{r}^{\mathrm{T}}$，所以 $A[j,k]=\vec{c}[j]+\vec{r}[k]$。

$$(A\star\vec{v})[j]=\arg\max_k(A[j,k]+\vec{v}[k])=\arg\max_k(\vec{c}[j]+\vec{r}[k]+\vec{v}[k])$$

因为 $\vec{c}[j]$ 与 $k$ 无关，可以提出来：

$$=\arg\max_k(\vec{r}[k]+\vec{v}[k])$$

这个 argmax 与 $j$ 无关！所以所有 $j$ 得到相同的下标。$\square$

直观：秩 1 矩阵的所有行只差一个常数，给所有候选值加同一个常数不改变 argmax。所以每一行的 argmax 位置相同。

4. 并行 Backward 伪代码

1  Backward_Par(vector pred[1..n]) {
2    vector res; vector conv;
3    // proc p owns stages (lp..rp]
4    ∀p: lp = n/P*(p-1); rp = n/P*p;
5    // parallel backward phase
6    parallel.for p in (P..1) {
7      // all processors start from 0
8      local x = 0;
9      for i in (rp..lp+1) {
10       x = res[i] = pred[i][x];
11     }
12     --barrier
13     do { // till convergence (fix up loop)
14       parallel.for p in (P-1..1) {
15         conv[p] = false;
16         // obtain final result from next proc
17         local x = res[rp+1];
18         for i in (rp..lp+1) {
19           x = pred[i][x];
20           if (res[i] == x)
21             conv[p] = true;
22             break;
23           res[i] = x;
24         }
25       }
26       --barrier
27       conv = ∧ conv[p];
28     } while (!conv)
29     return res;
30  }

5. 与 Forward 的对称性

方面	Forward	Backward
处理器顺序	$1\to P$	$P\to 1$
初始值	$P_1$ 用 $\bar{s}_0$，其他用 nz	所有处理器从 0 开始
依赖方向	从前一阶段拿 s[lp]	从后一阶段拿 res[rp+1]
收敛判据	新解平行于旧解	新 x 等于旧 res[i]
收敛依据	秩 1 矩阵映射到平行向量（Lemma 2.2）	秩 1 矩阵前驱全相等（Lemma 4.2）

注意：Backward 的收敛判据是 res[i] == x（相等），不是"平行"。因为 res[i] 是下标（前驱），不是向量。前驱是整数，只有相等/不等，没有"平行"。

6. 为什么所有处理器从 0 开始

all processors start from 0

在 Backward 里，每个处理器从"最后一个阶段的第 0 个位置"开始回溯。如果它的阶段足够长，秩收敛后，回溯路径会独立于起点（Lemma 4.2 保证秩 1 矩阵的前驱与输入无关）。

所以从任意起点（这里统一用 0）出发，只要阶段够长，结果都一样。

---

4.7 秩收敛的直观解释：高速公路类比

1. 图论视角

One can view solving an LTDP problem as computing shortest/longest paths in a graph. In this graph, each subproblem is a node and directed edges represent the dependencies between subproblems. The weights on edges represent the constants $A_{i}[j,k]$ in Equation (1).

把 LTDP 看成图上的最长/最短路径问题：

• 每个子问题 = 一个节点。
• 依赖关系 = 有向边。
• $A_i[j,k]$ = 边的权重。
• 求最优解 = 求最长路径。

2. 部分乘积的图论含义

Entries in the partial product $M_{l\to r}$ represent the cost of the shortest (or longest) path from a node in stage $l$ to a node in stage $r$.

$M_{l\to r}[j,k]$ = 从阶段 $l$ 的节点 $k$ 到阶段 $r$ 的节点 $j$ 的最优路径代价。

3. 秩 1 的图论含义

The rank of this product is 1 if these shortest paths go through a single node in some stage between $l$ and $r$.

秩 1 ⟺ 所有最优路径都经过某个中间阶段的同一个节点。

如果所有从阶段 $l$ 到阶段 $r$ 的最优路径都经过节点 $X$，那么：

• 从任何起点到任何终点的最优路径 = (起点到 $X$) + ($X$ 到终点)。
• 起点只影响前半段（一个常数），终点只影响后半段（一个常数）。
• 所以 $M_{l\to r}$ 可以分解成"列向量 × 行向量"——秩 1。

4. 高速公路类比

Road networks have this property. For instance, the fastest path from any city in Washington State to any city in Massachusetts is highly likely to go through Interstate I-90 that connects the two states. Routes that use I-90 are overwhelmingly better than those that do not; choices of the cities at the beginning and at the end do not drastically change how intermediate stages are routed.

类比：

• 从华盛顿州任何城市到马萨诸塞州任何城市，最快路线几乎一定经过 I-90 高速公路。
• 不经过 I-90 的路线太慢，不会被选为最优。
• 所以"起点选哪个城市"和"终点选哪个城市"不影响中间走哪条路。

对应到 LTDP：

• 阶段 $l$ 的起点 = 华盛顿州的城市。
• 阶段 $r$ 的终点 = 马萨诸塞州的城市。
• I-90 = 秩 1 分解中的"那个中间节点"。
• 所有最优路径经过 I-90 ⟺ 部分乘积秩为 1。

5. 什么时候秩收敛

Similarly, if problem instances have optimal solutions that are overwhelmingly better than other solutions, one should expect rank convergence.

秩收敛的条件：最优解显著优于其他解。

• 如果最优路径比次优路径好很多，所有起点都会选同一条"主干道"，秩收敛快。
• 如果最优路径和次优路径差不多，不同起点可能选不同路径，秩不收敛或收敛慢。

这解释了第 7.1 节 Table I 的现象：

• Smith-Waterman 收敛快（24 步）：最优比对显著优于其他比对。
• LCS 有时不收敛：很多子序列长度相同，最优解不唯一，没有"主干道"。

---

本节逻辑链总结

4.1 直接并行（矩阵-矩阵乘法）开销太大 ✗
  ↓
4.2 秩收敛：从任意初始向量出发，秩降到 1 后解平行于真实解 ✓
  │  依据：Lemma 2.2（秩 1 映射到平行向量）
  │  依据：Lemma 3.1（平行向量前驱相同）
  ↓
4.3 三阶段：random phase → fix-up → backward
  ↓
4.4 Forward 并行：每个处理器从任意 nz 开始，算自己的阶段；
    fix-up 循环从前一个处理器拿真实解，重算直到收敛
  ↓
4.5 初始向量必须 all-non-zero，否则会塌缩成全 -∞（Lemma 4.1）
  ↓
4.6 Backward 并行：对称思路，用 Lemma 4.2（秩 1 前驱全相等）
  ↓
4.7 直观解释：秩 1 = 所有最优路径经过同一"主干道"（高速公路类比）

---

最容易踩的坑

1. "秩收敛"不是定理，是经验假设。论文明确说理论上可能不收敛，只是实际中几乎总收敛。整个算法的正确性依赖这个经验性质。

2. 算法不做矩阵-矩阵乘法。$M_{i\to j}$ 只是概念工具，用于论证。实际只做矩阵-向量乘法和前驱乘积。

3. fix-up 的收敛判据是"平行"不是"相等"。Forward 里检查 s is parallel to s[i]，不是 s == s[i]。因为目标是平行，不是精确相等。

4. Backward 的收敛判据是"相等"。因为 res[i] 是下标（整数），不是向量，没有"平行"概念。

5. nz 的 "zero" 是 $-\infty$ 不是 0。All-non-zero 意思是"没有 $-\infty$ 分量"，普通 0 完全可以有。

6. 最坏情况退化成顺序算法。如果秩不收敛，fix-up 执行 $P-1$ 轮，每轮范围扩大，最终等于顺序算法。所以算法不会错，只是可能不快。

7. 处理器 1 不参与 fix-up。因为它的初始向量是真实的 $\bar{s}_0$，不需要修正。fix-up 从处理器 2 开始。

8. 第一遍的 pred[i] 可能被覆盖。fix-up 里重新计算 pred[i]，覆盖第一遍的值。最终用的是修正后的 pred[i]。

9. barrier 的位置很关键。第 13 行（第一遍后）、第 29 行（每轮 fix-up 后）都有 barrier，确保处理器之间同步。少了 barrier 会有数据竞争。

10. 高速公路类比只解释"为什么秩会收敛"，不解释"算法怎么工作"。类比是直觉，不是证明。算法的正确性靠 Lemma 2.2 和 Lemma 3.1。

---

一句话总结第 4 节

直接并行（矩阵-矩阵乘法）开销太大，Rank-1 方法改用秩收敛：让每个处理器从任意 all-non-zero 向量出发，同时计算自己负责的阶段；由于热带矩阵连乘的秩单调不增且实际中很快降到 1，后面阶段的解会平行于真实解（Lemma 2.2），而平行向量的前驱完全相同（Lemma 3.1），所以路径正确；第一遍算完后，用前一个处理器的真实解做 fix-up，重算开头未收敛的阶段，直到新解平行于旧解；最坏情况退化成顺序算法，但实际中通常一轮 fix-up 就收敛。

---

如果这一节已经吃透，下一步可以进入 第 5 节 THE PARALLEL DELTA METHOD。这一节是 Rank-1 方法的改进版，专门针对 Local LTDP（LLTDP） 问题（如 LCS、Needleman-Wunsch），核心思想是：

• 不存每个格子的值，存相邻格子的差（delta）。
• 只重算受错误 delta 影响的那部分格子，而不是整列重算。
• Lemma 5.1：delta 和 pred 只依赖相邻的两个 delta，与绝对位置无关。
• Lemma 5.3：一旦出现一条"全正确 delta 的路径"，后面的 delta 全正确。

这一节的关键是理解"为什么 delta 比绝对值更适合并行"，以及"workQueue 怎么追踪需要重算的格子"。