《并行計(jì)算課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《并行計(jì)算課件（45頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、并行計(jì)算,第一級(jí),第二級(jí),第三級(jí),第一級(jí),第二級(jí),第三級(jí),現(xiàn)代密碼學(xué)理論與實(shí)踐之五,*,*,并 行 計(jì) 算,中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系,國(guó)家高性能計(jì)算中心,(,合肥,),2004,年,12,月,2024/10/1,1,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,并 行 計(jì) 算 中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系2022,第二篇 并行算法的設(shè)計(jì),第四章 并行算法的設(shè)計(jì)基礎(chǔ),第五章 并行算法的一般設(shè)計(jì)方法,第六章,并行算法的基本設(shè)計(jì)技術(shù),第七章 并行算法的一般設(shè)計(jì)過程,2024/10/1,2,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,第二篇 并行算法的設(shè)計(jì) 第四章 并行算法的設(shè)計(jì)基礎(chǔ),第六章 并行算法的基本設(shè)計(jì)技術(shù),6.1

2、,劃分設(shè)計(jì)技術(shù),6.2,分治設(shè)計(jì)技術(shù),6.3,平衡樹設(shè)計(jì)技術(shù),6.4,倍增設(shè)計(jì)技術(shù),6.5,流水線設(shè)計(jì)技術(shù),2024/10/1,3,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,第六章 并行算法的基本設(shè)計(jì)技術(shù) 6.1 劃分設(shè)計(jì)技,6.1,劃分設(shè)計(jì)技術(shù),6.1.1,均勻劃分技術(shù),6.1.2,方根劃分技術(shù),6.1.3,對(duì)數(shù)劃分技術(shù),6.1.4,功能劃分技術(shù),2024/10/1,4,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,6.1 劃分設(shè)計(jì)技術(shù) 6.1.1 均勻劃分技術(shù),均勻劃分技術(shù),劃分方法,n,個(gè)元素,A1.n,分成,p,組，每組,A(i-1)n/p+1.in/p,，,i=1p,示例：,MIMD-SM,模型上的,PSRS,排序,b

3、egin,(1),均勻劃分：將,n,個(gè)元素,A1.n,均勻劃分成,p,段，每個(gè),p,i,處理,A(i-1)n/p+1.in/p,(2),局部排序：,p,i,調(diào)用串行排序算法對(duì),A(i-1)n/p+1.in/p,排序,(3),選取樣本：,p,i,從其有序子序列,A(i-1)n/p+1.in/p,中選取,p,個(gè)樣本元素,(4),樣本排序：用一臺(tái)處理器對(duì),p,2,個(gè)樣本元素進(jìn)行串行排序,(5),選擇主元：用一臺(tái)處理器從排好序的樣本序列中選取,p-1,個(gè)主元，并,播送給其他,p,i,(6),主元?jiǎng)澐郑?p,i,按主元將有序段,A(i-1)n/p+1.in/p,劃分成,p,段,(7),全局交換：各處理器

4、將其有序段按段號(hào)交換到對(duì)應(yīng)的處理器中,(8),歸并排序：各處理器對(duì)接收到的元素進(jìn)行歸并排序,end.,2024/10/1,5,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,均勻劃分技術(shù)劃分方法2022/10/105現(xiàn)代密碼學(xué)理論與,均勻劃分技術(shù),例,6.1 PSRS,排序過程。,N=27,，,p=3,，,PSRS,排序如下,：,2024/10/1,6,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,均勻劃分技術(shù)例6.1 PSRS排序過程。N=27，p=3，,6.1,劃分設(shè)計(jì)技術(shù),6.1.1,均勻劃分技術(shù),6.1.2,方根劃分技術(shù),6.1.3,對(duì)數(shù)劃分技術(shù),6.1.4,功能劃分技術(shù),2024/10/1,7,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,6.

5、1 劃分設(shè)計(jì)技術(shù) 6.1.1 均勻劃分技術(shù),方根劃分技術(shù),劃分方法,n,個(gè)元素,A1.n,分成,A(i-1)n(1/2)+1.in(1/2),，,i=1n(1/2),示例：,SIMD-CREW,模型上的,Valiant,歸并,(1975,年發(fā)表,),/,有序組,A1.p,、,B1.q,(,假設(shè),plogm=log4=2,=j1=rank(b,logm,:A)=rank(b,2,:A)=rank(9:A)=3,j2=8,B,0,:3,9 B,1,:16,21,A,0,:4,6,7 A,1,:10,12,15,18,20,A,和,B,歸并,化為,(,A,0,B,0,),和,(,A,1,B,1,),

6、的歸并,2024/10/1,12,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,對(duì)數(shù)劃分技術(shù)劃分方法2022/10/1012現(xiàn)代密碼學(xué)理論,6.1,劃分設(shè)計(jì)技術(shù),6.1.1,均勻劃分技術(shù),6.1.2,方根劃分技術(shù),6.1.3,對(duì)數(shù)劃分技術(shù),6.1.4,功能劃分技術(shù),2024/10/1,13,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,6.1 劃分設(shè)計(jì)技術(shù) 6.1.1 均勻劃分技術(shù),功能劃分技術(shù),劃分方法,n,個(gè)元素,A1.n,分成等長(zhǎng)的,p,組，每組滿足某種特性。,示例：,(m,n),選擇問題,(,求出,n,個(gè)元素中前,m,個(gè)最小者,),功能劃分：要求每組元素個(gè)數(shù)必須大于,m,；,算法：,p148,算法,6.4,輸入：,A=(a1

7、,an);,輸出：前,m,個(gè)最小者；,Begin,(1),功能劃分：將,A,劃分成,g=n/m,組，每組含,m,個(gè)元素；,(2),局部排序：使用,Batcher,排序網(wǎng)絡(luò)將各組并行進(jìn)行排序；,(3),兩兩比較：將所排序的各組兩兩進(jìn)行比較，從而形成,MIN,序列；,(4),排序,-,比較：對(duì)各個(gè),MIN,序列，重復(fù)執(zhí)行第,(2),和第,(3),步，直至,選出,m,個(gè)最小者。,End,2024/10/1,14,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,功能劃分技術(shù)劃分方法2022/10/1014現(xiàn)代密碼學(xué)理論,功能劃分技術(shù),2024/10/1,15,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,功能劃分技術(shù)2022/10/1015現(xiàn)

8、代密碼學(xué)理論與實(shí)踐之,第六章 并行算法的基本設(shè)計(jì)技術(shù),6.1,劃分設(shè)計(jì)技術(shù),6.2,分治設(shè)計(jì)技術(shù),6.3,平衡樹設(shè)計(jì)技術(shù),6.4,倍增設(shè)計(jì)技術(shù),6.5,流水線設(shè)計(jì)技術(shù),2024/10/1,16,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,第六章 并行算法的基本設(shè)計(jì)技術(shù) 6.1 劃分設(shè)計(jì)技,6.2,分治設(shè)計(jì)技術(shù),6.2.1,并行分治設(shè)計(jì)步驟,6.2.2,雙調(diào)歸并網(wǎng)絡(luò),2024/10/1,17,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,6.2 分治設(shè)計(jì)技術(shù) 6.2.1 并行分治設(shè)計(jì)步驟,并行分治設(shè)計(jì)步驟,將輸入劃分成若干個(gè)規(guī)模相等的子問題；,同時(shí),(,并行地,),遞歸求解這些子問題；,并行地歸并子問題的解，直至得到原問題的解。,2

9、024/10/1,18,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,并行分治設(shè)計(jì)步驟將輸入劃分成若干個(gè)規(guī)模相等的子問題；202,6.2,分治設(shè)計(jì)技術(shù),6.2.1,并行分治設(shè)計(jì)步驟,6.2.2,雙調(diào)歸并網(wǎng)絡(luò),2024/10/1,19,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,6.2 分治設(shè)計(jì)技術(shù) 6.2.1 并行分治設(shè)計(jì)步驟,雙調(diào)歸并網(wǎng)絡(luò),雙調(diào)序列,(p149,定義,6.2),(1,3,5,7,8,6,4,2,0),(8,7,6,4,2,0,1,3,5),(1,2,3,4,5,6,7,8,),以上都是雙調(diào)序列,Batcher,定理,給定雙調(diào)序列,(x,0,x,1,x,n-1,),對(duì)于,s,i,=minxi,xi+n/2,和,l,

10、i,=maxxi,xi+n/2,，,則小序列,(s,0,s,1,s,n-1,),和大序列,(,l,0,l,1,l,n-1,),仍是雙調(diào)序列,2024/10/1,20,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,雙調(diào)歸并網(wǎng)絡(luò)雙調(diào)序列(p149定義6.2)2022/10/,雙調(diào)歸并網(wǎng)絡(luò),(4,4),雙調(diào)歸并網(wǎng)絡(luò),2024/10/1,21,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,雙調(diào)歸并網(wǎng)絡(luò)(4,4)雙調(diào)歸并網(wǎng)絡(luò)2022/10/1021,雙調(diào)歸并網(wǎng)絡(luò),Batcher,雙調(diào)歸并算法,輸入：雙調(diào)序列,X=(x,0,x,1,x,n-1,),輸出：非降有序序列,Y=(y,0,y,1,y,n-1,),Procedure BITONIC_ME

11、RG(x),Begin,(1)for i=0 to n/2-1 par-do,(1.1)s,i,=minxi,xi+n/2,(1.2),l,i,=maxxi,xi+n/2,end for,(2)Recursive Call:,(2.1)BITONIC_MERG(MIN=(s,0,s,n/2-1,),(2.2)BITONIC_MERG(MIN=(,l,0,l,n/2-1,),(3)output sequence MIN followed by sequence MAX,End,2024/10/1,22,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,雙調(diào)歸并網(wǎng)絡(luò)Batcher雙調(diào)歸并算法2022/10/10,第六章

12、并行算法的基本設(shè)計(jì)技術(shù),6.1,劃分設(shè)計(jì)技術(shù),6.2,分治設(shè)計(jì)技術(shù),6.3,平衡樹設(shè)計(jì)技術(shù),6.4,倍增設(shè)計(jì)技術(shù),6.5,流水線設(shè)計(jì)技術(shù),2024/10/1,23,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,第六章 并行算法的基本設(shè)計(jì)技術(shù) 6.1 劃分設(shè)計(jì)技,6.3,平衡樹設(shè)計(jì)技術(shù),6.3.1,設(shè)計(jì)思想,6.3.2,求最大值,6.3.3,計(jì)算前綴和,2024/10/1,24,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,6.3 平衡樹設(shè)計(jì)技術(shù) 6.3.1 設(shè)計(jì)思想 6,平衡樹設(shè)計(jì)技術(shù),設(shè)計(jì)思想,以樹的葉結(jié)點(diǎn)為輸入，中間結(jié)點(diǎn)為處理結(jié)點(diǎn)，由葉向根或由根向葉逐層進(jìn)行并行處理。,示例,求最大值,計(jì)算前綴和,2024/10/1,25,現(xiàn)代密

13、碼學(xué)理論與實(shí)踐之五,平衡樹設(shè)計(jì)技術(shù)設(shè)計(jì)思想2022/10/1025現(xiàn)代密碼學(xué)理,6.3,平衡樹設(shè)計(jì)技術(shù),6.3.1,設(shè)計(jì)思想,6.3.2,求最大值,6.3.3,計(jì)算前綴和,2024/10/1,26,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,6.3 平衡樹設(shè)計(jì)技術(shù) 6.3.1 設(shè)計(jì)思想 6,求最大值,算法,6.8:SIMD-TC(SM),上求最大值算法,Begin,for k=m-1 to 0 do,for j=2,k,to 2,k+1,-1 par-do,Aj=maxA2j,A2j+1,end for,end for,end,圖示,時(shí)間分析,t(n)=mO(1)=O(logn),p(n)=n/2,A,1,A,

14、n/4,A,n/2-1,A,n/2,A,n/2+1,A,n-2,A,n-1,A,n,A,n+1,A,n+2,A,n+3,A,2n-4,A,2n-3,A,2n-2,A,2n-1,K=m-1,K=m-2,K=0,P,1,P,1,P,2,P,n/2-1,P,n/2,P,1,P,n/2-1,2024/10/1,27,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,求最大值算法6.8:SIMD-TC(SM)上求最大值算,6.3,平衡樹設(shè)計(jì)技術(shù),6.3.1,設(shè)計(jì)思想,6.3.2,求最大值,6.3.3,計(jì)算前綴和,2024/10/1,28,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,6.3 平衡樹設(shè)計(jì)技術(shù) 6.3.1 設(shè)計(jì)思想 6,計(jì)算前綴和,問

15、題定義,n,個(gè)元素,x,1,x,2,x,n,，前綴和是,n,個(gè)部分和：,S,i,=x,1,*x,2,*x,i,1in,這里*可以是或,串行算法：,S,i,=S,i,1,*x,i,計(jì)算時(shí)間為,O(n),并行算法：,p154,算法,6.9 SIMD-TC,上非遞歸算法,令,Ai=x,i,i=1n,Bh,j,和,Ch,j,為輔助數(shù)組,(h=0logn,j=1n/2,h,),數(shù)組,B,記錄由葉到根正向遍歷樹中各結(jié)點(diǎn)的信息,(,求和,),數(shù)組,C,記錄由根到葉反向遍歷樹中各結(jié)點(diǎn)的信息,(,播送前綴和,),2024/10/1,29,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,計(jì)算前綴和問題定義2022/10/1029現(xiàn)代密

16、碼學(xué)理論與,計(jì)算前綴和,例：,n=8,p=8,C,01,C,08,為前綴和,2024/10/1,30,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,計(jì)算前綴和例：n=8,p=8,C01C08為前綴和2,第六章 并行算法的基本設(shè)計(jì)技術(shù),6.1,劃分設(shè)計(jì)技術(shù),6.2,分治設(shè)計(jì)技術(shù),6.3,平衡樹設(shè)計(jì)技術(shù),6.4,倍增設(shè)計(jì)技術(shù),6.5,流水線設(shè)計(jì)技術(shù),2024/10/1,31,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,第六章 并行算法的基本設(shè)計(jì)技術(shù) 6.1 劃分設(shè)計(jì)技,6.4,倍增設(shè)計(jì)技術(shù),6.4.1,設(shè)計(jì)思想,6.4.2,表序問題,6.4.3,求森林的根,2024/10/1,32,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,6.4 倍增設(shè)計(jì)技術(shù) 6.4.1 設(shè)計(jì)思想 6.,倍增設(shè)計(jì)技術(shù),設(shè)計(jì)思想,又稱指針跳躍,(pointer jumping),技術(shù)，特別適合于處理鏈表或有向樹之類的數(shù)據(jù)結(jié)構(gòu)；,當(dāng)遞歸調(diào)用時(shí)，所要處理數(shù)據(jù)之間的距離逐步加倍，經(jīng)過,k,步后即可完成距離為,2,k,的所有數(shù)據(jù)的計(jì)算。,示例,表序問題,求森林的根,2024/10/1,33,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,倍增設(shè)計(jì)技術(shù)設(shè)計(jì)思想2022/10/1033現(xiàn)代密碼學(xué)理論,6.4,