mpi并行研究个人笔记

1.摘要来源：MPI并行程序设计的负载平衡实现方法MPI是目前集群系统中最重要的并行编程工具,它采用消息传递的方式实现并行程序间通信。在MPI并行程序设计中实现负载平衡有着重要的意义,可以减少运行时间,提高MPI并行程序的性能。负载平衡又可分为静态负载平衡和动态负载平衡,对于静态负载平衡,提出了一种分配任务的算法,可有效地按照节点的计算能力,在节点间分配任务;对于动态负载平衡,提出了一种在MPI并行程序中实现的方法,可有效地根据节点的负载情况,在节点间迁移任务。2.并行计算应用的领域来源：MPI并行程序设计的负载平衡实现方法应用于航空航天、气象与天气预报、环境问题、材料科学、石油勘探等领域3.群系统的特点来源：MPI并行程序设计的负载平衡实现方法集群系统具有低成本、高性能的特性,提供了强大的并行计算能力和批处理能力4.并行程序的运行时间由运行时间来源：MPI并行程序设计的负载平衡实现方法一个并行程序通常由多个进程组成,通常一个计算节点上运行一个进程,这些进程可同时并行执行任务,并行程序的运行时间由运行时间最长的进程决定。5.负载平衡的定义来源：MPI并行程序设计的负载平衡实现方法负载平衡是指在各计算节点间均匀分配负载,以使得各个进程倾向于同时完成任务,从而减少进程的最长运行时间。6.负载平衡的意义来源：MPI并行程序设计的负载平衡实现方法在并行程序设计中实现负载平衡可有效减少并行程序的运行时间,提高并行程序的性能7.MPI简介来源：MPI并行程序设计的负载平衡实现方法MPI是目前集群系统中最重要的并行编程工具[4][5],它采用消息传递的方式实现并行程序间通信。MPI具有移植性好、功能强大、效率高等多种优点,而且有多种不同的免费、高效、实用的实现版本,常见的如MPICH、LAM、IBMMPL,几乎所有的并行计算机厂商都提供对MPI的支持,成为了事实上的并行编程标准。8.负载平衡的分类来源：MPI并行程序设计的负载平衡实现方法负载平衡又可分为静态负载平衡和动态负载平衡9.静态负载平衡的简介来源：MPI并行程序设计的负载平衡实现方法静态负载平衡是MPI并行程序实现负载平衡的基本方法,是指在MPI并行程序运行前如何在各个进程上分配任务,以期望每个进程尽量同时完成各自的任务,从而有效减少程序运行时间。一般来说,每个节点上都运行一个进程,静态负载平衡也就是如何在每个节点上分配任务。10.如何实现静态负载平衡来源：MPI并行程序设计的负载平衡实现方法可先计算出每个节点上需要分配的任务量,每个节点上分配的任务量应当正比于此节点的计算能力,这样每个节点期望于同时完成任务,从而最大限度地减少程序运行时间。节点i上应当分配的任务量为hi=(t1+t2+…+tm)/(f1+f2+…+fn)×fi,节点i上实际分配的任务量为ki,应使ki接近于hi,这是一个NP完全问题。（计算能力为f1,f2,…,fn,若f1=f2=…=fn,则这是一个同构集群系统,否则是一个异构集群系统）（t为估算任务量）11.实现静态负载平衡的具体算法来源：MPI并行程序设计的负载平衡实现方法我们给出了一个近似算法,设di=|ki-hi|,即di为节点i上的实际任务量与最优任务量之差,节点i上当前分配的任务集合为Ti。初始时节点0的任务集T0包含所有任务,即task1,task2,…,taskm,然后在节点间移动任务,使得各个节点的d值不断变小。任务移动的准则如下:1)若将Ti中的某一任务移到Tj中,使得di和dj都变小,则移动此任务;2)若将Ti中的某一任务和Tj中的某一任务交换,使得di和dj都变小,则交换任务;通过以上的任务移动准则,会得到一个最终的任务分配方案,各个节点的任务集合T即是此节点上需要运行的任务集合,在编写MPI并行程序时,就可指定对应进程需要运行的任务。12.静态负载平衡的缺陷来源：MPI并行程序设计的负载平衡实现方法在静态负载平衡中,通常对任务的任务量估算不准确,可能存在较大的差异,此外任务的运行时间并不严格正比于任务量与节点计算能力之比,可能无法准确知道节点的计算能力,节点的计算能力可能受到诸多方面的影响,如当前系统的可用内存、带宽、负荷、磁盘的读写能力等等,因此任务的运行时间是一个不确定的量。如果按照静态负载平衡方法来分配任务,可能任务的实际运行时间与估算值有较大的差异,每个节点完成各自任务所需的时间也就存在较大的差异13.动态负载平衡定义来源：MPI并行程序设计的负载平衡实现方法动态负载平衡是静态负载平衡的有效补充,是指在MPI并行程序运行过程中,根据各计算节点的当前负荷,在计算节点间动态迁移任务,将负载重的节点上的任务迁移到负载轻的节点上,尽量平衡各计算节点的负载,从而减少程序运行时间。14.动态负载平衡的优缺点来源：MPI并行程序设计的负载平衡实现方法相比静态负载平衡,动态负载平衡无需在MPI并行程序运行前知道任务的任务量和节点的计算能力,但动态负载平衡在实现上比较复杂,需要一些额外的通信代价。15.动态平衡需要解决的问题来源：MPI并行程序设计的负载平衡实现方法1)如何收集系统当前负载的信息;2)决定是否进行任务迁移以及向何处迁移;3)如何进行迁移。16.动态负载平衡方法来源：MPI并行程序设计的负载平衡实现方法1)信息收集:制定衡量节点负载信息的负载指标,以及信息收集的方式;2)迁移决策:基于任务和节点负载,判断是否要把一个任务迁移到其它计算节点上运行;3)迁移执行:对于适合迁移到其它计算节点上的任务,选择任务迁移的目的节点;17.动态平衡具体实现方法来源：MPI并行程序设计的负载平衡实现方法在MPI并行程序中,可以让编号为0的进程作为调度进程,其他进程作为计算进程。因为调度进程相对计算量较少,所以可以让调度进程与某个计算进程运行在同一个计算节点上。具体实现方法如下:1)每个计算进程在完成一个任务后,向调度进程发送消息,通知调度进程其剩余任务数。如果其剩余任务数不为0,则等待调度进程的消息,否则等待其他计算进程的任务迁移消息。2)调度进程接收计算进程的消息。如果此进程的剩余任务数为0,则登记此进程为空闲进程。如果此进程还剩下2个以上任务没完成,并且存在空闲进程,那么便向此进程发送某一空闲进程的编号,否则发送-1。3)计算进程接收调度进程发送过来的空闲进程编号,如果编号为-1,则继续执行,否则向此空闲进程发送任务迁移消息,将其剩余的一半任务迁移到此空闲进程上运行。4)如果所有计算进程都是空闲进程,则此并行程序结束。18.开展并行计算具备的条件来源：MPI并行计算性能的研究开展并行计算,必须具备以下条件:(1)并行计算机,并需包含多个处理器,且相互连接,相互协作.(2)应用问题一般具有并行度,可以分解为多个可并行执行的子任务.其将一个应用问题分解为多个子任务的过程称为并行算法.(3)可在并行编程环境下,实现并行算法并编写程序运行,从而实现并行求解的目的.19.并行系统性能指标来源：MPI并行计算性能的研究并行系统性能有两个主要的技术指标,即:并行加速比和并行效率.并行加速比是串行耗时除以该问题的并行求解的耗时.并行效率,即加速比除以并行求解时处理器的数20.MPi的缺陷来源：MPI并行计算性能的研究现有MIP支撑环境和技术,尚有许多不完善或急需进一步充实和发展的内容.其挑战性主要有以下一些方面:(l)程序的设计与编写.并行程序支持多个操作同时进行,所以能显著提高程序的性能,但由于并行软件各元素之间存在着复杂的交互,也使得程序行为变的更加复杂,因此需要更加深人的思考才能正确驾驭,对这些同时发生的操作以及它们之间的交互必须进行很好的管理.(2)调试.除具有串行程序调试所具有的困难之外,还有一些新的较大的困难.首先,并行软件各元素之间存在着复杂的交互,这可能会引人新的BUG,这些BUG难以发现并定位,消除这些BUG非常耗时而且十分乏味,程序员被迫需要长时间跟踪软件元素的交互行为来确定这个逻辑错误的根源.其次,现在还没有有效的调试工具可利用,只能依靠程序员的个人经验进行试探性的调试,具有相当难度.(3)性能和移植.并行系统的性能对程序的微小变化非常敏感.并行程序中还存在潜在的问题,例如负载平衡、数据的局部性、输人输出问题.所有这些问题都使得并行程序的开发和调试变得非常复杂,而且经常与直觉相21.甲壳比迭代并行算法的问题来源：MPI并行计算性能的研究22.二维快速傅里叶变换的并行算法缺陷来源：MPI并行计算性能的研究二维快速傅里叶变换(FFT)的并行计算二维傅里叶变换,就是进行两次一维FFT计算,即首先进行行变换,然后再对行变换的结果进行列变换.并行实现快速傅里叶变换算法的思路就是把行变换和列变换的计算任务分配到各个节点并行完成.并行傅里叶变换的过程为:各节点进行行变换~各节点把行变换的结果发送给根进程~根进程对行变换结果进行转置运算~根进程把转置结果发送到所有计算节点~各计算节点再进行行变换~各节点把变换结果发送到根进程~根进程进行转置~得到最后结果.各节点之间计算要求同步而需要大量的通信传输数据,该算法并行计算的计算通信比小.由于在局域网上通信数据传输相对于计算来说是很耗时的,这就造成了负的效应即加速比小于1的情况,并行效率很低.很明显这类问题一般不适合在机群的网络下进行并行计算测试结果如图23.fft加速比来源：MPI并行计算性能的研究24.发展方向来源：MPI并行计算性能的研究在现有一般网络情况下,节点之间的通信耗时,是影响并行计算加速比和并行效率的主要原因,应尽量加大计算耗时与通信耗时的比值,一般认为该比值小于1时的,算法就不适于并行计算.但应注意到,通信耗时与计算机存储带宽、1/0带宽、网路通信协议、体系结构和介质传输速度等都有关,这可通过诸如并行存储、宽带网络及新的网络协议等来改善和解决.利用MIP并行计算有利于充分发掘多核处理器PC机的计算潜力和效力,其最有效的算例证明,可接近于处理器个数的倍数,即串行计算编程时,它仅利用了其多核单机的1(/处理器个数)的效力.另外,多核单机的通信传输也比网络环境效,因此对于组建工程应用系统作数据处理更紧凑有