第23講 并行算法設(shè)計方法

并行算法的一般設(shè)計過程

PCAM設(shè)計方法

1

PCAM設(shè)計方法學(xué)設(shè)計并行算法的四個階段劃分(Partitioning)通訊(Communication)組合(Agglomeration)映射(Mapping)劃分：分解成小的任務(wù)，開拓并發(fā)性；通訊：確定諸任務(wù)間的數(shù)據(jù)交換，監(jiān)測劃分的合理性；組合：依據(jù)任務(wù)的局部性，組合成更大的任務(wù)；映射：將每個任務(wù)分配到處理器上，提高算法的性能。2

PCAM設(shè)計過程3劃分

1方法描述

2域分解

3功能分解

4劃分判據(jù)4劃分方法描述充分開拓算法的并發(fā)性和可擴(kuò)放性；先進(jìn)行數(shù)據(jù)分解(稱域分解)，再進(jìn)行計算功能的分解(稱功能分解)；使數(shù)據(jù)集和計算集互不相交；劃分階段忽略處理器數(shù)目和目標(biāo)機(jī)器的體系結(jié)構(gòu)；能分為兩類劃分：域分解(domaindecomposition)功能分解(functionaldecomposition)5域分解劃分的對象是數(shù)據(jù)，可以是算法的輸入數(shù)據(jù)、中間處理數(shù)據(jù)和輸出數(shù)據(jù)；將數(shù)據(jù)分解成大致相等的小數(shù)據(jù)片；劃分時考慮數(shù)據(jù)上的相應(yīng)操作；如果一個任務(wù)需要別的任務(wù)中的數(shù)據(jù)，則會產(chǎn)生任務(wù)間的通訊；6域分解示例：三維網(wǎng)格的域分解，各格點(diǎn)上計算都是重復(fù)的。下圖是三種分解方法：實際上，分解沿X、Y、Z維及它們的任意組合都可以進(jìn)行。開始時，應(yīng)進(jìn)行三維劃分，因為該方法能提供最大靈活性。

7域分解不規(guī)則區(qū)域的分解示例：8功能分解劃分的對象是計算，將計算劃分為不同的任務(wù)，其出發(fā)點(diǎn)不同于域分解；劃分后，研究不同任務(wù)所需的數(shù)據(jù)。如果這些數(shù)據(jù)不相交的，則劃分是成功的；如果數(shù)據(jù)有相當(dāng)?shù)闹丿B，意味著要重新進(jìn)行域分解和功能分解；功能分解是一種更深層次的分解。9功能分解示例1：搜索樹搜索樹沒有明顯的可分解的數(shù)據(jù)結(jié)構(gòu)，但易于進(jìn)行細(xì)粒度的功能分解：開始時根生成一個任務(wù)，對其評價后，如果它不是一個解，就生成若干葉結(jié)點(diǎn)，這些葉結(jié)點(diǎn)可以分到各個處理器上并行地繼續(xù)搜索。

示例2：氣候模型10劃分判據(jù)劃分是否具有靈活性？(所劃分的任務(wù)數(shù)是否高于目標(biāo)機(jī)上處理器數(shù)目一個量級

?)劃分是否避免了冗余計算和存儲？(若不是，則產(chǎn)生的算法對大型問題可能不是可擴(kuò)展的。

)劃分任務(wù)尺寸是否大致相當(dāng)？(若不是，則分配處理器時很難做到負(fù)載平衡。

)11劃分判據(jù)任務(wù)數(shù)與問題尺寸是否成比例？(理想情況下，問題尺寸的增加應(yīng)引起任務(wù)數(shù)的增加而不是任務(wù)尺寸的增加。若不是這樣，算法可能不能求解更大的問題，盡管有更多的處理器。)功能分解是一種更深層次的分解，是否合理？(多考慮幾種選擇可以提高靈活性。同時既要考慮域分解又要考慮功能分解。)12通訊

方法描述

四種通訊模式

通訊判據(jù)

13通訊方法描述通訊是PCAM設(shè)計過程的重要階段；劃分產(chǎn)生的諸任務(wù)，一般不能完全獨(dú)立執(zhí)行，需要在任務(wù)間進(jìn)行數(shù)據(jù)交流；從而產(chǎn)生了通訊；功能分解確定了諸任務(wù)之間的數(shù)據(jù)流；諸任務(wù)是并發(fā)執(zhí)行的，通訊則限制了這種并發(fā)性；14四種通訊模式局部/全局通訊結(jié)構(gòu)化/非結(jié)構(gòu)化通訊靜態(tài)/動態(tài)通訊同步/異步通訊15局部通訊通訊限制在一個鄰域內(nèi)16局部通訊當(dāng)一個任務(wù)僅要求與鄰近的其它任務(wù)通信時，就呈現(xiàn)局部通信模式。例如在數(shù)值計算中的雅可比有限差分法。如果采用5點(diǎn)格式，迭代公式為:

17全局通訊通訊非局部的例如：AlltoAllMaster-Worker5372118全局通訊在全局通信中，有很多任務(wù)參與交換數(shù)據(jù)。這可能造成過多的通信，從而限制了并行執(zhí)行的機(jī)會。例如我們希望計算

。為此，我們使用一個根進(jìn)程S負(fù)責(zé)從各進(jìn)程一次接收一個值（xi）并進(jìn)行累加。這時就會出現(xiàn)全局通信的局面。

19全局通訊采用分治策略可以開拓求和的并行性：

上式右邊的兩個求和可以同時執(zhí)行，并且每一個仍可按同樣的方式進(jìn)一步分解。求和的過程如下圖所示，同一級上的求和可以并行執(zhí)行。這樣就可以避免全局通信，并提高算法的并行度。圖中

表示處理器X至處理器Y上所有數(shù)據(jù)的和。

20全局通訊21結(jié)構(gòu)化通訊每個任務(wù)的通訊模式是相同的；下面是否存在一個相同通訊模式？22非結(jié)構(gòu)化通訊沒有一個統(tǒng)一的通訊模式例如：無結(jié)構(gòu)化網(wǎng)格23通訊判據(jù)所有任務(wù)是否執(zhí)行大致相當(dāng)?shù)耐ㄓ?(若不是，所設(shè)計的算法的可擴(kuò)展性可能會不好。)是否盡可能的局部通訊？(若不是，則可能導(dǎo)致全局通信。此時應(yīng)設(shè)法將全局通信換成局部通信。)24通訊判據(jù)通訊操作是否能并行執(zhí)行?(若不能，所設(shè)計的算法可能是低效的和不具可擴(kuò)展性的。此時可試用分治策略來開發(fā)并行性。)同步任務(wù)的計算能否并行執(zhí)行？(是否會因為等待數(shù)據(jù)而降低并行度？若不能并行執(zhí)行，所設(shè)計的算法可能是低效的和不具可擴(kuò)展性的。此時可考慮重新安排通信和計算的順序以改善這種情況。

)25

方法描述

表面-容積效應(yīng)

重復(fù)計算

組合判據(jù)

組合26方法描述組合是由抽象到具體的過程，是將組合的任務(wù)能在一類并行機(jī)上有效的執(zhí)行；合并小尺寸任務(wù)，減少任務(wù)數(shù)。如果任務(wù)數(shù)恰好等于處理器數(shù)，則也完成了映射過程；通過增加任務(wù)的粒度和重復(fù)計算，可以減少通訊成本；保持映射和擴(kuò)展的靈活性，降低軟件工程成本；27增加粒度在劃分階段，為了盡可能地開發(fā)問題的并行性，可能產(chǎn)生了大量的細(xì)粒度任務(wù)。但是大量的任務(wù)可能會增加通信開銷和任務(wù)創(chuàng)建開銷。28表面-容積效應(yīng)通訊量與任務(wù)子集的表面成正比，計算量與任務(wù)子集的體積成正比；增加重復(fù)計算有可能減少通訊量；29表面-容積效應(yīng)因此一個計算單元的通信與計算之比隨任務(wù)尺寸的增加而減小。例如在二維問題中，“表面積”即是數(shù)據(jù)域的周長，它正比于問題的尺寸，而“容積”指數(shù)據(jù)域的面積，它正比于問題尺寸的平方。

30表面-容積效應(yīng)以二維平面上的雅可比有限差分法5點(diǎn)格式為例。假設(shè)需要計算的數(shù)據(jù)是4×4矩陣。如果把計算每個元素算作一個任務(wù)，則有16個任務(wù)。每輪迭代中，每個任務(wù)都需要與其上下左右的任務(wù)通信，共需48次通信（當(dāng)然這些通信中許多可以并行進(jìn)行）。如下圖（a）所示，每個箭頭表示一次通信。

31表面-容積效應(yīng)如果將相鄰的四個元素的計算作為一個任務(wù)則只需8次通信，如上圖（b）所示。雖然每次通信要傳遞兩個數(shù)據(jù)，但是相對于圖（a），通信的次數(shù)和通信量都大大減少了?？梢姡?dāng)小任務(wù)組合為大任務(wù)后，原來的某些數(shù)據(jù)傳遞被“包含”在大任務(wù)里面了，它們不再表現(xiàn)為通信，實際計算時，這些數(shù)據(jù)交換可以通過直接讀取內(nèi)存完成。這正是增加粒度可以減少通信的原因。

32重復(fù)計算重復(fù)計算減少通訊量，但增加了計算量，應(yīng)保持恰當(dāng)?shù)钠胶猓恢貜?fù)計算的目標(biāo)應(yīng)減少算法的總運(yùn)算時間；33重復(fù)計算假定在二叉樹上求N個數(shù)的和，且要求最終在每個處理器上都有該結(jié)果。一種方法是先自葉向根求和，得到結(jié)果后再自根向葉播送，共需2

步。如下圖所示。

34重復(fù)計算以上述方式求和，處理器的利用率是逐級減半的。如果在每一級每個處理器均接收兩個數(shù)據(jù)，求和后再發(fā)送給上一級的兩個處理器，那么經(jīng)過

步后，每個處理器中就都得到了N個數(shù)的全和。計算過程如下圖所示。

35組合判據(jù)增加粒度是否減少了通訊成本？（若不是，能否換用別的組合策略以減少通信開銷？）重復(fù)計算是否已權(quán)衡了其得益？是否保持了靈活性和可擴(kuò)放性？36組合判據(jù)組合的任務(wù)數(shù)是否與問題尺寸成比例?（若不是，算法是不可擴(kuò)展的。）是否保持了類似的計算和通訊？有沒有減少并行執(zhí)行的機(jī)會？（是否已證實現(xiàn)在的并發(fā)性仍能適應(yīng)目前和將來的并行機(jī)？）37

方法描述

負(fù)載平衡算法

任務(wù)調(diào)度算法

映射判據(jù)映射38方法描述每個任務(wù)要映射到具體的處理器，定位到運(yùn)行機(jī)器上；任務(wù)數(shù)大于處理器數(shù)時，存在負(fù)載平衡和任務(wù)調(diào)度問題；映射的目標(biāo)：減少算法的執(zhí)行時間并發(fā)的任務(wù)

不同的處理器任務(wù)之間存在高通訊的

同一處理器映射實際是一種權(quán)衡，屬于NP完全問題；39負(fù)載平衡算法靜態(tài)的：事先確定；概率的：隨機(jī)確定；動態(tài)的：執(zhí)行期間動態(tài)負(fù)載；基于域分解的：遞歸對剖局部算法概率方法循環(huán)映射40負(fù)載平衡算法

局部算法局部負(fù)載平衡算法的思想是通過從近鄰遷入任務(wù)和向近鄰遷出任務(wù)來達(dá)到負(fù)載平衡。比如，每個處理器周期性地與鄰居比較負(fù)載的輕重。如果差異超過了某個閾值，就進(jìn)行負(fù)載遷移。如果自己的負(fù)載輕且有鄰居負(fù)載重，則從該鄰居遷入一些任務(wù)。反之，如果自己的負(fù)載重，而別的鄰居較空閑，則把自己的一部分負(fù)載遷給它。局部算法的優(yōu)點(diǎn)是這個方案只利用局部的負(fù)載信息。同時，遷移任務(wù)時往往通信量很大，而此方案只在局部遷移，有利于提高效率。

41負(fù)載平衡算法

概率方法（ProbabilisticMethod）此法的思想是將任務(wù)隨機(jī)地分配給處理器，如果任務(wù)足夠多，則每個處理器預(yù)計能分到大致等量的任務(wù)。此法的優(yōu)點(diǎn)是低價和可擴(kuò)展性好；缺點(diǎn)是要求跨處理器進(jìn)行通信，并且只有當(dāng)任務(wù)數(shù)遠(yuǎn)遠(yuǎn)多于處理器數(shù)時才能達(dá)到預(yù)期的效果。

循環(huán)映射（CyclicMapping）此法又稱為循環(huán)指派法，即輪流地給處理器分配計算任務(wù)。它實際上是概率方法的一種形式。此法適用于各計算任務(wù)呈明顯的空間局部性的情況。

總之，局部算法代價小，但當(dāng)負(fù)載變化大時調(diào)整很慢；概率方法代價小，可擴(kuò)展性好，但通信代價可能較大，且只適用于任務(wù)數(shù)遠(yuǎn)多于處理器數(shù)的情況；循環(huán)映射技術(shù)是概率映射的一種形式，而概率方法比其它技術(shù)易于導(dǎo)致可觀的通信。

42負(fù)載平衡算法43任務(wù)調(diào)度算法任務(wù)放在集中的或分散的任務(wù)池中，使用任務(wù)調(diào)度算法將池中的任務(wù)分配給特定的處理器。下面是兩種常用調(diào)度模式：經(jīng)理/雇員模式

經(jīng)理/雇員模式：

在此模式中，有一個進(jìn)程（經(jīng)理）負(fù)責(zé)分配任務(wù)，每個雇員向經(jīng)理請求任務(wù)，得到任務(wù)后執(zhí)行任務(wù)。使用預(yù)取方法（以使計算和通信重疊）可以提高效率。

層次經(jīng)理/雇員模式：在此模式中，雇員被分成不相交的集合，每個集合有一個小經(jīng)理。雇員們從小經(jīng)理那里領(lǐng)取任務(wù)，小經(jīng)理從經(jīng)理處領(lǐng)取任務(wù)。經(jīng)理/雇員模式的缺點(diǎn)是經(jīng)理進(jìn)程容易成為系統(tǒng)的瓶頸。44任務(wù)調(diào)度算法非集中模式它就是無中心管理者的分布式調(diào)度法。

45映射判據(jù)如果采用集中式負(fù)載平衡方案，是否檢查了中央管理者不會成為瓶頸？如果采用動態(tài)負(fù)載平衡方案，是否衡量過不同策略的成本？

如果采用概率或循環(huán)指派法，是否有足夠多的任務(wù)？一般地，任務(wù)數(shù)應(yīng)不少于處理器數(shù)的10倍。46并行算法的復(fù)雜性度量串行算法的復(fù)雜性度量最壞情況下的復(fù)雜度(Worst-CASEComplexity)期望復(fù)雜度(ExpectedComplexity)并行算法的幾個復(fù)雜性度量指標(biāo)運(yùn)行時間t(n):包含計算時間和通訊時間，分別用計算時間步和選路時間步作單位。n為問題實例的輸入規(guī)模。處理器數(shù)p(n)并行算法成本c(n):c(n)=t(n)p(n)總運(yùn)算量W(n):并行算法求解問題時所完成的總的操作步數(shù)。

47Brent定理令W(n)是某并行算法A在運(yùn)行時間T(n)內(nèi)所執(zhí)行的運(yùn)算量，則A使用p臺處理器可在t(n)=O(W(n)/p+T(n))時間內(nèi)執(zhí)行完畢。W(n)和c(n)密切相關(guān)P=O(W(n)/T(n))時，W(n)和c(n)兩者是漸進(jìn)一致的對于任意的p，c(n)?W(n)并行算法的復(fù)雜性度量48算法級性能評測加速比性能定律并行系統(tǒng)的加速比是指對于一個給定的應(yīng)用，并行算法（或并行程序）的執(zhí)行速度相對于串行算法（或串行程序）的執(zhí)行速度加快了多少倍。Amdahl定律Gustafson定律SunNi定律可擴(kuò)放性評測標(biāo)準(zhǔn)等效率度量標(biāo)準(zhǔn)等速度度量標(biāo)準(zhǔn)平均延遲度量標(biāo)準(zhǔn)49Amdahl定律P：處理器數(shù)；W：問題規(guī)模（計算負(fù)載、工作負(fù)載，給定問題的總計算量）；Ws：應(yīng)用程序中的串行分量，f是串行分量比例（f=Ws/W，Ws=W1）；WP：應(yīng)用程序中可并行化部分，1-f為并行分量比例；Ws+Wp=W；Ts：串行執(zhí)行時間，Tp：并行執(zhí)行時間；S：加速比，E：效率；出發(fā)點(diǎn)：固定不變的計算負(fù)載；固定的計算負(fù)載分布在多個處理器上的，增加處理器加快執(zhí)行速度，從而達(dá)到了加速的目的。50固定負(fù)載的加速公式：

Ws+Wp可相應(yīng)地表示為f+（1-f）

p→∞時，上式極限為：S=1/fWo為額外開銷

Amdahl定律51Amdahl定律52Gustafson定律出發(fā)點(diǎn)：對于很多大型計算，精度要求很高，即在此類應(yīng)用中精度是個關(guān)鍵因素，而計算時間是固定不變的。此時為了提高精度，必須加大計算量，相應(yīng)地亦必須增多處理器數(shù)才能維持時間不變；除非學(xué)術(shù)研究，在實際應(yīng)用中沒有必要固定工作負(fù)載而計算程序運(yùn)行在不同數(shù)目的處理器上，增多處理器必須相應(yīng)地增大問題規(guī)模才有實際意義。

Gustafson加速定律:并行開銷Wo：53Gustafson定律54Sun和Ni定律基本思想：只要存儲空間許可，應(yīng)盡量增大問題規(guī)模以產(chǎn)生更好和更精確的解（此時可能使執(zhí)行時間略有增加）。假定在單節(jié)點(diǎn)上使用了全部存儲容量M并在相應(yīng)于W的時間內(nèi)求解之，此時工作負(fù)載W=fW+（1-f）W。在p個節(jié)點(diǎn)的并行系統(tǒng)上，能夠求解較大規(guī)模的問題是因為存儲容量可增加到pM。令因子G（p）反應(yīng)存儲容量增加到p倍時并行工作負(fù)載的增加量，所以擴(kuò)大后的工作負(fù)載W=fW+（1-f）G（p）W。存儲受限的加速公式：并行開銷Wo:55Sun和Ni定律G（p）=1時就是Amdahl加速定律；

G（p）=p變?yōu)閒+p（1-f），就是Gustafson加速定律G（p）>p時，相應(yīng)于計算機(jī)負(fù)載比存儲要求增加得快，此時Sun和Ni加速均比Amdahl加速和Gustafson加速為高。

56加速比討論參考的加速經(jīng)驗公式：p/logp≤S≤P線性加速比：很少通信開銷的矩陣相加、內(nèi)積運(yùn)算等p/logp的加速比：分治類的應(yīng)用問題通信密集類的應(yīng)用問題：S=1/C（p）超線性加速絕對加速：最佳并行算法與串行算法相對加速：同一算法在單機(jī)和并行機(jī)的運(yùn)行時間57可擴(kuò)放性評測標(biāo)準(zhǔn)并行計算的可擴(kuò)放性（Scalability）也是主要性能指標(biāo)可擴(kuò)放性最簡樸的含意是在確定的應(yīng)用背景下，計算機(jī)系統(tǒng)（或算法或程序等）性能隨處理器數(shù)的增加而按比例提高的能力影響加速比的因素：處理器數(shù)與問題規(guī)模求解問題中的串行分量并行處理所引起的額外開銷（通信、等待、競爭、冗余操作和同步等）加大的處理器數(shù)超過了算法中的并發(fā)程度增加問題的規(guī)模有利于提高加速的因素：較大的問題規(guī)?？商峁┹^高的并發(fā)度；額外開銷的增加可能慢于有效計算的增加；算法中的串行分量比例不是固定不變的（串行部分所占的比例隨著問題規(guī)模的增大而縮?。?。增加處理器數(shù)會增大額外開銷和降低處理器利用率，所以對于一個特定的并行系統(tǒng)（算法或程序），它們能否有效利用不斷增加的處理器的能力應(yīng)是受限的，而度量這種能力就是可擴(kuò)放性這一指標(biāo)。

58可擴(kuò)放性:調(diào)整什么和按什么比例調(diào)整并行計算要調(diào)整的是處理數(shù)p和問題規(guī)模W，兩者可按不同比例進(jìn)行調(diào)整，此比例關(guān)系（可能是線性的，多項式的或指數(shù)的等）就反映了可擴(kuò)放的程度。并行算法和體系結(jié)構(gòu)可擴(kuò)放性研究的主要目的：確定解決某類問題用何種并行算法與何種并行體系結(jié)構(gòu)的組合，可以有效地利用大量的處理器；對于運(yùn)行于某種體系結(jié)構(gòu)的并行機(jī)上的某種算法當(dāng)移植到大規(guī)模處理機(jī)上后運(yùn)行的性能；對固定的問題規(guī)模，確定在某類并行機(jī)上最優(yōu)的處理器數(shù)與可獲得的最大的加速比；用于指導(dǎo)改進(jìn)并行算法和并行機(jī)體系結(jié)構(gòu)，以使并行算法盡可能地充分利用可擴(kuò)充的大量處理器目前無一個公認(rèn)的、標(biāo)準(zhǔn)的和被普遍接受的嚴(yán)格定義和評判它的標(biāo)準(zhǔn)可擴(kuò)放性評測標(biāo)準(zhǔn)59等速度度量標(biāo)準(zhǔn)p表示處理器個數(shù)，W表示要求解問題的工作量或稱問題規(guī)模（在此可指浮點(diǎn)操作個數(shù)），T為并行執(zhí)行時間，定義并行計算的速度V為工作量W除以并行時間Tp個處理器的并行系統(tǒng)的平均速度定義為并行速度V除以處理器個數(shù)p：W是使用p個處理器時算法的工作量，令W’表示當(dāng)處理數(shù)從p增大到p’時，為了保持整個系統(tǒng)的平均速度不變所需執(zhí)行的工作量，則可得到處理器數(shù)從p到p’時平均速度可擴(kuò)放度量標(biāo)準(zhǔn)公式60等速度度量標(biāo)準(zhǔn)優(yōu)點(diǎn)：直觀地使用易測量的機(jī)器性能速度指標(biāo)來度量缺點(diǎn)：某些非浮點(diǎn)運(yùn)算可能造成性能的變化61并行數(shù)值算法

三角形方程組的求解

62基本術(shù)語線性方程組的定義和符號

a1,1x1+a1,2x2+…+a1,nxn=b1a2,1x1+a2,1x2+…+a2