C H— _

第 5 章

_ A P T E R 5

优化程序性能 #

写程序最主要的目标就是使它在所有可能的情况下都正确工作。一个运行得很快但是给出错误结果的程序没有任何用处。程序员必须写出清晰简洁的代码，这样做不仅是为了 自己能够看懂代码，也是为了在检查代码和今后需要修改代码时，其他人能够读懂和理解 代码。

另一方面，在很多情况下，让程序运行得快也是一个重要的考虑因素。如果一个程序要实时地处理视频帧或者网络包，一个运行得很慢的程序就不能提供所需的功能。当一个 计算任务的 计算量非常 大，需 要执行数日或者数周， 那么哪怕只是让它运行得快 20 %也会产生重大的影响。本章会探讨如何使用几种不同类型的程序优化技术，使程序运行得 更快。

编写高效程序需要做到以下几点：第一，我们必须选择一组适当的算法和数据结构。 第二，我们必须编写出编译器能够有效优化以转换成高效可执行代码的源代码。对于这第 二点，理解优化编译器的能力和局限性是很重要的。编写程序方式中看上去只是一点小小 的变动，都 会引起编译器优化方式很大的变化。有些编程语言比其他语言容易优化。C 语言的有些特性，例如执行指针运算和强制类型转换的能力，使得编译器很难对它进行优 化。程序员经常能够以一种使编译器更容易产生高效代码的方式来编写他们的程序。第三 项技术针对处理运算量特别大的计算，将一个任务分成多个部分，这些部分可以在多核和 多处理器的 某种组合上并行地计算。我们会 把这种性能改进的方法推迟到第 12 章中去讲。即使是要利用并行性，每个并行的线程都以最高性能执行也是非常重要的，所以无论如何 本章所讲的内容也还是有意义的。

在程序开发和优化的过程中，我们必须考虑代码使用的方式，以及影响它的关键因

素。通常，程序员必须在实现和维护程序的简单性与它的运行速度之间做出权衡。在算法 级上，几分钟就能编写一个简单的插入排序，而一个高效的排序算法程序可能需要一天或更长的时间来实现和优化。在代码级上，许多低级别的优化往往会降低程序的可读性和模块性，使得程序容易出错，并且更难以修改或扩展。对于在性能重要的环境中反复执行的代码，进行大量的优化会比较合适。一个挑战就是尽管做了大量的变化，但还是要维护代码一定程度的简洁和可读性。

我们描述许多提高代码性能的技术。理想的情况是，编译器能够接受我们编写的任何代码，并产生尽可能高效的、具有指定行为的机器级程序。现代编译器采用了复杂的分析 和优化形式，而且变得越来越好。然而，即使是最好的编译器也受到妨碍优化的因素(optimization blocker ) 的阻碍， 妨碍优化的因素就是程序行为中那些严重依赖于执行环境的方面。程序员必须编写容易优化的代码，以帮助编译器。

程序优化的第一步就是消除不必要的工作，让代码尽可能有效地执行所期望的任务。这包括消除不必要的函数调用、条件测试和内存引用。这些优化不依赖于目标机器的任何 具体属性。

为了使程序性能最大化，程序员和编译器都需要一个目标机器的模型，指明如何处理指

令，以 及各个操作的时序特性。例如， 编译器必须知道时序信息， 才能够确定是用一条乘法指令， 还是用移位和加法的某种组合 。现代计算机用复杂的技术来处理机器级程序， 并行地执行许多指令，执行顺序还可能不同 千它们在程序中出现的顺序。程序员必须理解这些处理器是如何工作的， 从而调整他们的程序以获得最大的 速度。基千 Intel 和 AMD 处理器最近的设计 ， 我们提出了这种机器的一个高级模型。我们 还设计了一种图形数据流( data-flow) 表示法， 可以使处理器对指令的执行 形象化， 我们还可以 利用它预测程序的性能。

了解了处理器的运作，我们就可以进行程序优化的第二步，利用处理器提供的指令级并 行(inst ru ction-level para llelism ) 能力， 同时执行多条指令。我们会讲述儿个对程序的 变化，降低一个计算的不同部分之间的数据相关， 增加并行度， 这样就可以同时执行这些 部分了。

我们以对优化 大型程序的问 题的讨论来结束这一章。我们描述了代码剖析 程序 ( profi­ le r ) 的使用 ， 代码剖析程序是测量程序各个部分性能的工具。这种分析能够帮助找到代码中低效率的地方，并且确定程序中 我们应该 着重优化的部分。

在本章的描述中，我们使代码优化看起来像按照某种特殊顺序，对代码进行一系列转 换的简单线性过程。实际上， 这项工作远非这么简单。需要相当多的试错法试验。当我们进行到后面的优化阶段时， 尤其是这样， 到那时 ， 看上去很 小的变化 会导致性能上很大的变化。相反， 一些看上去很有希望的技术被证明是 无效的。正如后面的例子中会看到的那样， 要确切解释为什么某段 代码序列具有特定的执行时间， 是很困难的。性能可能依赖于处理器设计的许多细节特性 ，而 对此我们所知甚少。这也是 为什 么要尝试各种技术的变形和组合的 另一个原因。

研究程序的汇编代码表示是理解编译楛以及产生的代码会如何运行的最有效手段之 一。仔细研究内 循环的代码是一个很好的开端，识别 出降低性能的属性， 例如过多的内存引 用 和对寄存器使用不当。从汇编代码开始 ， 我们还可以预测什么操作会并行执行， 以及它们会如何使用处理器资源。正如我们会看到的， 常常通过 确认关键路径( crit ica l pa t h) 来决定执行一个循环所需要的时间（或者说， 至少是一个时间下 界）。所谓关键路径是在循环的 反复执行过程中形成的数据相关链。然后 ， 我们会回过头来 修改源代码 ， 试着控制编译器使之产生更有效率的实现。

大多数编译器， 包括 GCC, 一直都在更新和改进， 特别是在优化能力方面。一个很有用的策略是只重写程序到 编译器由此就能产生有效代码所需要的程度就好了。这样，能尽量避免损 害代码的可读性 、模块性和可移植性， 就好像我们使用的是具有最低能力的编译器。同样， 通过测量值和检查生成的 汇编代码 ， 反复修改源代 码和分析它的性能是很有帮助的。

对千新手程序员来说，不断修改源代码，试图欺骗编译器产生有效的代码，看起来很 奇怪 ， 但这确实是编写很多高性能程序的方式。比较千另 一种方法－ 用汇编语言写代码， 这种间 接的方法具 有的优点是：虽 然性能不一定是最好的， 但得到的代码仍然能够在其他机器上运行。

5. 1 优化编译器的能力和局限性 #

现代编译器运用复杂精细的算法来确定一个程序中计算的是什么值，以及它们是被如 何使用的。然后会利用一些机会来简化表达式 ， 在几个不同的地方使用同一个计算， 以及降低一个给定的计算必须被执行的次数。大多数编译器， 包括 GCC, 向用户提供了一些对它们所使用的 优化的 控制。就像在第 3 章中讨论过的， 最简单的控制就是指定优化级

别。例如，以 命 令 行 选项 " - og" 调用 GCC 是让 GCC 使用一组基本的优化。以选项 " -

01" 或更高（如 " - 0 2" 或 " - 0 3" ) 调用 GCC 会让它使用更大翟的优化。这样做可以进一步提高程序的性能，但是也可能增加程序的规模，也可能使标准的调试工具更难对程序进行 调试。我们的表述，虽 然 对 于 大 多 数 使 用 GCC 的软件项目来说， 优 化 级 别 - 0 2 已经成为了被接受的标准，但 是 还是主要考虑以优化级别- 0 1 编译出的代码。我们特意限制了优化级别，以 展 示写 C 语言函数的不同方法如何影响编译器产生代码的效率。我们会发现可以写出的 C 代码， 即 使 用 - 0 1 选项编译得到的性能，也 比用 可能的最高的优化等级编译一个更原始的 版本得到的性能好。

编译器必须很小心地对程序只使用安全的优化，也就是说对于程序可能遇到的所有可 能的情况 ， 在 C 语言标准提供的保证之下，优 化 后 得 到 的 程 序 和 未 优 化 的 版本有一样的行为。限制编译器只进行安全的优化，消除了造成不希望的运行时行为的一些可能的原因， 但是这也意 味着程序员 必须花费 更大的力气写出编译器能够将之转换成有效机器代码的程序。为了理 解决定一种程序转换是否安全的难度，让 我们来看看下面这两个过程：

1 void twiddle1(long *xp, long *yp)

2 {

3 *XP += *yp;

4 *XP += *yp;

5 }

6

7 void twiddle2(long *XP, long *yp)

8 {

9 *XP += 2* *yp;

10 }

乍一看，这 两个过程似乎有相同的行为。它们都是将存储在由指针 y p 指示的位置处的值两次加 到指针 x p 指示的位置处的值。另一方面， 函 数 t wi d d l e 2 效 率 更 高 一 些 。 它只要求 3 次内存引用（读*x p , 读* y p , 写*x p ) , 而 t wi d d l e l 需 要 6 次( 2 次读*x p , 2 次读

*yp , 2 次写*x p ) 。因此， 如 果 要 编 译 器 编 译 过程 t wi d d l e 1 , 我们会认为基于 t wi d d l e 2

执行的计算能产生更有效的代码。

不过， 考虑 x p 等于 yp 的 清况 。 此 时 ， 函 数 t wi d d l e l 会执行下面的计算：

结果是 x p 的值增加 4 倍。另一方面， 函数 t wi d d l e 2 会 执 行 下 面的计算：

9 *XP += 2* *xp; I* Triple value at xp *I

结果是 xp 的值增加 3 倍。编译器不知道 t wi dd l e l 会如何被调用， 因 此它必须假设参数 xp

和 yp 可能会相等。因此， 它不 能 产 生 t wi dd l e 2 风格的代码作为 t wi dd l e l 的 优 化 版 本 。

这种两个指针可能指向同一个内存位置的情况称为内存别 名使 用 ( m e m o r y a li a s ing ) 。在只执行安全的优化中， 编 译 器 必 须 假 设 不 同 的 指 针可能会指向内存中同一个位置。再看一个例子， 对千一个使用指针变量 p 和 q 的程序， 考虑下面的代码序列：

X = 1000; y = 3000;

t l 的计算值依赖于指针 p 和 q 是否指向内存中同一个位置 如果不是， t l 就等于

3000, 但如果是， t1 就等于 1000 。这造成了一个主要的妨碍优化的因素， 这 也 是 可能严重限制编译器产生优化代码机会的程序的一个方面。如果编译器不能确定两个指针是否指 向 同 一 个 位 置 ， 就必 须 假设 什 么情 况都有可能，这 就 限 制了可能的优化策略。

沁囡 练习题 5. 1 下面的问题说明了内存别名使用可能会导致意想不到的程序行为的方式。 考虑下面这 个交换 两个 值的过程：

I* Swap value x at xp with value y at yp *I void swap(long *XP, long *yp)

｛

*XP = *XP + *yp;

*YP = *XP - *yp;

*XP = *XP - *yp;

如果调用这个过程 时 xp 等 于 yp , 会有什么样的效果？

第二个妨碍优化的因素是函数调用。作为一个示例， 考虑下面这两个过程：

long f();

long func10 {

return f () + f () + f () + f () ;

｝

long func2() { return 4*f () ;

｝

最初看上去两个过程计算的都是相同的结果， 但 是 f u n c 2 只 调 用 f 一 次 ， 而 fu ncl

调用 f 四次 。以 f u nc l 作为源代码时，会 很 想 产 生 f u n c 2 风 格 的 代 码 。不 过 ，考 虑下 面 f 的代码：

long counter= O;

long f O {

return counter++;

｝

这个函数有个副作用一 它 修 改 了 全 局 程序状态的一部分。改变调用它的次数会改变程 序 的 行 为。特别地， 假设开始时全局变最 c oun t er 都设詈为 o, 对 f u n c l 的调用会返回

0 + 1 + 2 + 3 = 6 , 而对 f un c 2 的调用会返回 4 • O= O。

大 多 数 编译器不会试图判断一个函数是否没有副作用， 如果没有，就 可能被优化成像

f unc 2 中的样 子 。 相反， 编译器会假设最糟的情况 ，并保持所有的 函数调用不 变。

田 日 用内联函数替换优化函数调用

包含 函 数 调用的 代码可以 用一个称为 内联 函数替 换 ( inli ne s ubstit ut ion , 或者简称S

“ 内联( in linin g ) " ) 的过程进行优化， 此时， 将函数调用替 换 为 函数体。例如 ， 我们可以通过替换掉对函数 f 的四次调用，展 开 f u n c l 的代码：

I* Result of inlining fin funcl *I long funclinO {

long t = counter++; I * +O * I

t += counter++; t += counter++; t += counter++; return t·，

I* +1 *I

I* +2 *I

I* +3 *I

这样的转换既减少了函数 调用的 开销，也 允许 对展开的代码做进一步优 化。例如， 编译器可以 统一 f unc li n 中对全 局变量 c ou nt e r 的更新，产 生这 个函数的一个优化版本：

I* Optimization of inlined code *I long func1opt () {

long t = 4 *counter+ 6;

counter+= 4; return t;

｝

对于这 个特定的函数 f 的定义， 上述代码忠实地 重现了 f u n c l 的行为。

GCC 的最近版本会尝试进行这种形式的优化，要 么是 被 用命 令 行 选项 " - f i n l i ne " 指示时 ，要 么是 使 用优 化等级- 01 或者更高的等级 时。遗憾的是， G CC 只 尝试在单个文件中定义的函数的内联。这就意味着它将无法应用于常见的情况，即一组库函数在一个 文件中被定义，却被其他文件内的函数所调用。

在某些情 况下， 最好能阻止编译 器执 行 内联替 换。一种情况是用符 号调试器来评估代码，比如 G DB, 如 3. 10. 2 节描 述的一样。如果一个函数调 用已经用内联替 换优化过 了，那 么任何对这个调用进行追踪或设置断点的尝试都会失败。还有一种情况是用代码剖析的方式来 评估程序 性能，如 5. 14. 1 节讨论的一样 。用内联替 换消除的 函数调用是无法被正确剖析的。

在各种编译 器中 ， 就 优 化 能 力 来 说 ， G CC 被认为是胜任的， 但 是 并 不 是 特 别 突 出 。它完成基本的优化，但是它不会对程序进行更加“有进取心的“编译器所做的那种激进变 换。因 此，使 用 G CC 的 程 序员 必 须 花费更多的精力，以 一 种 简 化 编译 器生成高效代码的任务的方式来编写程序。

5. 2 表示程序性能

我们引入度量标准每元素的周期数 ( C ycl es Per E le men t , CPE), 作为一种表示程序性能并指导我们改进代码的方法。CP E 这种度量标准帮助我们在更细节的级别上理解迭代程序的循环性能。这样的度量标准对执行重复计算的程序来说是很适当的，例如处理图像中的像素 ， 或是计算矩阵乘积中的元素。

处理器活动的顺序是由时钟控制的， 时 钟提供了某个频率的规律信号， 通常用千兆赫兹 CG H z) , 即十亿周期每秒来表示。例如， 当 表明一个系统有 " 4G H z" 处 理 器，这 表示处理器时 钟运行频率为每秒 4 X l 炉个 周 期 。 每个时钟周期的时间是时钟频率的倒数。通常

是以纳秒 ( nanoseco nd , 1 纳秒等于 1-0 g 秒 ）或 皮 秒 ( p icoseco nd , 1 皮秒等于 1-0 12 秒 ）为单

位的。 例如， 一个 4G H z 的时钟其周期为 o. 25 纳秒， 或 者 250 皮秒。从程序员的角度来看，用时 钟周 期 来 表示度量标准要比用纳秒或皮秒来表示有帮助得多。用时钟周期来表示， 度量值表示的是执行了多少条指令，而 不 是 时 钟 运行得有多快。

许多过程含有在一组元素上迭代的循环。例如，图 5 -1 中 的 函数 p s um l 和 p s um2 计 算的都是 一个长度为 n 的向量的前置和 ( prefi x s um ) 。对于向量 a = ( a。, a1 ’ … ， a . -1 〉， 前置和 p = ( p。, P1 , … ， P . - 1 〉定 义为

( 5. 1)

I* Compute prefix sum of vector a *I

2 void psum1(float a[] , float p[] , long n)

3 {

4 long i ;

5 p[O] = a [O] ;

6 for (i = 1; i < n ; i ++)

7 p[i] = p[i-1] + a [ i ] ;

8 }

9

10 voi d psum2(float a[], float p[J, long n)

11 {

12 long i;

13 p[O] = a[O];

14 for (i = 1; i < n- 1 ; i+=2) {

1. float mid_val = p [ i 一 1] + a [ i ] ;

2. p [ i ] = mid_val;

   17 p[i+1] = mid_val + a[i+1];

   18 }

3. I* For even n, finishr ema i n i ng e l em e n t * I

4. i f ( i < n )

   21 p[i] = p [ i 一 1] + a [i] ;

   22 }

图 5-1 前置和函数。这些函数 提供了 我们 如何表示程序性 能的示例

函数 p s u ml 每次迭代计 算结果向量的一个元素。第二个函数使用循环展 开( loo p un­ ro lling ) 的技术， 每次迭 代计算两个元素。本章后 面我们会探讨循环展开的好处。（关于分析和优化前 置和计算的内容请参见练习题 5. 11、5. 1 2 和家庭作业 5. 1 9。)

这样一个过程所需 要的时间可以用一个常数加 上一个与被处理元素个数成正比的因子来描述。例如，图 5- 2 是这两个函数需要的周期数关于 n 的取值范围图。使用最小二乘拟

2500

跺亟

。 20 40 60 80 100 120 140 160 180 200

元素

图 5-2 前置和函数的性能。两 条线的斜率表明 每元素的周期数 (CPE )的值

合(least squares fit) , 我们发现， p s uml 和 ps um2 的 运行时间（用时钟周期为单位）分别近似于等式 368 + 9. On 和 368 + 6. On 。 这 两 个 等 式 表 明 对 代 码 计 时 和初始化过程、准备循环以及完成过程的开销为 368 个周期加上每个元素 6. 0 或 9. 0 周期的线性因子。对千较大的

n 的值（比如说大千 200 ) , 运行时间就会主要由线性因子来决定。这些项中的系数称为每元素的 周期数（简称 CP E) 的有效值。注意，我 们更愿意用每个元素的周期数而不是每次循环的周期数来度量，这是因为像循环展开这样的技术使得我们能够用较少的循环完成计算，而

我们最终关心的是，对 于给定的向量长度，程 序运行的速度如何。我们将精力集中在减小计算的 CPE 上。根据这种度量标准， ps urn2 的 CPE 为 6. o, 优于 CPE 为 9. 0 的 p s uml 。

日 日 什么是最小二乘拟合

对于一 个数据点Cx 1 , Yi), …， （立 ， y . ) 的集合 ， 我们常常试图 画一条线， 它能最接近于这 些数 据代 表的 X- Y 趋势。使用最小二 乘拟合， 寻找一条形如 y = mx + b 的线， 使得下面这个误差度量最小：

E(m,b) = (mx1 +b - y;) 2

i - 1. n

将 E ( m , b) 分别对 m 和b 求导，把 两个 导数函数设置为 o, 进 行 推导就能得 出计 算 m 和

b 的算 法。

练习题 5. 2 在本章后面，我们会从一个函数开始，生成许多不同的变种，这些变种 保持函 数的 行为 ， 又具 有 不 同 的 性 能 特性。 对 于其中 三 个 变 种， 我 们 发现运行时 间

（以时钟周期为单位）可以用下面的函数近似地估计： 版本 1 : 60+35n

版本 2 : 136+4n

版本 3 : 157+1. 25n

每个版 本在 n 取什 么值 时是 三个版 本中最快的？ 记住， n 总是 整数。

1. 3 程序示例

为了说明一个抽象的程序是如何被系统

地转换成更有效的代码的，我们将使用一个 基于图 5-3 所示向量数据结构的运行示例。向

d ::三 声酮

囊由两个内存块表示：头部和数据数组。头部是一个声明如下的结构：

图 5-3

向扯的抽象数据类型。向量由头信息

加上指定长度的数组来表示

codeloptlvec.h

I* Create abstract data type for vector *I typedef struct {

long len; data_t *data;

} vec_rec, *vec_ptr;

code/opt/vec.h

这个声明用 d a t a _t 来表示基本元素的数据类型。在测试中， 我们度量代码对于整数( C 语言的 i n t 和 l o ng ) 和浮点数( C 语言的 fl oa t 和 doub l e ) 数据的性能。为此， 我们会分别为不同的类型声明编译和运行程序，就 像 下 面这个例子对数据类型 l o ng 一样：

typedef long data_t;

我们还会分配一个 l e n 个 d a t a _ t 类型对象的数组，来 存 放 实 际 的 向 量 元 素。

图 5-4 给出的是一些生成向扯、访问向量元素以及确定向扯长度的基本过程。一个值得 注意的重要特性是向量访问程序 g e t _ ve c _ e l e me n 七， 它 会对每个向量引用进行边界检查。这段代码类似于许多其他语言（包括J a va ) 所使用的数组表示法。边界 检查降低了程序出错的机会，但是它也会减缓程序的执行。

code/optlvec.c

I* Create vector of specified length *I

2 vec_ptr new_vec (long len)

3 {

4 I* Allocate header structure *I

5 vec_ptr result= (vec_ptr) malloc(sizeof(vec_rec));

6 data_t *data = NULL;

7 if (!result)

8 return NULL; I* Couldn’t allocate storage *I

9 result->len = len;

1. I* Allocate array *I

2. if (len > 0) {

3. data = (data_t *)calloc(len, sizeof(data_t));

4. if (!data) {

   14 free((void *) result);

   15 return NULL; I* Couldn’t allocate storage *I

   16 }

   17 }

   18 I* Data will either be NULL or allocated array *I

   19 result->data = data;

   20 return result;

   21 }

   22

   23 f*

5. * Retrieve vector element and store at dest.

6. * Return O (out of bounds) or 1 (successful)

7. *I

   27 int get_vec_element(vec_ptr v, long index, data_t *dest)

   28 {

8. if (index < 0 11 index >= v->len)

9. return O;

10. *dest = v->data[index];

11. return 1;

    33 }

    34

12. I* Return length of vector *I

13. long vec_length(vec_ptr v)

    37 {

    38 return v->len;

    39 }

code/otp/vec.c

图 -5 4 向量抽象数据类型的实现。在实际 程序中 ， 数据类型 da t a_t 被声明为

耳 北、 l ong 、 fl oat 或 doub l e

作为一个优化示例， 考虑图 5-5 中所示的代码， 它使用某种运算， 将一个向量中所有的元素合并 成一个值。通过 使用编译时常数 IDEN T 和 OP 的不同定义， 这段代码 可以重编译成对数据执行不同的运算。特别地，使用声明：

#define !DENT 0

#define OP +

它对向量的元素求和。使用声明：

#define !DENT 1

#define OP *

它计算的 是向量元素的乘积。

I* Implementation with maximum use of data abstraction *I void combinel(vec_ptr v, data_t *dest)

｛

long i;

*dest = !DENT;

for (i = O; i < vec_length(v); i++) { data_t val;

get_vec_element(v, i, &val);

*dest = *dest OP val;

｝

图 5-5 合并运算 的初始实 现。使用基本元素 IDENT 和合 并运算 OP 的不同声明， 我们可以测量该函数对不同运算的性能

在我们的讲述中 ， 我们会对这段代码进行一系列的 变化， 写出这个合并 函数的不同版本。为了评估性能变化， 我们会在一个具 有 Intel Core i7 H as well 处理器的机器上测量这些函数的

CPE性能， 这个机器称为参考机。3.1 节中给出了一些有关这个处理器的特性。这些 测量值刻画的是程序在某个特定的机器上的性能，所以在其他机器和编译器组合中不保证有同等的性能。 不过，我们 把这些结果与许多不同编译器／处理器组合上的结果做了比较， 发现也非常相似。

我们会进行一组变换，发现有很多只能带来很小的性能提高，而其他的能带来更巨大的效果。确定该使用哪 些变换组合确实是编写快速代码的 ＂糜术( black a r t ) " 。有些不能提供可测量的好处的组合确实是无效的，然而有些组合是很重要的，它们使编译器能够进 一步优化。根据我们的经验，最好的方法是实验加上分析：反复地尝试不同的方法，进行 测最，并检查汇编代码表示以确定底层的性能瓶颈。

作为一个起点 ，下 表给出的是 c omb i n e l 的 CPE 度量值，它 运行在我们的参考机上， 尝试了操作（加法或乘法）和数据类型（长整数和双精度浮点数）的不同组合。使用多个不同 的程序，我 们的实验显示 32 位整数操作和 64 位整数操 作有相同的性能，除 了 涉及除法操作的代码 之外。同样， 对于操作单精度和双精度浮点数据的程序 ， 其性能也是相同的。因此在表中 ， 我们将 只给出整数数 据和浮点数据各自的结 果。

函数 方法

整数 浮点数

combinel combinel

抽象的未优化的抽象的- 01

＊

20.02

10. 12

＋

19. 98

10. 17

＊

20. 18

11. 14

可以看到测量值 有 些 不 太 精 确。 对 于 整 数 求 和 的 CPE 数 更 像 是 23. 00 , 而不是

22. 68; 对千整数乘积的 CPE 数则是 20. 0 而非 20. 0 2。我们不会 ＂捏造“ 数据让它们看起来好看一点儿，只 是 给出了实际获得的测量值。有很多因素会使得可靠地测量某段代码序列 需 要 的 精 确 周 期 数 这个任务变得复杂。检查这些数字时，在 头 脑 里 把 结 果 向 上 或者向下取整几百分之一个时钟周期会很有帮助。

未经优化的代码是从 C 语言代码到机器代码的直接翻译 ， 通常效率明显较低。简单地使 用 命 令 行 选 项 " - 0 1" , 就会进行一些基本的优化。正如可以看到的，程序员不需要做什么 ，就 会 显 著 地提高程序性能—— 超过两个数量级。通常，养 成 至少使用这个级别优化的习 惯 是 很 好 的 。（使 用 - Og 优化级 别 能得到相似的性能结果。）在剩下的测试中， 我们使用

- 0 1 和 - 0 2 级 别 的 优 化来 生成 和测量程序。

4 消除循环的低效率 #

可以观察到， 过程 c omb i n e l 调用 函 数 v e c —l e n g t h 作 为 f or 循环的测试条件，如图 5 - 5 所 示。回想关于如何将含有循环的代码翻译成机器级程序的讨论（见3. 6. 7 节），每次 循 环 迭 代时都必须对测试条件求值。另一方面，向 量的长度并不会随着循环的进行而改变 。因 此 ， 只需 计 算 一 次 向量 的 长 度，然 后 在 我们的测试条件中都使用这个值。

图 5-6 是一个修改了的版本， 称为 c ombi n e 2 , 它在开始时调用 ve c _ l e ng t h , 并将结果 赋 值 给局部变量 l e n g t h。对千某些数据类型和操作， 这个变换明显地影响了某些数据类 型 和操作的整体 性能 ，对 千其他的则只有很小甚至没有影响。无论是哪种情况，都 需要这种变换来消除这个低效率，这有可能成为尝试进一步优化时的瓶颈。

1. I* Move call to vec_length out of loop *I

   1. void combine2(vec_ptr v, data_t *dest)

      3 {

2. long i;

3. long length= vec_length(v);

   6

   7 *dest = IDENT;

   8 for (i = O; i < length; i++) {

4. data_t val;

5. get_vec_element(v, i ,. &val);

6. *dest = *dest OP val; 12 }

   13 }

图 5-6 改进循环测试的效率。通过把对 ve c _l e ngt h 的 调用移 出循环测试， 我们不 再需要每次迭代时都执行这个函数

这个 优 化 是 一 类常见的优化的一个例子，称 为代码移动( co d e m o t io n ) 。这类优化包括识 别 要 执 行 多 次（例 如在循环里）但是计算结果不会改变的计算。因而可以将计算移动到代码 前 面不会被多次求值的部分。在本例中， 我们将对 v e c _ l e n g t h 的调用从循环内部移动

到循环的前面。

优化编译器会试着进行代码移动。不幸的是，就像前面讨论过的那样，对于会改变在 哪里调用函数或调用多少次的变换，编译器通常会非常小心。它们不能可靠地发现一个函 数是否会 有副作用， 因而假设函数会有副作用。例如， 如果 v e c _ l e n g t h 有某种副作用， 那么 c o mbi n e l 和 c o mbi n e 2 可能就会有不同的行为。为了改进代码， 程序员必须经常帮助编译器显式地完成代码的移动。

举一个 c ombi n e l 中看到的循环低效率的极端例子， 考虑图 5-7 中所示的过程 l o w­ e r l 。这个过程模仿几个学生的函数设计， 他们的函数是作为一个网络编程项目的一部分交上来 的。这个过程的 目的是将一个字符串中所有大写字母转换成小写字母。这个大小写转换涉 及将 " A" 到 " z" 范围内的字符转换成 " a" 到 " z" 范围内的字符。

I* Convert string to lowercase: slow *I void lower1(char *s)

｛

long i;

for (i

7 if

8

9

10

= O; i <

(s [i] >=

s (i] -=

strlen(s); i++)

I A’&& s [i] <= I z I)

(‘A’-‘a’);

1. I*Convert string to lowercase: faster *I

2. void lower2(char *s)

   13 ｛

   14 long i;

   15 long len = strlen(s);

   16

3. for (i

4. if

   19

   20

   21

   = O; i < len; i++) (s[i] >=‘A’&& s[i] <= s [i] -= (‘A’-‘a’) ;

I Z’)

1. I* Sample implementation of library function strlen *I

2. I* Compute length of string *I

3. size_t strlen(const char *s)

   25 ｛

   26 long length= O;

   27 while (*s !=’\0’) {

   28 s++;

   29 length++;

   30 ｝

   31 return length;

   32 ｝

图5-7 小写字母转换函数 。两个过程的性能差别很大

对库函数 s tr l e n 的调用是 l o wer l 的循环测试的一部分。虽 然 s tr l e n 通常是用特殊的 x86 字符串处 理指令来实现的， 但是它的整体执行也类似于图 5- 7 中给出的这个简单版本。因为 C 语言中的字符串是以 n u l l 结尾的字符序列， s tr l e n 必 须一步一步地检查这

个序列，直 到遇到 n u l l 字符。对于一个长度为 n 的字符串， s tr l e n 所用的时间与 n 成正比。因为对 l o wer l 的 n 次迭代的每一次 都会调用 s tr l e n , 所以 l ower l 的整 体运行时间是字符串长度的二 次项， 正比千 n勹

如图 5-8 所示（使用s tr l e n 的库版本）， 这个函数对各种长度的字符串的实际测量值证实了上述分析。l o wer l 的运行时间曲线图随着字符串 长度的增 加上升得很陡峭（图5-8a)。图 5- 8 b 展示了 7 个不同长度字符串的运行时间（与曲线图中所示的有所不同）， 每个长度都是 2 的幕。可以观察到， 对于 l o we r l 来说， 字符串长度每增 加一倍，运 行时间都会变为原来的 4 倍。这很明显地表明运行时间是二次的。对于一个长度为 1 04 8 5 76 的字符串来说， l o wer l 需 要超过 1 7 分钟的 CPU 时间。

250

200

150

记 #

u 100

50

100 000 200 000 300 000

字符串长度

a )

字符串长度

400 000 500 000

lower2 0.0000 0.0001 0.0001 0.0003 0.0005 0.0010 0.0020

b)

图 5-8 小写字母转换函数的性能 比较。由 千循环结构 的效率比较低， 初始代码 l owe r l

的运行时间是二次项的 。修改过的代 码 l ower 2 的运行 时间是线性的

除了把对 s 七r l e n 的调用移出了循环以外，图 5 - 7 中所示的 l ower 2 与 l o wer l 是一样的。做 了这样的变化之后， 性能有了显著改善。对千一个长度为1 048 576 的字符串， 这个函数只需 要 2. 0 毫秒—— 比 l o wer l 快了 500 000 多倍。字符串长度每增加一倍， 运行时间也会增加一倍一 很显然运行时间是线性的。对于更长的字符串 ，运 行时间的改进会更大。

在理想 的世界里， 编译器会认出循 环测试中对 s tr l e n 的每次调用都会返回相同的结果， 因此应该能够把这个调用移出循环。这需要非 常成熟完善的分析， 因为 s tr l e n 会检查字符串的元素， 而随着 l o wer l 的 进行， 这些值会改变。编译器需要探查， 即使字符串中的字符发生了改变， 但是没有字符会从非 零变为零 ， 或是反过来 ，从 零变为非零 。即使是使用内联函数，这样的分析也远远超出了最成熟完善的编译器的能力，所以程序员必须 自已进行这样的变换。

这个示例说明了编程时一个常见的问题，一个看上去无足轻重的代码片断有隐藏的浙 近低效 率( as ym p to tic ine fficie ncy ) 。人们可不希望一个小写字母转换函数成为程序性能的限制因素。通常 ，会 在小数据集上测试和分析程序 ， 对此， l o wer l 的 性能是足够的。不过，当程序 最终部署好以 后， 过程完全可能 被应用到一个有 1 00 万个字符的串上。突然，

这段无危险的代码变成了一个主要的性能瓶颈。相 比较而言， l o wer 2 的性能对于任意长度的字符串来说都是足够的。大型编程项目中出现这样问题的故事比比皆是。一个有经验 的程序员工作的一部分就是避免引入这样的 渐近低效 率。

练习题 5. 3 考虑下面的函数：

long min(long x, long y) { return x < y? x : y; } long max(long x, long y) { return x < y? y : x; } void incr(long *xp, long v) { *XP += v; }

long square(long x) { return x*x; }

下面 三个代码片 断调 用这 些 函数 ：

A. for (i = min(x, y); i < max(x, y); incr(&i, 1)) t += square(i);

:, B. for (i = max(x, y) - 1; i >= min(x, y); incr(&i, -1))

t += square(i);

C. long low= min(x, y); long high= max(x, y);

for_ (i = low; i < high; incr(&i, 1)) t += square(i);

假设 x 等于 1 0 , 而 y 等于 1 0 0。填写下表 ，指 出在代 码片断 A C 中 4 个函数每 个被调用的次数：

5. 5··减·-少过.一 ·程— 调. . 用.

像我们看到过的那样，过程调用会带来开销，而且妨碍大多数形式的程序优化。从 cornbi n e 2 的代码（见图 5-6 ) 中我们可以 看出， 每次循环迭代都会调用 g e t _ v e c _ e l e me n t 来获取下 一个向量元素。对 每个向 量引用， 这个函数要把向批索引 i 与循环边界 做比较， 很明显 会造成低效 率。在处理任意的数组访问时，边 界检查可能 是个很有用的特性， 但是对 c omb i n e 2 代码的简单分析表明所有的引用都是合法的。

作为替代， 假设为我们的 抽象数据类型增加一个函数 g e t —v e c _ s 七ar t 。 这个函数返回

数组的起始地址， 如图 5-9 所示。然后就能写出此图中 c o mbi ne 3 所示的过程，其 内 循环里没有函 数调用。它没有用函数调用来获取每个向 量元素， 而是直接访问 数组。一个纯粹主义者可能 会说这种变换严重 损害了程序的模块 性。原则上来说， 向扯抽象数据类观的使用者甚至不应该需 要知道向批的内容是作为数组来 存储的， 而不是作为诸如链表之类的某种其他 数据结构来存储的。比较实际的程序员 会争论说这种变换是 获得高性能结果的必要步骤。

data_t *get_vec_start(vec_ptr v)

｛

return v->data;

｝

code/opt/vec.c

code/otplvec.c

I* Direct access to vector data *f void combine3(vec_ptr v, data_t *dest)

｛

long i;

long length= vec_length(v); data_t *data = get_vec_start(v);

*dest = IDENT;

for (i = O; i < length; i++) {

*dest = *dest OP data[i];

｝

｝

图5-9 消除循环中的 函数调用。结果代码没有显示性能 提升，但是 它有其他的优化

令人吃惊的是， 性能没有明显的提升。事实上 ， 整数求和的性能还略有下降。显然，内循环中的其他操作形成了瓶颈， 限制性能超过调用ge t _ve c _e l e me n t 。 我们还会再回到这 个函数（见5. 11. 2 节）， 看看为什么 c ombi ne 2 中反复的边界检查不会让性能更差 。而现在，我们 可以将这个转换视为一系列步骤中的一步， 这些步骤将最终产生显著的 性能提升。

5. 6 消除不必要的内存引用

c o mb i ne 3 的代码将合并运算 计算的值累积在指针 d e 江 指定的位置。通过检查编译出来的为内循环产生的汇编代码 ， 可以看出这个属性。在此我们给出数 据类型为 d o ubl e , 合并运算为乘法的 x8 6-64 代码：

Inner loop of combi ne3 . data_t = doubl e , OP=*

dest in r7. bx, data+i i n r7. dx, data+length in

. L17: l oop:

r7. ax

在这段循环代码中， 我们看到， 指针 d e s t 的地址存放在寄存器%r b x 中，它 还改变了代码， 将第 i 个数据元素的指针保存在寄存器%r d x 中， 注释中显示为 d a t a + i 。每次迭代， 这个指针都加 8。循环终止操作通过比较 这个指 针与保存在寄存器%r a x 中的数值来判断。我们可以看到每次迭代时，累积变量的数值都要从内存读出再写入到内存。这样的读 写很浪费 ， 因为每次迭代开始时从 d e s t 读出的值就是上次迭代最后写入的值。

我们能够消除这种不必要的内存读写，按 照图 5-1 0 中 c ombi n e 4 所示的方式重写代码。引入一个临时 变量 a c e , 它在循环中用来累积计算出来的值。只有在循环完成之后结果才存放在 d e s t 中。正如下面的汇编代码所示， 编译器现在可以用寄存器%x mm0 来保存

累积值。 与 c o mb i n e 3 中的循环相比， 我们将 每次迭代的内存操作从两次读和一次写减少到只需要一次读。

Inner loop of combi ne4 . data_t = double, OP = * ace in 7.xmmO, data+i i n 肛 dx, data+length in 7.rax

. L25: loop:

1. vmulsd (%rdx), %xmm0, %xmm0 Multiply ace by data[i]
2. addq $8, %rdx Increment data+i

cmpq jne

%rax, %rdx

.L25

Compare to data+length

If !=, goto loop

1. I* Accumulate result in local variable *I

   1. void combine4(vec_ptr v, data_t *dest)

      3 {

2. long i;

3. long length= vec_length(v);

4. data_t *data= get_vec_start(v);

5. data_t acc = IDENT;

   8

   9 for (i = O; i < length; i++) { 1o acc = acc OP data [i] ;

   11 }

   12 *dest = acc;

   13 }

图 5-10 把结果累积在临时变量中。将 累积值存放在局部变最 a c e ( 累积器 ( accumulator ) 的简写）中， 消除 了每次循环迭代中从内 存中读出并 将更新值写 回的需要

我们看到程序性能有了显著的提高，如下表所示：

所有的时间改进范围从 2. 2 X 到 5. ? X , 整数加法情况的时间 下降到了每元素只需 1. 27 个

时钟周期。

可能又有人会认为编译 器应该能够自动将图 5- 9 中所示的 c o mbi ne 3 的代码转换为在寄存器中累积那个值， 就像图 5-10 中所示的 c o mbi ne 4 的代码所做的那 样。然而实际上， 由于内存别名使用 ， 两个函数可能会有不同的行 为。例如，考虑整数数据，运算为乘法，标识元 素为 1 的 情况。设 v= [ 2, 3, 5] 是一个由3 个元素组成的向量， 考虑下面两个函数调用 ：

combine3(v, get_vec_start(v) + 2); combine4(v, get_vec_start(v) + 2);

也就是在向量最后一个元素和存放结果的目标之间创建一个别名。那么，这两个函数的执

行如下： #

567

正如前面讲到过的， c o mb i n e 3 将它的结果累积在目标位置中，在 本例中， 目 标位置就 是 向 量的最后一个元素。因此， 这个值首先被设置为 1’ 然 后 设 为 2 • 1 = 2 , 然后设为

1. • 2 = 6 。最后一次迭代中，这 个 值会乘以它自己 ，得 到最后结果 3 6 。对千 c o mb i n e 4 的情 况来说 ，直 到 最 后 向扯都保持不变，结 束之前， 最后一个元素会被设置为计算出来的值1 • 2 • 3 • 5 = 30 。

   当然， 我们说明 c o mb i n e 3 和 c o mb i n e 4 之间差别的例子是人为设计的。有人会说c o mb i n e 4 的 行为更加符合函数描述的意图。不幸的是， 编 译 器不能判断函数会在什么情况 下 被调用，以 及 程序员的本意可能是什么。取而代之， 在编译 c o mb i n e 3 时，保 守 的方法 是 不 断 地读和写内存， 即 使 这样做效率不太高。

   练习题 5 . 4 当 用 带 命令行 选 项 " - 0 2 " 的 GCC 来 编 译 c o 邧江 n e 3 时 ， 得 到 的 代 码

   CPE 性 能 远好于使用 - 0 1 时的 ：

由此得 到 的性能 与 c o mb i n e 4 相 当 ， 不 过对于整数 求和的情况除外， 虽 然 性能已经得到 了 显著 的提高 ， 但还是低于 c o mb i n e 4。 在 检查编译器产 生的 汇编代码 时，我们发现对内循 环的 一个有趣的 变 化：

Inner loop of combi ne3 . da t a _t = doub l e , OP = *·Compiled -02 dest in¾rbx, data+i in¾rdx, data+length in¾rax

Ace 皿 ml a t ed product in¾xmmO

把上 面的 代码 与用 优 化等级 1 产 生的 代码进行比较：

Inner loop of combi ne3 . data_t = double, OP = * . Compiled -01 des t in i.r bx, data+i i n 肛 dx, data+length in i.rax

我们 看 到 ， 除 了 指 令 顺 序 有 些 不 同 ， 唯 一 的 区 别 就 是 使 用 更 优 化 的 版 本 不 含有

vm o v s d 指令 ， 它 实现的是从 d e s t 指定的位置读 数据（第 2 行）。

1. 寄存器%x mm0 的角 色在 两个循环中有什 么不 同？

   1. 这个更优化的版本忠 实地实现 了 c o mb i n e 3 的 C 语言代码吗（包 括在 d e s t 和向量数据之间使用内存别名的时候）？

2. 解释为什么这个优化保持了期望的行为，或者给出一个例子说明它产生了与使用较少优化的代码不同的结果。

   使用了这最后的变换，至 此， 对于每个元素的计算， 都只需要 l. 25 ~ 5 个时钟周期。

   比起最开 始采用优化时的 9 ~ 11 个周期， 这是相当大的提高了。现在我们想看看是什么因素在制约着代码的性能，以及可以如何进一步提高。

   5. 7 理解现代处理器

   到目前为止，我们运用的优化都不依赖于目标机器的任何特性。这些优化只是简单 地降低了过程调用的开销，以及消除了一些重大的＂妨碍优化的因素＂，这些因素会给 优化编译器造成困难。随着试图进一步提高性能，必须考虑利用处理器微体系结构的优 化，也就是处理器用来执行指令的底层系统设计。要想充分提高性能，需要仔细分析程 序，同时代码的生成也要针对目标处理器进行调整。尽管如此，我们还是能够运用一些 基本的优化，在很大一类处理器上产生整体的性能提高。我们在这里公布的详细性能结 果，对其他机器不一定有同样的效果，但是操作和优化的通用原则对各种各样的机器都 适用。

   为了理解改进性能的方法，我们需要理解现代处理器的微体系结构。由于大扯的晶 体管可 以被集成 到一块芯片上，现 代微处理器采用 了复杂的硬件， 试图使程序性能最大化。带来的一个后果就是处理器的实际操作与通过观察机器级程序所察觉到的大相径 庭。在代码级上，看上去似乎是一次执行一条指令，每条指令都包括从寄存器或内存取 值，执行一个操作，并把结果存回到一个寄存器或内存位置。在实际的处理器中，是同时 对多条 指令求值的， 这个现象称为指令级并行。在某些设 计中，可 以有 100 或更多条指令在处理中。采用一些精细的机制来确保这种并行执行的行为，正好能获得机器级程序要求 的顺序语义模型的效果。现代微处理器取得的了不起的功绩之一是：它们采用复杂而奇异 的微处理器结构，其中，多条指令可以并行地执行，同时又呈现出一种简单的顺序执行指 令的表象。

   虽然现代微处理器的详细设计超出了本书讲授的范围，对这些微处理器运行的原则有一般性的了解就足够能够理解它们如何实现指令级并行。我们会发现两种下界描述了程序 的最大性能。当一系列操作 必 须按照严格顺序执行时， 就会 遇 到 延迟界限 ( latency

   bound), 因为在下一条指令开始之前，这条指令必须结束。当代码中的数据相关限制了处理器利用 指令级并行的能力时， 延迟界限能够限制程 序性能。吞吐量界限( t hro ug hput bound) 刻画了处理器功能单元的原始计算能 力。这个界限 是程序性能的终极限制。

3. 7. 1 整体操作

   图 5-11 是现代微处 理器的一个非常简单化的示意图。我们假想的处理器设计是不太严格地 基千近期的 In tel 处理器的结构。这些处理器在工业界称为超标 量 ( s uperscala r ) , 意思是它可以 在每个时钟周期执行多个操作， 而且是乱序的( o ut- of - or de r ) , 意思就是指令执行的顺序不一定要与它们在机器级 程序中的顺序一致。整个设计有两个主要部 分： 指令 控制 单元 (I ns t ru ct io n Control Unit, ICU) 和执行单元 ( E xecu t io n Unit, EU)。前者负责 从内存中读出指令序列，并根据这些指令序列生成一组针对程序数据的基本操作；而后者执行这 些操作。和第 4 章中研究过的按序( in- order ) 流水线相比，乱 序处理器需要更大、更复杂的硬件，但是它们能更好地达到更高的指令级并行度。

"

指令控制单元

:—————————•

1—- #

指令高速缓存

寄存器更新

，，

！，预测OK?

操作结果 地址I I地址

数据I I I数据

数据高速缓存

执行单元

图 5-11 一个乱序处 理器的框图。指令控制单元负责从内存中读出指令，并 产 生 一 系 列 基 本操作。然后执行单元完成这些操作，以及指出分支预测是否正确

ICU 从指令高速 缓存( ins tru ction cache) 中读取指令， 指令高速缓存是一个特殊的高速存储器，它 包含最近访问 的指令。通常， ICU 会在当前正在执行的指令很早之前取指， 这样它才有足够的时间对指令译码， 并把操作发送到 EU。不过， 一个问题是当程序遇到分支气讨， 程序有两个 可能的前进方向。一种可能会选择分支， 控制被传递到分支目标。另一种可能是，不选择分支，控制被传递到指令序列的下一条指令。现代处理器采用了一 种称为分支预测( bra nch prediction ) 的技术， 处理器会猜测是否会选择分支，同 时还预测分支的目标地址。使用投机执行( speculative execution ) 的技术， 处理器会开始取出位于它预测的分支会跳到的地方的指令，并对指令译码，甚至在它确定分支预测是否正确之前就 开始执行这些操作。如果过后确定分支预测错误，会将状态重新设置到分支点的状态，并 开始取出和执行另一个方向上的指令。标记为取指控制的块包括分支预测，以完成确定取 哪些指令的任务。

指令译码逻辑 接收实际的程序指令 ，并 将它们转换成一组基本操作（有时称为微操作）。每个这样的操作都完成某个简单的计算任务，例如两个数相加，从内存中读数据，或是向内 存写数据。对千具有复杂指令的 机器，比如 x86 处理器， 一条指令可以被译码成多个操作。关于指令如何被译码成操作序列的细节，不同的机器都会不同，这个信息可谓是高度机密。 幸运的是， 不需要知道某台机器实现的底层细节，我 们也能优化自己的程序。

e 术语“分支” 专指条件转移指令 。对处理器来说，其他可能 将控 制传送到多 个目的地址的 指令， 例如过程返回和间接跳转，带来的也是类似的挑战。

在一个典 型的 x86 实现中， 一条只对寄存器操作的指令， 例如

addq %rax,%rdx

会被转化成一个操作。另一方面，一条包括一个或者多个内存引用的指令，例如

addq %rax,8(%rdx)

会产生多 个操作， 把内存引用和算术运算分开。这条指 令会被译码成为三个操作： 一个操作从内存 中加载一 个值到处理器中， 一个操作将加载进来的值加上寄存器%r a x 中的值，而一个操作将结果存回到内存。这种译码逻辑对指令进行分解，允许任务在一组专门的硬 件单元之间进行分割。这些单元可以并行地执行多条指令的不同部分。

EU 接收来自取指单元的 操作。通常， 每个时钟周期会接收多个操作。这些操作会被分派到一组功能单元中，它们会执行实际的操作。这些功能单元专门用来处理不同类型的 操作。

读写内存是由 加载和存储单元实现的。加载单元 处理从内存读数据到处理器的操作。这个单元有一个加法器来完成地址计算。类似，存储单元处理从处理器写数据到内存的操 作。它也有 一个加法器来完成地址 计算。如图中所示，加载 和存储单元通过数据高速 缓存(data cache )来访问内存。数据高速缓存是一个高速存储 器， 存放着最近访问的数据值。

使用投机执行技术对操作求值，但是最终结果不会存放在程序寄存器或数据内存中， 直到处理器能 确定应该实际执行这些指令。分支操作被送到 E U , 不是确定分支该往哪里去，而是确定分 支预测是否正确。如果预测错误 ， E U 会丢弃分支点之后计算出来的结果。它还会发 信号给分支单元， 说预测是错误的， 并指出正 确的分支目的。在这种情况中，分支单元开始 在新的位置取指。如在 3. 6. 6 节中看到的， 这样的预测错 误会导致很大的性能开销。在可以取出新指令、译码和发送到执行单 元之前 ， 要花费一点时间。

图 5-11 说明不同的功能单元被设计来执行不同的操作。那些标记为执行“算术运算” 的单元通常是专门用来执行整数和浮点数操作的不同组合。随着时间的推移，在单个微处 理器芯片上能够集成的晶体管数量越来越多，后续的微处理器型号都增加了功能单元的数 量以及每个单元能执行的操作组合，还提升了每个单元的性能。由于不同程序间所要求的 操作变化很大，因此，算术运算单元被特意设计成能够执行各种不同的操作。比如，有些 程序也许会涉及整数操作，而其他则要求许多浮点操作。如果一个功能单元专门执行整数 操作，而另一个只能执行浮点操作，那么，这些程序就没有一个能够完全得到多个功能单 元带来的好处了。

举个例子 ， 我们的 In t el Core i7 H as well 参考机有 8 个功能单元， 编号为 0 7。下面

部分列出了每个单元的功能：

0: 整数运算、浮点乘、整数和浮点数除法、分支

1: 整数运算、浮点加、整数乘、浮点乘

2: 加载、地址计算

3: 加载、地址计算

4: 存储

5: 整数运算

6: 整数运算、分支

7: 存储、地址计算

在上面的列表中，“整数运算”是指基本的操作，比如加法、位级操作和移位。乘法

坎

和除法需要更多的专用资源。我们看到存储操作要两个功能单元 一个计算存储地址， 一个实际保存数据。5. 1 2 节将讨论存储（和加载）操作的机制。

我们可以看出功能单元的这 种组合具有同时 执行多个同类型操作的潜力。它有 4 个功能单元可以执行整数操作， 2 个单元能执行加载操作， 2 个单元能执行浮点乘法。稍后我们将看到这些资源对程序获得最大性能所带来的影响。

在 IC U 中， 退役单元 ( retirem e n t u nit ) 记录正在进行的处理，并 确保它遵守机器级程序的顺序语义。我们的图 中展示了一个寄存器文件 ，它 包含整数 、浮点数和最近的 SSE 和A V X 寄存器， 是退役单 元的一部分， 因为退役单 元控制这些 寄存器的更新。指令译码时， 关千指令的信息被放置在一个先进先出的队列中。这个信息会一直保持在队列中，直到发 生以下两个结果中的一个。首先，一旦一条指令的操作完成了，而且所有引起这条指令的 分支点也都被确认为预测正确， 那么这条指令就可以 退役 ( ret ired ) 了， 所有对程序寄存器的更新都可以被实际执行了。另一方面，如果引起该指令的某个分支点预测错误，这条指 令会被清空 ( fl us hed ) , 丢弃所有计算出来的结果。通过这种方法，预测错误就不会改变程序的状态了。

正如我们已经描述的那样，任何对程序寄存器的更新都只会在指令退役时才会发生， 只有在处理器能够确信导致这条指令的所有分支都预测正确了，才会这样做。为了加速一 条指令到另一条指令的结果的传送，许多此类信息是在执行单元之间交换的，即图中的

“操作结果”。 如图中的箭头所示， 执行单元可以直接将结果发送给彼此。这是 4. 5. 5 节中简单处理器设计中采用的数据转发技术的更复杂精细版本。

控制操作数在执行单元间传送的最常见的机制称为寄存 器重 命名( register renaming) 。当一条更新寄存器r 的指令译码时， 产生标记 t , 得到一个指向该操作结果的唯一的标识符。条目(r , t ) 被加入到一张表中，该表维护着每 个程序寄存器 r 与会更新该寄存器的操作的标记 t 之间的关联。当随后以寄存器 r 作为操作数的指令译码时， 发送到执行单元的操作会包含 t 作为操作数源的值。当某个执行单元完成第一个操作时， 会生成一 个结果( v , t )’ 指明标记为 t 的操作产生值 V。所有等待t 作为源的操作都能使用 v 作为源值， 这就是一种形式的数据转发。通过这种机制，值可以从一个操作直接转发到另一个操作，而不是写到寄存器文件再读出来，使得第二个操作能够在第一个操作完成后尽快开始。重命名表只包含关于有未进行写操作的寄存器条目。当一条被译码的指令需要寄存 器 r , 而又没有标记与这个寄存器相关联，那么可以直接从寄存器文件中获取这个操作数。有了寄存器重命名，即使只有在处理器确定了分支结果之后才能更新寄存器，也可以预测着执行操作的整个序列。

田 日 乱序处理的历史

乱序处理 最早是 在 1 964 年 Co nt ro l Da ta Cor pora t ion 的 6600 处理 器中实现的。指令｝ 由十个不同的功 能单元处理 ， 每个单元都 能独立地运 行。在那个 时候 ， 这种时钟 频率为 勺

l OM hz 的机 器被认为是科学计算最好的机器。

在 1 9 66 年， IB M 首先是在 IB M 360 / 91 上 实现了乱序处理，但 只是用来执行 浮点指令。在大约 25 年的时间 里， 乱序处理 都被认为是一项异乎寻常的 技术，只 在追求尽 可1

能高性能 的机器中使 用，直到 1 990 年 IBM 在 RS / 6000 系列 工作站中重新 引入 了 这项技术。这种设计成 为 了 IB M / M o t o ro la P o w erP C 系列 的基础， 1 9 93 年引入的 型号 601 , 它i

成为笫一 个使 用乱序 处理的 单芯片微处理 器。I nt el 在 1995 年的 P ent ium P ro 型号 中引入｝ 了乱序处理 ， P e nt i umP ro 的底 层微体系结构类似 于我们的 参考机 。 i

为

1. 7. 2 功能单元的性能

   图 5-1 2 提供了 I nt el Core i7 H as well 参考机的 一些算术运算的性能 ， 有的是测量出来的，有的是引用 In tel 的文献[ 49] 。这些时间对于其他处理器来说 也是具有代表性的。每个运算 都是由以下这些数值来刻画的： 一个是延迟(l a te ncy ) , 它表示完成运算所需要的总时间； 另一个是 发射时间 ( is s ue time), 它表示两个连续的同类型的运算之间需要的最小时钟周期 数； 还有一个 是容量( capacit y) , 它表示能够执行该运算的功能单元的数量。

图 5-12 参考机的操作的延迟、发射时间和容量特性。延迟表明执行实际运算所需要的时钟周期总数， 而发射时间表明两次运算之间间隔的最小周期数。容最表明同时能发射多少个这样的操作。除法 需要的时间依赖于数据值

我们看到 ， 从整数 运算到浮点运算， 延迟是增加的。还可以 看到加法和乘法运算的发射时间 都为 1 , 意思是说在每个时钟周期，处理器都可以开始一条新的这样的运算。这种很短的 发射时间 是通过使用 流 水线实现的。流水线化的功能单元实现为一系列的阶段

(stage), 每个阶段完成一 部分的运算。例 如， 一个典型的浮点 加法器包含三个阶段（所以有三个周期的延迟）：一个阶段处理指数值，一个阶段将小数相加，而另一个阶段对结果 进行舍入。算术运算可以连续地通过各个阶段，而不用等待一个操作完成后再开始下一 个。只有当要执行的运算是连续的、逻辑上独立的时候，才能利用这种功能。发射时间为

1 的功能单元 被称为完全 流水 线化的 ( f ull y pipelined) : 每个时钟周期可以开始一个新的运

算。出现容量大于 1 的运算是由于有多个功能单元，就如 前面所述的 参考机一样。

我们还看到，除法器（用于整数和浮点除法，还用来计算浮点平方根）不是完全流水线 化的一—－它的发射时间等于它的延迟。这就意味着在开始一条新运算之前，除法楛必须完成整个除法。我们还看到，对千除法的延迟和发射时间是以范围的形式给出的，因为某些 被除数和除数的组合比其他的组合需要更多的步骤。除法的长延迟和长发射时间使之成为 了一个相对开销很大的运算。

表达发射时间的一种更常见的方法是指明这个功能单元的最大吞吐量，定义为发射时间的倒数。一个完全流水线化的功能单元有最大的吞吐量，每个时钟周期一个运算，而发射时间较大的功能单元的最大吞吐量比较小。具有多个功能单元可以进一步提高吞吐量。对一个容量为 C, 发射时间 为 I 的操作来说， 处理器可能获得的吞吐量为每时钟周期 C/ I 个操作。 比如，我 们的参考机可以 每个时 钟周期执行两个浮点乘法运算。我们将看到如何利用这种能力来提高程序的性能。

电路设计者可以创建具有各种性能特性的功能单元。创建一个延迟短或使用流水线的 单元需要较多的硬件，特别是对于像乘法和浮点操作这样比较复杂的功能。因为微处理器 芯片上 ， 对于这些单元 ，只 有有限的空间，所 以 CPU 设计者必须小心地平衡功能单元的数最和它们各自的性能，以获得最优的整体性能。设计者们评估许多不同的基准程序，将 大多数 资源用 千最关 键的操作。如图 5-1 2 表明的那样， 在 Core i7 H as well 处理器的设计中，整数乘法、浮点乘法和加法被认为是重要的操作，即使为了获得低延迟和较高的流水

线化程度需要大盘的硬件。另一方面，除法相对不太常用，而且要想实现低延迟或完全流 水线化是很困难的。

这些算术运算的延 迟、发射时 间和容量会影响合并函数的性能。我们用 CP E 值的两个基本界限来描述这种影响 ：

延迟界限给出了任何必须按照 严格顺序完成合并运算的函数所需要的最小 CPE 值。根据功能单元产生结果的最大速率，吞 吐量界 限给出 了 CPE 的最小界限。例如， 因为只有一个 整数乘法器， 它的发射时间为 1 个时钟周期， 处理楛不可能支持每个时钟周期大 于 1 条乘法的速度。另一方面，四个功能单元都可以执行整数加法，处理器就有可能持续每个周 期执行 4 个操作的 速率。不幸的是，因 为需 要从内存读数据， 这造成了另一个吞吐量界限。两个加载单元限制了处理器每个时钟周期最多只能读取两个数据值，从而使得吞吐量 界限为 0. 50。我们会展示延迟界限 和吞吐量界限对合并函数不同版本的影响。

5. 7. 3 处理器操作的抽象模型

作为分析在现代处理器上执行的机器级程序性能的一个工具，我们会使用程序的数据 流( data-flow) 表示， 这是一种图形化的 表示方法， 展现了不同操作之间的数据相关 是如何限 制它们的执行顺序的。这些限制形成了图中的关键 路径( critical path) , 这是执行一组机器指令所需时钟周期数的一个下界。

在继续技术细节之前 ，检 查一下函数 c ombi ne 4 的 CP E 测量值是很有帮助的，到目前为止 c ombi ne 4 是最快的代码：

我们可以看到，除 了整数加法的 情况，这 些测量值与处理器的延迟界限是一样的。这不是巧合一 它表明这些函数的性能是由所执行的求和或者乘积计算主宰的。计算 n 个元素的乘积或者和需要大约L · n+ K 个时钟周期， 这里 L 是合并运算的延迟， 而 K 表示调用 函数和初始化以 及终止循环的开销。因此 ， CP E 就等于延迟界限 L。

1 从机器级 代码到数 据流图

程序的数据流表示是非正式 的。我们只是想用 它来形象地描述程序中的数据相关是如何主宰程序的性能的。以 combi ne 4( 图 5-10 ) 为例来描述数据流表示法。我们将注意力集中在循环执行的计算上，因为对于大向量来说，这是决定性能的主要因素。我们考虑类型 为 d o ub l e 的数据、以乘法作为合并运算的情况 ， 不过其他数据类型和运算的组合也有几乎一样的结构。这个循 环编译出的代码由 4 条指令组成， 寄存器%r d x 存放指向数组 dat a中第 i 个元素的指 针，%r a x 存放指向数组末尾的指针 ， 而%x mm0 存放累积值 a c e。

Inner loop of combi ne4 . data_t = double, OP = *

ace i n 胚 江 皿 0 , data+i i n r 加 dx, data+length in Y.rax

. L25: l oop:

如图 5-13 所示，在我 们假想的处理器设计中， 指令译码器会把这 4 条指令扩展成为一系列 的五步操作， 最开始的乘法指令被扩展 成一个 l o a d 操作，从 内 存读出源操作数， 和一个 mul 操作， 执行乘法。

} =ulsd (% cd x ) , %x= O , %x= O addq $8, %r dx

cmpq %r a x, %r dx jne loop

毛r a x I % r dx I 号 xmmO

图 5-13 combi ne 4 的内循 环代码的图形化表示。指令动态地被 翻译成一个或两个操作， 每个操作从其他操作或 寄存器接收 值， 并且为其他操作和寄存器产生值。我们给出 最后一条指令的目标 为标号 l oop 。它跳转到给出的第一条指令

作为生成程序数据流图表示的一步，图 5-13 左手边的方框和线给出了各个指令是如何使用和更新寄存器的，顶 部的方框表示循环开始时寄存器的值，而底 部的方框表示最后寄存器的值。例如， 寄存器%r a x 只 被 c rnp 操作作为源值， 因此这个寄存器在循环结束时有着同循环开始时 一样的值。另一方面， 在循环中， 寄存器% r d x 既 被使用也被修改。它的初始值被 l o a d 和 a d d 操作使用； 它的新值由 a d d 操作产生， 然后被 c rnp 操作使用。在循环中， rnu l 操作首先使用寄存器%x mm0 的 初始值作为源值 ， 然后会修改它的值。

图 5-13 中的某些操作产生的值不对应于任何寄存器。在右边， 用操作间的弧线来表示。l o a d 操作从内存读出一个 值， 然后把它直接传递到 rnu l 操作。由千这两个操作是通过对一条 vmu l s d 指令译码产生的，所 以这个在两个操作之间传递的中间值没有与之相关联的寄存器。c rnp 操作更新条件码， 然后 j n e 操作会测试这些条件码。

对于形成循环的代码片段，我们可以将访问到的寄存器分为四类：

只读：这些寄存器只用作源值，可以作为数据，也可以用来计算内存地址，但是在循 环中它们是不会被修改的 。循环 c o mbi ne 4 的只读寄存器是%r a x 。

只 写： 这些寄存器作为数据传送操作的目的。在本循环中没有这样的 寄存器。

局部： 这些寄存器在循环内部被修改和使用， 迭代与迭代之间不相关。在这个循环中，条件码寄存器就是例子： c rnp 操作会修改它们， 然后 j n e 操作会使用它们， 不过这种相关是在单次迭代之内的。

循环：对于循环来说，这些寄存器既作为源值，又作为目的，一次迭代中产生的值会在另一次迭代中用 到。可以看到，%r d x 和%x mm0 是 c ombi n e 4 的循环寄存器， 对应于程序

值 da t a +i 和 a c e 。

正如我们会看到的，循环寄存器之间的操作链决定了限制性能的数据相关。

图 5-14 是对图 5-13 的图形化表示的进一步改进，目 标是只给出影响 程序执行时间的操作和数据相关。在图 5-14a 中看到， 我们重新排列了操作符， 更清晰地表明了从顶部源寄存器（只读寄存器和循环寄存器）到底部目的寄存器（只写寄存器和循环寄存器）的数据流。

a ) 蜇新排列了图5-13的操作符， 更消晰地表明了数据相关

b ) 操作在一次迭代中使用某些值， 产生出在下一次迭代中需要的新值

图 5-14 将 combi ne 4 的 操 作 抽 象 成 数 据 流图

在图 5-14a 中，如 果操作符不属于某个循环寄存器之间的相关链，那么就把它们标识成白色。例如，比 较( cmp ) 和分支( j ne ) 操作不直接影响程序中的数据流。假设指令控制单元预测会选择分支，因此程序会继续循环。比较和分支操作的目的是测试分支条件，如果不选择分支的话， 就通知 ICU。我们假设这个检查能够完成得足够快，不会减漫处理器的执行。

在图 5-1 4b 中， 消除了左边标识为白 色的

操作符，而且只保留了循环寄存器。剩下的 是一个抽象的模板， 表明的是由千循环的一次迭代在循环寄存器中形成的数据相关。在 这个图中可以看到，从一次迭代到下一次迭 代有两个数据相关。在一边，我们看到存储 在寄存器%x mrn0 中的程序值 a c e 的连续的值之间有相关。通过将 a c e 的旧值乘以一个数据元素， 循环计算出 a c e 的新值， 这个数据元素是由 l oad 操作产生的。在另一边， 我们看到循环索引 i 的连续的值之间有相关。每次迭代中，

i 的旧 值用来计算 l oa d 操作的地址， 然后 add

操作也会增加它的值，计算出新值。

图 5-1 5 给出了函数 c ombi ne 4 内循环的 n

次迭代的数据流表示。可以看出，简单地重

关键路径

图 5-15 co mbi ne 4 的 内 循 环的 n 次 迭代计算的数 据 流表示。乘法操作的序列形成了恨制程序性能的关键路径

复图 5-1 4 右边的模板 n 次， 就 能 得 到 这 张图。我们可以看到， 程 序 有 两 条 数 据 相 关 链 ， 分别对 应于操作 mu l 和 a d d 对程序值 a c e 和 d a 七a 江 的 修 改 。 假设浮点乘法延迟为 5 个周期， 而整数加法延迟为 1 个周期，可 以 看 到左边的链会成为关键路径，需 要 Sn 个周期 执 行。右边的 链只需 要 n 个周期执行， 因此， 它不会制约程序的性能。

图 5-15 说明在执行单精度浮点乘法时，对 于 c o mbi ne 4 , 为什么我们获得了等于 5 个周期延迟界限的 CPE。当执行这个函数时，浮点 乘法器成为了制约资源。循环中需要的其他操作－ 控制和测试指针值 da t a +i , 以及从内存中读数据 与乘法器并行地进行。每次后继的

ace 的值被计算出来，它 就反馈回来计算下一 个值， 不过只有等到 5 个周期后才能完成。

其他数据类型和运算组合的数据流与图 5- 15 所示的内容一样，只 是 在左边的形成数据相关链的数据操作不同。对于所有情况， 如果运算的延迟， L 大 于 1, 那么可以看到测量出来的 CPE 就是 L , 表明这个链是制约性能的关键路径。

1. 其他性能因素

   另一方面，对 于 整数 加 法的情况， 我们对 c ombi n e 4 的测试表明 CPE 为 1. 27, 而根据沿着图 5-1 5 中左边和右边形成的相关链预测的 CPE 为 1. 00, 测试值比预测值要慢。这说明了一个原则，那就是数据流表示中的关键路径提供的只是程序需要周期数的下界。还 有其他一 些因素会限制性能， 包括可用的功能单元的数量和任何一步中功能单元之间能够传递数据值的数量。对于合并运算为整数加法的情况，数据操作足够快，使得其他操作供 应数据的 速度不够快。要准确地确定为什么程序中每个元素需要 1. 27 个周期，需 要 比 公开可以获得的更详细的硬件设计知识。

   总结一下 c ombi n e 4 的性能分析： 我们对程序操作的抽象数据流表示说明， c o mbi ne 4

   的关键路 径长 L · n 是由对程序值 a c e 的连续更新造成的 ， 这条路径将 CPE 限制为最多

   L。除了整数加法之外，对 于 所 有 的 其 他情况， 测 量出的 CPE 确实等千 L , 对于整数加法， 测量出的 CPE 为 1. 27 而不是根据关键路径的长度所期望的 1. 00 。

   看上去，延迟界限是基本的限制，决定了我们的合并运算能执行多快。接下来的任务是重新调整操作的结构，增强指令级并行性。我们想对程序做变换，使得唯一的限制变成吞吐量界 限，得 到接近于 1. 00 的 CPE。

   练习题 5. 5 假设写 一个对多项 式求值的 函 数，这 里， 多项 式的 次数为 n , 系数为 a o ,

   a1, ···, a., 。 对于值 X , 我们对多项式求值，计算

   a。+ a 1x + a 江 ＋ … + a.,工n (5, 2)

   这个 求值 可以用下面 的函 数来实现， 参数包 括 一个系 数 数 组 a 、值 x 和 多项 式的次 数de gr e e ( 等 式 ( 5. 2 ) 中的值 n ) 。在这个函数的 一个 循环 中， 我们 计算连续的等 式的项， 以及 连续的 x 的幕：

   double poly(double a[], double x, long degree)

   2 {

   1. long i;

      4 double result= a[O];

      5 double xpwr = x; I* Equals x-i at start of loop *I

      6 for (i = 1; i <= degree; i++) {

      a[i] * xpwr; xpwr;

2. 对于次数 n , 这段代码执行多少次加法和多少次乘法运算？

3. 在我们 的参 考机 上， 算术运算的 延迟如图 5-1 2 所 示， 我们 测 量 了 这个函 数的 CPE 等于 5. 00 。根据由于实现函数 第 7 ~ 8 行的操作迭代之间形成的数据相关 ， 解释 为什么 会得到这样的 CPE。

   沁曷 练习题 5. 6 我们继续探索练 习题 5. 5 中描述的 多项 式求值的 方 法。 通过采用 H orner 法（以英国数学家 W ill iam G. HornerCl 786- 1837) 命名）对多项 式 求值 ， 我们 可以减少乘 法的 数量。 其思 想是 反复提出 工 的幕， 得到 下面的求值：

a 。十工Ca 1 + x Ca 2 +··· 十工( a 广］＋ 立 ，，）… ）） 使 用 H or ner 法， 我们 可 以用 下 面的 代码实现 多项 式求值：

I* Apply Horner’s method *I

double pol yh (doubl e a[], double x, long degree)

｛

(5. 3)

long i;

double result= a[degree];

for (i = degree-1; i >= O; i–) result= a[i] + x*result;

return result;

｝

5. 8

1. 对于次数 n , 这段代码执行多少次加法和多少次乘法运算？

2. 在我们的参考机上， 算术运 算 的廷迟如 图 5-12 所 示， 测 量这个函 数 的 CPE 等于

   8. 00 。 根据由于实现 函数 第 7 行的操作迭代之间形成 的 数据相关， 解释为 什 么会得到 这样的 CPE。

3. 请解 释虽 然练 习题 5. 5 中所 示的 函数需 要更多的操作 ， 但是它是 如何运行得更快的。

循环展开 #

循环展开是一种程序变换，通过增加每次迭代计算的元素的数批，减少循环的迭代次数。 p s um2 函数（见 图 5-1 ) 就是这样一个例子，其 中 每次迭代计算前置和的两个元素， 因而将需要的迭代次数减半。循环展开能够从两个方面改进程序的性能。首先，它减少了不直接 有助于程序结果的操作的数量， 例 如循环索引计算和条件分支。第二， 它 提供了一些方法， 可以进一步变化代码，减 少 整个计算中关键路径上的操作数量。在本节中， 我们会看 一 些 简 单 的 循 环 展开，不 做 任何 进一 步的变化。

图 5-16 是合并代码的使用 " 2 X l 循环展开＂的版本。第一个循环每次处理数组的两个元素。也就是每次迭代， 循环 索引 l 加 2, 在一次迭代中，对数组元 素 l 和 i + l 使用合并运算。

一般来说，向 量 长度不一定是 2 的倍 数 。 想 要 使 我们的代码对任意向量长度都能正确

工 作 ，可 以 从 两个方面来解释这个需求。首先，要 确 保 第一次循环不会超出数组的界限。对 于 长度为 n 的向量，我 们将循环界限设为 n - l 。然后，保 证 只 有 当 循 环 索 引 1 满足 i <

n —1 时 才会执行这个循环，因 此最大数组索引 i + l 满足 i + l < ( n - l) + l = n。

把这个思想归纳为对一个循环按任意因子 k 进行 展开，由 此 产 生 k X l 循环展开。为此， 上限 设 为 n - k + l , 在循环内 对元素 年 加+ k— l 应用合并运算。每次迭代 ，循 环 索引 1加k。

那 么 最大 循 环 索引 汁 k—1 会 小 千 n。要使用第二个循环，以 每次处理一个元素的方式处理向 最 的 最 后几 个元素。这个循环体将会执行 O k - l 次。对 于 k = 2 , 我们能用一个简单的条件语句， 可选地增加最后一次迭代， 如函数 ps um2( 图 5-1 ) 所示 。 对 于 k > 2 , 最后的这些情

况最好用一个 循环来 表示 ，所 以 对 k = 2 的 情 况， 我们同样也采用这个编程惯例。我们称这种变换为 " k X l 循环展开“，因 为循环展开因子为 k , 而累积值只在单个变量 a c e 中。

I* 2 x 1 loop unrolling *I

2 void combine5(vec_ptr v, data_t *dest)

3 {

1. long i;

2. long length= vec_length(v);

3. long limit= length-1;

4. data_t *data = get_vec_start(v);

5. data_t ace= !DENT;

   9

6. I* Combine 2 elements at a time *I

7. for (i = O; i < limit; i+=2) {

8. ace= (ace OP data[i]) OP data[i+1];

   13 }

   14

9. I* Finish any remaining elements *I

10. for (; i < length; i++) {

11. ace = ace OP data [i] ; 18 }

    19 *dest = ace; 20 }

    图 5-16 使用 2 X l 循环展开。这种变换能减小循环开销的影响区！ 练习题 5 . 7 修改 c o mb i n e s 的代码， 展开循 环 k = 5 次。

    当测 量展 开次数 k = 2 ( c o mbi ne 5 ) 和 k = 3 的展开代码的性能时， 得到 下面的结果 ：

我们 看到对于整数加法， CPE 有所改进， 得到的延迟界限为 1. 0 0 。会有这样的结果是得益千减少 了循环开销操作。相对于计算向量和所需要的加法数量，降 低 开销操作的数量，此时，整数加法的一个周期的延迟成为了限制性能的因素。另一方面，其他情况并没有性能提高——－它 们 已经达到了其延迟界限。图 5-1 7 给出了当循环展开到 10 次时的 CPE测量值。 对于展开 2 次 和 3 次时观察到的趋势还在继续一 没有一个低千其延迟界限。

要理解为什么 k X l 循环展开不能将性能改进到超过延迟界限，让 我们来查看一下 k =

2 时， c o mb i n e s 内 循 环 的机 器级代码。当类型 d a t a —t 为 d o u b l e , 操作为乘法时，生成如下代码：

Inner loop of combi nes . data_t = double, OP=* i in %rdx, data %rax, limit in %rbp, ace in %xmm0

.L35: loop:

1. vmulsd (%rax, %rdx, 8), %xmm0, %xmmO Multiply ace by data[i]

2. vmulsd 8(%rax,%rdx,8), %xmm0, %xmm0 Multiply ace by data[i+1]

3. addq

4. cmpq

   6 jg

   $2, %rdx

   %rdx, %rbp

   .135

6

5

4

Increment i by 2 Compare to limit:1. If>, goto loop

• double *
• double +

u lQ…t..l 3

2

。

牖耋 瞿 瞿 攫

X、、、

-·-一-· 一一- -、于 一一- 沃

3 4

展开次数K

矗 lo ng *

long+

图 5-17 不同程度 k X l 循 环展开的 CPE 性能。这种变换只改进了整数加法的性能

我们可以看到，相 比 c o mbi n e 4 生成的基千指针的代码， GCC 使用了 C 代码中数组引用 的 更 加 直 接的转换气 循环索引 J.. 在 寄 存 器%r d x 中 ， d a t a 的 地址在寄存器%r a x 中6 和前 面一样，累 积值 a c e 在向量寄存器%x mm0 中 。 循 环 展 开会导致两条 vmu l s d 指令＿ ＿ 条 将 d a t a [ i ) 加 到 a c e 上 ， 第 二 条将 d a t a [ i 十 l l 加到 a c e 上。图 5- 1 8 给出了这段代码的图 形 化 表 示。每条 vmu l s d 指令被翻译成两个操作： 一 个 操 作 是 从 内 存 中 加 载 一 个数组元素，另 一个是把这个值乘以已有的 累积值。这里我们 看到，循 环的每次执行中，对 寄存 器 %x mm0 读 和写两次。可以重新排列、简化和抽象这张图，按 照 图 5- 1 9a 所 示的过程得到图 5- 1 9 b 所 示的模板。然后，把 这个模板复制 n / 2 次， 给出一个长度为 n 的向量的计算， 得 到 如图 5- 20 所示的数据流表示。在此我们看到， 这 张 图 中 关 键 路 径 还是 n 个 mu l 操作 一 迭代次数减半了， 但 是 每次迭代中还是有两个顺序的乘法操作。这个关键路径是循环 没有展开代码的性能制约因素， 而它仍然是 k X l 循环展开代码的性能制约因素。

vmulsd ( %r a x , %r d x, 8 ) , %xmm0, %xmm0

vmu l s d 8 ( %r a x, % r d x, 8 ) , %x mm0, %xmm0 addq $2 , %r dx

cmpq % r d x, 号r bp jg l oop

令r a x l %r bp l %r d x l令xmmo:

图 5 - 1 8 co mbi ne s 内循环代码的图形化表示。每次迭代有两条 vmul s d 指令， 每条指令被翻译 成一个 l oa d 和一个 mul 操 作

8 GCC 优化 器 产生一个函数的多个版本， 并 从 中 选择 它预测会获得最佳性能和最小代码蜇的那一个。其结果就是， 源代码中微 小的变化就会生成各种不同形 式的机器码。我们已经发现对基于指针和基于数组的代码的 选择不会影响在参考机上运行的程序的性能。

a ) 重新排列、简 化和抽象图5-18的表示，给出连续迭代之间的数据相关

b) 每次迭代必须顺序地执行两个乘法图 5-19 将 c ombi ne s 的操作抽象成

数据流图

m 让编译器展开循环

关键路径

’–

data[O]

data[l]

da七a [ 2 J

data[3]

data[n-2)

data[n-1]

图 5- 20 c ombi ne s 对一个 长度为 n 的向量进行操作的数据流表示。虽然循环展开了 2 次 ，但 是 关 键 路 径上还是 有

n 个 mul 操作

编译器可以很容易地执行循环展开。只要优化级别设置得足够高，许多编译器都能 例行公事地做到这 一点。用优 化等级 3 或更高等级调 用 GCC , 它就会执行循环展开。

1. 9 提高并行性

   在此，程序的性能是受运算单元的延迟限制的。不过，正如我们表明的，执行加法和乘 法的功 能单元是完全流水线化的， 这意味着它们可以每个时钟周期开始一个新操作 ，并 且有些操作可以被多个功能单元执行。硬件具有以更高速率执行乘法和加法的潜力，但是代码不 能利用这种能力 ， 即使是使用循环展开也不能， 这是因为我们将 累积值放在一个单独的 变量a c e 中。在前面的计算完成之前 ， 都不能计算 a c e 的新值。虽然计算 a c e 新值的功能单元能

够每个时钟周期开始一个新的操作 ， 但是它只会每 L 个周期开始一条新操作， 这里L 是合并操作的延迟。现在我们要考察打破这种顺序相关，得到比延迟界限更好性能的方法。

5. 9. 1 多个累积变量

对于一个可结合和可交换的合并运算来说，比如说整数加法或乘法，我们可以通过将

一组合并运算分割成两个或更多的部分， 并在最后合并结果来提高性能。例如， P" 表示元素 a o’ a 1’ … ， a n- 1 的 乘积：

..- 1

Pn=IIa,

i=O

假设 n 为偶数， 我们还可以把它写成Pn = PEn X P On’ 这里 P E" 是索引值为偶数的元素的乘积， 而 P O" 是索引

值为奇数的元素的乘积：

n/ 2- 1

PE.= az,

,=O

n/2- 1

PO.= II 釭+I

i = O

图 5- 21 展示的是使用这种方法的代码。它既使用了两次循环展 开， 以使每次迭代合并更多的元素，也使用了两路 并行，将索引值为偶数的元素累积在变 量 a c c O 中， 而索引值为奇数的元素累积在变量 a c c l 中。因此， 我们将其称为" 2X 2 循环展开＂。同前面一样，我们 还

I* 2 x 2 loop unrolling *I

void combine6 (vec_ptr v, data_t *dest)

｛

long i;

long length= vec_l engt h (v ) ; long limit= l enght-1;

data_t *data = ge t _ve c _s t ar t (v) ; data_t accO = !DENT;

data_t acc1 = !DENT;

I* Combine 2 elements at a time *I for (i = O; i < limit; i+=2) {

accO = accO OP data[i]; acc1 = acc1 OP data[i+1];

｝

I* Finish anyr ema i ni ng e l ement s * I for (; i < length; i++) {

accO = accO OP dat a [ i ] ;

｝

*dest = accO OP ace!;

包括了第二个循环， 对千向量长度不为2

的倍数时，这个循环要累积所有剩下的数

图5-21 运用 2 X 2 循环展开。通 过维护多个累积变位，

组元素。然后， 我们对 a c c O 和 a cc l 应用 这种方法利用了多个功能单元以及它们的流水线

合并运算，计算最终的结果。 能力

比较只做循环展开和既做循环展开同时也使用两路并行这两种方法，我们得到下面的 性能：

我们看到所有情况都得到了改进， 整数乘 、浮点加、浮点乘改进了约 2 倍， 而整数加也有所改进。最棒的是，我们打破了由延迟界限设下的限制。处理器不再需要延迟一个加 法或乘法操作以待前一个操作完成。

要理解 c ombi ne 6 的性能 ， 我们从图 5- 22 所示的代码和操作序列开始。通过图 5-23

所示的过 程，可 以推导出一个模板， 给出迭代之间 的数据相关 。同 c ombi n e s 一样， 这个内循环包括 两个 vrnu l s d 运算， 但是这些指令被翻译成读写不同寄存器的 mu l 操作，它 们之间没有数 据相关（图5- 23 6 ) 。然后， 把这个模板复制 n / 2 次（图5- 24 ) , 就是在一个长度为 n 的向量上执行这 个函数的模型。可以看到， 现在有两条关 键路径， 一条对应于计算索引为偶数的元素的 乘积（程序值a c c O) , 另一条对应千计算索引为奇数的元素的乘积（程序值 a c c l ) 。 每条关键路径只包含 n / 2 个操作， 因此导致 C P E 大约为 5. 00 / 2 = 2. 50 。相似的分析可 以解释我们观察 到的对于不同的数 据类型和合并运算的 组合， 延迟为 L 的操作的

CPE 等于 L / 2 。实际上 ， 程序正在利用功能单元的流水线能 力， 将利用率提高到 2 倍。唯一的例外是 整数加。我们已将将 CP E 降低到 1. 0 以下， 但是还是有太多的循环开销， 而无法达到 理论界限 0. 50 。

%r a x l%r bp lr% dx l%xmmO I号xmml

vmul s d ( 毛r a x, r% dx , 8 ) , 沧xmmO, 号xmmO

v mul s d 8 (r% ax, 号 r dx, 8) , %xmml , %xmml

a ddq $2, r枭 dx

c mpq 号 r d x, %r bp

jg loop

釭 ax l号r bp lr马 dx l%xmm0I%xmml

图 5-22 co mbi ne 6 内循环代码的图形化表示。每次循环有两条 vrnul s d 指令， 每条指令被翻译成一个 l oad 和一个 mul 操作

我们可以将多个 累积变量变换归纳为将 循环展开 k 次， 以及并行累积 k 个值， 得到 k X k 循环展 开。图 5- 25 显示了当数值达到 k = 10 时， 应用这种变换 的效果。可以看到， 当 K 值足够大时，程序 在所有情况下几乎都能达到吞吐量界限。整数加在 k = 7 时达到的

CPE 为 0. 54 , 接近由两个加载单元导致的吞 吐量界限 0. 50 。整数乘和浮点加在 k 3 时达到的 CP E 为 1. 01, 接近由它们的功能单元设 置的吞吐最界限 1. 00 。浮点乘在 k l O 时达

到的 CP E 为 0. 5 1 , 接近由 两个浮点乘法器和两个加载单元设置的吞吐量界限 o. 5 0 。值得

注意的是， 即使乘法是更加复杂的操作， 我们的代码在浮点乘上达到的 吞吐量几乎是浮点加可以达到的两倍。

通常 ， 只 有保待能够执行该操作的所有功能单元的流水线 都是满的 ， 程序才能达到这个操作的吞吐量界限。对延迟为 L , 容量为 C 的操作而言，这 就要求循环展开因子 k

C · L 。比如， 浮点乘有 C = 2 , L = 5 , 循环展开因子就必须为 k l O。 浮点 加有 C = l ,

L = 3 , 则在 k 3 时达到最大吞吐量。

在执行 k X k 循环展开变换 时， 我们 必须考虑是否要保 留原 始函数的功能。在第 2 章 已经看到， 补码运算是可交换和可结合的， 甚至是当溢出时也是如此。因此， 对于整数 数据类型， 在所有 可能的情况下， c o mbi ne 6 计算出的结果都和 c o mbi ne s 计算出的相同。因此，优化 编译器潜在地能够将 c o mbi ne 4 中所示的代码首先转换成 c ombi n e s 的二路循环展开 的版本， 然后再通过引入并行性， 将之转换成 c o mbi ne 6 的版本。有些编译器可以 做这种或 与之类似的变换来 提高整数数 据的性能 。

a ) 重新排列、简化和抽象图5-22的表示， 给出连续迭代之间的数据相关

data[OJ

data (1]

data[2]

data[3]

data [n-2」]

da t a [ n 一1 ]

b ) 两个mul 操作之间没有相关

图 5-23 将 c ombi ne 6 的运算

抽象成数据流图

图 5- 24 c o mbi ne 6 对一个长度为 n 的向最进行操作的

数据流表示。现在有两条关键路径，每条关键路径包含 n / 2 个操作

2 3 4 5 6 7 8 9 10

展开次数K

• double*

• double+

  long *

  - long+

图 5-25 k X k 循环展开的 CP E 性能。使用这种变换后， 所有的 C P E 都有所改进，接近或达到其吞吐量界限

另一方面， 浮点乘法和加法不是可结合的。因此，由 于 四 舍 五 入或溢出， c o mb i ne s 和 c o mb i n e 6 可能产生不同的结果。例如， 假想这样一种情况，所 有索引值为偶数的元素都 是 绝 对值非常大的数，而 索引值为奇数的元素都非常接近于 o. 0 。 那 么 ，即 使 最 终的乘

积 P" 不 会 溢出，乘 积 PE ,, 也 可能上溢，或 者 PO " 也 可 能 下 溢。不过在大多数现实的程序中，不太可能出现这样的情况。因为大多数物理现象是连续的，所以数值数据也趋向千相

当平滑，不会出什么问题。即使有不连续的时候，它们通常也不会导致前面描述的条件那 样的周期性模式。按照严格顺序对元素求积的准确性不太可能从根本上比“分成两组独立 求积，然后再将这两个积相乘”更好。对大多数应用程序来说，使性能翻倍要比冒对奇怪 的数据模式产生不同的结果的风险更重要。但是，程序开发人员应该与潜在的用户协商， 看看是否有特殊的条件，可能会导致修改后的算法不能接受。大多数编译器并不会尝试对 浮点数代码进行这种变换，因为它们没有办法判断引入这种会改变程序行为的转换所带来 的风险，不论这种改变是多么小。

5. 9. 2 重新结合变换

现在来探讨另一种打破顺序相关从而使性能提高到延迟界限之外的方法。我们看到过 做 k X l 循环展开的 c ombi n e s 没有改 变合并向量元素形成和或者乘积中执行的操作。不过，对代码做很小的改动，我们可以从根本上改变合并执行的方式，也极大地提高程序的 性能。

图 5- 26 给出了一 个函数 c o mbi n e 7, 它与 c o mbi n e s 的展开代码（图5-1 6 ) 的唯一区别在于内循环中元素合并的方式。在 c o mbi n e s 中， 合并是以下面这条语 句来实现的

12 ace = (ace OP data[i]) OP data[i+1];

而在 c o mbi ne 7 中， 合并是以这条语句来实现的

12 ace= ace OP (data[i] OP data[i+1]);

差别仅在 于两个括号是如何放置的。我们称之为重新 结合变换( rea ss o cia t ion transforma­ tion), 因为括号改 变了向釐元素与累积值 a c e 的合并顺序， 产生了我们称为 " 2 X l a " 的循环展开形式 。

I* 2 x 1a loop unrolling *I

2 void combine7(vec_ptr v, data_t *dest)

3 {

4 long i;

5 long length= vec_length(v);

6 long limit= length-1;

7 data_t *data = get_vec_start(v);

8 data_t ace = !DENT;

9

10 I* Combine 2 elements at a time *I

11 for (i = O; i < limit; i+=2) {

12 ace= ace OP (data[i] OP data[i+1]);

13 }

14

1. I* Finish any remaining elements *I

2. for (; i < length; i++) {

3. ace= ace OP data[i];

   18 }

   19 *dest = ace·

   20 }

   图5-26 运用 Z X l a 循环展开 ， 重新结合合并操作 。这种方法增加了可以并行执行的操作数最

   对于未 经训练的人来说， 这两个语句可能看上去本质上是一样的， 但是当我们测扯

CPE 的时候， 得到令人吃惊的结果：

整数加的性能几 乎与使用 k X l 展开的 版本 ( c o mb i n e s ) 的性能相同，而 其他三种情况则 与使用并行累积变量的版本( c o mb i n e 6 ) 相同， 是 k X l 扩展的性能的两倍。这些情况已经突破了延迟界限造成的 限制。

图 5- 2 7 说明了 c o mb i n e 7 内循环的代码（对千合并操作为乘法， 数据类型为 d o ub l e 的 情况 ）是如何被译码成操作， 以及由此得到的数据相关。我们看到， 来自于 vm o v s d 和第一个 vm u l s d 指令的 l o a d 操作从内存中加载向量元素 t 和曰- 1, 第一个 mu l 操作把它们乘起来。然后， 第二个 mu l 操作把这个结果乘以累积值 a c e 。图 5- 28 a 给出了我们如何对图 5- 2 7 的操作进行重新 排列、优化和抽象， 得到表示一次迭代中数据相关的模板（图 5- 28 b ) 。对 于 c o mb i n e s 和 c o mb i n e 7 的模板， 有两个 l o a d 和两个 mu l 操作， 但是只有一个mu l 操作形成了循环寄存 器间的数据相关链。然后， 把这个模板复制 n / 2 次， 给出了 n 个向 量元素相乘所执 行的计算（图5 - 2 9 ) , 我们可以看 到关键路径上只有 n / 2 个操作。每次迭代内的第一个乘法都不需要等待前一次迭代的累积值就可以执行。因此， 最小可能的 CPE 减 少 了 2 倍。

%r a x I %r bp I %rdx l %x mmOl %x mml

vmo v s d ( 皂r a x , 毛 r d x , 8), 令x mmO

} = o vs d 8( 沧 c a a , 号 n ix , 8) , 令 x = O , 号 x= O

v mo v s d 令x mmO, 令x mml , 号xmm l a dd q $2 , %r d x

c mp q % r d x , % r bp jg l o op

图 5- 27 c o mbi n e ? 内循 环代码的图形化表示 。每次 迭代被译码成与 c ombi n e s 或

c ombi ne 6 类似的 操作， 但是数据相关不同

图 5- 3 0 展示了当数值达到 k = l O 时， 实现 k X l a 循环展开并重新结合变换的效果。可以看到， 这种变换带来的性能结果与 k X k 循环展开中保持 K 个累积变量的结果相似。对所有的情况来说 ，我 们都接近了由 功能单元造成的吞吐 量界限。

a ) 重新排列、简化和抽象图 5-27的表示， 给出连续迭代之间的数据相关

data [i]

data[OJ

data[l]

data[2]

data[3)

关键路径

data[i+l]

1. 上面的mu l 操作让两个二向量元素相乘，而下面的mu l 操作将前面的结果乘以循环变盘a c e

． 图 5- 28 将 co rnbi ne 7 的 操作

抽象成数据流图

6

5

4

u #

data[n-2)

data[n-1]

‘\ . 、

图 5-29 co mbi ne 7 对一个 长度为 n 的向量进行操作的数据流表示。我们 只有一条关键路径 ， 它 只 包 含n / 2 个 操 作

• double*
• double+

1匕1｝..

3

亡产 ，’

夏 ，，■

.t. long*

- - - long+

0 I I I I I I I

2 3 4 5 6 7 8 9 JO

展开次数K

图 5-30 kX l a 循环展开的 CP E 性能。在这种变换下，所 有 的 CP E 都 有 所改进，几乎达到了它们的吞吐量界限

在执行重新结合变换时，我们又一次改变向批元素合并的顺序。对于整数加法和乘 法，这些运算是可结合的，这表示这种重新变换顺序对结果没有影响。对于浮点数情况，

｀ 必须再次评估这种重新结合是否有可能严重影响结果。我们会说对大多数应用来说，这种差别不重要。

总的来说， 重 新 结 合 变 换 能 够 减 少 计 算 中 关 键 路 径 上 操 作 的 数 量 ， 通 过 更 好 地 利 用 功能单元的 流水线能力得到更好 的性能。大多数 编译 器不会 尝试 对 浮点 运算 做重新结 合 ，因 为这些 运算不保 证 是 可结合 的 。当前 的 GCC 版 本 会对 整 数 运算执行重新结合，但 不 是 总 有 好的效果 。通常 ，我 们 发 现 循 环 展 开 和并 行 地 累 积 在 多 个 值 中 ， 是 提 高 程 序 性 能 的 更 可靠的 方 法。沁氐 练习题 5. 8 考虑下面的计算 n 个双精度数 组 成 的 数组 乘 积 的 函 数。 我 们 3 次展开这

个循环。

double apr od (doubl e a[], long n)

long i;

double x, y, z; doubler= 1;

for (i = O; i < n- 2 ; i+= 3) {

x = a[i]; y = a [ i +l ] ; z = a[i+2];

r =r * x * y * z; I * Product comput a t i on *I

for (; i < n ; i ++)

r *= a [ i ] ; return r ;

对于标记为 Pr o d uc t c omp u t a t i o n 的行， 可 以用 括 号得 到该 计 算的五 种不 同的结合， 如下所 示 ：

r = ((r * x) * y) * z; I* Ai *I

r = (r * (x * y)) * z ; I * A2 *I r =r * ((x * y) * z ) ; I* A3 *I r = r * (x * (y * z ) ) ; I* A4 *I r = (r * x ) * (y * z ) ; I* A5 *I

假 设在一台浮点数乘法延迟为 5 个时钟周期的机器上运行这些函数。 确定 由乘法的数据相 关限定的 CPE 的下界。（提示： 画 出每 次迭代如何计算 r 的图形化表 示会 所帮助。）

口 开 ；一 用 向 量 指 令 达 到 更 高的 并 行 度

就像 在 3. 1 节 中 讲 述 的 ， I ntel 在 1 999 年 引入 了 SS E 指 令 ， SS E 是 " S t re aming SIM D E xt e ns io ns ( 流 SIM D 扩展 ）” 的 缩 写， 而 S IM D ( 读 作 " sim- dee" ) 是 " S ingle-In­ s t ru ct ion , M ul tip le- Da ta ( 单指令多 数 据 ）” 的 缩写。SS E 功能历 经几代， 最 新 的 版 本为高级 向 量 扩 展 ( advanced vector extens ion ) 或 AVX 。SIMD 执行 模型是 用单条指令对整个向量数 据进行操 作。 这 些向 量保存在一组特殊的向量寄存 器 ( vector register ) 中， 名 字为％

ymmO %ymml 5 。 目前的 AVX 向 量寄存器长为 32 字节 ， 因此每一个都可以存放 8 个 32 位数或 4 个 64 位数， 这 些数 据既可以是整数也可以是 浮点数。AVX 指令 可以对这些寄存器执行向 量操作， 比如 并行执行 8 组 数 值 或 4 组 数 值 的 加 法或 乘 法。 例如， 如 果 Y M M 寄存

器%ymm0 包含 8 个单精度浮点数， 用 a o’ …, a1 表示， 而%r c x 包含 8 个单精度浮点数的内

存 地 址 ， 用 b。, …, b1 表 示， 那么指 令

vmul p s ( %r cx) , %ymm0 , %ymm1

会 从 内 存 中 读 出 8 个值 ， 并 行 地 执 行 8 个乘法， 计算 a ;- a ; • b;, O i 7, 并将得到的

8 个乘积 保存到向 量寄存器 %y mml 。 我们看到 ， 一条指令能够产 生对多 个数据值的计算， 因此称 为 " SIMD" 。

GCC 支持 对 C 语言的扩展 ， 能够让程序 员在 程序中使 用向 量操作， 这些操 作能够被编译成 AVX 的向量指令（以及基于早前的 SSE 指令的代码）。这种代码凤格比直接 用汇编 语言写代 码要好， 因 为 GCC 还可以为其他处理器上 的向量指令产生代 码。

使用GCC 指令、循环展开和多个累积变量的组合， 我们的合并函数能够达到下面的性能 ：

上表中 ， 笫一组数字对应的是按照 c ornbi ne 6 的风格编写的传统标量代码， 循环展开因子为 1 0 , 并维护 10 个 累积 变 量。 第 二组数 字对 应的代码编写形 式 可以被 GCC 编译成

AVX 向 量代 码。除了使 用向 量操 作外， 这个版本也进行了循环展 开，展 开因子为 8 , 并维护 8 个不 同的 向量累积 变量 。我们给出 了 32 位和 64 位数字的 结果， 因 为向 量指令在笫一种情 况中达 到 8 路并行， 而在笫二种情况中只能达到 4 路 并行。

可以 看到 ，向 量代码在 32 位 的 4 种情况下几乎都荻得 了 8 倍的提升， 对于 64 位 来说， 在其中的 3 种情况下 荻得 了 4 倍 的提升。只有长整 数 乘法代码在我们尝试将其表 示为向量代 码时性 能不佳。AVX 指令集不 包括 64 位整数的并行乘法指令， 因此 GCC 无法为 此种 情况生成 向量代码。使用向 量指令对合并操作产 生了 新的吞吐量界 限。与标量界限相比 ， 32 位 操 作的新界限 小 了 8 倍， 64 位 操作的新界限小了 4 倍。 我们的代码在几种 数据类型和操作的组合上接近了这些界 限。

5. 10 优化合并代码的结果小结

我们极大化对向霓元素加或者乘的函数性能的努力获得了成功。下表总结了对千标量 代码所获得的结果，没 有使用 AVX 向量指令提供的向量并行性：

使用多项优化技术， 我们获得的 CPE 已经接近千 0. 50 和 1. 00 的吞吐量界限， 只 受限于功 能单元的容量。与原始代码相比提升了 10 20 倍 ， 且使用普通的 C 代码和标准编译器就获 得了 所有 这些改进。重写代码利用较新的 SIMD 指令得到了将近 4 倍 或 8 倍的性能提升。 比如单精度乘法， CPE 从初值 11. 14 降 到 了 0. 06, 整体性能提升超过 180 倍。这个例子说明现代处理器具有相当的计算能力，但 是 我们可能需要按非常程式化的方式来编写程序以便将这些能力诱发出来。

5. 11 一些限制因素

我们已经看到在一个程序的数据流图表示中，关 键 路 径 指 明 了 执 行 该 程 序 所 需 时间的一 个 基本的下界。也就是说，如 果 程序中有某条数据相关链， 这条链上的所有延迟之和等于 T , 那 么 这 个 程 序 至少需要 T 个周期才能执行完。

我们还看到功能单元的吞吐量界限也是程序执行时间的一个下界。也就是说，假设一 个 程 序 一 共需 要 N 个 某 种 运算的计算，而 微 处 理器只有 C 个能执行这个操作的功能单元， 并 且 这些单元的发射时间为 I 。那么，这 个 程序 的执 行 至 少需 要 N · I / C 个周期。

在本节中， 我们会考虑其他一些制约程序在实际机器上性能的因素。

5. 11. 1 寄存器溢出

循环并行性的好处受汇编代码描述计算的能力限制。如果我们的并行度 p 超过了可用的 寄 存 器 数 量 ，那 么 编译 器会诉诸溢出( s pilling ) , 将某些临时值存放到内存中，通常是在运行时堆栈上分配空间。举个例子，将 c o mbi ne 6 的 多 累 积 变最模式扩展到 k = l O 和k=

20, 其结果的比较如下表所示：

我们可以看到对这种循环展 开程度的 增加 没有改善 CPE , 有些甚至还变差了。现代x86-6 4 处理器有 16 个寄存器，并 可以使用 16 个 Y M M 寄存器来保存浮点数。一旦循环变量的数量超过了可用寄存器的数量， 程序就必须在栈上分配一些变量。

例如，下 面的代码片段展示了在 l O X 10 循环展开的内循环中， 累 积变 量 a c c O 是如何更新的：

Updating of accumulator accO in 10 x 10 urolling vmulsd (%rdx) , %xmm0, %xmm0 accO *= data[i]

我们看到该累积变量被保存在寄存器% x mm0 中 ，因 此 程序可以简单地从内存中读取 d a t a

[i l , 并 与 这 个 寄 存 器相乘。

与之相比， 20 X 20 循环展开的相应部分非常不同：

Updating of accumulator accO in 20 x 20 unrolling vmovsd 40(%rsp), %xmm0

vmulsd (%rdx), %xmm0, %xmm0 vmovsd %xmm0, 40(%rsp)

累积变量保存为栈上的一个局部变量，其 位 置距离栈指针偏移量为 40。程序必须从内存中读 取 两个 数 值 ：累 积 变 量的值和 d a t a [ i ] 的值， 将两者相乘后，将 结果 保 存 回内存。

一旦编译器必须要诉诸寄存器溢出，那 么维 护 多 个 累 积 变量的优势就很可能消失。幸运的是 ， x86-64 有足够多的 寄存器，大 多 数 循 环 在 出现寄存器溢出之前就将达到吞吐量限 制 。

1. 11. 2 分支预测和预测错误处罚

   在 3. 6. 6 节中通 过实验证明 ， 当分支预测 逻辑不能正 确预测一个分支是否要跳转的时候，条件分支可能会招致很大的预测错误处罚。既然我们已经学习到了一些关于处理器是 如何工作的知识，就能理解这样的处罚是从哪里产生出来的了。

   现代处理器的工作远超前千当前正在执行的指令，从内存读新指令，译码指令，以确 定在什 么操作数上执行 什么操作。只要指令遵循的是一种简单的顺 序， 那么这种指令流水线化 ( ins tru ctio n pipel ining ) 就能很好地工作。当遇到 分支的时候， 处理器必须猜测分支该往哪个 方向走。对于条件转移的情况， 这意味着要预 测是否会选择分支。对于像间接跳转

   （跳转到由一个跳转表条目指定的地址）或过程返回这样的指令，这意味着要预测目标地 址。在 这里 ， 我们 主要讨论条件分支。

   在一个使用投机执行( s peculat ive exec ut ion ) 的处理器中， 处理器会开始执行预测的 分支目标 处的指令。它会避免修改 任何实际的寄存器或内存位置， 直到确定了实际的结果。如果预测正确，那么处理器就会”提交“投机执行的指令的结果，把它们存储到寄存器或 内存。如果 预测错误 ， 处理器必须丢弃掉所有投机执行 的结果， 在正确的位置，重 新开始取指令的过程。这样做会引起预测错误处罚，因为在产生有用的结果之前，必须重新填充 指令流 水线。

   在 3. 6. 6 节中我们看 到， 最近的 x8 6 处理器（包含所有可以执行 x86- 64 程序的处理器）有条件传 送指令。在编译条件语句和表达式的时候， GCC 能产生使用这些指令的代码，而 不是更传统的基于控制的条件转移的实现。 翻译成条 件传送的基本思想是计算出一个条件 表达式或语句 两个方向上的值， 然后用 条件传送选 择期望的值。在 4. 5. 7 节中我们看到 ， 条件传送指令 可以被实现为普通指 令流水线 化处理的一部分。没有必要猜测条件是否满足 ， 因此猜测错误也 没有处罚。

   那么一个 C 语言程序员怎么能够保证分支预测处罚不 会阻碍程序的效 率呢？对于参考机来说， 预测错误处罚是 19 个时钟周期， 赌注很高。对于这个问题没有简单的答案， 但是下面的通用原则是可用的。

   1 不要过分关心可预 测的分支

   我们已经 看到错误的分支预测的 影响可能非常 大， 但是这并不意味着所有的程序分支都会减 缓程序的 执行。实际上， 现代处理器中的分支预测 逻辑非常善于辨别不同的分支指令的有规律的模式和长期的趋势。例如，在合并函数中结束循环的分支通常会被预测为选 择分支， 因此只在最后一次会导致预测错误处罚。

   再来看另一个例子， 当从 c ombi n e 2 变化到 c ombi ne 3 时， 我们把 函数 ge t _v e c _e l e ­ m ent 从函数的内 循环中拿了出来， 考虑一下我们观察 到的结果， 如下所示：

CPE 基本上没变， 即使这个转变消除了每次迭代中用 于检查向量索引是否在界限内的两个条件语句。对 这个函数来说， 这些检测总是确定索引 是在界内的， 所以是高度可预测的 。作为一种测试边界检查 对性能影响的方法， 考虑下面的合并代码 ，修 改 c ombi n e 4 的

内循环，用 执行 g e t _ v e c _ e l e rne 江 代码的 内联函数结果替换对数据元素的访问。我们称这个新版本为 c o mb i n e 4b 。这段 代码执行了边界检查， 还通过向晕数据结构来引用向量元素。

I* Include bounds check in loop *I

2 void comb i ne 4 b ( ve c _p tr v, d at a _t *dest)

3 {

1. long i ;
2. long length= vec_length(v);
3. data_t acc = !DENT;

12 }

13 *dest = acc; 14 }

然后， 我们直接比较使用和不使用边界检查的 函数的 CPE :

对整数加法来说， 带边界检测的版本会慢一点， 但对其他三种情况来说， 性能是一样的， 这些情况受限于它们各自的合并操作的延迟。执行边界检测所需 的额外计算可以与合并操作并行执行。处理器能够预测这些 分支的结果， 所以这些求值都不会对形成程序执行中关键 路径的指令的取指和处理产生太大的影响。

2. 书写适合用条件传送实现的代码

分支预测只对有规律的模式可行 。程序中的许多测试是完全不可预测的， 依赖于数据的任意特性， 例如一个数是负数还是正数。对千这 些测试， 分 支预测逻辑 会处理得很精糕。对千本质上无法预测的情况， 如果编译器能够产生使用条件数据传送而不是使用条件控制转移的代码，可 以极大地提高程序的性能。这不是 C 语言程序员 可以直接控制的，但是有些表达条 件行为的方法能够更直接地被翻译成条件传送， 而不是其他操作。

我们发现 GCC 能够为以一种更 ”功能性的“风格书写的代码产生条件传送 ，在这种风 格的代码中， 我们用条件操作来计算值， 然后用这些值来更新程序状态， 这种风格对立于一种更 ”命令式的“ 风格， 这种风格中， 我们用 条件语句来有 选择地 更新程序状态。

这两种风格也没有严格的规则， 我们用一个例子来说明。假设给定两个整数数组 a 和

b, 对千每个 位置 i , 我们想将 a [ i ] 设置为 a 巨］和b 巨］中较小的那一个， 而将 b [ i ] 设置为两者中较大的那一个。

用命令式的风格实现这个函数是检查 每个位置 i’ 如果它们的顺序与我们想要的不同， 就交换两个元素：

I* Rearrange two vectors so that for each i , b[i] >= a[i] *I

1. v o i d mi nrnax 1 ( l ong a[], long b[], l ong n) {
2. long i;

4 for (i = O; i < n; i++) {

5 if (a [i] > b[i]) { long t = a[i]; a[i] = b[i]; b[i] = t;

10

在随机数据上测试这个函数，得 到 的 CPE 大约 为 13. 50, 而对千可预测的数据， CP E

为 2. 5~3. 5, 其预测错误惩罚约为 20 个周期。

用功能式的风格实现这个函数是计算每个位置 1 的最大值和最小值，然 后 将 这些值分

别赋给 a[ i] 和 b[ i] :

1. I* Rearrange two vectors so that for each i, b[i] >= a[i] *I
   1. void mirunax2(long a[], long b[], long n) {
   2. long i;

对这个函数的测试表明无论数据是任意的， 还是可预测的， C PE 都 大 约 为 4. 0。（我们还检查 了产生的汇编代码，确 认 它确 实 使 用 了条件传送。）

在 3. 6. 6 节中讨论过 ，不 是 所 有 的 条 件 行 为都能用条件数据传送来实现，所 以 无 可避免地在某 些情况中， 程序员不能避免写出会导致条件分支的代码， 而 对 于 这 些 条 件 分 支 ， 处理器用 分支预测可能会处理得很糟糕。但是，正 如我们讲过的，程 序 员 方 面用一点点聪 明， 有时就能使代码更容易被翻译 成条件数据传送。这需要一些试验， 写 出函数的不同版本，然后 检查产生的汇编代码， 并 测 试 性 能 。

讫 ｝练习题 5. 9 对于归 并排序的合并步 骤的传统的 实现 需要 三个 循环[ 98] :

1 void merge (long src1[] , long src2[] , long dest [] , long n) { long i1 = O;

3 long i2 = O;

4 long id= O;

5 while (i1 < n && i2 < n) {

6 if (src1[i1] < src2[i 2])

7 dest [id++] = s r c1 [ i1 ++] ; else

9 de s t [ i d++] = sr c 2 [ i 2++] ;

10

对于把 变量 il 和 i 2 与 n 做比较 导致的分 支， 有很 好的预 测性 能－－－唯一的预测错误

发生在 它们 第 一次 变成错 误时。 另 一方面，值 sr c l [ il l 和 sr c 2 [ i 2 ] 之间的比 较（第6 行），对于通常的数据来说，都是非常难以预测的。这个比较控制一个条件分支，运 行在随 机数据 上时，得到 的 CP E 大约为 1 5. 0 ( 这里元 素的数 量为 2 n ) 。

重写这段代码，使得可以用一个条件传送语句来实现第一个循环中条件语句（第

6 ~ 9 行）的功能。

5. 12 理解内存性能 #

到目前为止我们写的所有代码，以及运行的所有测试，只访问相对比较少量的内存。 例如，我 们都是在长度小于 1000 个元素的向扯上测试这些合并函数， 数据量不会超过8 000 个字节。所有的 现代处理器都包含一个或多个高速 缓存( ca c h e ) 存储器， 以对这样少量的存储器提供快速的访问。本节会进一步研究涉及加载（从内存读到寄存器）和存储（从 寄存器写到内存）操作的程序的性能，只考虑所有的数据都存放在高速缓存中的情况。在 第 6 章 ， 我们会更详细地探究高速缓存是如何丁作的，它 们的性能特性， 以及如何编写充分利用高速缓存的代码。

如图 5-11 所示， 现代处理器有专门的功能单元来执行加载和存储操作， 这些单元有内部的缓冲区来保存未完成的内存操作请求集合。例如，我们的参考机有两个加载单元， 每一个可以保存多达 72 个未完成的读请求。它还有一个存储单元， 其存储缓冲区能保存最多 42 个写请求。每个这样的单元 通常可以每个时 钟周期开始一个操作。

5. 12. 1 加载的性能

一个包含加载操作的程序的性能既依赖于流水线的能力，也依赖于加载单元的延迟。 在参考机上运行合并操作的实验中， 我们 看到除了使用 SIMD 操作时以外， 对任何数据类型组合和合并操作来说， CPE 从 没有到过 0. 50 以下。一个制约示例的 CPE 的因素是，对于每个被计算的元素，所有的示例都需要从内存读一个值。对两个加载单元而言，其每个

时钟周期只能启动一条加载操作 ， 所以 CPE 不可能小于 o. 50。对于每个被计算的元素必

须加载 k 个值的应用， 我们不可能获得低千 k / 2 的 CP E ( 例 如参见家庭作业 5. 15) 。

到目前为止，我们在示例中还没有看到加载操作的延迟产生的影响。加载操作的地址 只依赖于循 环索引 i’ 所以加载操作不会 成为限制性能的关键路径的一部分。

要确定一台机器上加载操作的延迟，我们可 I 1 typedef struct ELE {

以建立由一系列加载操作组成的一个计算，一条加载操作的结果决定下一条操作的地址。作为一个例子， 考虑函数图 5-31 中的函数 l i s 七— l e n , 它计算一个链表的长度。在这个函数的循环中， 变扯 l s 的每个后续值依赖千指针引 用 l s - > n e x 七读出的值。测试表明函数 l i s t _ l e n 的 CPE 为

4.00, 我们认为这直接表明了加载操作的延迟。

1. struct ELE *next;
2. long data;
3. } list_ele, *list_ptr;
4. long list_len(list_ptr ls) {
5. long len = O;
6. while (ls) { len++;

要弄懂这一点，考虑循环的汇编代码：

Inner loop of 1 工s t _l en ls in %rdi, len in %rax

10

11

12

13 }

ls= ls->next; return len;

.13:

addq $1, %rax

l oop : I nrc

ement len

图5-31 链表函数。其性能受限于

movq (%rdi), %rdi

ls= ls->next

加载操作的延迟

testq jne

%rdi, %rdi

.L3

Test ls

If nonnull, goto loop

第 3 行上的 mov q 指令是这个循环中关键的瓶颈。后 面寄存 器%r 中 的每个值 都依赖于加载操作的结果， 而加载操作又以 %r 土 中 的 值作为它的地址。因此， 直到前一次迭代的加载操作完成 ， 下一次迭代的加载操作才能 开始 。这个函数的 CPE 等于 4. 00 , 是由加载操作的延迟决定 的。事实上 ， 这个测试结果与文档中参考机的 L1 级 cach e 的 4 周期访问时间是一致的 ， 相关内容将在 6. 4 节中讨论。

5. 12. 2 存储的性能

在迄今 为止所有的示例 中， 我们只分 析了大部分内存引 用都是加载操作 的函数，也 就是从内存位置读到寄存器中。与之对应的是存储 ( s to re ) 操作， 它将一个寄存器值写到内存。这 个操作的性能， 尤其是与加载操作的相互关系， 包括一些很细微的问 题。

与加载操作 一样， 在大多数情况中， 存储操作能 够在完全流水线 化的模式中丁作， 每个周期 开始一条新的存储。例如， 考虑图 5-32 中所示的函数， 它们将一个长度为 n 的数组 de s t 的元素设置为 0。我们测 试结果为 CPE 等于 1. 00 。对于只具有单个存储功能单元的机器，这已 经达到了最佳情况。

I* Set elements of array to O *I

void clear_array(long *dest, long n) { long i;

for (i = O; i < n; i++)

dest [i] = O;

｝

图 5-32 将数组元素设置为 0 的函数。该代码 CPE 达到 1. 0

与到目前 为止我们已经 考虑过的其他操作不同 ， 存储操作并不影响任何寄存器值。因此， 就其本性来 说， 一系列存储操作 不会产生数据相关。只有加载操作会受存储操作结果的影响 ， 因为只 有加载操作能从由存储操作写的那个位置读回值。图 5-33 所示的函数write r ead 说明了加载和存储操作之间可能的相互影响。这幅图也展示了该函数的两个示例执行 ， 是对两元素数组 a 调用的，该 数组的 初始内容为—10 和 17 , 参数 c n t 等于 3。这些执行说明了加载和存储操作的一些细微之处。

在图 5-33 的示例 A 中， 参数 s r c 是一个指向数组元素 a [0 l 的 指针， 而 d e s t 是一个指向数组元素 a [1 ] 的指针。在此种情况中， 指针引用 *sr c 的每次加载都会得到值—1 0。因此， 在两次迭代之后 ， 数组元素就会分别保持固定为—10 和—9。从 sr c 读出的结果不受对 de s t 的写的 影响。在较大次数的迭代上测试这个示 例得到 CPE 等于 1. 3。

在图 5-33 的示例 B 中，参数 sr c 和 de s t 都是指向数组元素 a [ OJ 的 指针。在这种情况中， 指针引用*sr c 的每次加载都会得到指针引用* de s t 的前次执行存储的值。因而， 一系列不断增加的值会被存储在这个 位置。通 常， 如果调用函数 wr i t e _r e a d 时 参数 sr c 和 de s t 指向同一个内存位置， 而参数 c n t 的值为 n> O, 那么净效果是将这个位置设置为 n- 1。这个示例说明了一个现象， 我们称之为写／读相 关 ( wr ite / read dependency)-­ 个内存读的结果依赖于一个最近的 内存写。我们的性能测试表明示例 B 的 CPE 为 7. 3。写／读相关导 致处理速度下降 约 6 个时钟周期。

I* Write to dest, read from src *I

2 void write_read(long *src, long *dst, long n)

3 {

1. long cnt = n;

2. long val= O;

   6

3. while (cnt) {

4. *dst = val;

   9 val= (*src)+1;

   10 cnt–·

   11 }

   12 }

示例A: wr i t e _ r e a d ( &a [ O ] , &a [ l ] , 3 )

示例B: wr i 七e _r e ad ( &a [ O] , &a [ 0 ] , 3 )

图 5-33 写 和读内存位置的代码，以 及示例执行。这个函数突出的是当参数

s r c 和 de s t 相等时，存 储 和加载之间的相互影响

为了了解处理器如何区别这两种情况，以及为什么一种情况比另一种运行得慢，我们必 须更加仔细地看看加载和存储执行单元， 如图 5-34 所示。存储单元包含一个存储缓冲区 ， 它 包 含巳经被发射到存储单元而又还没有完成的存储操作的地址和数据， 这里的完成包括更新数据高速缓存。提供这样一个缓冲区，使得一系列存储操作不必等待每个操作都更新 高速缓存就能够执行。当一个加载操作发生时，它必须检查存储缓冲区中的条目，看有没

有地址相匹配。如果有地址相匹配（意味着在写的

字节与在读的字节有相同的地址），它 就 取 出 相 应的数据条目作为加载操作的结果。

GCC 生成的 wr i t e r e a d 内循环代码如下 ：

Inner loop of 口r i t e_r ead

src in %rdi, dst in %rsi, val in %rax

.L3: l oop:

I 加载单元

存储单元

存储缓冲区地址数据

地址

机器地址｛

数据

movq %rax, (%rsi) Write val to dst movq (%rdi), %rax t = *STC

addq $1, %rax val = t+1

subq $1, 。%r dx cnt– 图5-34

jne .L3 If!= 0, goto loop

图 5-35 给出了这个循环代码的数 据流表示。

指令 mo v q %r ax, ( % r s i ) 被翻译 成 两个 操作： S

数据高速 缓存

加载和存储单元的细节。存储单元包 含一个未执行的写的缓冲区。加载 单 元 必 须 检 查 它 的 地址是否与存储单元中的地址相符，以发现 写／读相关

addr 指令计算存储操作的地址 ， 在存储缓冲区 创建一个条目， 并且设置该 条目的地址字段。s _ d a t a 操作设置该 条目的数据字段。正如我们会看到的 ， 两个计算是独立执行的， 这对程 序的性能来说很重要。这使得 参考机中不同 的功能单元来执行这些操作。

r% a x I %rdi I %r s i I %r dx

%r a x: I %rdi 1·% r s i I %rdx

图 5-35 writer e ad 内循环代码的图 形化表示。第一个 movl 指令被译码两个独立的操作，计算存储地址和将数据存储到内存

除了由于写和读寄存器造成的 操作之间的数据相关， 操作符右边的弧线表示这些操作隐含的相关。特别地， s —a d d r 操作的地址计算必须在 s —d a t a 操作之前。此外， 对指令movq ( %r d i ) , %r a x 译 码得到的 l o a d 操作必须检查所有未完成的 存储操作的地址， 在这个操作和 s _ a d dr 操作之间创建一个数据相关。这张图中 s _ d a t a 和 l o a d 操作之间有虚弧线。这个数据相关 是有条件的： 如果两个地址相同， l o a d 操作必须等待直 到 s—d a t a 将它的结果存放到 存储缓冲区中，但 是如果两个地址不同， 两个操作就可以独立地进行。

图 5- 36 说明了 wr i t e _r e a d 内循环操作之间的数据相关。在图 5- 36a 中， 重新排列了操作， 让相关显得更清楚。我们标出了三个涉及加载和存储操 作的相关， 希望引起大家特别的注 意。标号为(1 ) 的弧线表示存储地址必须在数据 被存储之前计算出来。标号为( 2 ) 的弧线表示需要 l o a d 操作将它的地址与所有未完成的存储操作的地址进行比较。最后， 标号为 ( 3 ) 的虚弧线表示条件数据相关， 当加载和存储地址 相同时会出现。

1. b )

图 5-36 抽象 wr i t e r_ ead 的操作。我们首先 重新排列图 5-35 的操作(a)’ 然后只显示

那些使用一次迭代中的值 为下一次迭代产生新值的操作 C b)

图 5-366 说明 了当 移走那些不直接影响迭代与 迭代之间数据流的 操作之后， 会发生什么。这个数据流图给出两个相关链：左边的一条，存储、加载和增加数据值（只对地址相 同的情况有效），右边的一条， 减小变量 c n t 。

现在我们 可以理 解函数 wr i t e _ r e a d 的 性能特征了。图 5-37 说明的是内循环的多次迭代形成的数据相关。对于图 5-33 示例 A 的情况，有 不同的源和目的地址， 加载和存储操作可以独立进行 ， 因此唯一的关键路径是由减少变量 c nt 形成的， 这使得 CP E 等于 1. 0。对于图 5-33 示例 B 的情况， 源地址 和目的地址相同， s _d a t a 和 l oa d 指令之间的数据相关使得关键路径的形成包括了存储、加载和增加数据。我们发现顺序执行这三个操作一共 需要 7 个时钟周期。

示例A

二

关键路径

示例B

：丁

亡

图 5-37 函数 rw i t e_r ead 的数据流表示。当 两个地址不同时， 唯一的关键路径是减少 cnt<示例

A ) 。当两个地址 相同时 ， 存储、加载和增加数据的 链形成了 关键路径（示例 B)

这两个例子说明 ，内 存操作的实现包括许多 细微之处 。对于寄存器操作， 在指令被译码成操作的时候， 处理器就可以 确定哪些指令 会影响其他哪些指令。另一方面，对 千内存操作，只有到计算出加载和存储的地址被计算出来以后，处理器才能确定哪些指令会影响 其他的哪些。高效地处理内存操作对许多程序的性能来说至关重要。内存子系统使用了很 多优化，例 如当操作可以独立地进行时 ， 就利用这种潜在的并 行性。

讫i 练习题 5. 10 作为 另 一个具有 潜在的加载－存储相互 影 响的代码 ， 考虑下 面 的 函数， 它将 一个数组的内容 复制到另 一个数 组 ：

void copy_array(long *src, long *dest, long n)

｛

long i;

for (i = 0 ; i < n; i ++) dest [i] = src [i] ;

｝

假设 a 是一个长 度为 1 00 0 的数组， 被初始化为 每个元素 a [ i ] 等于 1。

1. 调用 c o p y _ arr a y (a+l, a, 999) 的效果是什么？

2. 调用 c o p y _ arr a y (a , a +l , 9 9 9 ) 的效果是什么？

3. 我们的性能测试表明问题 A 调用的 CPE 为 1. 2( 循环展开因子为 4 时 ， 该值下降到

   1. 0 )’ 而问题 B 调用 的 CPE 为 5. 0 。 你认为是什么 因 素造成 了这样的性能差 异？

4. 你预计调用 c o p y_ a rr a y (a , a , 99 9 ) 的性能会是怎样的？

   讫； 练习题 5 . 11 我们 测量 出前置和函 数 p s u ml ( 图 5-1 ) 的 CPE 为 9. 00 , 在测试机器上， 要执 行的基本操作一 浮点加法 的延迟只是 3 个时钟周期。 试着理 解为 什 么 我们 的 函数执行效果这么差。

   下面是 这个函数内循 环的 汇编 代码 ：

   Inner loop of psum1

   a in %rdi, i in %rax, cnt in %rdx

. L5 :

vmovss vaddss vmovss addq cmpq jne

-4(%rsi,%rax,4), %xmm0 (%rdi,%rax,4), %xmm0, %xmm0

%xmm0, (%rsi,%rax,4)

$1, %rax

%rdx, %rax

. L5

l oop:

Ge t p [ i 一 1]

Add a[i] Store at p[i] Increment i Compare i:cnt

If !=, goto loop

参考对 c ombi ne 3( 图 5- 1 4 ) 和 wr 迂 e _ r e a d ( 图 5- 36) 的分析， 画 出这 个循环 生成 的数据相 关图 ， 再画出 计算进行 时由 此形 成的关键 路径。 解释 为 什么 CPE 如此之 高。

江 练习 题 5. 12 重写 p s u ml ( 图 5-1 ) 的代 码 ， 使之 不 需 要 反复地从内存 中读取 p [ i ] 的值。 不需要使 用循环展开。 得到 的代 码 测 试 出 的 CPE 等 于 3. 00, 受浮点加法延迟的限制。

1. 13 应用： 性能提高技术

   虽然只考虑了有限的一组应用程序，但是我们能得出关千如何编写高效代码的很重要 的经验教 训。我们已经描述了许多优化程序性能的基本策略：

   1. 高级 设 计。为遇到的问题选择适当的算法和数据结构。要特别警觉， 避 免 使 用 那些会渐进地产生糟糕性能的算法或编码技术。
   2. 基本编码原则。 避免限制优化的因素， 这样编译器就能产生高效的代码。

• 消除连续的函数 调用。在可能时，将 计 算移到循环外。考虑有选择地妥协程序的模块性以获得更大的效 率。
• 消除不必要的内存引用。引入临时变量来保存中间结果。只有在最后的值计算出来 时， 才将结果存放到数组或全局变量中。

3 ) 低级优化。结构化代码以利用硬件功能。

• 展开循环，降低开销，并且使得进一步的优化成为可能。
• 通过使用 例如多个累积变量和重新结合等技术 ， 找到方法 提高指令级并行。

  • 用功能性的风格重写条件操作，使得编译采用条件数据传送。

    最后要给读者一个忠告，要警惕，在为了提高效率重写程序时避免引入错误。在引入 新变蜇、改变循环 边界和使得代码整体上更复杂时， 很容易犯错误。一项有用的技术是在优化函数时，用检查代码来测试函数的每个版本，以确保在这个过程没有引入错误。检查 代码对函数的新版本实施一系列的测试， 确保它们产生与原来一样的结果。对于高度优化的 代码 ， 这组测试情况必须变得更 加广泛， 因为要考虑的情 况也更多。例如， 使用循环展开的检查代码需要测试许多不同的循环界限，保证它能够处理最终单步迭代所需要的所有 不同的可能的数字。

5. 14 确认和消除性能瓶颈

至此，我们只考虑了优化小的程序，在这样的小程序中有一些很明显限制性能的地方， 因此应该是集中注意力 对它们进行优化。在处理大程序时， 连知道应该优化什么地方都是很难的。本节会描述如何使用代码剖析程序 ( code profiler) , 这是在程序执行时收集性能数据的分 析工具。我们还展示了一个系统优化的通用原则， 称为 A mda hl 定律( A m­ dahl’s law), 参见 1. 9. 1 节。

1. 14. 1 程序剖析

   程序剖析 ( pro fil ing ) 运行 程序的一 个版本， 其中插入了工具代码， 以确定程序的各个部分需要多少时间。这对于确认程序中我们 需要集中注意力优化的部分是很有用的。剖析的 一个有力之处在千可以在现实的基准数据( be nchm a r k da ta ) 上运行实际程序的同时，进 行剖析。

   U nix 系统提供了一个剖析程序 GPROF。这个程序产生两种形 式的信息。首先， 它确定 程序中每个函数花费了多少 CP U 时间。其次， 它计算每个 函数被调用的次数， 以执行调用的函数来分类。这两种形式的信息都非常有用。这些计时给出了不同函数在确定整体 运行时间中的相对重要性。调用信息使得我们能理解程序的 动态行为。

   用 GPROF 进行 剖析需要 3 个步骤， 就像 C 程序 pr og . c 所示， 它运行时命令行参数

   为 f i l e . t xt :

   1. ) 程序必须为剖析而编译和链接。使用 GCC( 以及其他 C 编译器）， 就是在命令行上简单 地包括运行时标志 " - pg" 。确保编译器不通过内 联替换来尝试执行任何优化是很重要的，否则就可能无法正确刻画函数调用。我们使用优化标志- Og , 以保证能正确跟踪函数调用。

      linux> gee -Og -pg prog.e -o prog

2. 然后程序像往常一样执行：

   linux> ./prog t il e. txt

它运行得会比正常时稍微慢一点（大约慢 2 倍）， 不过除此之外唯一的区别就是它产生了 一个文件 grno n . o u t 。

3 ) 调用 GPROF 来分析 grno n . o 江 中的数据。

linux> gprof prog

剖析报告的第一部分列出了执行各个函数花费的时间，按照降序排列。作为一个示 例， 下面列出了报告的一部分， 是关于程序中最耗费时间的三个函数的：

每一行代 表对某个 函数的所有调用所花费的时间。第一列表明花费在这个函数上的时间占整 个时间的百分 比。第二列显示的是 直到这一行并 包括这一行的函数所花费的累计时间。第三列显示的是 花费在这个函数上的时间， 而第四列显示的是它被调用的次数（递归调用不 计算在内）。在例子中， 函数 s or t _ wor d s 只 被调用了一次， 但就是这一次调用需 要 203. 66 秒， 而函数 f i n d_ e l e _ r e c 被调用了 965 0 27 次（递归调用不计算在内），总 共需 要 4. 8 5 秒。 函数 S 七r l e n 通过调用库函数 s tr l e n 来计算字符串的长度。GPROF 的结果中通常不显示库函数调用。库函数耗费的时间通常计算 在调用 它们的函数内。通过创建这个“包 装函数( w ra p pe r fu nct io n ) " S 七r l e n , 我们可以 可靠地跟踪 对 s t r l e n 的调用， 表明它被 调用了 1 2 511 0 31 次， 但是一共只需 要 0. 30 秒。

剖析报告的第二部分是函数的调用历史 。下面是一个递归函数 f i nd _e l e _r e c 的历史：

[5] 2.4

这个历史既显示了调用 f i n d_ e l e _r e c 的函数， 也显示了它调用的函数。头两行显示的是对这个 函数的调用： 被它自身递归地调用了 158 655 72 5 次，被 函数 i n s er t _ s tr i n g 调用了 9&5 0 27 次（它本身被调用 了 965 0 27 次）。函数 f i n d _ e l e _r e c 也调用了另外两个函数 s ave _ s tr i n g 和 n e w_ e l e , 每个函数总共被调用了 3 63 039 次。

根据这个调用信息，我们通常可以推断出关于程序行为的有用信息。例如，函数 釭nd_e l e _r e c 是一个递归过程，它 扫描一个哈希桶( ha s h b uck et ) 的链表，查 找一个特殊的字符 串。对于这个函数， 比较递归调用的数量和顶层调用的 数量， 提供了关千遍历 这些链表的长度的统计信息。这里递归与顶层调用的比率是 1 64. 4, 我们可以推断出程序每次

平均大约扫描 1 64 个元素。

GPROF 有些属 性值得注意 ：

• 计时不是很准确。它的计时基于一个简单的间隔计数 ( interval co un ting ) 机制， 编译过

  的程序为每个函数维护一个计数器， 记录花费 在执行该 函数上的时间。操作系统使得每隔某个规则的时间间隔 o, 程序被中 断一次。8 的典型值的范围为 l. 0 ~ 10. 0 毫秒。

  当中断发生时， 它会确定程序正在执行 什么函数， 并将该函数的计数器值增加 8。当

｀

然，也可能这个函数只是刚开始执行，而很快就会完成，却赋给它从上次中断以来整个

的执行花费。在两次中断之间也可能运行其他某个程序，却因此根本没有计算花费。

对千运行时间较长的程序，这种机制工作得相当好。从统计上来说，应该根据 花费在执行 函数上的相对时间来计算每个 函数的花费。不过， 对于那些运行 时间少于 1 秒的程序来说， 得到的统计数字只能 看成是粗略 的估计值。

• 假设没有执行内联替换，则调用信息相当可靠。编译过的程序为每对调用者和被调 用者维护一个计数器。每次调用一个过程时 ， 就会对适当的计数器加 1 。
  • 默认情况下，不会显示对库函数的计时。相反，库函数的时间都被计算到调用它们 的函数的时间中。

1. 14. 2 使用剖析程序来指导优化

   作为一个用剖析程序来指导程序优化的示 例， 我们创建 了一 个包括几个不同任务和数据结构的应用。这个应用分析一个文本文档的 订g ra m 统计信息， 这里 n-g ra m 是一个出现在文档中 n 个单词的序列。对于 n = l , 我们收集每个单词的统计信息， 对于 n = 2 , 收集每对单词的 统计信息， 以此类推。对于一个给定的 n 值， 程序读一个文本文件， 创建一张互不相同的 n-gra m 的表， 指出每个 n-gra m 出现了多少次， 然后按照出现次数的降序对单词排序。

   作为基 准程序 ， 我们在一个由《莎士比亚全集》组成的文件上运行这个程序，一共有965 028 个单词 ， 其中 23 706 个是互不相同的。我们发现， 对于 n = I , 即使是一个写得很烂的分析程序也能在 1 秒以内处理完整个文件， 所以我们设置 n = Z, 使得事情更加有挑战。对于 n = Z 的情况， n- gra m 被称为 bigram ( 读作 " bye-gra m" ) 。我们确定《莎士比亚全集》包含 363 039 个互不相同的 bigra m。最常见的是 " I am", 出现了 1892 次。词组 “to

   be” 出现了 1020 次。bigr am 中有 266 018 个只出现了一 次。

   程序是由下列部分组成的。我们创建了多个版本 ， 从各部分简单的算法开始 ，然后再换成更成熟完善的算法：

   1. 从文件中读出每个单词， 并转换成小写字母。我们最初的版本使用的是函数 l owed

      （图 5-7 ) , 我们知道由于反复地调用 s tr l e n , 它的时间复杂度是二次的。

   2. 对字符串应用一个哈希函数， 为一个有 s 个桶( bucket ) 的哈希表产生一个 O~ s—l

      之间的数 。最初的函数只是简单地对字符的 ASCII 代码求和，再 对 s 求模。

2. ) 每个哈希桶 都组织成一个链表。程序沿着这个链表扫描， 寻找一个匹配的条目， 如果找到了， 这个 n-gra m 的频度就加 1。否则， 就创建一个新的链表元素。最初的版本递归地完成这个操作，将新元素插在链表尾部。

3. ) 一旦已经生成了这张表， 我们就根据频度对所有的元 素排序。最初的版本使用插入排序。

   图 5-38 是 兀gra m 频度分析程序 6 个不同版本的剖析结果。对千每个版本， 我们将时间分为下面的 5 类。

   Sort: 按照频度对 n-gram 进行排序

   List: 为匹配 n-g ra m 扫描链表， 如果需要， 插入一个新的元素

   Lower: 将字符串转换为小写字母

   Strlen: 计算字符串的长度

   Hash: 计算哈希函数

   Rest: 其他所有函数的和

   如图 5-38a 所示， 最初的版本需要 3. 5 分钟， 大多数时间花在了排序上。这并不奇怪， 因为插入排序有二次 的运行时间， 而程序对 363 039 个值进行排序。

   在下一个版本中 ， 我们用库函数 qs or t 进行排序， 这个函数是基于快速排序算法的

   [ 98] , 其预期运行时 间为 O( nlogn ) 。在图中这个版本称为 " Q uicksort" 。更有效的排序算

第 5 章 优 化 程序 性 能 391

法使花在排序上的 时间降低到可以忽略不计， 而整个运行时间降低到大约 5. 4 秒。图 5-38b

是剩下各个版本的时间，所用的比例能使我们看得更清楚。

250

200L 尸

,沪 150 +–

记u 100士 —

50 +—

。

6

5

i 4 #

Initial

－Quicksort －Iter first

lter last Big table Better hash Linear lower

a ) 所有的版本

U二p.. 3

2

Quicksort

Iter first

lter last Big table Better hash Linear lower

b ) 除了最慢的版本外的所有版本

图 5-38 big ram 频度计数程序的各个 版本的剖析结果。时间是 根据程序中 不同的 主要操作划分的

．改进了排序，现在发现链表扫描变成了瓶颈。想想这个低效率是由于函数的递归结构 引起的， 我们用一个 迭代的结构替换它， 显示为 " It e r fi r s t " 。令人奇 怪的是， 运行时 间增加到了大 约 7. 5 秒。根据更近一步的研究，我 们发现两个链表函数之间有一个细微的差 别。递归 版本将新元 素插入到链 表尾部 ， 而迭代版本 把它们插到链表头部。为了使性能最大化， 我们希望频 率最高的 n- g ra m 出现在链表的开始处。这样一来， 函数就能快速地定位常见 的情况。假设 n- g r a m 在文档中是均匀分布的 ， 我们期望频度高的单词的第一次出现在频度 低的单词之前。通过将新的 n- g ra m 插入尾部， 第一个函数倾向于按照频度的降序排序，而第二个函数则相反。因此我们创建第三个链表扫描函数，它使用迭代，但是将 新元素插 入到链表的尾部。使用这个版本， 显示为 " lt er last", 时间降到了大约 5. 3 秒， 比递归版本稍微 好一点。这些测量展示了对 程序 做实验作 为优化工 作一部分的重要性。开始时，我们假设将递归代码转换成迭代代码会改进程序的性能，而没有考虑添加元素到链 表末尾和开头的差别。

接下来 ，我们 考虑哈希表的结 构。最初的版本只有 10 21 个桶（通常会选择桶的个数为质数，以 增强哈希 函数将关键字均匀分布在桶中的 能力）。对于一个有 363 039 个条目的表来说 ， 这就意味着平均负 栽(l oad ) 是 363 039 / 1021 = 355. 6。这就解释了为什 么有那么多时间花在了 执行链表操作 上了一 搜索包括测试大量的候选 n- g ra m 。它还解释了为什么性能对链表的 排序这么敏感。然后， 我们将桶的数量增加到了 199 999 , 平均负载降低到了

1. 8。不过， 很奇怪的是， 整体运行时间 只下降到 5. 1 秒， 差距只有 0. 2 秒。

   进一步观察，我们可以看到，表变大了但是性能提高很小，这是由于哈希函数选择的 不好。简单地对字符串的字符编码求和不能产生一个大范围的值。特别是，一个字母最大 的编码值是 122 , 因而 n 个字符产生的和最多是 122n 。在文档中， 最长的 big ra m( " honor­ 巾 ca b小t udinita ti bus t ho u" ) 的和也不过是 3371 , 所以，我们哈希表中大多数桶都是不会被使用的。此外，可交换的哈希函数，例如加法，不能对一个字符串中不同的可能的字符顺 序做出区分。例如， 单词 " ra t" 和 " t ar" 会产生同样的和。

   我们 换成一个使用移位和异或操作的哈希函数。使用这个版本， 显示为 " Better

   Hash", 时间下降到了 0. 6 秒。一个更加系统化的 方法是更加仔细地研究关键字在桶中的分布，如果哈希函数的输出分布是均匀的，那么确保这个分布接近于人们期望的那样。

   最后，我 们把运行时间降到了大部分时间是花在 s tr l e n 上， 而大多数对 s tr l e n 的调用是作为小写字母转换的一部分。我们已 经看到了函数 l o wer l 有二次的性能， 特别是对长字符串来说。这篇文档中的单词足够短，能避免二次性能的灾难性的结果；最长的 bigra m 只有 32 个字符 。不过换成使用 l ower 2 , 显示为 " L inea r Low e r " 得到很好的性能， 整个时间降 到了 0. 2 秒。

   通过这个练习，我们展示 了代码剖析能够帮 助将一个简单应用程序所需的时间从 ,3. 5 分 钟降低到 0. 2 秒， 得到的性 能提升约为 1000 倍。剖析程序帮助我们把注意 力集中在程序最耗时的部分上，同时还提供了关于过程调用结构的有用信息。代码中的一些瓶颈，例 如二次的排序函数，很容易看出来；而其他的，例如插入到链表的开始还是结尾，只有通 过仔细的分析才能看出。

   我们可以看到，剖析是工具箱中一个很有用的工具，但是它不应该是唯一一个。计时测量不是很准确 ， 特别是对较短的运行时间（小于 1 秒）来说。更重要的是 ，结 果只适用于被测试的那些特殊的数据。例如，如果在由较少数扯的较长字符串组成的数据上运行最初的函 数，我们会发现小写字母转换函数才是主要的性能瓶颈。更糟糕的是，如果它只剖析包含短单词的文档， 我们可能永远 不会发现隐藏着的性能瓶颈， 例如 l ower l 的二次性能。通常， 假设在有代表性的数据上运行程序，剖析能帮助我们对典型的情况进行优化，但是我们还应该确保对所有可能的 情况，程序 都有相当的性能。这 主要包括避免得到糟 糕的渐近性能 (as­ ymptotic performance) 的算法（例如插入算法）和坏的编程实践（如例 l owe rl ) 。

   1. 9. 1 中讨论了 Amdahl 定律， 它为通过有针对性的优化来获取性能提升提供了一些其他的见解。 对千 n-gra m 代码来说 ， 当用 q uickso r t 代替了插入排序后，我 们看到总的执行 时间从 209. 0 秒下降到 5. 4 秒。初始版本的 20 9. 0 秒中的 203. 7 秒用于执行插入排序， 得到 a = 0. 974 , 被此次优化加速的时间比例。使用 q uicksort, 花在排序上的时间变得微不足道，得到 预计的 加速比为 209/ a = 39 . O, 接近千测量加速比 38. 5。我们之所以能获得大的加速比，是因为排序在整个执行时间中占了非常大的比例。然而，当一个瓶颈消除， 而新的瓶颈出现时，就需要关注程序的其他部分以获得更多的加速比。

5. 15 小结

虽然关于代码优化的大多数论述都描述了编译器是如何能生成高效代码的，但是应用程序员有很多方 法来协助编译器完成这项任务 。没有 任何编译器能用一 个好的算法或数据结构代替 低效率的算法或数据结构， 因此程序设计的这些方面仍然应该是程序员 主要关心的 。我们 还看到 妨碍优化的 因素， 例如内存别名使用 和过程调用 ， 严重限制了编译器执行大量优化的能力。同样， 程序员 必须对消除这些妨碍优化的因素负主要的责任。这些应该被 看作好的编程习惯的一部分， 因为它们可以用来消除不必要的工作。

基本级别之外调整性能需要一些对处 理器微体系结构的理解，描 述处理器用来实现它的指令集体系结构的底 层机制。对千乱序处理器的情况，只 需 要 知 道一些关千操作、容量、延迟和功能单元发 射时间的信息 ， 就能够基本地预测程序的性能了。

我们研究了一系列技术，包括循环展开、创建多个累积变榄和重新结合，它们可以利用现代处理器 提供 的指 令级并 行 。随 着对 优化的深入，研究 产 生 的 汇编代码以及试着理解机器如何执行计算变得重要起来 。确认 由程序中的数据相关决定的关键路径， 尤其是循环的不同迭代之间的数据相关 ，会 收获良多。我们还可以 根据必 须要计算的操作数量以及执行这些操作的功能单元的数噩和发射时间， 计 算 一 个 计 算的吞吐扯 界限。

包含条 件分支或与内存系统复杂交互的程序， 比我们最开始考虑的简单循环程序，更 难 以 分 析和优化。基本策 略是使分支更容易 预测，或 者使它们很容易用条件数据传送来实现。我们还必须注意存储和加载操 作。将数值保存在局部变量中，使 得 它 们可以存放在寄存器中 ， 这会很有帮助。

当处理大型程序时 ，将 注意力集中在最耗时的部分变得很重要。代 码剖析程序和相关的工具能帮助我们系 统地评价 和改进程序性 能。我们描述了 GP RO F , 一个标准的 U nix 剖 析工具。还有更加复杂完善的剖析 程序可用 ，例 如 Intel 的 VT U NE 程序开发系统， 还有 Linux 系统 基本上都有的 V ALGRIND。这些工具可以在过程级分韶执行时间，估 计 程序每个基本块( basic block ) 的性能。（基本块是内部没有控制转移的指令 序列，因 此基本块 总是 整个 被执行的。）

参考文献说明 #

我们的关注点是从程序员的角度描述代码优化，展示如何使书写的代码能够使编译器更容易地产生 高效的代码。Chellappa 、F ranchetti 和 P uschel 的扩展的论文[ 19] 采用了类似的方法，但 关 于处 理 器的特性描述 得更详细。

有许 多著作从编译器的角度描述了代码优化， 形 式 化 描 述 了 编 辑器可以产生更有效 代码的方法。Muchni ck 的著作被认为是最全面的[ 80] 。Wad leig h 和 Cra wfo r d 的关于软件优化的著作[ 115] 覆盖了一些 我们已经谈到的内容， 不 过它还描述了在并行机器上获得高性能的过程。Mahlke 等人的一篇比较早期的论文[ 75] , 描述了几种为编译器开发的将程序映射到并行机器上的技术，它们是如何能够被改造成利用现代处理器的指令级并行的。这篇论文覆盖了我们讲过的代码变换，包括循环展开、多个累积变扯（他们 称之为 累积变量 扩展 ( accum ula tor va ria ble expans io n ) ) 和 重新结合（他们称之为树 高 度 减 少 ( t ree h e ig h t reduct io n) ) 。

我们对乱序处理器的 操作的描述相当简单和抽象。可以 在高级计算机体系结构教科书中找到对通用原则更完整的 描述，例 如 H enness y 和 Pa tt erson 的著作[ 46 , 第 2~ 3 章］。S he n 和 L ipas t i 的 书[ 1 00 ] 提供了对现代处理器设计深人的论述。

家庭作业 #

•• 5. 13 假设 我们想编写一个计算两个向量 u 和 v 内积的过程。这个函数的一个抽象版本对整数和浮点数类型， 在 x86-64 上 C PE 等于 14 ~ 18 。 通过进行与我们将 抽象 程序 c ombi n e l 变换 为更有效的

c ombi ne 4 相同 类型的变换， 我们得到如下代码：

I* Inner product. Acc umul at e in t emp ro ar y *I

vo i d i nner 4 ( ve c_ptr u, vec_ptr v, data_t *dest)

｛

long i;

long length= vec_length(u); data_t *udata = get _vec _s t ar t (u) ; data_t *Vdata = get_vec_start(v); data_t sum = (data_t) O;

for (i = O; i < length; i++) {

sum= sum+ udata[i] * vdat a [i ] ;

｝

*dest = sum;

测试显示 ， 对千整数这个函数的 CP E 等于 1. 50 , 对千浮点 数据 C PE 等于 3. 00 。对于数据类型 d o ub l e , 内循环的 x86-64 汇编代码如下 所示：

Inner loop of i nner 4. dat a_t = double, OP=,.

udata in %r bp, vdata in %rax, sum in %xmm0 i in %rcx, lim1t in %rbx

.L15:

vmovsd vmulsd vaddsd addq cmpq jne

0(%rbp,%rcx,8), %xmm1 (%rax,%rcx,8), %xmm1, %xmm1

%xmm1, %xmm0, %xmm0

$1, %rcx

%rbx, %rcx

.L15

loop.

Get udata[i] Multiply by vdata[i] Add to s 皿

Increment i Compare i : limit If 1=, goto loop

• 5. 14
• 5. 15
• 5. 16

** 5. 17

假设功能单元的特性如图 5-12 所示。

1. 按照图 5-13 和图 5-14 的风格，画出这个 指令序列会如何被译码成操作， 并给出它们之间的数据相关如何形成一条操作的关键路径。

2. 对于数据类型 do ub l e , 这条关键路径决定的 CP E 的下界是什么？

3. 假设对于整数代码也有类 似的 指令序列 ， 对于整数数据的关 键路径决定的 CPE 的下界是什么？

4. 请解释虽然乘法操作需要 5 个时钟周期， 但是为什么两个 浮点版本的 CP E 都是 3. 00。

   编写习题 5. 13 中描述的内 积过程的一个版本， 使用 6 X l 循环展开。对 于 x86-64 , 我们对这个展开的版本的测试 得到，对整数数据 CP E 为 1. 07, 而对两种 浮点数据 CP E 仍然为 3. 01 。

5. 解释为什么 在 Intel Core i7 H aswell 上运行的 任何（标盘）版本的内积过程都不能 达到比 1. 00 更小 的 C PE 了 。

6. 解释为什么对浮点数据的性能不会通过循环展开而得到提高。

   编写习题 5. 13 中描述的内积过程的一个版本 ， 使用 6 X 6 循环展开。对 千 x86-6 4 , 我们对这个函数的测试得到对整数数据的 CP E 为 1. 06, 对浮点数据的 CP E 为 1. 01 。

   什么因素制约了性能 达到 CP E 等于 1. 00?

   编写习题 5. 13 中描述的内积 过程的一 个版本， 使用 6 X l a 循环展开产生更高的并行性。我们对这个函数的测试得到对 整数数据的 CP E 为 1. 10, 对浮点数 据的 CP E 为 1. 05 。

   库函数 me ms e t 的原型如下：

   void•memset(void•s, int c, size_t n);

这个函数将从 s 开始的 n 个字节的内存区域都填 充为 c 的低位字节。例如，通 过将参数 c 设置为

0, 可以用这个函数来对一个内存区域清零，不过用其他值也是可以的。下面是 me ms e t 最直接的实现 ：

I• Basic implementation of memset•I void•basic_memset(void•s, int c, size_t n)

｛

size_t cnt = O;

unsigned char•schar = s; while (cnt < n) {

•schar++ = (unsigned char) c; cnt++;

｝

returns;

｝

实现该函数一 个更有效的 版本， 使用数据类型为 uns i g ne d l ong 的字来装下 8 个 C, 然后用字级的写遍历目标内存区域 。你可能发现增 加额外 的循环展 开会有所帮助。在我们 的参考机上， 能 够把 C P E 从直接实 现的 1. 00 降低到 o. 127。即， 程序每个 周期可以写 8 个字节。

这里是一些 额外的 指导原则。在此，假 设 K 表示 你运行程序的 机器上的 s i ze o f (unsigned l o ng ) 的 值。

**5. 18

·: 5. 19

• 你不可以调用任何库函数。

• 你的代码应该 对任意 n 的值都能工作， 包括当它不是 K 的倍数的时候。你可以用 类似于使用循环展开时完成最后几次迭代的方法做到这一点。

• 你写的代码应该无论 K 的值是多 少，都 能够正确编译 和运行。使用操作 s i ze o f 来做到这一点 。

• 在某些机器上 ， 未对齐的写可能比对齐的写 慢很多。（在某些非 x8 6 机器上 ， 未对齐的写甚至可能会导致段错误。）写出这样的代码， 开始时 直到目的 地址是 K 的倍数时，使用 字节级的写，然后进行字级的写，（如果需要）最后采用用字节级的写 。

• 注意 c n t 足够小以 至于一些 循环上界变成负数的情 况。对 千涉及 s i ze o f 运算符的 表达式 ，可以用无符号运算来执行测试。（参见 2. 2. 8 节和家庭作 业 2. 72。)

  在练习题 5. 5 和 5. 6 中我们考虑了多项式求值的任务，既 有直接求 值， 也有用 H orner 方法求 值。试着用我们讲过的优化技术写出这个函数更快的版本，这些技术包括循环展开、并行累积和重新 结合。你会发现有很多 不同的方法可以将 H o rner 方法和直接求值与这些 优化技术混合起来。

  理想状况下 ， 你能达到的 CPE 应该接近于你的 机器的吞吐盘界限 。我们的 最佳版本在参 考机上能

  使 CPE 达到 1. 07。

  在练习题 5. 12 中 ，我们能 够把前置和计算 的 CPE 减少到 3. 00, 这是由该机器上浮点加法的延迟决定的。简单的循环展开没有改 进什么 。

  使用循环展开和重新结 合的组合，写 出求前 置和的代码， 能够得到一个小 于你机器上浮点 加法延迟的 CP E。要达到这个目标 ， 实际上需要增加执行的加法次数。例如，我 们使用 2 次循环展开的 版本每次迭代需 要 3 个加法 ， 而使用 4 次循环展开的版本需要 5 个。在参考机上， 我们的最佳实现能 达到 CPE 为 1. 67。

  确定你的机器的吞吐 益和延迟界限是 如何限制前 置和操作所能 达到的最小 CPE 的。

练习题 答 案 #

5. 1

5. 2

5. 4

这个问 题说明了内 存别名使用的 某些细微的 影响。

正如下面加了注释的代码所示 ，结 果会是将 xp 处的值设置为 0 :

•xp =•xp +•xp; /• 2x•/

•xp= • xp -•xp; I• 2x-2x = 0•/

•xp = • xp - • xp ; I• 0-0 = 0•I

这个示例说明我们关 于程序行 为的直觉往往会是错误 的。我们自然地会认 为 xp 和 yp 是不同的情况，却忽略了它们相等的可能性。错误通常源自程序员没想到的情况。

这个问 题说明了 CPE 和绝对性能之间的关 系。可以用初等代数解决这个问 题。我们发现对于 n 2 ,

版本 1 最快。对于 3 n 7 , 版本 2 最快 ， 而对于 n多8 , 版本 3 最快。

这是个简单 的练习，但是认识到一个 f or 循环的 4 个语句（初始化、测试、更新和循环体）执行的次数是不同的很重要。

这段汇编代码展示了 GCC 发现的一个 很聪明的优化 机会。要更 好地理解代码优化的细微之处， 仔细研究这段代码是很值得的。

1. 在没经过优 化的代码中，寄 存器%xrnm0 简单地被用 作临时值， 每次循环迭代 中都会设置和使用 。在经过更多 优化的代码中，它 被使用的 方式更像 c ombi ne 4 中的 变量 X , 累积向量元素的乘积。不过，与 c ombi ne 4 的区别 在于每次迭代第 二条 vmo v s d 指令都会更新位置 de s t 。

   我们可以 看到， 这个优化过的 版本运行起 来很像下 面的 C 代码：

I* Make sure dest updated on each iteration *I

2 void combi ne3 汃 vec _ptr v, data_t *dest)

3 {

long i;

1. long length = vec_length(v);

2. data_t *data = get_vec_start(v);

3. data_t ace = IDENT;

4. I* Initialize in event length <= 0 *I

5. *dest = ace;

6. for (i = O; i < length; i++) {

7. ace = a c e OP data [i] ;

   14 *dest = a ce · 15

   16 }

8. c o mbi ne 3 的两个版本有相同的功能， 甚至于相同的内存 别名使用。

9. 这个变换可以不 改变程序的行为 ， 因为，除 了 第一次迭代， 每次迭代 开始时从 d e 江 读出的值和前一次迭代最后写入到这个寄存器的值是相同的。因此，合并指令可以简单地使用在循环开始 时就已经在%x mm0 中的值。

10. 5 多项式求值是解决许多问题的核心技术。例如， 多 项式函数常常用作对数学库中三角函数求近似值。

    1. 这个函数执行 2n 个乘法和 n 个加法。
    2. 我们可以看到， 这里限制性能 的计算是反复地计算表达式 xp wr = x * xp wr 。这需要一个浮点数乘法( 5 个时钟周期），并且直到前 一次迭代完成 ， 下一次迭代的 计算才能开始。两次连续的迭代之间 ，对r e s u l t 的更新只需要一个浮点加法( 3 个时钟周期）。

11. 6 这道题说明了最小化一个计算中的操作数量不 一定会提高它的性能。

    1. 这个函数执行 n 个乘法和 n 个加法 ， 是原始函数 p o l y 中乘法数量的一半。

    2. 我们可以看到 ， 这里的性能限 制计算是反复地计算 表达式r e s u l 七=a [ i ) +x *r e s u l t 。从来自上一次迭代的r e s u l t 的值开始 ， 我们必须先把它乘以 x ( 5 个时钟周期）， 然后把它加上 a [习 (3 个时钟 周期）， 然后得到本次 迭代的值 。因此， 每次迭代 造成了最小 延迟时间 8 个周期 ， 正好等于我们 测最到的 CPE。

    3. 虽然函数 p o l y 中每次迭代需 要两个乘法， 而不是一个，但是只有一条乘法是 在每次 迭代的关键路径上出现。

       5. 7 下面的代码直接遵循了 我们对 K 次展开一个循环所阐述的规则：

       void unroll5(vec_ptr v, data_t *dest)

5. 8 这道题目说明了程序中小小的改动可能 会造成很大的 性能不 同，特别是在乱序执行的机器上。图 5-39 画出了该函数一 次迭代的 3 个乘法操作。在这张图中 ， 关键路径上的操作用黑 色方框表示 它们需要按照顺序计算 ， 计算出循环变最r 的新值。浅色方框表示的操作可以与关 键路径操作并 行地计算。对于一个 关键路径上有 P 个操作的循环 ， 每次迭代 需要最少 5 P 个时钟周期， 会计算出 3 个元素的乘积， 得到 C P E 的下界 5P / 3。也就是说， A l 的 下界为 5. 00 , A Z 和 A 5 的为 3. 33, 而 A 3 和

A4 的为 1. 67。我们在 In t el Core i7 H as well 处理器上运行这些函数， 发现得到的 C P E 值与前述一致。

Al : ((r*x) *y)*z A2: (r* (x*y)) *z A3: r* ( (x * y ) *z) A4 : r* (x* (y* z ) )

, y i z l i r l x ! y l z '

图 5- 39 对于练习题 5. 8 中各种情况乘法操 作之间的数据相关。用黑色方框表示的操作形成了迭代的 关键路径

5. 9 这道题又说明了 编码风格上的小 变化能够让编译器更容易 地察觉到使用 条件传送的 机会：

while (il < n && i2 < n) { long vl = src1[i1];

l ong v2 = src2[i2]; long take!= v1 < v 2 ;

dest[id++] = take1? v1 : v2;

i1 += take!;

i2 += (1-take1);

对于这个版本的代码，我 们测量到 CP E 大约为 1 2. 0 , 比原始的 C P E 1 5. 0 有了明显的提高。

5. 10 这道题要求你分 析一个程序中潜在的加载－存储相互影响。

. A. 对于 O i 9 98 , 它要将每个元 素 a [ i ] 设置为 i + l 。

1. 对于 l i 999 , 它要将每个元 素 a [ i ] 设置为 0 。

2. 在第二种情 况中， 每次迭代的 加载都依赖于前一次迭代的存储结果 。因此，在连 续的迭代之间有写／读相关。

3. 得到的 C P E 等于 1. 2’ 与示例 A 的相同， 这是因为存储 和后续的加 载之间 没有相关。

   5. 11 我们 可以看到 ， 这个函数在连续的 迭代之间有写／读相关 一次迭代 中的目 的值 p [ i ] 与下一次迭代中的 源值 p [ i - l ] 相同。因此， 每次迭代形成的关键路径就包括： 一次存储（来自前一次迭代）， 一次加载和一次浮点加。当存在数 据相关时 ， 测扯得 到的 C P E 值为 9. 0 , 与 wr i t e —r e a d 的 C P E 测益值 7. 3 是一致的， 因为 wr i t e _r e a d 包括一个整数加 (1 时钟周期延迟）， 而 p s u ml 包括一个浮点加( 3 时钟周期延迟）。

   5. 12 下面是对这个 函数的一个修改版本：

   v oi d psum1a(float a[], float p[J , long n)

   2 {

   long i;

   4 I* last_val holds p[i 一 1] ; val holds p[i] *I

4. float last_val, val;

   6 last_val = p [OJ = a[O];

   7 for (i = 1; i < n; i++) {

   8 val = last_val + a [i] ;

   9 p[i] = val;

   10 last_val = va l ;

12 }

我们引 入了局部变量 l a s t _ va l 。在迭代 l. 的开始， l a s t —va l 保存着 p [ i - l ] 的值。然后我们计算va l 为 p [ i ] 的值， 也是 l a s t _ v a l 的新值。

这个版本编译得到如下汇编代码：

Inner loop of psumla

a 立 ％ 过 i , i 1n r¼ ax , cnt i n 石 dx, last_ val in 7.xmmO

.L16: l oop :

vaddss (%rdi,%rax,4), %xmm0, %xmm0 l as t _val = val = l as t _val + a[i]

vmovss %xmm0 ,

Cor。/

s i , /,r ax , 4 ) Store val in p[i]

addq $1, %rax Increment i

cmpq %rdx, %rax Compare i : cnt

jne .L16 If !=, goto l oop

这段代码将 l a s t _v a l 保存在%x mm0 中 ， 避免了需要从内存中读出 p [ i 一l ] •

看到的写／读相关。

因而消除了 ps urnl 中