《并行計(jì)算ppt課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《并行計(jì)算ppt課件（45頁(yè)珍藏版）》請(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/11/11,1,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,并 行 計(jì) 算 中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系2023,第二篇 并行算法的設(shè)計(jì),第四章 并行算法的設(shè)計(jì)基礎(chǔ),第五章 并行算法的一般設(shè)計(jì)方法,第六章,并行算法的基本設(shè)計(jì)技術(shù),第七章 并行算法的一般設(shè)計(jì)過(guò)程,2024/11/11,2,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,第二篇 并行算法的設(shè)計(jì) 第四章 并行算法的設(shè)計(jì)基礎(chǔ),第六章 并行算法的基本設(shè)計(jì)技術(shù),6

2、.1,劃分設(shè)計(jì)技術(shù),6.2,分治設(shè)計(jì)技術(shù),6.3,平衡樹(shù)設(shè)計(jì)技術(shù),6.4,倍增設(shè)計(jì)技術(shù),6.5,流水線設(shè)計(jì)技術(shù),2024/11/11,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/11/11,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,

3、排序,begin,(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/11/11,5,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,均勻劃分技術(shù)劃分方法2023/10/65現(xiàn)代密碼學(xué)理論與實(shí),均勻劃分技術(shù),例,6.1 PSRS,排序過(guò)程。,N=27,，,p=3,，,PSRS,排序如下,：,2024/11/11,6,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,均勻劃分技術(shù)例6.1 PSRS排序過(guò)程。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/11/11,7,現(xiàn)代密碼學(xué)理論與

5、實(shí)踐之五,6.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

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

7、輸入：,A=(a1,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/11/11,14,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,功能劃分技術(shù)劃分方法2023/10/614現(xiàn)代密碼學(xué)理論與,功能劃分技術(shù),2024/11/11,15,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,功能劃分技術(shù)20

8、23/10/615現(xiàn)代密碼學(xué)理論與實(shí)踐之五,第六章 并行算法的基本設(shè)計(jì)技術(shù),6.1,劃分設(shè)計(jì)技術(shù),6.2,分治設(shè)計(jì)技術(shù),6.3,平衡樹(shù)設(shè)計(jì)技術(shù),6.4,倍增設(shè)計(jì)技術(shù),6.5,流水線設(shè)計(jì)技術(shù),2024/11/11,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/11/11,17,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,6.2 分治設(shè)計(jì)技術(shù) 6.2.1 并行分治設(shè)計(jì)步驟,并行分治設(shè)計(jì)步驟,將輸入劃分成若干個(gè)規(guī)模相等的子問(wèn)題；,同時(shí),(,并行地,),遞歸求解這些子問(wèn)題；,并行地歸并子問(wèn)題的解

9、，直至得到原問(wèn)題的解。,2024/11/11,18,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,并行分治設(shè)計(jì)步驟將輸入劃分成若干個(gè)規(guī)模相等的子問(wèn)題；202,6.2,分治設(shè)計(jì)技術(shù),6.2.1,并行分治設(shè)計(jì)步驟,6.2.2,雙調(diào)歸并網(wǎng)絡(luò),2024/11/11,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,=mi

10、nxi,xi+n/2,和,l,i,=maxxi,xi+n/2,，,則小序列,(s,0,s,1,s,n-1,),和大序列,(,l,0,l,1,l,n-1,),仍是雙調(diào)序列,2024/11/11,20,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,雙調(diào)歸并網(wǎng)絡(luò)雙調(diào)序列(p149定義6.2)2023/10/,雙調(diào)歸并網(wǎng)絡(luò),(4,4),雙調(diào)歸并網(wǎng)絡(luò),2024/11/11,21,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,雙調(diào)歸并網(wǎng)絡(luò)(4,4)雙調(diào)歸并網(wǎng)絡(luò)2023/10/621現(xiàn),雙調(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,),Pro

11、cedure BITONIC_MERG(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/11/11,22,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,雙調(diào)歸并網(wǎng)絡(luò)Batcher雙調(diào)歸

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

13、前綴和,2024/11/11,25,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,平衡樹(shù)設(shè)計(jì)技術(shù)設(shè)計(jì)思想2023/10/625現(xiàn)代密碼學(xué)理論,6.3,平衡樹(shù)設(shè)計(jì)技術(shù),6.3.1,設(shè)計(jì)思想,6.3.2,求最大值,6.3.3,計(jì)算前綴和,2024/11/11,26,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,6.3 平衡樹(shù)設(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

14、(logn),p(n)=n/2,A,1,A,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/11/11,27,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,求最大值算法6.8:SIMD-TC(SM)上求最大值算,6.3,平衡樹(shù)設(shè)計(jì)技術(shù),6.3.1,設(shè)計(jì)思想,6.3.2,求最大值,6.3.3,計(jì)算前綴和,2024/11/11,28,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,6.3 平衡樹(shù)設(shè)

15、計(jì)技術(shù) 6.3.1 設(shè)計(jì)思想 6,計(jì)算前綴和,問(wèn)題定義,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,記錄由葉到根正向遍歷樹(shù)中各結(jié)點(diǎn)的信息,(,求和,),數(shù)組,C,記錄由根到葉反向遍歷樹(shù)中各結(jié)點(diǎn)的信息,(,播送前綴和,),2024/11/11,29,現(xiàn)代密碼學(xué)理論與實(shí)踐之五

16、,計(jì)算前綴和問(wèn)題定義2023/10/629現(xiàn)代密碼學(xué)理論與實(shí),計(jì)算前綴和,例：,n=8,p=8,C,01,C,08,為前綴和,2024/11/11,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ù)設(shè)計(jì)技術(shù),6.4,倍增設(shè)計(jì)技術(shù),6.5,流水線設(shè)計(jì)技術(shù),2024/11/11,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,表序問(wèn)題,6.4.3,求森林的根,2024/11/11,32,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,6.4 倍增設(shè)計(jì)技術(shù) 6.4.1 設(shè)計(jì)思想 6.,倍增設(shè)計(jì)技術(shù),設(shè)計(jì)思想,又稱(chēng)指針跳躍,(pointer jumping),技術(shù)，特別適合于處理鏈表或有向樹(shù)之類(lèi)的數(shù)據(jù)結(jié)構(gòu)；,當(dāng)遞歸調(diào)用時(shí)，所要處理數(shù)據(jù)之間的距離逐步加倍，經(jīng)過(guò),k,步后即可完成距離為,2,k,的所有數(shù)據(jù)的計(jì)算。,示例,表序問(wèn)題,求森林的根,2024/11/11,33,現(xiàn)代密碼學(xué)理論與實(shí)踐之五,倍增設(shè)計(jì)技