并行计算课程算法实践教学的新工具CUDA编程模型

1、一一一文章编号：（）“并行计算课程算法实践教学的新工具：编程模型王智广，刘伟峰（中国石油大学（北隶）计算机科学与技术系，北京；中国石油化工股份有限公司石油勘探开发研究院信息技术研究所，北京）摘要：本文首先从当今多核微处理器的发展趋势出发，介绍适用于多核微处理器的细粒度并行编程模型，以及其适用于“并行计算”课程教学的一系列优势，接着对当前可用的几种并行编程模型进行分析和比较，最后给出采用编程模型的一个矩阵与矩阵相乘的教学实例。关键词：并行计算；实践教学；中图分类号：文献标识码：引言年，教育部高等学校计算机科学与技术教学指导委员会将“并行计算”课程定位在高等学校计算机专业高年级本科生或研究生以及面

2、向计算学科的非计算机专业的研究生层次上。“并行计算”课程一般主要包括以下四个层面：（）在算法理论层面主要讲授可计算性与计算复杂性以及算法研究的数学基础；（）在体系结构层面主要讲授并行计算机体系结构；（）在算法设计层面主要讲授计算机科学及其他科学计算领域中的非数值和数值并行算法；（）在算法实践层面主要讲授基于并行编程模型的并行算法编程。实际上，对于大多数学习“并行计算”课程的非并行计算研究方向的学生来讲，第（）层面，即算法实践是课程最具价值的组成部分。将并行算法实现成程序并投入大规模科学与工程计算生产应用是课程的最主要学习目的之一。其中对于编程模型的选择又是算法实践教学的重要前提。以往“并行计算

3、”课程在算法实践教学中大多采用作为编程模型，可的粗粒度特性不仅不足以满足“并行计算”课程的实践需要，还很难利用当前多核微处理器的硬件细粒度优势。本文从当今多核微处理器的发展趋势出发，介绍适用于多核微处理器的编程模型，以及其适用于“并行计算”课程教学的一系列优势，并给出对几种主流并行编程模型与的分析和比较，最后提供一个基于的矩阵与矩阵相乘程序作为教学实例。多核微处理器发展趋势过去的年间，提高运行频率是性能提高的主要方式，然而，自年以来，这种趋势发生了变化，不断提高的频率带来了高功耗和高发热量，使得主流频率止步于，并向单芯片多处理器（，），即多核方向发展。年，和正式向主流消费级市场推出了双核心的产

4、品，年推出了核心的，按照各厂商的发展路线图，今后大约每年单上的核心数将翻番。但由于市场变化和研制成本的原因，多核的每个核都基于以往的单核设计，保留了如乱序执行等很多单核时代的复杂执行方式，使得其对于科学计算等问题的计算能力提高非常有限。此时，以游戏加速和图形处理为初衷设计的（，图形处理器）以超出摩尔定律的速度发展，并开始在非图形的高性能计算领域被大量使用。图为近年来同等市场价格和的浮点运算速度对比图。作者简介：王智广（），男，教授，高级会员，主要研究方向为分布式计算和并行计算；刘伟峰（一），男，中国石油大学（北京）计算机科学与技术系届硕士，工程师，会员，主要研究方向为图形处理器架构，高性能计算

5、可视化。万方数据”卜一而磊蕊墨圈隧蕊镶镧啪乏享啪“乱。一抛。罗厂：御！：磊蒿：意。图和的理论峰值由图可见，的浮点运算速度可以达到的倍以上。带来这种数据处理能力差别的主要原因在于最早为并行处理大量三维计算机图形学中的顶点和像素数据而设计，近年来为通用计算又进行了一系列改进。其天生并行的体系结构决定了非常擅长以并行的方式运行高运算强度的应用。以为例，与体系结构相比，体系结构的优势主要有：（）单芯片上的更多处理器（核）与核心包含的个核心相比，目前最高仅达到核，虽然每个核的运算能力高于上的单核，但后者凭借更多核的并行在计算能力上高出很多；（）将更多的晶体管用于计算单元运算能力远高于的重要原因是将更多的

6、晶体管用于计算单元。目前将约的晶体管用于；而晶体管的以上是计算单元；（）超多活动线程能够保持个活动线程的上下文，与此相比，通过线程池管理的线程不过数十个。超多活动线程可以隐藏大量计算单元的访存延迟，在处理数据敏感的应用时要比的方式更加有效；（）高显存带宽与其显示设备内存间的带宽超过与内存的带宽倍以上。配合超多活动线程，使十分适合大规模并行处理高运算强度的应用。正是由于这些原因，在国际高性能计算研究领域，针对以为代表的硬件细粒度并行计算的研究是近年来的一个新的热点。并诞生了大量基于的科学计算改进算法，其领域涵盖各类数值模拟方法，包括计算天体物理、计算流体力学、计算量子化学，甚至计算金融学在内的众

7、多领域已经从计算中获益。万方数据由此可见，相对于多核而言，的高度并行体系结构天然地适合进行并行计算的研究和教学。而在年以前，的并行程序设计还主要是通过或这种图形来完成，入门难度较高。所以在高性能计算的研究者们对于利用进行并行计算的迫切需求下，编程模型诞生了。编程模型（，统一计算设备架构）是年由推出的一套并行编程模型。其推出的最初目的是为解决通用计算的易用性问题。至今已有众多研究者利用的高度并行性特点将科学计算算法迁移至编程模型并在上获得了相对于平均数十倍的性能提升。随着编程模型被越来越多的研究者接受，的研究人员利用源源的解决方案设计了（），使程序也可以运行在多核上，且运行效率要高于多数原生的优

8、化方法。使的应用范围基本覆盖了包括和在内的当今主流多核微处理器。可以说，并行编程模型的出现和迅速发展标志着细粒度并行程序设计已经逐渐为主流程序设计人员所接受。编程模型有和显式数据调用个主要特点。运行方式与以往和的并行计算常用指令和数据流运行方式相比，程序的运行方式被称为（，单指令多线程），其意义是可以让程序设计人员把编程的硬件对象作为若干个标量处理器调用，即没有固定的矢量宽度，并允许每一条线程占据各自路径，在不受可编程性制约的前提下保证每个处理器核心一直处于完全被利用状态。这样在并行程序设计上就可以将精力专注于程序线程的拆分，达到提高并行化效果并且降低程序编写难度的目的。显式数据调用的访存指令

9、与语言相同，但增加了一项重要特性，即对共享内存（）的显式操作。共享内存是芯片内的一块分为个的存储器，主要作用是作为并发线程间的共享数据存放空间，另外也可以显式地将其当成使用，存放并发线程其需要多卜囊豳豳霹里里型塑型！一斓镧镧次存取的数据。当每个线程访问不同的时候，共享内存的存取延迟与寄存器的存取延迟一样低，即数百倍地低于片外显示内存或主存的存取延迟，所以对共享内存的有效显式操作是提高并行程序运行效率的关键。本文第节会给出一个使用共享内存的教学实例。总体来讲，编程模型中基于多核的细粒度并行方式和对存储器的显式操作是十分理想的课程教学工具，有助于学生设计既贴近硬件体系结构又独立于运行平台的并行程序

10、。虽然学生在算法实践初期会觉得细粒度的并行程序设计较难接受，但就我们的教学经验来看，具有计算机体系结构和编程语言基础的学生大约在周内可以对的并行编程模型基本熟悉，况且在算法实践中获得数十倍性能提升带来的成就感也会促使学生逐渐克服学习的困难。几种弗行编程模型的分析和比较目前国内外一般教材和课程教学选用的并行编程模型主要有种：消息传递接口、线程接口和基于指令的。这三种编程模型各有比较鲜明的特点。本节将它们和本文选用的编程模型一并进行分析和比较。（，可移植操作系统接口）线程接口也称，年被通过成为被绝大多数厂商支持的线程。它提供了处理诸如死锁和竞态条件这类问题的工具，但没有限定线程的具体工作方式，对于

11、如何编制线程并行的程序留有很大的余地。基于此，被认为过于底层和编程难度较高，所以目前多数“并行计算”课程不将作为主要的算法实践工具。作为共享存储标准而在年问世的是为在多处理机上编写可移植的多线程应用程序而设计的一个应用编程接口。编程模型包括一套平台无关的编译指导（）、编译命令（）和一个用来支持它们的函数库。显示地指导编译器如何利用应用程序的并行性，而开发人员不需要关心实现细节，这使得的学习入门难度相对较低，但同时也很难完成并万方数据行算法的课程教学要求，所以一般也不将作为主要的算法实践工具。年由政府、学术界、产业界共同制定的（，消息传递接口）是根据并行应用程序对于消息传递的需求而定义的一组标准

12、接口说明和不同厂商提供的相应方法实现。吸收了等众多消息传递模型的优点，在集群型高性能计算机的流行化趋势下成为了目前最流行的并行编程模型。虽说的学习曲线较长，但大多数“并行计算”教科书还是主要使用作为并行算法教学实践的工具。种并行编程模型比较表是种并行编程模型主要特性比较表。表种并行编程模型主要特性比较表衅特征低级原语共享存储消息传递单指令多线程并行粒度细粒度细粒度粗粒度细粒度存储模式共享存储共享存储分布存储共享存储数据调用方式显式隐式显式显式学习难度难容易较难一般可扩展性较好较差好较好矩阵与矩阵相乘并行算法教学实例矩阵与矩阵相乘并行算法是最常用也最具代表性的并行算法之一，十分适合作为学生对并行

13、算法实践的入门教学。本节描述一个基于编程模型和块矩阵算法的矩阵与矩阵相乘并行算法教学实例。串行算法对于两个胛×稠密矩阵与相乘得到乘积矩阵×的算法，易写出其串行实现的伪代码如下：（，）：一：一，：一，：，×，；工¨努弋而蕊蕊暖圈酲峨块算法针对粗粒度的并行机制，一般采用基于块矩阵运算矩：；：？；？；斓碉镧阵与矩阵相乘算法，即将整个矩阵分成矩阵块大小为（哟）（的块矩阵，把原矩阵的代数运算转换成对这些块矩阵中元素的代数运算，进而通过消息传递实现粗粒度的并行。块算法的伪代码如下：一？：鼠，×，；（，）；，。；：一，：一其；语句表示在开始下一步操作之前：对

14、线程块内的线程进行同步。和是二维线程块中线程的编号，通过它们也容易理解编程模型的单指令多线程的工作方式。同时可以算出，为计算每个块，若不使用共享内存，。，；块算法的并行实现的细粒度并行机制要求从每个线程的角度考虑整个矩阵相乘，同时的三级线程管理结构也要求对线程进行适当的块划分，本实例中对线程块的划分可以与块矩阵运算思想直接对应起来。首先，根据需要划分两个胛×聍稠密矩阵彳与为口需要访问存放块矩阵，和取，的全局内存（响）次，反之仅需访存（，吻）次。通过以这种方式分块计算，可以有效利用快速的共享内存，进而节省许多全局内存带宽。由于篇幅所限，本实例仅包括块矩阵相乘的代码主体部分，对代码的调用

15、方式等其他内容请参考编程指南。块大小为（毗）×（确）的块矩阵，根据的体系结构，结束语本文在介绍多核微处理器发展趋势和编程模型的基础上，对和以往其他种并行编程模型进行了比较，最后给出了一个矩阵与矩阵相乘的教学实例对编程模型进行进一步详述。能够看出，作为近两年新出现的并行编程模型可以很好地利用新一代及芯片上数量众多的核进行细粒度并行计算，再结合相对易于学习掌握的特点，可以得出结论，编程模型可以与粗粒度的互为补充，为学生带来更丰富的算法实践经验，并且完全可以作为“并行计算”课程算法实践教学的工具使用。圈取以便每线程块的线程数是（上个线程组成的线程簇）大小的倍数，且低于每线程块的最大线程数。然后，计算的每个块，其执行过程是：（）使用每线程加载块矩阵抽和圾，的一个元素，将爿城和瞰，从全局内存加载到共享内存；（）每个线程计算结果块矩阵的一个元素，其中