7 Evaluation

第 7 节 EVALUATION 精读

这一节是全文的实验验证。它要回答三个问题：

1. 秩收敛在实际数据上真的会发生吗？（7.1）
2. 并行算法在四个基准上到底快多少？（7.3）
3. Delta 方法真的比 Rank-1 快吗？跨阶段并行真的比波前并行好吗？（7.4、7.5）

下面逐节拆解，重点讲实验数据如何印证前面的理论。

---

7.1 LTDP Rank Convergence：秩收敛的实测

1. 测量方法

For an LTDP instance, defined by the algorithm (Column 1) and input (Column 2), we first compute the actual solution vectors at each stage. Then, starting from a random all-non-zero vector at 200 different stages, we measured the number of steps required to generate a vector parallel to the actual solution vector (i.e., convergence).

测量步骤：

1. 先算出真实解：用顺序算法跑一遍，得到每个阶段的真实解向量 $\bar{s}_i$。
2. 从 200 个不同阶段出发：在每个阶段 $i$，用一个随机 all-non-zero 向量 $\bar{t}_i$ 代替真实解。
3. 往后算：计算 $\bar{t}_{i+1}=A_{i+1}\odot\bar{t}_i$，$\bar{t}_{i+2}=A_{i+2}\odot\bar{t}_{i+1}$，……
4. 检查何时收敛：每算一步，检查 $\bar{t}_j$ 是否平行于 $\bar{s}_j$。记录第一次平行的步数。
5. 统计 200 次：对 200 个不同起点，记录最小、中位数、最大步数。

关键：这是离线测量，不是算法的一部分。目的是回答"秩收敛在实际数据上需要多少步"，为后面的性能分析提供依据。

2. Table I 数据解读

算法	输入	最小	中位数	最大
Viterbi	Voyager	26	224	104
Viterbi	LTE	26	183	62
Viterbi	CDMA	28	223	872
Viterbi	MARS	214	461	12414
Smith-Waterman	Query-1	6	0	3
Smith-Waterman	Query-2	8	8	4
Smith-Waterman	Query-3	12	27	48
Smith-Waterman	Query-4	1	576	48
Needleman-Wunsch	Width 1,024	1,580	19,483	192,747
Needleman-Wunsch	Width 2,048	3,045	44,891	378,363
Needleman-Wunsch	Width 4,096	5,586	101,085	404,437
Needleman-Wunsch	Width 8,192	12,005	267,391	802,991
LCS	Width 8,192	9,142	79,530	370,927
LCS	Width 16,384	19,718	270,320	—
LCS	Width 32,768	42,597	626,688	—
LCS	Width 65,536	86,393	—	—

关键观察：

(a) Smith-Waterman 收敛极快：中位数 0–576，大多数在个位数。印证了第 6 节"0 项创造主干道"的直觉。

(b) Viterbi 收敛中等：中位数 183–461。不同卷积码差异大（CDMA 223 vs MARS 461）。说明收敛速度依赖输入结构。

(c) Needleman-Wunsch 收敛慢：中位数 19k–267k。没有 0 项，最优路径分散，没有主干道。

(d) LCS 收敛最慢，有时不收敛：中位数 79k–626k，宽度 65,536 时中位数缺失（200 次测量中很多没收敛）。LCS 最优解不唯一，大量并列最长子序列，没有单一主干道。

(e) 宽度越大，收敛越慢：NW 和 LCS 都显示这个趋势。阶段越大，部分乘积的"混合"越慢，秩降到 1 需要更多步。

3. 与理论的对应

观察	理论解释
SW 收敛快	0 项创造"重启点"，所有最优路径经过它（4.7 节高速公路类比）
Viterbi 收敛中等	HMM 转移概率有偏好，但不如 SW 的 0 项强
NW 收敛慢	无 0 项，最优比对可能分散在不同区域
LCS 有时不收敛	大量并列最优解，没有单一"主干道"
宽度越大越慢	阶段越大，$M_{i\to j}$ 的"混合"越慢，秩降得越慢

这一节的核心贡献：把"秩收敛"从经验假设变成可测量的实验事实，并展示它在不同问题上的巨大差异。

---

7.2 Environmental Setup：实验环境

1. 分布式内存机器：Stampede

Stampede, a Dell PowerEdge C8220 Cluster with 6,400 nodes... Each node contains two 8-core Intel Xeon E5-2600 processors @2.70GHz (16 cores in total) and 32GB of memory. The interconnect topology is a fat-tree, FDR InfiniBand interconnect.

• 规模：6,400 节点，每节点 16 核，共 102,400 核。
• 本文最多用 128 核（8 节点）。
• 通信：MPI（MVAPICH 2），InfiniBand 互联。
• 用途：报告所有 scalability 结果。

2. 共享内存机器

An unloaded Intel 2.27GHz Xeon (E7) workstation with 40 cores (80 threads with hyperthreading) and 128GB RAM.

• 规模：40 核（80 线程），128GB 内存。
• 用途：与波前并行对比（7.5 节）。
• 为什么用共享内存做对比：波前并行依赖频繁同步，共享内存通信快，对波前并行有利。用共享内存对比，如果本文方法还赢，说明优势不是靠通信快。

3. 测量方式

We use the MPI/OMP timer to measure process runtime. We do not measure setup costs—only the time it takes to execute one invocation of an LTDP problem.

• 只测一次 LTDP 调用的执行时间，不算 setup。
• 与基线对比时，基线代码也改成同样的测量方式。

4. 统计显著性

We run each experiment multiple times and report the mean and 95% confidence interval of the mean when appropriate.

• 多次运行，报告均值和 95% 置信区间。
• 置信区间小就不画在图上。

---

7.3 LTDP Benchmarks and Performance：四个基准的性能

7.3.1 Viterbi Decoder：24× 加速

基线与实现

Baseline. We used Spiral's Viterbi decoder: a highly optimized (via autotuning) decoder that utilizes SIMD to parallelize decoding within a stage.

• 基线：Spiral 的 Viterbi 解码器，自动调优 + SIMD，高度优化。
• 本文实现：把 Spiral 的内部循环当黑盒，用 Rank-1 方法做跨阶段并行。

Viterbi is not LLTDP and therefore we only implemented the Rank-1 method.

Viterbi 非 LLTDP，只能用 Rank-1。

数据

• 四种卷积码：Voyager、LTE、CDMA、MARS。
• 四种包大小：2,048、4,096、8,192、16,384。
• 每种组合 50 个随机包。

结果（Figure 11、12）

Figure 11（Voyager 和 LTE）和 Figure 12（CDMA 和 MARS）：

• 左图：吞吐量（Mb/S）和加速比随核数变化。
• 右图：效率（加速比 / 核数）。
• 实心点：fix-up 第一轮就收敛。
• 空心点：需要多轮 fix-up。

关键数据：

With 64 processors, our CDMA Viterbi decoder processing packets of size 16,384 decodes at a rate of 434Mb/S, which is 24× faster than the sequential algorithm.

• CDMA，64 核，16,384 包：434 Mb/S，24× 加速。
• MARS，同条件：只有 4.4 Mb/S，因为 MARS 每 bit 的计算量大得多。

为什么不同卷积码差异大：

The performance of our Rank-1 method—and thus our speedup numbers—depends on the rate of rank convergence for each pair of convolution codes and network size, as shown in Table I.

• CDMA 收敛中位数 223，MARS 收敛中位数 461。
• MARS 收敛慢 → fix-up 多 → 加速比低。

为什么包越大越快：

A larger network packet size provides better performance across all convolution codes... because the amount of recomputation (i.e., the part of the computation that has not converged), as a proportion of the overall computation, decreases with a larger network packet size.

• 包越大，阶段越多，收敛前的那段占总计算的比例越小。
• 所以包越大，效率越高。

期望加速比 vs 实际加速比（Table III）

The expected speedup is computed by

$$\frac{w.l}{\frac{w.l}{P} + w.o},$$

其中：

• $w$：每列计算量。
• $l$：计算长度（包大小）。
• $P$：处理器数。
• $o$：收敛步数中位数（Table I）。

含义：总工作量 $w\cdot l$，每处理器工作 $w\cdot l/P$，每个处理器额外开销 $w\cdot o$（收敛前的重算）。这是 Amdahl 定律的变形。

Table III：

卷积码	核数	期望加速比	实际加速比
Voyager	32	29.68	11.45
LTE	32	30.22	12.78
CDMA	64	55.72	23.52
MARS	64	44.52	21.10

关键观察：实际加速比远低于期望加速比。

This is not surprising since the amount of computation is very limited in this problem.

原因：Viterbi 每列计算量很小，通信开销占比大。期望加速比没算通信开销，实际有通信，所以差很多。

这印证了 4.4 节的讨论：Rank-1 方法的效率依赖"阶段足够长"，Viterbi 的阶段（每列）相对短，通信开销显著。

---

7.3.2 Smith-Waterman：近线性加速

基线与实现

• 基线：Farrar 的 SIMD 算法（最快的 CPU 版本）。
• 本文实现：Rank-1 方法，Farrar 算法当黑盒。
• 为什么不用 Delta：Smith-Waterman 非 LLTDP（加了 running max），Delta 不适用。

数据

• 人类基因组 hg19 的染色体 1、2、3、4 作为数据库。
• 4 个随机 EST 作为查询。
• 16 种组合，每种跑 5 次。

结果（Figure 13）

关键数据：

The efficiency plot in Figure 13 demonstrates that our approach has efficiency ~1 for any number of processors, which means almost a linear speed-up with up to 128 processors.

• 效率 ≈ 1：128 核几乎线性加速。
• 没有明显数据依赖：不同 DNA/查询组合性能差不多。

为什么这么好：

Since the length of computation is significantly larger than the number of steps for convergence to rank 1 (100 million vs. 24), the expected speedup is very close to the linear speedup.

• 计算长度 1 亿，收敛步数 24。
• 收敛前的重算只占 $24/10^8$，可以忽略。
• 所以效率接近 1。

印证了 Table I：SW 收敛中位数 8，远小于计算长度，所以 fix-up 开销可忽略。

通信开销小：

• SW 每阶段只传一个向量（大小为查询长度），计算量是 $10^8$ 级别，通信占比极小。
• 所以实际加速比接近期望加速比（论文说"omitted the comparison"因为太接近了）。

---

7.3.3 Needleman-Wunsch：Delta 方法，性能依赖输入

基线与实现

• 基线：Delta 方法的 SIMD 实现（阶段内并行）。
• 本文实现：并行 Delta 方法（跨阶段并行 + 阶段内 SIMD）。

数据

• 四对染色体：(17,18)、(19,20)、(21,22)、(X,Y)。
• 每对只用前 100 万个元素（内存限制）。
• 四种宽度：1,024、2,048、4,096、8,192。

结果（Figure 14）

关键观察：

(a) 性能因染色体对而异：

We separated them and reported the best-performing pair ((X,Y) in Figure 14(a)) and the worst-performing pair ((21, 22) in Figure 14(b)).

• (X,Y)：最好，128 核加速比约 70×。
• (21,22)：最差，128 核加速比约 20×。

原因：不同染色体对的收敛速度不同（Table I 显示 NW 收敛步数范围 19k–267k）。

(b) 宽度越大，性能越差：

Larger widths perform more poorly than smaller ones since the convergence rate depends on the size of each stage in an LTDP instance.

• 宽度 1,024 最快，8,192 最慢。
• 因为宽度大 → 阶段大 → 收敛慢（Table I：宽度 1,024 中位数 19k，8,192 中位数 267k）。
• 收敛慢 → fix-up 多 → 加速比低。

期望 vs 实际（Table IV）

宽度	期望加速比	实际加速比
1,024	119.8	83.3
2,048	112.7	83.2
8,192	101.6	74.9
16,384	87.0	64.2

关键观察：期望和实际比较接近（不像 Viterbi 差那么多）。

This means that the cost of communication in this problem is relatively small.

原因：NW 每阶段只传一个宽度大小的向量（最多 16,384），而计算量是 $16,384\times 10^6$，通信占比小。

对比 Viterbi：Viterbi 每列计算量小，通信占比大；NW 每阶段计算量大，通信占比小。这说明通信开销取决于"计算/通信比"，不是绝对的。

---

7.3.4 LCS：Delta 方法，性能依赖输入，通信开销显著

基线与实现

• 基线：bit-parallel 的单核 LCS（Deorowicz 2010; Hyyro 2004）。
• 本文实现：并行 Delta 方法，bit-parallel 当阶段内实现。

数据

• 同 NW 的四对染色体。
• 宽度：8,192、16,384、32,768、65,536。

结果（Figure 15）

关键观察：

(a) 性能差异更大：

• (X,Y)：最好，128 核加速比约 40×。
• (21,22)：最差，128 核加速比约 10×。

原因：LCS 收敛更慢，有时不收敛（Table I 中宽度 65,536 中位数缺失）。

(b) 宽度越大，性能越差：同 NW，但更明显。

期望 vs 实际（Table V）

宽度	期望加速比	实际加速比
8,192	88.7	41.3
16,384	72.8	36.4
32,768	58.0	28.6
65,536	45.6	24.0

关键观察：实际远低于期望。

This is because of the communication overhead.

原因：

• LCS 的 delta 只有 0/1，每阶段数据量小，但计算量也小（bit-parallel 极快）。
• 计算/通信比低，通信开销占比大。
• 所以实际加速比远低于期望。

对比 NW：NW 的 delta 范围大（计算量大），计算/通信比高，通信开销小。LCS 的 bit-parallel 太高效，反而使通信成为瓶颈。

---

7.4 Rank-1 vs Delta：Delta 快 5–15 倍

1. LCS 对比（Figure 16）

The left plot shows the performance of the Delta method over the Rank-1 method for a different number of cores using different widths. The right plot shows the ratio of the total amount of work done in the last processor by the Rank-1 method to that done by the Delta method.

左图：Delta / Rank-1 的加速比。 右图：最后一个处理器的工作量比值（Rank-1 / Delta）。

关键数据：

The Delta method is between ~5× and ~15× faster than the Rank-1 method with 128 cores.

• 128 核，Delta 比 Rank-1 快 5–15 倍。
• 宽度越大，Delta 优势越大（因为 Rank-1 整列重算，浪费更多）。

为什么：

The Delta method has a greater impact with wider widths since the Rank-1 method recomputes all deltas even if only one of them is incorrect.

• Rank-1：整列重算，哪怕只有一个 delta 错。
• Delta：只重算受影响的格子（workQueue）。
• 宽度越大，整列里"错的格子"占比越小，Rank-1 浪费越多。

2. Needleman-Wunsch 对比（Figure 17）

The Delta method is between ~2× and ~10× faster than the Rank-1 method with 128 cores.

• NW：Delta 比 Rank-1 快 2–10 倍。
• 比 LCS 略小，因为 NW 的 delta 范围大，Delta 方法本身计算量大一些。

3. 与工作量的对应

This is compatible with the ratio of the amount of work for the last processor.

右图的工作量比值与左图的加速比吻合。说明 Delta 的加速直接来自减少重算工作量，不是别的因素。

这印证了第 5.4 节的理论：Delta 只重算子集，Rank-1 整列重算，所以 Delta 更快。

---

7.5 Wavefront vs LTDP：跨阶段并行 vs 阶段内并行

1. 对比设置

We used OpenMP for wavefront implementations and compared it with our MPI implementation used in our Stampede experiments earlier, but running on our shared-memory machine.

• 波前并行：OpenMP，共享内存。
• 本文方法：MPI 代码，跑在共享内存机器上。
• 偏向波前：共享内存通信快，对波前有利；MPI 在共享内存上不是最优。如果本文方法还赢，说明优势不是靠通信。

2. 波前实现

Needleman-Wunsch：

• 分块（tiling）+ 块内 SIMD。
• 波前沿块的反角线推进。
• 调优了分块参数。

LCS：

• 分块 + 块内 bit-parallel。
• 波前沿块的反角线推进。

3. 结果（Figure 18）

左图：本文方法的性能和加速比。 右图：本文方法 / 波前的加速比。

关键数据：

Our approach is ~9× faster than the wavefront approach with 40 processors for Needleman-Wunsch and ~6× faster than the wavefront approach for LCS with width size 8,192.

• NW：40 核，本文方法比波前快 9×。
• LCS：40 核，宽度 8,192，本文方法比波前快 6×。

为什么本文方法赢：

Small widths are better for our approach (as the wavefront approach incurs more barriers per unit of compute), while large widths are better for the wavefront approach (as our approach is less likely to reach rank 1).

小宽度：

• 阶段小 → 波前并行的并行度低 → 大量 barrier → 波前效率低。
• 本文方法不受阶段大小限制 → 优势大。

大宽度：

• 阶段大 → 波前并行度高 → barrier 少 → 波前效率高。
• 本文方法收敛慢 → fix-up 多 → 优势小。

Figure 18 右图：宽度 8,192（小宽度）时本文方法优势最大，宽度 65,536（大宽度）时优势最小。完美印证理论。

4. 两种方法互补

We should note that the two approaches are complementary. Exploring the optimal way to distribute a given budget of processors to simultaneously use across-stage parallelism and within-stage parallelism is left for future work.

• 不是替代关系：波前并行阶段内，本文方法阶段间。
• 可以叠加：阶段内用波前，阶段间用 Rank-1/Delta。
• 最优分配是未来工作：给定 $P$ 个处理器，多少用于阶段间、多少用于阶段内？论文没解决。

---

本节逻辑链总结

7.1 秩收敛实测（Table I）
  │  SW 极快（8步）→ 0 项创造主干道
  │  Viterbi 中等（183–461）→ HMM 有偏好
  │  NW 慢（19k–267k）→ 无 0 项
  │  LCS 最慢/有时不收敛 → 大量并列最优
  ↓
7.2 环境：Stampede（分布式）+ 共享内存（对比波前）
  ↓
7.3 四个基准
  │  Viterbi：24×（64核），但实际远低于期望（通信开销大）
  │  SW：近线性（128核），收敛快 + 通信小
  │  NW：Delta 方法，性能依赖输入和宽度，通信开销小
  │  LCS：Delta 方法，性能依赖输入和宽度，通信开销大
  ↓
7.4 Delta vs Rank-1
  │  LCS：Delta 快 5–15×
  │  NW：Delta 快 2–10×
  │  优势来自减少重算工作量
  ↓
7.5 Wavefront vs LTDP
  │  小宽度：本文方法快 9×（NW）/ 6×（LCS）
  │  大宽度：本文方法优势小
  │  两种方法互补，可叠加

---

最容易踩的坑

1. Table I 是离线测量，不是算法的一部分。它回答"秩收敛需要多少步"，为性能分析提供依据。算法本身不测收敛步数，只检查"新解是否平行于旧解"。

2. 实际加速比远低于期望，不是算法错。Viterbi 和 LCS 的差距来自通信开销，期望加速比公式没算通信。NW 和 SW 差距小，因为计算/通信比高。

3. SW 效率 ≈ 1 不是因为算法特殊，是因为收敛快 + 通信小。计算长度 1 亿，收敛 24 步，重算占比可忽略。

4. LCS 的 Delta 比 NW 快，但 LCS 实际加速比低于 NW。Delta vs Rank-1 是方法对比；实际加速比是并行 vs 顺序。LCS 的 bit-parallel 太快，通信成为瓶颈，所以并行加速比低。NW 计算量大，通信占比小，并行加速比高。

5. 波前对比用共享内存，对波前有利。如果本文方法在共享内存上还赢，说明优势不是靠通信快，而是靠算法结构。

6. 小宽度本文方法赢，大宽度波前赢（或差距缩小）。因为小宽度波前 barrier 多，大宽度本文收敛慢。这是两种方法的互补性。

7. "24×"是 Viterbi 的最好情况（CDMA，64 核，16,384 包）。不是所有配置都 24×。MARS 同条件只有 4.4 Mb/S，加速比低得多。

8. Table III 的期望加速比公式是 Amdahl 定律变形。$w\cdot l$ 是总工作量，$w\cdot l/P$ 是每处理器工作量，$w\cdot o$ 是收敛前的重算开销。分母是每处理器的实际时间，分子是总工作量。

9. NW 和 LCS 的宽度选择影响性能。宽度小 → 阶段小 → 收敛快（Table I）→ fix-up 少 → 性能好。但宽度太小可能影响比对质量（第 6 节说宽度 > 8,192 不影响分数）。

10. 7.5 节的"9×"和"6×"是相对波前，不是相对顺序。波前本身已经比顺序快，本文方法比波前还快 6–9×，说明跨阶段并行的增量价值很大。

---

一句话总结第 7 节

Table I 实测秩收敛：SW 极快（8 步，0 项创造主干道）、Viterbi 中等（183–461）、NW 慢（19k–267k）、LCS 最慢甚至不收敛（大量并列最优）；四个基准上，Viterbi 64 核 24×（但通信开销大，实际远低于期望）、SW 近线性（收敛快 + 通信小）、NW 和 LCS 用 Delta 方法（性能依赖输入和宽度，LCS 通信开销大因 bit-parallel 太快）；Delta 比 Rank-1 快 5–15×（LCS）/ 2–10×（NW），优势来自精确重算子集；小宽度下本文方法比波前快 9×（NW）/ 6×（LCS），大宽度下优势缩小，两种方法互补可叠加。

---

下一步进入 第 8 节 RELATED WORK 和第 9 节 CONCLUSIONS。这两节比较短：

• 第 8 节：与波前并行、top-down 并行、理论并行复杂度、问题专用实现（bit-parallel LCS、Farrar SW、systolic Viterbi）的对比。重点理解本文方法与它们的区别和联系。
• 第 9 节：总结两大贡献（Rank-1 和 Delta）、主要结果（24×）、未来方向（GPU/FPGA）。

之后如果需要，我们还可以回头做全文回顾，把第 2–7 节的逻辑链串成一张完整的图。