1、2018/9/27,1,稠密矩阵LU分解的并行算法,块形式的串行算法一维块分布的基本与流水线并行算法一维循环块分布的基本与流水线并行算法二维块分布并行算法二维循环块分布并行算法二维流水线模式的并行算法 分布存储并行LU分解中的主元选取,2018/9/27,2,块形式的串行算法,LU(A,n,m)for(k=0; kn/m; k+) for(j=k+1; jn/m; j+) Ak,j = A-1k,k * Ak,j; for(i=k+1; in/m; i+) for(j=k+1; jp时，由,可知，并行效率不可能大于2/(3p2),2018/9/27,6,一维块分布的流水线并行算法,2018/9
2、/27,7,一维块分布的流水线并行算法(续),2018/9/27,8,一维块分布的流水线并行算法(续),序号越小的进程，计算量越小，负载严重不平衡，从而导致很多进程处于空闲状态负载最重的是最后一个进程，其上的个行块几乎需要更新 p1次，每次一个行块中的块数为p1不断减少到1并行执行时间为 (n3c/p)，所以无论n增大到什么程度，并行效率不可能大于2/3,2018/9/27,9,一维循环块分布的基本并行算法,2018/9/27,10,一维循环块分布的基本并行算法(续),2018/9/27,11,一维循环块分布的基本并行算法(续),并行执行时间为,当p=n，m=1时，,当p、m固定且np时，,2
3、018/9/27,12,一维循环块分布的流水线并行算法,2018/9/27,13,一维循环块分布的流水线并行算法(续),2018/9/27,14,一维循环块分布的流水线并行算法(续),当 p时，除了在流水线启动与结束前之外，在计算过程中，进程将很少空闲当m为给定的很小的正整数时，并行执行时间为(2n3c/(3p)结论在一维循环块分布下，如果p与m固定，则随问题规模的增大，算法的并行效率趋于1一维循环块分布优于一维块分布,2018/9/27,15,二维块分布并行算法,2018/9/27,16,二维块分布并行算法(续),2018/9/27,17,二维块分布并行算法(续),并行执行时间为,在q固定时
4、，Tp=(2cn3/q22cn3/(3q3)。无论问题规模多大，并行效率将最多1/(3-q-1),q=n，m=1时，Tp 3nc + 2ns + 2bn log n,2018/9/27,18,二维循环块分布并行算法,2018/9/27,19,二维循环块分布并行算法(续),2018/9/27,20,二维循环块分布并行算法(续),并行执行时间为,当q固定不变时，,当q=n，m=1时，,2018/9/27,21,二维流水线模式的并行算法,2018/9/27,22,二维流水线模式的并行算法(续）,2018/9/27,23,二维流水线模式的并行算法(续）,2018/9/27,24,二维流水线模式的并行算
5、法(续）,2018/9/27,25,二维流水线模式的并行算法(续）,2018/9/27,26,分布存储并行LU分解中的主元选取,对一维情况，如果选行主元，则在采用逐行分布时，对并行计算无明显影响在采用逐列分布时，主元选取时间可能更短，但既不利于流水线计算，也可能增加后续列交换的通信时间或引起负载不平衡对一维情况，如果选列主元，则结论与以上分析正好相反,2018/9/27,27,分布存储并行LU分解中的主元选取(续),在二维分布下，选主元将对流水线模式形成严重影响两种改善措施将主元的选取限制在当前行或列的最近若干行或列之内采用分散与多对多广播来实现一对多广播前者更有利于计算与通信重叠，在HPL测试中采用的就是前一种策略,
