稠密矩陣LU分解的并行算法課件

稠密矩陣LU分解的并行算法塊形式的串行算法一維塊分布的基本與流水線并行算法一維循環(huán)塊分布的基本與流水線并行算法二維塊分布并行算法二維循環(huán)塊分布并行算法二維流水線模式的并行算法分布存儲并行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一維塊分布的基本并行算法(續(xù))假設(shè)n=pm，其中p為進(jìn)程數(shù)，m為塊的階數(shù)，則第0

k<p步，進(jìn)程Pk/先分解Ak,k為Lk,kUk,k，所需要的時間為(2m3/3-m2/2-m/6)c;之后，Pk/進(jìn)行操作Ak,j:＝(Uk,k)-1(Lk,k)-1Ak,j，j>k，所需要的時間為(2m3-m2)(p-k-1)c；其次，Pk/將Ak,k+1:p-1廣播給所有進(jìn)程，所需要的時間為slogp+b(p-k-1)m2logp；最后，各進(jìn)程并行計算Ai,j:=Ai,j-Ai,kAk,j，所需要的時間為2m3min(p-k-1,)(p-k-1)c。2023/8/144一維塊分布的基本并行算法(續(xù))假設(shè)n=pm，其中p為進(jìn)程數(shù)一維塊分布的基本并行算法(續(xù))總的并行執(zhí)行時間在p=n，m=1的特殊情況下，在p、m固定且n>>p時，由可知，并行效率不可能大于2/(3－p－2)2023/8/145一維塊分布的基本并行算法(續(xù))總的并行執(zhí)行時間在p=n，m=一維塊分布的流水線并行算法2023/8/146一維塊分布的流水線并行算法2023/8/16一維塊分布的流水線并行算法(續(xù))2023/8/147一維塊分布的流水線并行算法(續(xù))2023/8/17一維塊分布的流水線并行算法(續(xù))序號越小的進(jìn)程，計算量越小，負(fù)載嚴(yán)重不平衡，從而導(dǎo)致很多進(jìn)程處于空閑狀態(tài)負(fù)載最重的是最后一個進(jìn)程，其上的個行塊幾乎需要更新p－1次，每次一個行塊中的塊數(shù)為p－1不斷減少到1并行執(zhí)行時間為

(n3c/p)，所以無論n增大到什么程度，并行效率不可能大于2/32023/8/148一維塊分布的流水線并行算法(續(xù))序號越小的進(jìn)程，計算量越小，一維循環(huán)塊分布的基本并行算法2023/8/149一維循環(huán)塊分布的基本并行算法2023/8/19一維循環(huán)塊分布的基本并行算法(續(xù))2023/8/1410一維循環(huán)塊分布的基本并行算法(續(xù))2023/8/110一維循環(huán)塊分布的基本并行算法(續(xù))并行執(zhí)行時間為當(dāng)p=n，m=1時，當(dāng)p、m固定且n>>p時，2023/8/1411一維循環(huán)塊分布的基本并行算法(續(xù))并行執(zhí)行時間為當(dāng)p=n，m一維循環(huán)塊分布的流水線并行算法2023/8/1412一維循環(huán)塊分布的流水線并行算法2023/8/112一維循環(huán)塊分布的流水線并行算法(續(xù))2023/8/1413一維循環(huán)塊分布的流水線并行算法(續(xù))2023/8/113一維循環(huán)塊分布的流水線并行算法(續(xù))當(dāng)

>>p時，除了在流水線啟動與結(jié)束前之外，在計算過程中，進(jìn)程將很少空閑當(dāng)m為給定的很小的正整數(shù)時，并行執(zhí)行時間為

(2n3c/(3p))結(jié)論在一維循環(huán)塊分布下，如果p與m固定，則隨問題規(guī)模的增大，算法的并行效率趨于1一維循環(huán)塊分布優(yōu)于一維塊分布2023/8/1414一維循環(huán)塊分布的流水線并行算法(續(xù))當(dāng)>>p時，除了在二維塊分布并行算法2023/8/1415二維塊分布并行算法2023/8/115二維塊分布并行算法(續(xù))2023/8/1416二維塊分布并行算法(續(xù))2023/8/116二維塊分布并行算法(續(xù))并行執(zhí)行時間為在q固定時，Tp=

(2cn3/q2－2cn3/(3q3))。無論問題規(guī)模多大，并行效率將最多1/(3-q-1)q=n，m=1時，Tp3nc+2ns+2bnlogn2023/8/1417二維塊分布并行算法(續(xù))并行執(zhí)行時間為在q固定時，Tp=(二維循環(huán)塊分布并行算法2023/8/1418二維循環(huán)塊分布并行算法2023/8/118二維循環(huán)塊分布并行算法(續(xù))2023/8/1419二維循環(huán)塊分布并行算法(續(xù))2023/8/119二維循環(huán)塊分布并行算法(續(xù))并行執(zhí)行時間為當(dāng)q固定不變時，當(dāng)q=n，m=1時，等效率函數(shù)為，最多可有效利用的進(jìn)程數(shù)量為n2/log2n2023/8/1420二維循環(huán)塊分布并行算法(續(xù))并行執(zhí)行時間為當(dāng)q固定不變時，當(dāng)二維流水線模式的并行算法2023/8/1421二維流水線模式的并行算法2023/8/121二維流水線模式的并行算法(續(xù)）2023/8/1422二維流水線模式的并行算法(續(xù)）2023/8/122二維流水線模式的并行算法(續(xù)）2023/8/1423二維流水線模式的并行算法(續(xù)）2023/8/123二維流水線模式的并行算法(續(xù)）2023/8/1424二維流水線模式的并行算法(續(xù)）2023/8/124二維流水線模式的并行算法(續(xù)）2023/8/1425二維流水線模式的并行算法(續(xù)）2023/8/125分布存儲并行LU分解中的主元選取對一維情況，如果選行主元，則在采用逐行分布時，對并行計算無明顯影響在采用逐列分布時，主元選取時間可能更短，但既不利于流水線計算，也可能增加后續(xù)列交換的通信時間或引起負(fù)載不平衡對一維情況，如果選列主元，則結(jié)論與以上分析正好相反2023/8/1426分布存儲并行LU分解中的主元選取對一維情