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

并行LU分解的在通信中的应用摘要:本文主要叙述了并行LU分解在WDM环网上的波长分配算法中的应用和容错并行算法设计与实现的应用，波长分配是光网络设计的基本问题,设计波长分配算法是洞察光网络通信能力的基本方法。不同的并行算法具有不同的通信模式,如何在光互连网上实现这些通信模式,是当前一个颇受关注的研究领域。基于WDM环网络,针对矩阵的并行LU分解,构造了一种并行LU分解的通信模式,讨论了将该通信模式嵌入在环形光网络中的波长分配问题。在解决该问题的过程中,得到了将一种特殊的二分图结构的通信模式嵌入在环网中的波长分配算法。通过分析和证明得到了在WDM环网上实现该并行LU分解通信模式所需的最小波长数。给出了容错并行算法的定义，提出了一种新的基于并行复算的容错并行算法。针对许多计算密集型任务中的矩阵LU分解设计了相应的基于并行复算的容错并行算法，并对设计的矩阵LU分解的容错并行算法的性能进行了评估并与checkpointing方法进行了对比。结果表明与checkpointing方法相比，矩阵LU分解的容错并行算法有性能上的优势。关键词:LU分解;波长分配;WDM环;网络嵌入;并行处理;容错Abstract: This paper mainly describes theapplication ofparallel LUdecompositionand fault toleranceand wavelength assignment algorithm inthe WDM loop networkinparallel applicationalgorithmdesign and implementation,wavelength assignmentis a basic problem inoptical networkdesign,the design ofwavelength assignment algorithmis the basicmethod ofinsight into theoptical network communicationability. Different parallel algorithms havedifferent modes of communication,how to realize these com- munication patterns onoptical interconnection networksis a hotre- search field. Based on theWDM ringnetwork,according to thepara -llel LUdecomposition of matrix,constructs aparallel LUcommuni- cationmode decomposition,discusses thewavelength assignment problemthat the communication modeis embedded inthe optical ring network. In theprocessof solving this problem,getthewavelength a- ssignmentalgorithm embeddedcommunicationmode of aspecialtwo parted graphstructurein ring network. Through the analysis and the proofobtained inthe WDM ring networkto realizetheparallel minimu -mwavelength of LUdecomposition ofthe number of required commu -nicationmode. Gives the definition offault-tolerant parallelalgorith -m,presents a new parallelalgorithmbased onfault tolerantparallel recomputing. According to the matrix LU many computationally inten- sive task decomposition to design the corresponding parallel algorith- ms for fault-tolerant parallel recomputing based fault tolerance and pe rformance on the decomposition of matrix LU design parallel algorithm was evaluated and compared with the checkpointing method. The res- ults show that compared with check- pointing method, the fault toler -ant matrix LU decomposition parallel algorithm has a performance advantage.Key Word: LU decomposition; avelength assignment; WDM ring; network embedding; parallel processing; fault tolerance一、LU并行分解在WDM环网上波长算法中的应用1LU并行分解在WDM环网上波长算法中为什么能得到广泛应用线性方程组的求解问题是很多科学和工程领域的基本重要问题,其中矩阵的LU分解是最基本和常用的.在很多科学计算领域中,求解大规模的线性方程组成为计算的瓶颈,通常采用并行处理来提高计算的速度.互连网络是并行计算机的关键部件,其效率直接影响到并行计算机的性能.而采用波分复用(W avelength DivisionMultiplexing,简称WDM)的全光网是互连网络的一个重要研究方向,利用全光互连网络具有高宽带、低延迟等优点来进一步提高大规模并行数值计算的速度有着巨大的潜力.目前,在一条物理连接上,实验室技术可以复用100个左右的虚拟通道,每个虚拟通道使用不同的波长.随着技术的发展,可复用的波长数会逐渐增加.如何高效地利用这些波长,是光互连网络研究的一个重要问题。互连网络有各种各样的通信模式,通过分析各种通信模式对波长的需求,洞察互连网络的能力是分析网络的一种行之有效的方法.环形网络是实际中广泛采用的一类拓扑结构,其上的波长分配问题具有重要的实用价值.在这方面,不少人作过研究:文献讨论了在WDM环网络上的波长分配问题;文献4将Hypercube通信模式嵌入到环,研究了其最大波长需求问题;文献讨论了在光RP(k)网络上实现Hyper-cube通信模式的波长分配问题,同时得到了在环网络上实现n维Hypercube通信模式的波长分配算法,并改进了文献中的结论.本文针对矩阵的并行LU分解,首先构造了一种并行LU分解的通信模式,然后讨论了将这种并行LU分解的通信模式嵌入在环形光通信网络中的波长分配问题,最后给出了在WDM环网络上实现并行LU分解的最小波长数的结论.2基本概念为了分析方便,下面我们先给出有关的基本概念和基础知识。2.1WDM光互连网络WDM光互连光网络提供一个诱人的特点,那就是波长路由,波长路由网络是通过光通道来实现通信的,光通道是网络节点之间的全光通信信道,可以跨越多个光链路.波长路由网络的基本要求是同一光纤链路上的不同光通道必须具有不同波长,以免通道间互相干扰.光通道可以划分为波长通道(WP: W avelength path)和虚波长通道(VWP: V irtualW avelength path)两种结构.波长通道网络满足波长连续性要求,即一条光通道从输入端口到输出端口所经过的物理链路分配的波长应该相同;虚波长通道网络的交换节点处具有波长转换功能,即一条光通道在通过光网络过程中,可以分配不同的波长.在没有波长转换器的WDM网络中,路由实现方式属于波长通道,后面的讨论都基于波长通道方式。2.2波长分配在光网络上,已给一个通信模式,如何实现路由及分配通道是一个重要的研究问题,称为波长分配问题(RCA )。RCA问题可以描述为:给定一个通信集合C= (x, y)|x向y传送信息,要完成如下的分配任务:(1)为每一个通信(x, y)分配一条由x到y的路径,在该路径上指定一个波长;(2)以上的波长分配满足:如果在某一物理连接上有多条路径经过,那么它们使用互不相同的波长;(3)分配的目标是最小化指定的波长数.很多文献讨论了RCA问题4, 7,本文基于WDM环网络，讨论实现并行LU分解通信模式的波长分配问题.3并行LU分解的通信模式在许多应用问题的科学计算中,矩阵的LU分解是最基本和常用的,它是求解三角形线性系的基础. LU分解法求解线性方程组Ax= b分为三步:(1)将矩阵A分解为一个单位下三角矩阵L和一个单位上三角矩阵U,则有LU x= b;(2)令Y=Ux,求解Ly= b;(3)求解Ux= y.其中,有效的LU分解是最复杂也是最关键的一步. LU分解的递推公式为:则下面的一段代码表示第k步LU分解时调整矩阵元素值暂不考虑选主元),该段代码具有良好的并行特征：DO k= 1, n-1A(k+ 1: n, k)= A(k+ 1: n, k) /A(k, k)! Column NormalizationFORALL (i= k+ 1: n, j= k+ 1: n)A(i, j)= A(i, j) -A(i, k)*A(k, j)END FORALL ! Sub-matrixM odificationEND DO并行LU分解的首要问题是矩阵数据的划分问题.循环块数据分布方式8是一种经常采用的矩阵划分方式,对于给定E=PQ个处理机、MN的矩阵AMN,将矩阵的元素分块,分块大小为rs,以循环块分布的形式分别存放到PQ的处理机上.若矩阵A的元素A(i, j)被分配在处理机E(p, q)上,则p= (i/s)mod P, q= (j/t)mod Q.假设PQ= 44=16个处理机,每个处理机用(p, q)唯一地标识,MN= 1010,rs= 13.则矩阵元素的分布情况如图1(a)所示,矩阵元素上的标号表示该元素被分配在处理机E(p, q)上。分析进行一步LU分解的通信情况,可知在第k步LU分解过程中,若矩阵元素Aik或Akj所在的块被分配在处理机s上,矩阵元素Aij所在的块被分配在处理机d上,则处理机s和d之间存在通信,否则不存在通信.图1(b)为进行第k步LU分解的示意图。基于循环块数据分布方式,对并行LU分解的过程以及通信状况进行分析,将处理机抽象为通信模式中的节点,通信请求抽象为通信模式中的边,由于循环块数据分布方式尽量保证处理机之间的负载平衡,并且每一步LU分解具有相似的通信模式,可用如图2(a)表示。更一般地,将规模较大的矩阵采用循环块数据分布方式分配给nn=n2(n2)个处理机,每个处理机用(i, j)唯一地标识,其中0i,jn-1,处理机(0, 0)记为m0,处理机(0, i)记为ci,处理机(i, 0)记为ri,处理机(i, j)记为vij(1in-1, 1jn-1).则上述并行LU分解通信模式可用有向图Gn(Vn,En)表示,节点集合Vn和边集合En可如下所示：为简便,后面我们将该通信模式简称为PLU通信模式。分析PLU通信模式有如下性质：性质1 不考虑边的方向时,Gn中的边(m0， ci)、(ci,，vii)、(ri, vii)、(m0, ri)在图Gn中构成回路,图Gn中这样的回路共n-1个(1in-1)。4PLU通信模式在WDM环网中的波长分配在WDM环网中上实现PLU通信模式,也就是说,将PLU通信模式嵌入WDM环网中,使得通过WDM环网中任何一条物理链路的光路数的最大值最小.为讨论方便,我们考虑无向的全光环网,用图G(V,E)来表示,其中V表示网络中的处理机节点集合,E表示节点间的光纤链路集合,通信请求可以沿顺时针方向实现,也可以沿逆时针方向实现,同时不考虑PLU通信模式中边的方向,即 (x, y)= (y, x)。4.1PLU通信模式的分解将PLU通信模式Gn(Vn,En),分解为子图G1(V1,E1)和子图G2(V2,E2),其中：引理1 将子图G1嵌入在WDM环网络中至少需要n-1个波长。证明：由性质1知,边(m0， ci)、(ci,，vii)、(ri, vii)、(m0, ri) (1in-1)在图G1中构成n-1条回路.易知,在环上实现每一条回路所需的波长数最少为1,当且仅当回路上的4条光路不共享任何一条物理链路且它们经过环上所有物理链路.因此,将子图G1嵌入在WDM环网络中所需的最小波长数为n-1。4.2PLU通信模式的化简由性质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嵌入环网络所需的最小波长数相等.经过上述的PLU通信模式的分解和化简,我们得到以下结论:定理1 在WDM环上实现PLU通信模式所需的最小波长数WPLU(n)=WG3(n-1)+ (n-1),其中WG3(n-1)是图G3嵌入环网络所需的最小波长数。证明:由引理1,若对G1中的n-1条回路分配波长集合=1 2、 、n-1,则该波长集合中的波长通道在每条物理链路上都被占用,图G2中的光路不会再分配波长集合中的波长.由引理2知,图G2嵌入环网络所需的最小波长数与图G3嵌入环网络所需的最小波长数相等,可得:WPLU(n)=WG3(n-1)+ (n-1)由定理1知,只要求出了图G3嵌入环网络所需的最小波长数就得到了实现PLU通信模式所需的最小波长数.后面我们得到并证明了图G3嵌入环网络所需的最小波长数.4.3图G3嵌入环网络首先给出了将图G3嵌入环形光网络所需波长数的一个下限值,然后给出一种嵌入方案,使得所需的波长数达到该下限。首先介绍一种求波长下限的方法6,如下所述:在光网络的物理拓扑结构中去掉一些链路U,把原来的网络分割成为两个子图Ga和Gb,移去的链路集构成一个链路割集U.观察所有要建立的光通道,容易知道,只有光路两端分别位于不同子图的光通道(称为割集通道)在选择路由时必然要穿过U中的链路,记割集通道集合为Du.假设这些光通道均匀地分布在割集U的各条链路上,那么每条割集链路平均容纳的最大光通道数量为|Du|/|U|。在不同的地方分割网络,所得的U不同,Du也随之不同.所有要在某个物理网络上实现给定的光通道所需的波长数必须满足:Wmax U|Du|/|U|,对于任意的U。根据上述求波长下限的方法,我们得到以下结论：定理2.将图G3嵌入到环形光网络中所需波长数满足：其中,w3(p)表示将2p个节点的图G3嵌入到环形网络所需的波长数。证明:选择链路割集U(S,T,i)= ei,e(i+p)mod2p,其中i为介于1到2p之间的某一整数,更直观地说,ei和e(i+p)mod2p是环上距离最远的两条边,该链路割集将环网络划分成两个节点数相等的子图S和T.将图G3的节点集C和R中的节点映射在环形网络的节点上,假设图G3的节点集C中的节点映射在子图S上的节点个数为m,则有:节点集C中的节点映射在子图T上的节点个数为p-m,节点集R的节点映射在子图S上的节点个数为p-m,节点集R的节点映射在子图T上的节点个数为m,可以计算通过链路割集U(S,T,i)的边ei和e(i+p)mod2p的光路数,记为U(m),则：其中, 0mp,m是整数。=|i|ciS且riT|+|i|ciT且riS|,p.易知,=p当且仅当不存在i=j,使得ciS,rjS或ciT,rjT,即ci和ri不同属于集合S或T.对(1)式分析知:(a) p为奇数:m=(p-1)/2或(p+ 1)/2且=p时,U(m)取最小值,最小值为p2 /2-p+1/2,该值记为B(p).设U(ei,ej)表示通过割集链路ei和ej的光路数,则有maxei,ejE(U(ei,ej)B(p)，ei,ej E。(b) p为偶数:m=p/2且=p时,U(m)取最小值,最小值为p2/2-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并行分解的容错并行算法设计与实现的应用系统级Checkpointing是一种广泛应用于大规模系统的容错技术，该技术是在程序执行期间周期性的将所有进程的地址空间内容(堆、栈和全局变量)、寄存器信息和通信库状态存储到可靠的存储器上。如果某个进程失效，所有进程都必须回滚到最近一个检查点处重新计算。当系统中包含数千甚至数万个处理器时，做一次checkpoint可能会导致所有处理器传输Terabytes的数据到存储介质上，从而使IO成为大规模并行系统中checkpointing技术的性能瓶颈由于这个原因，在IBM Blue Gene和ASCI等大规模系统中未采用系统级checkpointing技术。1、错并行算法系统中两种通用故障类型分别是Fail-stop和Byzatine故障。针对不同的故障类型，容错并行算法的设计有很大的不同文中主要针对fail -stop的故障类型，对基于并行复算的容错并行算法的设计进行讨论。定义1 复算段是指通信与通信之间、通信与初始化或算法终止过程之间的非空计算序列。并行算法的执行过程可被划分为复算段的连续过程，复算段的数目等于算法中通信次数最多的任务的通信次数加1，算法中各个任务的复算段数目相等，同一段内各个任务的计算相互独立，从1开始标记段号。如图1所示，算法中通信次数最多的是任务P1和P2，通信次数均为3次，因此程序可分为4个复算段，Ski表示任务Pi的第k个复算段。图1并行程序复算段的划分图1中箭头源表示发送任务从发送消息的MPI调用返回点，因此非阻塞通信MPIISend和MPIWait之间的计算属于下个计算段箭头目的表示接收消息的任务，如果接收任务使用MPIIRecv得到消息，箭头目的不是表示从MPIIRecv返回点，而是代表MPIWait的返回点，因此MPIIRecv和MPI Wait之间的计算属于上一个计算段基于并行复算的容错并行算法在故障恢复过程中将故障任务失效前的负载进行划分，由剩余任务并行计算。恢复过程结束后，继续执行未完成的计算。PRB聊rPA的一般步骤如下：正常情况下，每个任务在每个复算段的人口对可到达此复算段人口的变量进行保存，在每个复算段的末尾添加故障检测的语句，检测是否存在故障；出现故障时，无故障任务在复算段的末尾检测到故障，此时无故障任务处在当前复算段的末尾，然后执行基于并行复算的故障恢复程序，恢复过程完成后继续未完成的计算任务。2、LU分解算法的容错并行算法 算法设计和分析LU分解将矩阵A分解为一个上三角形矩阵L和一个下三角形矩阵U。矩阵A的大小为PP，算法运行在n个处理器上，假设p可被n整除，w=p/n。根据定义1，上述LU分解算法有P个复算段，每个复算段是LU分解的一个计算过程LU分解的计算过程中各行计算间没有数据相关关系，根据容错并行算法设计原则，在正常情况下无需对任何变量进行保存容错LU分解算法在每个复算段结束前添加故障检测的语句。如果在第