《并行LU分解的在通信中的应用.docx》由会员分享，可在线阅读，更多相关《并行LU分解的在通信中的应用.docx（13页珍藏版）》请在课桌文档上搜索。
1、并行LU分解的在通信中的应用摘要:本文主要表达了并行LU分解在WDM环网上的波长分配算法中的应用和容错并行算法设计与实现的应用，波长分配是光网络设计的根本问题,设计波长分配算法是洞察光网络通信能力的根本方法。不同的并行算法具有不同的通信模式,如何在光互连网上实现这些通信模式,是当前一个颇受关注的研究领域。基于WDM环网络,针对矩阵的并行LU分解,构造了一种并行LU分解的通信模式,讨论了将该通信模式嵌入在环形光网络中的波长分配问题。在解决该问题的过程中,得到了将一种特殊的二分图结构的通信模式嵌入在环网中的波长分配算法。通过分析和证明得到了在WDM环网上实现该并行LU分解通信模式所需的最小波长数。
2、给出了容错并行算法的定义，提出了一种新的基于并行复算的容错并行算法。针对许多计算密集型任务中的矩阵LU分解设计了相应的基于并行复算的容错并行算法，并对设计的矩阵LU分解的容错并行算法的性能进行了评估并与CheCkPointing方法进行了比照。结果说明与CheCkPointing方法相比，矩阵LU分解的容错并行算法有性能上的优势。关键词:LU分解;波长分配;WDM环;网络嵌入;并行处理;容错Abstract:ThispapermainlydescribestheapplicationOfparallelLudecompositionandfaulttoleranceandwavelengtha
3、ssignmentalgorithmintheWDMloopnetworkinparallelapplicationalgorithmdesignandimplementation,wavelengthassignmentisabasicprobleminopticalnetworkdesign,thedesignOfwavelengthassignmentalgorithmisthebasicmethodOfinsightintotheopticalnetworkcommunicationability.Differentparallelalgorithmshavedifferentmode
4、sofcommunication,howtorealizethesecom-municationpatternsonopticalinterconnectionnetworksisahotre-searchfield.BasedontheWDMringnetwork,accordingtothepara-IIeILudecompositionofmatrix,constructsaparallelLUcommuni-cationmodedecomposition,discussesthewavelengthassignmentproblemthatthecommunicationmodelse
5、mbeddedintheopticalringnetwork.Intheprocessofsolvingthisproblem,getthewavelengtha-Ssignmentalgorithmembeddedcommunicationmodeofaspecialtwopartedgraphstructureinringnetwork.ThroughtheanalysisandtheproofobtainedintheWDMringetworktorealizetheparallelminima-mwavelengthofLudecompositionofthenumberofrequi
6、redcommu-icationmode.Givesthedefinitionoffault-tolerantparallelalgorith-m,presentsanewparallelalgorithmbasedonfaulttolerantparallelrecomputing.AccordingtothematrixLUmanycomputationallyinten-sivetaskdecompositiontodesignthecorrespondingparallelalgorith-msforfault-tolerantparallelrecomputingbasedfault
7、toleranceandperformanceonthedecompositionofmatrixLUdesignparallelalgorithmwasevaluatedandcomparedwiththecheckpointingmethod.Theres-ultsshowthatcomparedwithcheck-pointingmethod,thefault-toler-antmatrixLUdecompositionparallelalgorithmhasaperformanceadvantage.KeyWord:LUdecomposition;avelengthassignment
8、;WDMring;networkembedding;parallelprocessing;faulttolerance一、LU并行分解在WDM环网上波长算法中的应用1LU并行分解在WDM环网上波长算法中为什么能得到广泛应用线性方程组的求解问题是很多科学和工程领域的根本重要问题,其中矩阵的LU分解是最根本和常用的.在很多科学计算领域中,求解大规模的线性方程组成为计算的瓶颈,通常采用并行处理来提高计算的速度.互连网络是并行计算机的关键部件,其效率直接影响到并行计算机的性能.而采用波分复用(WavelengthDiViSiOnMUItiPleXing,简称WDM)的全光网是互连网络的一个重要研究方向
9、,利用全光互连网络具有高宽带、低延迟等优点来进一步提高大规模并行数值计算的速度有着巨大的潜力.目前,在一条物理连接上,实验室技术可以复用100个左右的虚拟通道,每个虚拟通道使用不同的波长.随着技术的开展,可复用的波长数会逐渐增加.如何高效地利用这些波长,是光互连网络研究的一个重要问题。互连网络有各种各样的通信模式,通过分析各种通信模式对波长的需求,洞察互连网络的能力是分析网络的一种行之有效的方法.环形网络是实际中广泛采用的一类拓扑结构,其上的波长分配问题具有重要的实用价值.在这方面,不少人作过研究:文献讨论了在WDM环网络上的波长分配问题;文献4将Hypercube通信模式嵌入到环,研究了其最
10、大波长需求问题;文献讨论了在光RP(k)网络上实现HyPer-CUbe通信模式的波长分配问题,同时得到了在环网络上实现n维HyPerCUbe通信模式的波长分配算法,并改良了文献中的结论.本文针对矩阵的并行LU分解,首先构造了一种并行LU分解的通信模式,然后讨论了将这种并行LU分解的通信模式嵌入在环形光通信网络中的波长分配问题,最后给出了在WDM环网络上实现并行LU分解的最小波长数的结论.2根本概念为了分析方便,下面我们先给出有关的根本概念和根底知识。2.1WDM光互连网络WDM光互连光网络提供一个诱人的特点,那就是波长路由,波长路由网络是通过光通道来实现通信的,光通道是网络节点之间的全光通信信
11、道,可以跨越多个光链路.波长路由网络的根本要求是同一光纤链路上的不同光通道必须具有不同波长，以免通道间互相干扰.光通道可以划分为波长通道(WP:WavelengthPath)和虚波长通道(VWP:VirtualWavelengthPath)两种结构.波长通道网络满足波长连续性要求,即一条光通道从输入端口到输出端口所经过的物理链路分配的波长应该相同;虚波长通道网络的交换节点处具有波长转换功能,即一条光通道在通过光网络过程中,可以分配不同的波长.在没有波长转换器的WDM网络中,路由实现方式属于波长通道,后面的讨论都基于波长通道方式。2.2波长分配在光网络上,已给一个通信模式,如何实现路由及分配通道
12、是一个重要的研究问题,称为波长分配问题(RCA)。RCA问题可以描述为：给定一个通信集合C=(x,y)x向y传送信息,要完成如下的分配任务：(1)为每一个通信(x,y)分配一条由X到y的路径,在该路径上指定一个波长；以上的波长分配满足:如果在某一物理连接上有多条路径经过,那么它们使用互不相同的波长；分配的目标是最小化指定的波长数.很多文献讨论了RCA问题4,7,本文基于WDM环网络，讨论实现并行LU分解通信模式的波长分配问题.3并行LU分解的通信模式在许多应用问题的科学计算中,矩阵的LU分解是最根本和常用的,它是求解三角形线性系的根底.LU分解法求解线性方程组Ax=b分为三步：(1)将矩阵A分
13、解为一个单位下三角矩阵L和一个单位上三角矩阵U,那么有LUX=b;令Y=UX,求解Ly=b;(3)求解Ux=y.其中,有效的LU分解是最复杂也是最关键的一步.LU分解的递推公式为：那么下面的一段代码表示第k步LU分解时调整矩阵元素值暂不考虑选主元),该段代码具有良好的并行特征：DOk=l,n-lA(k+1:n,k)=A(k+1:n,k)/A(k,k)!ColumnNormalizationFORALL(i=k1:n,j=k+1:n)A(i,j)=A(iJ)-A(i,k)*A(k,j)ENDFORALL!Sub-matrixMOdificationENDDO并行LU分解的首要问题是矩阵数据的划分
14、问题.循环块数据分布方式8是一种经常采用的矩阵划分方式,对于给定E=PXQ个处理机、MXN的矩阵AMN,将矩阵的元素分块,分块大小为rXs,以循环块分布的形式分别存放到PXQ的处理机上.假设矩阵A的元素A(i,j)被分配在处理机E(p,q)上,那么P二(is)modP,q=(jt)modQ.假设PXQ=4X4=16个处理机,每个处理机用(p,q)唯一地标识,MXN=1010,rs=1X3.那么矩阵元素的分布情况如图1(a)所示,矩阵元素上的标号表示该元素被分配在处理机E(p,q)上。分析进行一步LU分解的通信情况,可知在第k步LU分解过程中,假设矩阵元素Aik或Akj所在的块被分配在处理机s上
15、,矩阵元素Aij所在的块被分配在处理机d上,那么处理机s和d之间存在通信,否那么不存在通信.图1(b)为进行第k步LU分解的示意图。基于循环块数据分布方式,对并行LU分解的过程以及通信状况进行分析,将处理机抽象为通信模式中的节点,通信请求抽象为通信模式中的边,由于循环块数据分布方式尽量保证处理机之间的负载平衡,并且每一步LU分解具有相似的通信模式,可用如图2(a)表示。更一般地,将规模较大的矩阵采用循环块数据分布方式分配给nn=n2(n22)个处理机,每个处理机用(i,j)唯一地标识,其中OWi,jWnl,处理机(0,0)记为m,处理机(0,i)记为ci,处理机(i,0)记为ri,处理机(i,
16、j)记为vij(lin-l,1jnJ).那么上述并行LU分解通信模式可用有向图Gn(Vn,En)表示,节点集合Vn和边集合En可如下所示：为简便,后面我们将该通信模式简称为PLU通信模式。分析PLU通信模式有如下性质：性质1不考虑边的方向时,Gn中的边(mo,c,)(ci,v)(n,v11)(mo,好)在图Gn中构成回路,图Gn中这样的回路共n-1个(1Wi(Ci,Yu)(ri,Vii)、(mo,彩)(IWiWn-I)在图Gl中构成n-1条回路.易知,在环上实现每一条回路所需的波长数最少为L当且仅当回路上的4条光路不共享任何一条物理链路且它们经过环上所有物理链路.因此,将子图Gl嵌入在WDM环
17、网络中所需的最小波长数为n-1o4.2 PLU通信模式的化简由性质2知,子图G2中的节点Vij度为2,构造和图G2同胚的图G3(V3,E3),即对于连接一个度数为2的两条边,去掉这个点,使两条边收缩为一条边.如图2(d)是n=4时G2的化简图.易知,所得到的图G3(V3,E3)恰好是一个二分图.引理2将图G3嵌入环网络所需的最小波长数与图G2嵌入环网络所需的最小波长数相等。可以证明,将图G3嵌入环网络所需的最小波长数不会小于图G2嵌入环网络所需的最小波长数，当G2中光路(ri,vij)和(cj,vij)不共享任何物理链路且分配相同的的波长时,图G2嵌入环网络所需的最小波长数与G3嵌入环网络所需
18、的最小波长数相等.经过上述的PLU通信模式的分解和化简,我们得到以下结论：定理1在WDM环上实现PLU通信模式所需的最小波长数WPLU(n)=WG3(n-1)+(n1),其中WG3(n1)是图G3嵌入环网络所需的最小波长数。证明:由引理1,假设对Gi中的n-1条回路分配波长集合人=入12、入nl,那么该波长集合中的波长通道在每条物理链路上都被占用,图G2中的光路不会再分配波长集合入中的波长.由引理2知,图G2嵌入环网络所需的最小波长数与图G3嵌入环网络所需的最小波长数相等,可得：WPLU(n)=WG3(n-l)+(n-l)由定理1知,只要求出了图G3嵌入环网络所需的最小波长数就得到了实现PLU
19、通信模式所需的最小波长数.后面我们得到并证明了图G3嵌入环网络所需的最小波长数.4.3 图G3嵌入环网络首先给出了将图G3嵌入环形光网络所需波长数的一个下限值,然后给出一种嵌入方案,使得所需的波长数到达该下限。首先介绍一种求波长下限的方法,如下所述:在光网络的物理拓扑结构中去掉一些链路U,把原来的网络分割成为两个子图Ga和Gb,移去的链路集构成一个链路割集U.观察所有要建立的光通道,容易知道,只有光路两端分别位于不同子图的光通道(称为割集通道)在选择路由时必然要穿过U中的链路,记割集通道集合为Du.假设这些光通道均匀地分布在割集U的各条链路上,那么每条割集链路平均容纳的最大光通道数量为UDUI
20、U在不同的地方分割网络,所得的U不同,Du也随之不同.所有要在某个物理网络上实现给定的光通道所需的波长数必须满足:WNmaXUHlDUlU,对于任意的U。根据上述求波长下限的方法,我们得到以下结论：定理2.将图G3嵌入到环形光网络中所需波长数满足：其中,W3(p)表示将2p个节点的图G3嵌入到环形网络所需的波长数。证明:选择链路割集U(S,T,i)=ei,e(i+p)mod2p,其中i为介于1到2p之间的某一整数,更直观地说和e(i+p)mod2p是环上距离最远的两条边,该链路割集将环网络划分成两个节点数相等的子图S和T.将图G3的节点集C和R中的节点映射在环形网络的节点上,假设图G3的节点集
21、C中的节点映射在子图S上的节点个数为m,那么有:节点集C中的节点映射在子图T上的节点个数为p-m,节点集R的节点映射在子图S上的节点个数为pm,节点集R的节点映射在子图T上的节点个数为m,可以计算通过链路割集U(S,T,i)的边ei和e(i+p)mod2p的光路数,记为U(m),那么：其中，OWnlWP,m是整数。A=iCiS且riT+iGT且nS,AWp.易知,A=p当且仅当不存在i=j,使得ciS,jS或ciT,jT,即ci和ri不同属于集合S或T.对(1)式分析知：(a) P为奇数:m二(pT)2或(p+1)/2且A=P时,U(m)取最小值,最小值为p?2-pl2,该值记为B(p),设U
22、(ei,ej)表示通过割集链路ei和5的光路数,那么有maxei,ejE(U(ei,ej)B(p),ei,ejEo(b) p为偶数:m=p2且A=P时,U(m)取最小值,最小值为p22-p,该值记为A(p).反证法易证,不存在节点集C和R到环形网络节点的映射,使得通过环上所有的链路割集ei和e(i+p)mod2p的光路数到达最小值A(p).那么有maxei,ejE(U(ei,ej)A(P)+1.根据(a)、(b)以及前面介绍的求波长下限的方法可知,将图G3嵌入到环网络中所需波长数满足：定理2得证。二、LU并行分解的容错并行算法设计与实现的应用系统级CheCkPe)inting是一种广泛应用于大
23、规模系统的容错技术，该技术是在程序执行期间周期性的将所有进程的地址空间内容（堆、栈和全局变量）、存放器信息和通信库状态存储到可靠的存储器上。如果某个进程失效，所有进程都必须回滚到最近一个检查点处重新计算。当系统中包含数千甚至数万个处理器时，做一次CheCkPoint可能会导致所有处理器传输TerabyteS的数据到存储介质上，从而使I/0成为大规模并行系统中CheCkPOinting技术的性能瓶颈.由于这个原因，在IBMBlueGene和ASCl等大规模系统中未采用系统级CheCkPointing技术。1、错并行算法系统中两种通用故障类型分别是Fail-stop和ByZatine故障。针对不同
24、的故障类型，容错并行算法的设计有很大的不同.文中主要针对fail-stop的故障类型，对基于并行复算的容错并行算法的设计进行讨论。定义1复算段是指通信与通信之间、通信与初始化或算法终止过程之间的非空计算序列。并行算法的执行过程可被划分为复算段的连续过程，复算段的数目等于算法中通信次数最多的任务的通信次数加1,算法中各个任务的复算段数目相等,同一段内各个任务的计算相互独立，从1开始标记段号。如图1所示，算法中通信次数最多的是任务Pl和P2,通信次数均为3次，因此程序可分为4个复算段，Ski表示任务Pi的第k个复算段。图1并行程序复算段的划分图1中箭头源表示发送任务从发送消息的MPl调用返回点，因
25、此非阻塞通信MPIISend和MPl-Wait之间的计算属于下个计算段.箭头目的表示接收消息的任务，如果接收任务使用MPI-IRecv得到消息，箭头目的不是表示从MPI一IReCV返回点，而是代表MPIWait的返回点，因此MPIIRecv和MPIWait之间的计算属于上一个计算段.基于并行复算的容错并行算法在故障恢复过程中将故障任务失效前的负载进行划分，由剩余任务并行计算。恢复过程结束后，继续执行未完成的计算。PRB聊rPA的一般步骤如下：正常情况下，每个任务在每个复算段的人口对可到达此复算段人口的变量进行保存，在每个复算段的末尾添加故障检测的语句，检测是否存在故障；出现故障时，无故障任务在
26、复算段的末尾检测到故障，此时无故障任务处在当前复算段的末尾，然后执行基于并行复算的故障恢复程序，恢复过程完成后继续未完成的计算任务。2、LU分解算法的容错并行算法算法设计和分析LU分解将矩阵A分解为一个上三角形矩阵L和一个下三角形矩阵U。矩阵A的大小为PXP,算法运行在n个处理器上，假设P可被n整除，w=pno根据定义1,上述LU分解算法有P个复算段，每个复算段是LU分解的一个计算过程LU分解的计算过程中各行计算间没有数据相关关系，根据容错并行算法设计原那么，在正常情况下无需对任何变量进行保存.容错LU分解算法在每个复算段结束前添加故障检测的语句。如果在第k行为主元进行变换时，进程Pj在复算段
27、中出现故障，在此复算段末尾其它进程检测到这个故障.所有存活进程进入故障恢复过程.恢复过程执行的任务是故障进程执行过的变换计算，所有存活进程共同完成此任务。恢复过程如下：根据发生故障的进程号歹确定需要重计算的初始数据A.”主结点P。(如果P。发生故障，那么选用P)对AJ按行交叉方式进行划分，将划分后的数据发送到相应的剩余进程中，每个剩余结点得到Aj中的w(nT)或w(nT)行的数据，存活结点Pi中的数据用Afi表示。编号为i(ij时为j+(i-l)n,后面的类似)，j+(i+n-1)n,，j+(i+w-n)n,j+(i+w-l)n行(行号以j+I)n为界)。依次以计算得到的A的第0,1,，k行数
28、据作为主行，将其播送给所有处理器，各处理器利用主行对分到的A；的数据的行向量做行变换。恢复过程完成后，矩阵A的分解结果和故障前相同。然后，以k+1行作为主元播送继续计算，剩余的n1个进程继续计算。图2解释了上述过程在四个处理器上运行的过程，其中矩阵A的大小为1212.假设以为主元进行计算时P出现故障，P。，P2,P3完成此次计算后检测到Pl的故障；然后P将Pl的子块A进一步按行划分，Po,P2,P3分别得到最初的a1,a5,a9；然后依次以第ra,，好作为主行(其中ra”ra5是复算过程中得到的结果，ra用于存储矩阵A的中间分解结果)，将其播送给所有剩余处理器,各处理器利用主行对a”a5,a9做行变换。计算完成后ra”ra5,r%和故障前相同。复算完成后，依次以第ra,ra10,ra”作为主行，将其播送给所有剩余处理器，各处理器利用主行对ra”ra10,ra”做行变换，完成最后的分解计算。最后，Pz和P3将原有矩阵A数据的分解结果和复算中分配数据的分解结果发送给P。，在P。上合成最终结果。这里简单给出了容错并行算法的定义，并提出了一种新的基于并行复算的容错并行算法.该方法的创新之处在于以下：通过多个无故障处理器并行的重算失效处理器上的任务，实现快速容错.这是一种应用级的容错方法，需要用户对原有的算法进行修改.根据设计方法设计了矩阵LU分解的基于并行复算的容错并行算法。
