并行LU分解的在通信中的应用.docx

并行LU分解的在通信中的应用摘要:本文主要表达了并行LU分解在WDM环网上的波长分配算法中的应用和容错并行算法设计与实现的应用，波长分配是光网络设计的根本问题,设计波长分配算法是洞察光网络通信能力的根本方法。不同的并行算法具有不同的通信模式,如何在光互连网上实现这些通信模式,是当前一个颇受关注的研究领域。基于WDM环网络,针对矩阵的并行LU分解,构造了一种并行LU分解的通信模式,讨论了将该通信模式嵌入在环形光网络中的波长分配问题。在解决该问题的过程中,得到了将一种特殊的二分图结构的通信模式嵌入在环网中的波长分配算法。通过分析和证明得到了在WDM环网上实现该并行LU分解通信模式所需的最小波长数。给出了容错并行算法的定义，提出了一种新的基于并行复算的容错并行算法。针对许多计算密集型任务中的矩阵LU分解设计了相应的基于并行复算的容错并行算法，并对设计的矩阵LU分解的容错并行算法的性能进行了评估并与CheCkPointing方法进行了比照。结果说明与CheCkPointing方法相比，矩阵LU分解的容错并行算法有性能上的优势。关键词:LU分解;波长分配;WDM环;网络嵌入;并行处理;容错Abstract:ThispapermainlydescribestheapplicationOfparallelLudecompositionandfaulttoleranceandwavelengthassignmentalgorithmintheWDMloopnetworkinparallelapplicationalgorithmdesignandimplementation,wavelengthassignmentisabasicprobleminopticalnetworkdesign,thedesignOfwavelengthassignmentalgorithmisthebasicmethodOfinsightintotheopticalnetworkcommunicationability.Differentparallelalgorithmshavedifferentmodesofcommunication,howtorealizethesecom-municationpatternsonopticalinterconnectionnetworksisahotre-searchfield.BasedontheWDMringnetwork,accordingtothepara-IIeILudecompositionofmatrix,constructsaparallelLUcommuni-cationmodedecomposition,discussesthewavelengthassignmentproblemthatthecommunicationmodelsembeddedintheopticalringnetwork.Intheprocessofsolvingthisproblem,getthewavelengtha-Ssignmentalgorithmembeddedcommunicationmodeofaspecialtwopartedgraphstructureinringnetwork.ThroughtheanalysisandtheproofobtainedintheWDMringetworktorealizetheparallelminima-mwavelengthofLudecompositionofthenumberofrequiredcommu-icationmode.Givesthedefinitionoffault-tolerantparallelalgorith-m,presentsanewparallelalgorithmbasedonfaulttolerantparallelrecomputing.AccordingtothematrixLUmanycomputationallyinten-sivetaskdecompositiontodesignthecorrespondingparallelalgorith-msforfault-tolerantparallelrecomputingbasedfaulttoleranceandperformanceonthedecompositionofmatrixLUdesignparallelalgorithmwasevaluatedandcomparedwiththecheckpointingmethod.Theres-ultsshowthatcomparedwithcheck-pointingmethod,thefault-toler-antmatrixLUdecompositionparallelalgorithmhasaperformanceadvantage.KeyWord:LUdecomposition;avelengthassignment;WDMring;networkembedding;parallelprocessing;faulttolerance一、LU并行分解在WDM环网上波长算法中的应用1LU并行分解在WDM环网上波长算法中为什么能得到广泛应用线性方程组的求解问题是很多科学和工程领域的根本重要问题,其中矩阵的LU分解是最根本和常用的.在很多科学计算领域中,求解大规模的线性方程组成为计算的瓶颈,通常采用并行处理来提高计算的速度.互连网络是并行计算机的关键部件,其效率直接影响到并行计算机的性能.而采用波分复用(WavelengthDiViSiOnMUItiPleXing,简称WDM)的全光网是互连网络的一个重要研究方向,利用全光互连网络具有高宽带、低延迟等优点来进一步提高大规模并行数值计算的速度有着巨大的潜力.目前,在一条物理连接上,实验室技术可以复用100个左右的虚拟通道,每个虚拟通道使用不同的波长.随着技术的开展,可复用的波长数会逐渐增加.如何高效地利用这些波长,是光互连网络研究的一个重要问题。互连网络有各种各样的通信模式,通过分析各种通信模式对波长的需求,洞察互连网络的能力是分析网络的一种行之有效的方法.环形网络是实际中广泛采用的一类拓扑结构,其上的波长分配问题具有重要的实用价值.在这方面,不少人作过研究:文献讨论了在WDM环网络上的波长分配问题;文献4将Hypercube通信模式嵌入到环,研究了其最大波长需求问题;文献讨论了在光RP(k)网络上实现HyPer-CUbe通信模式的波长分配问题,同时得到了在环网络上实现n维HyPerCUbe通信模式的波长分配算法,并改良了文献中的结论.本文针对矩阵的并行LU分解,首先构造了一种并行LU分解的通信模式,然后讨论了将这种并行LU分解的通信模式嵌入在环形光通信网络中的波长分配问题,最后给出了在WDM环网络上实现并行LU分解的最小波长数的结论.2根本概念为了分析方便,下面我们先给出有关的根本概念和根底知识。2.1WDM光互连网络WDM光互连光网络提供一个诱人的特点,那就是波长路由,波长路由网络是通过光通道来实现通信的,光通道是网络节点之间的全光通信信道,可以跨越多个光链路.波长路由网络的根本要求是同一光纤链路上的不同光通道必须具有不同波长，以免通道间互相干扰.光通道可以划分为波长通道(WP:WavelengthPath)和虚波长通道(VWP:VirtualWavelengthPath)两种结构.波长通道网络满足波长连续性要求,即一条光通道从输入端口到输出端口所经过的物理链路分配的波长应该相同;虚波长通道网络的交换节点处具有波长转换功能,即一条光通道在通过光网络过程中,可以分配不同的波长.在没有波长转换器的WDM网络中,路由实现方式属于波长通道,后面的讨论都基于波长通道方式。2.2波长分配在光网络上,已给一个通信模式,如何实现路由及分配通道是一个重要的研究问题,称为波长分配问题(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分解为一个单位下三角矩阵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=k÷1:n,j=k+1:n)A(i,j)=A(iJ)-A(i,k)*A(k,j)ENDFORALL!Sub-matrixMOdificationENDDO并行LU分解的首要问题是矩阵数据的划分问题.循环块数据分布方式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=10×10,r×s=1X3.那么矩阵元素的分布情况如图1(a)所示,矩阵元素上的标号表示该元素被分配在处理机E(p,q)上。分析进行一步LU分解的通信情况,可知在第k步LU分解过程中,假设矩阵元素Aik或Akj所在的块被分配在处理机s上,矩阵元素Aij所在的块被分配在处理机d上,那么处理机s和d之间存在通信,否那么不存在通信.图1(b)为进行第k步LU分解的示意图。基于循环块数据分布方式,对并行LU分解的过程以及通信状况进行分析,将处理机抽象为通信模式中的节点,通信请求抽象为通信模式中的边,由于循环块数据分布方式尽量保证处理机之间的负载平衡,并且每一步LU分解具有相似的通信模式,可用如图2(a)表示。更一般地,将规模较大的矩阵采用循环块数据分布方式分配给n×n=n2(n22)个处理机,每个处理机用(i,j)唯一地标识,其中OWi,jWnl,处理机(0,0)记为m,处理机(0,i)记为ci,处理机(i,0)记为ri,处理机(i,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<n-1)°4PLU通信模式在WDM环网中的波长分配在WDM环网中上实现PLU通信模式,也就是说,将PLU通信模式嵌入WDM环网中,使得通过WDM环网中任何一条物理链路的光路数的最大值最小.为讨论方便,我们考虑无向的全光环网用图G(V,E)来表示,其中V表示网络中的处理机节点集合,E表示节点间的光纤链路集合,通信请求可以沿顺时针方向实现,也可以沿逆时针方向实现,同时不考虑PLU通信模式中边的方向,即(x,y)