稠密矩阵LU分解的并行算法课件

稠密矩阵LU分解的并行算法块形式的串行算法一维块分布的基本与流水线并行算法一维循环块分布的基本与流水线并行算法二维块分布并行算法二维循环块分布并行算法二维流水线模式的并行算法分布存储并行LU分解中的主元选取2023/8/141稠密矩阵LU分解的并行算法块形式的串行算法2023/8/11块形式的串行算法LU(A,n,m)for(k=0;k<n/m;k++){for(j=k+1;j<n/m;j++)A[k,j]=A-1[k,k]*A[k,j];for(i=k+1;i<n/m;i++){for(j=k+1;j<n/m;j++)A[i,j]=A[i,j]–A[i,k]*A[k,j];}}计算量大约为2n3/3个浮点操作，与点LU分解一致2023/8/142块形式的串行算法LU(A,n,m)计算量大约为2n3/3个浮一维块分布的基本并行算法P0A0,0A0,1A0,2A0,3A0,4A0,5A0,6A0,7A0,8A1,0A1,1

A1,2A1,3A1,4A1,5A1,6A1,7A1,8A2,0A2,1

A2,2A2,3A2,4A2,5A2,6A2,7A2,8P1A3,0A3,1

A3,2A3,3A3,4A3,5A3,6A3,7A3,8A4,0A4,1

A4,2A4,3A4,4A4,5A4,6A4,7A4,8A5,0A5,1

A5,2A5,3A5,4A5,5A5,6A5,7A5,8P2A6,0A6,1

A6,2A6,3A6,4A6,5A6,6A6,7A6,8A7,0A7,1

A7,2A7,3A7,4A7,5A7,6A7,7A7,8A8,0A8,1

A8,2A8,3A8,4A8,5A8,6A8,7A8,82023/8/143一维块分布的基本并行算法P0A0,0A0,1A0一维块分布的基本并行算法(续)假设n=pm，其中p为进程数，m为块的阶数，则第0

k<p步，进程Pk/先分解Ak,k为Lk,kUk,k，所需要的时间为(2m3/3-m2/2-m/6)c;之后，Pk/进行操作Ak,j:＝(Uk,k)-1(Lk,k)-1Ak,j，j>k，所需要的时间为(2m3-m2)(p-k-1)c；其次，Pk/将Ak,k+1:p-1广播给所有进程，所需要的时间为slogp+b(p-k-1)m2logp；最后，各进程并行计算Ai,j:=Ai,j-Ai,kAk,j，所需要的时间为2m3min(p-k-1,)(p-k-1)c。2023/8/144一维块分布的基本并行算法(续)假设n=pm，其中p为进程数一维块分布的基本并行算法(续)总的并行执行时间在p=n，m=1的特殊情况下，在p、m固定且n>>p时，由可知，并行效率不可能大于2/(3－p－2)2023/8/145一维块分布的基本并行算法(续)总的并行执行时间在p=n，m=一维块分布的流水线并行算法2023/8/146一维块分布的流水线并行算法2023/8/16一维块分布的流水线并行算法(续)2023/8/147一维块分布的流水线并行算法(续)2023/8/17一维块分布的流水线并行算法(续)序号越小的进程，计算量越小，负载严重不平衡，从而导致很多进程处于空闲状态负载最重的是最后一个进程，其上的个行块几乎需要更新p－1次，每次一个行块中的块数为p－1不断减少到1并行执行时间为

(n3c/p)，所以无论n增大到什么程度，并行效率不可能大于2/32023/8/148一维块分布的流水线并行算法(续)序号越小的进程，计算量越小，一维循环块分布的基本并行算法2023/8/149一维循环块分布的基本并行算法2023/8/19一维循环块分布的基本并行算法(续)2023/8/1410一维循环块分布的基本并行算法(续)2023/8/110一维循环块分布的基本并行算法(续)并行执行时间为当p=n，m=1时，当p、m固定且n>>p时，2023/8/1411一维循环块分布的基本并行算法(续)并行执行时间为当p=n，m一维循环块分布的流水线并行算法2023/8/1412一维循环块分布的流水线并行算法2023/8/112一维循环块分布的流水线并行算法(续)2023/8/1413一维循环块分布的流水线并行算法(续)2023/8/113一维循环块分布的流水线并行算法(续)当

>>p时，除了在流水线启动与结束前之外，在计算过程中，进程将很少空闲当m为给定的很小的正整数时，并行执行时间为

(2n3c/(3p))结论在一维循环块分布下，如果p与m固定，则随问题规模的增大，算法的并行效率趋于1一维循环块分布优于一维块分布2023/8/1414一维循环块分布的流水线并行算法(续)当>>p时，除了在二维块分布并行算法2023/8/1415二维块分布并行算法2023/8/115二维块分布并行算法(续)2023/8/1416二维块分布并行算法(续)2023/8/116二维块分布并行算法(续)并行执行时间为在q固定时，Tp=

(2cn3/q2－2cn3/(3q3))。无论问题规模多大，并行效率将最多1/(3-q-1)q=n，m=1时，Tp3nc+2ns+2bnlogn2023/8/1417二维块分布并行算法(续)并行执行时间为在q固定时，Tp=(二维循环块分布并行算法2023/8/1418二维循环块分布并行算法2023/8/118二维循环块分布并行算法(续)2023/8/1419二维循环块分布并行算法(续)2023/8/119二维循环块分布并行算法(续)并行执行时间为当q固定不变时，当q=n，m=1时，等效率函数为，最多可有效利用的进程数量为n2/log2n2023/8/1420二维循环块分布并行算法(续)并行执行时间为当q固定不变时，当二维流水线模式的并行算法2023/8/1421二维流水线模式的并行算法2023/8/121二维流水线模式的并行算法(续）2023/8/1422二维流水线模式的并行算法(续）2023/8/122二维流水线模式的并行算法(续）2023/8/1423二维流水线模式的并行算法(续）2023/8/123二维流水线模式的并行算法(续）2023/8/1424二维流水线模式的并行算法(续）2023/8/124二维流水线模式的并行算法(续）2023/8/1425二维流水线模式的并行算法(续）2023/8/125分布存储并行LU分解中的主元选取对一维情况，如果选行主元，则在采用逐行分布时，对并行计算无明显影响在采用逐列分布时，主元选取时间可能更短，但既不利于流水线计算，也可能增加后续列交换的通信时间或引起负载不平衡对一维情况，如果选列主元，则结论与以上分析正好相反2023/8/1426分布存储并行LU分解中的主元选取对一维情