Amdahl's Law

Amdahl 定律（阿姆达尔定律）是并行计算里的一条基本规律，用来回答：

如果程序里有一部分不能并行加速，那么无论你加多少处理器、把能并行的部分加速多少倍，总加速比都有一个上限。

---

1. 公式

设：

• $p$：程序中可以并行/可以加速的比例；
• $1-p$：程序中不能并行/不能加速的比例；
• $N$：处理器数量或加速资源数量。

那么总加速比 $S(N)$ 为：

$$S(N)=\frac{1}{(1-p)+\frac{p}{N}}$$

当 $N \to \infty$ 时：

$$S_{\max}=\frac{1}{1-p}$$

也就是说，最大加速比只取决于不可加速部分的比例。

---

2. 直觉解释

假设一个程序总时间是 100 秒：

• 其中 90 秒可以并行加速；
• 剩下 10 秒必须串行执行，无法加速。

那么：

• 即使你有 1000 个处理器，把 90 秒的部分加速到几乎为 0；
• 总时间仍然至少是 10 秒；
• 所以最大加速比最多是：

$$\frac{100}{10}=10\times$$

不可能达到 1000 倍。

这就是 Amdahl 定律的核心：

串行部分决定了加速上限。

---

3. 一个具体计算

假设程序中可并行部分 $p=0.9$，不可并行部分 $1-p=0.1$。

用 $N=1000$ 个处理器：

$$S=\frac{1}{0.1+\frac{0.9}{1000}} =\frac{1}{0.1009} \approx 9.91$$

即使有 1000 个处理器，总加速也只有约 $9.91\times$，接近上限 $10\times$。

如果用 $N=10000$：

$$S=\frac{1}{0.1+\frac{0.9}{10000}} \approx 9.99$$

几乎不再提升。

---

4. 在 TALCO 论文里的意义

论文里提到：

序列比对通常占基因组工作流总执行时间的 $30\%-90\%$。
基于 Amdahl 定律，在已经有三到四个数量级加速的情况下，继续加速比对步骤的收益递减。

意思是：

• tiling 加速器已经把序列比对加速了 1000～10000 倍；
• 但基因组工作流里还有其他步骤不能一起加速；
• 所以即使把比对加速到无限快，总工作流加速也有上限；
• 因此，继续单纯追求比对速度，性价比越来越低；
• 更重要的目标变成了：保证比对质量，让硬件加速器能被真正广泛采用。

TALCO 正是针对这个目标：
它不追求把比对再快多少倍，而是保证 tiling 后结果仍然和完整软件算法一致。

---

5. 一句话总结

Amdahl 定律说：总加速比受限于不可加速部分。可并行部分加速得再多，串行部分也会成为瓶颈。论文用它说明：序列比对已经被 tiling 加速器加速了几个数量级，继续加速收益有限，因此 TALCO 更关注保证比对质量，而不是单纯追求更高速度。