1、并行算法1 一般設計方法并行算法的一般設計方法 串行算法的直接并行化 從問題描述開始設計并行算法 借用已有算法求解新問題串行算法的直接并行化 設計方法描述 快排序算法的并行化 設計方法的描述 方法描述 發掘和利用現有串行算法中的并行性，直接將串行算法改造為并行算法。 許多并行編程語言都支持通過在原有的串行程序中加入并行原語（例如某些通信命令等）的方法將串行程序并行化。 設計方法的描述 評注 由串行算法直接并行化的方法是并行算法設計的最常用方法之一； 不是所有的串行算法都可以直接并行化的；某些串行算法有內在的串行性，比如在某些串行算法中，每一步都要用到上一步的結果。只有當上一步完全結束后，下一步

2、才能開始。這樣，各步之間就不能并行，只能考慮其它的并行化辦法。例如模擬退火算法，每個溫度下迭代的出發點是上一個溫度下迭代的結束點。這樣就很難直接將各個溫度的迭代并行起來。 設計方法的描述 評注 一個好的串行算法并不能并行化為一個好的并行算法；另一方面，不好的串行算法并行化后也可能是優秀的并行算法。例如，串行算法中是沒有冗余計算的。但是在并行算法中，使用適當的冗余計算也可能使并行算法效率更高。加入冗余計算的并行算法就可能比直接由串行算法并行化得到的算法效率高。又比如，枚舉不是一種好的串行算法。但是將其直接并行化后可以得到比較好的并行算法。 許多數值串行算法可以并行化為有效的數值并行算法。設計方法

3、的描述 假設我們想用求和的方法進行數值積分。設被積函數為f(x)，積分區間為a,b。為了積分，將區間a,b均勻分成N個小區間，每個小區間長 ，根據積分的定義 是第i 個小區間左端點的坐標，而 是f(x)在第i 個小區間上積分的近似值。如果使用串行算法，可以用循環和疊加完成上述求和。這個串行算法可以直接并行化。 設計方法的描述 假設有k臺處理器，可以把這N個小區間上的計算任務分到各處理器：0號處理器負責第 個小區間上的計算和累加，1號處理器負責第 個小區間上的計算和累加，k-1號處理器負責第 個小區間上的計算和累加。k個處理器并行地計算出部分和，然后再把結果加到一起。設計方法的描述 快排序算法的

4、并行化算法 PRAM-CRCW上的快排序二叉樹構造算法 輸入：序列(A1,An)和n個處理器 輸出：供排序用的一棵二叉排序樹 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 t

5、hen exit else fi=RCfi endif endif end repeat End 從問題描述開始設計并行算法 方法描述 從問題本身描述出發，不考慮相應的串行算法，設計一個全新的并行算法。 評注 挖掘問題的固有特性與并行的關系； 設計全新的并行算法是一個挑戰性和創造性的工作； 利用串的周期性的PRAM-CRCW算法是一個很好的范例；并行串匹配算法 給定長度為n的正文串正文串T和長度為m的模式串模式串P，找出P在T中所有出現的位置稱為串匹配問題。 研究發現，兩串能否匹配是與串本身的特性有關的。這種特性，就是串的周期性周期性。 串可以分為周期的和非周期的。 可以引入見證函數見證函數（

6、Witness Function）來判斷串的周期性。確定了串的周期性后就可以先研究非周期串的匹配，然后在此基礎上再研究周期串的匹配。 并行串匹配算法 對于非周期串的研究，就是如何利用見證函數快速地找出P在T中的位置。為此，引入競爭函數競爭函數duel(p,qduel(p,q) ) 。 先把正文串分成小段，借助于見證函數并行地計算競爭函數值，找出那些可能匹配的位置。然后逐步擴大正文串分段的長度，并計算競爭函數值，在可能匹配的位置中排除那些不可能匹配的位置。最后在剩下的可能位置中驗證哪些是符合要求的位置。并行串匹配算法假設T=abaababaababaababaababa，n=23，P=abaab

7、aba，m=8。由見證函數可知P是非周期串。因為P只可能在前16個位置上與T匹配，所以在找所有“可能位置”時只考慮T的前16個字符。匹配時，先要計算見證函數值，然后由其計算 的值，找到可能匹配的位置。計算duel(p,q)時，可以所有的塊并行計算。先將P和T分成長度為2的塊，用模式塊(ab) 與正文塊(ab)(aa)(ba)(ba)(ab)(ab)(aa)(ba)進行匹配可知模式塊(ab)在位置1，4，6，9，11，14，16（即duel(p,q)的獲勝者）出現匹配。再把P與T劃分成長度為4的塊，用模式塊(abaa)與正文塊(abaa)(baba)(abab)(aaba)進行匹配, 可知在位置

8、1，6，11，16出現匹配（位置4、9、14被淘汰）；最后用模式串(abaababa)在正文串的位置1，6，11，16進行檢查，排除那些不匹配的位置。本例中這4個位置都匹配。借用已有算法求解新問題 設計方法描述 利用矩陣乘法求所有點對間最短路徑 設計方法的描述 方法描述 找出求解問題和某個已解決問題之間的聯系； 改造或利用已知算法應用到求解問題上。 評注 這是一項創造性的工作； 使用矩陣乘法算法求解所有點對間最短路徑是一個很好的范例。利用矩陣乘法求所有點對間最短路徑計算原理設在一有向圖中，各弧都賦予了非負整數權。圖中一條路徑的長長度度定義為該路徑上所有的弧的權的和。圖中兩結點之間的最短路徑最短

9、路徑是指它們之間長度最短的路徑。設G為一個含有n個結點的有向圖。矩陣W=(wij)是G中各弧上的權構成的矩陣，即W的元素wij是G中結點vi到結點vj的弧上的權（如果vi到vj無弧，則令wij=）。我們的目的是計算G中所有結點對之間的最短路。為此，記dij為結點vi到結點vj的最短路長，并記D=(dij)。用dij k表示從vi到vj至多經過k-1個中間結點的所有路徑的長度的最小值，記Dk=(dijk) 。因此dij 1=wij（ij）， dij 1=0 （i=j）。如果假設G中不包含權為負的有向圈，則dij = dij n-1，D=Dn-1利用矩陣乘法求所有點對間最短路徑 根據組合最優原理（

10、Combinatorial Optimization Principle）有 從而可以從D1 開始，逐次計算出D2 ， D4 ， D8，Dn-1=D。為了從Dk/2計算Dk，可以借用標準的矩陣乘法。矩陣乘法執行的計算是 只需將矩陣乘法中的乘法操作換成加法操作，把矩陣乘法中的求和換求最小值操作即可。 利用矩陣乘法求所有點對間最短路徑計算原理 有向圖G=(V,E)，邊權矩陣W=(wij)nn，求最短路徑長度矩陣D=(dij)nn，dij為vi到vj的最短路徑長度。假定圖中無負權有向回路，記d(k)ij為vi到vj至多有k-1個中間結點的最短路徑長，Dk=(d(k)ij)nn，則 (1) d(1)i

11、j=wij 當 ij (如果vi到vj之間無邊存在記為) d(1)ij=0 當 i=j (2) 無負權回路 dijd(n-1)ij (3) 利用最優組合原理：d(k)ij=min1lnd(k/2)il+d(k/2)lj 視：”+” “”， “min” “”，則上式變為 d(k)ij=1lnd(k/2)ild(k/2)lj (4) 應用矩陣乘法：D1 D2 D4 D2logn (= Dn)SIMD-CC上的并行算法：p139算法5.5并行算法2 基本設計技術并行算法的基本設計技術 劃分設計技術 分治設計技術 平衡樹設計技術 倍增設計技術 流水線設計技術劃分設計技術 均勻劃分技術 方根劃分技術 對

12、數劃分技術 功能劃分技術 均勻劃分技術劃分方法n個元素A1.n分成p組，每組A(i-1)n/p+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調用串行排序算法對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按主

13、元將有序段A(i-1)n/p+1.in/p劃分成p段 (7)全局交換：各處理器將其有序段按段號交換到對應的處理器中 (8)歸并排序：各處理器對接收到的元素進行歸并排序 end. 均勻劃分技術例 PSRS排序過程。N=27，p=3，PSRS排序如下： 方根劃分技術劃分方法n個元素A1.n分成A(i-1)n(1/2)+1.in(1/2)，i=1n(1/2) 示例：SIMD-CREW模型上的 Valiant歸并(1975年發表) /有序組A1.p、B1.q, (假設plogm=log4=2 = j1=rank(blogm:A)=rank(b2:A)=rank(9:A)=3, j2=8 B0: 3,

14、9 B1: 16, 21 A0: 4, 6, 7 A1: 10, 12, 15, 18, 20 A和B歸并化為(A0, B0)和(A1, B1)的歸并 功能劃分技術劃分方法 n個元素A1.n分成等長的p組，每組滿足某種特性。示例：(m, n)選擇問題(求出n個元素中前m個最小者) 功能劃分：要求每組元素個數必須大于m； 算法：p148算法6.4 輸入：A=(a1,an); 輸出：前m個最小者； Begin (1) 功能劃分：將A劃分成g=n/m組，每組含m個元素； (2) 局部排序：使用Batcher排序網絡將各組并行進行排序； (3) 兩兩比較：將所排序的各組兩兩進行比較，從而形成MIN序列

15、； (4) 排序-比較：對各個MIN序列，重復執行第(2)和第(3)步，直至 選出m個最小者。 End 功能劃分技術分治設計技術 并行分治設計步驟 雙調歸并網絡 并行分治設計步驟 將輸入劃分成若干個規模相等的子問題； 同時(并行地)遞歸求解這些子問題； 并行地歸并子問題的解，直至得到原問題的解。 雙調歸并網絡 雙調序列(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定理 給定雙調序列(x0,x1,xn-1), 對于si=minxi,xi+n/2和 l li=maxxi,x

16、i+n/2， 則小序列(s0,s1,sn-1)和大序列(l l0,l l1,l ln-1) 仍是雙調序列 雙調歸并網絡 (4,4)雙調歸并網絡 雙調歸并網絡Batcher雙調歸并算法 輸入：雙調序列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) l li=maxxi,xi+n/2 end for (2)Recursive Call: (2.1)BITONIC_MERG(MIN=(s0,sn/2

17、-1) (2.2)BITONIC_MERG(MIN=(l l0, l ln/2-1) (3)output sequence MIN followed by sequence MAX End平衡樹設計技術 設計思想 求最大值 計算前綴和 平衡樹設計技術 設計思想 以樹的葉結點為輸入，中間結點為處理結點，由葉向根或由根向葉逐層進行并行處理。 示例 求最大值 計算前綴和 求最大值算法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

18、圖示時間分析 t(n)=mO(1)=O(logn) p(n)=n/2A1An/4An/2-1An/2An/2+1An-2An-1AnAn+1An+2An+3A2n-4A2n-3A2n-2A2n-1K=m-1K=m-2K=0P1P1P2Pn/2-1Pn/2P1Pn/2-1 計算前綴和 問題定義n個元素x1,x2,xn，前綴和是n個部分和：Si=x1*x2*xi, 1in 這里*可以是或 串行算法： Si=Si1*xi 計算時間為 O(n) 并行算法：p154算法6.9 SIMD-TC上非遞歸算法 令Ai=xi, i=1n, Bh,j和Ch,j為輔助數組(h=0logn, j=1n/2h) 數組B

19、記錄由葉到根正向遍歷樹中各結點的信息(求和) 數組C記錄由根到葉反向遍歷樹中各結點的信息(播送前綴 和) 計算前綴和例：n=8, p=8, C01C08為前綴和倍增設計技術 設計思想 表序問題 求森林的根 倍增設計技術 設計思想 又稱指針跳躍(pointer jumping)技術，特別適合于處理鏈表或有向樹之類的數據結構； 當遞歸調用時，所要處理數據之間的距離逐步加倍，經過k步后即可完成距離為2k的所有數據的計算。 示例 表序問題 求森林的根 表序問題問題描述 n個元素的列表L，求出每個元素在L 中的次第號(秩或位序或rank(k)， rank(k)可視為元素k至表尾的距離；示例：n=7 (1

20、)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, 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)并行做：

21、初始化pk和distancek /O(1) (2)執行 次 /O(logn) (2.1)對k并行地做 /O(1) 如果k的后繼不等于k的后繼之后繼，則 (i) distancek= distancek+ distancepk (ii) pk=ppk (2.2)對k并行地做 rankk=distancek /O(1) 運行時間：t(n)=O(logn) p(n)=nnlog 求森林的根問題描述 一組有向樹F中, 如果是F中的一條弧，則pi=j(即j是i的雙親)；若i為根，則pi=i。求每個結點j(j=1n)的樹根sj.示例 初始時 P1=p2=5 p3=p4=p5=6 P6=p7=8 p8=8

22、P9=10 p10=11 p11=12 p12=13 p13=13 si=pi 求森林的根 示例 第一次迭代后 第二次迭代后 算法：P157算法6.11 運行時間：t(n)=O(logn) W(n)=O(nlogn)流水線設計技術 設計思想 5-point DFT的計算 流水線設計技術 設計思想 將算法流程劃分成p個前后銜接的任務片斷，每個任務片斷的輸出作為下一個任務片斷的輸入； 所有任務片斷按同樣的速率產生出結果。 評注 流水線技術是一種廣泛應用在并行處理中的技術； 脈動算法(Systolic algorithm)是其中一種流水線技術； 5-point DFT的計算問題描述 5-point

23、DFT的計算。應用秦九韶(Horner)法則，04142434440313233343021222324201112131410010203040021426316444021426312433021426384220112233441100102030400)()()()()(aaaaayaaaaayaaaaayaaaaayaaaaayaaaaabyaaaaabyaaaaabyaaaaabyaaaaaby 5-point DFT的計算示例：p(n)=n-1, t(n)=2n-2=O(n) 并行算法3 一般設計過程并行算法的一般設計過程 PCAM設計方法學 劃分 通訊 組合 映射 小結 PCA

24、M設計方法學 設計并行算法的四個階段 劃分(Partitioning) 通訊(Communication) 組合(Agglomeration) 映射(Mapping) 劃分：分解成小的任務，開拓并發性； 通訊：確定諸任務間的數據交換，監測劃分的合理性； 組合：依據任務的局部性，組合成更大的任務； 映射：將每個任務分配到處理器上，提高算法的性能。 PCAM設計過程劃分 方法描述 域分解 功能分解 劃分判據 劃分方法描述 充分開拓算法的并發性和可擴放性； 先進行數據分解(稱域分解)，再進行計算功能的分解(稱功能分解)； 使數據集和計算集互不相交； 劃分階段忽略處理器數目和目標機器的體系結構； 能分

25、為兩類劃分： 域分解(domain decomposition) 功能分解(functional decomposition)域分解 劃分的對象是數據，可以是算法的輸入數據、中間處理數據和輸出數據； 將數據分解成大致相等的小數據片； 劃分時考慮數據上的相應操作； 如果一個任務需要別的任務中的數據，則會產生任務間的通訊；域分解域分解（Domain Decomposition）也叫數據劃分，劃分的對象是數據。這些數據可以是算法（或程序）的輸入數據、計算的中間結果或計算的輸出數據。域分解的步驟是：首先分解與問題相關的數據，如果可能的話，應使每份數據的數據量大體相等；然后再將每個計算關聯到它所操作的數

26、據上。由此就產生出一些任務，每個任務包括一些數據及其上的操作。當一個操作需要別的任務中的數據時，就會產生通信要求。域分解的經驗方法是：優先集中在最大數據的劃分和經常被訪問的數據結構上。在不同的階段，可能要對不同的數據結構進行操作或需要對同一數據結構進行不同的分解。在此情況下，要分別對待，然后再將各階段設計的分解與算法裝配到一起。域分解 示例：三維網格的域分解，各格點上計算都是重復的。下圖是三種分解方法：域分解 不規則區域的分解示例：功能分解 劃分的對象是計算，將計算劃分為不同的任務，其出發點不同于域分解； 劃分后，研究不同任務所需的數據。如果這些數據不相交的，則劃分是成功的；如果數據有相當的重

27、疊， 意味著要重新進行域分解和功能分解； 功能分解是一種更深層次的分解。功能分解 功能分解功能分解（Functional Decomposition）也叫計算劃分，它首先關注被執行的計算的分解，而不是計算所需的數據，然后，如果所作的計算劃分是成動的，再繼續研究計算所需的數據。如果這些數據是不相交或相交很少的，就意味著劃分是成功的；如果這些數據有相當的重疊，就會產生大量的通信，此時就暗示應考慮數據分解。 盡管大多數并行算法采用域分解，但功能分解有時能揭示問題的內在結構，展示出優化的機會。單對數據進行研究往往很難做到這一點。 功能分解的一個例子是搜索樹。搜索樹沒有明顯的可分解的數據結構，但易于進行

28、細粒度的功能分解：開始時根生成一個任務，對其評價后，如果它不是一個解，就生成若干葉結點，這些葉結點可以分到各個處理器上并行地繼續搜索。功能分解 示例1：搜索樹 示例2：氣候模型劃分判據 劃分是否具有靈活性？ 劃分是否避免了冗余計算和存儲？ 劃分任務尺寸是否大致相當？ 任務數與問題尺寸是否成比例？ 功能分解是一種更深層次的分解，是否合理？劃分判據1）所劃分的任務數是否高于目標機上處理器數目一個量級？若不是，在后面的設計步驟中將缺少靈活性。2）劃分是否避免了冗余的計算和存儲要求？若不是，則產生的算法對大型問題可能不是可擴展的。3）各任務的尺寸是否大致相當？若不是，則分配處理器時很難做到負載平衡。4

29、）劃分的任務數是否與問題尺寸成比例？理想情況下，問題尺寸的增加應引起任務數的增加而不是任務尺寸的增加。若不是這樣，算法可能不能求解更大的問題，盡管有更多的處理器。5）是否采用了幾種不同的劃分法？多考慮幾種選擇可以提高靈活性。同時既要考慮域分解又要考慮功能分解。 通訊 方法描述 四種通訊模式 通訊判據 通訊方法描述 通訊是PCAM設計過程的重要階段； 劃分產生的諸任務，一般不能完全獨立執行，需要在任務間進行數據交流；從而產生了通訊； 功能分解確定了諸任務之間的數據流； 諸任務是并發執行的，通訊則限制了這種并發性； 四種通訊模式 局部/全局通訊:局部通信中，每個任務只與少數的幾個近鄰任務通信；全局

30、通信中，每個任務要與很多別的任務通信。 結構化/非結構化通訊:結構化通信中，一個任務和其近鄰形成規則的結構（如樹、網格等）；非結構化通信中，通信網可能是任意圖。 靜態/動態通訊:靜態通信中，通信伙伴不隨時間變化；動態通信中，通信伙伴可能動態變化。 同步/異步通訊:同步通信中，接收方和發送方協同操作；異步通信中，接收方獲取數據無需與發送方協同。 局部通訊 當一個任務僅要求與鄰近的其它任務通信時，就呈現局部通信模式。例如在數值計算中的雅可比有限差分法。如果采用5點格式，迭代公式為 假設在二維網格上計算，并且處于(i,j)位置上的處理器負責計算xij。此時，計算每個xi,j(k)時，(i,j)位置上

31、的處理器只需與其上、下、左、右的鄰居處理器通信以獲得xi-1,j(k-1)，xi+1,j(k-1)， xi,j-1(k-1)，xi,j+1(k-1)，并把 xi,j(k-1)發送給它們。局部通訊 通訊限制在一個鄰域內全局通訊 在全局通信中，有很多任務參與交換數據。這可能造成過多的通信，從而限制了并行執行的機會。例如我們希望計算 為此，我們使用一個根進程S負責從各進程一次接收一個值（xi）并進行累加。這時就會出現全局通信的局面。全局通訊 采用分治策略可以開拓求和的并行性： 上式右邊的兩個求和可以同時執行，并且每一個仍可按同樣的方式進一步分解。求和過程中，同一級上的求和可以并行執行。這樣就可以避免

32、全局通信，并提高算法的并行度。圖中 表示處理器X至處理器Y上所有數據的和。 全局通訊 通訊非局部的 例如： All to All Master-Worker53721結構化通訊 每個任務的通訊模式是相同的； 下面是否存在一個相同通訊模式？非結構化通訊 沒有一個統一的通訊模式 例如：無結構化網格非結構化通訊 非結構化通信對算法設計的前期不會造成實質性的困難，但會使任務組合和處理器映射更為復雜。特別是要求組合策略既能創建尺寸大致相當的任務又要盡量減小任務間的通信時就需要非常復雜的算法，而這些算法在通信要求是動態的時又會在算法的執行過程中頻繁地使用，所以必須權衡利弊。通訊判據 所有任務是否執行大致相

33、當的通訊? 是否盡可能的局部通訊？ 通訊操作是否能并行執行? 同步任務的計算能否并行執行？通訊判據1）所有任務是否執行大致同樣多的通信？若不是，所設計的算法的可擴展性可能會不好。2）每個任務是否只與少數的近鄰通信？若不是，則可能導致全局通信。此時應設法將全局通信換成局部通信。3）諸通信操作能否并行執行？若不能，所設計的算法可能是低效的和不具可擴展性的。此時可試用分治策略來開發并行性。4）不同任務的計算能否并行執行？是否會因為等待數據而降低并行度？若不能并行執行，所設計的算法可能是低效的和不具可擴展性的。此時可考慮重新安排通信和計算的順序以改善這種情況。組合 方法描述 表面-容積效應 重復計算

34、組合判據方法描述 在任務劃分和通信分析階段，我們都沒有考慮特定的并行機對執行效率的影響。在組合階段，我們將重新考察劃分和通信階段所作的選擇，力圖得到一個在某一類并行機上能有效執行的并行算法。組合的目的是通過合并小尺寸的任務來減少任務數量和通信開銷。方法描述 組合是由抽象到具體的過程，是將組合的任務能在一類并行機上有效的執行； 合并小尺寸任務，減少任務數。如果任務數恰好等于處理器數，則也完成了映射過程； 通過增加任務的粒度和重復計算，可以減少通訊成本；在劃分階段，為了盡可能地開發問題的并行性，可能產生了大量的細粒度任務。但是大量的任務可能會增加通信開銷和任務創建開銷。 保持映射和擴展的靈活性，降

35、低軟件工程成本；表面-容積效應 通訊量與任務子集的表面成正比，計算量與任務子集的體積成正比； 增加重復計算有可能減少通訊量；表面-容積效應 通常，一個任務的通信需求正比與它所操作的數據域的表面積，而計算需求正比于它所操作的數據域的容積。因此一個計算單元的通信與計算之比隨任務尺寸的增加而減小。例如在二維問題中，“表面積”即是數據域的周長，它正比于問題的尺寸，而“容積”指數據域的面積，它正比于問題尺寸的平方。 以二維平面上的雅可比有限差分法5點格式為例。假設需要計算的數據是44矩陣。如果把計算每個元素算作一個任務，則有16個任務。每輪迭代中，每個任務都需要與其上下左右的任務通信，共需48次通信（當

36、然這些通信中許多可以并行進行）。如上圖（a）所示，每個箭頭表示一次通信。 表面-容積效應表面-容積效應 如果將相鄰的四個元素的計算作為一個任務則只需8次通信，如上圖（b）所示。雖然每次通信要傳遞兩個數據，但是相對于圖（a），通信的次數和通信量都大大減少了。可見，當小任務組合為大任務后，原來的某些數據傳遞被包含在大任務里面了，它們不再表現為通信，實際計算時，這些數據交換可以通過直接讀取內存完成。這正是增加粒度可以減少通信的原因。表面-容積效應 上例我們只想說明增加粒度可以減少通信次數和通信量。仔細思考我們會發現在上例中，圖（b）的通信開銷可能比圖（a）大。設通信建立的時間為S，傳遞一個數據的時間

37、為t。假設圖（a）的通信方式是方向相同的所有通信同時執行。比如所有的任務同時先向左傳遞，那么所有向左的通信需時間S+t。同理，向其它三個方向的通信各需時間S+t。所以圖（a）的通信開銷是4(S+2t)。對圖（b）也可進行相同的分析，但是圖（b）中每個通信要傳遞兩個數據，因此總的通信開銷比圖（a）大。表面-容積效應 上例中的通信是均勻的，且可以并行執行。實際上，實際問題的各小任務之間的通信很可能是不均勻的。比如一個問題可以分為A，B、 C三個任務，A與B之間通信頻繁，而它們與C之間通信很少。那么顯然應該將 A和 B組合成一個大任務，以避免通信對它們并行執行造成的影響。但是組合之后，出現了一個較大

38、的任務，完成這個大任務可能需要更長的時間。這時就需要權衡，看哪種方案更好。重復計算 重復計算（Replication Computation）也稱為冗余計算。它是指采用多余的計算來減少通信和/或整個計算時間。 重復計算減少通訊量，但增加了計算量，應保持恰當的平衡； 重復計算的目標應減少算法的總運算時間；重復計算 假定在二叉樹上求N個數的和，且要求最終在每個處理器上都有該結果。一種方法是先自葉向根求和，得到結果后再自根向葉播送，共需2 步。如下圖所示。 重復計算 示例：二叉樹上N個處理器求N個數的全和，要求每個處理器均保持全和。 二叉樹上求和，共需2logN步重復計算 以上述方式求和，處理器的利

39、用率是逐級減半的。如果在每一級每個處理器均接收兩個數據，求和后再發送給上一級的兩個處理器，那么經過 步后，每個處理器中就都得到了N個數的全和。計算過程如下圖所示。重復計算 示例：二叉樹上N個處理器求N個數的全和，要求每個處理器均保持全和。 蝶式結構求和，使用了重復計算，共需logN步靈活性和成本 要維持一個算法的可移植性和可擴展性，創建可變數目的任務是很關鍵的。組合時往往會使問題的任務數的變化范圍受到限制。根據經驗，為了能在映射階段達到負載平衡，任務數至少比處理器數多一個數量級。可用分析模型結合實際經驗討論最優的任務數。當然，靈活性并不意味著必須創建大量的任務。粒度可由編譯或運行時的參數控制。

40、重要的是不要對任務數進行不必要的限制。 組合時的另一個問題是要盡量減少軟件工程的代價，尤其是并行化一個串行程序時應盡量避免程序代碼的大量修改。 增加任務的粒度可以減少通信開銷，但組合時也要使算法保持足夠的靈活性并要盡量減少軟件工程的成本。這幾個目的有時是相互矛盾的，要權衡其利弊。組合判據 增加粒度是否減少了通訊成本？ 重復計算是否已權衡了其得益？ 是否保持了靈活性和可擴放性？ 組合的任務數是否與問題尺寸成比例? 是否保持了類似的計算和通訊？ 有沒有減少并行執行的機會？組合判據1）用增加局部性的方法實施組合是否減少了通信開銷？若不是，能否換用別的組合策略以減少通信開銷？2）如果使用了重復計算，是

41、否權衡了其得失？3）如果組合已復制了數據，是否已證實這不會因限制問題尺寸和處理器數量的變化范圍而犧牲了可擴展性？4）由組合產生的任務是否具有相似的計算和通信代價？5）任務數目是否仍然與問題尺寸成比例？若不是，算法是不可擴展的。6）如果組合減少了并行執行的機會，是否已證實現在的并發性仍能適應目前和將來的并行機？7）在不導致負載不平衡，不增加軟件工程代價和不減少可擴展性的前提下，任務數能否再進一步減少？在其它條件相同時，創建較少的粗粒度任務的算法通常是高效的。8）如果是并行化現有的串行程序，是否考慮了修改串行代碼的成本？如果此成本較高，應考慮別的組合策略。映射 方法描述 負載平衡算法 任務調度算法

42、 映射判據方法描述映射映射階段的任務是指定每個任務到哪個處理器上去執行。映射的目標是最小化全局執行時間和通信成本、最大化處理器的利用率，減少算法的總執行時間。為了達到以上目的，可采用以下策略：1）把能夠并發執行的任務放在不同的處理器上以增加并行度；2）把需頻繁通信的任務置于同一處理器上以提高局部性。這二者有時會沖突，需要權衡。對于某些基于域分解技術開發的算法，它們有固定數目的等尺寸的任務，通信結構化強，此時映射較簡單。如果任務的工作量不同，通信是非結構化的，可采用負載平衡算法。對于基于功能分解開發的算法，常常會產生一些由短暫任務組成的計算，它們只在執行的開始與結束時需要與別的任務協調，此時可用

43、任務調度算法進行任務分配。 方法描述 每個任務要映射到具體的處理器，定位到運行機器上； 任務數大于處理器數時，存在負載平衡和任務調度問題； 映射的目標：減少算法的執行時間 并發的任務 不同的處理器 任務之間存在高通訊的 同一處理器 映射實際是一種權衡，屬于NP完全問題；負載平衡算法 負載平衡算法負載平衡算法針對基于域分解技術開發的算法，有很多專用和通用的負載平衡技術（Load-Balancing Technigues）。 局部算法局部算法 局部負載平衡算法的思想是通過從近鄰遷入任務和向近鄰遷出任務來達到負載平衡。比如，每個處理器周期性地與鄰居比較負載的輕重。如果差異超過了某個閾值，就進行負載遷

44、移。如果自己的負載輕且有鄰居負載重，則從該鄰居遷入一些任務。反之，如果自己的負載重，而別的鄰居較空閑，則把自己的一部分負載遷給它。局部算法的優點是這個方案只利用局部的負載信息。同時，遷移任務時往往通信量很大，而此方案只在局部遷移，有利于提高效率。 負載平衡算法 概率方法概率方法（Probabilistic Method） 此法的思想是將任務隨機地分配給處理器，如果任務足夠多，則每個處理器預計能分到大致等量的任務。此法的優點是低價和可擴展性好；缺點是要求跨處理器進行通信，并且只有當任務數遠遠多于處理器數時才能達到預期的效果。 循環映射循環映射（Cyclic Mapping） 此法又稱為循環指派法

45、，即輪流地給處理器分配計算任務。它實際上是概率方法的一種形式。此法適用于各計算任務呈明顯的空間局部性的情況。 總之，局部算法代價小，但當負載變化大時調整很慢；概率方法代價小，可擴展性好，但通信代價可能較大，且只適用于任務數遠多于處理器數的情況；循環映射技術是概率映射的一種形式，而概率方法比其它技術易于導致可觀的通信。 負載平衡算法 靜態的：事先確定； 概率的：隨機確定； 動態的：執行期間動態負載； 基于域分解的： 遞歸對剖 局部算法 概率方法 循環映射任務調度算法任務調度算法任務調度算法任務調度算法的最關鍵之處是任務的分配策略。常用的調度模式有經理/雇員模式和非集中模式。經理經理/ /雇員模式

46、雇員模式 在此模式中，有一個進程（經理）負責分配任務，每個雇員向經理請求任務，得到任務后執行任務。使用預取方法（以使計算和通信重疊）可以提高效率。這種方案的一種變體是層次經理層次經理/ /雇員模式雇員模式。在此模式中，雇員被分成不相交的集合，每個集合有一個小經理。雇員們從小經理那里領取任務，小經理從經理處領取任務。經理/雇員模式的缺點是經理進程容易成為系統的瓶頸。非集中模式非集中模式 它就是無中心管理者的分布式調度法。結束檢測結束檢測 任務調度算法需要一種機制來檢測整個問題的計算何時結束。否則，空閑的雇員們將永不停止地發出任務請求。在經理/雇員模式中，經理可以判斷雇員是否都空閑了。所有的雇員都

47、空閑了就意味著整個問題的計算結束了。在非集中模式中結束檢測則比較困難，因為沒有一個進程知道全局的情況。任務調度算法 任務放在集中的或分散的任務池中，使用任務調度算法將池中的任務分配給特定的處理器。下面是兩種常用調度模式： 經理/雇員模式 非集中模式映射判據 采用集中式負載平衡方案，是否存在通訊瓶頸？ 采用動態負載平衡方案，調度策略的成本如何？映射判據 1）如果采用集中式負載平衡方案，是否檢查了中央管理者不會成為瓶頸？ 2）如果采用動態負載平衡方案，是否衡量過不同策略的成本？ 3）如果采用概率或循環指派法，是否有足夠多的任務？一般地，任務數應不少于處理器數的10倍。 4）如果要為一個問題設計一個

48、SPMD程序，是否考慮過基于動態任務創建和消除的算法？小 結 劃分 域分解和功能分解 通訊 任務間的數據交換 組合 任務的合并使得算法更有效 映射 將任務分配到處理器，并保持負載平衡并發的類型 并行程序必須以某種形式給出任務的并行性，它們可以以下面的方式給出： 數據并行 任務并行 流水并行 混合并行 數據并行 考慮下面的矩陣加法：A，B，C都是nn的矩陣，計算C=A+B為了計算C的每個元素，需要進行如下的計算： Ci,j=ai,j+bi,j 注意計算C的每個元素的操作都是一次加法，只是操作數不同而已，而且，每個元素的計算都是獨立的，它們可以并行執行。 這種類型的并行性表現為：并行的在不同的數據

49、上進行相同的操作，稱為數據并行性數據并行性。表現出這種并行性的問題通常稱為數據并行數據并行（的問題）。數據并行問題的一個突出特點是對大多數的這類問題，數據并行性的程度（可以并行進行數據并行的操作數目）隨著問題規模的增加而增大，這意味著對于這類問題，可以用較多的處理器來有效的處理更大規模的問題。這是一種比較簡單的并行方式，幸運的是，在實際的應用中，有很多有趣的問題都是數據并行的。任務并行 如果需要做如下的查詢：Select all where （MODEL=“Accord” AND YEAR=“1996”） AND（COLOR=“Green” OR COLOR=“Black”）； 這個查詢尋找數

50、據庫中所有1996年產的綠色或黑色的Accord車的資料。在關系數據庫中，這個查詢通常需要創建幾個中間表，一種可能的情形如下：一個表包含所有的Accord車數據，一個表包含所有1996款的車，一個表包含所有綠色車，一個表包含所有的黑色車。然后在這些表上進行Join操作，更詳細的說，數據庫將求出前兩個表的交集，從而得到1996款的Accord車的表，同時，將求出后兩個表的并，得到綠色或黑色的車的表，最后，用這兩個表求交集，就得到了最后的數據。上面的操作可以用下面的圖來形象的表示。任務并行任務并行 圖中的每個節點表示一個需要被計算的表（計算子任務），節點間的箭頭給出了任務間的依賴關系。 在上面圖中

51、，只要所有必需的子任務已經完成，后續子任務就可以進行，因此，通常來說，很多的子任務都可以并行的執行。這種并行性表現為子任務的并行執行，因此被稱為任務并行性。任務并行性比數據并行性要復雜一些（實際上，用任務并行性完全可以描述數據并行性的問題）。 流水并行 流水并行性是指在同一個數據流上同時的執行多個程序（后續的程序處理的是前面程序處理過的數據流）。流水并行性通常也被稱為流水線。在流水線上，計算的并行性表現為：每個處理器上運行一個不同的程序，它們構成一個完整的處理流程，每個處理器把自己處理完的數據馬上傳遞給（邏輯上）的下一個處理器。這樣實際上形成了處理器間的一個流水線，因此稱為流水并行性流水并行性

52、。 混合并行 很多的問題中的并行性表現為數據并行性，任務并行性和流水并行性的混合，某個問題表現出的流水并行性的數量通常獨立于問題的規模，而任務和數據并行性則相反，他們通常會隨問題規模的增長而增長。通常情況下，任務并行性可以用來開發粗粒度的并行性，而數據并行性用來開發細粒度的并行性，因此，任務并行性和數據并行性的組合可以用來有效的開發應用在大量處理器上的并行算法。 分解技術 設計并行算法的一個基本的步驟是描述完成給定任務所需要的計算，并把這些計算分解為可以并行執行的子任務集。對很多的問題來說，它們的任務圖都包含了足夠的并行性。對這樣的任務圖，各個任務可以在多個處理器上進行調度，從而使得問題得以并

53、行的完成。但不幸的是，很多的問題的任務圖中并不表現出如此豐富（或者稱為直觀）的并行性，相反的，它們往往包含一個任務或者多個需要串行執行的任務。對這樣的問題，我們需要將總的計算任務進行分解為一個可以并行執行的子任務集，這個過程稱為任務分解。一個好的任務分解應該具有下面的特點： 它應該有很高的并行度。并行度越高意味著這個分解后的任務可以在越多的處理器上并行的執行。 子任務間的交互（通信和同步）應該盡可能的少。交互少意味著處理器可以更專心的完成任務本身而不是其它由于通信和同步帶來的額外計算和等待。分解技術 很多情況下，這兩個要求會產生沖突，也就是說，有很高的并行度的任務分解，通常需要子任務間的大量交

54、互操作。如何平衡沖突是并行算法設計中的藝術。這一節中主要考慮如何提高子任務的并行度，關于子任務間的交互的討論在下一節進行。下面介紹幾種用于任務分解的常用的方法。對不同的問題，這些方法并不總是可行，而且也不一定會得到最有效的并行算法，但對很多問題來說，這些方法可以提供一個好的并行化的“著眼點”。其中的遞歸分解和數據分解可以被看成是相對通用的分解方法，因為它們可以用來對大多數的問題進行任務分解，而搜索分解要特殊一些，它只能應用于某些特定類型的問題。遞歸分解 遞歸分解通常用來對采用Divide-and-conquer(分治)方法的問題進行任務分解。這種方法將任務分解為獨立的子任務，這個分解的過程會遞

55、歸的進行。問題的答案是所有的子任務的答案的組合。分-治策略表現出一種自然的并行性。 考慮下面的問題：對n個元素的序列A進行快速排序。快速排序算法是一種分治的算法。算法首先選取一個軸元素x，然后把A分成兩個子序列A0和A1，其中A0中的所有元素小于x,而A1中的所有元素大于等于x,這是算法的分割部分。對得到的子序列遞歸地進行上面的分割過程，然后用經過排序的子序列組合成最后的結果序列A。快速排序的過程可以用下面的圖來示例。 遞歸分解遞歸分解其中的深色的元素為選中的軸元素。現在考慮如何根據算法的分-治特性來對快速排序算法進行任務分解。從上面的圖可以看出，對任務樹的每一層，每個子任務的繼續分割是可以并

56、行執行的，而且它們互相獨立。因此對計算的分解實際上也是一棵樹。算法開始時，只有一個序列（樹的根節點），我們用一個處理器來完成對它的第一次分割。分割完成后，我們得到了第一層中的2個子序列，對這兩個子序列的分割可以在兩個處理器上分別進行，（如果序列足夠長）樹中的第i層中會出現2i個子序列，它們可以由2i個處理器獨立并行完成。 遞歸分解遞歸分解處理的問題（的串行算法）并不一定是遞歸的。比如下面的問題：n個元素的未排序序列A，求A的最小值。下面的串行算法對A采取逐個掃描的方法：Minimum(A, n)min = A0；for (i=1; in; i+)if (Ai min)min = Ai；retu

57、rn min；遞歸分解這個算法本身沒有表現出任何的并行性（實際上與min的使用有關）。一種可行的解決辦法是采用分治的策略來重新得到一個算法，然后采用遞歸分解的方法來開發并行性。改寫后的算法如下（遞歸算法）：Minimum(A, n)if (n = 1)return A0；lmin = Minimum(A, n/2)；rmin = Minimum(A+n/2,n-n/2)；if (lmin rmin)return lmin；elsereturn rmin；這個算法很好理解，思路與上面的快速排序幾乎一樣。上面算法的遞歸樹如下圖（對8個元素的序列進行操作）所示：遞歸分解遞歸分解 現在對任務的分解就簡

58、單多了。注意與前面的并行快速排序算法相反，這個分-治算法更多的計算時間花費在結果的組合階段。因此，這個算法的并行版本在執行時，最開始有n個任務可以并行執行（雖然不需要），然后可以并行執行的任務依次減半（沿著樹往上走），到根節點時，只能由一個處理器執行來的到最后的結果。 數據分解 對那些具有大型數據結構的算法來說，數據分解是一種非常有用的方法。它可以分為兩個步驟。第一個步驟中，對計算操作的數據（或稱為域）進行劃分，第二個步驟根據數據的劃分來將對應的計算組織成相應的子任務。對數據的劃分可以用下面的方法進行。 對輸出數據進行劃分 對中間數據進行劃分 對輸入數據進行劃分數據分解 一般的來說，當我們需要

59、決定對數據如何劃分或者是對那些數據進行劃分時，我們需要看哪一種劃分能夠得到一個最好的（或者最簡單的）計算劃分。因為數據劃分的目的只不過是為了得到一種合理的計算劃分。對有些問題來說，對輸入數據進行劃分效果比較好，而對有些問題，對輸出數據（計算結果）進行劃分要更好一些。在使用數據分解的時候，需要對所有可能的數據劃分方式進行考察。 混合分解方法對問題進行任務分解需要靈活的應用上面的方法。遞歸分解，數據分解和搜索分解雖然有不同，但它們之間卻不一定相互排斥，因此，在實際的應用中，為了得到更高的并行度，可以將這些分解方法組合使用。前面我們討論過快速排序算法，這個算法對大小為n的序列排序時，可以產生O(n)

60、個子任務，但由于任務之間的依賴關系和任務分配的不均勻性，有效的并行性相當有限。比如，第一個任務（將初始序列分割為兩個子序列）復雜度為O(n)，這確定了并行算法的時間復雜度的下界。快速排序也可以采用對輸入數據進行分解的方法，對快速排序采用輸入數據分解以及遞歸分解的方法可以得到一個更為高效的算法 任務的分配:任務映射 上一節中討論的分解算法可以用來識別出問題中可以提供的并行性，并且把計算分解為可以并行執行的子任務。要完成對問題的計算，下一步是將這些子任務分配給可用的處理器來執行。給出一個子任務集和一個可用處理器集，有很多種可能的方法來在它們之間建立某種映射關系，為了判斷哪種映射更好，我們需要使用下