基于OpenMP+MPI+CUDA并行混合编程的N体问题实现

N-Body问题的并行混合编程实现Abstract:MultilevelSMPclusterprogrammingmodelistheeffectivewaytoincreasethecomputingperformanceof.SMPclusterfromthehardwarecanbedividedintonodes,andnodeswithinasingleprocessorinstructionlevelparallelismonthreelayerarchitecture.BasedontheresearchofparallelprogrammingmodelbasedonSMPclusterhardwarearchitectureandSMPclusterhierarchy,realizationN-bodyalgorithminthedesignofhybridprogrammingmodelbasedonOpenMP+MPI+CUDA.Finally,theprogramtestindawningW580Icluster,andcombinedwiththemethodofperformanceevaluationofmulti-coreSMPclusterhierarchyprogramming,thealgorithmwiththetraditionalN.Parallelalgorithmisperformedtocomparetheexecutiontimeandspeedup,andtheconclusionisdrawn.Keywords:parallelprogramming；OpenMP+MPI+CUDA；n-bodyproblem；clustersystem摘要:SMP集群上的多级层次化编程模型是提升计算性能的有效方式。SMP集群从硬件上可以分为节点间、节点内和单个处理器上的指令级并行三层架构。本文在对SMP集群硬件体系结构和SMP集群多层次并行化编程模型的研究基础上，实现N-body问题算法的基于OpenMP+MPI+CUDA的混合编程模型的设计。最后在曙光W580I机群上进行程序测试，并结合多核SMP集群层次化编程的性能评测方法，将该算法与传统的N体并行算法进行了执行时间与加速比的比较，得出总结性论述。关键词：并行编程；OpenMP+MPI+CUDA混合编程模型；N体问题；SMP集群1.引言N-Body模拟问题在天体物理、分子动力学等很多领域都有重要应用。可以描述为一个物理系统中的N个粒子，每对粒子间都存在着相互作用力（万有引力、库仑力等）。它们从一个初始的状态开始，每隔一定的时间步长，由于粒子间的相互作用，粒子的状态会有一个增量，需要对粒子的加速度、速度和位置信息进行更新。N-body的串行算法需要计算N(N-1)次受力，故此算法的时间复杂度为O(n^2)。然而，一般模拟的粒子规模都很大，一个体系中可以包含数百万乃至上千万的粒子，直接计算的话O(N^2)的量级对于任何高性能的单个处理器都是一个难以突破的瓶颈。N体问题从并行化的数据相关性、控制相关性和并行化粒度等方面都是典型的可并行化处理的问题。对于一些大规模的应用问题，单一处理器计算机远不能满足需求：（1）一些大型复杂科学计算问题对计算精度要求比较高，同时也意味着大的计算量；（2）大量的科学技术和工程问题，对问题的求解有强烈的时效性要求，超过一定的时间结果就毫无意义。因此，出现了并行体系结构计算机和并行编程技术。高性能并行计算（HPC）是求解大规模计算问题的有力手段之一。HPC把计算问题分解成小的计算任务，同时在多个计算单元上执行各个计算任务。本文基于当前流行的SMP集群硬件体系结构和SMP集群多层次并行化编程模型，采用OpenMP+MPI+CUDA的混合编程模型进行了N-body问题的算法实现，并将该算法与传统的N体并行算法进行了执行时间与加速比的比较。2.SMP多核集群体系结构高性能并行计算的研究包括并行计算机体系结构、并行程序设计、并行算法理论模型和并行算法实践应用四个方面。2.1并行计算机系统结构并行计算机体系结构主要有对称多处理器共享存储并行机（SMP）、分布式共享存储并行机（DSM）、大规模并行机（MPP）和SMP多核集群系统等。其中，SMP体系结构采用商用微处理器，通常有片上和外置Cache，具有低通信延迟的特点，可采用多线程机制（如Pthreads）和编译制导（如OpenMP）并行编程，其实现较为简单，但缺点是可扩展性较差；MPP则是指由数百或者数千台处理器所构成的规模较大的计算机系统，基于分布存储的多计算机系统，具有良好的可扩展性，主要采用消息传递机制，实现标准有MPI，PVM等，但其处理器之间的通信开销大，编程比较困难。2.2多核SMP集群系统SMP多核机群系统（SymmetricMultiprocessorCluster）由固定数量的独立节点构成的多级体系结构，这些节点有拥有多个CPU的SMP、普通计算机以及服务器，它们之间能够协同工作，并且能作为一个独立的计算机资源运用。SMP计算机系统因其高性价比而得到广泛应用。全球超级计算机2014年TOP500是以Linkpack浮点计算能力来排位的，现在全球最快的超级计算机是我国的天河2号，已经达到了33．86petanops(千万亿次)的浮点峰值计算能力。目前超级计算机的体系结构主要有两类，一类是机群架构(C1usters)，另外一类是大规模并行处理机架构(MPP)。目前，在前十名超级计算机中，大部分是SMP机群系统。其物理结构如下图2-1所示。高速互联网络（如Myrinet、以太网或高性能开关）总线或交叉开关共享存储I/O设备网络接口硬件CPU核CPU核二级缓存系统软件消息传递系统软件CPU核CPU核二级缓存系统软件消息传递系统软件.........PCn-1PC0总线或交叉开关共享存储I/O设备网络接口硬件CPU核CPU核二级缓存系统软件消息传递系统软件CPU核CPU核二级缓存系统软件消息传递系统软件.........PCn-1PC0...多核SMP节点0多核SMP节点n-1图2-1SMP集群体系结构SMP集群架构一方面，节点内一般采用两个或以上的偶数个多核CPU，来保证单个节点的处理性能；另一方面，节点之间使用InfiniBand高速计算网络进行数据通信，延迟仅100ns，保证了节点间通信控制的实时性。很多高性能计算平台(HPC)采用具有层次结构的SMP集群系统。SMP集群节点间采用消息传递的分布式存储结构，集群节点内部采用共享存储模型。如图1所示。因此，SMP集群不仅兼顾了单个节点的强大的并行能力，而且具有分布式并行系统的高扩展性，强连通。3SMP多层次并行程序设计模型并行算法设计模型是高性能计算中软硬件之间的桥梁。并行编程模型是一个程序抽象的集合，用于并行程序设计的编程模型包括：分布式存储消息传递编程模型MPI、共享内存模型OpenMP、多核微处理器细粒度编程模型CUDA和基于MPI、OpenMP+CUDA的多层次混合编程模型等。3.1SMP多核体系结构SMP集群（cluster）层次并行体系结构计算机已经成为国内外主流的并行体系结构。3.1分布式存储编程模型MPI消息传递模型MPI（MessagePassingInterface）是目前分布式存储系统上的主流编程模型。它是基于进程并行，需要用到明显的发送和接收消息。消息传递模型在C、Fortran和C++等编程语言都有相应的函数库。开发人员在编写并行程序时，只要安装MPI的函数库，就可以方便的调用MPI的函数。而在分布式存储结构中，处理器之间常常要采用消息传递来完成消息交换、同步等等功能。MPI模型适用于大规模并行处理机(MPP)和机群。MPI具有可移植性好、功能强大、效率高等优点，特别适用于粗粒度的并行，几乎被所有多线程操作系统（包括UNIX，WindowsNT等）支持，是目前超大规模并行计算最可信赖的平台。。但它也有许多不足之处：消息传递和全局操作的开销非常大；细粒度任务会引发大量的通信；动态负载平衡困难；将串行程序转换为并行程序需要对代码作大量改动；程序员完成数据和任务的划分，编程和调试的难度大。3.2共享主存模型OpenMP基于编译制导的OpenMP是目前广泛使用的共享存储编程模型。它是多线程编程模型之一，在共享存储体系结构上应用的一种应用程序编程接口(API)[i]。OpenMP并行编程技术因为它的编程简单、可移植性好，多使用在UNIX以及WindowsNT等等各种平台，OpenMP的应用广泛，因此被当做共享变量编程模型的一个代表。OpenMP是对一些基本语言进行的扩展，它并不是一种新的语言，比如常用的Fortan、C和C++等等。OpenMP编程环境包括编译指导语句、运行库函数和环境变量。OpenMP的编程相对简单，充分利用了共享存储体系结构的特点，避免了消息传递的开销。虽然它也支持粗粒度的并行，但主要还是针对细粒度的循环级并行。OpenMP的另一个特点在于将串行程序转换为并行程序时无须对代码作大的改动。其不足之处有只能在共享存储结构的机器上运行；数据的放置策略不当可能会引发其他问题；并行化的循环粒度过小会增加系统开销等。OpenMP的并行机制主要是fork-join（如图3-1所示），当程序开始串行执行时是有一个主线程，并行制导语句是在并行区域中建立了很多线程。在这个区域内，多个线程执行同样的代码块，也可以用工作共享结构体来并行执行各种任务。图3-1fork-join并行机制(1)Fork：主线程在遇到parallel指令后，会自动创建一组并行的线程，这样并行区域中的代码被复制，各个线程都会对这段代码进行并行执行。(2)Join：并行域运行结束以后会产生一个路障，除主线程以外的其他线程或者被中断或者被同步，这时只有主线程能通过路障，最后程序中只有主线程在执行。3.3多核微处理器细粒度编程模型CUDACUDA(ComputeUnifiedDeviceArchitecture，统一计算设备架构)是2007年由nVidia推出的一套并行编程模型。以游戏加速和图像处理为初衷设计的GPU（graphicsprocessingunit，图形处理器）以超出摩尔定律的速度发展，在利用GPU进行并行计算的迫切需求下，CUDA编程模型产生。至今已有众多研究者利用GPU的高度并行性特点将科学计算算法迁移至CUDA编程模型并在GPU上获得了相对于CPU平均数十倍的性能提升。CUDA是首款并行运算语言，CPU专用于解决可表示为数据并行计算的问题，即在许多数据元素上并行执行的程序，具有极高的计算密度（数学运算与存储器运算的比率）。由于所有数据元素都执行相同的程序，因此对精密流控制的要求不高；由于在许多数据元素上运行，且具有较高的计算密度，因而可通过计算隐藏存储器访问延迟，而不必使用较大的数据缓存。CUDA编程模型主要有SIMT和显示数据调用2个主要特点。CUDA的运行方式为SIMT（SingleInstructionMultipleThread，单指令多线程），即编程设计人员把编程的SIMD硬件多项作为若干个标量处理器调用，保证每个处理器核心一直处于被利用的状态，达到提升并行化效果的目的。CUDA访存指令比C语言增加了一项对共享内存（SharedMemory）的显示操作指令，以此提高CUDA并行程序运行效率。3.4多核机群SMP系统上MPI+OpenMP+CUDA三级混合编程模型程序提交到SMP集群系统后，由于各物理节点间的分布式存储结构，节点间通过MPI消息传递模式，由程序员在不存在相关性的情况下，将任务划分为子任务，每个子任务通过MPI编程模型的消息广播到SMP集群的每个节点机上；由于节点机采用共享存储体系结构，每个节点机在收到广播的子任务后，内部通过OpenMP并行模型，利用OpenMP编译制导语句按照某种规约将子程序分配到几点的多核处理器的每个CPU上，此过程对程序员是透明的，再由每个处理器建立若