并行视角下的硬件习性

大多数人根据直觉就知道，在系统间传递消息要比在单个系统上执行简单计算更加耗时。不过，在共享同一块内存的系统的线程间传递消息是不是也更加耗时，这点可就不一定了。本章主要关注共享内存系统中的同步和通信的开销，只涉及了一些共享内存并行硬件设计的皮毛，想了解更多信息的读者，可以翻看Hennessy和Patterson的经典教材最新版[HP95]。

小问题：为什么并行软件程序员需要如此痛苦地学习硬件的低级属性？如果只学习更高级些的抽象是不是更简单，更好，更通用？

概述

如果只是粗略地扫过计算机系统规范手册，很容易让人觉得CPU的性能就像在一条清晰跑道上的赛跑，如下图所示，总是最快的人赢得比赛。

虽然有一些只限于CPU的基准测试能够让CPU达到上图中显示的理想情况，但是典型的程序不像跑道，更像是一条带有障碍的道路。托摩尔定律的福，最近几十年间CPU的内部架构发生了急剧的变化。在后面的章节中将描述这些变化。

CPU流水线

在上世纪80年代初，典型的微处理器在处理下一条指令之前，至少需要取指，解码和执行3个时钟周期来完成本条指令。与之形成鲜然对比是，上世纪90年代末期和本世纪初的CPU可以同时处理多条指令，通过一条很长的“流水线”来控制CPU内部的指令流，图2.2显示了这种差异。

带有长流水线的CPU想要达到最佳性能，需要程序给出高度可预测的控制流。代码主要在紧凑循环中执行的程序，可以提供恰当的控制流，比如大型矩阵或者向量中做算术计算的程序。此时CPU可以正确预测在大多数情况下，代码循环结束后的分支走向。在这种程序中，流水线可以一直保持在满状态，CPU高速运行。

另一方面，如果程序中带有许多循环，且循环计数都比较小；或者面向对象的程序中带有许多虚对象，每个虚对象都可以引用不同的实对象，而这些实对象都有频繁被调用的成员函数的不同实现，此时CPU很难或者完全不可能预测某个分支的走向。这样CPU要么等待控制流进行到足以知道分支走向的方向时，要么干脆猜测——由于此时程序的控制流不可预测——CPU常常猜错。在这两种情况中，流水线都是空的，CPU需要等待流水线被新指令填充，这将大幅降低CPU的性能，就像图中的画一样。

不幸的是，流水线冲刷并不是唯一影响现代CPU运行性能的的障碍。下一节将讲述内存引用带来的危害。

内存引用

在上世纪80年代，微处理器从内存读取一个值的时间比执行一条指令的时间短。在2006年，同样是读取内存的时间，微处理器可以在这段时间执行上百条甚至上千条指令。这个差异来源于摩尔定律使得CPU性能的增长速度大大超过内存性能的增长速度，也有部分是由于内存大小的增长速度。比如，70年代的微型计算机通常带有4KB主存（是的，是KB，不是MB，更别提GB了），访问需要一个周期。到2008年，CPU设计者仍然可以构造单周期访问的4KB内存，即使是在几GHz时钟频率的系统上。事实上这些设计者经常构造这样的内存，但他们现在称呼这种内存为“0级cache”。

虽然现代微型计算机上的大型缓存极大地减少了内存访问延迟，但是只有高度可预测的数据访问模式才能让缓存发挥最大效用。不幸的是，一般像遍历链表这样的操作的内存访问模式非常难以预测——毕竟如果这些模式是可预测的，我们也就不会被指针所困扰了，是吧？

因此，正如图中显示的，内存引用常常是影响现代CPU性能的重要因素。

到现在为止，我们只考虑了CPU在单线程代码中执行时会遭遇的性能障碍。多线程会为CPU带来额外的性能障碍，我们将在下面的章节中接着讲述。

原子操作

其中一种障碍是原子操作。原子操作的概念在某种意义上与CPU流水线上的一次执行一条的汇编操作冲突了。拜硬件设计者的精密设计所赐，现代CPU使用了很多非常聪明的手段让这些操作看起来是原子的，即使这些指令实际上不是原子的。不过即使如此，也还是有一些指令是流水线必须延迟甚至需要冲刷，以便一条原子操作成功完成。

原子指令对性能的影响见上图。

不幸的是，原子操作通常只用于数据的单个元素。由于许多并行算法都需要在更新多个数据元素时，保证正确的执行顺序，大多数CPU都提供了内存屏障。内存屏障也是影响性能的因素之一，下一节将对它进行描述。

小问题：什么样的机器会允许对多个数据元素进行原子操作？

内存屏障

下面是一个简单的基于锁的临界区。

spin_lock(&mylock);

a = a + 1;

spin_unlock(&mylock);

如果CPU没有按照上述语句的顺序执行，变量”a”会在没有得到“mylock”保护的情况下加一，这肯定和我们取”a”的值的目的不一致。为了防止这种有害的乱序执行，锁操作原语必须包含或显式或隐式的内存屏障。由于内存屏障的作用是防止CPU为了提升性能而进行的乱序执行，所以内存屏障几乎一定会降低CPU性能，如下图所示。

Cache Miss

对多线程程序来说，还有个额外的障碍影响CPU性能提升——“Cache Miss”。正如前文提到的，现代CPU使用大容量的高速缓存来降低由于较低的内存访问速度带来的性能惩罚。但是，CPU高速缓存事实上对多CPU间频繁访问的变量起反效果。因为当某个CPU想去更改变量的值时，极有可能该变量的值刚被其他CPU修改过。在这种情况下，变量存在于其他CPU而不是当前CPU的缓存中，这将导致代价高昂的Cache Miss。如下图所示。

I/O操作

缓存未命中可以视为CPU之间的I/O操作，这应该是代价最低廉的I/O操作之一。I/O操作涉及网络、大容量存储器，或者（更糟的）人类本身，I/O操作对性能的影响远远大于之前几个章节提到的各种障碍，如下图所示。

共享内存式的并行计算和分布式系统式的并行计算的其中一个不同点是，共享内存式并行计算的程序一般不会处理比缓存未命中更糟的情况，而分布式并行计算的程序则很可能遭遇网络通信延迟。这两种情况的延迟都可看作是通信的代价——在串行程序中所没有的代价。因此，通信的开销占执行的实际工作的比率是一项关键设计参数。并行设计的一个主要目标是尽可能的减少这一比率，以达到性能和可扩展性上的目的。

当然，说I/O操作属于性能障碍是一方面，说I/O操作对性能的影响非常明显则是另一方面。下面的章节将讨论两者的区别。

开销

本节将概述前一节列出的性能障碍的实际开销。不过在此之前，需要读者对硬件体系结构有一个粗略认识，下一小节将对该主题进行阐述。

硬件体系结构

上图是一个粗略的八核计算机系统概要图。每个管芯有两个CPU核，每个核带有自己的高速缓存，管芯内还带有一个互联模块，使管芯内的两个核可以互相通信。在图中央的系统互联模块可以让四个管芯相互通信，并且将管芯与主存连接起来。

数据以“缓存线”为单位在系统中传输，“缓存线”对应于内存中一个2的幂大小的字节块，大小通常为32到256字节之间。当CPU从内存中读取一个变量到它的寄存器中时，必须首先将包含了该变量的缓存线读取到CPU高速缓存。同样地，CPU将寄存器中的一个值存储到内存时，不仅必须将包含了该值的缓存线读到CPU高速缓存，还必须确保没有其他CPU拥有该缓存线的拷贝。

比如，如果CPU0在对一个变量执行“比较并交换”（CAS）操作，而该变量所在的缓存线在CPU7的高速缓存中，就会发生以下经过简化的事件序列：

1. CPU0检查本地高速缓存，没有找到缓存线。

2. 请求被转发到CPU0和CPU1的互联模块，检查CPU1的本地高速缓存，没有找到缓存线。

3. 请求被转发到系统互联模块，检查其他三个管芯，得知缓存线被CPU6和CPU7所在的管芯持有。

4. 请求被转发到CPU6和CPU7的互联模块，检查这两个CPU的高速缓存，在CPU7的高速缓存中找到缓存线。

5. CPU7将缓存线发送给所属的互联模块，并且刷新自己高速缓存中的缓存线。

6. CPU6和CPU7的互联模块将缓存线发送给系统互联模块。

7. 系统互联模块将缓存线发送给CPU0和CPU1的互联模块。

8. CPU0和CPU1的互联模块将缓存线发送给CPU0的高速缓存。

9. CPU0现在可以对高速缓存中的变量执行CAS操作了。

小问题：这是一个简化后的事件序列吗？还有可能更复杂吗？

小问题：为什么必须刷新CPU7高速缓存中的缓存线？

操作的开销

一些在并行程序中很重要的常见操作开销如下所示。该系统的时钟周期为0.6ns。虽然在现代微处理器上每时钟周期retire多条指令并不常见，但是在表格的第三列，操作被标准化到了整个时钟周期，称作“比率”。关于这个表格，第一个需要注意的是比率的值都很大。

4-CPU 1.8GHz AMD Opteron 844系统

最好情况下的CAS操作消耗大概40纳秒，超过60个时钟周期。这里的“最好情况”是指对某一个变量执行CAS操作的CPU正好是最后一个操作该变量的CPU，所以对应的缓存线已经在CPU的高速缓存中了，类似地，最好情况下的锁操作（一个“round trip对”包括获取锁和随后的释放锁）消耗超过60纳秒，超过100个时钟周期。这里的“最好情况”意味着用于表示锁的数据结构已经在获取和释放锁的CPU所属的高速缓存中了。锁操作比CAS操作更加耗时，是因为锁操作的数据结构中需要两个原子操作。

缓存未命中消耗大概140纳秒，超过200个时钟周期。需要在存储新值时查询变量的旧值的CAS操作，消耗大概300纳秒，超过500个时钟周期。想想这个，在执行一次CAS操作的时间里，CPU可以执行500条普通指令。这表明了细粒度锁的局限性。

小问题：硬件设计者肯定被要求过改进这种情况！为什么他们满足于这些单指令操作的糟糕性能呢？

I/O操作开销更大。一条高性能（也是高价的）光纤通信，比如Infiniand或者其他私有的 interconnects，它的通讯延迟大概有3微秒，在这期间CPU可以执行5000条指令。基于某种标准的通信网络一般需要一些协议的处理，这更进一步增加了延迟。当然，物理距离也会增加延迟，理论上光速绕地球一周需要大概130毫秒，这相当于2亿个时钟周期。

小问题：这些数字大的让人发疯！我怎么才能记住它们？

硬件的免费午餐

最近几年并行计算受到大量关注的主要原因是摩尔定律的终结，摩尔定律带来的单线程程序性能提升（或者叫“免费午餐”[Sut08]）也结束了。本节简短地介绍一些硬件设计者可能采用的办法，这些办法可以带来某种形式上的“免费午餐”。

不过，前文中概述了一些影响并发性的硬件障碍。其中对硬件设计者来说最严重的一个限制莫过于有限的光速。在一个1.8GHz的时钟周期内，光只能在真空中传播大约8厘米远。在5GHz的时钟周期内，这个距离更是降到3厘米。这个距离对于一个现代计算机系统的体积来说，还是太小了点。

更糟糕的是，电子在硅中的移动速度比真空中的光慢3到30倍，比如，内存引用需要在将请求发送给系统的其他部分前，等待查找本地缓存操作结束。此外，相对低速和高耗电的驱动器需要将电信号从一个硅制管芯传输到另一个管芯，比如CPU和主存间的通信。

不过，以下（包括硬件和软件的）技术也许可以改善这一情况：

1. 3D集成，

2. 新材料和新工艺，

3. 用光来替换电子，

4. 专用加速器，

5. 已有的并行计算软件。

在下面的小节中将会分别介绍这些技术。

3D集成

不过，由于时钟逻辑级别造成的延迟是无法通过3D集成的方式降低的，并且必须解决诸如生产、测试、电源和散热等3D集成中的重大问题。散热问题需要用基于钻石的半导体来解决，钻石是热的良好导体，但却是电的绝缘体。据说生成大型单晶体钻石仍然很困难，更别说将钻石切割成晶圆了。另外，看起来上述这些技术不大可能让性能出现指数级增长，如同某些人习惯的那样。

新材料和新工艺

据说斯蒂芬·霍金曾经声称半导体制造商面临两个基本问题：（1）有限的光速，（2）物质的原子本质。半导体制造商很有可能已经逼近这两个限制，不过有一些研究报告和开发过程关注于如何规避这两个基本闲置。

其中一个规避物质的原子本质的办法是一种称为“high-K”绝缘体材料，这种材料允许较大的设备模拟较小型设备的电气属性。这种材料存在一些严重的生产困难，但是能让研究的前沿再向前推进一步。另一个比较奇异的规避方法，根据电子可以存在于多个能级之上的事实，在电子中存储多个二进制位。不过这种方法还有待观察，确定能否在生产的半导体设备中稳定工作。

还有一种称为“量子点”的规避方法，使得可以制造体积小得多的半导体设备，不过该方法还处于研究阶段。

虽然光速是一个很难跨越的限制，但是半导体设备更多的是受限于电子移动的速度，而非光速，在半导体材料中移动的电子速度仅是真空中光速的3%到30%。在半导体设备间用铜来连接是一种提升电子移动速度的方法，并且出现其他技术让电子移动速度接近光速的可能性是很大的。另外，还有一些实验用微小的光纤作为芯片内和芯片间的传输通道，因为在玻璃中的光速能达到真空中光速的60%还多。这种方法存在的一个问题是光电/电光转换的效率，会产生电能消耗和散热问题。

这也就是说，除开在物理学领域的基础性进展以外，任何让数据流传输速度出现指数级增长的想法都受限于真空中的光速。

专用加速器

用通用CPU来处理某个专门问题，通常会将大量的时间和能源消耗在一些与当前问题无关的事项上。比如，当对一对向量进行点积操作时，通用CPU一般会使用一个带循环计数的循环（一般是展开的）。对指令解码、增加循环计数、测试计数和跳转回循环的开始处，这些操作在某种意义上来说都是无用功：真正的目标是计算两个向量对应元素的乘积。因此，在硬件上设计一个专用于向量乘法的部件会让这项工作做的既快速又节能。

这就是在很多商用微处理器上出现向量指令的原因。这些指令可以同时操作多个数据，能让点积计算减少解码指令消耗和循环开销。

类似的，专用硬件可以更有效地进行加密/解密、压缩/解压缩、编码/解码和许多其他的任务。不过不幸的是，这种效率提升不是免费的。包含特殊硬件的计算机系统需要更多的晶体管，即使在不用时也会带来能源消耗。软件也必须进行修改以利用专用硬件的长处，同时这种专门硬件又必须足够通用，这样高昂的up-front设计费用才能摊到足够多的用户身上，让专用硬件的价钱变得可以承受。部分由于以上经济考虑，专用硬件到目前为止只在几个领域出现，包括图形处理（GPU），矢量处理器（MMX、SSE和VMX指令），以及相对规模较小的加密领域。

不过，随着摩尔定律带来的单线程性能提升的结束，我们可以安全的预测：未来各种各样的专用硬件会大大增加。

现有的并行软件

虽然多核CPU曾经让计算机行业惊讶了一把，但是事实上基于共享内存的并行计算机已经商用了超过半个世纪了。这段时间足以让一些重要的并行软件登上舞台，事实也确实如此。并行操作系统已经非常常见了，比如并行线程库，并行关系数据库管理系统和并行数值计算软件。这些现有的并行软件在解决我们可能遇见的并行难题上已经走了很长一段路。

也许最常见的例子是并行关系数据库管理系统。它和单线程程序不同，并行关系数据库管理系统一般用高级脚本语言书写，并发地访问位于中心的关系数据库。在现在的高度并行化系统中，只有数据库是真正需要直接处理并行化的。因此它运用了许多非常好的技术。

软件设计

操作的开销表格中的比率值至关重要，因为它们限制了并行计算程序的效率。为了弄清这点，我们假设一款并行计算程序使用了CAS操作来进行线程间通信。假设进行通信的线程不是与自身而主要是与其他线程通信，那么CAS操作一般会涉及到缓存未命中。进一步假设对应每个CAS通信操作的工作需要消耗300纳秒，这足够执行几个浮点transendental函数了。其中一半的执行时间消耗在CAS通信操作上！这也意味着有两个CPU的系统运行这样一个并行程序的速度，并不比单CPU系统运行一个串行执行程序的速度快。

在分布式系统中结果还会更糟糕，因为单次通信操作的延迟时间可能和几千条甚至上百万条浮点操作的时间一样长。这就说明了会产生大量工作量的通信操作应该尽可能减少。

小问题：既然分布式系统的通信操作代价如此昂贵，为什么人们还要使用它？

总结

并行算法必须将每个线程设计成尽可能独立运行的线程。越少使用线程间通信手段，比如原子操作、锁或者其它消息传递方法，应用程序的性能和可扩展性就会更好。简而言之，想要达到优秀的并行性能和可扩展性，就意味着在并行算法和实现中挣扎，小心的选择数据结构和算法，使用现有的并行软件和环境，或者将并行问题转换成已经有并行解决方案存在的问题。