1、并行算法的基本設(shè)計(jì)技術(shù)4.1 PA的一般設(shè)計(jì)方法4.2 PA的基本設(shè)計(jì)過(guò)程4.3 PA的常用設(shè)計(jì)技術(shù)PA的一般設(shè)計(jì)方法串行算法直接并行化借用法全新的方法串行算法直接并行化串行算法并非都可并行化好的串行算法不一定直接是好的并行算法很多數(shù)值運(yùn)算都可直接并行化串行算法直接并行化步驟 檢測(cè)和開發(fā)現(xiàn)有程序內(nèi)在的并行性并行編碼并行實(shí)現(xiàn)借用法找問(wèn)題與原有方法之間的關(guān)系設(shè)計(jì)相似算法有豐富的經(jīng)驗(yàn)基礎(chǔ)全新的方法根據(jù)一個(gè)給定問(wèn)題的描述，重新設(shè)計(jì)或發(fā)明一個(gè)并行算法一般可以得到較好的并行算法是一個(gè)具有挑戰(zhàn)性和創(chuàng)新性工作設(shè)計(jì)者應(yīng)有較好的理解能力和設(shè)計(jì)背景并行算法的基本設(shè)計(jì)技術(shù)4.1 PA的一般設(shè)計(jì)方法4.2 PA的基本設(shè)

2、計(jì)過(guò)程4.3 PA的常用設(shè)計(jì)技術(shù)劃分（P）目的開發(fā)并行性的可行性方法數(shù)據(jù)分解+功能分解規(guī)劃常用的數(shù)據(jù)，通信頻率的進(jìn)程分為一組判據(jù)（Check list 的設(shè)計(jì)問(wèn)題）通信（C）目的根據(jù)任務(wù)執(zhí)行的需要交換數(shù)據(jù)后；協(xié)調(diào)任務(wù)的執(zhí)行通信要求在域分解中的確定通信要求在功能分解時(shí)，容易確定通信需求通信（C）通信模式局部通信 結(jié)構(gòu)化 靜態(tài) 同步全局通信 非結(jié)構(gòu)化 動(dòng)態(tài) 異步判據(jù)（測(cè)試表的設(shè)計(jì)問(wèn)題）匹配（M）目的將每個(gè)任務(wù)分配到一個(gè)處理機(jī)上，降低通信開銷和執(zhí)行時(shí)間，提高處理機(jī)利用率判據(jù)（涉及策略，方法和測(cè)試表設(shè)計(jì)等問(wèn)題）并行算法的基本設(shè)計(jì)技術(shù)4.1 PA的一般設(shè)計(jì)方法4.2 PA的基本設(shè)計(jì)過(guò)程4.3 PA的常用

3、設(shè)計(jì)技術(shù)Outline4.3.1 劃分技術(shù)4.3.2 分治策略4.3.3 流水線技術(shù)4.3.4 倍增技術(shù)4.3.5 破對(duì)稱技術(shù)4.3.6平衡樹算法劃分方法基本出發(fā)點(diǎn)有效利用空閑處理器大問(wèn)題求解需要提高求解速度具體劃分方法均勻劃分法平方根劃分對(duì)數(shù)劃分隨機(jī)劃分功能劃分對(duì)數(shù)劃分法舉例問(wèn)題描述設(shè)兩非降數(shù)組 A=（a1,a2,an） B=（b1,b2,bm）其中l(wèi)ogm和K(m)=m/logm都是整數(shù)要求：K(m)配對(duì)A和B的子序列（Ai, Bi）,使得Bi=logm, Ai=n和對(duì)于所有1ik(m)-1,Ai和Bi中的每一個(gè)元素都大于Ai-1和Bi-1中的每一個(gè)元素對(duì)數(shù)劃分法舉例定義Rank(x:X)

4、表示x在X中的位序號(hào)方法描述先找B序列劃分點(diǎn) b1*logm b2*logm b(i+1)*logm再找A序列劃分點(diǎn) a(b1*logm:A) a(b2*logm:A) a(b(i+1)logm:A)然后分組歸并對(duì)數(shù)劃分法舉例-實(shí)現(xiàn)Begin j(0)0;j(k(m)-n for i=1 to k(m)-1 par_do (2.1) rank bi logm in A using binary search (2.2) j(i)rank(bi.logm:A) End for for i=0 to k(m)-1 par_do (3.1) Bi(bi.logm+1,b(i+1)logm) (3.2

5、) Ai230011204-070111011-1141110215-220010000-0151111011-140100000-050101011-160110113-081000102-2101010000-0111011011-1121100000-091001204-1131101215-0114215456810119131237241501013201450201201010010102Outline4.3.1 劃分方法4.3.2 分治策略4.3.3 流水線技術(shù)4.3.4 倍增技術(shù)4.3.5 破對(duì)稱技術(shù)4.3.6平衡樹算法平衡樹算法兩個(gè)例子求最大值求前綴和實(shí)例-求最大值問(wèn)題描述令

6、n=2m，A是一個(gè)2n維德數(shù)組；待求最大值n個(gè)數(shù)開始存放A（n），A（n+1），A（2n-1）；將求得的最大值于A（1）算法輸入：n=2m個(gè)數(shù)存在數(shù)組A（n:2n-1）中輸出：最大值置于A（1）中實(shí)例-求最大值算法實(shí)現(xiàn)Begin For k=m-1 to 0 do For j=2k to 2k+1-1 par_do A(j)MaxA(2j),A(2j+1) End for End forEnd實(shí)例-求最大值復(fù)雜度分析T(n)=O(logn)p(n)=n/2實(shí)例-求最大值例：（4,6,8,0）這里n=4,m=2,(n=2m), A=(0,0,0,0,4,6,8,0)解：K=m-1=1時(shí)，j=2k

7、=2時(shí)，A(j)=A(2)=maxA(4),A(5)=6 4 6 j=2k+1或-1=3時(shí)，A(j)=A(3)=maxA(6),A(7)=8 8 0 K=0時(shí)， j=1 to 1 A(1)=maxA(2),A(3)=8 6 8 實(shí)例求前綴和設(shè)SIMO*字模型中有 p=2qn2k 個(gè)處理器p1,pp 令l=n/p=2k-q,將輸入數(shù)組劃分成P個(gè)子數(shù)組，使得處理器ps負(fù)責(zé)處理器子數(shù)組A(l-(s-1)+1),A(l(s-1)+2),s(ls)在二叉樹高度H上，正向和反向便利中所產(chǎn)生的值B(h,.)和C(h,.)也以類似方式非配給各處理器實(shí)例求前綴和實(shí)例求前綴和算法實(shí)現(xiàn)Begin (1) for j

8、=1 to l=n/p do B(0,l(s-1)+j)=0) then for j=2k-h-q(s-1)+1 to 2k-h-qs doB(h,j)-B(h-1,2j-1)*B(h-1,2j) end for end if (2.2) if (s=2k-h) then B(h,s)=0) then for j=2k-h-q(s-1)+1 to 2k-h-qs do (1) if(j=even) then C(h,j)-C(h+1,j/2) end if (2) if(j=1) then C(h,1)1 then C(h,j)-C(h+1,(j-1)/2)*B(h,j) end if end

9、 for (3.2) if s2k-h then (1) if(s=even) then C(h,s)-C(h+1,s/2) end if (2) if(s=1) then C(h,1)1) then C(h,s)-C(h+1,(s-1)/2)*B(h,s) end if end if end for end實(shí)例求前綴和實(shí)例：n=8,p=2時(shí)求前綴和處理分布情況：p1p1p1p1p1p1p1p1p2p2p2p2p2p2p2實(shí)例求前綴和以p2情況為例第一步：p2將設(shè)置B(0,5)=A(5),(0,6)=a(6) B(0,7)=A(7),(0,7)=a(7)第二步：正向遍歷時(shí)，p2在h=1,2時(shí)是活動(dòng)的，在 h=3是空閑的，p2通過(guò)循環(huán)B(1,3),B(1,4) 和B(3,2)第三步：反向遍歷時(shí)，p2在h=3時(shí)是空閑的，而在 h=2時(shí)是活動(dòng)的因此，p2將產(chǎn)生：C(2,2),C(1,3),C(1,4),C(0,5),C(0,6),C(0,7),C(0,8)作業(yè)1. 在劃分設(shè)計(jì)技術(shù)