2 使用GPU理解并行计算

2.1 简介

本章旨在对并行程序设计的基本概念及其与GPU技术的联系做一个宽泛的介绍。本章主要面向具有串行程序设计经验，但对并行处理概念缺乏了解的读者。我们将用GPU的基本知识来讲解并行程序设计的基本概念。

2.2 传统的串行代码

绝大多数程序员是在串行程序占据主导地位而并行程序设计仅吸引极少数技术狂的年代里成长起来的。大多数人是因为对技术感兴趣才到大学去攻读与IT有关的学位的。同时他们也会意识到将来还需要一个能够获得可观收入的工作岗位。因此，在选择专业时，他们肯定会考虑毕业后，社会上是否有足够多的就业岗位。即便在并行程序设计最火的年代，除了研究所或学术机构的岗位外，适合并行程序设计的商业岗位总是很少的。绝大多数程序员都是用简单的串行模式来开发应用软件，而这个串行模式主要是基于大学程序设计课程的教学内容，且受市场需求的驱动。

并行程序设计的发展态势一直不太明朗，与它有关的各种技术及程序设计语言一直没能将它变成主流。市场上从来没有出现过对并行硬件的大规模需求。相应地，也没有出现对并行程序员的大规模需求。每一到两年，各个CPU厂商都会推出新一代的处理器。相比之前的处理器，新一代处理器执行代码的速度更快。无须改进运行方式就可以有更快的运行效果，因此串行程序的地位稳如泰山。

并行程序通常与硬件的联系更紧密。引入并行程序的目的是为了获得更高的性能，但是这往往需要付出降低可移植性的代价。在新一代并行计算机中，原先计算机的某种特性可能会换种方式实现，甚至被取消。每隔一定的时间，就会出现一种新的革命性的并行计算机架构，从而导致所有的程序代码都要重新编写。作为程序员，如果你的知识仅局限于某一个处理器，那么从商业角度看，这些知识会随着这款处理器的淘汰而失去价值。由此可见，学习x86类型架构的程序设计比学习某种并行计算机架构的程序设计具有更大的商业意义，因为后者很可能仅有几年的使用寿命。

然而有趣的是，多年以来，两个并行程序设计标准，OpenMP和MPI，却通过不断地修改、完善而得以始终采用。面向包含多核处理器的共享存储并行计算机而设计的OpenMP标准，强调的是在单个节点内部实现并行处理。它不涉及节点间并行处理的任何概念。因此，你所能解决的问题只受到单个节点的处理能力、内存容量和辅存空间的限制。但是对于程序员而言，采用OpenMP，程序设计相对容易，因为大多数低层级的线程代码(需要采用Windows线程库函数或 POSIX线程库函数编制)都由OpenMP替你完成了。MPI(Message Passing Interface)标准用于解决节点间的并行处理，常用于定义良好的网络内的计算机集群。它常用于由几千个节点组成的超级计算机系统。每个节点只分担问题的一小部分。因此，公共资源(CPU、缓存、内存、辅存等)的大小就等于单个节点的资源量乘以网络中节点的个数。任何网络的阿喀琉斯之踵(Achilles’heel，要害)就是它的互连结构，即把机器连接在一起的网络结构。通常，节点间通信是任何基于集群的解决方案中决定最大速率的关键因素。

当然，OpenMP和MPI也可以联合使用来实现节点内部的并行处理和集群中的并行处理。但是由于应用程序编程接口(API)库和编程方法完全不同，所以这种情况并不常见。OpenMP的并行指令允许程序员通过定义并行区，从而从一个较高的层次分析算法中的并行性;而 MPI却需要程序员做大量的工作来显式地定义节点间的通信模型。

既然已经花很长时间才掌握一种API库，程序员都不愿意再学习另外一种。因此，适合于一台计算机就能解决的问题通常采用 OpenMP，而需要用集群来解决的大问题就采用 MPI。

本书将要探讨的GPU编程语言CUDA，却能够很好地将OpenMP和MPI联系在一起例如,CUDA 提供的类 OpenMP指令(OpenACC)就很方便地供熟悉 OpenMP 的程序员采用。OpenMP、MPI和CUDA正在越来越多地出现在大学计算机专业本科生或研究生的课堂教学内容中。

然而，绝大多数串行程序设计者第一次接触并行程序是在介绍多核处理器的时候。除了少数技术狂之外，他们往往对眼前的并行处理环境视而不见，因为多核处理器主要用于实现“任务并行”(task parallelism)，这是一种基于操作系统的并行处理，后面我们再详细介绍。

显而易见，今天的计算机技术正在向着多核的方向前进。越来越多的程序员开始关注多核处理器。几乎所有商场销售的台式机要么采用双核处理器，要么采用四核处理器。因此

程序员开始利用多线程来发挥处理器中多核的作用。

线程是程序中一个独立的执行流，它可以在主执行流的要求下分出或聚合。通常情况下，CPU程序拥有的活动线程数量，不超过其包含的物理处理核数量的两倍。就像在单核处理器中，操作系统的任务是分时、轮流运行的，每个任务只能运行一小段时间，从而实现数量多于物理 CPU 核数的众多任务同时运行。

然而，随着线程数量的增加，终端用户也开始感觉到线程的存在。因为在后台，操作系统需要频繁进行“上下文切换”(即对于一组寄存器进行内容的换入、换出)。而“上下文切换”是一项很费时的操作，通常需要几千个时钟周期，所以CPU的应用程序的线程数要尽量比 GPU 的少。

2.3 串行/并行问题

线程会引起并行程序设计中的许多问题，例如，资源的共享。通常，这个问题用信号灯semaphore)来解决，而最简单的信号灯就是一个锁或者令牌(token)。只有拥有令牌的那个线程可以使用资源，其他线程只能等待，直到这个线程释放令牌。因为只有一个令牌，所以所有工作都有条不紊地进行。

当同一线程必须拥有两个或者更多的令牌时，就会出现问题。例如，在线程0拥有令牌0而线程1拥有令牌1的情况下，如果线程0想得到令牌1而线程1想得到令牌0，想得到的令牌没有了，线程0和线程1就只好休眠，直到它们期待的令牌出现。由于没有一个线程会释放掉已经拥有的令牌，所以所有的线程将永远等待下去。这就是所谓的“死锁’(deadlock)，如果程序设计不当，死锁将不可避免地发生。

当然，在极偶然的情况下，程序可以共享资源而不发生死锁。无论哪种加锁系统，每一个线程都必须正确地使用资源。也就是说，它们必须先申请令牌，如果没成功则等待。获得令牌后，才执行相应的操作。这就需要程序员定义好共享的资源，并制定恰当的机制来协调多线程对该资源的更新操作"。然而，在任何一个团队里都有若干个程序员，即便有一个程序员不遵守规则，或者并不知道它是一个共享资源，你的程序多数情况下不会正常工作。我曾经为一个大公司开发的项目里就出现过这个现象。所有的线程都申请一个锁，如果没成功则等待。获得令牌后，就更新共享资源。一切都运行正常，所有的代码都通过了质量保证检查(QualityAssurance，QA)和所有的测试。然而投入运行后，现场的用户偶尔会报告说某个参数被重置为0了，看上去像随机发生的。由于跟踪发现Bug的前提往往是它能够持续地引发同一个问题，所以随机的 Bug 总是很难发现的。

最后是公司里的一个实习生发现了问题的原因。在代码中一个与其完全无关的区域里，一个指针在特定的条件下没有被初始化。在程序的运行过程中，当线程以某种特定的顺序执行时，这个指针就会碰巧指向受我们保护的数据。程序中的其他代码会将这个指针所指向变量的值初始化成0。这样，受我们保护的并被线程共享的参数的值就被清除了。

这是基于线程操作的一个让人为难的地方。线程操作的是一个共享的内存空间，这既可以带来不借助消息就可以完成数据交换的便利，也会引起缺乏对共享数据保护的问题。

可以用进程来替换线程。不过，因为代码和数据的上下文都必须由操作系统保存，所以操作系统装入进程就要吃力得多。相比之下，只有线程代码的上下文(一个程序或指令计数器加上一组寄存器)由操作系统保存，而数据空间是共享的。总之，进程和线程可以在任意时刻、在程序中的不同区域分别执行。

默认情况下，进程在一个独立的内存空间内运行。这样就可以确保一个进程不会影响其他进程的数据。因此，一个错误的指针访问将引发“越界访问”异常，或者很容易在特定的进程中找到 Bug。不过，数据传递只能通过进程间消息的发送和接收来完成。

一般说来，线程模型较适合于OpenMP，而进程模型较适合于MPI。在GPU的环境下就需要将它们混合在一起。CUDA使用一个线程块(block)构成的网格(grid)。这可以看成是一个进程(即线程块)组成的队列(即网格)，而进程间没有通信。每一个线程块内部有很多线程，这些线程以批处理的方式运行，称为线程束(warp)。后续的章节中我们将进一步介绍。

2.4 并发性

并发性的首要内涵是，对于一个特定的问题，无须考虑用哪种并行计算机来求解，而只需关注求解方法中哪些操作是可以并行执行的。

如果可能，请设计出一个公式来把每一个输出数据表示成输人数据的函数。不过，对于某些算法而言，这显得很麻烦，例如，迭代次数很大的算法。对于这些算法，可以单独考虑每一步或每一次迭代。能否将对应每一步的数据表示成输入数据集的一个变换?如果能，则你只需拥有顺序执行的一组内核函数(迭代步)即可解决问题。只需将这些操作压人队列(或者处理流)，计算机将依次执行该队列的操作。

很多问题属于“易并行”(embarrassingly parallel)问题，其实这个名称还是相当保守的。如果能够设计出一个公式把每一个输出数据都表示成相互无关的，例如，矩阵乘法，那将是很令人开心的结局。这类问题可以在 GPU上得到很好的解决而且编程很简单。尽管算法中可能有一个阶段不是“易并行”，但某一步或某几步还是能够用这种方式表达，这也不错。尽管该阶段会成为一个“瓶颈”(bottleneck)，还会让程序员很劳神。但对于问题的其他部分，程序员还是很容易就可以编写出在GPU上求解的代码。

如果求解问题的算法在计算每一个点的值的时候，必须知道与其相邻的其他点的值，那么算法的加速比(speed up)最终将很难提高。在这种情况下，对一个点的计算就需要投入多个处理器。在这一点上，计算将会变得很慢，因为处理器(或者线程)需要花费更多的时间来进行通信以实现数据共享，而不做任何有意义的计算。至于你到底会遇到怎样糟糕的情况，则取决于通信的次数和每次通信的开销。

由于“易并行”不需要或者只需少许线程间或线程块间通信，所以CUDA是很理想的并行求解平台。它用基于片上资源的、显式的通信原语来支持线程间通信。但是块间通信只有通过按顺序调用多个内核程序才能实现，而且内核间通信需要用到片外的全局内存。块间通信还可以通过对全局内存的原子操作来实现，当然使用这种方法会受到一定的限制。CUDA将问题分解成线程块的网格，每块包含多个线程。块可以按任意顺序执行。不过在某个时间点上，只有一部分块处于执行中。一旦被调度到 GPU包含的N个“流处理器簇”（Streaming Multiprocessors，SM)中的一个上执行，一个块必须从开始执行到结束。网格中的块可以被分配到任意一个有空闲槽的SM上。起初，可以采用“轮询调度”(round-robin)策略，以确保分配到每个SM上的块数基本相同。对绝大多数内核程序而言，分块的数量应该是GPU中物理SM数量的八倍或者更多倍。

以一个军队比喻，假设有一支由士兵(线程)组成的部队(网格)。部队被分成若干个连队(块)，每个连队由一位连长来指挥。按照32名士兵一个班(一个线程束)，连队又进一步分成若干个班，每个班由一位班长来指挥(参见图2-1)。

图2-1 基于GPU的线程视图

要执行某个操作，总司令(内核程序/主机程序)必须提供操作名称及相应的数据。每个士兵(线程)只处理分配给他的问题中的一小块。在连长(负责一个块)或班长(负责一束)的控制下，束与束之间的线程或者一束内部的线程之间，要经常地交换数据。但是，连队(块)之间的协同就得由总司令(内核函数/主机程序)来控制了。

因此，当思考CUDA程序如何实现并发处理时，你应该用这种非常层次化的结构来协调几千个线程的工作。尽管一开始听上去很复杂，但是对绝大多数“易并行”程序而言，仅仅需要针对一个线程思考它计算输出数据的那一点。在一个典型的 GPU 上可以运行 24K个“活动”线程。在费米架构 GPU上，你总共可以定义65535x65535x1536个线程，其中 24K个线程随时都是活动的。这表明一个节点就足够满足单点中绝大多数问题的求解要求了。

局部性

在过去的十几年间，计算性能的提高已经从受限于处理器的运算吞吐率的阶段，发展到迁移数据成为首要限制因素的阶段。从设计处理器过程中的成本来讲，计算单元(Algorithmic Logic Unit，ALU)是很便宜的。它们能够以很高的速度运行，而消耗很小的电能并占用很少的物理硅片空间。然而,ALU的工作却离不开操作数。将操作数送入计算单元，然后从计算单元中取出结果，耗费了大量的电能和时间。

在现代计算机设计中，这个问题是通过使用多级缓存来解决的。缓存的工作基础是空间局部性(地址空间相对簇集)和时间局部性(访问时间的集)。因此，之前被访问过的数据很可能还要被再次访问(时间局部性);刚刚被访问过的数据附近的数据很可能马上就会被访问(空间局部性)。

当任务被多次重复执行时，缓存的作用会充分地发挥。假设一个工人带着一个装有4件工具的工具箱(缓存)，当分配给他的大量工作都是相同的时候，这4件工具将被反复使用缓存命中)。

反之，大量的工作都需要不同的工具，情况就不一样了。例如，工人来上班时，并不知道今天会分配给他什么工作。简单来说，今天的工作需要一件不同的工具。由于它不在工具箱(一级缓存)中，那么他就到工具柜(二级缓存)里找。

偶尔，工人可能需要一个工具箱和工具柜里都没有的、特殊的工具或零件，这时他就得停下手中的工作，跑到附近的硬件仓库(全局内存)里，取回他想要的东西。由于公路上可能发生拥堵，或者五金商店门前排起了长队(其他进程争相访问主存)，因此，无论是工人还是客户都不知道为了拿到工具需要花费多少时间(延迟)。

显然，工人的时间效率很低。因此，每项工作都需要一个新的、不同的工具或零件，工人就只得去工具柜或者五金商店去取。而这个取的过程，工人并不是忙于手里的工作。

与到硬件仓库里去取工具类似，到硬盘或者固态硬盘(Solid-StateDrive，SSD)里取数据，也是很糟糕的。尽管固态硬盘比硬盘要快得多，好比一个普通的送货员需要几天才能把硬盘里的数据送到，而送货员一个晚上就能把固态硬盘里的数据送到，但是与访问全局内存相比，它还是很慢的。

某些现代处理器已经支持多线程。如某些英特尔处理器中，每个处理器核支持2个硬件线程即“超线程”(hyperthreading)。接着上面的比喻,“超线程”相当于给工人配了一名助手,并分配给他两项任务。在处理某项任务时，每当需要一个新的工具或零件，工人就派他的助手去取。然后工人就切换去处理另一项任务。假定这个助手总是能够在另一项任务也需要新的工具或零件前就能返回，那么工人就始终处于忙碌的工作状态。

尽管改进后时间效率提高了，但是从硬件仓库(全局内存)里取回新的工具或零件到底有多少延迟还是不清楚。通常，访问全局内存的延迟大概有几百个时钟周期。对于传统的处理器设计，这个问题的答案是不断增大缓存的容量。实际上，为了降低访问仓库的次数，必须采用一个更大的工具柜。

然而，这种办法会增加成本。一则更大的工具柜需要投入更多的资金，二则在一个更大的工具柜里查找工具或零件需要更多的时间。因此，在当前绝大多数处理器设计中，这种方法表现为一个工具柜(二级缓存)加一个货车(三级缓存)。在服务器处理器中，这种情况尤为突出，就如同工厂购买了一辆18轮大货车来保证工人总是处于忙碌状态。

因为一个基本的原因(局部性)，所以上述工作是必须的。CPU是设计以运行软件的，而编制软件的程序员并不一定关心局部性。无论处理器是否试图向程序员隐藏局部性，局部性是客观存在的。为了降低访存延迟而需要引人大量的硬件并不能否认局部性是客观存在的这个事实。

GPU的设计则采用一个不同的方法。它让GPU的程序员负责处理局部性，并给程序员提供很多小的工具柜而不是一辆18轮大货车，同时给他配备很多工人。

对于GPU程序设计，程序员必须处理局部性。对于一个给定的工作，他需要事先思考需要哪些工具或零件(即存储地址或据结构)，然后一次性地把它们从硬件仓库(全局内存)取来，在工作开始时就把它们放在正确的工具柜(片内存储器)里。一旦数据被取来，就尽可能把与这些数据相关的不同工作都执行了，避免发生“取来--存回--为了下一个工作再取”。

因此,“工作--等待--从全局内存取”、“工作一等待一从全局内存取”……这样连续的周期就被打破了。我们可以用生产流水线来比拟，一次性提供给工人一筐零件，而不是工人需要一个零件就到仓库管理员那里去取。后者导致工人的大多数时间被浪费了。这个简单的计划使得程序员能够在需要数据前就把它们装入片内存储器。这项工作既适合于诸如GPU内共享内存的显式局部存储模型，也适合于基于CPU的缓存。在共享内存的情况下，你可以通知存储管理单元去取所需的数据，然后就回来处理关于已有的其他数据的实际工作。在缓存的情况下，你可以用特殊的缓存指令来把你认为程序将要使用的数据，先行装人缓存。

与共享内存相比，缓存的麻烦是替换和对“脏”数据的处理。所谓“脏”数据是指缓存中被程序写过的数据。为了获得缓存空间以接纳新的有用数据,“脏”数据必须在新数据装入之前写回到全局内存。这就意味着，对于延迟未知的全局内存访问，我们需要做两次，而不是一次--第一次是写旧的数据，第二次是取新的数据。引入受程序员控制的片上内存，带来的好处是程序员可以控制发生写操作的时间。如果你正在进行数据的局部变换，可能就没有必要将变换的中间结果写回全局内存。反之用缓存的话，缓存控制器就不知道哪些数据应该写、哪些数据可以抛弃。因此，它全部写人。这势必增加了很多无用的访存操作，甚至会造成内存接口拥塞。

尽管做了很多工作，但是并不是每个算法都具备“事先预知的”内存访问模式，而程序员正是需要对此进行优化。同时，也不是每个程序员都想处理局部性的事务，所以程序的局部性要么是“与生俱有的”，要么就根本没有。要想深人理解局部性，最好、最有效的方法就是开发一个程序，验证概念，然后琢磨如何改进局部性。

为了使这种方法得到更好的应用，并改进那些没有很好定义数据或执行模式的算法的局部性，新一代GPU(计算能力2.x以上)同时设有一级和二级缓存。它们还可以根据需要配置成缓存或者共享内存，这样程序员就可以针对具体的问题灵活地配置硬件条件了。

2.5 并行处理的类型

2.5.1 基于任务的并行处理

如果仔细分析一个典型的操作系统，我们就会发现它实现的是一种所谓任务并行的并行处理，因为各个进程是不同的、无关的。用户可以在上网阅读文章的同时，在后台播发他音乐库中的音乐。多个CPU核运行不同的应用程序。

就并行程序设计而言，这可以通过编写一个程序来实现，这个程序由多个段组成，这些段将信息从一个应用程序“传递”(通过发送消息)到另一个应用。Linux操作系统的管道操作符(|)就具有这个功能。一个程序(例如grep)的输出是另一个程序(例如sort)的输人。这样，就可以轻松地对一组输人文件进行扫描(通过grep程序)，以查看是否包含特定的字符，然后输出排好序的结果(通过sort 程序)。每个程序都分别调度到不同CPU核上运行。一个程序的输出作为下一个程序的输人，这种并行处理称为流水线并行处理(pipelincparallelism)。借助一组不同的程序模块，例如，Linux操作系统中各种基于文本的软件工具用户就可以实现很多有用的功能。也许程序员并不知道每个人所需要的输出，但通过共同工作并可以轻松连接在一起的模块，程序员可以为广泛的、各种类型的用户服务。

这种并行处理向着“粗粒度并行处理”(coarse-grained parallelism)发展，即引人许多计算能力很强的处理器，让每个处理器完成一个庞大的任务。

就 GPU而言，我们看到的“粗粒度并行处理”是由GPU卡和 GPU内核程序来执行的。GPU有两种方法来支持流水线并行处理模式。一是，若干个内核程序被依次排列成一个执行流，然后不同的执行流并发地执行;二是，多个GPU协同工作，要么通过主机来传递数据要么直接通过 PCI-E总线，以消息的形式在GPU之间直接传递数据。后一种方法，也叫“点对点”(Peer-to-Pcer，P2P)机制，是在CUDA4.xSDK中引人的，需要特定的操作系统/硬件/驱动程序级支持。

和任何生产流水线一样，基于流水线的并行处理模式的一个问题就是，它的运行速度等于其中最慢的部件。因此，若流水线包含5个部件，每个部件需要工作1秒，那么我们每1秒钟就可以产生一个结果。然而，若有一个部件需要工作2秒，则整个流水线的吞吐率就降至每2秒钟产生一个结果。

解决这个问题的方法是“加倍”(twofold)。让我们用工厂的流水线来打比方。由于工作复杂，Fred负责的工段需要花费2秒钟。如果我们为Fred配一名助手Tim，那么Fred 就可以把工作一分为二，把一半分给Tim。这样我们就又回到每个工段只需1秒的状态。现在我们拥有了一个6段流水线而不是5段流水线，但流水线的吞吐率又重新回到每秒钟一个结果。出于某种考虑，经过精心设计(参见第11章)，你可以将4个GPU加到一个面PC中。这样，若我们仅有一个GPU，则处理一个特定的工作流花费的时间太长。若我们增加一个GPU，则这个节点的整体处理能力就提高了。但是我们需要考虑在两个GPU之间如何划分工作。简单的 50/50划分可能不可行。若仅能实现70/30划分，则最大收益是当前运行时间的 7/10(70%)。若我们再增加一个GPU并能够分给它占总时间20%的任务，即按50/30/20划分。这样与一个GPU相比，加速效果是原来时间的1/2或50%。无论如何，整体的执行时间仍取决于最慢的时间。

为了加速而使用一个CPU/GPU组合时，也需要考虑上述问题。如果我们把80%的工作从CPU移到GPU上，而GPU计算这些任务仅需原来时间的10%，那么加速比是多少呢?由于 CPU花费原来时间的20%，而GPU花费原来时间的10%，但是它们是并行的，因此决定性因素仍然是CPU。由于GPU是并行地与CPU一起工作，且工作时间少于CPU，所以它的工作时间就忽略不计了。因此，最大加速比就等于程序执行时间最长那部分占整个程序比

例的倒数。这称为“阿姆达尔法则”(Amdahl’slaw)，它表示任意加速比的上限。它让我们在一开始，一行代码都还没写的情况下，就知道可能达到的最大加速比。无论如何，你都要做串行操作。即便把所有的计算都移到GPU上，你也需要用CPU来访问辅存、装入和存回数据。你还需要与 GPU交换数据以完成输人及输出(I/O)。因此，最大加速比取决于程序中计算或算术部分占整个程序的比例加上剩下的串行部分的比例。

2.5.2 基于数据的并行处理

在过去的二十多年间，计算能力不断增长。现在我们已经拥有了运算速度达到每秒万亿次浮点操作的 GPU。然而，跟不上计算能力增长步伐的是数据的访问时间。基于数据的并行处理的思路是首先关注数据及其所需的变换，而不是待执行的任务。基于任务的并行处理更适合于粗粒度并行处理方法。让我们看一个对4个不同且无关的等长数组分别进行不同变换的例子。我们有4个CPU核以及1个带有4个SM的GPU。若对这个问题采用基于任务的分解，则4个数组将被分别赋给4个CPU核或者GPU中的每个SM。对问题的这种并行分解是在只考虑任务或变换，而不考虑数据的思路下进行的。在CPU上，我们将产生4个线程或进程来完成任务。在GPU上，我们将使用4个线程块，并把每个数组的地址分别送给1个块。在更新的费米架构和开普勒架构GPU上，我们也可以产生4个并发运行的内核程序，每个内核程序处理1个数组。

基于数据的分解则是将第1个数组分成4数据块，CPU中的1个核或者GPU中的1个SM 分别处理数组中的1数据块。处理完毕后，再按照相同的方式处理剩下的3个数组。对采用GPU处理而言，将产生4个内核程序，每个内核程序包含4个或者更多的数组块。对问题的这种并行分解是在考虑数据后再考虑变换的思路下进行的。

由于我们的CPU仅有4个核，所以使我们想到将数据分成4数据块。我们既可以让线程0处理数组元素0，线程1处理数组元素1，线程2处理数组元素2，线程3处理数组元素3，以此类推。我们还可以把数组分成4数据块，每个线程处理数组中对应的一数据块。在第一种情况下，线程0去取元素0。由于CPU包含多级缓存，数据将存人缓存。通三级缓存是被所有的核心共享的。因此，第一次内存访问取来的数据需要分发给所有常，CPU核。相反在第二种情况下，需要进行4次不同的内存访问，取来的数据分别存人到三级缓存中的不同缓存中。因为CPU核心需要把数据写回内存，所以后一种方法通常更好些。第一种情况下，CPU核交替地使用数据，这意味着，缓存必须协调和组合来自不同CPU核心的写操作，这是很糟糕的思路。

如果算法允许，我们还可以探讨另一种类型的数据并行处理--单指令多数据(SingleInstruction，Multiple Data，SIMD)模型。这需要特殊的 SIMD指令，例如，许多基于 x86 型CPU提供的MMX、SSE、AVX等。这样，线程0就可以取出多个相邻的数组元素，并用一条 SIMD 指令来进行处理。

同样的问题，如果我们用GPU来处理，每个数组则需要进行不同的变换，且每一个变换将映射以被看成一个单独的GPU内核程序。与CPU核不同，每个SM可以处理多个数据块，每个数据块的处理被分成多线程来执行。因此为了提高GPU的使用效率，我们需要对问题进行进一步的分解。通常，我们将块和线程做一个组合，使得一个线程处理一个数组元素。使用CPU，让每个线程处理多个数据，会有很多好处。相比之下，由于GPU仅支持“加载”(load)/“存储”(store)/“移动”(move)三条显式的 SIMD 原语，那么它的应用受到限制。但这反过来促进了GPU“指令级并行处理”(Instruction-Level Parallelism，ILP)功能的增强。在本书的后面，我们将看到ILP给我们带来的好处。

在费米架构和开普勒架构GPU上，我们有一个共享的二级缓存，它的功能与CPU上的三级缓存相同。因此，在CPU上，一个线程访存的结果可以从缓存直接分布给其他线程。早期的硬件处理器，没有缓存。但是在GPU上，相邻的内存单元是通过硬件合并(组合)在一起进行存取的。因此单次访存的效率就更高了。具体细节可查阅第6章关于内存的介绍。

GPU与CPU在缓存上的一个重要差别就是“缓存一致性”(cache coherency)问题。对于“缓存一致”的系统，一个内存的写操作需要通知所有核的各个级别的缓存。因此，无论何时，所有处理器核看到的内存视图是完全一样的。随着处理器中核数量的增多，这个“通知”的开销迅速增大，使得“缓存一致性”成为限制一个处理器中核数不能太多的一个重要因素。“缓存一致”系统中最坏的情况是，一个内存写操作会强迫每个核的缓存都进行更新进而每个核都要对相邻的内存单元进行写操作。

相比之下，非“缓存一致”系统不会自动地更新其他核的缓存。它需要由程序员写清楚每个处理器核输出的各自不同的目标区域。从程序的视角看，这支持一个核仅负责一个输出或者一个小的输出集。通常，CPU遵循“缓存一致”原则，而 GPU 则不是。故 GPU 能够扩展到一个芯片内具有大数量的核心(流处理器簇)。

为了简单起见，我们假设4个线程块构成一个GPU内核程序。这样，GPU上就有4个内核程序，而CPU上有4个进程或线程。CPU也可能支持诸如“超线程”这样的机制，使得发生停顿事件(例如，访问缓存不命中)时，CPU能够处理其他的进程或线程。这样，我们就可以把 CPU上进程的数量提高到8，从而得到性能的提升。然而，在某个时间点上，甚至在进程数小于核数的时候，CPU可能会遇到线程过多的情况。

这时，内存带宽就变得很拥挤，缓存的利用率急剧下降，导致性能降低而不是增高。

在GPU上，4个线程块无论如何也不能满足4个SM的处理能力。每个SM最大能处理8个线程块(开普勒架构中为16个线程块)。因此，我们需要8x4=32个线程块才能填满4个SM。既然需要完成4个不同的操作，我们就可以借助其流处理功能(参见第8章关于使用多GPU的内容)，在费米架构GPU上同时启动4个内核程序。最终，我们总共可以启动16个线程块来并行处理4个数组。若采用CPU，则一次处理一个数组效率会更高些，因为这会提高缓存的利用率。总之，使用GPU时，我们必须确保总是有足够多的线程块(通常至少是GPU内SM数量的8~16倍)。

2.6 弗林分类法

前面我们用到一个词“SIMD”。它来源于划分不同计算机架构的弗林分类法(Flynn’staxonomy)。根据弗林分类法，计算机的结构类型有:

SIMD--单指令，多数据

MIMD--多指令，多数据

SISD--单指令，单数据

MISD--多指令，单数据

绝大多数人熟悉的标准串行程序设计遵循的是SISD模型，即在任何时间点上只有一个指令流在处理一个数据项，这相当于一个单核CPU在一个时刻只能执行一个任务。当然它也可以通过所谓的“分时”(time-slicing)机制，即在多个任务间迅速切换，达到“同时’执行多个任务的效果。

我们今天看到的双核或4核桌面计算机就是MIMD系统。它具有一个线程或进程的工作池，操作系统负责逐个取出线程或进程，将他们分配到N个CPU核中的一个上执行。每个线程或进程具有一个独立的指令流，CPU内部包含了对不同指令流同时进行解码所需的全部控制逻辑。

SIMD系统尽可能简化了它的实现方法，针对数据并行模型，在任何时间点，只有一个指令流。这样，在CPU内部就只需要一套逻辑来对这个指令流进行解码和执行，而无须多个指令解码通路。由于从芯片内部移除了部分硅实体，因此相比它的MIMD兄弟，SIMD系统就可以做得更小、更便宜、能耗更低，并能够在更高的时钟频率下工作。

很多算法只需要对很少量的数据点进行这样或那样的处理。很多数据点常常被交给一条SIMD指令。例如，所有的数据点可能都是加上一个固定的偏移量，再乘以一个数据，例如放大因子。这就很容易地用SIMD指令来实现。实际上就是你编写的程序，从“对一个数据点进行一个操作”改为“对一组数据进行一个操作”。既然这组数据中每一个元素需要进行的操作或变换是固定的，所以“访问程序存储区取指令然后译码”只需进行一次。由于数据区间是有界且连续的，所以数据可以全部从内存中取出，而不是一次只取一个字。然而，如果算法是对一个元素进行A变换而对另一个元素进行B变换，而对其他元素进行C变换，那么就很难用 SIMD来实现了。除非这个算法由于非常常用而采用硬编码在硬件中实现，例如“先进的加密标准”(Advanced Encryption Standard，AES)”和H.264(一种视频压缩标准)。

与SIMD稍有不同，GPU实现的是被英伟达称为“单指令多线程(Single InstructionMultiple Thread,SIMT)的模型。在这种模型中，SIMD指令的操作码跟 CPU中硬件实现的方式不同，它指示的并不是一个固定的功能。程序员需要通过一个内核程序，指定每个线程的工作内容。因此，内核程序将统一读入数据，程序代码根据需要执行A、B或C变换。实际上，A、B、C是通过重复指令流而顺序执行的，只不过每次执行时屏蔽掉无须参与的线程。与仅支持 SIMD的模型相比，从理论上说，这个型更容易掌握。

2.7 常用的并行模式

很多并行处理问题都可以按照某种模式来分析。在很多程序中，尽管并不是每个人都意识到它们的存在，但我们也可以看到不同的模式，按照模式来分析，使得我们能够对问题进行深人的解构或抽象，这样就很容易找到解决问题的办法。

2.7.1 基于循环的模式

几乎任何一个编写过程序的人都会对循环很熟悉。不同循环语句(如，for、do…while、while)的主要区别在于入口、退出条件以及两次循环迭代之间是否会产生依赖。循环的迭代依赖是指循环的一次迭代依赖于之前的一次或多次先前迭代的结果。这些依赖将并行算法的实现变得十分困难，而这是我们希望消除的。如果消除不了，则通常将循环分解成若干个循环块，块内的选代是可以并行执行的。循环块0执行完后将结果送给循环块1，然后送给循环块2，以此类推。本书的后面有一个例子就是采用这种方法来处理前缀求和(prefix-sum)算法。

基于循环的迭代是实现并行化的模式中最容易的一个。如果循环间的依赖被消除掉了，那么剩下的问题就是在可用的处理器上如何划分工作。划分的原则是让处理器间通信量尽可能少，片内资源(GPU上的寄存器和共享内存，CPU上的一级/二级/三级缓存)的利用率尽可能高。糟糕的是，通信开销通常会随着分块数目的增多而迅速增大，成为提高性能的瓶颈、系统设计的败笔。

对问题的宏观分解应该依据可用的逻辑处理单元的数量。对于CPU，就是可用的逻辑硬件线程的数量;对于GPU，就是流处理器簇(SM)的数量乘以每个SM的最大工作负载。依赖于资源利用率、最大工作负荷和GPU模型，SM的最大工作负载取值范围是1~16块。请注意，我们使用的词是逻辑硬件线程而不是物理硬件线程。某些英特尔CPU采用所谓的“超线程”技术，在一个物理CPU核上支持多个逻辑线程。由于GPU在一个SM 内运行多个线程块，所以我们需要用 SM 的数量乘以每个SM 支持的最大块数。在一个物理设备上支持多个线程可以使设备的吞吐率最大化，也就是说在某线程等待访存或者 I/O类型的操作时，设备可以处理其他线程的工作。这个倍数的选择有助于在GPU上实现负载平衡(load balancing)，并可以应用于改进新一代GPU。当数据划分导致负载不均时，这一点表现得尤为明显--某些块花费的时间远远大于其他块。这时，可以用几倍于SM 数目的数量作为划分数据的基础。当一个SM空闲下来后，它可以去存放待处理块的“池子”里取一个块来处理。

然而对于CPU，过多的线程数量却可能会导致性能下降，这主要是由于上下文切换时操作系统以软件的形式来完成。对缓存和内存带宽竞争的增多，也要求降低线程的数量。因此对于一个基于多核 CPU的解决方案，通常它划分问题的粒度要远大于面向 GPU的划分粒度。如果在 GPU上解决同一个问题，你则要对数据进行重新划分，把它们划分成更小的数据块。

当考虑采用循环并行来处理一个串行程序时，最关键的是发现隐藏的依赖关系。在循环体中仔细地查找，确保每一次迭代的计算结果不会被后面的迭代使用。对于绝大多数循环而言，循环计数通常是从0~设置的最大值。当遇到反过来采用递减计数的循环，你就应该小心些。为什么这个程序员采用相反的计数方法呢?很可能就是循环中存在某种依赖。如果不了解这一点就将循环并行化了，很可能把其中的依赖破坏掉。我们还需要考虑的另外一种情况是有一个内循环和多个外循环。如何将它们并行化呢?对于CPU，由于你只有有限的线程，所以只能将这些外循环并行化。不过，像前面提到的那样，可以这样处理的前提是不存在循环迭代依赖。如果分配给 GPU执行的内循环是很小的，通常用一个线程块内的线程来处理。由于循环迭代是成组进行的，所以相邻的线程通常访问相邻的内存地址，这就有助于我们利用访存的局部性，这一点对CUDA程序设计十分重要。外循环的并行处理都是用线程块来实现的这部分内容将在第5章详细介绍。

考虑到大多数循环是可以展开的，因此把内循环和外循环合并成一个循环。例如，图像处理算法中，沿X轴的处理是内循环，而沿Y轴的处理是外循环。可以通过把所有像素点看成是一个一维数组来展开循环，这样迭代就是沿像素点而不是图像坐标进行。尽管编程时麻烦一些，但是在每次循环包含的迭代次数很小时，收效很大。因为这些小的循环带来的循环开销相对每次迭代完成的有效工作比较大，所以这些循环的效率很低。

2.7.2 派生/汇集模式

派生/汇聚模式是一个在串行程序设计中常见的模式，该模式中包含多个同步点而且仅有一部分内容是可以并行处理的，即首先运行串行代码，当运行到某一点时会遇到一个并行区，这个并行区内的工作可以按某种方式分布到P个处理器上。这时，程序就“派生”(fork)出N个线程或进程来并行地完成这些工作。N个线程或进程的执行是独立的、互不相关的当其工作完成后，则“汇聚”(join)起来。在OpenMP中常常可以看见这种处理方法--程序员用编译指令语句定义可并行区，并行区中的代码被分成 N个线程，随后再汇聚成单个线程。

如图 2-2所示，有一个输人的数据项队列和三个处理单元(即CPU核)，输人数据队列被分成三个小的数据队列，一个处理单元处理一个小的数据队列，每个队列的处理是互不相关的，处理结果分别写在结果队列的相应位置。

通常，派生/汇聚模式是采用数据的静态划分来实现，即串行代码派生出N个线程并把数据集等分到这N个线程上。如果每个数据块的处理时间相同的话，这种划分方法是很好的。但是，由于总的执行时间等于最慢线程的执行时间，所以如果分配给一个线程太多的工作，它将成为决定总时间的一个因素。

图2-2由N个线程处理一个数据队列

诸如 openMP这样的系统跟GPU的方案类似，实现动态的调度分配。具体办法是，先创建一个“线程池”(对 GPU 而言是一个“块池”)，然后池中的线程取一个任务执行，执行完后再取下一个。假设有1个任务需要10个单位时间才能完成，而其余20个任务需要1个单位时间就能完成，则它们只能分配到空闲的处理器核上执行。现在有一个双核处理器，则把那个需要10个单位时间的大任务和5个需要1个单位时间的小任务分配给核1，而把其余的15个需要1个单位时间的小任务分配给核2。这样，核1与核2就基本上可以同时完成任务了。

在图2-2的例子中，我们选择派生3个线程。既然队列中有6个数据，为什么不派生6个线程呢?这是因为在实际工作中，我们要处理的数据多达好几百万，无论用哪种方法，派生一百万个线程都会使任何一个操作系统以某种方式崩溃掉。

通常，操作系统执行的是一个“公平的”调度策略。因此，每个线程都需要按顺序，分配到4个可用的处理器核中的某一个上处理，每个线程都需要一个它自己的内存空间，例如，在 Windows操作系统中，每个线程需要1MB的栈空间。这就意味着，在派生出足够多的线程前，我们已经迅速地用尽了全部的内存空间。

因此，对于CPU而言，程序员或者多数多线程库通常是按照处理器的个数来派生相同数目的逻辑处理器线程。由于CPU创建或删除一个线程的开销是很大的，而且线程过多也会降低处理器的利用率，所以常常使用一个“工人”线程池，池中的“工人”每次从待处理的任务队列中取一个任务来处理，处理完后再取下一个。

对于GPU则相反，我们的确需要成千上万个线程。我们还是使用在很多先进的CPU调度程序中使用过的线程池的概念，不过将“线程池”改为“线程块池”更好。GPU上可以并发执行的“线程块”的数目存在一个上限。每个线程块内包含若干个线程。每个线程块内包含的线程的数目和并发执行的“线程块”的数目会随着不同系列的 GPU 而不同。

派生/汇聚模式常常用于并发事件的数目事先并不确定的问题。遍历一个树形结构或者路径搜索这类算法，在遇到另一个节点或路径时，就很可能会派生出额外的线程。当所有的路径都被考查后，这些线程就汇聚回线程池中或者汇聚后又开始新一轮的派生。

由于在启动内核程序时，块/线程的数量是固定的，所以GPU并不是天生就支持这种模式。额外的块只能由主机程序而不是内核程序启动。因此，在GPU上实现这类算法一般都需要启动一系列的 GPU内核程序，一个内核程序要产生启动下一个内核程序所需的工作环境。还有一种办法，即通知或与主机程序共同，启动额外的并发内核程序。因为GPU是被设计来执行固定数目的并发线程，所以无论哪种方法实际效果都不算太好。为了解决这个问题，开普勒架构 GPU引人了“动态并行性”(dynamic parallelism)的概念。关于这个概念的更多内容，请参见第12章。

在求解某些问题时，内核程序内部的并发性会不断变化，内部也会出现一些问题。为此，线程之间需要进行通信与协调。在GPU的一个线程块内，线程之间通信与协调可以通过很多方法来实现。例如，假设你有一个8x8的块矩阵，很多块仅需要64个工作线程。然而，很可能其他块却需要使用256个线程。你可以在每个块上同时启动256个线程，这时多数线程处于空闲状态直到需要它们进行工作。由于这些空闲进程占用了一定的资源，会限制整个系统的吞吐率，但它们在空闲时不会消耗GPU的任何执行时间。这样就允许线程使用靠近处理器的更快的共享内存，而不是创建一系列需要同步的操作步骤，而同步这些操作步骤需要使用较慢的全局内存并启动多个内核程序。内存的类型将在第6章介绍。

最后，新的GPU支持更快的原子操作和同步原语。除了可以实现同步外，这些同步原语还可以实现线程间通信，本书的后面部分将给出这方面的例子。

2.7.3 分条/分块

使用CUDA来解决问题，都要求程序员把问题分成若干个小块，即分条/分块。绝大多数并行处理方法也是以不同的形式来使用“条/块化”的概念。甚至像气候模型这样巨大的超级计算问题也必须分为成千上万个块，每个块送到计算机中的一个处理单元上去处理。这种并行处理方法在可扩展方面具有很大的优势。

在很多方面，GPU与集成在单个芯片上的对称多处理器系统非常类似。每个流处理器（SM)就是一个自主的处理器，能够同时运行多个线程块，每个线程块通常有256或者512个线程。若干个SM 集成在一个 GPU上，共享一个公共的全局内存空间。它们同时工作时，一个GPU(GTX680)的峰值性能可达3Tfops。

尽管峰值性能会给你留下深刻的印象，但是达到这个性能却需要一个精心设计的程序，因为这个峰值性能并不包括诸如访存这样的操作，而这些操作却是影响任何一个实际程序性能的关键因素。无论在什么平台上，为了达到高性能，就必须很好地了解硬件的知识并深刻理解两个重要的概念--并发性和局部性。

许多问题中都存在并发性。可能是由于先前串行程序的背景，你也许不能立刻就看出问题中的并发性。而“条/块模型”就很直观地展示了并发性的概念。在二维空间里想象一个问题--数据的一个平面组织，它可以理解为将一个网格覆盖在问题空间上。在三维空间里想象一个问题，就像一个魔方(Rubik'sCube)，可以把它理解为把一组块映射到问题空间中。CUDA提供的是简单二维网格模型。对于很多问题，这样的模型就足够了。如果在一个块内，你的工作是线性分布的，那么你可以很好地将其分解成CUDA块。由于在一个SM内，最多可以分配16个块，而在一个GPU内有16个(有些是32个)SM，所以把问题分成256个甚至更多的块都可以。实际上，我们更倾向于把一个块内的元素总数限制为 128、256或者512，这样有助于在一个典型的数据集内划分出更多数量的块，

当考虑并发性时，还可以考虑是否可以采用指令级并行性(ILP)。通常，人们从理论上认为一个线程只提供一个数据输出。但是，如果GPU上已经充满了线程，同时还有很多数据需要处理，这时我们能够进一步提高吞吐量吗?答案是肯定的，但只能借助于IP。实现IP的基础是指令流可以在处理器内部以流水线的方式执行。因此，与“顺序执行4 个加法操作”(压人一等待一压人一等待一压人一等待一压入一等待)相比,“把4个加法探作压人流水线队列、等待然后同时收到4个结果”(压人一压入一压人一压入一等待)的效率更高。对于绝大多数 GPU，你会发现每个线程采用4个IP级操作是最佳的。第9章中有更详细的研究和例子。如果可能的话，我们更愿意让每个线程只处理N个元素，这样就不会导致工作线程的总数变少了。

2.7.4 分而治之

分而治之模式也是一种把大问题分解成的小问题的模式，其中每个小问题都是可控制的。通过把这些小的、单独的计算汇集在一起，使得一个大的问题得到解决。常见的分而治之的算法使用“递归”(recursion)来实现,“快速排序”(quick sort)就是一个典型的例子。该算法反复递归地把数据一分为二,一部分是位于支点(pivot point)之上的那些点，另一部分是位于支点之下的那些点。最后，当某部分仅包含两个数据时，则对它们做“比较和交换”处理。

绝大多数递归算法可以用迭代模型来表示。由于迭代模型较适合于GPU基本的条块划分模型，所以该模型易于映射到 GPU上。

费米架构GPU也支持递归算法。尽管使用CPU时，你必须了解最大调用深度并将其转换成栈空间使用。所以你可以调用APIcudaDeviceGetLimit()来查询可用的栈空间，也可以调用 APcudaDeviceSetLimit()来设置需要的栈空间。如果没有申请到足够的栈空间，CPU将产生一个软件故障。诸如 Parallel Nsight和CUDA-GDB 这样的调试工具可以检测出像“栈溢出”(stack overflow)这样的错误。

在选择递归算法时，你必须在开发时间与程序性能之间做出一个折中的选择。递归算法较易于理解，与将其转换成一个迭代的方法相比，编码实现递归算法也比较容易。但是所有的递归调用都需要把所有的形参和全部的局部变量压入栈。GPU和CPU实现栈的方法是相同的，都是从全局内存中划出一块存储区间作为栈。尽管CPU和费米架构GPU都用缓存栈，但与使用寄存器来传递数据相比，这还是很慢的。所以，在可能的情况下最好还是使用迭代的方法，这样可以获得更好的执行性能，并可以在更大范围的GPU硬件上运行。