并行编程的演化

一个自然而然的问题是：为什么要用并行编程？在20世纪70年代、80年代甚至90年代的一部分时间里，我们对单线程编程（或者称为串行编程）非常满意。你可以编写一个程序来完成一项任务。执行结束后，它会给你一个结果。任务完成，每个人都会很开心！虽然任务已经完成，但是如果你正在做一个每秒需要数百万甚至数十亿次计算的粒子模拟，或者正在对具有成千上万像素的图像进行处理，你会希望程序运行得更快一些，这意味着你需要更快的CPU。

在2004年以前，CPU制造商IBM、英特尔和AMD都可以为你提供越来越快的处理器，处理器时钟频率从16 MHz、20 MHz、66 MHz、100 MHz，逐渐提高到200 MHz、333 MHz、466 MHz⋯⋯看起来它们可以不断地提高CPU的速度，也就是可以不断地提高CPU的性能。但到2004年时，由于技术限制，CPU速度的提高不能持续下去的趋势已经很明显了。这就需要其他技术来继续提供更高的性能。CPU制造商的解决方案是将两个CPU放在一个CPU内，即使这两个CPU的工作速度都低于单个CPU。例如，与工作在300 MHz速度上的单核CPU相比，以200 MHz速度工作的两个CPU（制造商称它们为核心）加在一起每秒可以执行更多的计算（也就是说，直观上看2×200 > 300）。

听上去像梦一样的“单CPU多核心”的故事变成了现实，这意味着程序员现在必须学习并行编程方法来利用这两个核心。如果一个CPU可以同时执行两个程序，那么程序员必须编写这两个程序。但是，这可以转化为两倍的程序运行速度吗？如果不能，那我们的2×200 > 300的想法是有问题的。如果一个核心没有足够的工作会怎么样？也就是说，只有一个核心是真正忙碌的，而另一个核心却什么都不做？这样的话，还不如用一个300 MHz的单核。引入多核后，许多类似的问题就非常突出了，只有通过编程才能高效地利用这些核心。

核心越多，并行性越高

程序员不能简单地忽略CPU制造商每年推出的更多数量的核心。2015年，英特尔在市场上推出8核台式机处理器i7-5960X[11]和10核工作站处理器，如Xeon E7-8870 [14]。很明显，这种多核狂热在可预见的未来会持续下去。并行编程从2000年年初的一种奇异的编程模型转变为2015年唯一被接受的编程模型。这种现象并不局限于台式电脑。在移动处理器方面，iPhone和Android手机都有2个或4个核。预计未来几年，移动领域的核心数量将不断增加。

那么，什么是线程？要回答这个问题，让我们来看看8核INTEL CPU i7-5960X [11]。 INTEL的文档说这是一个8C/16T CPU。换句话说，它有8个核心，但可以执行16个线程。你也许听到过并行编程被错误地称为多核编程。正确的术语应该是多线程编程。这是因为当CPU制造商开始设计多核架构时，他们很快意识到通过共享一些核心资源（如高速缓存）来实现在一个核心中同时执行两项任务并不困难。

类比1.1：核心与线程

图1-1显示了两个兄弟Fred和Jim，他们是拥有两台拖拉机的农民。每天，他们开车从农舍到椰子树所在的地方，收获椰子并把它们带回农舍。他们用拖拉机内的锤子来收获（处理）椰子。整个收获过程由两个独立但有序的任务组成，每个任务需要30秒：任务1是从拖拉机走向椰子树，每次带回1颗椰子。任务2是用锤子敲碎（处理）它们，并将它们存放在拖拉机内。Fred每分钟可以处理1颗椰子，而Jim每分钟也可以处理1颗椰子。综合起来，他们俩每分钟可以处理2颗椰子。

一天，Fred的拖拉机发生了故障。他把拖拉机留在修理厂，并把椰子锤忘在了拖拉机内。回到农舍的时候已经太迟了，但他们仍然有工作要做。只使用Jim的拖拉机和里面的1把椰子锤，他们还能每分钟处理2颗椰子吗？

核心与线程

让我们来看看图1-1中描述的类比1.1。如果收获1颗椰子需要完成两个连续的任务（我们将它们称为线程）：线程1从树上摘取1颗椰子并花费30秒将它带回拖拉机，线程2花费30秒用拖拉机内的锤子敲碎（处理）该椰子，这样可以在60秒内收获1颗椰子（每分钟1颗椰子）。如果Jim和Fred各自都有自己的拖拉机，他们可以简单地收获两倍多的椰子（每分钟2颗椰子），因为在收获每颗椰子时，他们可以共享从拖拉机到椰子树的道路，并且他们各自拥有自己的锤子。

在这个类比中，一台拖拉机就是一个核心，收获一颗椰子就是针对一个数据单元的程序执行。椰子是数据单元，每个人（Jim、Fred）是一个执行线程，需要使用椰子锤。椰子锤是执行单元，就像核心中的ALU一样。该程序由两个互相依赖的线程组成：在线程1执行结束之前，你无法执行线程2。收获的椰子数量意味着程序性能。性能越高，Jim和Fred销售椰子挣的钱就越多。可以将椰子树看作内存，你可以从中获得一个数据单元（椰子），这样在线程1中摘取一颗椰子的过程就类似于从内存中读取数据单元。

并行化更多的是线程还是核心

现在，让我们看看如果Fred的拖拉机发生故障后会发生什么。过去他们每分钟都能收获两颗椰子，但现在他们只有一台拖拉机和一把椰子锤。他们把拖拉机开到椰子树附近，并停在那儿。他们必须依次地执行线程1（Th1）和线程2（Th2）来收获1颗椰子。他们都离开拖拉机，并在30秒内走到椰子树那儿，从而完成了Th1。他们带回挑好的椰子，现在，他们必须敲碎椰子。但因为只有1把椰子锤，他们不能同时执行Th2。Fred不得不等Jim先敲碎他的椰子，并且在Jim敲碎后，他才开始敲。这需要另外的30+30秒，最终他们在90秒内收获2颗椰子。虽然效率不如每分钟2颗椰子，但他们的性能仍然从每分钟1颗提升至每分钟1.5颗椰子。

收获一些椰子后，Jim问了自己一个问题：“为什么我要等Fred敲碎椰子？当他敲椰子时，我可以立即走向椰子树，并摘获下1颗椰子，因为Th1和Th2需要的时间完全相同，我们肯定不会遇到需要等待椰子锤空闲的状态。在Fred摘取1颗椰子回来的时候，我会敲碎我的椰子，这样我们俩都可以是100%的忙碌。”这个天才的想法让他们重新回到每分钟2颗椰子的速度，甚至不需要额外的拖拉机。重要的是，Jim重新设计了程序，也就是线程执行的顺序，让所有的线程永远都不会陷入等待核心内部共享资源（比如拖拉机内的椰子锤）的状态。正如我们将很快看到的，核心内部的共享资源包括ALU、FPU、高速缓存等，现在，不要担心这些。

我在这个类比中描述了两个配置场景，一个是2个核心（2C），每个核心可以执行一个单线程（1T）；另一个是能够执行2个线程（2T）的单个核心（1C）。在CPU领域将两种配置称为2C/2T与lC/2T。换句话说，有两种方法可以让一个程序同时执行2个线程：2C/2T（2个核心，每个核心都可以执行1个线程—就像Jim和Fred的两台单独的拖拉机一样）或者lC/2T（单个核心，能够执行2个线程—就像Jim和Fred共享的单台拖拉机一样）。尽管从程序员的角度来看，它们都意味着具有执行2个线程的能力，但从硬件的角度来看，它们是非常不同的，这要求程序员充分意识到需要共享资源的线程的含义。否则，线程数量的性能优势可能会消失。再次提醒一下：全能的INTEL i7-5960X [11] CPU是8C/l6T，它有8个核心，每个核心能够执行2个线程。

图1-2显示了三种情况：a）是具有2个独立核心的2C/2T情况；b）是具有糟糕编程的1C/2T情况，每分钟只能收获1.5颗椰子；c）是对椰子锤的需求永远不会同时发生的顺序正确版本，每分钟可以收获2颗椰子。

核心资源共享的影响

Jim为自己的发现感到自豪，他们的速度提高到每分钟2颗椰子，Jim希望继续创造一些方法来用一台拖拉机完成更多的工作。一天，他对Fred说：“我买了一把新的自动椰子锤，它在10秒内就能敲碎1颗椰子。”他们对这一发现非常满意，立即出发并将拖拉机停在椰子树旁。这次他们知道在开始收获前必须先做好计划⋯⋯

Fred问道：“如果我们的Th1需要30秒，而Th2需要10秒，并且我们唯一需要共享资源的任务是Th2（椰子锤），我们应该如何收获椰子？”答案对他们来说很清楚：唯一重要的是线程的执行顺序（即程序的设计），应确保他们永远不会遇到两人同时执行Th2并需要唯一的椰子锤（即共享核心资源）的情况。换句话说，它们的程序由两个互相依赖的线程组成：Th1需要30秒，并且不需要共享（内存）资源，因为两个人可以同时步行到椰子树。Th2需要10秒并且不能同时执行，因为他们需要共享（核心）资源：椰子锤。由于每颗椰子需要30+10=40秒的总执行时间，他们能够期望的最好结果是40秒收获2颗椰子，如

图1-2 d所示。如果每个人都按顺序执行Th1和Th2，且不等待任何共享资源，则会发生这种情况。所以，他们的平均速度将是每分钟3颗椰子（即每颗椰子平均20秒）。

内存资源共享的影响

用新的椰子锤实现了每分钟收获3颗椰子后，Jim和Fred第二天开始工作时看到了可怕的一幕。因为昨晚的一场大雨阻塞了半边道路，从拖拉机到椰子树的道路今天只能由一个人通行。所以，他们再次制订计划⋯⋯现在，他们有2个线程，每个线程都需要一个不能共享的资源。Th1（30秒—表示为30s）只能由一人执行，而Th2（10s）也只能由一人执行。怎么办？

考虑多种选择后，他们意识到其速度的限制因素是Th1，他们能达到的最好目标是30秒收获1颗椰子。当可以同时执行Th1（共享内存访问）时，每个人可以顺序地执行10+30s，并且两个人都可以持续运行而无须访问共享资源。但是现在没有办法对这些线程进行排序。他们能够期望的最好结果是执行10+30s并等待20s，因为在此期间两人都需要访问内存。他们的速度回到平均每分钟2颗椰子，如图1-2 e所示。

这场大雨使他们的速度降低到每分钟2颗椰子。Th2不再重要，因为一个人可以不慌不忙地敲椰子，而另一个人正在去摘取椰子的路上。Fred提出了这样一个想法：他们应该从农舍再拿一把（较慢）椰子锤来帮忙。然而，这对于此时的情况绝对没有帮助，因为收获速度的限制因素是Th1。这种来自于某个资源的限制因素被称为资源竞争。这个例子展示了当访问内存是我们程序执行速度的限制因素时会发生什么。处理数据的速度有多快（即核心运行速度）已无关紧要。我们将受到数据获取速度的限制。即使Fred有一把可以在1秒钟内敲碎椰子的椰子锤，但如果存在内存访问竞争，他们仍然会被限制为每分钟2颗椰子。在本书中，我们将区分两种不同类型的程序：核心密集型，该类型不大依赖于内存访问速度；存储密集型，该类型对内存访问速度高度敏感，正如我刚才提到的那样。

第一个串行程序

我们已经理解了椰子世界中的并行编程，现在是时候将这些知识应用于真实计算机编程了。我会先介绍一个串行（即单线程）程序，然后将其并行化。我们的第一个串行程序imf?lip.c读入图1-3（左）中的小狗图片并将其水平（中）或垂直（右）翻转。为了简化程序的解释，我们将使用Bitmap（BMP）图像格式，并将结果也输出为BMP格式。这是一种非常容易理解的图像格式，可以让我们专注于程序本身。不要担心本章中的细节，它们很快就会被解释清楚，目前可以只关注高层的功能。

imflip.c源文件可以在Unix提示符下编译和执行，如下所示：

gcc imflip.c -o imflip
./imflip dogL.bmp dogh.bmp V

在命令行中用“H”指定水平翻转图像（图1-3中），用“V”指定垂直翻转（图1-3右侧）。你将看到如下所示的输出（数字可能不同，取决于你电脑的速度）：

Input BMP File name : dogL.bmp (3200×2400) 
Output BMP File name : dogh.bmp (3200×2400)
Total execution time : 81.0233 ms (10.550 ns per pixel)

运行该程序的CPU速度非常快，以致我必须将原始的640×480的图像dog.bmp扩展为3200×2400的dogL.bmp，这样它的运行时间才能被测量出来；dogL.bmp的每个维度扩大到原来的5倍，因此比dog.bmp大25倍。统计时间时，我们必须在图像翻转开始和结束时记录CPU的时钟。

理解数据传输速度

从磁盘读取图像的过程（无论是SSD还是硬盘驱动器）应该从执行时间中扣除，这很重要。换句话说，我们从磁盘读取图像，并确保它位于内存中（在我们的数组中），然后只统计翻转操作所需的时间。由于不同硬件部件的数据传输速度存在巨大差异，我们需要分别分析在磁盘、内存和CPU上花费的时间。

在本书将要编写的众多并行程序中，我们重点关注CPU执行时间和内存访问时间，因为我们可以控制它们。磁盘访问时间（称为I/O时间）通常在单线程中就达到极限，因而几乎看不到多线程编程的好处。另外，请记住，当我们开始GPU编程时，较慢的I/O速度会严重困扰我们，因为I/O是计算机中速度最慢的部分，并且从CPU到GPU的数据传输要通过I/O子系统的PCI express总线进行，因此我们将面临如何将数据更快地提供给GPU的挑战。没有人说GPU编程很容易！为了让你了解不同硬件部件的传输速度，我在下面列举了一些：

典型的网卡（NIC）具有1 Gbps的传输速度（千兆比特每秒或一亿比特每秒）。这些卡俗称“千兆网卡”或“Gig网卡”。请注意，1 Gbps只是“原始数据”的数量，其中包括大量的校验码和其他同步信号。传输的实际数据量少于此数量的一半。我的目的是给读者一个大致的概念，这个细节对我们来说并不重要。
即使连接到具有6 Gbps峰值传输速度的SATA3接口，典型的硬盘驱动器（HDD）也几乎无法达到1 Gbps〜2 Gbps的传输速度。HDD的机械读写性质根本不能实现快速的数据访问。传输速度甚至不是硬盘的最大问题，最大问题是定位时间。HDD的机械磁头需要一段时间在旋转的金属柱面上定位需要的数据，这迫使它在磁头到达数据所在位置前必须等待。如果数据以不规则的方式分布（即碎片式的存放），则可能需要毫秒（ms）级的时间。因此，HDD的传输速度可能远远低于它所连接的SATA3总线的峰值速度。
连接到USB 2.0端口的闪存磁盘的峰值传输速度为480 Mbps（兆比特每秒或百万比特每秒）。但是，USB 3.0标准具有更快的5 Gbps传输速度。更新的USB 3.1可以达到10 Gbps左右的传输速率。由于闪存磁盘使用闪存构建，它不需要查找时间，只需提供地址即可直接访问数据。
典型的固态硬盘（SSD）可以连接在SATA3接口上，达到接近4 Gbps〜5 Gbps的读取速度。因此，实际上SSD是唯一可以达到SATA3接口峰值速度的设备，即以预期的6 Gbps峰值速率传输数据。
一旦数据从I/O（SDD、HDD或闪存磁盘）传输到CPU的内存中，传输速度就会大大提高。已发展到第6代的Core i7系列（i7-6xxx），更高端的Xeon CPU使用DDR2、DDR3和DDR4内存技术，内存到CPU的传输速度为20 GBps〜60 GBps（千兆字节每秒）。注意这个速度是千兆字节。一个字节有8个比特，为与其他较慢的设备进行比较，转换为存储访问速度时为160 Gbps〜480 Gbps（千兆比特每秒）。
正如我们将在第二部分及以后所看到的，GPU内部存储器子系统的传输速度可以达到100 GBps〜1000 GBps。例如，新的Pascal系列GPU就具有接近后者的内部存储传输速率。转换后为8000 Gbps，比CPU内部存储器快一个数量级，比闪存磁盘快3个数量级，比HDD快近4个数量级。

imflip.c中的main( )函数

代码1.1中所示的程序会读取一些命令行参数，并按照命令行参数垂直或水平地翻转输入图像。命令行参数由C放入argv数组中。

clock( )函数以毫秒为单位统计时间。重复执行奇数次（例如129次）操作可以提高时间统计的准确性，操作重复次数在"#define REPS 129"行中指定。该数字可以根据你的系统更改。

ReadBMP( )函数从磁盘读取源图像，WriteBMP( )将处理后的（即翻转的）图像写回磁盘。从磁盘读取图像和将图像写入磁盘的时间定义为I/O时间，我们从处理时间中去除它们。这就是为什么我在实际的图像翻转代码之间添加"start = clock( )"和"stop = c1ock( )"行，这些代码对已在内存中的图像进行翻转操作，因此有意地排除了I/O时间。

在输出所用时间之前，imf?lip.c程序会使用一些free( )函数释放所有由ReadBMP( )分配的内存以避免内存泄漏。

代码1.1：imflip.c的main( ){⋯}

imflip.c中的main( )函数读取3个命令行参数，用以确定输入和输出的BMP图像文件名以及翻转方向（水平或垂直）。该操作会重复执行多次（REPS）以提高计时的准确性。

垂直翻转行：FlipImageV( )

代码1.2中的FlipImageV( )遍历每一列，并交换该列中互为垂直镜像的两个像素的值。有关Bitmap（BMP）图像的函数存放在另一个名为ImageStuff.c的文件中，ImageStuff.h是对应的头文件，我们将在下一章详细解释它们。图像的每个像素都以“struct Pixel”类型存储，包含unsigned char类型的该像素的R、G和B颜色分量。由于unsigned char占用1个字节，所以每个像素需要3个字节来存储。

ReadBMP( )函数将图像的宽度和高度分别放在两个变量ip.Hpixels和ip.Vpixels中。存储一行图像需要的字节数在ip.Hbytes中。FlipImageV( )函数包含两层循环：外层循环遍历图像的ip.Hbytes，也就是每一列，内层循环一次交换一组对应的垂直翻转像素。

代码1.2：imflip.c　⋯FlipImageV( ){⋯}

对图像的行做垂直翻转，每个像素都会被读取并替换为镜像行中的相应像素。

水平翻转列：FlipImageH( )

imf?lip.c的FlipImageH( )实现图像的水平翻转，如代码1.3所示。除了内层循环相反，该函数与垂直翻转的操作完全相同。每次交换使用“struct Pixel”类型的临时像素变量pix。

由于每行像素以3个字节存储，即RGB、RGB、RGB⋯⋯因此访问连续的像素需要一次读取3个字节。这些细节将在下一节介绍。现在我们需要知道的是，以下几行代码：

只是读取位于垂直的第row行和水平的第col列处的一个像素。像素的蓝色分量在地址img[row][col]处，绿色分量在地址img[row][col+1]处，红色分量在img[row][col+2]处。在下一章中我们将看到，指向图像起始地址的指针img由ReadBMP( )为其分配空间，然后由main( )传递给FlipImageH( )函数。

代码1.3：imflip.c　FlipImageH( ){⋯}

进行水平翻转时，每个像素都将被读取并替换为镜像列中相应的像素。

本文内容来自作者图书作品《基于CUDA的GPU并行程序开发指南》，点击购买。

创作场景

CPU 并行编程概述（上）