1.3  理解Amdahl法则

如果想要充分发挥多核的优势，在更短时间内运行更多的指令，那么就有必要将代码分解为并行的序列。然而，大部分算法都要求运行一些串行代码来协调并行的执行。例如，以并行方式启动很多块计算，然后收集它们的计算结果。用于分解并行任务和收集结果的代码可能是串行代码，因而不能利用并行化的优势。如果将很多这类算法组合起来，则整体的串行代码的比例会增加，而性能优势可能会下降。

著名计算机架构师Gene Amdahl对只有部分能够改进的计算机系统所能够获得的最大性能提升进行了观察。他通过这些观察定义了Amdahl法则，通过以下公式预测多处理器系统的最大理论性能提升(即加速比，speedup)。这个公式也可以应用于运行在多核微处理器上的并行算法。

最大加速比(倍数) = 1 / ((1 - P) + (P/N)) 

其中：

● P表示能够完全并行运行的代码比例。

● N表示可用的计算单元数(处理器或物理内核数)。

根据这个公式，如果一个算法中总任务的50%(P=0.50)可以并行执行，那么在具有两个物理内核的微处理器上的最大加速比为1.33x。图1-8展示了一个带有1000份任务的算法，其中500份串行任务，500份并行任务。如果串行版本需要耗费1000秒的时间完成，那么带有并行代码的新版本至少需要750秒才能完成。

最大加速比(倍数) = 1 / ((1 - 0.50) + (0.50 / 2)) = 1.33x