基于MPI（通用8篇）
基于MPI 篇1
并行计算从本质上讲就是将多任务映射到多处理机上执行,或将多任务映射到具有特定拓扑结构的多节点机上求解,每台节点机启动一个进程。MPI(Message Passing Interface)消息传递接口[1]用于开发基于消息的并行程序,通过传递消息来协调各个并行执行的进程的步伐,并且利用交换信息和数据去控制执行并行计算任务,广泛应用于集群系统的并行程序开发环境。随着集群规模的不断扩大和节点机数的增加,异常关机、节点故障虽然不会经常但极有可能发生,但是现行的MPI标准中不包括任何机制去恢复意外失效的进程,系统发生故障时程序必须从头开始重新执行,从而引起计算时间的大量浪费[2]。因此,需要将容错技术引入到并行计算中,保证在发生各种异常事件或故障时,为用户提供持续的服务。
目前,并行程序的容错通常是基于检查点技术,再加入故障探测、处理以及自动恢复等辅助功能而形成的完整容错机制,在全局一致性状态下将进程的运行状态进行保存,当程序运行出现故障时,利用保存的进程状态对出错进程进行恢复,使计算任务从检查点处恢复执行,以减少计算损失,提高程序运行的可靠性和可用性。
1 容错相关内容
1.1 检查点技术
检查点技术[3]是指在程序运行时选择适当的时刻设置检查点,进行检查点操作,保存各个进程的运行状态到存储器中,系统如果在随后的运行过程中发生故障,所有进程停止计算卷回到上一次最近的检查点处,利用检查点处保存的正确状态去恢复出错的进程,从该检查点处重新计算。其过程如图1所示,这样可以避免由于故障而导致程序从头重新执行,因而能有效地减少计算损失。
在设置检查点时要保证所有进程处于全局一致性状态[4],所谓全局一致性状态,就是一个并行程序在无错执行期间所有进程的某种状态集合,当某个进程的状态表现为发送了一条消息时,在相对的另一个进程状态必须反映为接收该消息。为了发生故障时正确地卷回恢复,设置检查点时必须保证记录的状态是所有进程处在全局一致性状态下,避免产生多米诺效应。
如图2所示,黑色方块代表各个进程独立设置的检查点,当进程P2发出消息m7后发生故障,则卷回到检查点C处,卷回过程中P2取消发送m7,因此P1必须回退到检查点B以取消对m7的接收。同理P1发送的消息m6无效,进程P0卷回到检查点A处,依次类推,P1卷回到D处,导致P1卷回到E处,P0卷回到F处,最后所有进程又卷回到起点,重新开始计算所有任务,这种现象称为多米诺效应[5]。
1.2 故障
一个系统是容错的[6],是指并行程序在发生逻辑故障的情况下仍然能够正确地运行,故障模型[7]一般分为两类:Byzatine故障模型和Fail-stop故障模型。本文针对Fail-stop故障模型进行研究,可描述为并行计算中进程的挂起或崩溃情况,是并行计算领域常见的硬件故障模型。fail-stop故障可分为节点失效故障和进程失效故障两大类。节点失效故障一旦发生,进程执行中断不对任何请求做出响应,比如进程崩溃故障、系统掉电故障等;而进程失效故障是指某个进程异常退出,其它进程或运行环境无法感知,并行程序成为悬空程序。两种情况的发生都会导致并行程序计算失败,因此,容错系统应及时检测出出错的故障类型,以便系统进行卷回恢复处理。
1.3 卷回恢复
卷回恢复技术[8]把一个并行系统看作是一个应用进程的集合,各进程相互之间通过网络通讯。在进程无错执行到检查点处将进程的运行状态保存到稳定存储器中来实现容错,当出现错误时,一个出错进程可从检查点处所保存的一个状态中进行重启恢复,这样就可以尽量减少计算的损失。在卷回恢复过程中,可以通过进程迁移来实现,将在出错进程上执行的任务迁移到另外一个进程上,执行同样的计算得到结果。还可以重构并行环境,发生故障后,所有进程卷回到上一次最近的检查点处,利用保存的进程状态重构并行环境,重新分配任务进行计算。本文研究的容错系统采用后一种方法,将出错进程剔除,剩余节点机重构并行环境,实现负载平衡重新执行计算任务。
2 容错系统的设计
本MPI并行程序的容错系统可分为三个模块:用户界面模块、总控模块和检测模块。用户界面模块:是容错系统和用户的通讯接口,用户在界面上完成所有准备工作,然后启动容错系统运行并行程序,并且在计算的过程中,系统运行状态会输出显示在用户界面上,方便用户了解各个节点机的状况;总控模块:掌握整个系统的运行过程,系统初始化、调用执行并行程序、负责检查点操作、卷回恢复处理,以及协调检测模块与总控模块的配合;检测模块:监听各个进程运行状况,一旦发现某个进程发生故障则向总控模块报告。
本容错系统的模块结构图,如图3所示。
2.1 检查点的生成
本文针对MPI并行程序而设计的容错系统,设计的出发点是在容错系统上调用并行程序,然后启动后台并行环境执行并行计算。用户必须将并行程序进行粒度划分,使得每一个粒度成为一个.exe的可执行程序,并将所有的.exe可执行程序交给容错系统。用户可以根据MPI的特点以及需要自由地对并行程序进行粒度划分,并规定.exe可执行程序被容错系统调用的顺序。
容错系统通过依次调用所有粒度的.exe可执行程序完成计算任务,将粒度连接点默认为检查点,作为卷回恢复的参考点,在每个检查点处保存进程的运行状态,利用这些状态去恢复出错的故障。此检查点方法可以避免产生多米诺效应,如图4所示,当进程P1或是P2发生故障时,所有进程停止计算任务,卷回到上一次最近的检查点B或是C处,由主进程P0根据故障类型对出错进程进行恢复,重新执行计算任务。
2.2 用户界面模块
用户界面是用户与程序交互的窗口,比较直观,方便用户与容错系统的交流,在界面上用户进行相应的操作,完成所有准备工作,然后启动系统开始运行并行程序,在计算的过程中各个节点机的运行情况会输出显示在用户界面上,方便用户了解各个节点机的状况。用户的准备工作如下:
1)依次保存要运行的.exe可执行程序;
2)存储机器信息文件,用于判断可用于并行计算的节点机以及故障检测的依据;
3)登记用户名和密码,用于并行计算的节点机的用户名和密码。
在容错系统界面上操作以上三个步骤,即可启动系统执行并行计算。
2.3 总控模块
总控模块是容错系统的核心,由主进程调用执行,主要包括三个部分的内容,系统初始化、检查点操作以及卷回恢复处理,系统功能示意图如图5所示。
1)系统初始化。主进程进行初始化工作,获得使用的机器信息和初始化各类系统资源,系统将初始化设定为第一个检查点,在此处保存所有进程运行状态,即得到本局域网中可用于并行计算的所有节点机,并将相关的信息(即可计算节点机的机器名和IP地址)保存在本地磁盘上的检查点文件中,这些信息用于总控模块给符合条件的节点机分配任务执行.exe可执行程序,同时这些信息也是检测模块执行的原始数据。
2)检查点操作。当系统执行到检查点处主进程调用总控模块进行一次检查点操作,任务是保存此时进程的运行状态到本地磁盘上的检查点文件中,用于执行下一个.exe可执行程序为各个进程分配任务以及发生故障时进行卷回恢复处理的依据。进程的运行状态包括节点机的机器名和IP地址,执行并行计算时将任务平均分配给这些机器名对应的节点机,在这些节点机上分别启动一个进程执行并行计算的任务,IP地址用于检测模块监听进程时判断参与计算的进程是否正常运行。
3)卷回恢复。当参与计算的某一节点机上的进程发生故障时,总控模块执行卷回恢复任务,所有进程停止一切计算任务卷回到上一次检查点处,主进程读取该检查点处的检查点文件内容,得到所有符合运行条件的进程,根据所发生的故障类型进行恢复处理,如图4所示,当发生进程失效故障时,重新启动所有进程再一次进行相同的计算任务,相应的,当发生节点机失效故障时,主进程去掉出错进程,为检查点文件中保存的其他剩余进程重新分配任务,然后进行相同的计算。
2.4 检测模块
检测故障是实现并行程序容错的重要环节之一,保证实现容错功能的先决条件,探知发生故障及其类型并交由总控模块判断进行哪种处理。检测模块由守护进程来实现,周期性地检测进程运行状况是否良好,如发生故障及时通知主进程的总控模块。
利用java提供的异常(Exception)处理实现故障检测的功能。除了标准异常,根据容错功能的需要扩展java.lang.Exception类来实现特定的异常,如在表达故障类型时事先定义每种故障发生对应的异常,将某节点机网络不在线定义为节点失效故障,MPI并行环境的wmpiconfig.exe进程不在线定义为进程失效故障。当抛出异常时总控模块得知发生故障,提供了一种在并行程序容错中实现错误捕捉的机制。
3 系统测试
以基于MPI的P-Q法潮流并行程序为测试用例,验证容错系统的有效性。此并行程序被划分为四个粒度,容错系统依次调用四个粒度的.exe可执行程序。实验方法:在执行计算的过程中断开一台用于并行计算的节点机的网络连接制造节点机失效故障,另一种方法是手动杀死一台节点机上的MPI进程制造进程失效故障。测试结果如表1所示。
实验结果表明,本容错系统能够检测出并行程序计算过程中发生的节点机失效故障和进程失效故障,并且能够对故障进行相应的处理,最终得到并行计算的结果,实现了一定范围内的容错功能。
4 总结
本文将容错技术应用到并行计算中,在不修改原并行程序代码的情况下设计出一个容错系统,利用守护进程实现故障的检测及时发现故障,并结合检查点/卷回恢复技术对出错的进程进行恢复,为并行计算的过程提供保障。本文设计的容错系统实现了对除主机之外的其他节点机故障的恢复,一旦主进程发生故障,则所有计算都白费。本文下一步的研究工作是解决此问题,可以将生成的检查点文件进行备份,保存在另外一台计算节点机上,主机发生故障后将此节点机上的进程转为主进程,负责重构并行环境和启动并行程序重新计算。
摘要：为了确保并行程序能够在并行环境下准确地运行,须提高系统的可靠性,将容错技术应用到并行计算中。该文针对MPI并行程序提出一种容错系统的设计方法,采用检查点/卷回恢复技术、并添加故障检测功能,能够有效地处理节点失效故障和进程失效故障,在一定范围内实现容错,为MPI环境下进行大规模计算提供一个可使用的应用模型。
关键词：MPI并行程序,容错,检查点/卷回恢复,故障检测
参考文献
[1]任波,王乘.MPI集群通信性能分析[J].计算机工程,2004,30(11):71-73.
[2]崔丽青,徐炜民.MPI容错问题的研究及实现[J].计算机应用,2003,23(12):236-238.
[3]周恩强,卢宇彤,沈志宇.一个适合大规模集群并行计算的检查点系统[J].计算机研究与发展,2005,42(6):987-992.
[4]万国伟.消息传递系统容错技术研究[D].长沙:国防科学技术大学研究生院,2006:15-21.
[5]薛瑞尼.面向集群系统的MPI并行程序容错技术研究[D].北京:清华大学,2005:12-23.
[6]丁俊,童维勤.群机系统的容错和恢复[J].计算机应用,2001,21(06):90-92.
[7]孙峻朝,王建莹,杨孝宗.故障和容错机制的层次模型[J].计算机工程与应用,1999(10):5-7.
[8]周军海.基于回卷恢复的MPI程序容错[D].长沙:湖南大学,2004:32-38.
基于MPI 篇2
通信域
??MPI通信域包括两部分：进程组和通信上下文。进程组即所有参加通信的进程的集合，如果一共有N个进程参加通信，则进程的编号从0到N-1;通信上下文提供一个相对独立的通信区域，不同的消息在不同的上下文中进行传递，不同上下文的消息互不干涉，通信上下文可以将不同的通信区别开来。
讲解
??一个预定义的通信域MPI_COMM_WORLD由MPI提供。MPI初始化后，便会产生这一描述子，它包括了初始化时可得的全部进程，进程是由它们在MPI_COMM_WORLD组中的进程号所标识。
??用户可以在原有的通信域的基础上，定义新的通信域。通信域为库和通信模式提供一种重要的封装机制。他们允许各模式有其自己的独立的通信域，和它们自己的进程计数方案。
-----------------------------------------------------------------------------------------------------------------------
除了数据部分, 消息带有用于识别消息并选择接收他们的信息。这个信息是由确定的域数组成的，我们称信封。这些域有 :
source( 源 )
destination( 目的 )
tag( 标识 )
communicator( 通信子 ) 也称作通信域
消息的source隐含地由消息发送者的标识来决定，
其他域是由发送操作的参数决定。
消息的destination是由dest参数指定。
整型值的消息tag是由tag参数指定。这个整型能被程序用于识别不同的消息。有效标识值的范围是0,...,UB, 这儿UB的值依赖于实现。在第七章描述，通过查寻属性MPI_TAG_UB的值, 可得到UB。MPI要求UB不小于32767。 comm参数指定用于发送操作的communicator。在第五章解释communicator; 下面是其使用的简介。
一个通信子( communicator )给一个通信操作指定上下文。每个通信上下文提供一个单独的“通信全域”：消息总是在其被发送的上下文内被接收，不同的上下文发送的消息互不干涉。
通信子也指定共享这个通信上下文的进程组。这个进程组被编号，并且进程是由这个组中的进程号标识。所以，dest的有效值范围是0,...,n-1, 其中n是该组中的进程数。( 如果这个进程组是一个通信子间的, 那么destination是由远程组中他们的进程号所标识。请看第五章)。
一个预定义的通信子MPI_COMM_WORLD是由MPI提供。MPI初始化后, 它允许和可存取的全部进程通信, 进程是由他们在MPI_COMM_WORLD组中的进程号所标识。
给用户的建议. 喜欢进程名字空间的用户, 和由大多数已存在的通信库提供的一个简单通信上下文, 仅需要使用预定义的变量MPI_COMM_WORLD作为comm参数。这将允许初始化时和所有可能得到的进程通信。用户可以定义新的通信子，第五章解释这个。通信子为库和模式提供一种重要封装机制。他们允许模式有其自己的独立的通信域，和他们自己的进程计数方案。(给用户的建议结束)。
给实现者的建议. 消息信封将正常地由一个定长的消息头编码。但实际的编码是依赖于实现的。有些信息( 例如, source或destination )可以是隐式的, 不必由消息显式携带。进程也可以由相对的进程号或绝对的进程号标识，等等。(给实现者的建议结束)。
基于MPI的随机数并行检验算法 篇3
随着计算机科学技术的发展,随机数已越来越多地应用于一些大规模科学与工程计算尤其是MC数值模拟中。随机数发生器是MC方法的基础和核心,随机数检验是确保随机数品质的必要条件。国内外针对随机数检验大多采用串行的方法,对于长周期的随机数,传统的串行检验方法往往显得太慢。本文针对这一问题将主要采用Monte Carlo方法提出一种随机数并行检验的方法来提高检验速度。
1 相关工作
目前,国内外很多研究人员在随机数发生器和随机数检验方面做了大量的工作。L’Ecuyer[2]提出了线性同余组合随机数发生器,该方法产生的随机数序列具有线性同余序列的所有特性,在高维空间的均匀性要优于线性同余发生器。
Sergio Callegari[3]等设计出一种基于模数转换(ADC)的嵌入式真随机数发生器,并对产生的随机数的品质进行了验证,结果表明这种随机数发生器能够应用于密码学。
Yufeng Liang与P.A.Whitlock[4]针对并行随机数发生器提出了一种经验化的检验方法。Ashok Srinivasan[5]等人又根据并行随机数的特点,提出并行随机数检验应该进行内部和外部两类相关性测试。
在国内,龚春叶[6]等对为大型通用粒子输运程序MCNP(Monte Carlo N-Particle Transport Code)设计的并行随机数在GPU上进行了加速优化。中国科学院计算中心张建中[7]教授的随机数检验程序系统SUTEST给出了十二类、二十七种不同的统计检验方法,此外,还有不少研究人员对随机数及其检验进行了深入系统的研究,也扩展了一些思路。
2 串行检验算法
2.1 最值检验
最值检验主要是检验随机数序列的最大值和最小值。众所周知,U[0,1]区间上均匀随机数序列的最大值和最小值分别为1和0。
2.2 卡方(χ2)检验
采用χ2拟合优度检验法进行随机数的分布均匀性检验。将样本的取值范围分布在m个等宽区间,即分成O~1/m,1/m~2/m,…,m-2/m~m-1/m,m-1/m~1,m个区间。统计实际落在每个区间内的样本个数。
检验假设H0:ni=mi成立,若假设成立,则有
自由度n=k-1=m-1。由于当n>m-2时,χ(不是χ2)近似服从正态分布N(0,1),即近似的有:
取α=0.05,则χ0.05=1.645,将n=m-1代入计算得出χ02。(可查表得到χ20.05=44.985)比较χ02和χ20.05的大小,当χ02<χ20.05时,通过检验。
2.3 柯氏(KS)检验
设F(x)是某随机变数的分布函数,FN(x)是对该变数作N次独立观测获得的经验分布函数,由格列汶科定理,当N→∞时,有
根据柯尔莫哥罗夫定理,若F(x)是连续的,则当N→∞时,有
因此,当实验次数足够大时,就可认为的概率趋于K(z)。现对上述的N设DN0为|FN(x)-F(x)|中最大的一个,且,若
同时如α很小,这就出现小概率事件,而由此可检验差异的显著性。
2.4 参数(矩)检验
假设我们产生的随机数服从U[0,1]均匀分布,则有:
服从U[0,1]均匀分布的随机数的期望均值与期望方差为:
取统计量X1,Y1,则当n充分大时,服从标准正态分布。
取α=O.05,查正态分布表Zα2=1.96,仅当|X1|<1.96且|Y1|<1.96时,才接受此假设。
3 并行检验算法
3.1 MPI并行环境
MPI[8]是一种基于消息传递思想的编程模型,它在原有编程语言(例如Fortran、C语言)的基础上进行扩展和延伸,使其能够并行执行。MPI本质上是一个库,它通过提供应用程序编程接口方便用户进行调用。各个并行执行的部分通过消息传递来交换信息、协调步伐、控制执行。MPI提供了一种与语言和平台无关可以被广泛使用的编写消息传递程序的标准用它来编写消息传递程序不仅实用可移植高效和灵活而且和当前原先的实现相差无几。MPI吸取了众多消息传递系统的优点,是目前国际上最流行的并行编程环境之一,尤其是在针对大规模科学与工程计算的分布式存储的并行计算机中。MPI具有具有可移植性、易用性、完备的异步通信功能、正式和详细的精确定义等优点,成为大规模科学与工程计算工业标准。
3.2 并行随机数发生器
根据近年来研究人员对多种随机数的产生及并行实现[9],研究发现采用分段随机数序列,并行与串行可以取得相同的计算结果。适合MCNP的并行随机数发生器采用分段法[10],算法如图1所示,其数学原理是基于组合线性同余法。其中,seed[2]是初始化种子,Mod[2]是模数,NUM是需要生成的随机数的数目,NORM是Mod[2]中第一个数的倒数。跳跃的距离为4297的整数倍,如何跳跃可参考文献[6]。
3.3 并行检验算法
随机数并行检验算法如图2所示。基于MPI并行环境,启动N个线程。每个线程按图1所示方法产生一定数量的随机数,并分配到相应的进程中,然后采用不同的检验方法对相应的随机数进行检验,根据检验算法的不同,采用不同的归约算法,在中间可能采用MPI_Allreduce()进行进程间通信交换数据,最后对检验结果采用MPI_Reduce()进行汇总。
4 测试结果
4.1 试验平台
试验平台采用Intel六核至强处理器X5670,主频为2.93GHz,系统内存为48 G,操作系统为Red Hat Enterprise Linux Server release 5.2,编译器为Intel编译器,编译时采用3级优化。
4.2 并行和串行检验结果对比
对适合MCNP的随机数的串行和并行检验结果如表1所示。从检验结果得知,并行检验结果保持和串行检验结果完全一致。从而说明我们设计的随机数并行检验算法的正确性。
4.3 性能比较
使用1、2、4和8个线程时对352010240个随机数进行最值检验、卡方检验、柯氏检验和矩检验所耗费的时间如表2所示,单位为秒。
通过上图试验数据可以看出,当检验随机数个数为352010240时,矩检验单进程即串行检验运行时间3.97秒;进程个数为2时,运行时间1.98秒,加速比为1.99;进程个数为4时,并行执行时间0.99秒,加速比3.99;进程个数为8时,并行执行时间0.49秒,加速比7.98。并行检验加速效果如图3所示。
可以看出,随着MPI工作进程的增加,加速效果越来越明显。
5 结束语
在随机数检验中,如何快速准确的检验随机数的随机性已成为当前随机数研究的一个重要方向。该文从随机数的统计检验出发,提出了一种基于MPI的随机数并行检验的方法,对于当前应用较为广泛的MCNP中使用的并行随机数发生器进行了检验,结果表明该检验能有效提高随机数检验速度,效果明显。
下一步工作包括在更大规模的计算机系统上,试验本文设计算法的并行性能,进一步设计其它随机数并行检验方法,并对更多的并行随机数进行检验。
参考文献
[1]徐钟济.蒙特卡罗方法[M].上海:上海科技出版社,1985:5-28.
[2]L'Ecuyer P.Uniform Random Nmber Generators[C].Simulation Conference Porceedings,1998.
[3]Callegari S,Rovatti R,Senior G.Embeddable ADC-Based True Random Number Generator for Cryptographic Applications ExploitingNonlinear Signal Processing and Chaos[J].Transactions on Signal Processing,2005,52(2):793-805
[4]Liang Yufeng,Whitlock P A.A new empirical test for parallel pseudo-random number generators[J].Mathematics and Computers in Simu lation,2001(55).
[5]Srinivasan A,Mascagni M,Ceperley D.Testing parallel random number generators[J].Parallel Computing archive,2003,29(1).
[6]Gong Chunye,Liu Jie,Chi Lihua,et al.Accelerating Pseudo-Random Number Generator for MCNP on GPU[C].International Conference ofNumerical Analysis and Applied Mathematics,2010.
[7]张建中.随机数检验程序系统[J].计算物理,1989,6(3):371-377.
[8]都志辉.高性能计算并行编程技术:MPI并行程序设计[M].北京:清华大学出版社,200l:15-17.
[9]邓力,许海燕,王瑞宏.确保并行与串行结果一致的蒙特卡罗并行随机数产生及应用[C].中国工程物理研究院科技年报,2001.
基于MPI 篇4
本文基于MPI集群框架结构,通过分析单层型集群和树型结构集群的聚合通信原理,提出了一种采用树型结构的MPI集群系统设计方案,用以降低聚合通信的开销,改善集群计算环境,同时也为集群的扩展提供更加灵活的手段。聚合通信包括很多全局操作(如广播、同步、归约、分发、收集)等,但很多聚合通信是由其他聚合通信的组合来实现的,本文选择了有代表性的广播和收集作为主要研究对象。
1 单层型结构与树型结构
1.1 单层型结构介绍
单层型结构是目前大多数MPI集群工具所采用的框架结构。如图1所示。该结构由一个主控节点和多个从属节点组成,主控节点和每个从属节点之间都建立了通信连接,实现聚合通信,从属节点相互之间可以实现点到点通信[2]。
主控节点的功能主要包括与用户进行交互,向从属节点广播、分发消息,收集、归纳从属节点发来的消息,以及系统认证、网络管理和远程控制等。
从属节点的功能主要用于计算、接收主控节点发来的各种控制命令、数据,根据控制命令在其节点机上进行相应的执行,然后将执行后的结果传回给主控节点。
单层型结构集群的实现相对简单,易于操作,且集群工具和应用软件较多,所以应用广泛。但是由于集群中只有一个主控节点,在聚合通信时,无论是一对多模式,多对多模式还是多对一模式,都要围绕着主控节点进行,使得集群中全局通信流量所占比重较大。当集群节点数增加或计算量很大时,网络负载极易到达额定上限,使得主控节点无法正常运行,计算性能下降。
单层型结构的消息广播和消息收集的时间复杂度均为:O(n)
1.2 树型结构介绍
树型结构是针对单层型结构在消息广播和消息收集方面速度慢、可扩展性差的弱点而提出的新的消息传输结构。图2所示为典型的树型结构,和单层型结构一样,树型结构也有主控节点(根节点)和从属节点(叶子节点),且功能与单层型结构类似。不同的是,树型结构中还包含分支节点,这些分支节点是树的内部节点,没有计算功能,也没有系统认证、网络管理和远程控制等功能,只有对消息的转发、分发和收集功能,所以也叫路由节点。图2中,根节点与其下一层的分支节点有直接的通信连接,同样每个分支节点都与其下一层的节点有直接通信连接,上层节点与下层节点可以实现聚合通信,而拥有同一个父亲的同层节点之间可以进行点到点通信。除此以外,其他非同父节点相互之间没有建立直接的通信连接。
树型结构集群可以将全局通信域划分为多个子通信域,并且可以将主控节点的负载量分担到各个分支节点上,降低全局通信量进而改善集群计算环境。同时随着树的深度增加,使得集群更易于扩展。但该集群实现起来比较复杂,且没有专用的协议、应用软件或集群工具的支持[3]。
树型结构的消息广播和消息收集的时间复杂度均为:O(1ogn)
2 树型MPI的设计与实现
虽然使用树型结构的集群系统可以改善聚合通信的效率,但其实现起来则相对复杂。主要原因是常用的MPI计算通信工具基于单层型集群设计,是在主控节点与若干计算节点之间的通信基础之上实现的。为此,本文提出了一种利用IP转发技术和MPI并行编程技术实现树型结构的MPI集群系统设计方案。这里需要注意以下问题:
(1)根节点的设计
在构建集群网络时,网络安全和通信效率既相互依赖又相互制衡。若省去频繁的核实用户身份等安全方面的检查,则可以省去一部分系统开销,进而提高网络通信效率,但集群网络的安全性就无法保障;同样,若牺牲通信效率而实现网络安全,则集群计算的优势将无法体现。通常的做法是采用内外网模式,即从属节点和主控节点之间由内部网络互联,只有主控节点另有网络通道通向外部网络。这样,由于内外网络物理隔离,为网络安全提供了保证,在内部网络中可以省去频繁的用户身份认证等安全方面的开销,从而为通信效率的提升留出空间。
根节点(主控节点)的设计也将采用内外网模式,在其机器上安装两块网卡(网络适配器),一块接集群内部网,使用内部网络设置,提供内部网络服务(域名服务,NIS,NFS和RSH);另一块接外部网,留出对外联系的通道,两网卡之间不提供路由、转发等功能。
(2)分支节点的设计
树形结构中的分支节点用于连接根节点(主控节点)和叶子节点(计算节点),在整个集群中发挥两个作用:一个是承上启下的连接作用,另一个则是对根节点(主控节点)的分担作用,所以分支节点应具有路由和对消息的传递、分发和收集等功能。
分支节点的设计与根节点有类似之处。也是在其机器上安装两块网卡,一块连接上层节点(根节点或上层的分支节点),IP地址设置在上层节点的同一个网段内,默认网关指向上层节点(父节点),使其成为上层网络的成员;另一块连接下层节点(下层的分支节点或叶子节点),设置IP地址(最好与前一块网卡的IP地址不同网段),为下层网络提供网关服务。但若要在上下层两个网络实现路由,需要在分支节点上修改/etc/sysctl.conf配置文件中的net.ipv4.ip_forward=1 (以Linux操作系统为平台参考),使得本节点机IP转发功能生效。这样做的目的是既能实现上下两层网络之间的通信,同时又能阻止基于网络第二层的广播帧的传播。
(3)域名的设计
在TCP/IP中,计算机之间的通信通过IP访问来实现,但IP地址不容易编程和管理,所以整个集群系统需要为每个节点提供一套统一的命名机制。如图3所示,Boot为根节点内部网卡的网络标识,bran01-up和bran01-down为同一个分支节点机上的两块网卡上的网络标识,前一块为连接上层网络的接口,后一块为连接下层网络的接口,leaf01为叶子节点的网络标识。MPI编程环境可以通过此域名来区分、访问运行在各个节点机上的进程(如MPI_Get_processor_name()函数)。
对于集群系统来说,集群中所有节点域名和IP地址的对应关系的建立是在/etc/hosts文件中描述的,不仅是因为它们经常用到,而且还因为该文件结构简单,更易于快速查找。图3所示的/etc/hosts.equiv文件可以为RSH(远程shell命令)提供无口令远程登录,这也为各节点载入同一个计算程序二进制代码和用户身份的快速验证提供了可能。
(4)进程组和通信域的设计
MPI中的通信域(Communicator)提供了一种组织和管理进程间通信的方法。每个通信域包括一组MPI进程,称为进程组。这一组进程之间可以相互通信,而且这个通信域内的通信不会跨越通信域的边界。这样就提供了一种安全的消息传递机制,因为它隔离了内部和外部的通信,避免了不必要的同步。每个进程都至少在某个特定的通信域中,但有可能进程在多个通信域中,这就像某个人可以是多个组织的成员一样。进程组由一个进程的有序序列进行描述,每个进程根据在序列中的位置被赋予一个进程号(0,1,…,N-1)[4]。
本文将根节点与其相邻的下一层节点(孩子节点)划定为一个进程组0,将分支节点1与其相邻的下一层节点(孩子节点)划定为进程组1,…,依此类推,直到所有分支节点或根节点都拥有自己的进程组为止,如图4所示。由于每个分支节点或根节点都有两块网卡,所以将两块网卡分属不同的进程组中,彼此互不包含。将全局通信域划分成若干个子通信域,使得大量的消息传递开销被限制在局部范围内,大大降低了全局通信的频率,从而提高了集群通信的性能。
(5)组间通信
进程组划分之后,形成相应的通信域,规避了大量节点间同步所消耗的开销。但进程组之间也要进行通信,根节点需要将消息逐层传递到叶子节点,同样叶子节点所计算出来的结果也是要逐层收集、规约到根节点,所以组间通信也是本系统实现的关键之一。这里,通过使用MP1组间通信函数(如MPI_Intercomm_create ()函数)来实现组间消息的传递。
(6)叶子节点的设计
叶子节点作为主要计算节点,除了NIS、NFS、RSH客户端软件和MPI相关软件外,尽量不再安装其他软件,以减少叶子节点额外的开销。设置与其父节点同属一个网段的IP地址,并将网关指向其父节点。如有必要可以精简操作系统内核,使其尽量占用CPU时间少、占用内存少。
3 实验结果与分析
3.1 实验环境和方法
本实验将先后搭建三组环境对这两种结构的MPI集群进行测试,测试环境如下:
(1)第一组是具有2个计算节点的集群,单层型和树型集群均由1个主控节点和两个计算节点构成。
(2)第二组是拥有4个计算节点的集群,单层型是指1主控节点和4个计算节点构成,而树型结构则是由1个根节点(主控节点),2个分支节点和4个计算节点构成,其中每个分支节点各连接两个计算节点,对称分布。
(3)第三组是具有6个计算节点的集群,如图5所示。左图为单层型MPI集群,拥有6个计算节点和1个主控节点;右图为树型集群,拥有1个根节点,2个分支节点和6个计算节点。
这其中每个节点包含一颗PIV处理器和2 GB内存,操作系统采用Redhat Linux Enterprise 5,并行集群软件为OPEN MPI 1.3。由于条件所限,加之实验规模较小,所以本实验采用MPI自带的函数MPI_Wtime ()来采集MPI计算的开始和结束时间,取两者的时间差作为程序的运行时间,并对其进行比较和分析,用MPI_Wtick()函数来监测MPI_Wtime()返回结果的精度。
在实验用例设计上,考虑到两种MPI集群的通信机制中的传输路径不同,所以采用计算求解三对角方程组作为测试方案,主要测试通信和计算的平衡。
3.2 测度结果和分析
测试结果如表1、表2所示。
测试结果表明,在第一组的测试中,双方的运行时间没有明显差别,这是由于它们都拥有1个主控节点和2个计算节点。虽然树型结构在MPI聚合通信机制上有所改动,但影响有限,测试的结果基本相同。对于第二组的测试,测试结果差异较明显,在传输短消息时,可以发现单层型集群的运算速度并不比树型慢多少,在16B的情况单层型还优于树型。这是因为树型结构的集群中除了拥有和单层型相同数目的计算节点外,还有两个分支节点(也叫路由节点),分支节点需要在两个通信域之间传递处理消息,需要处理时间,所以树型结构的消息传输时间除了消息广播和收集时间外,还有域间转发处理的时间。尽管在时间复杂度上树型结构优于单层型结构,但在通信域中节点数较少、消息较小的情况下,两者之间差距不是十分明显,若再加上域间处理的时间,自然会出现这样的情况。但当消息增大时,由于树型结构中每个通信域的广播和收集时间远远小于单层结构的广播和收集时间,从而抵消了分支节点处理消息的时间,所以树型的整体运算时间明显小于单层型的运算时间。对于第三组的测试,树型的整体运算时间明显优于单层型集群,几乎相当于同级别单层型集群的1/2。这是由于随着计算节点的增加,树型MPI集群的优势明显发挥出来,尤其是聚合通信方面。
(s)
(s)
由上分析表明,基于树型MPI并行计算集群的设计方案是可行的。在该方案上构建的MPI集群系统可以使消息广播和消息收集的速度明显提高,使得全局通信使用频率明显下降,从而提升了集群整体计算速度。同时,由于树型结构的特点,使得集群的扩展更加轻松。尽管从理论上可知随着节点数的增加树型MPI的集群的优势将更加凸显,但是由于实验条件的限制,只能对集群通信系统做初步验证。所以希望在未来的研发工作中能够引入更科学的评测体系,不断地论证和完善该系统,为提升中小型MPI集群性能提供帮助。
摘要：针对单层型MPI集群通信效率不高的特点,通过对比分析单层型结构和树型结构在集群聚合通信中的不同,提出了一种基于树型结构的MPI集群系统设计方案。用以降低全局通信流量和均衡主控节点负载,从而改善集群通信效率,使集群的扩展更加灵活,通过实验验证了该方案的可行性。
关键词：MPI,聚合通信,广播,收集
参考文献
[1]刘洋,曹建文,李玉成.聚合通信模型的测试与分析[J].计算机工程与应用,2006(9):30-33.
[2]CHEN C P.The parallel technologies(PaCT-2003)[C]. Nizhni Novgorod,Russia.2003.
[3]ROCH P C,ARNOLD D C,MILLER B P.MRNet:A software-based multicast/reduction network for scalable Tools[A].Phoenix,Arizona,2003.
基于MPI 篇5
随着计算机科学的发展,依赖于并行技术的高性能计算已经成为工程计算的新方向。并行计算能极大地提高问题的求解规模,并达到理想的解题速度。因而特别适合于大型工程结构和多物理场问题的精准计算,为工程设计提供科学依据。但这类问题往往模型很复杂,程序冗长。作为并行计算方法上的研究,我们首先选用简单的导热问题进行并行算法的尝试,在取得经验后再应用到较复杂的散体粒子数值计算的并行处理上。
近年来,人们对导热和传热传质等的实时计算提出了更高的要求,但基于有限差分法等手段建构的串行数值模拟方法,在考虑因素众多、划分网格更加精细时,单机环境下的数值模拟难以在短时间内完成计算任务,模拟周期成倍延长,因此发展并行计算成为解决这一难题的主要途径。稳态导热的计算由传统的串行计算发展为基于MPI、PVM、OpenMp等的并行计算。文献[1]通过融合MPI和OpenMP的区域分裂并行计算算法,运用非结构化网格有限元方法对复杂区域的温度场进行数值模拟,证明了融合MPI和OpenMP的区域分裂的并行方法可以在计算流体力学问题的并行求解中应用;文献[2]使用PVM并行编程技术对温度场的可视化进行了并行化研究,指出基于PVM的并行编程易于实现科学计算以及可视化等方面的并行开发;文献[3]使用MPI并行编程方式对金属凝固过程的温度场进行模拟,有效地提高了模拟计算速度等。然而,多数文献均是研究某一特定情境下的温度场的并行实现,并没有针对温度场并行实现的设计方法、性能效率等方面进行研究。本文以稳态导热为应用背景,进行相应的并行设计方法及其性能效率的比较研究,旨在展现并行设计的一般思路,扩大求解规模、缩短运行时间、提高效率,并且易于扩展到其他数值计算领域。
1 稳态温度场的基本算法
1.1 稳态温度场控制方程
对于物理场中的导热问题,基本物理量为温度T(x,y)。无内热源的热传导问题的控制方程:
这是典型的Laplace方程。为简单起见我们对宽×高的尺寸为a×b的矩形域求解,采取等距网格,x方向分为nx个间距Δx,y方向分为ny个间距Δy,如图1所示。这时对算点位置可以用x和y方向的2个下标来表示。
二阶偏导数的差分可取作向前差分的向后差分[4,5],即:
将式(2)与式(3)代入式(1)就得到域中任意点(i,j)的差分方程如下:
为简单起见,只考虑第一类边界条件即强迫边界条件。边界上给定T值如图1所示。
1.2 稳态温度场迭代法求解
温度场导热问题的迭代法求解就是对所有内点(i=2,3,…,nx; j=2,3,…,ny)上的温度Ti,j进行扫描计算。可以利用前次迭代所得的邻点T值求得本次(第n+1次)点(i,j)的T值,在对点的扫描时按照(i=2,3,…,nx,(j=2,3,…,ny))顺序进行,在求点(i,j)第n+1次的温度值T
其中,Ri,j是方程的残差。
C是方程中T
根据松驰法的原理,可以把式(5)修正为:
其中ω是松驰因子。对超松驰法,1<ω<2时可加快收敛速度,对欠松驰法则0<ω<1。
2 稳态温度场的并行处理设计
本实验的运行环境是CPU结构的刀片服务器,使用适于集群环境的MPI并行库,对稳态温度场的迭代算法进行并行化处理。
2.1 并行计算及MPI简介
集群是最常见的并行计算环境,具有高性价比、高性能的优势。集群中相互独立的计算机就是集群的节点,节点既可以是一个单处理器系统,也可以是多处理器系统。
并行计算指将一个应用分解成多个子任务,分配给不同的处理器,各个处理器之间相互协同,并行地执行子任务,共同完成同一应用,从而达到加快求解速度,或者提高求解问题规模的目的。
MPI是一个广泛使用的消息传递接口标准,用于开发基于消息传递的并行程序,可以被Fortran、C++等调用,具有可移植性、灵活性、可靠性等优点。
2.2 并行设计
本文采用有限差分法实现并行化,设计方法是将整个计算域划分[6]为多个子域,把各子域上的迭代计算任务分配给相应的节点执行。并行设计过程中需要考虑的问题有计算域划分、计算域通信、计算次序等。
下面结合实现二维稳态温度场的迭代法并行求解过程,探讨和应用MPI的并行处理机制提高温度场的计算效率。
2.2.1 计算域划分
分析二维稳态温度场的串行算法,其中迭代运算是计算量最大的任务。考虑到各温度点在一个二维网格(亦称为计算域)中,将温度点以二维数组形式表示,采用计算域分解策略。有三种较为直接的分解方法:按列分解、按行分解和棋盒分解。如图2所示。
(1) 按列分解:
数据按列处理,各进程负责其中的若干列。有交叉列和连续列分解两种方式。使用交叉分解,各列之间的通信次数较多;而连续列分解(如图2(a)所示)可以有效地避免交叉分解出现的问题。
(2) 按行分解:
这种分解方式类似于按列分解。由于本程序用Fortran语言编写,而Fortran语言是按列存放数组的,因此每发送一行数据就要建立多次通信,通信时耗较长。故不适合本程序。
(3) 棋盒分解:
将基本任务规则地聚合成矩形块,并在进程与块之间建立对应关系。显然,如果某个方向的进程个数等于1,则二维块分解策略就退化为一维条分解策略。
考虑到各处理器的高利用率与处理器间通信最小化之间的平衡,在划分子域时尽可能使每个子域包含的网格算点数相等,保证进程间的负载平衡。
2.2.2 计算域通信
稳态导热问题迭代过程需要反复通信,为最小化通信时间,减少通信次数,本文使用广播、规约、数据散发与收集等聚合通信,并自定义MPI数据类型,将许多不同类型的数据合并起来传递。同时,本文采用重复非阻塞通信对反复执行的通信进行优化,实现通信与计算重叠,以降低不必要的通信开销。
2.2.3 计算次序
由于迭代计算时每个格点的计算都依赖于邻接的上下左右格点的温度值,因此每个子域的数据分为两部分:边界数据和内部数据[7],所以在子域的数据存储空间分配时应包括相邻子域中的边界数据。为减少等待时间以提高计算效率,先计算需要通信的边界数据的温度值,并通过MPI的通信机制发送给相邻子域的进程。在本子域进程等待接收相邻子域边界数据的同时,对内部数据完成迭代计算,从而实现计算和通信的重叠。边界数据接收结束后,一次迭代任务完成。接下来进行本子域的第二次迭代计算。
2.3 稳态温度场的并行算法实现
稳态温度场并行算法的程序流程如图3所示。
本程序使用笛卡尔拓扑结构表示进程在逻辑上的通信模型,并以此来描述及管理进程。图4为计算域A[1:256][1:256]划分为2×2时,分块数组与笛卡儿坐标的映射关系的示意图。
通过函数MPI_CART_CREATE创建进程分布的笛卡儿结构,获得笛卡儿拓扑的通信域;通过MPI_CART_COORDS将原来进程的编号转化为笛卡儿坐标;使用MPI_CART_SHIFT获得通信域中的某一笛卡儿坐标在某一方向的相邻的笛卡儿坐标值,从而便于与相邻的笛卡儿坐标通信。根据已创建的笛卡儿结构的相关信息,完成后续的迭代计算。笛卡儿结构中,进程被排列成二维网格形式的拓扑模型,使计算域能任意按行、按列、棋盒式进行分解,便于比较多种计算域划分后的并行运算结果,从而分析进程数和进程分布对程序运行时间的影响。
本程序使用重复非阻塞通信实现计算和通信的重叠,完成稳态温度场的迭代运算。迭代运算之前,通过函数MPI_SEND_INIT执行通信的初始化。循环体内部,先计算需要通信区域的温度值,然后通过MPI_STARTALL将所有的重复非阻塞通信对象激活,启动通信,接着计算非边界区域的温度值,调用函数MPI_WAITALL,完成通信。当完成指定次数的迭代计算,不需要再进行通信时,通过显式的语句MPI_REQUEST_FREE将非阻塞通信对象释放。
本程序采用多视口的方法实现并行读写文件[8]。通过函数MPI_FILE_SET_VIEW设置文件视图,产生以某一偏移量为起始位置的文件数据。通过函数MPI_FILE_SEEK将文件指针移动到指定的位置,最后使用组调用MPI_FILE_WRITE_ ALL,所有进程将迭代结果写入文件。
2.4 并行性能的评价
对并行程序并行性能的评估,最常用的是加速比和并行效率[9]。
假设某个串行程序在并行计算机的单个处理器上运行的时间为Ts,将该程序并行化后,在P个处理器上并行运行的时间为Tp,则该并行程序在该并行计算机上的加速比可定义为:
SP=Ts/ Tp
效率可定义为:
EP= SP / P
其中,在P个处理器上并行运行的时间Tp由P个进程中运行最慢的进程决定,则负载是否分配平衡,直接会影响加速比的大小。
加速比越大,说明程序运行时间越短;效率越大,说明性价比越高。综合考虑运行时间和性价比,选择合适实际条件的并行方案。
3 并行计算结果分析和性能评价
3.1 并行计算环境
本程序使用的集群环境是由两个曙光TC2600刀片服务器组成,每片配置2个CPU(5620MHz)。并行软件包是MPICH 2-1.3.1,使用Intel Visual Fortran Compiler作为Fortran的编译器,操作系统是Redhat 5。
3.2 结果与分析
本实验中,将计算域划分为N×N的网格,并设定左、下边界温度为0,右、上边界为1,内部网格温度初值均为0。
本实验对稳态温度场实现并行处理,同时与串行运算的结果进行比较。串行和并行处理得到的结果图像完全一致,但处理时间有较大的差异。图5为将宽×高尺寸为1×1的网格分解为100×100的计算域,串并行算法运行结果的图形显示。
当稳态温度场的问题规模较小时,如网格规模为(100×100),串并行运行时间统计如表1所示。通过比较可以看出:在该实验集群环境下,串行算法的效率高于并行算法。这是因为该实验计算规模小,使得并行所带来的性能效益较低,通信耗时相对于计算时间而言比较长。
由表1可以得出,当网格规模较小时,进程间的通信时间大于计算的时间,由此就出现了使用并行计算却比串行运算花费更多的时间。而随着网格规模的不断增大,如计算规模为(600×600)时,串并行运行时间如表2所示。由表中数据我们可以看出:① 当数据规模相对较大时,并行运算可以显著缩短程序运行时间,提高运算效率;② 并行算法的运行时间随着进程数的改变而变。当进程数较少时,通信时间较短,计算时间占主导因素,因此随着进程数的增多,并行算法运行时间减少;当进程数较多时,通信时间较长,成为影响程序运行时间的主要因素。
除此之外,进程分布也会影响程序的运行时间。进程数相同但进程分布不同时,程序运行时间不同。如表2中,进程分布为1×4的运行时间大于进程分布为2×2。但在表1中,进程分布为1×4的运行时间小于进程分布为2×2。这是由于计算域按列划分为1×4时,只需要左右通信,而计算域划分为2×2时,需要左右通信,还需要上下通信。当网格规模较小时,进程分布为1×4的程序,通信次数少,运行时间短;当网格规模较大时,进程分布为1×4的程序,虽然通信次数少,但是边界数据多,通信量大,运行时间长。
稳态温度场并行化处理时间(迭代10万次)的对比情况如图6所示。
图6中描述了串行、进程分布为1×2、进程分布为1×4的运行时间随网格规模变化的示意图。由图6可知,① 当进程分布不变时,随着网格规模不断增大,程序的运行时间不断增长;② 随着网格规模的增大,串并行程序运行时间差距越来越大,并行算法的优势愈加明显。
4 结 语
本文在实现并行方法和提高并行算法效率的一些措施的基础上,使用静态负载平衡的策略,成功实现了导热问题的并行计算。通过对实验结果的分析可知,进程分布会影响程序的运行时间。当网格规模较小时,使用按列分解,有助于缩短程序运行时间;反之,使用棋盒分解。此外,进程之间的通信耗时是影响并行效率的主要原因。因此在设计并行算法时,要同时考虑网络规模和进程分布,并在进程设计时应尽量加大计算耗时与通信耗时的比值,该比值越大,并行效率越高。
参考文献
[1]孙晗琦.并行计算在计算流体力学中的研究[D].大连理工大学,2005.
[2]周亚,蒋慕蓉.基于PVM的并行编程技术及其对温度场的可视化[J].云南大学学报,2007,29(3):251-255.
[3]赵建华,胡黎辉,秦树人.MPI并行计算在金属凝固温度场模拟中的实现[J].铸造,2007(7):708-711.
[4]王伟,潘建伟.有限差分法的并行化计算实现[J].微型电脑应用,2008,24(5):62-64.
[5]张维儒,潘无名.基于MPI的并行计算实现Jacobi迭代[J].软件导刊,2008(9):16-17.
[6]周灿.基于MPI的矩阵运算并行算法研究[D].重庆大学,2010.
[7]都志辉.高性能计算之并行编程技术——MPI并行程序设计[M].北京:清华大学出版社,2001.
[8]李小卫,罗省贤.基于MPI的并行I/O方法[J].微型机与应用,2003(3):13-14.
基于MPI 篇6
1 CSAMT二维正演及反演
1.1 二维正演数值模拟
本文在进行二维正演模拟时建立如下模型,场源放置在坐标原点,构造走向方向y轴,电性参数沿构造走向方向不变,仅在x-z平面中变化。
我们取电磁场随时间变化的因子为eiωt,忽略位移电流影响的时候[6],二次场满足的麦克斯韦方程组为
图1二维正演模型Fig.1 2D Model
式中,ω为角频率;μ0为真空中磁导率;σ为二维电导率;Δσ为异常电导率;σ0为背景电导率;Δσ=σ-σ0。沿y方向利用傅里叶变换公式为
从频率空间域过渡到频率波数域得
解方程组得
和
式(7)~式(10)为波数域中的二次场的计算公式。其中,为阻抗率;为导纳率;ke2=ky2=k2,k2=-iωμ0σ。将式(8)、式(10)带入(4)得
式(11)和式(12)为正演计算所要求的电磁场偏微分方程组[7,8,9]。通过解方程组可求得电磁场分量各方向的二次场。通过有限差分形成的矩阵方程为[10,11]
式(13)中,k为系数矩阵[12];Eys和Hys为二次场值;其余各参数为
给出一次场的值,即可求解方程(13)。
1.2 数据空间occam反演理论
数据空间OCCAM反演方法通过数学公式将模型迭代序列的计算从模型空间(M×M)转化到数据空间形式(N×N),达到减少计算量(weerachai siripunvaraporn,2000)[13,14]和提高计算效率的目的。OCCAM反演目标函数为
式(16)中,m为模型向量;d为观测数据;F[m]为正演数据;Cm为协方差矩阵;Cd是数据方差矩阵;λ为拉格朗日乘子[15—18]。用泰勒级数进一步推导可得
式(17)中,Jk为N×M的雅克比矩阵;为
为了使目标函数最小,对目标函数求偏导,且令偏导为0,得
令Xk=d-F[mk]+Jk(mk-m0),Γkm=JkTCd-1Jk为M×M矩阵,则
对式(21)通过一系列数学变换,得
于是
式中
将式(23)带入式(17)得到数据空间occam目标函数的表达式
式(25)中数据空间叉积矩阵Γkn=JkCm-1JkT,是一个N×N的半对称正定阵。通过这些变换,将模型空间数据转换为数据空间数据。在数据空间反演中仅需解N×N阶的方程,在实际应用中观测数据的个数要远小于模型数据的个数,所以数据空间反演中的计算量要远小于模型空间中的计算量[19]。
2 CSAMT的MPI并行反演算法
2.1 MPI并行计算
通过MPI实现了数据的广播[20,21,22]、发送、接收和数据的同步。MPI也支持多种数剧类型,包括复数。虽然看起来MPI的程序是一套程序,但是可以通过进程ID号进行区分,各进程可分配不同的计算任务。
MPI程序中,所有的变量(包括全局变量和局部变量)和函数,只要没有明确的区分,那么每个进程都享有这个变量和函数,这些变量对各进程来说名字是相同的,但是装载的信息很可能不相同,各进程若想了解其他进程的数据须进行通信。同时,对于alloctable的数据类型来说,每个进程可以为指针分配大小不一的内存空间。特别是MPI应用在频率域的时候,每个进程分配的任务很可能不完全相同,那么就需要灵活的分配空间[23,24,25]。
2.2 CSAMT的MPI并行反演算法
通过对CSAMT数据空间OCCAM反演算法研究后,发现在进行二维反演计算的过程中,根据频率的变化进行循环,求解雅克比矩阵和视电阻率消耗了大部分时间,占用总计算时间的90%以上,这个环节是进行并行化的首要部分。搜索λ值时根据不同的频率求解视电阻率,对于给定的不同频率值,在求取视电阻率的过程中,各个环节不需要交互数据,可独立自主地执行运算任务,根据二维反演程序的上述特性,可以将算法通过不同的频率进行分配,将若干个频率对应的计算任务分配到若干个进程上同时进行计算,通过对任务进行分配,每个进程需要执行的任务和顺序执行时间相比变少了。
图2为CSAMT数据空间OCCAM反演MPI并行的流程图。程序使用了10个频率。各个进程都被分配了计算任务,但是进程中有一个进程作为管理进程来分配任务。在并行程序里,将0进程设为管理进程,0进程负责读取参数文件,向各个计算进程分配计算任务,将读取的参数广播到其他进程,回收各进程的计算结果并广播给各进程以及将计算结果输出到文件。计算进程从管理进程那里接收参数,执行分配任务的计算,并将计算结果发回管理进程。同时管理进程也作为计算进程,参与计算相应的分配任务,以合理使用管理进程。二维正反演并行计算按下列步骤进行。
(1)初始化并行环境MPI_INIT(),主进程读入所有频率值和模型网格剖分数据和观测数据,MPI_Bcast()将其广播给所有子进程。其中,模型部分数据全部使用背景电阻率作为初始模型。
(2)主从进程按照分配的频率(表1),同时各自独立计算,通过第一次正演求解观测点的视电阻率ρa和雅克比矩阵,所有进程按频率计算完后,利用函数MPI_Gatherv()让主进程收集所有进程的视电阻率ρa,雅克比矩阵记录了10个频率所产生的视电阻率值和雅克比矩阵值。还需对这些值进行排序得到视电阻率ρa。雅克比矩阵主进程完成上述操作后,MPI_Bcast()将视电阻率ρa和雅克比矩阵广播给所有子进程。
(3)通过计算目标函数,主进程可得到拟合差rms,若rms<1,则循环中止,转到第(3)步,否则程序求取Xk=d-F[mk]+Jk(mk-m0)和Γkn=JkCm-1JkT,分别通过λa、λx、λb更新了三套模型,每套模型主从进程按照分配的频率同时各自独立的计算视电阻率ρa,待所有进程完成求解视电阻率ρa后,主进程收集所有进程的视电阻率ρa数据,视电阻率ρa记录了根据10个频率计算出的FFC,还需对视电阻率ρa进行排序。MPI_Bcast()将视电阻率ρa广播给所有子进程。得到视电阻率ρa后可计算拟合差以选取合适的λ值,得到λ值后,可对模型更新,程序转到第(2)步。
(4)达到循环中止条件后,主进程将视阻率和相位输出,MPI_FINALIZE()结束并行环境。
3 算例分析
3.1 模型
低阻模型,异常体顶面埋深50 m,大小为80 m×200 m。背景电阻率为100Ω·m,异常体电阻率为10Ω·m。模型网格为63×37,数据采集点为地表28~53点处。10个频率为1 000.000,464.160,215.440,100.000,46.416,21.544,10.000,4.642,2.154,1.000 Hz。X、Z方向剖分网格单元数:横向(x)63纵向(z)37。模型如图3。
3.2 正演及反演结果对比
通过并行计算得到的TM模式频率为1 000 Hz时,与串行结果正演效果对比(视电阻率)如图4所示。
图4中,频率为1 000 Hz,横轴为测点的位置,纵轴为正演视电阻率取对数,MPI并行算法计算的结果用+表示,串行计算的结果用o表示,计算结果完全重合。
通过并行计算得到的TM模式反演效果如图5所示。
色棒的取值为视电阻率取对数,背景视电阻率为100Ω·m,取对数为2,异常体视电阻率为10Ω·m,取对数为1,通过图4可看出程序较好地恢复了异常体的位置。
3.3 程序正确性验证及效率分析
根据各频率的计算是独立的特点,本文的并行计算是将多个频率的计算任务分配给多个进程并行处理,各进程的计算过程与顺序执行时计算过程是相同的,因此,计算结果应与串行计算结果相同,从而验证并行程序的正确性。图5是CSAMT数据空间occam反演并行程序TM模式反演出来的视电阻率断面图,通过这张图,看到了恢复的目标体及初始模型的位置与视电阻率基本一致,证明了程序的运行结果是正确的。同时,也用串行程序的反演结果图进行对比,也证明了并行程序的结果正确。
以并行效率对表2进行分析,当使用2个进程计算时并行效率最高;当进程数为5时,加速比有较大的提高,并行效率略有下降,这是因为当节点数增加时,进程通信会占用一定的时间。从表2可以看出并行计算的效果还是比较明显的,采用5进程计算时比顺序计算少用了约17.5 h。
4 结论
基于MPI 篇7
随着近年来互联网信息技术以及社会化发展进程的加快，互联网数据信息的数量级急剧增长，互联网的核心部分已不再是服务器，而更加注重它的存储系统。与此同时，随着高速网络技术、数据库处理技术、智能计算等技术的快速发展以及彼此之间的渗透结合，带来了数据存储领域新的研究及应用领域，这就为研究和应用新的存储技术奠定了坚实的基础。基于这样的事实，开发基于并行计算的分布式数据存储系统是可能的。本文主要讨论并行计算、分布式存储系统、基于消息传递编程接口（MessagePassing Interface,MPI）并行计算在分布式存储系统中的应用及实现过程。
1 并行计算
并行计算，就是在并行计算机上所作的计算。所有并行算法的设计都依赖于某种特定的并行计算的系统模型，而且建立并行计算模型需要依赖于具体的并行机，它可以在某种程度上表达出具体并行机的特性，同时也可以让算法的研究及应用具有较强的适应性，不受限于具体的并行机。并行算法的设计过程可分为任务划分、通信分析、任务组合和处理器映射四个步骤。在这个过程中，首先要实现算法的并发性以及扩展性；然后优化并行算法的通信成本以及执行时间，从而实现一个满意的设计思路；最后一步是实现映射，把经过优化处理后的多个进程分派到多个具体的处理器执行处理。
2 分布式存储系统
分布式存储系统是把数据信息分散地存储到多台彼此独立的服务器设备上，通过采用多台服务器来降低整体系统的存储负载。它不但可以提高系统的可靠性、实用性和运行效率，而且具有较好的扩展性。基于分布式存储的大量信息并行处理机（Massively Parallel Processor,MPP）的意义会随着时间的变化而改变。按照当前的科学知识体系，它主要表示由成百上千以至于上万的处理器构成的大型计算机系统。MPP系统属于非远程存储访问（NoRemoteMemoryAccess,NORMA）模型机器。大部分的MPP都采用物理上分布的系统存储器，而且采用分布式的输入输出接口也比较多。目前MPP的公共系统结构如图1所示。其中的每一个节点都有一个或者多个处理器以及高速缓存（Processor/Cache,P/C）、一个局部的存储器（Memory,Mem），而磁盘及网络接口电路（Network Interface Circuitry,NIC）是可有可无的。它们均连向本地互连网络，节点间通过高速网络（High Speed Network,HSN）相连[1]。
3 并行计算在分布式存储系统中的应用
3.1 分布式存储系统中的并行编程模型
借助互联网把多个处理器链接在一起构成分布式存储系统。整个分布式存储系统的地址空间由每个处理器中独立的部存储器形成。地址空间的形成可以使用两种方法：统一编址和独立编址。统一编址方法使用相同的指令访问和管理远程存储器以及局部存储器，将系统中所有局部存储器作为一个整体进行集中编址[2]。独立编址方法主要借助于调用基于MPI的库函数来访问和管理远程存储器，对系统中的局部存储器进行单独编址。于是，产生了基于分布式存储系统的访问和管理的两种并行的算法编程模型：基于数据的编程模型和基于MPI的编程模型。基于数据的编程模型可以采用单指令、多数据流（Single Instruction Multiple Data,SIMD）实现，也可以采用单程序、多数据流（Single Program Multiple Data,SPMD）实现；基于MPI的编程模型可以采用SPMD实现，也可以多程序、多数据流（Multiple Program Multiple Data,MPMD）实现。一般来讲，在MIMD系统结构中，即可以实现基于数据并行的编程模型，也可以实现基于MPI的编程模型；而在SIMD系统结构中仅可实现基于数据并行的编程模型。
3.2 基于MPI的并行编程模型在分布式存储系统中的实现
MPI是由MPI委员会在一系列会议上逐渐产生的一个消息传递标准。这个标准可应用于并行计算机系统、机群系统和异构网络环境，能达到较高的数据传输速率[3]。基于MPI的并行编程主要应用于MPP以及工作站机群（Cluster of Workstations,COW）编程实现方法，各处理器之间的数据传送通过收发消息的方式实现。在这种方式中，每个进程都具有相互独立的地址空间，一个进程只能借助MPI来实现远程访问其它进程中的数据信息。由于系统开销比较大，所以MPI一般应用于大粒度及粗粒度并行系统的实现。而依据问题分解的方法，基于MPI的并行算法的开发与实现具有两种方式：基于域的分解方式，也就是把一个大的待求解问题域拆分为多个较小的问题域或子域，然后求解各个子域；函数分解法或者功能分解法，主要是指把一个待求解问题拆分为多个子问题，然后分别对子问题进行并行求解[4]。因此，对于这两种方法，对应着SPMD编程以及MPMD编程两种形式。SPMD模式把同一个程序算法复制到多个处理器上，不同的处理器存储不同的数据，系统中的处理器执行相同的算法程序，但是其中的数据信息是不一样的，所以基于域的分解思路开发的并行性程序都通过SPMD模式实现。使用SPMD模型设计基于MPI的程序算法的一般过程有三步：第一步是划分数据信息：需要兼顾系统负载的平衡，均衡系统的存储，尽量降低各个处理器间的通信频度；第二步是提高通信过程：要尽量提高并行计算性能和通信频度的比值，对于数据处理，需要采用长信息与短消息合并的方式来传递消息；第三步是全局性操作：整合各个处理器求解的局部结果以形成待求解问题的解。那么使用SPMD模型设计并实现算法有两种方法：主机-节点形式及无主机形式。主机-节点型结构的应用程序包括主机程序和节点程序两个部分。主机程序运行在该结构的最上方，其下方是节点程序，节点程序的下方是其对应的计算节点。主机程序可以把数据信息传送到各个节点处理器上，并采集处理结果；也可以请求并释放处理器，加载并执行节点程序；还可以进行系统输入输出处理并进行人机交互。节点程序可以利用从主机接收到的数据信息执行各个处理器的独立计算，同时也可以实现各个计算节点之间的通信，并将返回值回传给主机[5]。基于主机-节点型系统结构的优势主要有两点：一是并行编程的实现简单：在实现串行程序到基于主机-节点型的并行算法程序的转换时，对于原有算法程序的输入输出模块以及人机交互模块无需更改，需要将计算部分转换为并行的特性即可，这样可以降低并行程序的开发成本；二是可以充分发挥主机的系统性能：大部分MPP系统中的计算节点都具备简单的操作系统功能，比如图形图像处理、输入输出接口及数据库访问接口的功能等，但是都比较简单，因此对于需要用到图形图像处理功能或者数据库访问接口功能的应用系统来说，可以使用基于主机-节点型系统结构。在无主机的系统结构中，一个系统应用程序全部在计算节点上方运行，其中控制节点主要用于执行通用输入输出服务模块程序，提供各个计算节点不具备的操作系统请求服务及输入输出接口服务。当然，在这种系统结构中，计算节点运行于程序控制模块的下方。它的优势主要有三点：一是由于计算节点处于程序的下方，程序调试采用标准的输入输出模块功能即可实现，所以程序调试简单；二是在无主机的系统结构上实现的并行程序与系统硬件不相关，简单修改或者不需要修改就可以运行在串行机上，所以程序不易出错，移植简单；三是系统中只有一种节点，用户只需实现一种应用程序即可，所以程序开发、维护简单。考虑以上原因，无主机系统成为当前实现SPMD并行程序的基本方法。在基于MPI的并行编程中，使用标准串行语言源代码和用于消息收发的库函数调用进程执行的程序，程序在初始化时生成进程，且一个处理器只生成一个进程，由一个或多个调用库函数[6]进行消息收发通信的进程组成了计算。进程间的通信可以在群体间进行，也可以点到点进行[7,8]。
4 结论
分布存储系统的并行编程模型有两种，即数据并行模型以及MPI模型。本文在介绍了分布式存储系统、并行计算理论的基础上，选择了基于MPI的并行编程模型对分布式存储系统的并行计算进行了详细的分析和论述，较好地论证了并行计算在分布式系统设计中的重要意义以及实现过程，取得了预期的研究成果。
对分布式的并行数据存储系统而言，它拥有较多的优势：数据信息的管理效率较高、可靠性高、可用性好、实现经费低廉、可扩展性强，这些对于社会信息化的发展具有重要意义。基于并行计算的分布式数据存储系统，主要针对网络数据及信息实行高效的、合理的组织，通过采用分布式的系统结构来进行存储及管理，目的就是为了保障数据信息的可靠性以及可用性，从而更好地为用户提供并行的数据信息检索以及知识抽取的便利，而最终的目标是实现为用户提供基于网络的数据信息系统的服务。基于并行计算的分布式网络数据存储系统是一种新技术，它主要以数据分布处理、并行数据处理、网络存储系统等技术作为研究基础。通过对这些现有的技术进行整合以及进一步地探索，实现一种全新的基于并行计算的网络数据存储系统。
摘要：海量的数据信息对WWW服务器的存储和检索系统提出了较高的要求,同时,互联网技术的发展为开发下一代适合高速发展的新的存储技术奠定了坚实的基础。为此,提出开发新一代基于消息传递编程接口的分布式网络数据存储系统。通过引入并行计算实现分布式存储系统的可靠性及可用性。
关键词：消息传递编程接口,并行计算,分布式存储系统
参考文献
[1]薛弘晔,李言俊,杜鸿.并行BSP模型在实时集群系统中的应用[J].计算机工程,2008,34(04):71-72.
[2]Nichol,Salz.An Analysis of Scatter Decomposition.IEEE Transactions on Computers,November 1990:1153-1161.
[3]张武生,薛巍,李建江等.MPI并行程序设计实例教程[M].北京:清华大学出版社.2009:25-30.
[4]蒋韵联,孙广中,许胤龙.并行异构系统中的一种高效任务调度算法[J].计算机工程,2007,33(11):39-41.
[5]梁强.复杂流场的非定常气动力计算以及气动弹性研究[D].西安:西北工业大学,2003.
[6]Kumar V,Gupta A,Gupta A et al.Introduction to Parallel Computing;Design and Analysis of Algorithms,Benjamin/CummingsPublishing Company,Inc.1994.
[7]祝永志,赵岩,魏榕晖.基于MPICH的Beowulf集群系统构建与性能评测[J].计算机工程与应用,2006,42(14):132-133.
基于MPI 篇8
在当前的集群通信应用中,普遍采用两类通信结构,即核心级通信和用户级通信。但由于它们设计的初衷并非是针对集群通信,所以并不适合当前集群环境的特点。为此,本文通过分析这两类通信结构的特点,提出了以核心级通信为基础,旁路内核中IP层及以上协议层,实现数据链路层直接与MPI通道接口层通信的新机制,并通过实验验证,为传统集群的升级改造提供一种新的无连接、无差错控制,开销小、延时低的通信机制。
1 基于数据链路层的集群通信结构的提出
目前各种通信协议普遍采用两种通信结构,即核心级通信和用户级通信[1]。
1.1 核心级通信
在核心级通信中,操作系统内核控制着所有消息传递中的发送与接收处理,并且负责它们的缓冲管理和通信协议的实现,设备驱动程序也是通过内核来完成所有的硬件支持与协议软件处理的任务,如图1所示。在通信过程中,系统要经过多次内核态与用户态之间的数据拷贝才能够实现数据的传送。有数据表明[2],一般奔腾处理器的内存拷贝速率平均为70 Mb/s,但是由于操作系统在交换页面时的I/O数据传送都是阻塞操作,若出现缺页中断,其时延将会更大,所以频繁的内存拷贝操作的开销将是影响整体性能的瓶颈所在。因此,对于通信效率要求较高的集群计算系统,核心级通信是不适合的。
1.2 用户级通信
在用户级通信中,操作系统内核将网络接口控制器NIC(Network Interface Controller)的寄存器和存储器映射到用户地址空间,允许用户进程旁路操作系统内核从直接访问NIC,直接将数据从用户空间发送到网络中进行传输。通信事件处理的触发采用查询方式而不是中断方式,由于旁路操作系统内核,使得整个通信过程省掉了执行系统调用、用户态与核心态之间的数据拷贝及用户与内核的上下文切换等软件上的开销,进而减少对主机CPU资源的占用,缩短通信操作的关键路径,实现通信与计算的重叠。如图2所示[3]。
但是,采用用户级通信协议时,通信过程中的所有操作均在用户空间中进行,当用户程序出错或有恶意用户进行破坏时,系统就很容易被破坏。这是因为系统数据结构中不仅包含本进程(或并行任务)及其相关信息,同时也包含与本进程无关的其他进程(或并行任务)的相关信息。若某一用户(并行任务)出错或失误,都将会影响到其他用户(并行任务)的执行,因而很难保证系统的安全性和可靠性,也无法保证并行任务间的相互独立性。
1.3 基于数据链路层通信
为了既能保证系统安全、可靠以及并行任务间相互独立,同时又能降低通信成本,本文提出了一种以核心级通信为基础的基于数据链路层的通信结构,即在操作系统内核(以Linux内核为例)中旁路IP层、INET Socke层和BSD Socket层,使得数据链路层直接与应用程序的通道接口层通信。如图3所示。
图3中阴影部分表示通信关键路径上数据链路层。在该通信结构下,系统在通信的关键路径上将通过内存映射和内存拷贝两种技术实现通信。在发送消息时,系统通过内存映射技术将消息映射到内核中的缓冲区,注册协议标识,并调用数据链路层函数对其进行封包发送;在接收消息时,系统通过数据链路层的MAC地址进行寻址、接收消息,并通过内存拷贝直接将消息传送到用户空间中的应用程序,实现点到点通信。
与用户级通信结构相比,基于数据链路层的通信结构在通信关键路径上只增加了一次内存拷贝的开销。同时,由于保留了数据链路层的通信,进而为系统的安全性、可靠性和并行任务间的独立性提供了保障。此外,该通信结构可以屏蔽系统的硬件信息,使得在应用程序中不再出现与系统通信硬件有关的操作。
与核心级通信结构相比,该通信结构在通信关键路径上减少了协议处理开销、数据拷贝次数和冗余的差错校验,进而提高了系统的通信效率。
2 MPI的通信
MPI(Message Passing Interface)是为基于消息传递的并行程序设计提供一个高效、可扩展、统一的编程环境,是目前主流的并行编程模式,也是分布式并行系统的主要编程环境。在集群环境中MPI并行程序设计中使用的通信模式有阻塞通信、非阻塞通信和组通信,其中阻塞通信和非阻塞通信属于点对点通信,而点对点通信也正是MPI其他通信的基础。
在阻塞通信中,当发送调用函数MPI_Send后即被阻塞,这时,系统会将发送缓冲区中的数据拷贝到系统缓冲区,由系统负责发送消息,而发送者的操作只在拷贝操作完成时结束并返回,不必等待发送完成。但是,如果系统缓冲区不足或消息过长,导致拷贝失败,则发送者将被阻塞,直到消息发送完成为止;同样,当接收者在调用函数MPI_Recv后会被阻塞,直至收到匹配的消息为止[3]。
非阻塞通信主要是通过实现计算与通信的重叠,进而提高整个程序的执行效率。对于非阻塞通信,不必等到通信操作完全结束后才可返回,而是由特定的通信硬件完成通信操作。在通信硬件执行通信操作的同时,处理机可以同时进行计算操作,这样便实现了通信与计算的重叠。发送者调用函数MPI_Isend或接收者调用数MPI_Irecv后,处理机便可执行其他计算任务。在发送(接收)操作开始时,发送者(接收者)使用请求句柄(request handler),MPI通过检查请求来决定发送(接收)操作是否完成,发送者(接收者)通过调用MPI_Test来确定发送(接收)操作是否完成。在发送或接收操作期间,发送者不能更改发送缓冲区中的内容,接收者也不能使用接收缓冲区中的内容。若发送者(接收者)调用函数MPI_Wait,则发送者(接收者)会被阻塞,直到发送(接收操作完成才能返回[4]。
由此可知,MPI点到点通信在发送缓冲区、接收缓冲区和内核中的系统缓冲区之间进行传递,并由内核发送或接收系统缓冲区中的消息,本文提出的新通信机制就是围绕着系统缓冲区展开的。
3 基于数据链路层的MPI通信机制的设计与实现
若要实现本文所提出的基于数据链路层的集群通信机制,则需要开发一个中间件DLMC(Data_link Layer MPI Communication)用于提供双方进行通信的底层交换协议、数据包校验、用户空间与内核空间的数据交换和重传机制等。这里需要注意的问题有:
(1)编译方式
对于Linux内核编译分为直接编译进内核和通过模块编译加载进内核。本系统采用模块加载的方式进行编译,其理由是由于系统是在传统Linux网络下进行的修改,只有MPI计算才会用到此中间件,而对于计算之外的部分仍然要依靠传统的TCP/IP。例如计算前期的准备工作,虽然模块加载比直接编译的效率低,但它可以随意动态加载和卸载,这样不仅灵活,而且有利于开发、调试等工作。
(2)用户空间和内核空间之间的数据交换
基于数据链路层的通信进程是在内核空间运行的,而MPI进程是在用户空间进行的,所以需要在用户空间和内核空间进行通信。通过利用Linux内核机制,在用户空间缓存页面以及物理页面之间建立映射关系,将物理内存映射到进程的地址空间,从而达到直接内存访问的目的。
在Linux中,对于高端物理内存(896 MB之后),并没有与内核地址空间建立对应的关系(即虚拟地址=物理地址+PAGE_OFFSET),所以不能使用诸如get_free_pages()函数进行内存分配,而必须使用alloc_pages()来得到struct*page结构,然后将其映射到内核地址空间,但此时映射后的地址并非和物理地址相差PAGE_OFFSET[5]。为实现内存映射技术,其具体使用方法是:使用alloc_pages()在高端存储器区得到struct*page结构,然后调用kmap(struct*page)在内核地址空间PAGE_OFFSET+896M之后的地址空间中建立永久映射。DLMC首先让内核得到用户空间中发送缓冲区的页信息,再将其映射到内核地址空间,并且返回内核虚拟地址,以供DLMC直接将发送缓冲区中的数据传递到数据链路层进行发送,这样就完成了用户地址空间到内核地址空间的映射。
(3)校验与重传机制
由于数据链路层的传输是一种不可靠的网络传输方式,涉及到对传输数据进行数据校验重传等工作。考虑到局域网或者机对机传输的稳定性和可靠性,系统校验方式使用简单的数据校验和,重传机制使用选择重传ARQ方案。当出现差错必须重传时,不必重复传送已经正确到达接收端的数据帧,而只重传出错的数据帧或计时器超时的数据帧,以避免网络资源的浪费。
(4)中断机制
由于本系统改变了TCP/IP的传输机制,所以需要对发出的数据包进行协议标识。系统在初始化阶段,调用内核的dev_add_pack()函数向内核注册了标识为Ox080A的网络数据处理函数。在发送数据包时,系统先通过kmap()函数将MPI的发送缓冲区sendbuff映射到内核映射缓冲区sysbuff,以软中断的方式通知系统,申请分配一个新的SKB来存储sysbuff里的数据包,调用dev_queue_xmit函数,使数据包向下层传递,并清空sysbuff,释放SKB。在接收端需要向内核注册相应的硬件中断处理函数,在接收到数据后唤醒上层的处理函数,并在netif_receive_skb函数(net/core/dev.c)中屏蔽将SKB包向上层传递的语句,改为将SKB里的数据以MPI数据包格式通过copy_to_user函数拷贝到MPI的接收缓冲区recvbuff中,完成数据的接收,其传输过程如图4所示。
4 实验结果与分析
4.1 实验结果和方法
本实验环境是一个4节点的Beowulf集群系统,每个节点包含一个PIV处理器和2 GB内存,操作系统采用Redhat Linux Enterprise 5,并行集群软件为OPEN MPI1.3。由于条件所限,加之实验规模较小,本实验采用MPI自带的函数MPI_Wtime()来采集MPI计算的开始时间和结束时间,取二者的时间差作为程序的运行时间并对其进行比较和分析。
由于本实验的目的是要测试基于数据链路层的通信机制的可行性,而该通信机制是在TCP/IP协议基础之上构建的,所以本实验对象将以单机系统、基于TCP/IP的MPI集群和基于DLMC的MPI集群作为参照平台进行测试。在实验用例设计上,考虑到两种MPI集群的通信机制中的传输路径不同,所以采用如下两种测试方案:
(1)计算圆周率,主要测试系统的数学函数浮点计算性能,以点对点短消息传输为主;
(2)计算求解三对角方程组,主要测试通信和计算的平衡,以点对点长消息传输为主。
4.2 性能分析
(1)计算圆周率,如表1所示。
测试结果表明,在精度值设为10-8,精确值比较大时,基于TCP/IP的集群(4个进程)的运行时间是19.540237 s,单机系统(单进程)运行时间是84.798 166 s,并行运算效果明显。在精度值设为10-4,精确值比较小时,基于TCP/IP的集群(4个进程)的运行时间是0.026 346 s,单机系统(单进程)运行时间是0.013 742 s,这是由于并行运算过程中,参与运算的机器需要通过网络传递消息,若计算量规模不大,则在网络传输上花费的时间会比较多,所以反不如单机的运行速度快。从基于DLMC的集群与基于TCP/IP的集群运行结果对比看,在精度值较大时,前者略微快于后者,而在精度值较小时,后者略快于前者,这主要是因为基于TCP/IP的MPI集群在发送和接收的整个过程中,需要2次数据拷贝,即发送缓冲区到内核的拷贝和内核到接收缓冲区的拷贝,同时还有经过各协议层的开销。而基于DLMC的MPI集群在整个的传输过程中,通过使用内存映射,只需要1次数据拷贝,同时旁路IP层及以上各协议层,在这种以短消息传输为主的测试中使得DLMC集群不能发挥其在网络传输上的优势,所以在精度值较大时,二者相差无几;在精度值较小时,反而基于TCP/IP的集群更快一些,这是因为内存映射和内核操作所引入的开销大于1次内存拷贝开销而造成性能的下降。
(2)计算求解三对角方程组,如表2所示。
由测试结果表明,在传输消息较小时,基于DLMC的MPI集群花费的时间略微小于基于TCP/IP的MPI集群,这说明此时基于内存映射和内核调用等操作的开销要高于两次数据拷贝的开销,造成网络延迟略高。但随着传输消息规模的增大,特别是消息大小超过1 MB时,基于内存映射和数据链路层协议的DLMC相对于具有2次内存拷贝的多协议机制的网络延时要小得多,这样使得系统的整体运行时间明显低于传统的TCP/IP集群。
(s)
由上分析可知,基于Linux数据链路层的集群通信机制是可行的。在该机制下构建的MPI集群系统完成了无IP条件下的数据传输,并且支持多用户调用,在传输过程中减少了协议开销、和内存拷贝次数,相比于TCP IP传输有一定提高。但是基于数据链路层协议的特点,该机制只能在局域网范围内运行,所以集群节点数量或规模会受到一定的限制,只能适合中小集群系统的应用。由于实验条件的有限,对集群通信系统未能充分验证,希望在今后的研发工作中能够进一步加强。
摘要：针对MPI集群通信的特点,通过分析当前网络的通信结构和MPI的点到点通信模式,提出了一种基于数据链路层的集群通信机制,用以减少协议开销和内存拷贝次数,从而提高集群节点间的通信性能,并且通过实验验证了该机制的可行性。
关键词：内存映射,数据链路层,内存拷贝
参考文献
[1]马捷.基于SMP结点的机群通信系统关键技术的研究[D].北京:中国科学院研究生院(计算技术研究所),2001.
[2]可向民,李正虎,夏建东.零拷贝技术及其实现的研究[J].计算机工程与科学,2000,22(5):17-24.
[3]刘路,谢旻,张磊,等.用户级通信中基于网络接口的虚实地址变换技术[J].计算机工程与科学,2008,(09):154-157.
[4]WILLIAM G,LUCK E,SKJELLUM A.Using MPI:portableparallel programming with the message passing interface[M].2nd Edition.Cambridge,MIT Press,1999.
[5]BUNTINAS D,GOGLIN B,GOODELL D,et al.Cache-efficient,intranode,large-message MPI communication withMPICH2-Nemesis[C].38th International Conference on Par-allel Processing(ICPP-2009).2009:462-469.