带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

点击查看第一章
点击查看第三章

第2章

开发第一个CPU并行程序
本章主要关注的是理解第一个CPU并行程序imflipP.c。注意,文件名末尾的“P”表示并行。开发平台对于CPU并行程序来说没有任何区别。在本章中,我将逐步介绍有关并行程序最主要的概念,当我们在第二部分开发GPU程序时,这些概念将很容易地应用于GPU编程。你可能已经注意到,我从不说GPU并行编程,而是GPU编程。这就像不需要说一辆带*的汽车,说一辆车就足够了。换句话说,根本没有GPU串行编程,这意味着即使你有100 000个可用的GPU线程,但却只使用一个!所以,按照定义,GPU编程就意味着GPU并行编程。

2.1 第一个并行程序

现在是编写第一个并行程序imflipP.c的时候了,它是我们在1.4节中介绍的串行程序imflip.c的并行版本。为了并行化imflip.c,我们需要在main()函数中创建多个线程并让它们各自完成一部分工作后退出。在最简单的情况下,如果我们尝试运行一个双线程的程序,main()将创建两个线程,让它们各自完成一半的工作,合并线程然后退出。在这种情况下,main()不过是各个事件的管理者,它没有做实际的工作。
为了实现我们刚刚描述的内容,main()需要能够创建、终止和管理线程并将任务分配给线程。Pthreads库的部分函数可以帮助它完成这些任务。Pthreads只能在符合POSIX标准的操作系统中工作。讽刺的是,Windows不符合POSIX标准!但是,在POSIX和Windows之间执行某种API到API的转换后,Cygwin64允许Pthreads代码在Windows中运行。这就是为什么本书描述的所有东西都可以在Windows中使用,也是在你的计算机是一台Windows PC的情况下,我推荐Cygwin64的原因。以下是我们将要使用的一些Pthreads库函数:

  1. pthread_create()用于创建一个线程。
  2. pthread_join()用于将任何给定的线程合并到最初创建它的线程中。你可以将“合并”过程想象成“毁灭”线程,或者父线程“吞食”刚刚创建的线程。
  3. pthread_attr()用于初始化线程的各项属性。
  4. pthread_attr_setdetachstate()用于为刚刚初始化的线程设置属性。

2.1.1 imflipP.c中的main()函数

我们的串行程序imflip.c(如代码1.1所示)读取一些命令行参数,并按照用户的命令对输入图像进行垂直或水平翻转。同样的翻转操作重复奇数次(例如129),用以改进由clock()获取的系统时间的准确性。
代码2.1和代码2.2显示的都是imflipP.c中的main()函数,不同之处在于:代码2.1标注的是“main(){...”,这表示main()的“第一部分”,后面所跟的“...”进一步强调了这一点。这部分用于命令行参数解析和一些常规操作。在代码2.2中,“main() ...}”后部的符号与2.1相反,“...”在前,表示这是main()函数的“第二部分”,该部分用于启动线程和给线程分配任务。
为了提高可读性,我可能在这两部分代码中重复一些代码,例如使用gettimeofday()获取时间戳,使用ReadBMP()进行图像读取等,稍后将详细介绍ReadBMP()。这将使读者能够清楚地了解这两个部分的开始和连接处。你可能已经注意到,如果完全列出一个函数的代码,就会使用“func(){...}”来表示。当一个函数和它前后的代码同时被列出时,用“... func(){...}”来表示,意思是“一些常规代码...func()完整的代码。”
下面是main()函数中命令行解析的部分,命令行参数在argv[]数组中给出(总共有argc个)。如果用户输入的参数个数不对时会报错。用户指定的翻转方向存放在一个名为Flip的变量中备用。全局变量NumThreads也是基于用户输入确定的,稍后将在实际执行翻转操作的函数中使用。
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

2.1.2 运行时间

当有多个线程执行时,我们希望能够量化加速倍数。在串行代码中我们使用clock()函数,它包含在time.h头文件中,精度仅为毫秒级。
我们将在imflipP.c中使用的gettimeofday()函数能够使精度达到μs。gettimeofday()需要包含sys/time.h头文件,并且给一个结构的两个成员变量提供时间:一个是给.tv_sec成员变量设置以秒为单位的时间,另一个是给.tv_usec成员变量设置以微秒为单位的时间。这两个成员变量都是int类型,在输出之前联合生成一个双精度的时间值。
值得注意的是,计时的准确与否不取决于C函数本身,而取决于硬件。如果你的计算机的操作系统或硬件无法提供μs级的时间戳,gettimeofday()将只提供从操作系统获得的最佳结果(操作系统从硬件的时钟单元获得该值)。例如,即使使用gettimeofday()函数,由于Cygwin64依赖于Windows API,Cygwin64的精确度也不会达到μs。
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

2.1.3 imflipP.c中main()函数代码的划分

我有意避免在一个代码片段中列出长长的main()函数代码。这是因为,从第一个示例中可以看出,代码2.1和代码2.2的功能完全不同:代码2.1用于获取命令行参数,解析它们以及向用户发出警告。而代码2.2用于创建与合并线程的“酷动作”。大多数情况下,我会按照类似的方法来安排我的代码,并尽量关注代码的重要部分。
代码2.1:imflipP.c ... main(){...
imflipP.c中main()函数的第一部分读取和解析命令行选项。如有必要,输出错误告警。 BMP图像被读入主存的数组中并启动计时器。这部分决定多线程代码是否会运行。
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

代码2.2:imflipP.c ... main() ...}
imflipP.c中main()函数的第二部分创建多个线程并为它们分配任务。每个线程执行其分配的任务并返回。当每个线程完成后,main()会合并(即终止)线程并报告已用时间。
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

2.1.4 线程初始化

以下代码用于初始化线程并多次运行多线程代码。为了初始化线程,通过应用程序接口pthread_attr_init()和pthread_attr_setdetachstate(),我们告诉操作系统准备启动一系列线程,并且稍后将合并它们……将同样的代码重复执行129次只是为了“减慢”时间!与计算执行一次需要多长时间相比,执行129次并将消耗的总时间除以129,结果并没有什么变化,除非你对Unix计时API的不准确性不在意。
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

2.1.5 创建线程

这里是好事情发生的地方:请看下面的代码。每个线程都是通过使用API函数pthread_create()创建的,一旦创建就开始执行。 这个线程将做什么?第三个参数将告诉线程要执行的任务:MTFlipFunc。就好像我们调用了一个名为MTFlipFunc()的函数,但它自己开始执行,也就是说,与我们并行执行。main()只是创建了一个名为MTFlipFunc()的子线程,并且立即开始并行地执行。问题是,如果main()创建了2个、4个或8个线程,那么每个线程如何知道它自己是谁?这个问题由第四个参数负责,经过一些指针操作后,该参数指向ThParam[i]。
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

OS需要第一和第二个参数:第二个参数&ThAttr对于所有线程都相同,内容是线程属性。第一个参数是每个线程的“句柄”,它对操作系统非常重要,使操作系统能够跟踪线程。如果操作系统无法创建线程,它将返回NULL(即0),这意味着我们不能再创建线程。这是致命的错误,所以程序将报告一个运行时错误并退出。
下面是一个有趣的问题:如果main()创建两个线程,那么我们的程序是一个双线程的程序吗?正如我们马上就要看到的,当main()函数用pthread_create()创建2个线程时,我们可以期望的最好结果是程序提高2倍的运行速度。那么main()本身呢?其实,main()本身也是一个线程。因此,当main()创建2个子线程后,程序中一共有3个线程。我们只期望有2倍加速的原因是,main()只做了一些微不足道的工作,而另外的两个线程完成的是繁重的工作。
可以对上述情景进行量化分析:main()函数创建线程,为它们分配任务,然后合并它们,占大约1%的工作量,而其他99%的工作是由另外两个线程执行的(各占49.5%)。在这种情况下,运行main()函数的第三个线程所花费的时间可以忽略不计。图2-1所示为我电脑的Windows任务管理器,它显示了1499个活跃线程。但是,CPU负载可以忽略不计(几乎为0%)。这1499个线程是Windows操作系统创建的用于侦听网络数据包、键盘敲击、其他中断等事件的。例如,如果操作系统意识到一个网络数据包已到达,它会唤醒相应的线程,立即用很短的时间处理该数据包。然后线程会回到睡眠状态,尽管它仍然是一个活跃线程。请记住:CPU的速度比网络数据包快得多。

带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

2.1.6  线程启动/执行

图1-2显示,虽然操作系统中有1499个休眠的线程,但main()函数创建的线程具有完全不同的个性:一旦main()创建好2个子线程,线程总数就为1501。然而,这2个子线程执行了82 ms,在它们执行的过程中,Windows任务管理器中的两个虚拟CPU将显示100%的峰值,直到82 ms后被main()函数用pthread_join()吞噬。那时,系统又回到1499个线程。main()函数在运行到最后一行并输出时间之前不会死亡。当main()退出后,线程数减少到1498。因此,如果你在代码循环129次时查看Windows任务管理器,其中有2个线程处于肾上腺素状态下的急速增长状态—从线程启动到线程合并,你会看到8个CPU中的2个占用率为100%。我的电脑的CPU有4个核心,8个线程(4C/8T)。 Windows操作系统将此CPU视为“8个虚拟CPU”,这就是在任务管理器中看到8个“CPU”的原因。当你有一台Mac或一台Unix机器时,情况会很类似。总结一下当我们的2线程代码运行时会发生什么,请记住你键入的运行代码的命令行:
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

该命令行指示操作系统加载并执行二进制代码imf?lipP。执行过程包括创建第一个线程,为其分配函数main(),并将参数argc和argv[]传递给该线程。这听起来与我们创建子线程非常相似。
当操作系统完成加载可执行二进制文件imf?lipP后,将控制权交给main(),就像它调用了main()函数并将变量argc和argv[]数组传递给它一样。main()开始运行……在执行过程中的某处,main()要求操作系统创建另外两个线程……
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序
操作系统设置好内存和栈区并将2个虚拟CPU分配给这两个超级活跃线程。成功创建线程后,必须启动它们。pthread_create()同时也意味着启动一个刚刚创建的线程。启动线程等同于调用以下函数:
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

随后它们将进入水平或垂直翻转函数,这由用户在运行时输入的参数决定。如果用户选择“H”作为翻转选项,那么启动过程等同于:
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

2.1.7 线程终止(合并)

线程启动后,一股龙卷风会袭击CPU!它们会疯狂地使用这两个虚拟CPU,并且最终会依次地调用return(),这会让main()对每个线程逐一执行pthread_join():
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

执行第一个pthread_join()后,线程数减少到1500个。第一个子线程被main()吞噬了。 执行第二个pthread_join()后,线程数减少到1499个。第二个子线程也被吞噬了。这将让龙卷风停止!几毫秒后,main()报告时间并退出。正如我们将在代码2.5中看到的,imageStuff.c中的部分代码用来动态分配用于存放从磁盘读取的图像数据的存储空间。malloc()函数用于动态(即在运行时)的内存分配。在main()退出之前,所有这些存储空间都要用free()来释放,如下所示。
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

当main()函数退出时,它在操作系统中的父线程会结束运行main()的子线程。这些线程是一种有趣的生命形式,它们就像某种细菌一样创造和吞噬其他线程!

2.1.8 线程任务和数据划分

好了,这些被称为线程的“细菌”的各种操作我们现在已经很清楚了。数据呢?创建多个线程的最终目的是更快地执行任务。根据定义,这意味着我们创建的线程越多,任务划分也越多,我们处理的数据划分也越多。要理解这一点,请看类比2.1。
类比2.1:多线程中的任务和数据划分
Cocotown是椰子的主要生产地,每年收获1800棵树。树木从0到1799编号。每年,整个城镇都在收割椰子。由于参与收割椰子的人越来越多,该镇制定了以下加快收割速度的策略:
愿意帮助的农民需要出现在收割地点,并将获得一页指导手册。该手册分为上、下两个部分。对于每位农民来说,上半部分都是一样的:“敲碎外壳、剥皮……对后面的椰子树做同样的事。”
当只有两位农民时,手册的下半部分写道:第一位农民只处理编号为[0 ... 899]的树,第二位农民只处理编号为[900 ... 1799]的树。但是,如果有五位农民时,手册的下半部分将会是以下数字:第一位农民[0 ... 359],第二位农民[360 ... 719],……,最后一位农民[1440 ... 1799]。
在类比2.1中,无论有多少农民参与,每个线程的任务都是收获一部分椰子树,这对每位农民来说都是一样的。农民就是正在执行的线程。需要给每位农民一个唯一的ID,以知道他们应该收获哪些椰子树。这个唯一的ID类似于线程ID或tid。椰子树的数量是1800棵,这是要处理的所有数据。最有意思的是,任务(即指导手册的上半部分)可以与数据分离(即指导手册的下半部分)。虽然每位农民的任务都是一样的,但数据是完全不同的。所以,从某种意义上说,任务只有一个,但要处理由tid确定的不同数据。
很显然,这个任务在编译时完全可以预先确定,也就是说,在准备指导手册时。但是,看起来数据部分必须在运行时才能确定,即每个人都出现时,我们才能确切知道有多少农民参加。关键问题是数据部分是否也可以在编译时确定。换句话说,镇长只能写1份指导手册,然后复印60份(即可预计的最多的农民数量),而且当不同数量的农民参加时不需要准备任何其他的东西。如果有2位农民出现,镇长会发出2份指导手册,并将tid=0和tid=1分配给他们。如果有5位农民出现,他会发出5份指导手册,并指定tid=0、tid=1、tid=2、tid=3、tid=4。
更一般地说,唯一必须在运行时确定的是tid的赋值,即tid=0,...,tid=N-1。其他的一切都是在编译时确定的,包括任务参数。这可能吗?事实证明,这是绝对可能的。最终,对于N位农民来说,我们清楚地知道数据划分将会是什么样子:每位农民将分配1800/N棵椰子树来收割,而第tid位农民必须收割如下范围内的椰子树:
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

为了验证这一点,让我们计算tid=[0 ... 4](5位农民)的数据划分。对于给定的tid,式2.1的结果是[360×tid,...,360×tid+359]。因此,对于5位农民来说,数据划分结果为[0,...,359]、[360,...,719]、[720,...,1079]、[1080,...,1439]和[1440,...,1799]。这正是我们想要的。这意味着对于一个N线程程序,例如对图像做水平翻转,我们确实需要编写一个函数,在运行时将其分配给启动的线程。我们需要做的就是让启动的线程知道它的tid是什么。然后,线程将能够使用类似于式2.1的公式准确计算出在运行时要处理的数据部分。
重要的一点是,这里的数据元素互相之间没有依赖关系,即它们可以被独立地、并行地处理。因此,我们预计,当我们启动N个线程时,整个任务(即1800棵椰子树)的执行速度可以提高N倍。换句话说,如果1800棵椰子树需要1800小时才能收获,那么当5位农民出现时,我们预计需要360小时。正如我们将很快看到的,这种完美的结果是难以实现的。并行化任务存在隐含的开销,称为并行开销。由于这种开销的存在,5位农民可能需要400小时才能完成这项工作。其中的细节取决于硬件和我们为每个线程编写的函数。在接下来的章节中,我们将更多地关注这个问题。

2.2 位图文件

了解了多线程程序必须进行任务划分和数据划分后,让我们将这些知识应用到第一个并行程序imf?lipP.c中。在开始前,我们需要了解位图(BMP)图像文件的格式以及如何读取/写入这些文件。

2.2.1 BMP是一种无损/不压缩的文件格式

BMP文件是一种不压缩的图像文件。这意味着知道图像大小,可以轻松确定存储该图像的文件大小。例如,每像素24位的BMP图像每个像素占用3个字节(即R、G和B各一字节)。这种格式还需要54个额外的字节来存储“头”信息。我将在2.2.2节给出并解释相应的公式,但现在让我们关注压缩的概念。
类比2.2:数据压缩
Cocotown的档案管理部门想要保存在2015年年初和年末收获1800棵椰子树的照片。办公室职员将以下信息存储在一个名为1800trees.txt的文件中。
2015年1月1日,共有1800棵相同的树木,分布在一个宽40、长45的矩形中。我拍下一棵树的图片,并将其保存在名为OneTree.BMP的文件中。用这张照片按40×45的方式平铺复制。我注意到只有在位置(30, 35)处有一棵不同的树,并将其图片存储在另一个图片文件DifferentTree.BMP中。其他1799棵是相同的。
2015年12月31日,树木看起来不同了,因为它们长大了。我拍下一棵树的照片并保存在GrownTree.BMP中。尽管它们长大了,但在2015年12月31日,其中的1798棵仍然相同,另2棵不同。用GrownTree.BMP文件中的树创建一个40×45的平铺复制,并使用Grown3236.BMP和Grown3238.BMP文件替换位置(32, 36)和(32, 38)处两棵不同的树。
如果你看看类比2.2就会发现,职员可以通过一棵椰子树的照片(OneTree.BMP)和另一棵与其他1799棵稍有不同的椰子树照片(DifferentTree.BMP)来获得绘制整张40×45林场图片所需的所有信息。假设每张这样的图片都要占用1KB的存储空间。包括职员提供的文本文件,这些信息在2015年1月1日约为3KB。如果我们要将整个40×45林场制作成一个BMP文件,我们需要1800 KB,因为每棵树需要1KB。重复的(即冗余的)数据允许职员大大减少我们传递该信息时所需文件的大小。
这个概念称为数据压缩,可以应用于任何有冗余的数据。这就是为什么像BMP这样未压缩的图像文件大小会比采用JPEG(或JPG)格式的压缩文件大很多,JPEG格式会在存放图像前先进行压缩。压缩技术包括频率域分析等,抽象出的概念其实很简单,就是类比2.2中给出的思路。
BMP文件存储“原始”图像像素而不压缩它们。因为没有压缩,所以在将每个像素存储在BMP文件中之前不需要额外的处理。这与JPEG文件格式形成对比,JPEG格式首先需要进行像余弦变换之类的频域转换。JPEG文件的另一个有趣之处在于只保存了90%~99%的图像信息,这种丢失部分图像信息的概念—虽然我们的眼睛察觉不到—意味着JPEG文件是一种有损图像存储格式,而BMP文件中没有信息丢失,因为每个像素都是在没有任何转换的情况下存储的。考虑到如果我们可以容忍1%的图像数据损失,20 MB的BMP文件可以存储为1 MB的JPG文件,这种妥协几乎可以被任何用户接受。这就是为什么几乎每部智能手机都以JPG格式存储图像以避免过快地占满存储空间。

2.2.2 BMP图像文件格式

虽然BMP文件支持灰度和各种颜色深度(例如8位或24位),但在我们的程序中只使用24位RGB文件。该文件有一个54字节的文件头,接着存放每个像素的RGB颜色。与JPEG文件不同,BMP文件不进行压缩,因此每个像素占用3个字节,可以根据以下公式确定BMP文件的确切大小:

带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

其中Vpixels和Hpixels是图像的高度和宽度(例如,对于640×480的dog.bmp图像文件来说,Vpixels = 480,Hpixels = 640)。根据式2.2,dog.bmp占用54+3×640×480 = 921 654
个字节,而3200×2400的dogL.bmp图像文件的大小为23 040 054个字节(≈22 MB)。
从Hpixels到Hbytes字节的转换如下式所示,非常简单:
Hbytes = 3×Hpixels
然而,Hbytes必须舍入为下一个可以被4整除的整数以确保BMP图像大小是4的倍数。可以通过在公式2.2的第一行中加3并将结果的两位最低有效位清零来实现(即,将最后2位与00进行与运算)。
下面是一些计算BMP大小的示例:

  • 24位1024×1024的BMP文件需要3 145 782字节的存储空间(54+1024×1024×3)。
  • 24位321×127的BMP文件需要122 482字节(54+(321×3+1)×127)。

2.2.3 头文件ImageStuff.h

由于我在本书第一部分使用完全相同的图像格式,因此我将所有BMP图像处理文件和关联的头文件放在实际代码之外。 ImageStuff.h头文件包含与图像相关的函数声明和结构定义,需要被我们的所有程序包含,如代码2.3所示。除了ImageStuff.h文件,你还可以使用更多专业级图像软件包,如ImageMagick。但是,由于ImageStuff.h在某种意义上是“开源的”,我强烈建议读者在开始使用ImageMagick或OpenCV之类的其他软件包之前了解此文件。这将使你能够很好地掌握与图像相关的底层概念。我们将在本书第二部分使用其他易用的软件包。
在ImageStuff.h中,为图像定义了一个结构(struct),成员变量包括前面提到的图像的Hpixels和Vpixels。当前处理的图像的文件头信息保存在HeaderInfo[54]中,以便翻转操作后写回图像时被恢复。Hbytes是每行图像数据在内存中占据的字节数,舍入到下一个可以被4整除的整数。例如,如果一个BMP图像具有640个水平像素,则Hbytes = 3×640 = 1920。然而,对于有201个水平像素的图像,Hbytes=3×201=603→604。因此,每行将占用604字节,将会有一个浪费的字节。
ImageStuff.h文件还包含ImageStuff.c文件中提供的BMP图像读取和写入函数Read-BMP()和WriteBMP()的声明。C变量ip保存的是当前图像的属性,也就是我们许多示例中的小狗图片。由于该变量是在本章的程序imf?lipP.c中定义的,因此它必须作为外部结构包含在ImageStuff.h中,这样ReadBMP()和WriteBMP()函数才可以正确地引用它们。

代码2.3:ImageStuff.h
头文件ImageStuff.h包含两个BMP图像处理函数的声明以及用于表示图像的结构定义。

带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

2.2.4 ImageStuff.c中的图像操作函数

ImageStuff.c文件包含两个函数,分别负责读取和写入BMP文件。将这两个函数和相关的变量定义等封装到ImageStuff.c和ImageStuff.h文件中,这样,在本书的第一部分,我们只需要在此处关注这些代码细节就可以了。无论开发CPU还是GPU程序,我们都会使用这些函数读取BMP图像。即使在开发GPU程序时,图像也会被先读入CPU,然后再传送到GPU内存中,这些将在本书的第二部分详细介绍。
代码2.4显示了WriteBMP()函数,它将处理后的BMP图像写回磁盘。该函数的输入参数包括一个指向需要输出的图像结构的指针变量img,以及一个存放输出文件名的字符串变量filename。输出BMP文件的文件头为54字节,在读取BMP时被保存起来。
代码2.4:ImageStuff.c WriteBMP(){...}
WriteBMP()将一个处理后的BMP图像写入文件。变量img是指向将要被写入文件的图像结构的指针。

带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

代码2.5中显示的ReadBMP()函数使用关键字new每次一行地为图像分配内存。在处理过程中,每个像素都是一个3字节的结构,包含该像素的RGB值。但是,从磁盘读取图像时,我们可以一次读取一整行的Hbytes字节,并将其写入长度为Hbytes的unsigned char数组中,不用考虑单个像素。
代码2.5:ImageStuff.c ... ReadBMP(){...}
ReadBMP()函数读取BMP图像并为其分配内存。所需的图像参数(如Hpixels和Vpixels)从BMP文件中提取并写入结构变量。Hbytes使用公式2.2进行计算。

带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

ReadBMP()函数从BMP文件的文件头(即BMP文件的前54个字节)中提取Hpixels和Vpixels值,并用公式2.2计算Hbytes。它用malloc()函数为图像动态分配足够的内存,这些动态分配的内存将在main()的末尾用free()函数释放。读取的图像文件名由用户指定,存放在传递给ReadBMP()的字符串参数变量filename中。BMP文件的文件头保存在HeaderInfo[]中,以便在将处理后的文件写回磁盘时使用。
ReadBMP()和WriteBMP()函数用C库函数fopen()和“rb”或“wb”选项读取或写入二进制文件。如果操作系统不能打开文件,fopen()的返回值为NULL,并向用户报告错误。这种情况往往是由文件名错误或文件已存在引起的。fopen()为新文件分配一个文件句柄和一个读/写缓冲区并将其返回给调用者。
根据fopen()参数的不同,还会对文件进行锁定,以防止多个程序因同时访问而破坏文件。通过使用缓冲区,每个字节数据可以一次一个地(即C变量类型unsigned char)从文件读取或写入文件。fclose()函数释放分配的缓冲区并取消对该文件的锁定(如果有的话)。

2.3 执行线程任务

现在我们已经知道了如何计算CPU代码运行的时间以及如何读取/写入BMP图像,让我们使用多线程来实现图像的翻转吧。多线程程序中各部分责任如下:

  • main()负责创建线程并在运行时为每个线程分配唯一的tid(例如,下面显示的ThParam [i])。
  • main()为每个线程调用一个函数(函数指针MTFlipFunc)。
  • main()还必须将其他必要的参数(如果有的话)传递给线程(也是通过ThParam[i]传递)。

带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

  • main()还负责让操作系统知道它正在创建什么类型的线程(即线程属性,由&ThAttr传入)。最后,main()只不过是另一个线程,代表它将创建的子线程发言。
  • 操作系统决定是否可以创建一个线程。线程其实是操作系统管理的资源。如果可以创建线程,操作系统就负责为该线程分配句柄(ThHandle[i])。如果不能,操作系统返回NULL(ThErr)。
  • 如果操作系统不能创建某个线程,main()负责退出或实施其他操作。

带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

  • 每个线程的职责是接收tid,执行任务MTFlipFunc(),处理需要自己处理的那部分数据。在这个方面我们会多做一些介绍。
  • main()最后的任务是等待线程完成并合并它们。这将告诉操作系统释放分配给线程的资源。

带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

2.3.1 启动线程

让我们看看函数指针是如何启动线程的。pthread_create()函数期望一个函数指针作为其第三个参数,即MTFlipFunc。这个指针从何而来?为了能够确定这一点,让我们列出参与“计算”变量MTFlipFunc的imflipP.c中的所有代码。代码2.6中列出了它们。我们的目标是为main()提供足够的灵活性,这样可以使用任何我们想要的函数来启动线程。 代码2.6列出了四种不同的函数:
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

前两个函数正是我们在1.1节中介绍的。它们是在垂直或水平方向上对图像进行翻转的串行函数。刚刚我们介绍了它们的多线程版本(上述代码的后两行),它将完成与串行版本相同的工作,除了因为使用多线程而变得更快(希望如此)!请注意,多线程版本将需要我们之前描述的tid,而串行版本不需要。
现在,我们的目标是了解如何将函数指针和数据传递给每个启动的线程。该函数的串行版本被稍作修改以消除返回值(即void),这样与没有返回值的多线程版本保持一致。这四个函数都只是对指针TheImage指向的图像稍作修改。事实证明,我们并不需要将函数指针传递给线程。相反,我们必须调用函数指针指向的函数。这个过程称为线程启动。
传递数据并启动线程的方式根据启动的是串行函数还是多线程版本的函数而有所不同。我设计的imf?lipP.c能够根据用户命令行参数运行旧版本的代码或新的多线程版本。由于两个函数的输入变量略有不同,因此定义两个单独的函数指针FlipFunc和MTFlipFunc会更容易,它们分别负责启动串行函数和多线程版本的函数。我使用了两个函数指针,如下所示:
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

让我们来澄清创建和启动一个线程之间的区别,两者都隐含在pthread_create()中。创建一个线程涉及父线程main()和操作系统之间的请求/授权机制。如果操作系统说不,什么都不会发生。因此,正是操作系统实际创建了一个线程,并为它建立了内存空间、句柄、虚拟CPU和栈区,还将一个非零的线程句柄返回给父线程,从而授权父线程启动(又名运行)另一个并行线程。
代码2.6:imflipP.c 线程函数指针
定义作为参数传递到启动线程的函数指针的代码。这是线程知道要执行什么的方式。
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

注意,虽然父线程现在已被许可运行一个子线程,但还没有发生任何事情。启动一个线程实际上是一个并行函数调用。换句话说,main()知道另一个子线程在启动后正在运行,并且可以在需要时与它通信。
main()函数也许永远不会与它的子线程通信(例如来回传递数据),如代码2.2所示,因为它不需要。子线程修改所需的内存区域并返回。在这种特定情况下,分配给子线程的任务只需要main()负责一件事情:等待子线程完成并终止(合并)它们。因此,main()唯一关心的事情是:它有新线程的句柄,并且可以通过使用pthread_join()来确定该线程何时完成执行(即返回)。所以,实际上,pthread_join(x)意味着等待句柄为x的线程运行结束。当该线程完成时,意味着它执行了return并完成了它的工作。没有理由让它继续
存在。
当线程(带有句柄x)与main()合并时,操作系统释放分配给该线程的所有内存、虚拟CPU和栈,然后该线程消失。然而,main()仍然活着,直到它到达最后一行代码并返回(代码2.2中的最后一行)。当main()执行返回操作时,操作系统将释放分配给main()(即imflipP程序)的所有资源。程序完成运行。然后,你将在Unix中获得提示符,等待下一个Unix命令,因为imflipP的执行刚刚完成。

2.3.2 多线程垂直翻转函数MTFlipV()

我们已经知道多线程程序应该如何工作了,现在来看一看每个线程在多线程版本的程序中执行的任务。这就像类比2.1,如果是独自一人,一位农民必须收获所有的1800棵树(从0到1799),而如果有两位农民来收获,他们就可以分成两部分[0 ... 899 ]和[900 ... 1799],随着农民人数的增加,每个区域的椰子树会越来越少(数据范围)。神奇的公式是公式2.1,它仅基于名为tid的单一参数来指定这些划分范围。因此,为每个单独的线程分配相同的任务(即编写每个线程将在运行时执行的函数),并在运行时为每个线程分配唯一的tid,这对于编写多线程程序足够了。
如果我们记得代码1.2中显示的垂直翻转代码的串行版本,它会逐列遍历,并将每列中的每个像素与其垂直镜像的像素交换。例如,在名为dog.bmp的640×480的图像中,行0(第一行)包含水平像素0,其垂直镜像行479(最后一行)包含像素479。所以,为了垂直翻转图像,我们的串行函数FliplmageV()必须按照以下方式逐一交换每行的像素。←→符号表示交换。
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

代码1.2用于更新内存,交换像素的FlipImageV()函数看起来像下面这样。注意:返回值类型被改为void,与该程序的多线程版本保持一致。除此之外,下面列出的代码的剩余部分看起来和代码1.2完全一样。
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

问题是:如何修改FlipImageV()函数使它能够以多线程运行?正如我们之前强调的那样,该函数的多线程版本MTFlipV()将接收一个名为tid的参数。它将处理的图像保存在全局变量TheImage中,因此不需要作为额外的输入参数进行传递。由于我们的老朋友pthread_create()期望我们给它一个函数指针,所以我们将这样定义MTFlipV():
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

在本书中,我们会遇到一些不适合并行化的函数。不容易并行化的函数通常称为不易线程化函数。在这一点上,任何读者都不应该怀疑,如果一个函数不易线程化,那么它很可能是GPU不友好的。在本节中,我认为这样的函数可能也是CPU多线程不友好的。
那么,当一项任务是“天生的串行”时,我们该怎么做?显然你不会在GPU上运行此任务。你应该把它放在CPU上,保持串行,让它快速地运行。大多数现代CPU,比如我在1.1节中提到的i7-5960x[11],都有一个称为Turbo Boost的特性,它允许CPU在运行串行(单线程)代码时在单线程上实现非常高的性能。为了实现这一目标,CPU可以将其中一个核心的时钟频率设为4 GHz,而其他核心的频率为3 GHz,从而大大提高单线程代码的性能。这使得现代和老式的串行代码都可以在CPU上获得良好的性能。
代码2.7给出了MTFlipV( )的完整代码清单。与代码1.2给出的该函数的串行版本相比,除了充当数据分块代理的tid外,没有太多差别。请注意,这段代码是一段非常简单的多线程代码。通常,每个线程的工作完全取决于程序员的逻辑。就我们的目的而言,这个简单的例子非常适合展示基本的思想。此外,FlipImageV( )函数是一个非常友好且适合多线程的函数。
代码2.7:imflipP.c ... MTflipV( ){...}
FlipImageV( )在代码1.2中,它的多线程版本需要提供tid。它和串行版本之间的唯一区别在于它处理的是部分数据,而不是全部数据。
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

2.3.3 FlipImageV( )和MTFlipV( )的比较

以下是串行垂直翻转函数FlipImageV( )和其并行版本MTFlipV( )之间的主要区别:

  • FlipImageV( )定义为函数,而MTFlipV( )定义为函数指针。这是为了让我们在使用pthread_create()启动线程时更加容易地使用这个指针。

带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

  • FlipImageV( )处理全部图像数据,而并行版本的MTFlipV( )仅处理通过与式2.1类似的公式计算出的部分图像数据。因此,MTFlipV( )需要一个传递给它的变量tid以知道它是谁。这在用pthread_create( )启动线程时完成。
  • 除了在pthread_create( )启动线程函数中使用MTFlipFunc函数指针,我们还可以通过MTFlipFunc函数指针(及其串行版本FlipFunc)自己调用该函数。要调用这些指针所指向的函数,必须使用以下表示法:

带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

  • 图像的每行占用ip.Hbytes字节。例如,根据公式2.2,对于640×480的图像dog.bmp,
    ip.Hbytes=1920字节。串行函数FlipImageV()显然必须遍历范围[0 ... 1919]中的每个字节。但多线程版本MTFlipV( )会根据tid对这些水平的1920字节进行分块。如果启动了4个线程,则每个线程需要处理的字节(和像素)范围为:

带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

  • 多线程函数的第一个任务是计算它必须处理的数据范围。如果每个线程都这样做,那么上面显示的4个像素范围就可以并行处理了。以下是每个线程如何计算其自己的范围:

    带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

线程的第一个任务是计算它的ts值和te值(线程开始和线程结束)。这是Hbytes中的范围,与上面列出的类似,基于公式2.1计算分块。由于每个像素占用3个字节(每个RGB颜色分量需要一个字节),因此函数将for循环中的col变量加3。FlipImageV( )函数不需要做这样的计算,因为它需要处理所有的数据,即Hbytes的范围是0到1919。

  • 在串行的FliplmageV( )函数中,待处理的图像通过局部变量img传递,与1.1节中介绍的版本兼容,而在MTFlipV( )中则使用全局变量(TheImage),原因将在后面的章节中介绍。
  • 多线程函数执行pthread_exit( )让main( )知道它已经完成。此时,pthread_join()函数才会继续执行下一行,处理已完成的线程。

一个有趣的情况是,如果我们用pthread_create( )只启动一个线程,那么技术上我们正在运行一个多线程程序,其中tid的范围是[0 ... 0]。这个线程仍然会计算它的数据范围,但它发现它必须处理整个范围。在imf?lipP.c程序中,FlipImageV()函数被称为串行版本,而使用1个线程的多线程版本是允许的,这被称为l线程版本。
通过比较串行代码1.2和其并行版本代码2.7,很容易看出,只要一开始就小心编写函数,通过一些小改动就能很容易地对它进行并行化。当我们对某些串行CPU代码实施GPU并行化时,这种思想非常有用。根据定义,GPU代码意味着并行代码,因此这种思想允许我们以最小的努力将CPU代码移植到GPU环境下。当然,这种情况只在某些时候成立,并不总是成立的!

2.3.4 多线程水平翻转函数MTFlipH()

代码2.8中所示为代码1.3中的串行函数FlipImageH()的多线程并行化版本MTFlipH()。与垂直翻转函数类似,多线程的水平翻转函数也需要查看tid以确定它必须处理哪部分数据。对于使用4个线程的640×480图像(480行),像素分块为:
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

对于线程负责的每一行数据来说,每个像素3个字节的RGB值都会与其水平镜像的像素进行交换。该交换从存放第0个像素RGB值的col = [0 ... 2]开始,并一直持续到最后的RGB(3字节)值被交换。对于640×480的图像来说,由于Hbytes=1920,并且没有浪费的字节,所以最后一个像素(即像素639)在col = [1917 ... 1919]处。
代码2.8:imflipP.c ... MTFlipH(){...}
代码1.3中FliplmageH()函数的多线程版本。
带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

2.4 多线程代码的测试/计时

我们已经知道了imf?lipP程序是如何工作的,现在是时候测试它了。程序的命令行语法是通过main()的解析部分来确定的,如代码2.l所示。要运行imf?lipP,一般的命令行语
法是:
imflipP InputfileName OutputfileName [v/h/V/H] [1-128]
其中,InputFileName和OutputFileName分别是要读取和写入的BMP文件名。可选的命令行参数[v/h/V/H]用于指定翻转方向(默认值是'V')。下一个可选参数是线程数,可以在1和MAXTHREADS(128)之间指定,默认值为1(串行)。
表2-1显示了同一程序在拥有4C/8T(4个核心/8个线程)的Intel i7-960 CPU上使用1到10个线程时的运行时间。我们一直测试到10个线程,并不是希望超过8个线程后,程序还能提速,而是作为完备性检查。这些检查有助于快速发现潜在的错误。功能性测试可以通过查看输出图片,检查文件大小以及运行比较两个二进制文件的比较程序(Unix diff命令)来完成。

带你读《基于CUDA的GPU并行程序开发指南》之二:开发第一个CPU并行程序

那么,这些结果告诉我们什么?首先,在垂直和水平翻转的情况下,使用多个线程很明显是有帮助的。所以,我们对该程序进行并行化并非没有用处。然而,令人不安的消息是,超过3个线程后,水平和垂直翻转似乎都没有性能的提升。对于≥4个线程的情况,你可以将结果数据简单地视为噪声!
表2-1清楚地表明,在小于3个线程时,多线程是有效果的。当然,这个结论不具普遍性。当我在i7-960 CPU(4C/8T)上运行代码2.7和代码2.8中所示的代码时,该结论是满足的,代码2.7和代码2.8是imflipP.c的核心代码。现在,你心里应该有一千个问题。下面也许是其中的一些:

  • 在2C/2T这样功能较弱的CPU上,结果会不同吗?
  • 在功能更强大的CPU上,如6C/12T,结果会怎样?
  • 在表2-1中,考虑到我们是在4C/8T的CPU上进行测试,在8个线程的配置上不是应该获得更好的结果吗?或者,至少在6个线程上获得最好的结果?为什么超过3个线程时,性能会退化?
  • 如果我们处理较小的640×480图像(如dog.bmp),而不是巨大的3200×2400图像dogL.bmp,结果会怎样?性能增长的拐点会是一个不同的线程数吗?
  • 或者,对于较小的图像,是否会出现拐点?
  • 同样是处理相同数量的3200×2400个像素为什么水平翻转比垂直翻转操作更快?
  • ……

上述列表还可以继续。不要因为表2-1失眠。对于本章,我们已经实现了我们的目标。我们知道了如何编写多线程程序,并且使程序获得了一些加速。在我们的并行编程之旅中,这已经足够了。我可以保证你会想到1000个关于为什么这个程序没有我们所希望的那么快的问题。我也可以保证,你不会想到实际上导致这种平淡表现的关键问题。回答这些问题需要一整章的内容,这就是我将要做的。在第3章中,我将回答上述所有问题以及更多你没有问的问题。现在,请你思考一下你可能不会问的问题……

上一篇:用例执行完后切换到指定的页面


下一篇:10天拿到阿里Android岗offer,想进BTAJ