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

1、2022-3-271稠密矩阵稠密矩阵LULU分解的并行算法分解的并行算法n块形式的串行算法块形式的串行算法n一维块分布的基本与流水线并行算法一维块分布的基本与流水线并行算法n一维循环块分布的基本与流水线并行算法一维循环块分布的基本与流水线并行算法n二维块分布并行算法二维块分布并行算法n二维循环块分布并行算法二维循环块分布并行算法n二维流水线模式的并行算法二维流水线模式的并行算法 n分布存储并行分布存储并行LULU分解中的主元选取分解中的主元选取2022-3-272块形式的串行算法块形式的串行算法LU(A,n,m)for(k=0; kn/m; k+) for(j=k+1; jn/m; j+) A

2、k,j = A-1k,k * Ak,j; for(i=k+1; in/m; i+) for(j=k+1; jn/m; j+) Ai,j = Ai,j Ai,k * Ak,j; 计算量大约为计算量大约为2 2n n3 3/3/3个浮点操作，与点个浮点操作，与点LULU分解一致分解一致2022-3-273一维块分布的基本并行算法一维块分布的基本并行算法P0A0,0 A0,1 A0,2 A0,3 A0,4 A0,5 A0,6 A0,7 A0,8A1,0 A1,1 A1,2 A1,3 A1,4 A1,5 A1,6 A1,7 A1,8A2,0 A2,1 A2,2 A2,3 A2,4 A2,5 A2,6

3、A2,7 A2,8P1A3,0 A3,1 A3,2 A3,3 A3,4 A3,5 A3,6 A3,7 A3,8A4,0 A4,1 A4,2 A4,3 A4,4 A4,5 A4,6 A4,7 A4,8A5,0 A5,1 A5,2 A5,3 A5,4 A5,5 A5,6 A5,7 A5,8P2A6,0 A6,1 A6,2 A6,3 A6,4 A6,5 A6,6 A6,7 A6,8A7,0 A7,1 A7,2 A7,3 A7,4 A7,5 A7,6 A7,7 A7,8A8,0 A8,1 A8,2 A8,3 A8,4 A8,5 A8,6 A8,7 A8,82022-3-274一维块分布的基本并行算法一

4、维块分布的基本并行算法( (续续) )假设假设n=p m，其中其中p为进程数，为进程数，m为块的阶数，则为块的阶数，则n第第0 k k，所需要的时间为所需要的时间为(2m3-m2)( p-k-1)c；n其次，其次， Pk/ 将将Ak, k+1: p-1广播给所有进程，所需要广播给所有进程，所需要的时间为的时间为s log p + b( p-k-1)m2 log p；n最后，各进程并行计算最后，各进程并行计算Ai,j := Ai,j - Ai,k Ak,j，所需所需要的时间为要的时间为2m3 min( p-k-1, )( p-k-1)c。2022-3-275一维块分布的基本并行算法一维块分布的基

5、本并行算法( (续续) )n总的并行执行时间总的并行执行时间)3/()3/(/ 2/log)/(log)/11)(/( )()2/1()6/12/3/2(233232222pcnmpcnpcmnpcnppmnmnpnnbppmnscmnnmncmmTpn在在p=n，m=1的特殊情况下，的特殊情况下，2/loglog2/322nbnnsncnTpn在在p、m固定且固定且np时，由时，由)3/(/2/log)/(333222pcnpcnppnnbTp 可知，并行效率不可能大于可知，并行效率不可能大于2/(3p2)2022-3-276一维块分布的流水线并行算法一维块分布的流水线并行算法2022-3-

6、277一维块分布的流水线并行算法一维块分布的流水线并行算法( (续续) )2022-3-278一维块分布的流水线并行算法一维块分布的流水线并行算法( (续续) )n序号越小的进程，计算量越小，负载严重序号越小的进程，计算量越小，负载严重不平衡，从而导致很多进程处于空闲状态不平衡，从而导致很多进程处于空闲状态n负载最重的是最后一个进程，其上的负载最重的是最后一个进程，其上的 个个行块几乎需要更新行块几乎需要更新 p1次，每次一个行次，每次一个行块中的块数为块中的块数为 p1不断减少到不断减少到1n并行执行时间为并行执行时间为 (n3c/p)，所以无论所以无论n增大增大到什么程度，并行效率不可能大

7、于到什么程度，并行效率不可能大于2/32022-3-279一维循环块分布的基本并行算法一维循环块分布的基本并行算法2022-3-2710一维循环块分布的基本并行算法一维循环块分布的基本并行算法( (续续) )2022-3-2711一维循环块分布的基本并行算法一维循环块分布的基本并行算法( (续续) )n并行执行时间为并行执行时间为21)1(3203202102323) 1(2) 1(2 log) 1(log ) 1)(2(6232p-pkp-kp-kpkpkpmkpmpmkpbpsckpmmpcmmmTn当当p=n，m=1时，时，n当当p、m固定且固定且np时，时，2/loglog2/322n

8、bnnsncnTp2/log)3/(223pbnpcnTp2022-3-2712一维循环块分布的流水线并行算法一维循环块分布的流水线并行算法2022-3-2713一维循环块分布的流水线并行算法一维循环块分布的流水线并行算法( (续续) )2022-3-2714一维循环块分布的流水线并行算法一维循环块分布的流水线并行算法( (续续) )n当当 p时，除了在流水线启动与结束前时，除了在流水线启动与结束前之外，在计算过程中，进程将很少空闲之外，在计算过程中，进程将很少空闲n当当m为给定的很小的正整数时，并行执行为给定的很小的正整数时，并行执行时间为时间为 (2n3c/(3p)n结论结论v在一维循环块

9、分布下，如果在一维循环块分布下，如果p与与m固定，则随固定，则随问题规模的增大，算法的并行效率趋于问题规模的增大，算法的并行效率趋于1v一维循环块分布优于一维块分布一维循环块分布优于一维块分布2022-3-2715二维块分布并行算法二维块分布并行算法2022-3-2716二维块分布并行算法二维块分布并行算法( (续续) )2022-3-2717二维块分布并行算法二维块分布并行算法( (续续) )n并行执行时间为qqbmnsqmnmncmnmmmcmmqnqncmqnmqnqncqqnmqnTplog)/22)(/(/( )/)(6/2/3/2( )2/1)(/)(/( 3/)/2)(/)(/(

10、2 ) 1(/) 12(/2232233n在q固定时，Tp=(2cn3/q22cn3/(3q3)。无论问题规模多大，并行效率将最多1/(3-q-1)nq=n，m=1时，Tp 3nc + 2ns + 2bn log n2022-3-2718二维循环块分布并行算法二维循环块分布并行算法2022-3-2719二维循环块分布并行算法二维循环块分布并行算法( (续续) )2022-3-2720二维循环块分布并行算法二维循环块分布并行算法( (续续) )n并行执行时间为并行执行时间为222223222/23/)3/(2 /log2log2 /) 12()6/12/3/2(qcmnncmqcmnqcnqqb

11、nqnsqcnmcmmnTqqn当当q固定不变时，固定不变时，)3/(2/log232qcnqqbnTqqn当当q=n，m=1时，时，ncnnsnbnTqq3log2log2)log(32/3ppWn等效率函数为等效率函数为，最多可有效利用，最多可有效利用的进程数量为的进程数量为n2/log2n2022-3-2721二维流水线模式的并行算法二维流水线模式的并行算法2022-3-2722二维流水线模式的并行算法二维流水线模式的并行算法( (续）续）2022-3-2723二维流水线模式的并行算法二维流水线模式的并行算法( (续）续）2022-3-2724二维流水线模式的并行算法二维流水线模式的并行

12、算法( (续）续）2022-3-2725二维流水线模式的并行算法二维流水线模式的并行算法( (续）续）2022-3-2726分布存储并行分布存储并行LULU分解中的主元选取分解中的主元选取n对一维情况，如果选行主元，则对一维情况，如果选行主元，则v在采用逐行分布时，对并行计算无明显影响在采用逐行分布时，对并行计算无明显影响v在采用逐列分布时，主元选取时间可能更短，在采用逐列分布时，主元选取时间可能更短，但既不利于流水线计算，也可能增加后续列交但既不利于流水线计算，也可能增加后续列交换的通信时间或引起负载不平衡换的通信时间或引起负载不平衡n对一维情况，如果选列主元，则结论与以对一维情况，如果选列主元，则结论与以上分析正好相反上分析正好相反2022-3-2727分布存储并行分布存储并行LULU分解中的主元选取分解中的主元选取( (续续) )n在二维分布下，选主元将对流水线模式形在二维分布下，选主元将对流水线模式形成严重影响成严重影响n两种改善措施两种改善措施v将主元的选取限制在当前行或列的最近若干行将主元的选取限制在当前行或列的最近若干行或列之内或列之内v采用分散与多对多广播来实现一对多广播采用分散与多对多广播来实现一对多广播v前者更有利于计算与通信重叠，在前者更有利于计算与通信重叠，在HPL测试测试中采用的就是前一种策略中采用的就是前一种策略