网站备案变更域名,网页翻译插件哪个好用,WordPress目录和连接关系,永久免费asp空间申请2.1 简介
本章旨在对并行程序设计的基本概念及其与GPU技术的联系做一个宽泛的介绍。本章主要面向具有串行程序设计经验#xff0c;但对并行处理概念缺乏了解的读者。我们将用GPU的基本知识来讲解并行程序设计的基本概念。 2.2 传统的串行代码
绝大多数程序员是在串行程序占据…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)如果程序设计不当死锁将不可避免地发生。
当然在极偶然的情况下程序可以共享资源而不发生死锁。无论哪种加锁系统每一个线程都必须正确地使用资源。也就是说它们必须先申请令牌如果没成功则等待。获得令牌后才执行相应的操作。这就需要程序员定义好共享的资源并制定恰当的机制来协调多线程对该资源的更新操作。然而在任何一个团队里都有若干个程序员即便有一个程序员不遵守规则或者并不知道它是一个共享资源你的程序多数情况下不会正常工作。我曾经为一个大公司开发的项目里就出现过这个现象。所有的线程都申请一个锁如果没成功则等待。获得令牌后就更新共享资源。一切都运行正常所有的代码都通过了质量保证检查(QualityAssuranceQA)和所有的测试。然而投入运行后现场的用户偶尔会报告说某个参数被重置为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 MultiprocessorsSM)中的一个上执行一个块必须从开始执行到结束。网格中的块可以被分配到任意一个有空闲槽的SM上。起初可以采用“轮询调度”(round-robin)策略以确保分配到每个SM上的块数基本相同。对绝大多数内核程序而言分块的数量应该是GPU中物理SM数量的八倍或者更多倍。
以一个军队比喻假设有一支由士兵(线程)组成的部队(网格)。部队被分成若干个连队(块)每个连队由一位连长来指挥。按照32名士兵一个班(一个线程束)连队又进一步分成若干个班每个班由一位班长来指挥(参见图2-1)。 图2-1 基于GPU的线程视图
要执行某个操作总司令(内核程序/主机程序)必须提供操作名称及相应的数据。每个士兵(线程)只处理分配给他的问题中的一小块。在连长(负责一个块)或班长(负责一束)的控制下束与束之间的线程或者一束内部的线程之间要经常地交换数据。但是连队(块)之间的协同就得由总司令(内核函数/主机程序)来控制了。
因此当思考CUDA程序如何实现并发处理时你应该用这种非常层次化的结构来协调几千个线程的工作。尽管一开始听上去很复杂但是对绝大多数“易并行”程序而言仅仅需要针对一个线程思考它计算输出数据的那一点。在一个典型的 GPU 上可以运行 24K个“活动”线程。在费米架构 GPU上你总共可以定义65535x65535x1536个线程其中 24K个线程随时都是活动的。这表明一个节点就足够满足单点中绝大多数问题的求解要求了。 局部性
在过去的十几年间计算性能的提高已经从受限于处理器的运算吞吐率的阶段发展到迁移数据成为首要限制因素的阶段。从设计处理器过程中的成本来讲计算单元(Algorithmic Logic UnitALU)是很便宜的。它们能够以很高的速度运行而消耗很小的电能并占用很少的物理硅片空间。然而,ALU的工作却离不开操作数。将操作数送入计算单元然后从计算单元中取出结果耗费了大量的电能和时间。
在现代计算机设计中这个问题是通过使用多级缓存来解决的。缓存的工作基础是空间局部性(地址空间相对簇集)和时间局部性(访问时间的集)。因此之前被访问过的数据很可能还要被再次访问(时间局部性);刚刚被访问过的数据附近的数据很可能马上就会被访问(空间局部性)。
当任务被多次重复执行时缓存的作用会充分地发挥。假设一个工人带着一个装有4件工具的工具箱(缓存)当分配给他的大量工作都是相同的时候这4件工具将被反复使用缓存命中)。
反之大量的工作都需要不同的工具情况就不一样了。例如工人来上班时并不知道今天会分配给他什么工作。简单来说今天的工作需要一件不同的工具。由于它不在工具箱(一级缓存)中那么他就到工具柜(二级缓存)里找。
偶尔工人可能需要一个工具箱和工具柜里都没有的、特殊的工具或零件这时他就得停下手中的工作跑到附近的硬件仓库(全局内存)里取回他想要的东西。由于公路上可能发生拥堵或者五金商店门前排起了长队(其他进程争相访问主存)因此无论是工人还是客户都不知道为了拿到工具需要花费多少时间(延迟)。
显然工人的时间效率很低。因此每项工作都需要一个新的、不同的工具或零件工人就只得去工具柜或者五金商店去取。而这个取的过程工人并不是忙于手里的工作。
与到硬件仓库里去取工具类似到硬盘或者固态硬盘(Solid-StateDriveSSD)里取数据也是很糟糕的。尽管固态硬盘比硬盘要快得多好比一个普通的送货员需要几天才能把硬盘里的数据送到而送货员一个晚上就能把固态硬盘里的数据送到但是与访问全局内存相比它还是很慢的。
某些现代处理器已经支持多线程。如某些英特尔处理器中每个处理器核支持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-PcerP2P)机制是在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核心的写操作这是很糟糕的思路。
如果算法允许我们还可以探讨另一种类型的数据并行处理--单指令多数据(SingleInstructionMultiple DataSIMD)模型。这需要特殊的 SIMD指令例如许多基于 x86 型CPU提供的MMX、SSE、AVX等。这样线程0就可以取出多个相邻的数组元素并用一条 SIMD 指令来进行处理。
同样的问题如果我们用GPU来处理每个数组则需要进行不同的变换且每一个变换将映射以被看成一个单独的GPU内核程序。与CPU核不同每个SM可以处理多个数据块每个数据块的处理被分成多线程来执行。因此为了提高GPU的使用效率我们需要对问题进行进一步的分解。通常我们将块和线程做一个组合使得一个线程处理一个数组元素。使用CPU让每个线程处理多个数据会有很多好处。相比之下由于GPU仅支持“加载”(load)/“存储”(store)/“移动”(move)三条显式的 SIMD 原语那么它的应用受到限制。但这反过来促进了GPU“指令级并行处理”(Instruction-Level ParallelismILP)功能的增强。在本书的后面我们将看到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个线程块)。因此我们需要8x432个线程块才能填满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 StandardAES)”和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。
尽管峰值性能会给你留下深刻的印象但是达到这个性能却需要一个精心设计的程序因为这个峰值性能并不包括诸如访存这样的操作而这些操作却是影响任何一个实际程序性能的关键因素。无论在什么平台上为了达到高性能就必须很好地了解硬件的知识并深刻理解两个重要的概念--并发性和局部性。
许多问题中都存在并发性。可能是由于先前串行程序的背景你也许不能立刻就看出问题中的并发性。而“条/块模型”就很直观地展示了并发性的概念。在二维空间里想象一个问题--数据的一个平面组织它可以理解为将一个网格覆盖在问题空间上。在三维空间里想象一个问题就像一个魔方(RubiksCube)可以把它理解为把一组块映射到问题空间中。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硬件上运行。 2.8 本章小结
至此我们已经对并行处理的概念及其如何应用到GPU工业领域中有了一个全面的了解。本书的写作目的并不是全面深人地论述并行处理因为这方面的书籍已经很多了。我们只是希望读者能够感受到并行程序设计的理念不再按照串行程序设计的思路来考虑程序设计问题。
在后续的章节中我们将通过分析实际例子详细介绍上述基本概念。我们还将分析并行前缀求和算法。这个算法允许对一个共享的数组同时进行多个写操作而不会发生“一个写操作写到另外一个写操作的数据上”这样的错误。这类问题在串行程序设计中不会出现无须考虑。
随着并行处理带来的复杂度的提高需要程序员把并发性和局部性当作关键问题事先考虑。在设计面向GPU的任何软件时都应该时刻把这两个概念牢记于心。
