[計(jì)算機(jī)軟件及應(yīng)用]并行計(jì)算4算法ppt課件

1、并行算法1 普通設(shè)計(jì)方法并行算法的普通設(shè)計(jì)方法 串行算法的直接并行化 從問題描畫開場設(shè)計(jì)并行算法 借用已有算法求解新問題串行算法的直接并行化 設(shè)計(jì)方法描畫 快排序算法的并行化 設(shè)計(jì)方法的描畫 方法描畫 開掘和利用現(xiàn)有串行算法中的并行性，直接將串行算法改造為并行算法。 許多并行編程言語都支持經(jīng)過在原有的串行程序中參與并行原語例如某些通訊命令等的方法將串行程序并行化。 設(shè)計(jì)方法的描畫 評(píng)注 由串行算法直接并行化的方法是并行算法設(shè)計(jì)的最常用方法之一； 不是一切的串行算法都可以直接并行化的；某些串行算法有內(nèi)在的串行性，比如在某些串行算法中，每一步都要用到上一步的結(jié)果。只需當(dāng)上一步完全終了后，下一步才干

2、開場。這樣，各步之間就不能并行，只能思索其它的并行化方法。例如模擬退火算法，每個(gè)溫度下迭代的出發(fā)點(diǎn)是上一個(gè)溫度下迭代的終了點(diǎn)。這樣就很難直接將各個(gè)溫度的迭代并行起來。 設(shè)計(jì)方法的描畫 評(píng)注 一個(gè)好的串行算法并不能并行化為一個(gè)好的并行算法；另一方面，不好的串行算法并行化后也能夠是優(yōu)秀的并行算法。例如，串行算法中是沒有冗余計(jì)算的。但是在并行算法中，運(yùn)用適當(dāng)?shù)娜哂嘤?jì)算也能夠使并行算法效率更高。參與冗余計(jì)算的并行算法就能夠比直接由串行算法并行化得到的算法效率高。又比如，枚舉不是一種好的串行算法。但是將其直接并行化后可以得到比較好的并行算法。 許多數(shù)值串行算法可以并行化為有效的數(shù)值并行算法。設(shè)計(jì)方法的描

3、畫 假設(shè)我們想用求和的方法進(jìn)展數(shù)值積分。設(shè)被積函數(shù)為f(x)，積分區(qū)間為a,b。為了積分，將區(qū)間a,b均勻分成N個(gè)小區(qū)間，每個(gè)小區(qū)間長 ，根據(jù)積分的定義 是第i 個(gè)小區(qū)間左端點(diǎn)的坐標(biāo)，而 是f(x)在第i 個(gè)小區(qū)間上積分的近似值。假設(shè)運(yùn)用串行算法，可以用循環(huán)和疊加完成上述求和。這個(gè)串行算法可以直接并行化。 設(shè)計(jì)方法的描畫 假設(shè)有k臺(tái)處置器，可以把這N個(gè)小區(qū)間上的計(jì)算義務(wù)分到各處置器：0號(hào)處置器擔(dān)任第 個(gè)小區(qū)間上的計(jì)算和累加，1號(hào)處置器擔(dān)任第 個(gè)小區(qū)間上的計(jì)算和累加，k-1號(hào)處置器擔(dān)任第 個(gè)小區(qū)間上的計(jì)算和累加。k個(gè)處置器并行地計(jì)算出部分和，然后再把結(jié)果加到一同。設(shè)計(jì)方法的描畫 快排序算法的并行

4、化算法 PRAM-CRCW上的快排序二叉樹構(gòu)造算法 輸入：序列(A1,An)和n個(gè)處置器 輸出：供排序用的一棵二叉排序樹 Begin (1)for each processor i do (2)repeat for each processor iroot do (1.1)root=i if (AiAfi)(Ai=Afiifi) then (1.2)fi=root (2.1)LCfi=i (1.3)LCi=RCi=n+1 (2.2)if i=LCfi then exit else fi=LCfi endif end for else (2.3)RCfi=i (2.4)if i=RCfi the

5、n exit else fi=RCfi endif endif end repeat End 從問題描畫開場設(shè)計(jì)并行算法 方法描畫 從問題本身描畫出發(fā)，不思索相應(yīng)的串行算法，設(shè)計(jì)一個(gè)全新的并行算法。 評(píng)注 發(fā)掘問題的固有特性與并行的關(guān)系； 設(shè)計(jì)全新的并行算法是一個(gè)挑戰(zhàn)性和發(fā)明性的任務(wù)； 利用串的周期性的PRAM-CRCW算法是一個(gè)很好的范例；并行串匹配算法 給定長度為n的正文串T和長度為m的方式串P，找出P在T中一切出現(xiàn)的位置稱為串匹配問題。 研討發(fā)現(xiàn)，兩串能否匹配是與串本身的特性有關(guān)的。這種特性，就是串的周期性。 串可以分為周期的和非周期的。 可以引入見證函數(shù)Witness Function

6、來判別串的周期性。確定了串的周期性后就可以先研討非周期串的匹配，然后在此根底上再研討周期串的匹配。 并行串匹配算法 對(duì)于非周期串的研討，就是如何利用見證函數(shù)快速地找出P在T中的位置。為此，引入競爭函數(shù)duel(p,q) 。 先把正文串分成小段，借助于見證函數(shù)并行地計(jì)算競爭函數(shù)值，找出那些能夠匹配的位置。然后逐漸擴(kuò)展正文串分段的長度，并計(jì)算競爭函數(shù)值，在能夠匹配的位置中排除那些不能夠匹配的位置。最后在剩下的能夠位置中驗(yàn)證哪些是符合要求的位置。并行串匹配算法假設(shè)T=abaababaababaababaababa，n=23，P=abaababa，m=8。由見證函數(shù)可知P是非周期串。由于P只能夠在前1

7、6個(gè)位置上與T匹配，所以在找一切“能夠位置時(shí)只思索T的前16個(gè)字符。匹配時(shí)，先要計(jì)算見證函數(shù)值，然后由其計(jì)算 的值，找到能夠匹配的位置。計(jì)算duel(p,q)時(shí)，可以一切的塊并行計(jì)算。先將P和T分生長度為2的塊，用方式塊(ab) 與正文塊(ab)(aa)(ba)(ba)(ab)(ab)(aa)(ba)進(jìn)展匹配可知方式塊(ab)在位置1，4，6，9，11，14，16即duel(p,q)的獲勝者出現(xiàn)匹配。再把P與T劃分生長度為4的塊，用方式塊(abaa)與正文塊(abaa)(baba)(abab)(aaba)進(jìn)展匹配, 可知在位置1，6，11，16出現(xiàn)匹配位置4、9、14被淘汰；最后用方式串(ab

8、aababa)在正文串的位置1，6，11，16進(jìn)展檢查，排除那些不匹配的位置。本例中這4個(gè)位置都匹配。借用已有算法求解新問題 設(shè)計(jì)方法描畫 利用矩陣乘法求一切點(diǎn)對(duì)間最短途徑 設(shè)計(jì)方法的描畫 方法描畫 找出求解問題和某個(gè)已處理問題之間的聯(lián)絡(luò)； 改造或利用知算法運(yùn)用到求解問題上。 評(píng)注 這是一項(xiàng)發(fā)明性的任務(wù)； 運(yùn)用矩陣乘法算法求解一切點(diǎn)對(duì)間最短途徑是一個(gè)很好的范例。利用矩陣乘法求一切點(diǎn)對(duì)間最短途徑計(jì)算原理設(shè)在一有向圖中，各弧都賦予了非負(fù)整數(shù)權(quán)。圖中一條途徑的長度定義為該途徑上一切的弧的權(quán)的和。圖中兩結(jié)點(diǎn)之間的最短途徑是指它們之間長度最短的途徑。設(shè)G為一個(gè)含有n個(gè)結(jié)點(diǎn)的有向圖。矩陣W=(wij)是G

9、中各弧上的權(quán)構(gòu)成的矩陣，即W的元素wij是G中結(jié)點(diǎn)vi到結(jié)點(diǎn)vj的弧上的權(quán)假設(shè)vi到vj無弧，那么令wij=。我們的目的是計(jì)算G中一切結(jié)點(diǎn)對(duì)之間的最短路。為此，記dij為結(jié)點(diǎn)vi到結(jié)點(diǎn)vj的最短路長，并記D=(dij)。用dij k表示從vi到vj至多經(jīng)過k-1個(gè)中間結(jié)點(diǎn)的一切途徑的長度的最小值，記Dk=(dijk) 。因此dij 1=wijij， dij 1=0 i=j。假設(shè)假設(shè)G中不包含權(quán)為負(fù)的有向圈，那么dij = dij n-1，D=Dn-1利用矩陣乘法求一切點(diǎn)對(duì)間最短途徑 根據(jù)組合最優(yōu)原理Combinatorial Optimization Principle有 從而可以從D1 開場

10、，逐次計(jì)算出D2 ， D4 ， D8，Dn-1=D。為了從Dk/2計(jì)算Dk，可以借用規(guī)范的矩陣乘法。矩陣乘法執(zhí)行的計(jì)算是 只需將矩陣乘法中的乘法操作換成加法操作，把矩陣乘法中的求和換求最小值操作即可。 利用矩陣乘法求一切點(diǎn)對(duì)間最短途徑計(jì)算原理 有向圖G=(V,E)，邊權(quán)矩陣W=(wij)nn，求最短途徑長度矩陣D=(dij)nn，dij為vi到vj的最短途徑長度。假定圖中無負(fù)權(quán)有向回路，記d(k)ij為vi到vj至多有k-1個(gè)中間結(jié)點(diǎn)的最短途徑長，Dk=(d(k)ij)nn，那么 (1) d(1)ij=wij 當(dāng) ij (假設(shè)vi到vj之間無邊存在記為) d(1)ij=0 當(dāng) i=j (2)

11、無負(fù)權(quán)回路 dijd(n-1)ij (3) 利用最優(yōu)組合原理：d(k)ij=min1lnd(k/2)il+d(k/2)lj 視：+ “， “min “，那么上式變?yōu)?d(k)ij=1lnd(k/2)ild(k/2)lj (4) 運(yùn)用矩陣乘法：D1 D2 D4 D2logn (= Dn)SIMD-CC上的并行算法：p算法5.5并行算法2 根本設(shè)計(jì)技術(shù)并行算法的根本設(shè)計(jì)技術(shù) 劃分設(shè)計(jì)技術(shù) 分治設(shè)計(jì)技術(shù) 平衡樹設(shè)計(jì)技術(shù) 倍增設(shè)計(jì)技術(shù) 流水線設(shè)計(jì)技術(shù)劃分設(shè)計(jì)技術(shù) 均勻劃分技術(shù) 方根劃分技術(shù) 對(duì)數(shù)劃分技術(shù) 功能劃分技術(shù) 均勻劃分技術(shù)劃分方法n個(gè)元素A1.n分成p組，每組A(i-1)n/p+1.in/p，

12、i=1p例如：MIMD-SM模型上的PSRS排序 begin (1)均勻劃分：將n個(gè)元素A1.n均勻劃分成p段，每個(gè)pi處置 A(i-1)n/p+1.in/p (2)部分排序：pi調(diào)用串行排序算法對(duì)A(i-1)n/p+1.in/p排序 (3)選取樣本：pi從其有序子序列A(i-1)n/p+1.in/p中選取p個(gè)樣本元素 (4)樣本排序：用一臺(tái)處置器對(duì)p2個(gè)樣本元素進(jìn)展串行排序 (5)選擇主元：用一臺(tái)處置器從排好序的樣本序列中選取p-1個(gè)主元，并 廣播給其他pi (6)主元?jiǎng)澐郑簆i按主元將有序段A(i-1)n/p+1.in/p劃分成p段 (7)全局交換：各處置器將其有序段按段號(hào)交換到對(duì)應(yīng)的處置

13、器中 (8)歸并排序：各處置器對(duì)接納到的元素進(jìn)展歸并排序 end. 均勻劃分技術(shù)例 PSRS排序過程。N=27，p=3，PSRS排序如下： 方根劃分技術(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(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歸并化為

14、(A0, B0)和(A1, B1)的歸并 功能劃分技術(shù)劃分方法 n個(gè)元素A1.n分成等長的p組，每組滿足某種特性。例如：(m, n)選擇問題(求出n個(gè)元素中前m個(gè)最小者)功能劃分：要求每組元素個(gè)數(shù)必需大于m；算法：p148算法6.4 輸入：A=(a1,an); 輸出：前m個(gè)最小者； Begin (1) 功能劃分：將A劃分成g=n/m組，每組含m個(gè)元素； (2) 部分排序：運(yùn)用Batcher排序網(wǎng)絡(luò)將各組并行進(jìn)展排序； (3) 兩兩比較：將所排序的各組兩兩進(jìn)展比較，從而構(gòu)成MIN序列； (4) 排序-比較：對(duì)各個(gè)MIN序列，反復(fù)執(zhí)行第(2)和第(3)步，直至 選出m個(gè)最小者。 End 功能劃分技

15、術(shù)分治設(shè)計(jì)技術(shù) 并行分治設(shè)計(jì)步驟 雙調(diào)歸并網(wǎng)絡(luò) 并行分治設(shè)計(jì)步驟 將輸入劃分成假設(shè)干個(gè)規(guī)模相等的子問題； 同時(shí)(并行地)遞歸求解這些子問題； 并行地歸并子問題的解，直至得到原問題的解。 雙調(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)序列(x0,x1,xn-1), 對(duì)于si=minxi,xi+n/2和 li=maxxi,xi+n/2， 那么小序列(s0,s1,sn-1)和大序列(l0,l1,ln-1) 仍是雙調(diào)序列 雙調(diào)歸并網(wǎng)絡(luò) (4,

16、4)雙調(diào)歸并網(wǎng)絡(luò) 雙調(diào)歸并網(wǎng)絡(luò)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=(l0, ln/2-1) (3)output sequence MIN fol

17、lowed by sequence MAX End平衡樹設(shè)計(jì)技術(shù) 設(shè)計(jì)思想 求最大值 計(jì)算前綴和 平衡樹設(shè)計(jì)技術(shù) 設(shè)計(jì)思想 以樹的葉結(jié)點(diǎn)為輸入，中間結(jié)點(diǎn)為處置結(jié)點(diǎn)，由葉向根或由根向葉逐層進(jìn)展并行處置。 例如 求最大值 計(jì)算前綴和 求最大值算法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圖示時(shí)間分析 t(n)=mO(1)=O(logn) p(n)=n/2A1An/4An/2-1An/2An/2+1An-2An-1AnAn+

18、1 An+2An+3A2n-4 A2n-3 A2n-2A2n-1K=m-1K=m-2K=0P1P1P2Pn/2-1Pn/2P1Pn/2-1 計(jì)算前綴和 問題定義 n個(gè)元素x1,x2,xn，前綴和是n個(gè)部分和： Si=x1*x2*xi, 1in 這里*可以是或 串行算法： Si=Si1*xi 計(jì)算時(shí)間為 O(n) 并行算法：p154算法6.9 SIMD-TC上非遞歸算法 令A(yù)i=xi, i=1n, Bh,j和Ch,j為輔助數(shù)組(h=0logn, j=1n/2h) 數(shù)組B記錄由葉到根正向遍歷樹中各結(jié)點(diǎn)的信息(求和) 數(shù)組C記錄由根到葉反向遍歷樹中各結(jié)點(diǎn)的信息(廣播前綴 和) 計(jì)算前綴和例：n=8,

19、 p=8, C01C08為前綴和倍增設(shè)計(jì)技術(shù) 設(shè)計(jì)思想 表序問題 求森林的根 倍增設(shè)計(jì)技術(shù) 設(shè)計(jì)思想 又稱指針騰躍(pointer jumping)技術(shù)，特別適宜于處置鏈表或有向樹之類的數(shù)據(jù)構(gòu)造； 當(dāng)遞歸調(diào)用時(shí)，所要處置數(shù)據(jù)之間的間隔逐漸加倍，經(jīng)過k步后即可完成間隔為2k的一切數(shù)據(jù)的計(jì)算。 例如 表序問題 求森林的根 表序問題問題描畫 n個(gè)元素的列表L，求出每個(gè)元素在L 中的次第號(hào)(秩或位序或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, r

20、g=0 (2)pa=c, pb=d, pc=e, 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 表序問題算法：P155算法6.10 (1)并行做：初始化pk和distancek /O(1) (2)執(zhí)行 次 /O(logn) (2.1)對(duì)k并行地做 /O(1) 假設(shè)k的后繼不

21、等于k的后繼之后繼，那么 (i) distancek= distancek+ distancepk (ii) pk=ppk (2.2)對(duì)k并行地做 rankk=distancek /O(1) 運(yùn)轉(zhuǎn)時(shí)間：t(n)=O(logn) p(n)=nnlog 求森林的根問題描畫 一組有向樹F中, 假設(shè)是F中的一條弧，那么pi=j(即j是i的雙親)；假設(shè)i為根，那么pi=i。求每個(gè)結(jié)點(diǎn)j(j=1n)的樹根sj.例如 初始時(shí) P1=p2=5 p3=p4=p5=6 P6=p7=8 p8=8 P9=10 p10=11 p11=12 p12=13 p13=13 si=pi 求森林的根 例如 第一次迭代后 第二次迭

22、代后 算法：P157算法6.11 運(yùn)轉(zhuǎn)時(shí)間：t(n)=O(logn) W(n)=O(nlogn)流水線設(shè)計(jì)技術(shù) 設(shè)計(jì)思想 5-point DFT的計(jì)算 流水線設(shè)計(jì)技術(shù) 設(shè)計(jì)思想 將算法流程劃分成p個(gè)前后銜接的義務(wù)片斷，每個(gè)義務(wù)片斷的輸出作為下一個(gè)義務(wù)片斷的輸入； 一切義務(wù)片斷按同樣的速率產(chǎn)生出結(jié)果。 評(píng)注 流水線技術(shù)是一種廣泛運(yùn)用在并行處置中的技術(shù)； 脈動(dòng)算法(Systolic algorithm)是其中一種流水線技術(shù)； 5-point DFT的計(jì)算問題描畫 5-point DFT的計(jì)算。運(yùn)用秦九韶(Horner)法那么，041424344403132333430212223242011121

23、31410010203040021426316444021426312433021426384220112233441100102030400)()()()()(aaaaayaaaaayaaaaayaaaaayaaaaayaaaaabyaaaaabyaaaaabyaaaaabyaaaaaby 5-point DFT的計(jì)算例如：p(n)=n-1, t(n)=2n-2=O(n) 并行算法3 普通設(shè)計(jì)過程并行算法的普通設(shè)計(jì)過程 PCAM設(shè)計(jì)方法學(xué) 劃分 通訊 組合 映射 小結(jié) PCAM設(shè)計(jì)方法學(xué) 設(shè)計(jì)并行算法的四個(gè)階段 劃分(Partitioning) 通訊(Communication) 組合(Ag

24、glomeration) 映射(Mapping) 劃分：分解成小的義務(wù)，開辟并發(fā)性； 通訊：確定諸義務(wù)間的數(shù)據(jù)交換，監(jiān)測(cè)劃分的合理性； 組合：根據(jù)義務(wù)的部分性，組合成更大的義務(wù)； 映射：將每個(gè)義務(wù)分配四處置器上，提高算法的性能。 PCAM設(shè)計(jì)過程劃分 方法描畫 域分解 功能分解 劃分判據(jù) 劃分方法描畫 充分開辟算法的并發(fā)性和可擴(kuò)放性； 先進(jìn)展數(shù)據(jù)分解(稱域分解)，再進(jìn)展計(jì)算功能的分解(稱功能分解)； 使數(shù)據(jù)集和計(jì)算集互不相交； 劃分階段忽略處置器數(shù)目和目的機(jī)器的體系構(gòu)造； 能分為兩類劃分： 域分解(domain decomposition) 功能分解(functional decomposit

25、ion)域分解 劃分的對(duì)象是數(shù)據(jù)，可以是算法的輸入數(shù)據(jù)、中間處置數(shù)據(jù)和輸出數(shù)據(jù)； 將數(shù)據(jù)分解成大致相等的小數(shù)據(jù)片； 劃分時(shí)思索數(shù)據(jù)上的相應(yīng)操作； 假設(shè)一個(gè)義務(wù)需求別的義務(wù)中的數(shù)據(jù)，那么會(huì)產(chǎn)生義務(wù)間的通訊；域分解域分解Domain Decomposition也叫數(shù)據(jù)劃分，劃分的對(duì)象是數(shù)據(jù)。這些數(shù)據(jù)可以是算法或程序的輸入數(shù)據(jù)、計(jì)算的中間結(jié)果或計(jì)算的輸出數(shù)據(jù)。域分解的步驟是：首先分解與問題相關(guān)的數(shù)據(jù)，假設(shè)能夠的話，應(yīng)使每份數(shù)據(jù)的數(shù)據(jù)量大體相等；然后再將每個(gè)計(jì)算關(guān)聯(lián)到它所操作的數(shù)據(jù)上。由此就產(chǎn)生出一些義務(wù)，每個(gè)義務(wù)包括一些數(shù)據(jù)及其上的操作。當(dāng)一個(gè)操作需求別的義務(wù)中的數(shù)據(jù)時(shí)，就會(huì)產(chǎn)生通訊要求。域分解的閱

26、歷方法是：優(yōu)先集中在最大數(shù)據(jù)的劃分和經(jīng)常被訪問的數(shù)據(jù)構(gòu)造上。在不同的階段，能夠要對(duì)不同的數(shù)據(jù)構(gòu)造進(jìn)展操作或需求對(duì)同一數(shù)據(jù)構(gòu)造進(jìn)展不同的分解。在此情況下，要分別對(duì)待，然后再將各階段設(shè)計(jì)的分解與算法裝配到一同。域分解 例如：三維網(wǎng)格的域分解，各格點(diǎn)上計(jì)算都是反復(fù)的。以下圖是三種分解方法：域分解 不規(guī)那么區(qū)域的分解例如：功能分解 劃分的對(duì)象是計(jì)算，將計(jì)算劃分為不同的義務(wù)，其出發(fā)點(diǎn)不同于域分解； 劃分后，研討不同義務(wù)所需的數(shù)據(jù)。假設(shè)這些數(shù)據(jù)不相交的，那么劃分是勝利的；假設(shè)數(shù)據(jù)有相當(dāng)?shù)闹丿B， 意味著要重新進(jìn)展域分解和功能分解； 功能分解是一種更深層次的分解。功能分解 功能分解功能分解Functional

27、 DecompositionFunctional Decomposition也叫計(jì)算劃分，也叫計(jì)算劃分，它首先關(guān)注被執(zhí)行的計(jì)算的分解，而不是計(jì)算所需的數(shù)據(jù)，它首先關(guān)注被執(zhí)行的計(jì)算的分解，而不是計(jì)算所需的數(shù)據(jù)，然后，假設(shè)所作的計(jì)算劃分是成動(dòng)的，再繼續(xù)研討計(jì)算所然后，假設(shè)所作的計(jì)算劃分是成動(dòng)的，再繼續(xù)研討計(jì)算所需的數(shù)據(jù)。假設(shè)這些數(shù)據(jù)是不相交或相交很少的，就意味需的數(shù)據(jù)。假設(shè)這些數(shù)據(jù)是不相交或相交很少的，就意味著劃分是勝利的；假設(shè)這些數(shù)據(jù)有相當(dāng)?shù)闹丿B，就會(huì)產(chǎn)生著劃分是勝利的；假設(shè)這些數(shù)據(jù)有相當(dāng)?shù)闹丿B，就會(huì)產(chǎn)生大量的通訊，此時(shí)就暗示應(yīng)思索數(shù)據(jù)分解。大量的通訊，此時(shí)就暗示應(yīng)思索數(shù)據(jù)分解。 雖然大多數(shù)并行

28、算法采用域分解，但功能分解有時(shí)能提示雖然大多數(shù)并行算法采用域分解，但功能分解有時(shí)能提示問題的內(nèi)在構(gòu)造，展現(xiàn)出優(yōu)化的時(shí)機(jī)。單對(duì)數(shù)據(jù)進(jìn)展研討問題的內(nèi)在構(gòu)造，展現(xiàn)出優(yōu)化的時(shí)機(jī)。單對(duì)數(shù)據(jù)進(jìn)展研討往往很難做到這一點(diǎn)。往往很難做到這一點(diǎn)。 功能分解的一個(gè)例子是搜索樹。搜索樹沒有明顯的可分解功能分解的一個(gè)例子是搜索樹。搜索樹沒有明顯的可分解的數(shù)據(jù)構(gòu)造，但易于進(jìn)展細(xì)粒度的功能分解：開場時(shí)根生的數(shù)據(jù)構(gòu)造，但易于進(jìn)展細(xì)粒度的功能分解：開場時(shí)根生成一個(gè)義務(wù)，對(duì)其評(píng)價(jià)后，假設(shè)它不是一個(gè)解，就生成假成一個(gè)義務(wù)，對(duì)其評(píng)價(jià)后，假設(shè)它不是一個(gè)解，就生成假設(shè)干葉結(jié)點(diǎn)，這些葉結(jié)點(diǎn)可以分到各個(gè)處置器上并行地繼設(shè)干葉結(jié)點(diǎn)，這些葉結(jié)點(diǎn)

29、可以分到各個(gè)處置器上并行地繼續(xù)搜索。續(xù)搜索。功能分解 例如1：搜索樹 例如2：氣候模型劃分判據(jù) 劃分能否具有靈敏性？ 劃分能否防止了冗余計(jì)算和存儲(chǔ)？ 劃分義務(wù)尺寸能否大致相當(dāng)？ 義務(wù)數(shù)與問題尺寸能否成比例？ 功能分解是一種更深層次的分解，能否合理？劃分判據(jù)1所劃分的義務(wù)數(shù)能否高于目的機(jī)上處置器數(shù)目一個(gè)量級(jí)？假設(shè)不是，在后面的設(shè)計(jì)步驟中將短少靈敏性。2劃分能否防止了冗余的計(jì)算和存儲(chǔ)要求？假設(shè)不是，那么產(chǎn)生的算法對(duì)大型問題能夠不是可擴(kuò)展的。3各義務(wù)的尺寸能否大致相當(dāng)？假設(shè)不是，那么分配處置器時(shí)很難做到負(fù)載平衡。4劃分的義務(wù)數(shù)能否與問題尺寸成比例？理想情況下，問題尺寸的添加應(yīng)引起義務(wù)數(shù)的添加而不是義

30、務(wù)尺寸的添加。假設(shè)不是這樣，算法能夠不能求解更大的問題，雖然有更多的處置器。5能否采用了幾種不同的劃分法？多思索幾種選擇可以提高靈敏性。同時(shí)既要思索域分解又要思索功能分解。 通訊 方法描畫 四種通訊方式 通訊判據(jù) 通訊方法描畫 通訊是PCAM設(shè)計(jì)過程的重要階段； 劃分產(chǎn)生的諸義務(wù)，普通不能完全獨(dú)立執(zhí)行，需求在義務(wù)間進(jìn)展數(shù)據(jù)交流；從而產(chǎn)生了通訊； 功能分解確定了諸義務(wù)之間的數(shù)據(jù)流； 諸義務(wù)是并發(fā)執(zhí)行的，通訊那么限制了這種并發(fā)性； 四種通訊方式 部分/全局通訊:部分通訊中，每個(gè)義務(wù)只與少數(shù)的幾個(gè)近鄰義務(wù)通訊；全局通訊中，每個(gè)義務(wù)要與很多別的義務(wù)通訊。 構(gòu)造化/非構(gòu)造化通訊:構(gòu)造化通訊中，一個(gè)義務(wù)和

31、其近鄰構(gòu)成規(guī)那么的構(gòu)造如樹、網(wǎng)格等；非構(gòu)造化通訊中，通訊網(wǎng)能夠是恣意圖。 靜態(tài)/動(dòng)態(tài)通訊:靜態(tài)通訊中，通訊同伴不隨時(shí)間變化；動(dòng)態(tài)通訊中，通訊同伴能夠動(dòng)態(tài)變化。 同步/異步通訊:同步通訊中，接納方和發(fā)送方協(xié)同操作；異步通訊中，接納方獲取數(shù)據(jù)無需與發(fā)送方協(xié)同。 部分通訊 當(dāng)一個(gè)義務(wù)僅要求與臨近的其它義務(wù)通訊時(shí)，就呈現(xiàn)部分通訊方式。例如在數(shù)值計(jì)算中的雅可比有限差分法。假設(shè)采用5點(diǎn)格式，迭代公式為 假設(shè)在二維網(wǎng)格上計(jì)算，并且處于(i,j)位置上的處置器擔(dān)任計(jì)算xij。此時(shí)，計(jì)算每個(gè)xi,j(k)時(shí)，(i,j)位置上的處置器只需與其上、下、左、右的鄰居處置器通訊以獲得xi-1,j(k-1)，xi+1,j

32、(k-1)， xi,j-1(k-1)，xi,j+1(k-1)，并把 xi,j(k-1)發(fā)送給它們。部分通訊 通訊限制在一個(gè)鄰域內(nèi)全局通訊 在全局通訊中，有很多義務(wù)參與交換數(shù)據(jù)。這能夠呵斥過多的通訊，從而限制了并行執(zhí)行的時(shí)機(jī)。例如我們希望計(jì)算 為此，我們運(yùn)用一個(gè)根進(jìn)程S擔(dān)任從各進(jìn)程一次接納一個(gè)值xi并進(jìn)展累加。這時(shí)就會(huì)出現(xiàn)全局通訊的局面。全局通訊 采用分治戰(zhàn)略可以開辟求和的并行性： 上式右邊的兩個(gè)求和可以同時(shí)執(zhí)行，并且每一個(gè)仍可按同樣的方式進(jìn)一步分解。求和過程中，同一級(jí)上的求和可以并行執(zhí)行。這樣就可以防止全局通訊，并提高算法的并行度。圖中 表示處置器X至處置器Y上一切數(shù)據(jù)的和。 全局通訊 通訊非

33、部分的 例如： All to All Master-Worker53721構(gòu)造化通訊 每個(gè)義務(wù)的通訊方式是一樣的； 下面能否存在一個(gè)一樣通訊方式？非構(gòu)造化通訊 沒有一個(gè)一致的通訊方式 例如：無構(gòu)造化網(wǎng)格非構(gòu)造化通訊 非構(gòu)造化通訊對(duì)算法設(shè)計(jì)的前期不會(huì)呵斥本質(zhì)性的困難，但會(huì)使義務(wù)組合和處置器映射更為復(fù)雜。特別是要求組合戰(zhàn)略既能創(chuàng)建尺寸大致相當(dāng)?shù)牧x務(wù)又要盡量減小義務(wù)間的通訊時(shí)就需求非常復(fù)雜的算法，而這些算法在通訊要求是動(dòng)態(tài)的時(shí)又會(huì)在算法的執(zhí)行過程中頻繁地運(yùn)用，所以必需權(quán)衡利弊。通訊判據(jù) 一切義務(wù)能否執(zhí)行大致相當(dāng)?shù)耐ㄓ? 能否盡能夠的部分通訊？ 通訊操作能否能并行執(zhí)行? 同步義務(wù)的計(jì)算能否并行執(zhí)行？通

34、訊判據(jù)1一切義務(wù)能否執(zhí)行大致同樣多的通訊？假設(shè)不是，所設(shè)計(jì)的算法的可擴(kuò)展性能夠會(huì)不好。2每個(gè)義務(wù)能否只與少數(shù)的近鄰?fù)ㄓ崳考僭O(shè)不是，那么能夠?qū)е氯滞ㄓ崱４藭r(shí)應(yīng)設(shè)法將全局通訊換成部分通訊。3諸通訊操作能否并行執(zhí)行？假設(shè)不能，所設(shè)計(jì)的算法能夠是低效的和不具可擴(kuò)展性的。此時(shí)可試用分治戰(zhàn)略來開發(fā)并行性。4不同義務(wù)的計(jì)算能否并行執(zhí)行？能否會(huì)由于等待數(shù)據(jù)而降低并行度？假設(shè)不能并行執(zhí)行，所設(shè)計(jì)的算法能夠是低效的和不具可擴(kuò)展性的。此時(shí)可思索重新安排通訊和計(jì)算的順序以改善這種情況。組合 方法描畫 外表-容積效應(yīng) 反復(fù)計(jì)算 組合判據(jù)方法描畫 在義務(wù)劃分和通訊分析階段，我們都沒有思索特定的并行機(jī)對(duì)執(zhí)行效率的影響。在

35、組合階段，我們將重新調(diào)查劃分和通訊階段所作的選擇，力圖得到一個(gè)在某一類并行機(jī)上能有效執(zhí)行的并行算法。組合的目的是經(jīng)過合并小尺寸的義務(wù)來減少義務(wù)數(shù)量和通訊開銷。方法描畫 組合是由籠統(tǒng)到詳細(xì)的過程，是將組合的義務(wù)能在一類并行機(jī)上有效的執(zhí)行； 合并小尺寸義務(wù)，減少義務(wù)數(shù)。假設(shè)義務(wù)數(shù)恰好等于處置器數(shù)，那么也完成了映射過程； 經(jīng)過添加義務(wù)的粒度和反復(fù)計(jì)算，可以減少通訊本錢；在劃分階段，為了盡能夠地開發(fā)問題的并行性，能夠產(chǎn)生了大量的細(xì)粒度義務(wù)。但是大量的義務(wù)能夠會(huì)添加通訊開銷和義務(wù)創(chuàng)建開銷。 堅(jiān)持映射和擴(kuò)展的靈敏性，降低軟件工程本錢；外表-容積效應(yīng) 通訊量與義務(wù)子集的外表成正比，計(jì)算量與義務(wù)子集的體積成正

36、比； 添加反復(fù)計(jì)算有能夠減少通訊量；外表-容積效應(yīng) 通常，一個(gè)義務(wù)的通訊需求正比與它所操作的數(shù)據(jù)域的外表積，而計(jì)算需求正比于它所操作的數(shù)據(jù)域的容積。因此一個(gè)計(jì)算單元的通訊與計(jì)算之比隨義務(wù)尺寸的添加而減小。例如在二維問題中，“外表積即是數(shù)據(jù)域的周長，它正比于問題的尺寸，而“容積指數(shù)據(jù)域的面積，它正比于問題尺寸的平方。 以二維平面上的雅可比有限差分法5點(diǎn)格式為例。假設(shè)需求計(jì)算的數(shù)據(jù)是44矩陣。假設(shè)把計(jì)算每個(gè)元素算作一個(gè)義務(wù)，那么有16個(gè)義務(wù)。每輪迭代中，每個(gè)義務(wù)都需求與其上下左右的義務(wù)通訊，共需48次通訊當(dāng)然這些通訊中許多可以并行進(jìn)展。如上圖a所示，每個(gè)箭頭表示一次通訊。 外表-容積效應(yīng)外表-容積

37、效應(yīng) 假設(shè)將相鄰的四個(gè)元素的計(jì)算作為一個(gè)義務(wù)那么只需8次通訊，如上圖b所示。雖然每次通訊要傳送兩個(gè)數(shù)據(jù)，但是相對(duì)于圖a，通訊的次數(shù)和通訊量都大大減少了?？梢?，當(dāng)小義務(wù)組合為大義務(wù)后，原來的某些數(shù)據(jù)傳送被包含在大義務(wù)里面了，它們不再表現(xiàn)為通訊，實(shí)踐計(jì)算時(shí)，這些數(shù)據(jù)交換可以經(jīng)過直接讀取內(nèi)存完成。這正是添加粒度可以減少通訊的緣由。外表-容積效應(yīng) 上例我們只想闡明添加粒度可以減少通訊次數(shù)和通訊量。仔細(xì)思索我們會(huì)發(fā)如今上例中，圖b的通訊開銷能夠比圖a大。設(shè)通訊建立的時(shí)間為S，傳送一個(gè)數(shù)據(jù)的時(shí)間為t。假設(shè)圖a的通訊方式是方向一樣的一切通訊同時(shí)執(zhí)行。比如一切的義務(wù)同時(shí)先向左傳送，那么一切向左的通訊需時(shí)間S+

38、t。同理，向其它三個(gè)方向的通訊各需時(shí)間S+t。所以圖a的通訊開銷是4(S+2t)。對(duì)圖b也可進(jìn)展一樣的分析，但是圖b中每個(gè)通訊要傳送兩個(gè)數(shù)據(jù)，因此總的通訊開銷比圖a大。外表-容積效應(yīng) 上例中的通訊是均勻的，且可以并行執(zhí)行。實(shí)踐上，實(shí)踐問題的各小義務(wù)之間的通訊很能夠是不均勻的。比如一個(gè)問題可以分為A，B、 C三個(gè)義務(wù)，A與B之間通訊頻繁，而它們與C之間通訊很少。那么顯然應(yīng)該將 A和 B組合成一個(gè)大義務(wù)，以防止通訊對(duì)它們并行執(zhí)行呵斥的影響。但是組合之后，出現(xiàn)了一個(gè)較大的義務(wù)，完成這個(gè)大義務(wù)能夠需求更長的時(shí)間。這時(shí)就需求權(quán)衡，看哪種方案更好。反復(fù)計(jì)算 反復(fù)計(jì)算Replication Computat

39、ion也稱為冗余計(jì)算。它是指采用多余的計(jì)算來減少通訊和/或整個(gè)計(jì)算時(shí)間。 反復(fù)計(jì)算減少通訊量，但添加了計(jì)算量，應(yīng)堅(jiān)持恰當(dāng)?shù)钠胶猓?反復(fù)計(jì)算的目的應(yīng)減少算法的總運(yùn)算時(shí)間；反復(fù)計(jì)算 假定在二叉樹上求N個(gè)數(shù)的和，且要求最終在每個(gè)處置器上都有該結(jié)果。一種方法是先自葉向根求和，得到結(jié)果后再自根向葉廣播，共需2 步。如以下圖所示。 反復(fù)計(jì)算 例如：二叉樹上N個(gè)處置器求N個(gè)數(shù)的全和，要求每個(gè)處置器均堅(jiān)持全和。 二叉樹上求和，共需2logN步反復(fù)計(jì)算 以上述方式求和，處置器的利用率是逐級(jí)減半的。假設(shè)在每一級(jí)每個(gè)處置器均接納兩個(gè)數(shù)據(jù)，求和后再發(fā)送給上一級(jí)的兩個(gè)處置器，那么經(jīng)過 步后，每個(gè)處置器中就都得到了N個(gè)數(shù)

40、的全和。計(jì)算過程如以下圖所示。反復(fù)計(jì)算 例如：二叉樹上N個(gè)處置器求N個(gè)數(shù)的全和，要求每個(gè)處置器均堅(jiān)持全和。 蝶式構(gòu)造求和，運(yùn)用了反復(fù)計(jì)算，共需logN步靈敏性和本錢 要維持一個(gè)算法的可移植性和可擴(kuò)展性，創(chuàng)建可變數(shù)目的義務(wù)是很關(guān)鍵的。組合時(shí)往往會(huì)使問題的義務(wù)數(shù)的變化范圍遭到限制。根據(jù)閱歷，為了能在映射階段到達(dá)負(fù)載平衡，義務(wù)數(shù)至少比處置器數(shù)多一個(gè)數(shù)量級(jí)?？捎梅治瞿Ｐ徒Y(jié)合實(shí)踐閱歷討論最優(yōu)的義務(wù)數(shù)。當(dāng)然，靈敏性并不意味著必需創(chuàng)建大量的義務(wù)。粒度可由編譯或運(yùn)轉(zhuǎn)時(shí)的參數(shù)控制。重要的是不要對(duì)義務(wù)數(shù)進(jìn)展不用要的限制。 組合時(shí)的另一個(gè)問題是要盡量減少軟件工程的代價(jià)，尤其是并行化一個(gè)串行程序時(shí)應(yīng)盡量防止程序代碼的

41、大量修正。 添加義務(wù)的粒度可以減少通訊開銷，但組合時(shí)也要使算法堅(jiān)持足夠的靈敏性并要盡量減少軟件工程的本錢。這幾個(gè)目的有時(shí)是相互矛盾的，要權(quán)衡其利弊。組合判據(jù) 添加粒度能否減少了通訊本錢？ 反復(fù)計(jì)算能否已權(quán)衡了其得益？ 能否堅(jiān)持了靈敏性和可擴(kuò)放性？ 組合的義務(wù)數(shù)能否與問題尺寸成比例? 能否堅(jiān)持了類似的計(jì)算和通訊？ 有沒有減少并行執(zhí)行的時(shí)機(jī)？組合判據(jù)1用添加部分性的方法實(shí)施組合能否減少了通訊開銷？假設(shè)不是，能否換用別的組合戰(zhàn)略以減少通訊開銷？2假設(shè)運(yùn)用了反復(fù)計(jì)算，能否權(quán)衡了其得失？3假設(shè)組合已復(fù)制了數(shù)據(jù)，能否已證明這不會(huì)因限制問題尺寸和處置器數(shù)量的變化范圍而犧牲了可擴(kuò)展性？4由組合產(chǎn)生的義務(wù)能否具

42、有類似的計(jì)算和通訊代價(jià)？5義務(wù)數(shù)目能否依然與問題尺寸成比例？假設(shè)不是，算法是不可擴(kuò)展的。6假設(shè)組合減少了并行執(zhí)行的時(shí)機(jī)，能否已證明如今的并發(fā)性仍能順應(yīng)目前和未來的并行機(jī)？7在不導(dǎo)致負(fù)載不平衡，不添加軟件工程代價(jià)和不減少可擴(kuò)展性的前提下，義務(wù)數(shù)能否再進(jìn)一步減少？在其它條件一樣時(shí)，創(chuàng)建較少的粗粒度義務(wù)的算法通常是高效的。8假設(shè)是并行化現(xiàn)有的串行程序，能否思索了修正串行代碼的本錢？假設(shè)此本錢較高，應(yīng)思索別的組合戰(zhàn)略。映射 方法描畫 負(fù)載平衡算法 義務(wù)調(diào)度算法 映射判據(jù)方法描畫映射階段的義務(wù)是指定每個(gè)義務(wù)到哪個(gè)處置器上去執(zhí)行。映射的目的映射階段的義務(wù)是指定每個(gè)義務(wù)到哪個(gè)處置器上去執(zhí)行。映射的目的是最小

43、化全局執(zhí)行時(shí)間和通訊本錢、最大化處置器的利用率，減少算是最小化全局執(zhí)行時(shí)間和通訊本錢、最大化處置器的利用率，減少算法的總執(zhí)行時(shí)間。為了到達(dá)以上目的，可采用以下戰(zhàn)略：法的總執(zhí)行時(shí)間。為了到達(dá)以上目的，可采用以下戰(zhàn)略：1 1把可以并發(fā)執(zhí)行的義務(wù)放在不同的處置器上以添加并行度；把可以并發(fā)執(zhí)行的義務(wù)放在不同的處置器上以添加并行度；2 2把需頻繁通訊的義務(wù)置于同一處置器上以提高部分性。把需頻繁通訊的義務(wù)置于同一處置器上以提高部分性。這二者有時(shí)會(huì)沖突，需求權(quán)衡。這二者有時(shí)會(huì)沖突，需求權(quán)衡。對(duì)于某些基于域分解技術(shù)開發(fā)的算法，它們有固定數(shù)目的等尺寸對(duì)于某些基于域分解技術(shù)開發(fā)的算法，它們有固定數(shù)目的等尺寸的義務(wù)

44、，通訊構(gòu)造化強(qiáng)，此時(shí)映射較簡單。假設(shè)義務(wù)的任務(wù)量不同，的義務(wù)，通訊構(gòu)造化強(qiáng)，此時(shí)映射較簡單。假設(shè)義務(wù)的任務(wù)量不同，通訊是非構(gòu)造化的，可采用負(fù)載平衡算法。對(duì)于基于功能分解開發(fā)的通訊是非構(gòu)造化的，可采用負(fù)載平衡算法。對(duì)于基于功能分解開發(fā)的算法，經(jīng)常會(huì)產(chǎn)生一些由短暫義務(wù)組成的計(jì)算，它們只在執(zhí)行的開場算法，經(jīng)常會(huì)產(chǎn)生一些由短暫義務(wù)組成的計(jì)算，它們只在執(zhí)行的開場與終了時(shí)需求與別的義務(wù)協(xié)調(diào)，此時(shí)可用義務(wù)調(diào)度算法進(jìn)展義務(wù)分配。與終了時(shí)需求與別的義務(wù)協(xié)調(diào)，此時(shí)可用義務(wù)調(diào)度算法進(jìn)展義務(wù)分配。 方法描畫 每個(gè)義務(wù)要映射到詳細(xì)的處置器，定位到運(yùn)轉(zhuǎn)機(jī)器上； 義務(wù)數(shù)大于處置器數(shù)時(shí)，存在負(fù)載平衡和義務(wù)調(diào)度問題； 映射的目

45、的：減少算法的執(zhí)行時(shí)間 并發(fā)的義務(wù) 不同的處置器 義務(wù)之間存在高通訊的 同一處置器 映射實(shí)踐是一種權(quán)衡，屬于NP完全問題；負(fù)載平衡算法 負(fù)載平衡算法負(fù)載平衡算法針對(duì)基于域分解技術(shù)開發(fā)的算法，有很多公用和通用的負(fù)針對(duì)基于域分解技術(shù)開發(fā)的算法，有很多公用和通用的負(fù)載平衡技術(shù)載平衡技術(shù)Load-Balancing TechniguesLoad-Balancing Technigues。 部分算法部分算法 部分負(fù)載平衡算法的思想是經(jīng)過從近鄰遷入義部分負(fù)載平衡算法的思想是經(jīng)過從近鄰遷入義務(wù)和向近鄰遷出義務(wù)來到達(dá)負(fù)載平衡。比如，每個(gè)處置器務(wù)和向近鄰遷出義務(wù)來到達(dá)負(fù)載平衡。比如，每個(gè)處置器周期性地與鄰居比較

46、負(fù)載的輕重。假設(shè)差別超越了某個(gè)閾周期性地與鄰居比較負(fù)載的輕重。假設(shè)差別超越了某個(gè)閾值，就進(jìn)展負(fù)載遷移。假設(shè)本人的負(fù)載輕且有鄰居負(fù)載重，值，就進(jìn)展負(fù)載遷移。假設(shè)本人的負(fù)載輕且有鄰居負(fù)載重，那么從該鄰居遷入一些義務(wù)。反之，假設(shè)本人的負(fù)載重，那么從該鄰居遷入一些義務(wù)。反之，假設(shè)本人的負(fù)載重，而別的鄰居較空閑，那么把本人的一部分負(fù)載遷給它。部而別的鄰居較空閑，那么把本人的一部分負(fù)載遷給它。部分算法的優(yōu)點(diǎn)是這個(gè)方案只利用部分的負(fù)載信息。同時(shí)，分算法的優(yōu)點(diǎn)是這個(gè)方案只利用部分的負(fù)載信息。同時(shí)，遷移義務(wù)時(shí)往往通訊量很大，而此方案只在部分遷移，有遷移義務(wù)時(shí)往往通訊量很大，而此方案只在部分遷移，有利于提高效率。

47、利于提高效率。 負(fù)載平衡算法 概率方法概率方法Probabilistic MethodProbabilistic Method 此法的思想是將義務(wù)此法的思想是將義務(wù)隨機(jī)地分配給處置器，假設(shè)義務(wù)足夠多，那么每個(gè)處置器隨機(jī)地分配給處置器，假設(shè)義務(wù)足夠多，那么每個(gè)處置器估計(jì)能分到大致等量的義務(wù)。此法的優(yōu)點(diǎn)是低價(jià)和可擴(kuò)展估計(jì)能分到大致等量的義務(wù)。此法的優(yōu)點(diǎn)是低價(jià)和可擴(kuò)展性好；缺陷是要求跨處置器進(jìn)展通訊，并且只需當(dāng)義務(wù)數(shù)性好；缺陷是要求跨處置器進(jìn)展通訊，并且只需當(dāng)義務(wù)數(shù)遠(yuǎn)遠(yuǎn)多于處置器數(shù)時(shí)才干到達(dá)預(yù)期的效果。遠(yuǎn)遠(yuǎn)多于處置器數(shù)時(shí)才干到達(dá)預(yù)期的效果。 循環(huán)映射循環(huán)映射Cyclic MappingCyclic

48、Mapping 此法又稱為循環(huán)指派法，即此法又稱為循環(huán)指派法，即輪番地給處置器分配計(jì)算義務(wù)。它實(shí)踐上是概率方法的一輪番地給處置器分配計(jì)算義務(wù)。它實(shí)踐上是概率方法的一種方式。此法適用于各計(jì)算義務(wù)呈明顯的空間部分性的情種方式。此法適用于各計(jì)算義務(wù)呈明顯的空間部分性的情況。況。 總之，部分算法代價(jià)小，但當(dāng)負(fù)載變化大時(shí)調(diào)整很慢；概總之，部分算法代價(jià)小，但當(dāng)負(fù)載變化大時(shí)調(diào)整很慢；概率方法代價(jià)小，可擴(kuò)展性好，但通訊代價(jià)能夠較大，且只率方法代價(jià)小，可擴(kuò)展性好，但通訊代價(jià)能夠較大，且只適用于義務(wù)數(shù)遠(yuǎn)多于處置器數(shù)的情況；循環(huán)映射技術(shù)是概適用于義務(wù)數(shù)遠(yuǎn)多于處置器數(shù)的情況；循環(huán)映射技術(shù)是概率映射的一種方式，而概率方

49、法比其它技術(shù)易于導(dǎo)致可觀率映射的一種方式，而概率方法比其它技術(shù)易于導(dǎo)致可觀的通訊。的通訊。 負(fù)載平衡算法 靜態(tài)的：事先確定； 概率的：隨機(jī)確定； 動(dòng)態(tài)的：執(zhí)行期間動(dòng)態(tài)負(fù)載； 基于域分解的： 遞歸對(duì)剖 部分算法 概率方法 循環(huán)映射義務(wù)調(diào)度算法義務(wù)調(diào)度算法義務(wù)調(diào)度算法義務(wù)調(diào)度算法的最關(guān)鍵之處是義務(wù)的分配戰(zhàn)略。常用的調(diào)度方式有經(jīng)理義務(wù)調(diào)度算法的最關(guān)鍵之處是義務(wù)的分配戰(zhàn)略。常用的調(diào)度方式有經(jīng)理/ /雇員方式和非集中方式。雇員方式和非集中方式。經(jīng)理經(jīng)理/ /雇員方式雇員方式 在此方式中，有一個(gè)進(jìn)程經(jīng)理擔(dān)任分配義務(wù)，每個(gè)在此方式中，有一個(gè)進(jìn)程經(jīng)理擔(dān)任分配義務(wù)，每個(gè)雇員向經(jīng)理懇求義務(wù)，得到義務(wù)后執(zhí)行義務(wù)。運(yùn)

50、用預(yù)取方法以使計(jì)算雇員向經(jīng)理懇求義務(wù)，得到義務(wù)后執(zhí)行義務(wù)。運(yùn)用預(yù)取方法以使計(jì)算和通訊重疊可以提高效率。和通訊重疊可以提高效率。這種方案的一種變體是層次經(jīng)理這種方案的一種變體是層次經(jīng)理/ /雇員方式。在此方式中，雇員被分成雇員方式。在此方式中，雇員被分成不相交的集合，每個(gè)集合有一個(gè)小經(jīng)理。雇員們從小經(jīng)理那里領(lǐng)取義務(wù)，不相交的集合，每個(gè)集合有一個(gè)小經(jīng)理。雇員們從小經(jīng)理那里領(lǐng)取義務(wù)，小經(jīng)理從經(jīng)理處領(lǐng)取義務(wù)。經(jīng)理小經(jīng)理從經(jīng)理處領(lǐng)取義務(wù)。經(jīng)理/ /雇員方式的缺陷是經(jīng)理進(jìn)程容易成為雇員方式的缺陷是經(jīng)理進(jìn)程容易成為系統(tǒng)的瓶頸。系統(tǒng)的瓶頸。非集中方式非集中方式 它就是無中心管理者的分布式調(diào)度法。它就是無中心管

51、理者的分布式調(diào)度法。終了檢測(cè)終了檢測(cè) 義務(wù)調(diào)度算法需求一種機(jī)制來檢測(cè)整個(gè)問題的計(jì)算何時(shí)終了。義務(wù)調(diào)度算法需求一種機(jī)制來檢測(cè)整個(gè)問題的計(jì)算何時(shí)終了。否那么，空閑的雇員們將永不停頓地發(fā)出義務(wù)懇求。在經(jīng)理否那么，空閑的雇員們將永不停頓地發(fā)出義務(wù)懇求。在經(jīng)理/ /雇員方式雇員方式中，經(jīng)理可以判別雇員能否都空閑了。一切的雇員都空閑了就意味著整中，經(jīng)理可以判別雇員能否都空閑了。一切的雇員都空閑了就意味著整個(gè)問題的計(jì)算終了了。在非集中方式中終了檢測(cè)那么比較困難，由于沒個(gè)問題的計(jì)算終了了。在非集中方式中終了檢測(cè)那么比較困難，由于沒有一個(gè)進(jìn)程知道全局的情況。有一個(gè)進(jìn)程知道全局的情況。義務(wù)調(diào)度算法 義務(wù)放在集中的

52、或分散的義務(wù)池中，運(yùn)用義務(wù)調(diào)度算法將池中的義務(wù)分配給特定的處置器。下面是兩種常用調(diào)度方式： 經(jīng)理/雇員方式 非集中方式映射判據(jù) 采用集中式負(fù)載平衡方案，能否存在通訊瓶頸？ 采用動(dòng)態(tài)負(fù)載平衡方案，調(diào)度戰(zhàn)略的本錢如何？映射判據(jù) 1假設(shè)采用集中式負(fù)載平衡方案，能否檢查了中央管理者不會(huì)成為瓶頸？ 2假設(shè)采用動(dòng)態(tài)負(fù)載平衡方案，能否衡量過不同戰(zhàn)略的本錢？ 3假設(shè)采用概率或循環(huán)指派法，能否有足夠多的義務(wù)？普通地，義務(wù)數(shù)應(yīng)不少于處置器數(shù)的10倍。 4假設(shè)要為一個(gè)問題設(shè)計(jì)一個(gè)SPMD程序，能否思索過基于動(dòng)態(tài)義務(wù)創(chuàng)建和消除的算法？小 結(jié) 劃分 域分解和功能分解 通訊 義務(wù)間的數(shù)據(jù)交換 組合 義務(wù)的合并使得算法更有

53、效 映射 將義務(wù)分配四處置器，并堅(jiān)持負(fù)載平衡并發(fā)的類型 并行程序必需以某種方式給出義務(wù)的并行性，它們可以以下面的方式給出： 數(shù)據(jù)并行 義務(wù)并行 流水并行 混合并行 數(shù)據(jù)并行 思索下面的矩陣加法：A，B，C都是nn的矩陣，計(jì)算C=A+B為了計(jì)算C的每個(gè)元素，需求進(jìn)展如下的計(jì)算： Ci,j=ai,j+bi,j 留意計(jì)算C的每個(gè)元素的操作都是一次加法，只是操作數(shù)不同而已，而且，每個(gè)元素的計(jì)算都是獨(dú)立的，它們可以并行執(zhí)行。 這種類型的并行性表現(xiàn)為：并行的在不同的數(shù)據(jù)上進(jìn)展一樣的操作，稱為數(shù)據(jù)并行性。表現(xiàn)出這種并行性的問題通常稱為數(shù)據(jù)并行的問題。數(shù)據(jù)并行問題的一個(gè)突出特點(diǎn)是對(duì)大多數(shù)的這類問題，數(shù)據(jù)并行性

54、的程度可以并行進(jìn)展數(shù)據(jù)并行的操作數(shù)目隨著問題規(guī)模的添加而增大，這意味著對(duì)于這類問題，可以用較多的處置器來有效的處置更大規(guī)模的問題。這是一種比較簡單的并行方式，僥幸的是，在實(shí)踐的運(yùn)用中，有很多有趣的問題都是數(shù)據(jù)并行的。義務(wù)并行 假設(shè)需求做如下的查詢：Select all where MODEL=“Accord AND YEAR=“1996 ANDCOLOR=“Green OR COLOR=“Black； 這個(gè)查詢尋覓數(shù)據(jù)庫中一切1996年產(chǎn)的綠色或黑色的Accord車的資料。在關(guān)系數(shù)據(jù)庫中，這個(gè)查詢通常需求創(chuàng)建幾個(gè)中間表，一種能夠的情形如下：一個(gè)表包含一切的Accord車數(shù)據(jù)，一個(gè)表包含一切19

55、96款的車，一個(gè)表包含一切綠色車，一個(gè)表包含一切的黑色車。然后在這些表上進(jìn)展Join操作，更詳細(xì)的說，數(shù)據(jù)庫將求出前兩個(gè)表的交集，從而得到1996款的Accord車的表，同時(shí)，將求出后兩個(gè)表的并，得到綠色或黑色的車的表，最后，用這兩個(gè)表求交集，就得到了最后的數(shù)據(jù)。上面的操作可以用下面的圖來籠統(tǒng)的表示。義務(wù)并行義務(wù)并行 圖中的每個(gè)節(jié)點(diǎn)表示一個(gè)需求被計(jì)算的表計(jì)算子義務(wù)，節(jié)點(diǎn)間的箭頭給出了義務(wù)間的依賴關(guān)系。 在上面圖中，只需一切必需的子義務(wù)曾經(jīng)完成，后續(xù)子義務(wù)就可以進(jìn)展，因此，通常來說，很多的子義務(wù)都可以并行的執(zhí)行。這種并行性表現(xiàn)為子義務(wù)的并行執(zhí)行，因此被稱為義務(wù)并行性。義務(wù)并行性比數(shù)據(jù)并行性要復(fù)雜

56、一些實(shí)踐上，用義務(wù)并行性完全可以描畫數(shù)據(jù)并行性的問題。 流水并行 流水并行性是指在同一個(gè)數(shù)據(jù)流上同時(shí)的執(zhí)行多個(gè)程序后續(xù)的程序處置的是前面程序處置過的數(shù)據(jù)流。流水并行性通常也被稱為流水線。在流水線上，計(jì)算的并行性表現(xiàn)為：每個(gè)處置器上運(yùn)轉(zhuǎn)一個(gè)不同的程序，它們構(gòu)成一個(gè)完好的處置流程，每個(gè)處置器把本人處置完的數(shù)據(jù)馬上傳送給邏輯上的下一個(gè)處置器。這樣實(shí)踐上構(gòu)成了處置器間的一個(gè)流水線，因此稱為流水并行性。 混合并行 很多的問題中的并行性表現(xiàn)為數(shù)據(jù)并行性，義務(wù)并行性和流水并行性的混合，某個(gè)問題表現(xiàn)出的流水并行性的數(shù)量通常獨(dú)立于問題的規(guī)模，而義務(wù)和數(shù)據(jù)并行性那么相反，他們通常會(huì)隨問題規(guī)模的增長而增長。通常情況

57、下，義務(wù)并行性可以用來開發(fā)粗粒度的并行性，而數(shù)據(jù)并行性用來開發(fā)細(xì)粒度的并行性，因此，義務(wù)并行性和數(shù)據(jù)并行性的組合可以用來有效的開發(fā)運(yùn)用在大量處置器上的并行算法。 分解技術(shù) 設(shè)計(jì)并行算法的一個(gè)根本的步驟是描畫完成給定義務(wù)所需求的計(jì)算，并把這些計(jì)算分解為可以并行執(zhí)行的子義務(wù)集。對(duì)很多的問題來說，它們的義務(wù)圖都包含了足夠的并行性。對(duì)這樣的義務(wù)圖，各個(gè)義務(wù)可以在多個(gè)處置器上進(jìn)展調(diào)度，從而使得問題得以并行的完成。但不幸的是，很多的問題的義務(wù)圖中并不表現(xiàn)出如此豐富或者稱為直觀的并行性，相反的，它們往往包含一個(gè)義務(wù)或者多個(gè)需求串行執(zhí)行的義務(wù)。對(duì)這樣的問題，我們需求將總的計(jì)算義務(wù)進(jìn)展分解為一個(gè)可以并行執(zhí)行的子

58、義務(wù)集，這個(gè)過程稱為義務(wù)分解。一個(gè)好的義務(wù)分解應(yīng)該具有下面的特點(diǎn)： 它應(yīng)該有很高的并行度。并行度越高意味著這個(gè)分解后的義務(wù)可以在越多的處置器上并行的執(zhí)行。 子義務(wù)間的交互通訊和同步應(yīng)該盡能夠的少。交互少意味著處置器可以更專心的完成義務(wù)本身而不是其它由于通訊和同步帶來的額外計(jì)算和等待。分解技術(shù) 很多情況下，這兩個(gè)要求會(huì)產(chǎn)生沖突，也就是說，有很高的并行度的義務(wù)分解，通常需求子義務(wù)間的大量交互操作。如何平衡沖突是并行算法設(shè)計(jì)中的藝術(shù)。這一節(jié)中主要思索如何提高子義務(wù)的并行度，關(guān)于子義務(wù)間的交互的討論在下一節(jié)進(jìn)展。下面引見幾種用于義務(wù)分解的常用的方法。對(duì)不同的問題，這些方法并不總是可行，而且也不一定會(huì)得

59、到最有效的并行算法，但對(duì)很多問題來說，這些方法可以提供一個(gè)好的并行化的“著眼點(diǎn)。其中的遞歸分解和數(shù)據(jù)分解可以被看成是相對(duì)通用的分解方法，由于它們可以用來對(duì)大多數(shù)的問題進(jìn)展義務(wù)分解，而搜索分解要特殊一些，它只能運(yùn)用于某些特定類型的問題。遞歸分解 遞歸分解通常用來對(duì)采用Divide-and-conquer(分治)方法的問題進(jìn)展義務(wù)分解。這種方法將義務(wù)分解為獨(dú)立的子義務(wù)，這個(gè)分解的過程會(huì)遞歸的進(jìn)展。問題的答案是一切的子義務(wù)的答案的組合。分-治戰(zhàn)略表現(xiàn)出一種自然的并行性。 思索下面的問題：對(duì)n個(gè)元素的序列A進(jìn)展快速排序?？焖倥判蛩惴ㄊ且环N分治的算法。算法首先選取一個(gè)軸元素x，然后把A分成兩個(gè)子序列A0

60、和A1，其中A0中的一切元素小于x,而A1中的一切元素大于等于x,這是算法的分割部分。對(duì)得到的子序列遞歸地進(jìn)展上面的分割過程，然后用經(jīng)過排序的子序列組合成最后的結(jié)果序列A?？焖倥判虻倪^程可以用下面的圖來例如。 遞歸分解遞歸分解其中的深色的元素為選中的軸元素。如今思索如何根據(jù)算法的分-治特性來對(duì)快速排序算法進(jìn)展義務(wù)分解。從上面的圖可以看出，對(duì)義務(wù)樹的每一層，每個(gè)子義務(wù)的繼續(xù)分割是可以并行執(zhí)行的，而且它們相互獨(dú)立。因此對(duì)計(jì)算的分解實(shí)踐上也是一棵樹。算法開場時(shí)，只需一個(gè)序列樹的根節(jié)點(diǎn)，我們用一個(gè)處置器來完成對(duì)它的第一次分割。分割完成后，我們得到了第一層中的2個(gè)子序列，對(duì)這兩個(gè)子序列的分割可以在兩個(gè)處