并行計算mpc高性能計算中心合肥

1、多核并行計算Multicore Parallel Computing主講人 徐 云第二篇 并行算法的設計 第四章 并行算法的設計基礎 第五章 并行算法的一般設計方法 第六章 并行算法的基本設計技術 第七章 并行算法的一般設計過程第六章 并行算法的基本設計技術 6.1 劃分設計技術 6.1.1 均勻劃分技術 6.1.2 方根劃分技術 6.1.3 對數(shù)劃分技術 6.1.4 功能劃分技術 6.2 分治設計技術 6.3 平衡樹設計技術 6.4 倍增設計技術 6.5 流水線設計技術國家高性能計算中心（合肥）42022/8/12 均勻劃分技術（1）劃分方法n個元素A1.n分成p組，每組A(i-1)n/p+

2、1.in/p，i=1p示例：MIMD-SM模型上的PSRS排序 begin (1)均勻劃分：將n個元素A1.n均勻劃分成p段，每個pi處理 A(i-1)n/p+1.in/p (2)局部排序：pi調(diào)用串行排序算法對A(i-1)n/p+1.in/p排序 (3)選取樣本：pi從其有序子序列A(i-1)n/p+1.in/p中選取p個樣本元素 (4)樣本排序：用一臺處理器對p2個樣本元素進行串行排序 (5)選擇主元：用一臺處理器從排好序的樣本序列中選取p-1個主元，并 播送給其他pi (6)主元劃分：pi按主元將有序段A(i-1)n/p+1.in/p劃分成p段 (7)全局交換：各處理器將其有序段按段號交

3、換到對應的處理器中 (8)歸并排序：各處理器對接收到的元素進行歸并排序 end.國家高性能計算中心（合肥）52022/8/12 均勻劃分技術（2）例6.1 PSRS排序過程。N=27，p=3，PSRS排序如下：第六章 并行算法的基本設計技術 6.1 劃分設計技術 6.1.1 均勻劃分技術 6.1.2 方根劃分技術 6.1.3 對數(shù)劃分技術 6.1.4 功能劃分技術 6.2 分治設計技術 6.3 平衡樹設計技術 6.4 倍增設計技術 6.5 流水線設計技術國家高性能計算中心（合肥）72022/8/12 方根劃分技術（1）劃分方法n個元素A1.n分成A(i-1)n(1/2)+1.in(1/2)，i

4、=1n(1/2) 示例：SIMD-CREW模型上的 Valiant歸并(1975年發(fā)表) /有序組A1.p、B1.q, (假設plogm=log4=2 = j1=rank(blogm:A)=rank(b2:A)=rank(9:A)=3, j2=8 B0: 3, 9 B1: 16, 21 A0: 4, 6, 7 A1: 10, 12, 15, 18, 20 A和B歸并化為(A0, B0)和(A1, B1)的歸并第六章 并行算法的基本設計技術 6.1 劃分設計技術 6.1.1 均勻劃分技術 6.1.2 方根劃分技術 6.1.3 對數(shù)劃分技術 6.1.4 功能劃分技術 6.2 分治設計技術 6.3

5、平衡樹設計技術 6.4 倍增設計技術 6.5 流水線設計技術國家高性能計算中心（合肥）132022/8/12 功能劃分技術（1）劃分方法 n個元素A1.n分成等長的p組，每組滿足某種特性。示例：(m, n)選擇問題(求出n個元素中前m個最小者)功能劃分：要求每組元素個數(shù)必須大于m；算法：p144算法6.4 輸入：A=(a1,an); 輸出：前m個最小者； Begin (1) 功能劃分：將A劃分成g=n/m組，每組含m個元素； (2) 局部排序：使用Batcher排序網(wǎng)絡將各組并行進行排序； (3) 兩兩比較：將所排序的各組兩兩進行比較，從而形成MIN序列； (4) 排序-比較：對各個MIN序列

6、，重復執(zhí)行第(2)和第(3)步，直至 選出m個最小者。 End國家高性能計算中心（合肥）142022/8/12 功能劃分技術（2）第六章 并行算法的基本設計技術 6.1 劃分設計技術 6.2 分治設計技術 6.2.1 并行分治設計步驟 6.2.2 雙調(diào)歸并網(wǎng)絡 6.3 平衡樹設計技術 6.4 倍增設計技術 6.5 流水線設計技術國家高性能計算中心（合肥）162022/8/12 并行分治設計步驟將輸入劃分成若干個規(guī)模相等的子問題；同時(并行地)遞歸求解這些子問題；并行地歸并子問題的解，直至得到原問題的解。第六章 并行算法的基本設計技術 6.1 劃分設計技術 6.2 分治設計技術 6.2.1 并行

7、分治設計步驟 6.2.2 雙調(diào)歸并網(wǎng)絡 6.3 平衡樹設計技術 6.4 倍增設計技術 6.5 流水線設計技術國家高性能計算中心（合肥）182022/8/12 雙調(diào)歸并網(wǎng)絡（1）雙調(diào)序列(p145定義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)序列(x0,x1,xn-1), 對于si=minxi,xi+n/2和 li=maxxi,xi+n/2，則小序列(s0,s1,sn-1)和大序列(l0,l1,ln-1) 仍是雙調(diào)序列。國家高性能計算中心（合肥）192022/8/12

8、雙調(diào)歸并網(wǎng)絡（2）(4,4)雙調(diào)歸并網(wǎng)絡國家高性能計算中心（合肥）202022/8/12 雙調(diào)歸并網(wǎng)絡（3）Batcher雙調(diào)歸并算法 輸入：雙調(diào)序列X=(x0,x1,xn-1) 輸出：非降有序序列Y=(y0,y1,yn-1) Procedure BITONIC_MERG(x) Begin (1)for i=0 to n/2-1 par-do (1.1) si=minxi,xi+n/2 (1.2) li=maxxi,xi+n/2 end for (2)Recursive Call: (2.1)BITONIC_MERG(MIN=(s0,sn/2-1) (2.2)BITONIC_MERG(MIN=

9、(l0, ln/2-1) (3)output sequence MIN followed by sequence MAX End第六章 并行算法的基本設計技術 6.1 劃分設計技術 6.2 分治設計技術 6.3 平衡樹設計技術 6.3.1 設計思想 6.3.2 求最大值 6.3.3 計算前綴和 6.4 倍增設計技術 6.5 流水線設計技術國家高性能計算中心（合肥）222022/8/12 平衡樹設計技術設計思想 以樹的葉結(jié)點為輸入，中間結(jié)點為處理結(jié)點，由葉向根或由根向葉逐層進行并行處理。示例求最大值計算前綴和 第六章 并行算法的基本設計技術 6.1 劃分設計技術 6.2 分治設計技術 6.3 平

10、衡樹設計技術 6.3.1 設計思想 6.3.2 求最大值 6.3.3 計算前綴和 6.4 倍增設計技術 6.5 流水線設計技術國家高性能計算中心（合肥）242022/8/12 求最大值（1）算法6.8: SIMD-TC(SM)上求最大值算法 Begin for k=m-1 to 0 do for j=2k to 2k+1-1 par-do Aj=maxA2j, A2j+1 end for end for end圖示時間分析 t(n)=mO(1)=O(logn) p(n)=n/2A1An/4An/2-1An/2An/2+1An-2An-1AnAn+1An+2An+3A2n-4A2n-3A2n-2

11、A2n-1K=m-1K=m-2K=0P1P1P2Pn/2-1Pn/2P1Pn/2-1國家高性能計算中心（合肥）252022/8/12 求最大值（2）SIMD-CRCW上常數(shù)時間求最大值算法算法2.10 SIMD-CRCW上枚舉算法/輸入A1.p，p個不同元素/B1.p1.p,M1.p為中間處理用的布爾數(shù)組, 如果Mi1, 則Ai為最大值begin (1)for 1i, jp par-do /工作量O(p2); 時間O(1),因為允許同時讀 if AiAj then Bi, j=1 else Bi, j=0 end if end for (2)for 1ip par-do /工作量O(p2);

12、時間O(1),因為允許同時寫 Mi=Bi,1 Bi,2 Bi,p end forendT(n)=O(1) W(n)=O(p2) 可以用p2個處理器實現(xiàn)速度雖快，但不是WT最優(yōu)第六章 并行算法的基本設計技術 6.1 劃分設計技術 6.2 分治設計技術 6.3 平衡樹設計技術 6.3.1 設計思想 6.3.2 求最大值 6.3.3 計算前綴和 6.4 倍增設計技術 6.5 流水線設計技術國家高性能計算中心（合肥）272022/8/12 計算前綴和（1）問題定義n個元素x1,x2,xn，前綴和是n個部分和：Si=x1*x2*xi, 1in 這里*可以是或串行算法： Si=Si1*xi 計算時間為 O

13、(n) 并行算法：p150算法6.9 SIMD-TC上非遞歸算法 令Ai=xi, i=1n, Bh,j和Ch,j為輔助數(shù)組(h=0logn, j=1n/2h) 數(shù)組B記錄由葉到根正向遍歷樹中各結(jié)點的信息(求和) 數(shù)組C記錄由根到葉反向遍歷樹中各結(jié)點的信息(播送前綴和)國家高性能計算中心（合肥）282022/8/12 計算前綴和（2）例：n=8, p=8, C01C08為前綴和國家高性能計算中心（合肥）292022/8/12 計算前綴和（3）SIMD-SM上非遞歸算法begin (1)for j=1 to n par-do /初始化 B0,j=Aj end if (2)for h=1 to lo

14、gn do /正向遍歷 for j=1 to n/2h par-do Bh,j=Bh-1,2j-1*Bh-1,2j end for end for 時間分析: (1) O(1) (2) O(logn) (3) O(logn) = t(n)=O(logn) , p(n)=n , c(n)=O(nlogn)(3)for h=logn to 0 do /反向遍歷 for j=1 to n/2h par-do (i) if j=even then /該結(jié)點為其父結(jié)點的右兒子 Ch,j=Ch+1,j/2 end if (ii) if j=1 then /該結(jié)點為最左結(jié)點 Ch,1=Bh,1 end if

15、 (iii) if j=odd1 then /該結(jié)點為其父結(jié)點的左兒子 Ch,j=Ch+1,(j-1)/2*Bh,j end if end for end for end第六章 并行算法的基本設計技術 6.1 劃分設計技術 6.2 分治設計技術 6.3 平衡樹設計技術 6.4 倍增設計技術 6.4.1 設計思想 6.4.2 表序問題 6.5 流水線設計技術國家高性能計算中心（合肥）312022/8/12 倍增設計技術設計思想又稱指針跳躍(pointer jumping)技術，特別適合于處理鏈表或有向樹之類的數(shù)據(jù)結(jié)構；當遞歸調(diào)用時，所要處理數(shù)據(jù)之間的距離逐步加倍，經(jīng)過k步后即可完成距離為2k的所

16、有數(shù)據(jù)的計算。示例表序問題第六章 并行算法的基本設計技術 6.1 劃分設計技術 6.2 分治設計技術 6.3 平衡樹設計技術 6.4 倍增設計技術 6.4.1 設計思想 6.4.2 表序問題 6.5 流水線設計技術國家高性能計算中心（合肥）332022/8/12 表序問題（1）問題描述 n個元素的列表L，求出每個元素在L 中的次第號(秩或位序或rank(k)， rank(k)可視為元素k至表尾的距離；示例：n=7 (1)pa=b, pb=c, pc=d, pd=e, pe=f, pf=g, pg=g ra=rb=rc=rd=re=rf=1, rg=0 (2)pa=c, pb=d, pc=e,

17、pd=f, pe=pf=pg=g ra=rb=rc=rd=re=2, rf=1, rg=0 (3)pa=e, pb=f, pc=pd=pe=pf=pg=g ra=4, rb=4, rc=4, rd=3, re=2, rf=1, rg=0 (4)pa=pb=pc=pd=pe=pf=pg=g ra=6, rb=5, rc=4, rd=3, re=2, rf=1, rg=0國家高性能計算中心（合肥）342022/8/12 表序問題（2）算法：P151算法6.10 (1)并行做：初始化pk和distancek /O(1) (2)執(zhí)行 次 /O(logn) (2.1)對k并行地做 /O(1) 如果k的后

18、繼不等于k的后繼之后繼，則 (i) distancek= distancek+ distancepk (ii) pk=ppk (2.2)對k并行地做 rankk=distancek /O(1) 運行時間：t(n)=O(logn) p(n)=n第六章 并行算法的基本設計技術 6.1 劃分設計技術 6.2 分治設計技術 6.3 平衡樹設計技術 6.4 倍增設計技術 6.5 流水線設計技術 6.5.1 設計思想 6.5.2 5-point DFT的計算 6.5.3 多線程軟件流水例子國家高性能計算中心（合肥）362022/8/12 流水線設計技術設計思想將算法流程劃分成p個前后銜接的任務片斷，每個任

19、務片斷的輸出作為下一個任務片斷的輸入；所有任務片斷按同樣的速率產(chǎn)生出結(jié)果。評注流水線技術是一種廣泛應用在并行處理中的技術；脈動算法(Systolic algorithm)是其中一種流水線技術；第六章 并行算法的基本設計技術 6.1 劃分設計技術 6.2 分治設計技術 6.3 平衡樹設計技術 6.4 倍增設計技術 6.5 流水線設計技術 6.5.1 設計思想 6.5.2 5-point DFT的計算 6.5.3 多線程軟件流水例子國家高性能計算中心（合肥）382022/8/12 5-point DFT的計算（1）問題描述 5-point DFT的計算。應用秦九韶(Horner)法則，國家高性能計算中心（合