高性能计算技术丛书
点击查看第二章
点击查看第三章
基于CUDA的GPU并行程序开发指南
GPU Parallel Program Development Using CUDA

[美]托尔加·索亚塔（Tolga Soyata）　著
唐　杰　译

第1章

CPU并行编程概述
本书是一本适用于自学GPU和CUDA编程的教科书，我可以想象当读者发现第1章叫“CPU并行编程概述”时的惊讶。我们的想法是，本书希望读者具备较强的低级编程语言（如C语言）的编程能力，但并不需要具备CPU并行编程的能力。为了达到这个目标，本书不期望读者有CPU并行编程经验，但通过学习本书第一部分中的内容，获得足够多的CPU并行编程技巧并不困难。
不用担心，最终目标是学会GPU编程，因而在学习CPU并行编程的这部分时，我们并不是在浪费时间，因为我在CPU世界中介绍的几乎每一个概念都适用于GPU世界。如果你对此持怀疑态度，下面是一个例子：线程ID，或者称之为tid，是多线程程序中一个正在执行的线程的标识符，无论它是一个CPU线程还是GPU线程。我们编写的所有CPU并行程序都将用到tid概念，这将使程序可以直接移植到GPU环境。如果你对线程不熟悉，请不要担心。本书的一半内容是关于线程的，因为它是CPU或GPU如何同时执行多个任务的基础。

1.1　并行编程的演化

一个自然而然的问题是：为什么要用并行编程？在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的单核。引入多核后，许多类似的问题就非常突出了，只有通过编程才能高效地利用这些核心。

1.2　核心越多，并行性越高

程序员不能简单地忽略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.3　核心与线程

让我们来看看图1-1中描述的类比1.1。如果收获1颗椰子需要完成两个连续的任务（我们将它们称为线程）：线程1从树上摘取1颗椰子并花费30秒将它带回拖拉机，线程2花费30秒用拖拉机内的锤子敲碎（处理）该椰子，这样可以在60秒内收获1颗椰子（每分钟1颗椰子）。如果Jim和Fred各自都有自己的拖拉机，他们可以简单地收获两倍多的椰子（每分钟2颗椰子），因为在收获每颗椰子时，他们可以共享从拖拉机到椰子树的道路，并且他们各自拥有自己的锤子。
在这个类比中，一台拖拉机就是一个核心，收获一颗椰子就是针对一个数据单元的程序执行。椰子是数据单元，每个人（Jim、Fred）是一个执行线程，需要使用椰子锤。椰子锤是执行单元，就像核心中的ALU一样。该程序由两个互相依赖的线程组成：在线程1执行结束之前，你无法执行线程2。收获的椰子数量意味着程序性能。性能越高，Jim和Fred销售椰子挣的钱就越多。可以将椰子树看作内存，你可以从中获得一个数据单元（椰子），这样在线程1中摘取一颗椰子的过程就类似于从内存中读取数据单元。

1.3.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颗椰子。

1.3.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秒）。

1.3.3　内存资源共享的影响

用新的椰子锤实现了每分钟收获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颗椰子。在本书中，我们将区分两种不同类型的程序：核心密集型，该类型不大依赖于内存访问速度；存储密集型，该类型对内存访问速度高度敏感，正如我刚才提到的那样。

1.4　第一个串行程序

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

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

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

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

1.4.1 　理解数据传输速度

从磁盘读取图像的过程（无论是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个数量级。

1.4.2　imflip.c中的main()函数

代码1.1中所示的程序会读取一些命令行参数，并按照命令行参数垂直或水平地翻转输入图像。命令行参数由C放入argv数组中。
clock( )函数以毫秒为单位统计时间。重复执行奇数次（例如129次）操作可以提高时间统计的准确性，操作重复次数在"#define REPS 129"行中指定。该数字可以根据你的系统更改。
ReadBMP( )函数从磁盘读取源图像，WriteBMP( )将处理后的（即翻转的）图像写回磁盘。从磁盘读取图像和将图像写入磁盘的时间定义为I/O时间，我们从处理时间中去除它们。这就是为什么我在实际的图像翻转代码之间添加"start = clock()"和"stop = c1ock()"行，这些代码对已在内存中的图像进行翻转操作，因此有意地排除了I/O时间。
在输出所用时间之前，imflip.c程序会使用一些free( )函数释放所有由ReadBMP( )分配的内存以避免内存泄漏。
代码1.1：imflip.c的main( ){…}
imflip.c中的main()函数读取3个命令行参数，用以确定输入和输出的BMP图像文件名以及翻转方向（水平或垂直）。该操作会重复执行多次（REPS）以提高计时的准确性。

1.4.3　垂直翻转行：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( ){…}
对图像的行做垂直翻转，每个像素都会被读取并替换为镜像行中的相应像素。

1.4.4　水平翻转列：FlipImageH( )

imf?lip.c的FlipImageH( )实现图像的水平翻转，如代码1.3所示。除了内层循环相反，该函数与垂直翻转的操作完全相同。每次交换使用“struct Pixel”类型的临时像素变量pix。
由于每行像素以3个字节存储，即RGB、RGB、RGB……因此访问连续的像素需要一次读取3个字节。这些细节将在下一节介绍。现在我们需要知道的是，以下几行代码：

只是读取位于垂直的第row行和水平的第col列处的一个像素。像素的蓝色分量在地址imgrow处，绿色分量在地址imgrow处，红色分量在imgrow处。在下一章中我们将看到，指向图像起始地址的指针img由ReadBMP( )为其分配空间，然后由main(?)传递给FlipImageH( )函数。
代码1.3：imflip.c　FlipImageH(?){…}
进行水平翻转时，每个像素都将被读取并替换为镜像列中相应的像素。

1.5　程序的编辑、编译、运行

在本节中，我们将学习如何在以下平台上开发程序：Windows、Mac或运行诸如Fedora、CentOS或Ubuntu等系统的Unix机器。读者大多会侧重选择其中一个平台，并且能够使用该平台完成第一部分剩余的串行或并行程序的开发。

1.5.1　选择编辑器和编译器

要开发一个程序，你需要编辑、编译和执行该程序。我在本书中使用的是普通的、简单的C语言，而不是C++，因为它足够好地展示CPU并行性或GPU编程。我不希望不必要的复杂性分散我们的注意力，使我们偏离CPU、GPU以及并行化等概念。
要编辑一个C程序，最简单的方法就是使用编辑器，例如Notepad++[17]。你可以免费下载，它适用于任何平台。它还能够以不同的颜色显示C语言的关键字。当然，还有更复杂的集成开发环境（IDE），如微软的Visual Studio。但是，我们在第一部分中偏好简单性。第一部分的结果都将输出在Unix命令行中。你马上就会看到，即使你是Windows 7系统也可以工作。为了编译C程序，我们将在第一部分中使用g++编译器，它也适用于任何平台。我将提供一个Makefile文件，它将允许我们用适当的命令行参数编译我们的程序。要执行编译好的二进制代码，只需在编译它的同一个平台环境中运行即可。

1.5.2　在Windows 7、8、10平台上开发

Cygwin64[5]可以免费下载，它允许你在Windows中模拟Unix环境。简而言之，Cygwin64是“Windows中的Unix”。请注意获取Cygwin的64位版本（称为Cygwin64），因为它含有最新的软件包。你的计算机必须能够支持64位x86。如果你有Mac或Unix系统，你可以跳过本节。如果你的计算机是Windows系统（最好是Windows x 专业版），你最好安装Cygwin64，它有一个内置的g++编译器。要安装Cygwin64 [5]，访问http//www.cygwin.com 并选择64位安装版本。如果你的Internet连接速度较慢，此过程需要几个小时。因此，我强烈建议你将所有内容下载到临时目录中，然后从本地目录开始安装。如果你直接进行Internet安装，很可能会中断，然后重新开始。不要安装Cygwin的32位版本，因为它已经严重过时了。没有Cygwin64，本书中的代码都不能正常工作。此外，我们正在运行的最新的GPU程序也需要64位系统来执行。
在Cygwin64中，你将有两种不同类型的shell：第一种是一个简单的命令行（文本）shell，称为“Cygwin64终端”。第二种是“xterm”，意思是“X Windows终端”，能够显示图形。为了在不同类型的计算机上获得最大的兼容性，我将使用第一种：纯文本终端，即“Cygwin64终端”，它也是一种Unix bash shell。使用文本shell还有以下理由：

1. 由于我们将要编写的每个程序都是对图像进行操作，因此需要一种方法在终端外显示图像。在Cygwin64中，由于你在Cygwin64终端上浏览的每个目录都对应一个实际的Windows目录，因此你只需找到该Windows目录并使用常用的程序（如mspaint或Internet Explorer浏览器）显示输入和输出图像即可。这两个应用程序都允许你将巨大的3200×2400图像调整到任何你想要的大小，并舒适地显示它。
2. Cygwin命令ls、md和cd都在Windows目录上工作。 cygwin64-Windows的目录映射是：
   ~/Cyg64dir ←→ C:cygwin64homeTolgaCyg64dir

Tolga是我的登录名，也就是我的Cygwin64的根目录名。每个cygwin64用户的主目录都位于相同的C:cygwin64home目录下。在很多情况下，只有一个用户，这就是你的名字。

1. 我们需要在Cygwin64终端外（即从Windows）运行Notepad++，方法是将C源文件拖放到Notepad++中并进行编辑。编辑完成后，我们将在Cygwin64终端中对它们进行编译，然后在终端外显示它们。
2. 还有另一种方式来运行Notepad++并在Cygwin64中显示图像，而无须转到Windows。 键入以下命令行：
   

命令行cygstart notepad++ imflip.c如同你双击Notepad ++图标运行它来编辑名为imflip.c的文件。第二行将编译imflip.c程序，第三行将运行它并显示执行时间等。最后一行将运行默认的Windows程序来显示图像。Cygwin64中的cygstart命令基本上相当于“在Windows中双击”。最后一行命令的结果就像在Windows中双击图像dogh.bmp一样，这会告诉Windows打开照片查看器。你可以通过更改Windows资源管理器中的“文件关联”来更改默认查看器。
有一件事看起来很神秘：为什么我在程序名前面加上./而没有为cygstart做同样的事情？输入以下命令：

在初次安装Cygwin64后，当前的PATH环境变量中不会有./，因此Cygwin64将不知道在当前目录中搜索你键入的任何命令。如果你的PATH中已经有./，则不必担心这一点。如果没有，你可以将它添加到.bash_profile文件中的PATH中，现在它就会识别。该文件位于你的主目录中，要添加的行是：

由于cygstart命令位于PATH环境变量中的某个路径中，因此你不需要在它之前添加任何目录名称，例如表示当前目录的./。

1.5.3　在Mac平台上开发

正如我们在1.5.2节中讨论过的，在本书第一部分，我们所说的执行程序并显示结果就是如何在图像存放目录中显示一张BMP图像。对于Mac计算机也如此。Mac系统有一个内置的Unix终端，或者一个可下载的iterm，所以它不需要Cygwin64之类的东西。换句话说，Mac就是一台Unix电脑。如果你在Mac中使用像Xcode这样的IDE，那么你可能会看到小差异。如果你使用Notepad ++，一切都应该和我前面描述的一样。但是，如果需要开发大量的并行程序，Xcode非常棒，并且在Apple.com上创建开发人员账户后可以免费下载。这值得尝试。Mac系统有自己的显示图像的程序，所以只需双击BMP图像即可显示它们。Mac也会为每个终端目录设置相应的目录。因此，在桌面上找到你正在开发的应用程序的目录，然后双击BMP图像。

1.5.4　在Unix平台上开发

如果你有一个运行图形界面的Ubuntu、Fedora或CentOS的Unix机器，它们都有一个命令行终端。我使用术语“系列”来表示具有INTEL或AMD CPU的通用计算机或品牌计算机。Unix系统要么有xterm，要么有一个纯文本终端，比如bash。这两个都可以编译和运行此处描述的程序。然后，你可以找出程序运行的目录，然后双击BMP图像以显示它们。双击图像而不是拖拽到程序中，就会要求操作系统运行默认程序来显示它们。你可以通过系统设置更改这个默认程序。

1.6　Unix速成

在我过去５年的GPU教学中，几乎每年都有一半的学生需要Unix入门课程。所以，我在本节中介绍这些内容。如果你对Unix很熟悉，可以跳过这一节。我们只提供关键概念和命令，这些应该足以让你完成本书中的所有内容。更全面地学习Unix需要大量的练习以及一本专门针对Unix的书。

1.6.1　与目录相关的Unix命令

Unix目录结构从你的主目录开始，它由一个特殊的代字符（～）来表示。你创建的任何目录都在你的“～/”主目录下。例如，如果你在主目录中创建了一个名为cuda的目录，则表示此目录的Unix方式是：～/cuda。你应该将文件排列整齐，并在目录下创建子目录以使其层次化。例如，本书中的示例可以放在cuda目录下，每章的示例都可以放在一个子目录下，例如ch1、ch2、ch3……它们的目录名称为～/cuda/ch1等。
Unix中常用的创建/删除目录命令有：

无论你处于哪个目录，都可以使用ls-al命令查看当前目录下包含的目录和文件（即详细列表）的大小及权限。你还将看到Unix为你自动创建的两个有特殊名字的目录，.（意味着当前目录）和..（意味着上一层目录），这两个目录与你所处的位置有关。因此，命令./imflip...告诉Unix从当前目录运行imflip。
用pwd命令寻找你的位置时，你会得到一个不是以波浪字符开头的目录，而是看起来像/home/Tolga/cuda这样，为什么？因为pwd输出的是相对于Unix根目录的路径，而不是相对于你的主目录/home/Tolga/或缩写符号～/的路径。cd命令会将你带到你的主目录，而cd /命令会将你带到Unix根目录，你将在其中看到名为home的目录。可以使用cd home/Tolga命令进入home/Tolga目录，也就是你的主目录，但显然，简短的cd命令要方便得多。
当某个目录为空时，rmdir命令可以删除该目录。但如果该目录中包含某个文件或其他目录（即子目录），则会显示一条错误消息，指出目录不为空且不能删除。如果要删除包含文件的目录，请使用文件删除命令rm和选项“-r”，这意味着“递归”。 rm -r dirname的含义是：从目录dirname中删除所有的文件及其子目录。可能不需要强调这个命令有多危险。一旦你执行该命令，目录就消失了，其中的全部内容也不见了，更不用说所有的子目录了。所以，请谨慎使用此命令。
mv命令适用于文件和目录。例如，mv dir1 dir2将目录dir1“移动”到dir2中。事实上，这是将目录dir1重命名为dir2，且旧的目录dir1不见了。当你执行ls，你只会看到新的目录dir2。

1.6.2　与文件相关的Unix命令

一旦创建了目录（又名文件夹），你可以在其中创建或删除文件。这些文件包括你的程序，程序所需要的输入文件以及程序生成的文件。例如，要运行在1.4节提到的串行图像翻转程序imflip.c，你需要程序本身并编译它，并且当程序输出BMP图片时，你需要能够查看那张图片。你还需要将图片带到（复制到）此目录中。该目录下还有一个我创建的用于编译的Makefile文件。以下是用于文件操作的常用Unix命令：

• #（井号）是注释符号，它之后的任何内容都会被忽略。
• clear命令清除终端屏幕。
• cat Makefile以命令行显示Makefile的内容，而不必使用Notepad ++之类的其他外部程序。
• more Makefile显示Makefile更多的内容，并且还可以逐个滚动页面。这对于多页文件非常有用。
• cat > filename是创建名为filename的文本文件的最快方式。这使Unix进入文本输入模式。文本输入模式将你输入的所有内容发送到你在 > 之后输入的文件（例如mytest.c）中。输入CTRL-D（同时按住CTRL键和D键，这是EOT字符，ASCII码为4，表示传输结束）可以退出文本输入模式。如果你不想使用像Notepad ++这样的编辑器，那么这种输入文本的方法非常棒。对于只有几行的程序来说，它是完美的，尽管没有什么能够阻止你使用这种方法输入整个程序！
• | 是“管道”命令，它将一个Unix命令或程序的输出通道（即管道）转换为另一个命令。这允许用户仅使用一个命令行来运行两个单独的命令。第二个命令接受第一个命令的输出作为其输入。管道可以被创建多次，但这不常见。
• cat Makefile | grep imflip将cat命令的输出传递给另一个命令grep，该命令查找并列出包含关键字imf?lip的行。grep非常适合在文本文件中搜索一些字符串。任何Unix命令的输出都可以重定向输入到grep中。
• ls -al grep imflip将ls命令的输出传递给grep imflip。实际上这是在ls命令的输出中查找字符串imflip。这在确定包含特定字符串的文件名时非常有用。
• make imflip 在Makefile中寻找imflip: file1 file2 file3 …，如果某个文件已被修改，则重新生成imflip。
• cp imflip if1将刚创建的可执行文件imflip复制为另一个名为if1的文件，这样你不会丢失它。

1. cp显示cp命令的帮助文件。能够显示任意一条Unix命令的详细信息，这非常棒。

• ls -al可以用来显示源文件和输入/输出文件的权限和文件大小。例如，检查输入和输出BMP文件dogL.bmp和dogH.bmp的大小是否完全相同。如果不是，这是一个错误的早期迹象！
• ls imf *列出名称以imf开头的所有文件。这对于列出你知道的包含imf前缀的文件很有用，就像我们在本书中创建的名为imflip、imflipP……（*）是一个通配符，意思是“任何东西”。当然，你可能更喜欢这样使用*，如：Is imf *12是指以imf开始并以12结尾的文件。另一个例子是ls imf *12*，意思是以imf开头并且在文件名中间有12的文件。
• diff file1 file2显示两个文本文件之间的差异。这对确定文件是否发生变化很有用。它也可以用于二进制文件。
• imflip或imflip dog … 如果./在$PATH中，则启动该程序。否则，你必须使用./imflip dog。
• touch imflip更新文件imflip的“上次访问时间”。
• rm imflip删除imflip可执行文件。
• mv命令，就像重命名目录一样，也可以用来重命名文件并真正移动它们。mv file1 file2将file1重命名为file2并保留在同一目录中。如果你想将文件从一个目录移动到另一个目录，在文件名之前加上目录名，就会移动到该目录。你也可以移动文件而无须重命名它们。大多数Unix命令都具有这种多功能性。例如，可以像使用mv命令将文件从一个目录复制到另一个目录一样来使用cp命令。
• history列出你打开终端后使用过的命令。

如下所示为编译本书第一个串行程序imflip.c并将其转换为可执行的imflip（或Windows中的imflip.exe）的Unix命令。用户输入的重要命令显示在左侧，Unix的输出显示向右侧缩进了一段距离：

在上述的输出结果中，每个文件的权限显示为-rwxr-x等。根据你运行这些命令的计算机不同，输出可能会略有不同。 可以用Unix命令chmod更改这些权限，使其成为只读等。
Unix的make工具使我们能够自动执行若干常用的命令，方便地编译文件。在我们的例子中，“make imflip”要求Unix查看Makefile文件并执行“gcc imflip.c ImageStuff.c -o imflip”这行命令，它将调用gcc编译器编译imflip.c和ImageStuff.c源文件，并生成一个名为imflip的可执行文件。在我们的Makefile中，第一行显示了文件依赖关系：它告诉make，只有当列出的源文件imflip.c、ImageStuff.c或ImageStuff.h发生更改时才重新生成可执行文件imflip。要想强制编译，可以先使用Unix的touch命令。

1.7　调试程序

调试代码是你不得不做的事情。有时，你认为编写的代码应该可以正常工作，但却抛出了一个段错误或一些从未见过的错误。这个过程可能会令人非常沮丧，常常是由很难发现的简单的输入错误或逻辑错误造成的。还有一些代码错误甚至可能在运行时也不总是发生，乍一看你不会发现它的影响。这是最糟糕的错误，因为编译器没有发现它们，在运行时也不明显。例如像内存泄漏这样的错误并不会在运行时马上显现出来。在代码开发过程中，一个好的做法是定期运行gdb和valgrind等调试工具来寻找潜在的发生段错误的位置。要在调试器中运行代码，你需要在编译时设置调试标志，通常为“-g”。这会告诉编译器包含调试符号（包括行号等），以告诉你代码出错的位置。如下所示为一个例子：

1.7.1　gdb

为了说明当你的代码一团糟时会发生什么，我在imflip.c中的数据变量使用完成前的某个位置插入了一条内存free()语句。显然这将引起一个段错误，如下所示：

由于imflip是用调试模式编译的，所以可以用GNU的调试器gdb来找出段错误发生的位置。gdb的输出在图1-4中给出。执行下述指令可以启动gdb：

一旦gdb启动，程序参数由以下命令设置：

在此之后，程序使用简单的run命令来运行。gdb会输出一堆错误，说你的代码全部搞砸了，where命令可以提供代码出错位置的信息。最初，gdb认为错误出现在ImageStuff.c
中第73行的WriteBMP(?)函数中，但where命令将范围缩小到imf?lip.c中的第98行。进一步检查imf?lip.c代码后发现，在用WriteBMP(?)函数将数据写入BMP图像之前调用了free(data)语句。这只是一个简单的例子，gdb的功能包括添加断点，查看变量值以及其他一些选项。表1-1中列出了一些常用命令。

大多数集成开发环境（IDE）都有一个内置的调试模块，这使得调试过程非常容易。通常它们的后端仍然是gdb或一些专有的调试引擎。无论你是否使用IDE，都可从命令行使用gdb，并且与你的IDE（取决于你选择的IDE）相比，它包含的功能就算不是更多，也基本一样。

1.7.2　古典调试方法

这可能是最能体现程序员在过去的年代—40年代、50年代、60年代、70年代—使用的调试类型的名词了，这些调试方式至今仍被使用。我看不出古典调试方法在可预见的将来会消失。毕竟，我们用来调试代码的“真实”调试器，比如gdb，只不过是古典调试方法的自动执行版本。我将在7.9节的GPU编程环境中详细介绍古典调试方法。这些内容也适用于CPU。所以，你可以选择继续阅读本章或者马上跳到7.9节。
每个调试器的主要思想都是在代码中插入断点，以打印/显示在该断点处与系统状态有关的各种数值。所谓状态包括变量值或外设的状态，你可以自己定义它们。可以在断点处中止或继续一个程序的执行，同时输出多个状态值。
指示灯：在早期阶段，编写机器指令的程序员通过拨动各种开关来逐位编写程序，断点可能是显示某一位值的一个指示灯。今天，FPGA程序员使用8个LED显示一个8位Verilog变量的值（注意：Verilog是一种硬件描述语言）。但是，从几个比特的显示值推断系统状态需要程序员具备非常丰富的经验。
printf：在一个C程序中，程序员通常会插入一堆printf()语句来输出程序运行到某些位置时相关变量的值。这其实同手动设置断点差不多。正如我在1.7.1节中所述，如果你觉得很容易发现代码中的错误，那就没有必要使用繁杂的gdb操作。在代码中粘贴一堆printf()，它们会告诉你发生了什么。一个printf()可以显示大量关于变量的信息，显然比几个LED的功能更强大。
assert：除非违反了你指定的条件，否则assert语句不会执行任何操作。这与printf()相反，printf总是输出某些内容。例如，如果你的代码有以下几行：

此时，你只是试图确保拿到的指针不是NULL，这是对内存分配的最严重问题的告警。尽管assert()在正常情况下不会执行任何操作，但如果违反了指定的条件，它将发出如下所示的错误：
Assertion violation: file mycode.c, line 36: ImgPtr != NULL
注释行：令人惊讶的是，还有比在代码中添加一堆printf()更容易的方法。虽然C语言并不要求代码按“行”编写，但C程序员偏好一行一行地编写代码，这很常见，就像Python。这也是为什么Python受到一些批评，因为它让逐行式的语言成为实际语法，而不是C中的可选形式。在注释驱动的调试中，你只需注释掉一条可疑的行，重新编译，重新执行以查看问题是否消失，尽管结果肯定不再正确。这在出现重大错误时是非常有效的。在下面的例子中，如果用户输入速度为0，你的程序会给你一个除0错误。你可以在那里插入printf()语句来看看它会在哪里崩溃，但用assert()语句就方便得多，因为assert()在正常情况下不会做任何事情，这可以避免调试过程中屏幕上出现混乱。

注释非常实用，如果代码中存在多条C语句，你可以将它们插入代码中间，如下所示：

1.7.3　valgrind

另一种非常有用的调试工具是valgrind。 一旦代码用调试模式编译，valgrind就很容易运行。它可以设置许多选项，类似于GDB，但基本用法很简单。图1-5显示了在valgrind中运行具有内存错误的imflip代码的输出。它会捕获更多的错误，甚至可以定位imflip.c中发生错误的第96行，也就是不合适的free()命令所在的行。

valgrind还擅长查找运行时不显现的内存错误。通常内存泄漏很难用简单的打印语句或像gdb这样的调试器发现。例如，如果最后imflip没有释放任何内存，则会出现内存泄漏，而valgrind会发现它们。valgrind还有一个名为cachegrind的模块，可以用来模拟代码如何与CPU的缓存系统交互。cachegrind模块可以用-tool=cachegrind命令选项来调用。更多的选项和文档可以参考http://valgrind.org 。

1.8　第一个串行程序的性能

我们先来看看我们的第一个串行程序imflip.c的性能。由于操作系统（OS）会执行许多随机事件，因此一个好办法是多运行几次相同的程序以确保获得一致的结果。所以，通过命令行多运行几次imflip.c。这样做后，我们得到的结果有81.022 ms、82.7132 ms、81.9845 ms……我们可以说它大约为82 ms。非常好，这相当于10.724 ns/像素，因为这个扩展的dogL.bmp图像有3200×2400像素。
为了能够更准确地测量程序的性能，我在代码中增加了一个for(?)循环来重复（例如129次）执行相同的代码，并将执行时间除以相同的数值129。这将使我们比正常情况多花费129倍的时间，从而能使用不太准确的UNIX系统定时来实现更准确的计时。大多数机器提供的硬件时钟精度不会好于10 ms，甚至更糟糕。如果一个程序只需要执行50 ms，那么即使你按照上述方法简单地多次重复测量，你也会得到非常不准确的性能结果（在时钟精度为10 ms的情况下）。但是，如果你将同一个程序重复129次，在129次循环的开始和结束时测量时间，并将其除以129，则10 ms实际上变为10/129 ms的精度，这对我们的目标来说已经足够了。请注意，循环次数必须是奇数，否则，最终的图片将不会被翻转！

1.8.1　可以估计执行时间吗

经过这一改动后，执行水平翻转小狗图片的imflip.c程序获得了81～82 ms的结果。我们想知道在较小的dog.bmp图片上运行该程序时会发生什么情况，如果在一张901 KB的位图图片上运行完全相同的程序，输入为原始的640×480的dog.bmp文件，我们获得了3.2636 ms的运行时间，即10.624 ns/像素。换句话说，当图片缩小到1/25时，运行时间也几乎减少到了那么多。然而，一件奇怪的事情是：每次我们都会得到完全相同的执行时间。虽然这表明我们能够以令人难以置信的准确度计算执行时间，但不要高兴太早，因为我们会遇到一个动摇我们世界的复杂情况！
事实上，第一个奇怪的地方已经出现了。你能回答这个问题吗：尽管我们获得了几乎相同的（每像素）执行时间，但为什么处理较小图像的执行时间不会改变？都是完全相同的4位十进制小数，而处理较大图像的执行时间会在1%～2%内变化。虽然这看起来可能像一个统计上的随机性，但事实并非如此！它有一个非常明确的解释。为防止你睡不着觉，我会马上公布答案，不让你等到下一章了：当我们处理22 MB的dogL.bmp图像时，与原来的901 KB的dog.bmp相比，哪些东西改变了？答案是：在处理dogL.bmp的过程中，CPU无法将整个图像保存在最后一级的L3缓存（L3$）中，该级缓存的大小为8 MB。这意味着，要访问该图像，在执行期间它需要不断地清空和填充L3$。与之对应的是，在处理901 KB的dog.bmp图像时，只需要一轮处理即可将数据完全装入L3$，并且在所有129个执行循环中CPU都拥有该数据。请注意，我将用符号L3$来表示L3缓存。

1.8.2　代码执行时OS在做什么

较大图像的处理时间变化较大的原因是访问内存的不确定性比访问片内数据更大。由于imflip.c是一个串行程序，我们确实需要一个“1T”来执行我们的程序。另一方面，我们的CPU拥有诸如4C/8T的豪华资源。这意味着，一旦开始运行，我们只有一个活跃线程的程序，操作系统几乎能立即意识到给我们一个完全专用的CPU线程（甚至是核心），以符合所有人的最大利益，因此我们的应用程序可以充分利用此资源。总之，这是操作系统的工作：智能地分配资源。无论是Windows系统还是Unix系统，当今所有的操作系统代码在理解程序执行中的这些模式时都非常聪明。如果一个程序热衷于寻求一个单独的线程而没有其他要求，除非你正在运行许多其他程序，否则操作系统的最佳操作就是让你像VIP一样地访问单个线程（甚至可能是一个完整的核心）。
然而，对于主存储器来说，这个故事是完全不同的，操作系统中的每个活动线程都可以访问主存。想象它只有1 M！没有2 M！所以，操作系统必须在每个线程中共享它。主存是所有操作系统数据，以及每个线程的数据所在的地方，主存是所有椰子（即图像数据）所在的地方。所以，操作系统不仅必须弄清楚你的imflip.c如何从主存访问图像数据，甚至得弄清楚它自己如何访问数据。操作系统的另一项重要工作是确保公平性。如果一个线程缺少数据，而另一个线程却绰绰有余，那么操作系统并没有很好地完成它的工作。它必须公平对待每个人，包括它自己。当你在主存访问中有如此多的内容需要传输时，你就会知道为什么主存访问时间具有不确定性。相反，当我们在处理较小图像时拥有一个几乎完全专属的核，就可以在该核中运行程序而无须访问主存。我们没有与其他人分享这个核。因此，在确定执行时间方面几乎没有不确定性。如果你对这些概念有些模糊，不要担心，后面会有一整章解释CPU架构。以下是C/T（核心/线程）符号的含义：

• C/T（核心/线程）符号表示：
  例如，4C/8T表示4个核心，8个线程，

4C意味着处理器有4个核心，
8T意味着每个核心可以执行2个线程。

• 因此，4C/8T处理器可以同时执行8个线程。
  然而，每个线程对必须共享内部核心的资源。

1.8.3　如何并行化

即使在运行串行版本的代码时，仍然需要了解很多细节。我宁愿将并行版本的代码扩展为完整的一章内容，而不是压缩到本小节中。事实上，接下来的几章将完全致力于代码的并行化以及对其性能的深入分析。现在，让我们从椰子这个类比开始，请回答下列问题：
在类比1.1中，如果我们拥有两台拖拉机且每台拖拉机中有2位农民时会发生什么情况？此时，你有4个线程在运行……因为有2台物理上独立的拖拉机，拖拉机（即核心）内部的一切都很舒适。然而，现在需要分享从拖拉机到椰子树的道路（即多个线程需要访问主存储器）是4个人而不是2个人。继续……，如果有8位农民去收获椰子怎么办？有16位农民又怎么办？换句话说，即使在8C/16T的情况下，也就是你有8个核心和16个线程，相当于你有8台拖拉机可以满足农民的需求，其中每2位农民需要共享一把椰子锤。但是，主存储器的访问又如何呢？参加收获的农民越多，他们等待通过那条道路获取椰子的时间就越长。在CPU方面，内存带宽迟早会饱和。事实上，在下一章中，我会给出一个发生该情况的程序。这意味着，在我们开始对程序进行并行化之前，必须考虑线程在执行期间会访问哪些资源。

1.8.4　关于资源的思考

即使你知道上述问题的答案，还有另一个问题：针对不同的资源，并行性的魔法都会起到同样的作用吗？换句话说，并行性的概念与它所应用的资源是独立的吗？举例来说，无论内存带宽如何，2C/4T核心配置总能让我们获得相同的性能改进吗？或者说如果内存带宽非常糟糕，那么额外增加核心数量所获得的性能增益是否会消失？现在只是思考一下，本书的第一部分将回答这些问题。所以，现在不要过度强调它们。
好吧，这已经足够让大脑热身了……让我们编写第一个并行程序吧。