第2章 程序性能评估方法

2.1 性能评估的方法

在多核系统中，衡量程序性能的一个重要指标就是加速比S(n)，加速比定义如下：

在加速比的发展历史上，出现过以下两种定义。

（1）Amdahl 定律

Gene Amdahl 发现在计算机体系架构设计过程中，某个部件的优化对整个架构的优化和改善是有上限的。这个发现后来成为著名的 Amdahl 定律。Amdahl定律指出加速比和串行部分所占比例f有关，而与CPU核数n无关，其定义如式（2-1）所示：

当处理器个数n趋近于无穷大时，有以下等式（2-2）：

Amdahl定律的提出让整个软件界灰心了许多年。该定律告诉我们。假如以2倍加速全部程序，那可以预期程序运行的比2倍更快。但是假如只以2倍加速优化程序的一半，那么整个程序只改善9.33倍。Amdahl 定律很容易可视化表达。设想程序由5个相同的部分串行组成，且每个部分的运行时间均花费100秒，如图2-1所示。

如果以2倍和4倍来加速如图2-2所示的两部分，那么程序运行总时间将由原来的500秒分别缩减至400秒和350秒。但是，也应该看到，更多的部分不能通过并行来加速。无论有多少处理器核心可用，串行部分300秒的需求都不会被打破，如图2-3所示。

Amdahl定律最终表明，无论拥有多少个处理器核，都无法让程序运行得更快，但并行程序开发人员可以利用 Amdahl 定律来预测使用多少个处理器核可以达到最大的加速比。总之，Amdahl 定律是个悲观的定律。

（2）Gustafson 定律

Sandia 国家实验室的 John Gustafson 从一个不同的视角来重新审视Amdahl定律，他指出并行非常有用。因为随着计算机越来越强大，应用程序会聚焦在更多工作上，而不是一个固定工作量。今天的应用程序几乎都不运行在10年前的老机器上，甚至也很少运行在5年前的机器上。而且这并不局限在游戏领域，它同样适用于办公软件、Web 浏览器、图形图像处理软件和像 Google Earth 此类的软件。 Gustafson 定律的定义如式（2-3）：

式中，K是一个常数，表示串行执行时间所占的比例。按照Gustafson定律，加速比显然是和CPU核数n成正比的，CPU核数越大，加速比也越大。

Gustafson 定律和 Amdahl 定律本质的差异在于，Amdahl 定律作了几个现实世界中不一定正确的假设。第一个假设就是最优串行算法的性能严格受限于 CPU 资源的可用性。但是实际情况并非如此，多核处理器可能会为每个核实现一个单独的 Cache，这样， Cache 中就能够存放更多的数据，从而降低了存储延迟。Amdahl 定律的第二个缺陷就是它假定串行算法是给定问题的最优解决方案。但是，有一些问题本质上就是并行的，因此采用并行实现时所需的计算步骤就会比串行算法减少很多。Amdah1定律还有更大的缺陷是关于问题规模的假设。Amdahl 定律假设在处理器核数量增长的时候，问题的规模保持不变，这在大多数情况下不成立。一般来讲，当给予更多计算资源的时候，问题规模都会随之增大以适应资源规模的扩大。对于很多问题来说，随着问题规模的增长，需要解决的并行部分比非并行部分（即串行部分）增长的更快速。因此，随着问题域增长，串行部分所占比例减少。

Gustafson定律的前提条件是假设串行化代码的规模是固定的，计算规模是随CPU核数增加而增加的。实际情况中，共享资源访问的计算量和程序的计算规模是成正比的，如果共享资源通过锁保护操作而变成串行化执行，那么串行化代码的规模将随程序规模的增加而线性增加，这样将导致不符合Gustafson定律的前提条件，而是符合Amdahl定律的前提条件。最终得出的加速比将是按照 Amdahl 定律计算出结果。无论采用 Amdahl 定律还是Gustafson 定律，在任何情况下，最小化串行代码都是良好的习惯。这两大定律的观点也都是正确的。不同之处在于你想要程序在既有工作量的前提下运行得更快，还是更快速地处理更大的工作量。不过实践表明程序越复杂，要解决的问题规模越大。

如何消除锁竞争造成的串行化执行就成了程序员需要解决的问题，下面看一下几种不同类型的锁竞争形式对加速比指标的具体影响。在锁竞争的情况下，任务粒度因子和锁粒度因子是影响加速比的重要因素之一，因此需要先理解任务粒度因子和锁粒度因子的概念。

2.1.1 任务粒度因子与锁粒度因子

在一个有锁保护操作的程序中，每个任务中的计算可以分为图2-4所示的几部分：

其中，ts表示锁内计算时间，大小由共享资源的操作时间决定，与共享资源类型有关，并且与程序员的程序设计有关；t1表示 Lock操作和Unlock操作耗费的时间，如果CPU核的速度固定，那么它为一常量；pt 表示锁外可并行计算部分耗费的时间，大小与具体的应用类型及程序员的分解有关。为了形象地表示出各段计算间的比例关系，引入两个概念：任务粒度因子和锁粒度因子。

1．任务粒度因子

任务粒度因子主要用来反映一个任务的计算量大小，由于t1是常量，因此把任务内的有效计算和t1的比值叫做任务粒度因子 tf，即

2．锁粒度因子

锁粒度因子反映了一个任务内锁操作的粒度关系，用锁内计算时间ts和t1的比值来表示锁粒度因子 kf，即

2.1.2 固定式锁竞争中的加速比分析

在一个固定式锁竞争情况中，由若干个同时创建的对等任务竞争同一把锁，在这种固定式竞争环境中，假设每个任务都执行一次锁内操作，锁竞争一定会发生并因锁竞争而导致任务排队串行执行锁操作及锁内计算。固定式锁竞争属于实际情况中的常见现象，比如使用OpenMP来创建任务，如果在任务中使用了锁操作，那么它就是一种固定式锁竞争。

固定式锁竞争的加速比如下：

当处理器的数量n→+∞时，有

式（2-7）表明，固定式锁竞争的加速比是有极限值的，它不能随着处理器数量的增加而增加。

2.1.3 随机锁竞争加速比分析

在实际情况中，除了固定式锁竞争情况外，锁竞争还有一种随机竞争的形式，在随机锁竞争中，各个对等任务运行锁计算的时间是随机的。比如在服务器软件中，各个任务创建后，每个任务都在循环地做同样的计算，而各个任务的运行时间受网络客户端的影响，其处理时间不是固定的，而是随机的，这样将导致各个任务在竞争同一把锁时出现随机竞争现象。随机锁竞争情况下的加速比期望值如下：

令i个线程运行于锁外的概率为 Q(k,n) = i ，其中 为每个线程运行于锁外的概率，则有

式（2-8）计算出的加速比是期望值，在最坏情况下，实际上有(1 )k−p 的概率所有的任务都处于锁内计算状态，此时只有一个任务在运行，因此加速比为1，如果考虑锁计算开销，那么加速比为：

即最坏情况下的加速比将小于1。

2.1.4 分布式锁竞争的加速比分析

在一个分布式锁竞争环境中，有多个任务竞争多把不同的锁，不妨设有m个任务竞争r把不同的锁。如果任务数量m足够大的话，那么运行锁外计算的任务数量将会大于CPU核数，导致每个CPU核上都有任务在运行，此时的多CPU效率为 ，因此有，即：

可以看出这种情况下的加速比和CPU核数成正比，并和任务粒度因子有关，任务粒度因子越大，那么加速比也越大。此时加速比和锁粒度没有任何关系。这是分布式锁竞争和普通锁竞争的最大区别。

如果任务数量m不够大，运行锁外计算的任务数量小于CPU核数，那么需要计算有多少个进行锁竞争的任务在运行。为方便起见，令k为运行锁内计算的任务数量，那么这k个任务在竞争r把锁，假设有1把锁上有任务在竞争，可以求出q的期望值为：

实际上q表示了这些锁竞争的任务中，最多可能有q个任务在运行，最大运行锁内计算的任务数为没有运行锁外计算的CPU核数。

如果q小于n−m+k，那么有m−k个任务在运行锁外计算，有q个任务在运行q把锁上的锁内计算，此时多CPU效率为，求出加速比的期望值为：

式（2-11）表明此时的加速比的大小完全取决于q的大小，而q的大小与任务数k和锁的数量 r 有关，r 保持不变情况下，任务数愈大，则q愈大；任务数 k 保持不变情况下，r愈大则q愈大。

如果q大于等于n−m+k，那么将至少有n个任务在运行，所有的CPU核都处于运行状态，考虑加锁解锁增加的开销后，多 CPU 效率期望值为 ，可以求出此时的加速比期望值为：

所以在随机分布式锁竞争情况下，加速比只和4个因素有关：CPU核数、任务粒度因子、任务数量、锁的数量。只要选取合适的任务数量和锁的数量，那么就可以使加速比和CPU核数n成正比关系。

分布式锁竞争情况下，考虑一种最坏的情况，所有的任务都在运行锁内计算，此时可以计算出有 n 把以上的锁上有任务并且加速比达到 的概率为 。因而只要选择合适的任务数m，锁数量r，那么可以将概率q控制在一个比较大的值，这样在最坏情况下也不会出现问题。

以上三种锁竞争形式中，固定式锁竞争所得到的加速比是很糟糕的，和Amdahl定律相当；随机式锁竞争所得到的加速比比固定式好了许多，但最坏情况下仍然不容乐观。分布式锁竞争所得到的加速比是最好的，加速比和 CPU 核数成正比，和 Gustafson 定律描述的相当。因此在多核系统中使用分布式锁竞争，可以取得和单核系统中多任务编程差不多的性能。分布式锁竞争形式将是多核编程的发展方向。

2.2 并行编程的基本概念

每个软件开发人员都不得不面对并行编程。以前在完成任务时，首先会考虑选择最佳算法，实现语言等。但现在必须首先考虑任务的内在并行性。而这反过来又会影响对算法和实现的抉择。如果将并行放在最后考虑，还不如不使用并行。实际上，并行是相当自然的思维方式，只是似乎开发人员并不常用这种方式。一旦关注并且使用并行编程，那么便会思考并行。那时，将会首先思考整个项目的并行性，然后才考虑如何进行编程。应该怎样来实现程序并行呢？

2.2.1 数据并行

如图2-5所示的是一种很典型的数据并行示例：拥有大量的数据，并且这些数据都采取同一种操作来转换每一块数据。

图2-5表示，把数据集中的每一个英文小写字母均转换成相对应的英文大写字母。这个很简单的示例展示了要操作的数据集和同时应用于每个元素的转换操作。

2.2.2 任务并行

数据并行往往最终受限于要处理的数据量。现实中，CPU 拥有多少核心数也无法应付巨大的数据增长，即使 CPU 可以乱序并行执行多个指令。而且很多时候瓶颈并不在 CPU处，内存和缓存也有着重要的影响，甚至可以让GPU来参与处理。这时就要转向任务并行了，如图2-6所示。

任务并行意味着拥有大量不同的、独立的、由共享数据联系起来的任务。图2-6表示在相同的数据集上应用一些数学运算规则来获取其值，而这些值都相对独立。换句话说，可以单独计算其值，而不受其他计算的影响。

2.2.3 合并数据和任务并行

纯粹的任务并行要比纯粹的数据并行难的多。很多时候，当发现任务并行时，它同时也是一种特定的管道/流水线。许多独立的任务需要应用到数据流上。每一项都会被阶段性处理，正如图2-7中从 a 到 A 所展示的那样。

假如使用管道/流水线，数据流A可以被处理得更快。因为不同项的不同阶段可以并行处理。管道/流水线比其他处理方式更高级：它可以更改数据或者针对选定的项跳过某些步骤。汽车工厂的装配线就是一个管道/流水线的典型示例，如图2-8所示。

2.2.4 混合方案

考虑一下在信纸上写完你的浓浓情思之后，该如何寄信。大概需要六个步骤：折叠信纸、把信纸装入信封、密封封口、在信封正面写上地址、贴上邮票、投递。 如果现在你有六个人来完成大量的信封装填投递任务，你会如何安排？很自然的反应是按照上述六个步骤，每个阶段安排一人来完成它，如图2-9所示。

参照前面所讲的数据并行，或许应该把这六个人单独分开，每个人独自来完成所有步骤，如图2-10所示。

如果每个人在不同的位置工作，并且彼此相隔甚远，那么图2-10很显然是个正确的选择。这就是所谓的“粗粒度并行”，因为彼此任务互动很少（他们只不过取走信封时会在一起，然后转身就去做工作了，甚至包括投递）。此外，如图2-9所示的是“细粒度并行”，这是因为他们时常交互（每一个信封都会由上一个人传过来，然后再传给下一个人）。

程序不可能完全符合现实，但有时候足够接近也很有用。在这个示例中，或许第四个步骤（在信封正面写上地址）会让三个人保持足够忙碌，但前两个步骤和后两个步骤仅仅需要一个人就可以赶上了。图2-11表明了每个步骤的工作量，而图2-12则说明了一个真正的数据并行和任务并行的混合方案。

2.2.5 实现并行

上述示例可以用下面两个步骤来简单的表达：

（1）分配任务（围绕着工作量来自由支配）；

（2）一开始每人做六个任务的其中一部分，但乐于分割既定任务以便两个或多个人一块工作。

那应该如何并行编程呢？首先，思考程序哪些地方可以并行；其次，根据实际情况进行并行分解。如果幸运的话，可能只碰到数据并行，这个就很简单了，比如并行迭代。当碰到复杂的情况时，依据上述分类来逐一比对，最麻烦也不过是混合方案而已。请尽可能使用硬件并行，这会大大消除使用锁机制同步的需要，而且也高效得多。

2.2.6 可伸缩性与加速比

可伸缩性是衡量应用程序加速比多少的尺度之一（注：加速比指应用程序串行化与并行化之间所花费时间之比，它表示并行化之后的效率提升结果）。2倍的加速比表明并行程序仅需要花费串行程序的一半时间。比如理想情况下，运行在单处理器上的程序花费30秒，而在双核机器上运行仅需花费15秒。总是期望运行在双核机器上的应用程序要比在单核上快得的多。同理，运行在四核机器上也要比在双核上快得多。这就好像以前当 CPU 换代升级时，随着主频提升，应用程序总是可以运行的更快。很不幸，大多数应用程序在步入多核时代后，性能不但没有提升，甚至有所降低。

假如增加更多的处理器核心数，而应用程序并没有获得额外的加速，则该应用程序不具有可伸缩性。如果强制使用另外的处理器核心，通常会造成性能下降。因为这时分布式和同步的开销开始凸显威力。那么应用程序到底有多少并行性呢？显然，这个问题取决于解决问题的多寡和发现并恰当利用并行算法的能力。先前大部分讨论都围绕着如何在昂贵和稀有的并行计算机上编写高性能程序。随着多核处理器时代的到来，许多方面已经发生变化。

2.3 本章小结

本章的主要内容在于介绍并行编程的评价方法和并行编程的基本模型，其中数据并行编程模型和任务并行编程模型是本书的重点。