并行計算,第一級,第二級,第三級,第一級,第二級,第三級,現(xiàn)代密碼學理論與實踐之五,*,*,并 行 計 算,中國科學技術大學計算機科學與技術系,國家高性能計算中心,(,合肥,),2004,年,12,月,2024/11/11,1,現(xiàn)代密碼學理論與實踐之五,并 行 計 算 中國科學技術大學計算機科學與技術系2023,第二篇 并行算法的設計,第四章 并行算法的設計基礎,第五章 并行算法的一般設計方法,第六章,并行算法的基本設計技術,第七章 并行算法的一般設計過程,2024/11/11,2,現(xiàn)代密碼學理論與實踐之五,第二篇 并行算法的設計 第四章 并行算法的設計基礎,第六章 并行算法的基本設計技術,6.1,劃分設計技術,6.2,分治設計技術,6.3,平衡樹設計技術,6.4,倍增設計技術,6.5,流水線設計技術,2024/11/11,3,現(xiàn)代密碼學理論與實踐之五,第六章 并行算法的基本設計技術 6.1 劃分設計技,6.1,劃分設計技術,6.1.1,均勻劃分技術,6.1.2,方根劃分技術,6.1.3,對數(shù)劃分技術,6.1.4,功能劃分技術,2024/11/11,4,現(xiàn)代密碼學理論與實踐之五,6.1 劃分設計技術 6.1.1 均勻劃分技術,均勻劃分技術,劃分方法,n,個元素,A1.n,分成,p,組，每組,A(i-1)n/p+1.in/p,，,i=1p,示例：,MIMD-SM,模型上的,PSRS,排序,begin,(1),均勻劃分：將,n,個元素,A1.n,均勻劃分成,p,段，每個,p,i,處理,A(i-1)n/p+1.in/p,(2),局部排序：,p,i,調用串行排序算法對,A(i-1)n/p+1.in/p,排序,(3),選取樣本：,p,i,從其有序子序列,A(i-1)n/p+1.in/p,中選取,p,個樣本元素,(4),樣本排序：用一臺處理器對,p,2,個樣本元素進行串行排序,(5),選擇主元：用一臺處理器從排好序的樣本序列中選取,p-1,個主元，并,播送給其他,p,i,(6),主元劃分：,p,i,按主元將有序段,A(i-1)n/p+1.in/p,劃分成,p,段,(7),全局交換：各處理器將其有序段按段號交換到對應的處理器中,(8),歸并排序：各處理器對接收到的元素進行歸并排序,end.,2024/11/11,5,現(xiàn)代密碼學理論與實踐之五,均勻劃分技術劃分方法2023/10/65現(xiàn)代密碼學理論與實,均勻劃分技術,例,6.1 PSRS,排序過程。

N=27,，,p=3,，,PSRS,排序如下,：,2024/11/11,6,現(xiàn)代密碼學理論與實踐之五,均勻劃分技術例6.1 PSRS排序過程N=27，p=3，,6.1,劃分設計技術,6.1.1,均勻劃分技術,6.1.2,方根劃分技術,6.1.3,對數(shù)劃分技術,6.1.4,功能劃分技術,2024/11/11,7,現(xiàn)代密碼學理論與實踐之五,6.1 劃分設計技術 6.1.1 均勻劃分技術,方根劃分技術,劃分方法,n,個元素,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,(,假設,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,),的歸并,2024/11/11,12,現(xiàn)代密碼學理論與實踐之五,對數(shù)劃分技術劃分方法2023/10/612現(xiàn)代密碼學理論與,6.1,劃分設計技術,6.1.1,均勻劃分技術,6.1.2,方根劃分技術,6.1.3,對數(shù)劃分技術,6.1.4,功能劃分技術,2024/11/11,13,現(xiàn)代密碼學理論與實踐之五,6.1 劃分設計技術 6.1.1 均勻劃分技術,功能劃分技術,劃分方法,n,個元素,A1.n,分成等長的,p,組，每組滿足某種特性。

示例：,(m,n),選擇問題,(,求出,n,個元素中前,m,個最小者,),功能劃分：要求每組元素個數(shù)必須大于,m,；,算法：,p148,算法,6.4,輸入：,A=(a1,an);,輸出：前,m,個最小者；,Begin,(1),功能劃分：將,A,劃分成,g=n/m,組，每組含,m,個元素；,(2),局部排序：使用,Batcher,排序網絡將各組并行進行排序；,(3),兩兩比較：將所排序的各組兩兩進行比較，從而形成,MIN,序列；,(4),排序,-,比較：對各個,MIN,序列，重復執(zhí)行第,(2),和第,(3),步，直至,選出,m,個最小者End,2024/11/11,14,現(xiàn)代密碼學理論與實踐之五,功能劃分技術劃分方法2023/10/614現(xiàn)代密碼學理論與,功能劃分技術,2024/11/11,15,現(xiàn)代密碼學理論與實踐之五,功能劃分技術2023/10/615現(xiàn)代密碼學理論與實踐之五,第六章 并行算法的基本設計技術,6.1,劃分設計技術,6.2,分治設計技術,6.3,平衡樹設計技術,6.4,倍增設計技術,6.5,流水線設計技術,2024/11/11,16,現(xiàn)代密碼學理論與實踐之五,第六章 并行算法的基本設計技術 6.1 劃分設計技,6.2,分治設計技術,6.2.1,并行分治設計步驟,6.2.2,雙調歸并網絡,2024/11/11,17,現(xiàn)代密碼學理論與實踐之五,6.2 分治設計技術 6.2.1 并行分治設計步驟,并行分治設計步驟,將輸入劃分成若干個規(guī)模相等的子問題；,同時,(,并行地,),遞歸求解這些子問題；,并行地歸并子問題的解，直至得到原問題的解。

2024/11/11,18,現(xiàn)代密碼學理論與實踐之五,并行分治設計步驟將輸入劃分成若干個規(guī)模相等的子問題；202,6.2,分治設計技術,6.2.1,并行分治設計步驟,6.2.2,雙調歸并網絡,2024/11/11,19,現(xiàn)代密碼學理論與實踐之五,6.2 分治設計技術 6.2.1 并行分治設計步驟,雙調歸并網絡,雙調序列,(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,),以上都是雙調序列,Batcher,定理,給定雙調序列,(x,0,x,1,x,n-1,),對于,s,i,=minxi,xi+n/2,和,l,i,=maxxi,xi+n/2,，,則小序列,(s,0,s,1,s,n-1,),和大序列,(,l,0,l,1,l,n-1,),仍是雙調序列,2024/11/11,20,現(xiàn)代密碼學理論與實踐之五,雙調歸并網絡雙調序列(p149定義6.2)2023/10/,雙調歸并網絡,(4,4),雙調歸并網絡,2024/11/11,21,現(xiàn)代密碼學理論與實踐之五,雙調歸并網絡(4,4)雙調歸并網絡2023/10/621現(xiàn),雙調歸并網絡,Batcher,雙調歸并算法,輸入：雙調序列,X=(x,0,x,1,x,n-1,),輸出：非降有序序列,Y=(y,0,y,1,y,n-1,),Procedure 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)代密碼學理論與實踐之五,雙調歸并網絡Batcher雙調歸并算法2023/10/62,第六章 并行算法的基本設計技術,6.1,劃分設計技術,6.2,分治設計技術,6.3,平衡樹設計技術,6.4,倍增設計技術,6.5,流水線設計技術,2024/11/11,23,現(xiàn)代密碼學理論與實踐之五,第六章 并行算法的基本設計技術 6.1 劃分設計技,6.3,平衡樹設計技術,6.3.1,設計思想,6.3.2,求最大值,6.3.3,計算前綴和,2024/11/11,24,現(xiàn)代密碼學理論與實踐之五,6.3 平衡樹設計技術 6.3.1 設計思想 6,平衡樹設計技術,設計思想,以樹的葉結點為輸入，中間結點為處理結點，由葉向根或由根向葉逐層進行并行處理。

示例,求最大值,計算前綴和,2024/11/11,25,現(xiàn)代密碼學理論與實踐之五,平衡樹設計技術設計思想2023/10/625現(xiàn)代密碼學理論,6.3,平衡樹設計技術,6.3.1,設計思想,6.3.2,求最大值,6.3.3,計算前綴和,2024/11/11,26,現(xiàn)代密碼學理論與實踐之五,6.3 平衡樹設計技術 6.3.1 設計思想 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,圖示,時間分析,t(n)=mO(1)=O(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)代密碼學理論與實踐之五,求最大值算法6.8:SIMD-TC(SM)上求最大值算,6.3,平衡樹設計技術,6.3.1,設計思想,6.3.2,求最大值,6.3.3,計算前綴和,2024/11/11,28,現(xiàn)代密碼學理論與實踐之五,6.3 平衡樹設計技術 6.3.1 設計思想 6,計算前綴和,問題定義,n,個元素,x,1,x,2,x,n,，前綴和是,n,個部分和：,S,i,=x,1,*x,2,*x,i,1in,這里*可以是或,串行算法：,S,i,=S,i,1,*x,i,計算時間為,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ù)組,C,記錄由根到葉反向遍歷樹中各結點的信息,(,播送前綴和,),2024/11/11,29,現(xiàn)代密碼學理論與實踐之五,計算前綴和問題定義2023/10/629現(xiàn)代密碼學理論與實,計算前綴和,例：,n=8,p=8,C,01,C,08,為前綴和,2024/11/11,30,現(xiàn)代密碼學理論與實踐之五,計算前綴和例：n=8,p=8,C01C08為前綴和2,第六章 并行算法的基本設計技術,6.1,劃分設計技術,6.2,分治設計技術,6.3,平衡樹設計技術,6.4,倍增設計技術,6.5,流水線設計技術,2024/11/11,31,現(xiàn)代密碼學理論與實踐之五,第六章 并行算法的基本設計技術 6.1 劃分設計技,6.4,倍增設計技術,6.4.1,設計思想,6.4.2,表序問題,6.4.3,求森林的根,2024/11/11,32,現(xiàn)代密碼學理論與實踐之五,6.4 倍增設計技術 6.4.1 設計思想 6.,倍增設計技術,設計思想,又稱指針跳躍,(pointer jumping),技術，特別適合于處理鏈表或有向樹之類的數(shù)據(jù)結構；,當遞歸調用時，所要處理數(shù)據(jù)之間的距離逐步加倍，經過,k,步后即可完成距離為,2,k,的所有數(shù)據(jù)的計算。

示例,表序問題,求森林的根,2024/11/11,33,現(xiàn)代密碼學理論與實踐之五,倍增設計技。