基于MPI+CUDA异步模型的并行矩阵乘法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于MPI+CUDA异步模型的并行矩阵乘法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

フ 要:矩阵乘法在科学计算领域中起着重要的作用，不同结构模型能够改善并行矩阵乘的性能。现有的MPI+CUDA同步模型中，主机端需要进入等待状态，直到设备端完成任务后才能继续工作,这显然浪费时间。针对上述问题，提出一种基于mpi+cuda异步模型的并行矩阵乘法。该模型避免了主机端进入等待状态，并采用CUDA流技术解决数据量超过GPU内存问题。通过分析异步模型的加速比和效率，实验结果表明，此方法显著提高了并行效率和大型矩阵乘法的运算速度，充分发挥了节点间分布式存储和节点内共享内存的优势，是一种有效可行的并行策略。

ス丶词:矩阵乘法；并行计算；混合编程；消息传递接口；统一计算设备架构

ブ型挤掷嗪: TP311;TP316.4 文献标志码:A

Abstract: Matrix multiplication plays an important role in scientific computing. Different structural models can improve the performance of parallel matrix multiplication. In the existing MPI+CUDA synchronization model, the hostside need enter the waiting state and cannot continue to work until the device completes the task, which obviously wastes time. Concerning this question, a parallel matrix multiplication based on MPI+CUDA asynchronous model was proposed. This model prevented hostsides entering into the waiting state, and used CUDAstream technology to solve the problem of data bulk over GPU memory. By analyzing the speedup ratio and efficiency of the asynchronous model, the experimental results show that MPI+CUDA parallel programming obviously promotes parallel efficiency and largescale matrix multiplication’s speed，which exerts the advantages of the distributional memory between the nodes and the share memory in the node. It is an effective and feasible parallel strategy.

Key words: matrix multiplication; parallel computing; hybrid programming; Message Passing Interface (MPI); Computer Unified Device Architecture (CUDA)

0 引言

矩阵乘法在科学计算领域起着重要的作用。由于矩阵乘法计算量大，有效矩阵乘并行算法在实际应用中就显得非常重要。在国内，刘杰等人于1997年提出了一种B迁移矩阵乘并行算法［1］；吴建平等人于1999年将cannon算法由正方形网格处理机阵列推广到长方形网格处理机阵列［2］。在国外，文献［3］提出的基于OTISMesh网络结构的并行矩阵乘算法；文献［4］提出六种不同的并行矩阵乘法在非均质多核处理器计算集群的实验研究。这些成果表明，根据不同的结构模型开发并行矩阵乘法能够有效地改善并行算法的性能。

随着计算机图形处理器(Graphic Processing Unit，GPU)的计算能力越来越强大［5-6］, 它已经具备了实现大规模快速计算的编程能力，2007年NVIDIA公司提出的计算统一设备架构(Computer Unified Device Architecture，CUDA)技术就是这方面的杰出代表［7］。目前普遍使用的并行程序设计模型是消息传递的消息传递接口 (Message Passing Interface, MPI)模型，这种消息传递模型一般面向分布式内存的，不能充分发挥集群节点内共享内存的优势。本文将消息传递模型MPI和共享内存模型CUDA结合在一起，开发一套MPI+CUDA异步模型，该异步模型主机端不需等待设备端完成任务就可以进行数据通信，使CPU与GPU执行任务期间互不影响，更加充分地发挥了消息传递和共享内存两种编程模型的优势。

1 MPI+CUDA并行模型

MPI［8］是消息传递接口的简称, 是一种消息传递编程模型。由于MPI细粒度并行会引发大量的通信，从而产生昂贵的通信代价，造成较大开销。通过开发混合并行程序，MPI只需要建立粗粒度并行，实现节点间通信即可，有效地克服了MPI通信代价大的缺点。

CUDA是基于GPU进行通用计算的开发平台，适合于大规模的并行数据计算。在CUDA编程模型中，GPU被视为一个协处理器，能够执行大量线程并行。在其架构下面，一个程序分为两部分：host端和device端［9］。host端是指在CPU上执行的部分，而device端是在显示芯片上执行的部分。当处理数据并行计算时，CUDA首先将程序编译成GPU能够执行的程序，而后传送到GPU。运行在GPU上的CUDA并行计算函数叫作“kernel(内核函数)”。在实际运行中，CUDA会产生大量在GPU上执行的线程，线程间只能通过共享存储器和同步机制进行通信，能充分发挥节点内共享内存的优势，非常适合MPI+CUDA模型中细粒度并行部分。

混合编程模型的优势在于能取单一模型所具备的长处，克服单一模型所存在的缺点与不足。在编写并行程序时，使用MPI将任务分解成若干子任务，每个节点完成一个子任务，由于每个节点只能读写本地内存中的数据，所以各子任务之间通过消息传递的方式来进行通信完成对远程数据的访问。每个节点在GPU上采用多线程共享存储机制来实现数据共享进行细粒度并行，充分发挥单个节点计算能力，从而提高计算性能和加速比。混合粒度的并行化可以兼顾性能和可扩展性，MPI解决多处理器间的粗粒度的并行通信，而GPU采用由硬件管理的轻量级线程并行机制，可以很好地解决处理器内部的通信，CUDA提供大量线程数目可以快速地进行大规模矩阵乘计算。在MPI+CUDA并行模型中，MPI并行位于顶层，CUDA位于底层。这种模型很好地映射了多处理器计算机组成的集群体系结构［10］。

文献［11］提出了MPI+CUDA并行编程同步的计算模型，如图l所示，处理器CPU将分配的矩阵块数据传给GPU，CUDA就会产生许多在GPU上执行的线程来实现块矩阵乘加运算，然后将计算结果从GPU调回CPU上，而后进行进程间的数据通信。

在MPI+CUDA异步模型中，CUDA利用GPU多线程计算矩阵乘―加运算的同时，处理器则利用MPI消息传递进行数据的交换，将通信开销隐藏在计算开销中，大大提高了并行效率，图3显示了MPI+CUDA模型同步与异步执行方式比较。

显然，不使用异步执行时的程序运行时间为(初始化数据时间+计算时间+通信时间)；而使用异步后，时间将为(初始化数据时间+计算时间)。此时，CPU和GPU间的数据传输时间被有效地隐藏了，程序的性能得到了改善。

3 数值实验

为了测试这种编程模型的性能，将其对同步模型和MPI模型、CUDA模型进行模拟数值实验，实验环境是：4台带有支持CUDA的 GeForce GTX 470显卡的多核处理器。采用大规模矩阵相乘作为测试程序。机器配置如下：Intel core 2 CPU E8400 @3.00@GHz，1.00@GB内存，OpenSuse11.2操作系统，MPICH2函数库，CUDA，通过千兆交换机连接成集群系统。

通过编写MPI程序控制这些处理器间的通信实现MPI模型和MPI+CUDA模型的逻辑连接。首先，г诠潭ù理器数目的条件下(P=4)选取五组固定矩阵规模，Ф员疚乃惴ê屯步算法以及MPI算法、CUDA算法在执行时间方面进行了实验测试，运行时间如表1所示，根据时间得到不同模型的加速比如表2所示，再由加速比计算出的效率如表3所示。而后还在单台PC上对传统O(n3)У拇行矩阵乘算法在执行时间方面进行了实验测试，得出实验数据如图4所示。

从图4上看，MPI+CUDA模型的执行时间远远小于MPI的并行执行时间，表现出非常高的执行效率，相对于同步模型而言，MPI+CUDA异步模型执行时间更少，执行效率的提高更加明显。

由表1和表2的实验数据可知，随着矩阵阶数的增大，本文算法加速比呈线性增长，效率越来越高，充分证明该模型具有很高的可行性。

4 结语

实现MPI+CUDA异步模型，通过对矩阵乘法的测试，实验证明，MPI+CUDA异步模型具有更高的执行效率，更加充分发挥节点间分布式存储和节点内共享存储的优势。在多核处理器环境下该模型可以有效提高并行计算性能，是一种高效可行的并行编程策略。

げ慰嘉南:

[1] 刘杰,胡庆丰,迟利华.并行矩阵乘的B迁移算法［J］.计算机工程与科学,1997,19(3):50-54.

[2] 吴建平，迟学斌.分布式系统上并行矩阵乘法［J］.计算数学，1999，21(1)：99-108.

[3] WANG C F, SAHNI S. Matrix multiplication on the OTISmesh optoelectronic computer［J］. IEEE Transactions on Computers，2001，50(7)：635-645.

[4] ALONSO P, REDDY R, LASTOVETSKY A. Experimental study of six different implementations of parallel matrix multiplication on heterogeneous computational clusters of multicore processors［C］// 18th Euromicro Conference on Parallel, Distributed and Networkbased Processing. Washington, DC:IEEE Computer Society, 2010:263-270.

[5] 刘伟峰，杨权一，曹邦功，等.基于GPU的高度并行Marching Cubes改进算法［J］.微电子学与计算机，2008，25(9)：151-157.

[6] 钱悦.图形处理器CUDA编程模型的应用研究［J］.计算机与数字工程，2008，36(12)：177-180.

[7] 董荦，葛万成，陈康力CUDA并行计算的应用研究［J］ .信息技术，2010(4)：11-13.

[8] GROPP W,LUSK E,DOSS N, et al. A highperformance, portable implementation of the MPI messagepassing interface standard［J］.Parallel Computing,1996,22(6):789-828.

[9] NVIDIA Corporation.CUDA Programming Guide 2.3［M］.[s.l.]:NVDIA Coporation,2009:11-13.

[10] 赵永华，迟学斌.基于SMP集群的MPI+OpenMP混合编程模型及有效实现［J］.微电子学与计算机，2005，22(10)：7-11.

[11] 许彦芹，陈庆奎.基于SMP集群的MPI+CUDA模型的研究与实现［J］. 计算机工程与设计,2010,31(15)：3408-3412.

[12] 夏丽华，张丽晓. PC集群环境下大规模矩阵乘法算法的研究［J］.计算机工程与设计，2007,28(19)：4603-4605,4615.