多核处理器并行计算模型研究
开篇：润墨网以专业的文秘视角，为您筛选了一篇多核处理器并行计算模型研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：针对并行计算机体系结构中没有通用的计算模型这一问题，分析了一些现有的典型计算模型，在同步性、通信方式、参数方面进行比较，以LogGP模型为基础提出一种改进的mzLogGP模型。利用MPI并行算法对满足节点计算资源非独占、网络存在拥塞条件下的并行程序进行分析与测试，通过增加memory层次化层数和网络拥塞指数这两个参数，计算其计算开销和通信开销，将实测时间与预测时间进行比较，可知随节点数的增加系统误差不断减小，说明该新模型能改善并行应用在多核处理器集群平台上运行的性能，具有较好的可扩展性．
关键词：
中图分类号： TP301 文献标识码： A 文章编号：2095－2163（2011）03－0009－05
Research of Parallel Computing Model based on Multi－core Processor
LI Jingmei， ZHANG Qi， WANG Junfeng
Abstract, As there is not a universal model in parallel computer architecture， the paper analyzes some existing typical models ， comparing them in synchronization， communication， parameters, then proposes a new model: mzLogGP based on LogGP . After that, the paper analyzes and tests the parallel process using the MPI parallel algorithm in the environment of non-exclusive nodes on the computing resources and existing network congestion， and calculates the computational overhead and communication overhead by increasing two parameters: network congestion and layers of memory hierarchy. In the end, by comparing the measured time with the predicted time, the paper shows that with the increase in the number of nodes, the system error decreases. The results demonstrate that the new model can improve running performance of parallel application in the platform of multi-core processor cluster, and has better scalability.
Key words,
0 引言
在单核处理器中，通过提升CPU频率来提高CPU性能的方法，已经促使CPU频率达到了极限，功耗问题达到瓶颈。因此，目前处理器的发展已由纯粹的频率提升逐渐转向了多核和并行应用的研究方向上。截止2007年11月排名世界Top500的超级计算机中，约87．6％的处理器采用多核芯片，并且约81．2％的超级计算机采用了集群[1]结构―以MPI为主导的并行应用的主流计算平台。并行计算的应用需要一个统一的计算模型来与硬件所匹配。因此，如何提高并行计算在多核处理器上的应用，更好地发挥处理器的性能优势成为当前面临的主要问题。本文通过分析与研究各种典型的并行计算模型的优缺点以及对一些经典常用模型的扩展分析，提出一种改进的基于多核处理器机群平台的横向memory层次化的LogGP[2]并行计算模型，并采用典型并行算法对其进行性能测试。
1 典型并行计算模型
并行计算模型[3]是并行算法设计的基础，是从不同的并行计算机体系结构模型中抽象出来的。针对这种新的并行体系结构，解决并行应用面临的问题，需要与之适应的并行计算模型。然而，不像串行计算机那样，全世界基本上都在使用冯•诺伊曼的计算模型；并行计算机没有统一的计算模型。
理想的并行计算模型应该具有以下特征：独立的体系结构；提供软件开发方法；使用简单；性能有保障；可计算成本。根据上述特征，现有计算模型按照其通讯方式可分为共享存储类模型、消息传递模型和层次模型．
1．1 共享存储类模型
早先的并行计算模型为共享存储类模型，分为PRAM模型、QSM模型等。
（1）PRAM模型
PRAM（Parallel Random Access Machine）模型也称之为共享存储的SIMD模型，是早期最有影响力的理论模型之一，作为一种抽象的并行计算模型，被广泛地用来评估并行算法的理论性能。PRAM模型由若干具有本地存储器的处理器和一个具有无限容量的共享存储器组成，处理器由公共的时钟进行控制，以同步方式运行。
（2）QSM模型
QSM（Queue Shared Memory）[4]模型是一个多指令、多数据流(MIMD)机器的共享存储模型，由若干个处理机组成，适用于同步算法，每个处理机都执行一个同步操作队列，每个同步操作包含：读、计算、写三个步骤。
1．2 消息传递模型
随着分布存储并行机的发展，提出了各类消息传递模型：BSP、LogP、C3等。
（1）BSP模型
BSP[5](Bulk Synchronous Parallel)模型是由哈佛大学Validate提出的，作为体系结构和计算机语言之间的桥梁，是一种由一系列超级步组成的、分布存储的MIMD计算模型。BSP模型的计算机由三部分组成：计算单元（处理器－存储器对）；单元间点对点通信；组件之间的同步机制。
（2）LogP模型
LogP[6]是1993年Culler等人提出的以MPC为背景的多处理机模型，具有分布存储、点到点通信等特点。其通信网络有一组参数来描述： L表示通信延迟； o表示通信开销； g表示通信时间间隔； p表示处理器／存储模块个数。
（3）C3模型
C3(Computation， Communication， Congestion)模型是有Hambrusch和Khokhar等人提出的一个用于粗粒度并行算法设计和分析的并行计算模型，此模型分析计算通信和通信中出现的潜在拥挤。
1．3 层次模型
UMH(Uniform Memory Hierarchy)模型是Alpern等人提出的，该模型是抽象化的存储层次结构，概括了计算机层次访问技术中与性能有关的特征。
2 常用并行计算模型的扩展
2．1 异步PRAM模型
由于PRAM模型是同步模型，用户虽然感觉不到，但是所有指令均是按照同步方式操作的，浪费时间；分布式存储的异步MIMD机器，超出了共享单一存储器的作用范围；未能描述当今并行体系结构使用的最普遍的两种技术：线程技术和流水线预取技术。所以对PRAM进行扩展，得到异步PRAM模型[7]，简记为APRAM，计算过程如图1所示。该模型由p个处理器组成，每个处理器都有其局部时钟和局部程序，通过添加同步路障（Synchronization Barrier）来控制程序的执行；共享全局存储器；取消全局时钟，各处理器一步、独立地执行各自的指令。定量化的成本参数是APRAM模型比PRAM更接近于实际的并行机。
2．2 CSA－BSP模型
BSP模型中，超步即连续的两个同步之间的周期，如图2所示。
每个超步由计算、通信和同步组成，但是同步操作使得超步之间相互无关，限制了处理机之间的异步执行 ，可能导致出现互相等待，降低了处理机的执行效率。为改进BSP程序的性能，提出了一些建立在BSP模型基础上的扩展模型：异步BSP模型（A－BSP）；HBSP模型；计算－发送段BSP模型（CSA－BSP）。CSA－BSP模型中一个计算－发送段（CS段）由计算部分和数据部分组成，CS－超步是由一系列计算－发送段和接受语句组成的。相对于A－BSP模型，CSP－BSP模型中，进程执行超步时，不必完成其所有计算，只需完成发送数据所在的CS－段的计算，即可执行下一条指令。
2．3 LogP模型扩展
LogP模型是带有缓冲的异步消息传递机制，采用异步通信的互联网络，具有良好的移植性，能体现出多线程技术。通过参数l、o和g刻画了通信网络的特性，屏蔽了网络拓扑、选路算法和通信协议等细节，加上参数p刻画了并行机的主要瓶颈。对于每个节点处理器，接收和发送消息时均要付出开销o，但由于并行机的硬件效率问题，LogP模型不支持长消息处理；在共享主存模式中，远距离读写操作视为两次消息传递，没有考虑计算机硬件与软件的影响：Cache命中率、进程同步和流水线预取技术等。基于对LogP模型的改进，又提出了很多扩展模型，如：LogGP、LogGPS、LogGPC、LogPQ等。LogGP模型对长消息做了特别处理，添加参数G，代表长消息每字节间距，如图3所示。
LogGPS是对LogGP的扩展，添加同步机制，定义一个表示消息长度阈值的参数S。LogGPC是在LogGP的基础上添加通信网络和网络接口。LogPQ则是添加消息队列，处理机发送和接收队列。
多核处理器，将多个相对简单、同构的处理器核集成到同一块芯片上，而且这些处理器核都共享片上高速缓存（Cache）。其中，片上多核处理器（CMP）技术的主要特点有：功耗低、延迟小、线程级并行等。随着多核处理器的普遍应用，大规模并行计算机都采用了多核处理器，构件集群平台，多核处理器集群的比较见表1。所以，在并行体系结构上，需要与之相适应的并行计算模型。第一节介绍的计算模型大多是以单核处理器为基础开发的，针对共享存储器结构和分布式存储结构的。近代计算机中，由于寄存器、高速缓存、主存对并行计算机性能影响越来越大，不同层次memory间流动的性能受数分布的影响，存在系统通信开销。Memory层次化并行计算模型也越来越少重视，如：memory LogP、LognP／Log3P。
现代的并行计算平台大多是建立在多核处理器机群平台上的，基于此原因，本文提出一个新的并行计算模型mzLogGP，这是基于多核机群平台的、考虑异构性和节点计算能力的非独占性的模型，充分考虑了网络拥塞对节点间通信存在的影响以及memory层次化对多核处理器机群消息通信性能的影响。其中，m代表多核环境下memory层次化的深度， z代表考虑网络拥塞指数，表示消息在当前网络存在拥塞和不存在拥塞时传递所消耗的时间比，用于反映网络拥塞的程度。
3 mzLogGP模型
并行系统由多个计算节点通过网络连接组成。任何两个计算节点之间可以进行通信，当网络中存在过多的数据包时，网络性能会下降，由此而引发网络拥塞。 mzLogGP模型是应用于多核处理器机群平台的模型，考虑到了网络方面对通信开销所带来的影响，使测得进程通讯开销更精确。网络拥塞程度，延时大小和带宽都是造成网络损耗主要原因，所以，可以选择更高性能的硬件资源，使得集群系统尽可能地减少网络损耗。
mzLogGP模型的参数有：P，o，l，g4个LogP的基本参数，根据第一节所讲，P代表处理器／存储器模块个数（节点个数），由多核处理器组成的并行系统一般有P个计算节点个数；o表示程序执行时互联网络的通信开销，包括发送开销和接收开销；L表示网络中消息传递所产生的延迟；g表示处理器可连续进行消息发送或接收的最小时间间隔。对于一个具体的并行机，网络传送一个M位的消息所花的时间为
T（M,H）＝Tsend＋[M／w]＋H?}r＋Trev （1）
其中，w为通道带宽；H表示H个跨步(Hops)；Tsend为接收开销，即处理器向网络传输数据前为网络接口准备数据的时间；Trev为接收开销，即处理器收到最后一条数据的处理时间；[M／w]为处理器发送消息到网上所需的时间；H?}r为最后一个数据通过网络到达目标节点的时间。在LogP模型中，对网络的容量增加了限制，以防止网络重载，出现资源竞争而浪费时间，模型参数选取如下：系统通讯开销o＝( Tsend＋Trev)／2，L＝H?}r＋[M／w]，g＝[M／b]，b为处理器对剖宽度。
LogP模型扩展参数：G，S，l，m，z。由于LogP模型中不支持长消息传递，引入参数G，代表节点发送或接收消息时单位长度数据的时间间隔；S表示单位时间内处理器处理的消息数，即计算速度；l表示同步时间机制，用于各个超步之间路障同步对并行程序执行时间影响的描述；z为网络拥塞的程度，表示消息在当前网络存在拥塞和不存在拥塞时传递所消耗的时间比， 用于考虑网络中传递消息的额外时间开销。
在多核处理器机群平台上，由于多核处理器中CPU和存储器能量提升失衡，不能满足高性能计算对硬件资源的需求，导致需要更多的核供计算使用，使多核不断地向众核发展，从而使处理器墙问题更加严重，非一致性访问内存成为必然的发展趋势；因存储器的差异而导致的带宽和通信延迟不匹配，使得并行更加层次化。因此，这里引入m参数，表示memory层次化深度，方便计算因memory存取过程而产生的通讯开销。
mzLogGP并行计算模型中，考虑影响系统通信开销的两大因素：memory和network。引入参数m计算memory中的通信开销；引入参数z计算网路中的通信开销。结构如图4所示。
由于缓存和主存互联结构的差异，多核处理器中片内通信、片间通信以及处理器节点间通信带宽和延迟不同，导致memory层次化加深，这一过程中的通信统称为节点内通信。对于短消息的传递，节点内通信较小，处理器各个核之间通信延迟较小；当传送较长消息，处理器负荷增加，核间通信延迟增大，与节点间通信接近。划分通信等级使测得的程序实际执行时间更加精确，以减小误差。
并行程序可划分为若干个超级步[7](Superstep)，用路障(B－arrier)分隔两个相邻的超级步，每个超级步中计算节点之间互相进行点对点通信。并行程序执行的总时间是所有计算节点的运行时间和节点间的通信时间的总和。一个超级步中包含若干个计算节点，所有超级步的计算时间和通信时间的总和为程序执行时间。假设一个并行程序由n个超级步组成，则预测模型的通信时间开销为：
T＝Ti＋Tj＋nlnet （2）
其中，Ti为超级步的节点内计算时间；Tj为超级步节点间通信时间；lnet为互联网络中的通信延迟。节点间通信时间受互联网络中带宽和延迟的影响，而节点内的计算时间为：
Ti＝om＋lm （3）
om表示处理器／存储器处理时间；lm为消息在处理器和存储器内的执行开销，减小这个开销的有效方法是改变中间件、硬件的性能，提高数据的吞吐率或带宽。由于多核处理器机群平台上，消息传递包括网络传递、CPU／memory处理、内存拷贝和缓存操作等，这些通信中间件的性能关系着这条消息传递的效率，通信层次明显。软件层次的memory层次化反映在中间件的性能上，网络通信开销从硬件层次反映了通信网络的性能。mzLogGP模型刻画了多核处理器机群计算平台处理器通信和网络通信的性能瓶颈和特征。
mzLogGP模型节点间通信与LogGP差别不大，其特征是可能存在网络拥塞；是否独自占有计算资源，节点是同构还是异构。首先考虑网络中不存在拥塞，节点独占计算资源，这是理想的网络信息传递模式。
这种情况下，节点处理器向另一节点处理器发送一条短消息，需要的时间为：om＋lm＋onet＋L，其中，onet是网络中接受或发送消息的通信开销。当发送长消息时，需要考虑参数G，假设一条消息长度为x字节，消息的通信开销为：om＋lm＋onet＋(x－1)G＋L，其中，处理器在第一个字节发送前，为网络接口的准备时间即为消息的发送时间，消息分为x等分，每个字节的发送需要G时间；网络的通信延迟为L。接收方的处理器和发送方的处理器在接收或发送消息时不能进行其他操作。
当发送多条消息时，处理器发送完一条消息后，至少要等待g时间才能发送第二条消息，第二条消息进入网络的时间为om＋lm＋(x1－1)G＋g，由于处理器连续处理消息的最小时间间隔的限制，处理器不能不间断地连续发送或接收数据。
理想的无网络拥塞情况下，消息传递效率最高，现实中很难实现，当网络中存在拥塞时，节点不能享有全部的计算资源，需要一定的时间来处理网络拥塞所造成的延迟。消息在网络中传递会出现等待现象，所以考虑了网络拥塞指数z，消息的通信开销为om＋lm＋(x1－1)z?}G＋g＋zL。
并行程序的执行时间，在没有重叠操作的情况下为：
T＝Tcom＋Tp＋Tconn （4）
其中，Tcom＝Ti，为节点内的计算时间； Tp为并行执行的开销时间，包括进程切换、结束等时间；Tconn为网络中的交互通信时间，受带宽、路障、延迟等影响。层次化存储器中，一个层次包含三个参数：带宽、延迟和容量，分为纵向和横向层次化，模型支持节点内和节点间通信互连拓扑，抽象化了memory横向和纵向层次化，大大优化了节点内的计算时间。 因网络拥塞所产生额外开销，是造成并行执行的预测时间开销和实测时间开销的关键原因。mzLogGP模型即采用了memory层次化技术，减少了节点内执行计算因CPU和memory速度不匹配而产生的额外开销；考虑了网络拥塞情况，验证消息在网络中传递时所带来的额外损耗。
4 模型评价与分析
本实验采用4节点机群，每个节点有2颗4核处理器，操作系统内核版本是Linux kernel 2．6．18，开发环境为mpich 2－1．3．2p1＋VC6．0，采用MPI－Send、MPI－Recv接口测试RTT的方法获取通信的时间开销，分别对不同大小、不同步长的数据进行了点对点通信和一对多集合通信的测试。
实验采用单字节消息的连续发送、连续Ping＿Pong、一次Ping＿Pong以及尽可能大数据的消息的Ping＿Pong等，得到MPI环境下，节点参数如表2所示。
下面测试mzLogGP模型在网络拥塞指数z＝1．1的情况下的程序执行时间。实验以Jacobi 迭代算法[8]为例，用mz－LogGP模型对算法的执行过程进行分析，在搭建的多核处理器机群平台上验证模型的有效性和实用性。
Jacobi 迭代具有良好的局部性，可取得很高的并行性，可将参加迭代的数据按块分割，如图5所示，各块之间处理相邻元素通信外，各块内部也可进行独立的并行计算，可降低计算的通信开销，有利于并行效果。
假设需要迭代的数据是M?}M的二维数组A(M,M)，令M＝4?}N，按图5进行数据划分，则分布在四个不同进程上的数据分别是：进程0，A(M,1,N)， 进程1，A(M，N＋1,2?}N)，进程2，A(M,2?}N＋1,3?}N)，进程3，A(3?}N＋1,M)。
根据mzLogGP模型的原理，在算法的每个步骤之间插入Barrier语句，将该算法分成4个超级步，以4级memory横向层次化技术求出机群平台上程序执行的节点内计算时间，再利用表2给出的参数，计算出Jacobi 迭代算法在mzLogGP模型下的分别传送512KB和2MB数据所运行的时间，并将实验测得实际运行时间与预测时间作比较。上述算法考虑了在阻塞指数z＝1．1的情况，MPI环境下。