并行算法的一般設計過程

并行算法的一般設計過程第一頁，共四十七頁，2022年，8月28日第二篇并行算法的設計

第四章并行算法的設計基礎

第五章并行算法的一般設計方法

第六章并行算法的基本設計技術

第七章并行算法的一般設計過程

第二頁，共四十七頁，2022年，8月28日第七章并行算法的一般設計過程

7.1PCAM設計方法學

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結

第三頁，共四十七頁，2022年，8月28日

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

PCAM設計過程2023/2/55第五頁，共四十七頁，2022年，8月28日第七章并行算法的一般設計過程

7.1PCAM設計方法學

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結

第六頁，共四十七頁，2022年，8月28日7.2劃分

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

7.2.4劃分判據(jù)第七頁，共四十七頁，2022年，8月28日劃分方法描述充分開拓算法的并發(fā)性和可擴放性；先進行數(shù)據(jù)分解(稱域分解)，再進行計算功能的分解(稱功能分解)；使數(shù)據(jù)集和計算集互不相交；劃分階段忽略處理器數(shù)目和目標機器的體系結構；能分為兩類劃分：域分解(domaindecomposition)功能分解(functionaldecomposition)2023/2/58第八頁，共四十七頁，2022年，8月28日7.2劃分

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

7.2.4劃分判據(jù)第九頁，共四十七頁，2022年，8月28日域分解劃分的對象是數(shù)據(jù)，可以是算法的輸入數(shù)據(jù)、中間處理數(shù)據(jù)和輸出數(shù)據(jù)；將數(shù)據(jù)分解成大致相等的小數(shù)據(jù)片；劃分時考慮數(shù)據(jù)上的相應操作；如果一個任務需要別的任務中的數(shù)據(jù)，則會產(chǎn)生任務間的通訊；2023/2/510第十頁，共四十七頁，2022年，8月28日域分解示例：三維網(wǎng)格的域分解，各格點上計算都是重復的。下圖是三種分解方法：2023/2/511第十一頁，共四十七頁，2022年，8月28日域分解不規(guī)則區(qū)域的分解示例：2023/2/512第十二頁，共四十七頁，2022年，8月28日7.2劃分

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

7.2.4劃分判據(jù)第十三頁，共四十七頁，2022年，8月28日功能分解劃分的對象是計算，將計算劃分為不同的任務，其出發(fā)點不同于域分解；劃分后，研究不同任務所需的數(shù)據(jù)。如果這些數(shù)據(jù)不相交的，則劃分是成功的；如果數(shù)據(jù)有相當?shù)闹丿B，意味著要重新進行域分解和功能分解；功能分解是一種更深層次的分解。2023/2/514第十四頁，共四十七頁，2022年，8月28日功能分解示例1：搜索樹示例2：氣候模型2023/2/515第十五頁，共四十七頁，2022年，8月28日7.2劃分

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

7.2.4劃分判據(jù)第十六頁，共四十七頁，2022年，8月28日劃分判據(jù)劃分是否具有靈活性？劃分是否避免了冗余計算和存儲？劃分任務尺寸是否大致相當？任務數(shù)與問題尺寸是否成比例？功能分解是一種更深層次的分解，是否合理？2023/2/517第十七頁，共四十七頁，2022年，8月28日第七章并行算法的一般設計過程

7.1PCAM設計方法學

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結第十八頁，共四十七頁，2022年，8月28日7.3通訊

7.3.1方法描述

7.3.2四種通訊模式

7.3.3通訊判據(jù)

第十九頁，共四十七頁，2022年，8月28日通訊方法描述通訊是PCAM設計過程的重要階段；劃分產(chǎn)生的諸任務，一般不能完全獨立執(zhí)行，需要在任務間進行數(shù)據(jù)交流；從而產(chǎn)生了通訊；功能分解確定了諸任務之間的數(shù)據(jù)流；諸任務是并發(fā)執(zhí)行的，通訊則限制了這種并發(fā)性；2023/2/520第二十頁，共四十七頁，2022年，8月28日7.3通訊

7.3.1方法描述

7.3.2四種通訊模式

7.3.3通訊判據(jù)

第二十一頁，共四十七頁，2022年，8月28日四種通訊模式局部/全局通訊結構化/非結構化通訊靜態(tài)/動態(tài)通訊同步/異步通訊2023/2/522第二十二頁，共四十七頁，2022年，8月28日局部通訊通訊限制在一個鄰域內(nèi)2023/2/523第二十三頁，共四十七頁，2022年，8月28日全局通訊通訊非局部的例如：AlltoAllMaster-Worker537212023/2/524第二十四頁，共四十七頁，2022年，8月28日結構化通訊每個任務的通訊模式是相同的；下面是否存在一個相同通訊模式？2023/2/525第二十五頁，共四十七頁，2022年，8月28日非結構化通訊沒有一個統(tǒng)一的通訊模式例如：無結構化網(wǎng)格2023/2/526第二十六頁，共四十七頁，2022年，8月28日7.3通訊

7.3.1方法描述

7.3.2四種通訊模式

7.3.3通訊判據(jù)

第二十七頁，共四十七頁，2022年，8月28日通訊判據(jù)所有任務是否執(zhí)行大致相當?shù)耐ㄓ?是否盡可能的局部通訊？通訊操作是否能并行執(zhí)行?同步任務的計算能否并行執(zhí)行？2023/2/528第二十八頁，共四十七頁，2022年，8月28日第七章并行算法的一般設計過程

7.1PCAM設計方法學

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結第二十九頁，共四十七頁，2022年，8月28日7.4組合

7.4.1方法描述

7.4.2表面-容積效應

7.4.3重復計算

7.4.4組合判據(jù)第三十頁，共四十七頁，2022年，8月28日方法描述組合是由抽象到具體的過程，是將組合的任務能在一類并行機上有效的執(zhí)行；合并小尺寸任務，減少任務數(shù)。如果任務數(shù)恰好等于處理器數(shù)，則也完成了映射過程；通過增加任務的粒度和重復計算，可以減少通訊成本；保持映射和擴展的靈活性，降低軟件工程成本；2023/2/531第三十一頁，共四十七頁，2022年，8月28日7.4組合

7.4.1方法描述

7.4.2表面-容積效應

7.4.3重復計算

7.4.4組合判據(jù)第三十二頁，共四十七頁，2022年，8月28日表面-容積效應通訊量與任務子集的表面成正比，計算量與任務子集的體積成正比；增加重復計算有可能減少通訊量；2023/2/533第三十三頁，共四十七頁，2022年，8月28日7.4組合

7.4.1方法描述

7.4.2表面-容積效應

7.4.3重復計算

7.4.4組合判據(jù)第三十四頁，共四十七頁，2022年，8月28日重復計算重復計算減少通訊量，但增加了計算量，應保持恰當?shù)钠胶?；重復計算的目標應減少算法的總運算時間；2023/2/535第三十五頁，共四十七頁，2022年，8月28日重復計算示例：二叉樹上N個處理器求N個數(shù)的全和，要求每個處理器均保持全和。

二叉樹上求和，共需2logN步2023/2/536第三十六頁，共四十七頁，2022年，8月28日重復計算示例：二叉樹上N個處理器求N個數(shù)的全和，要求每個處理器均保持全和。

蝶式結構求和，使用了重復計算，共需logN步2023/2/537第三十七頁，共四十七頁，2022年，8月28日7.4組合

7.4.1方法描述

7.4.2表面-容積效應

7.4.3重復計算

7.4.4組合判據(jù)第三十八頁，共四十七頁，2022年，8月28日組合判據(jù)增加粒度是否減少了通訊成本？重復計算是否已權衡了其得益？是否保持了靈活性和可擴放性？組合的任務數(shù)是否與問題尺寸成比例?是否保持了類似的計算和通訊？有沒有減少并行執(zhí)行的機會？2023/2/539第三十九頁，共四十七頁，2022年，8月28日第七章并行算法的一般設計過程

7.1PCAM設計方法學

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結第四十頁，共四十七頁，2022年，8月28日7.5映射

7.5.1方法描述

7.5.2負載平衡算法

7.5.3任務調(diào)度算法

7.5.4映射判據(jù)第四十一頁，共四十七頁，2022年，8月28日方法描述每個任務要映射到具體的處理器，定位到運行機器上；任務數(shù)大于處理器數(shù)時，存在負載平衡和任務調(diào)度問題；映射的目標：減少算法的執(zhí)行時間并發(fā)的任務不同的處理器任務之間存在高通訊的同一處理器映射實際是一種權衡，屬于NP完全問題；2023/2/542第四十二頁，共四十七頁，2022年，8月28日7.5映射

7.5.1方法描述

7.5.2負載平衡算法

7.5.3任務調(diào)度算法

7.5.4映射判據(jù)第四十三頁，共四十七頁，2022年，8月28日負載平衡算法靜態(tài)的：事先確定；概率的：隨機確定；動態(tài)的：執(zhí)行期間動態(tài)負載；基于域分解的：遞歸對剖局部算法概率方法循環(huán)映射2023/2/544第四十四頁，共四十七頁，2022年，8月28日7.5映射

7.5.1方法描述

7.5.2負載平衡算法

7.5.3任務調(diào)度算法