西安交大并行計算理論趙銀亮課件第七章

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

7.1PCAM設(shè)計方法學(xué)

7.2劃分

7.3通信

7.4組合

7.5映射

7.6小結(jié)

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

PCAM設(shè)計過程第七章并行算法的一般設(shè)計過程

7.1PCAM設(shè)計方法學(xué)

7.2劃分

7.3通信

7.4組合

7.5映射

7.6小結(jié)

7.2.1劃分方法描述充分開拓算法的并發(fā)性和可擴(kuò)放性；先進(jìn)行數(shù)據(jù)分解(稱域分解)，再進(jìn)行計算功能的分解(稱功能分解)；使數(shù)據(jù)集和計算集互不相交；劃分階段忽略處理器數(shù)目和目標(biāo)機(jī)器的體系結(jié)構(gòu)；能分為兩類劃分：域分解(domaindecomposition)功能分解(functionaldecomposition)7.2.2域分解劃分的對象是數(shù)據(jù)，可以是算法的輸入數(shù)據(jù)、中間處理數(shù)據(jù)和輸出數(shù)據(jù)；將數(shù)據(jù)分解成大致相等的小數(shù)據(jù)片；劃分時考慮數(shù)據(jù)上的相應(yīng)操作；如果一個任務(wù)需要別的任務(wù)中的數(shù)據(jù)，則會產(chǎn)生任務(wù)間的通信；域分解示例：三維網(wǎng)格的域分解，各格點上計算都是重復(fù)的。下圖是三種分解方法：域分解不規(guī)則區(qū)域的分解示例：7.2.3功能分解劃分的對象是計算，將計算劃分為不同的任務(wù)，其出發(fā)點不同于域分解；劃分后，研究不同任務(wù)所需的數(shù)據(jù)。如果這些數(shù)據(jù)不相交的，則劃分是成功的；如果數(shù)據(jù)有相當(dāng)?shù)闹丿B，意味著要重新進(jìn)行域分解和功能分解；功能分解是一種更深層次的分解。功能分解示例1：搜索樹示例2：氣候模型7.2.4劃分判據(jù)劃分是否具有靈活性？劃分是否避免了冗余計算和存儲？劃分任務(wù)尺寸是否大致相當(dāng)？任務(wù)數(shù)與問題尺寸是否成比例？功能分解是一種更深層次的分解，是否合理？第七章并行算法的一般設(shè)計過程

7.1PCAM設(shè)計方法學(xué)

7.2劃分

7.3通信

7.4組合

7.5映射

7.6小結(jié)

7.3.1通信方法描述通信是PCAM設(shè)計過程的重要階段；劃分產(chǎn)生的諸任務(wù)，一般不能完全獨立執(zhí)行，需要在任務(wù)間進(jìn)行數(shù)據(jù)交流；從而產(chǎn)生了通信；功能分解確定了諸任務(wù)之間的數(shù)據(jù)流；諸任務(wù)是并發(fā)執(zhí)行的，通信則限制了這種并發(fā)性；

7.3.2四種通信模式局部/全局通信結(jié)構(gòu)化/非結(jié)構(gòu)化通信靜態(tài)/動態(tài)通信同步/異步通信局部通信通信限制在一個鄰域內(nèi)全局通信通信非局部的例如：AlltoAllMaster-Worker53721結(jié)構(gòu)化通信每個任務(wù)的通信模式是相同的；下面是否存在一個相同通信模式？非結(jié)構(gòu)化通信沒有一個統(tǒng)一的通信模式例如：無結(jié)構(gòu)化網(wǎng)格7.3.3通信判據(jù)所有任務(wù)是否執(zhí)行大致相當(dāng)?shù)耐ㄐ?是否盡可能的局部通信？通信操作是否能并行執(zhí)行?同步任務(wù)的計算能否并行執(zhí)行？第七章并行算法的一般設(shè)計過程

7.1PCAM設(shè)計方法學(xué)

7.2劃分

7.3通信

7.4組合

7.5映射

7.6小結(jié)7.4.1方法描述組合是由抽象到具體的過程，是將組合的任務(wù)能在一類并行機(jī)上有效的執(zhí)行；合并小尺寸任務(wù)，減少任務(wù)數(shù)。如果任務(wù)數(shù)恰好等于處理器數(shù)，則也完成了映射過程；通過增加任務(wù)的粒度和重復(fù)計算，可以減少通信成本；保持映射和擴(kuò)展的靈活性，降低軟件工程成本；7.4.2表面-容積效應(yīng)一個任務(wù)的通信量與所操作的子域的表面積成比例；計算量與體積成比例通信計算之比與任務(wù)粒度成反比7.4.3重復(fù)計算重復(fù)計算減少通信量，但增加了計算量，應(yīng)保持恰當(dāng)?shù)钠胶?；重?fù)計算的目標(biāo)應(yīng)減少算法的總運算時間；重復(fù)計算示例：二叉樹上N個處理器求N個數(shù)的全和，要求每個處理器均保持全和。

二叉樹上求和，共需2logN步重復(fù)計算示例：二叉樹上N個處理器求N個數(shù)的全和，要求每個處理器均保持全和。

蝶式結(jié)構(gòu)求和，使用了重復(fù)計算，共需logN步7.4.4組合判據(jù)增加粒度是否減少了通信成本？重復(fù)計算是否已權(quán)衡了其得益？在大數(shù)據(jù)計算中對重復(fù)計算進(jìn)行權(quán)衡的因素更多，重復(fù)計算降低了結(jié)點的作業(yè)吞吐率，可能引起推測執(zhí)行是否保持了可擴(kuò)放性？組合的任務(wù)數(shù)是否與問題尺寸成比例?是否保持了類似的計算和通信？第七章并行算法的一般設(shè)計過程

7.1PCAM設(shè)計方法學(xué)

7.2劃分

7.3通信

7.4組合

7.5映射

7.6小結(jié)7.5.1映射技術(shù)描述一旦問題被分解成并發(fā)任務(wù)，它們必須被映射到進(jìn)程（進(jìn)程運行在并行平臺上）；任務(wù)數(shù)大于處理器數(shù)時，存在負(fù)載平衡和任務(wù)調(diào)度問題；映射的目標(biāo)：最小化開銷（基本開銷是指通信和空閑）并發(fā)的任務(wù)

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

同一處理器最小化開銷通常表現(xiàn)出矛盾的目標(biāo)（映射實際是一種權(quán)衡，屬于NP完全問題）映射技術(shù)最小化空閑映射必須同時最小化空閑和平衡負(fù)載，只平衡負(fù)載不會最小化空閑。最小化空閑的映射技術(shù)靜態(tài)和動態(tài)的映射技術(shù)靜態(tài)映射：任務(wù)預(yù)先映射到進(jìn)程（a-priori）。要這樣做，我們必須對每個任務(wù)的大小有很好的估計，即使在這種情況下，這個問題也是NP完全的動態(tài)映射：任務(wù)在運行時映射給進(jìn)程。這可能是因為任務(wù)產(chǎn)生于運行時，或者任務(wù)的尺寸不知道。其他決定技術(shù)選擇的因素包括關(guān)聯(lián)給任務(wù)的數(shù)據(jù)大小以及領(lǐng)域的性質(zhì)。靜態(tài)映射模式基于數(shù)據(jù)劃分的映射基于任務(wù)圖劃分的映射復(fù)合的映射基于數(shù)據(jù)劃分的映射

我們可以合并數(shù)據(jù)劃分和計算劃分為任務(wù)，計算劃分依照“擁有者進(jìn)行計算”原則進(jìn)行.對稠密矩陣簡單的數(shù)據(jù)分解模式是1-D按塊分布模式.按塊數(shù)組分布模式

塊數(shù)組分布模式也可推廣到高維.塊數(shù)組分布模式的例子

對于稠密矩陣A和B相乘，我們可以使用塊分解來劃分輸出矩陣C.考慮到負(fù)載均衡，我么給予每個任務(wù)相同數(shù)量的矩陣C的因素.(注意到每個C因素對應(yīng)一單個點積.)選擇精確的分解(1-D或2-D)由涉及到的通信開銷決定.通常，高維分解允許更多的進(jìn)程用上.稠密矩陣乘法中的數(shù)據(jù)共享循環(huán)與塊循環(huán)分布如果與數(shù)據(jù)關(guān)聯(lián)的計算量是變化的，塊劃分可能導(dǎo)致顯著的負(fù)載不均衡.一個簡單例子出現(xiàn)在稠密矩陣的LU分解（高斯消去法）中.稠密矩陣的LU分解

將LU分解劃分出14個任務(wù)-注意負(fù)載明顯不均衡.塊循環(huán)分布塊分布模式的變種能用來減輕負(fù)載不均衡和空閑問題.將數(shù)組劃分成別可用進(jìn)程更多的塊.按照輪轉(zhuǎn)方式將數(shù)據(jù)塊賦予進(jìn)程，以使得每個進(jìn)程得到幾個不相鄰的塊.高斯消去法中的塊循環(huán)分布

高斯消去法中矩陣的活動部分變動.通過將塊以塊循環(huán)方式賦予，每個處理器收到從矩陣不同部分來的塊.塊循環(huán)分布的例子

四個進(jìn)程的一維或者二維塊循環(huán)分布。塊循環(huán)分布循環(huán)分布是一種特殊情形，其中塊的大小為1.塊分布是一種特殊情形，其中塊大小為

n/p,其中

n

是矩陣維數(shù)，p

是進(jìn)程數(shù).基于數(shù)據(jù)分解的圖劃分對于稀疏矩陣,塊分解更為復(fù)雜.考慮稀疏矩陣乘向量.矩陣圖是個有用的計算（節(jié)點個數(shù)）與通信（每個節(jié)點的度）的指示.在這種情況下，我們會對圖劃分以使得等量節(jié)點給每個進(jìn)程,從而最小化圖劃分中邊的計數(shù).劃分

蘇必略湖

的圖

按最小割劃分隨機(jī)劃分基于任務(wù)劃分的映射對著進(jìn)程劃分給定的任務(wù)依賴圖.確定一個通用任務(wù)依賴圖的優(yōu)化映射是一個NP完全問題.對結(jié)構(gòu)化圖有好的啟發(fā)式方法存在.任務(wù)劃分:映射一個二叉樹依賴圖

示例快排的一種依賴圖以及如何被賦給超立方體中的進(jìn)程.

任務(wù)劃分:映射稀疏圖

計算稀疏矩陣乘向量的稀疏圖及其映射.層次性映射有時候單一映射技術(shù)不合適.例如，快排二叉樹的任務(wù)映射用不上大量的處理器.基于此原因，任務(wù)映射在頂層進(jìn)行，而數(shù)據(jù)劃分在每一層進(jìn)行.

例子，任務(wù)映射在頂層進(jìn)行，而數(shù)據(jù)劃分在下層進(jìn)行.7.5.2負(fù)載平衡算法靜態(tài)的：事先確定；概率的：隨機(jī)確定；動態(tài)的：執(zhí)行期間動態(tài)負(fù)載；基于域分解的：遞歸對剖局部算法概率方法循環(huán)映射usingonlyinformationobtainedfromasmallnumberofneighboringprocessors.

topartitionadomain(e.g.,afiniteelementgrid)intosubdomainsofapproximatelyequalcomputationalcostwhileattemptingtominimizecommunicationcosts,Ifweknowboththatcomputationalloadpergridpointvariesandthatthereissignificantspatiallocalityinloadlevels,

toallocatetasks

torandomlyselectedprocessors.非平衡遞歸對剖amappingonto64processors.thegridinquestionisanirregularfiniteelementmeshgeneratedforasupercondu-ctivitysimulation.

動態(tài)映射模式動態(tài)映射也稱為動態(tài)負(fù)載均衡，因為負(fù)載均衡是動態(tài)調(diào)度的主要動機(jī)動態(tài)映射模式可以是集中式的和分布式的。集中式動態(tài)映射進(jìn)程被設(shè)定為主和從當(dāng)一個進(jìn)程完成工作完便向主請求新工作當(dāng)進(jìn)程增加時，主可能成為瓶頸為了緩和此問題，進(jìn)程可以每一次拿多個任務(wù)，成為快組調(diào)度選取大的塊尺寸也可能導(dǎo)致顯著的負(fù)載不均衡有一些模式用于隨著計算進(jìn)行而逐漸減小塊尺寸分布式動態(tài)映射每個進(jìn)程可以發(fā)送任務(wù)給其它任務(wù)或從其它接收任務(wù)這樣減輕了集中式模式的瓶頸有四個關(guān)鍵問題：發(fā)送和接收的進(jìn)程如何配對；那個初始化傳輸；傳多少；合適啟動傳輸對于這些問題的回答特定于應(yīng)用最小化交互開銷最大化數(shù)據(jù)局部性：只要可能就服用中間數(shù)據(jù)，重建計算以使數(shù)據(jù)在較小的窗口內(nèi)得到重用最小化數(shù)據(jù)交換量：最小化交互的頻度：最小化競爭和熱點：最小化交互開銷（續(xù)）計算與通信重疊：使用非