PC7-PCAM并行程序設(shè)計方法學(xué)

并行計算

中國科學(xué)技術(shù)大學(xué)計算機(jī)科學(xué)與技術(shù)系國家高性能計算中心(合肥)2004年12月2023/2/41現(xiàn)代密碼學(xué)理論與實踐之五第二篇并行算法的設(shè)計

第四章并行算法的設(shè)計基礎(chǔ)

第五章并行算法的一般設(shè)計方法

第六章并行算法的基本設(shè)計技術(shù)

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

2023/2/42現(xiàn)代密碼學(xué)理論與實踐之五第七章并行算法的一般設(shè)計過程

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

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結(jié)

2023/2/43現(xiàn)代密碼學(xué)理論與實踐之五

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

PCAM設(shè)計過程2023/2/45現(xiàn)代密碼學(xué)理論與實踐之五第七章并行算法的一般設(shè)計過程

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

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結(jié)

2023/2/46現(xiàn)代密碼學(xué)理論與實踐之五7.2劃分

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

7.2.4劃分判據(jù)2023/2/47現(xiàn)代密碼學(xué)理論與實踐之五劃分方法描述充分開拓算法的并發(fā)性和可擴(kuò)放性；先進(jìn)行數(shù)據(jù)分解(稱域分解)，再進(jìn)行計算功能的分解(稱功能分解)；使數(shù)據(jù)集和計算集互不相交；劃分階段忽略處理器數(shù)目和目標(biāo)機(jī)器的體系結(jié)構(gòu)；能分為兩類劃分：域分解(domaindecomposition)功能分解(functionaldecomposition)2023/2/48現(xiàn)代密碼學(xué)理論與實踐之五7.2劃分

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

7.2.4劃分判據(jù)2023/2/49現(xiàn)代密碼學(xué)理論與實踐之五域分解劃分的對象是數(shù)據(jù)，可以是算法的輸入數(shù)據(jù)、中間處理數(shù)據(jù)和輸出數(shù)據(jù)；將數(shù)據(jù)分解成大致相等的小數(shù)據(jù)片；劃分時考慮數(shù)據(jù)上的相應(yīng)操作；如果一個任務(wù)需要別的任務(wù)中的數(shù)據(jù)，則會產(chǎn)生任務(wù)間的通訊；2023/2/410現(xiàn)代密碼學(xué)理論與實踐之五域分解示例：三維網(wǎng)格的域分解，各格點上計算都是重復(fù)的。下圖是三種分解方法：2023/2/411現(xiàn)代密碼學(xué)理論與實踐之五域分解不規(guī)則區(qū)域的分解示例：2023/2/412現(xiàn)代密碼學(xué)理論與實踐之五7.2劃分

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

7.2.4劃分判據(jù)2023/2/413現(xiàn)代密碼學(xué)理論與實踐之五功能分解劃分的對象是計算，將計算劃分為不同的任務(wù)，其出發(fā)點不同于域分解；劃分后，研究不同任務(wù)所需的數(shù)據(jù)。如果這些數(shù)據(jù)不相交的，則劃分是成功的；如果數(shù)據(jù)有相當(dāng)?shù)闹丿B，意味著要重新進(jìn)行域分解和功能分解；功能分解是一種更深層次的分解。2023/2/414現(xiàn)代密碼學(xué)理論與實踐之五功能分解示例1：搜索樹示例2：氣候模型2023/2/415現(xiàn)代密碼學(xué)理論與實踐之五7.2劃分

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

7.2.4劃分判據(jù)2023/2/416現(xiàn)代密碼學(xué)理論與實踐之五劃分判據(jù)劃分是否具有靈活性？劃分是否避免了冗余計算和存儲？劃分任務(wù)尺寸是否大致相當(dāng)？任務(wù)數(shù)與問題尺寸是否成比例？功能分解是一種更深層次的分解，是否合理？2023/2/417現(xiàn)代密碼學(xué)理論與實踐之五第七章并行算法的一般設(shè)計過程

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

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結(jié)

2023/2/418現(xiàn)代密碼學(xué)理論與實踐之五7.3通訊

7.3.1方法描述

7.3.2四種通訊模式

7.3.3通訊判據(jù)

2023/2/419現(xiàn)代密碼學(xué)理論與實踐之五通訊方法描述通訊是PCAM設(shè)計過程的重要階段；劃分產(chǎn)生的諸任務(wù)，一般不能完全獨立執(zhí)行，需要在任務(wù)間進(jìn)行數(shù)據(jù)交流；從而產(chǎn)生了通訊；功能分解確定了諸任務(wù)之間的數(shù)據(jù)流；諸任務(wù)是并發(fā)執(zhí)行的，通訊則限制了這種并發(fā)性；2023/2/420現(xiàn)代密碼學(xué)理論與實踐之五7.3通訊

7.3.1方法描述

7.3.2四種通訊模式

7.3.3通訊判據(jù)

2023/2/421現(xiàn)代密碼學(xué)理論與實踐之五四種通訊模式局部/全局通訊結(jié)構(gòu)化/非結(jié)構(gòu)化通訊靜態(tài)/動態(tài)通訊同步/異步通訊2023/2/422現(xiàn)代密碼學(xué)理論與實踐之五局部通訊通訊限制在一個鄰域內(nèi)2023/2/423現(xiàn)代密碼學(xué)理論與實踐之五全局通訊通訊非局部的例如：AlltoAllMaster-Worker537212023/2/424現(xiàn)代密碼學(xué)理論與實踐之五結(jié)構(gòu)化通訊每個任務(wù)的通訊模式是相同的；下面是否存在一個相同通訊模式？2023/2/425現(xiàn)代密碼學(xué)理論與實踐之五非結(jié)構(gòu)化通訊沒有一個統(tǒng)一的通訊模式例如：無結(jié)構(gòu)化網(wǎng)格2023/2/426現(xiàn)代密碼學(xué)理論與實踐之五7.3通訊

7.3.1方法描述

7.3.2四種通訊模式

7.3.3通訊判據(jù)

2023/2/427現(xiàn)代密碼學(xué)理論與實踐之五通訊判據(jù)所有任務(wù)是否執(zhí)行大致相當(dāng)?shù)耐ㄓ?是否盡可能的局部通訊？通訊操作是否能并行執(zhí)行?同步任務(wù)的計算能否并行執(zhí)行？2023/2/428現(xiàn)代密碼學(xué)理論與實踐之五第七章并行算法的一般設(shè)計過程

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

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結(jié)2023/2/429現(xiàn)代密碼學(xué)理論與實踐之五7.4組合

7.4.1方法描述

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

7.4.3重復(fù)計算

7.4.4組合判據(jù)2023/2/430現(xiàn)代密碼學(xué)理論與實踐之五方法描述組合是由抽象到具體的過程，是將組合的任務(wù)能在一類并行機(jī)上有效的執(zhí)行；合并小尺寸任務(wù)，減少任務(wù)數(shù)。如果任務(wù)數(shù)恰好等于處理器數(shù)，則也完成了映射過程；通過增加任務(wù)的粒度和重復(fù)計算，可以減少通訊成本；保持映射和擴(kuò)展的靈活性，降低軟件工程成本；2023/2/431現(xiàn)代密碼學(xué)理論與實踐之五7.4組合

7.4.1方法描述

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

7.4.3重復(fù)計算

7.4.4組合判據(jù)2023/2/432現(xiàn)代密碼學(xué)理論與實踐之五表面-容積效應(yīng)通訊量與任務(wù)子集的表面成正比，計算量與任務(wù)子集的體積成正比；增加重復(fù)計算有可能減少通訊量；2023/2/433現(xiàn)代密碼學(xué)理論與實踐之五7.4組合

7.4.1方法描述

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

7.4.3重復(fù)計算

7.4.4組合判據(jù)2023/2/434現(xiàn)代密碼學(xué)理論與實踐之五重復(fù)計算重復(fù)計算減少通訊量，但增加了計算量，應(yīng)保持恰當(dāng)?shù)钠胶?；重?fù)計算的目標(biāo)應(yīng)減少算法的總運算時間；2023/2/435現(xiàn)代密碼學(xué)理論與實踐之五重復(fù)計算示例：二叉樹上N個處理器求N個數(shù)的全和，要求每個處理器均保持全和。

二叉樹上求和，共需2logN步2023/2/436現(xiàn)代密碼學(xué)理論與實踐之五重復(fù)計算示例：二叉樹上N個處理器求N個數(shù)的全和，要求每個處理器均保持全和。

蝶式結(jié)構(gòu)求和，使用了重復(fù)計算，共需logN步2023/2/437現(xiàn)代密碼學(xué)理論與實踐之五7.4組合

7.4.1方法描述

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

7.4.3重復(fù)計算

7.4.4組合判據(jù)2023/2/438現(xiàn)代密碼學(xué)理論與實踐之五組合判據(jù)增加粒度是否減少了通訊成本？重復(fù)計算是否已權(quán)衡了其得益？是否保持了靈活性和可擴(kuò)放性？組合的任務(wù)數(shù)是否與問題尺寸成比例?是否保持了類似的計算和通訊？有沒有減少并行執(zhí)行的機(jī)會？2023/2/439現(xiàn)代密碼學(xué)理論與實踐之五第七章并行算法的一般設(shè)計過程

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

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結(jié)2023/2/440現(xiàn)代密碼學(xué)理論與實踐之五7.5映射

7.5.1方法描述

7.5.2負(fù)載平衡算法

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

7.5.4映射判據(jù)2023/2/441現(xiàn)代密碼學(xué)理論與實踐之五方法描述每個任務(wù)要映射到具體的處理器，定位到運行機(jī)器上；任務(wù)數(shù)大于處理器數(shù)時，存在負(fù)載平衡和任務(wù)調(diào)度問題；映射的目標(biāo)：減少算法的執(zhí)行時間并發(fā)的任務(wù)不同的處理器任務(wù)之間存在高通訊的同一處理器映射實際是一種權(quán)衡，屬于NP完全問題；2023/2/442現(xiàn)代密碼學(xué)理論與實踐之五7.5映射

7.5.1方法描述

7.5.2負(fù)載平衡算法

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

7.5.4映射判據(jù)2023/2/443現(xiàn)代密碼學(xué)理論與實踐之五負(fù)載平衡算法靜態(tài)的：事先確定；概率的：隨機(jī)確定；動態(tài)的：執(zhí)行期間動態(tài)負(fù)載；基于域分解的：遞歸對剖局部算法概率方法循環(huán)映射2023/2/444現(xiàn)代密碼學(xué)理論與實踐之五7.5映射

7.5.1方法描述

7.5.2負(fù)載平衡算法

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

7.5.4映射判據(jù)2023/2/445現(xiàn)代密碼學(xué)理論與實踐之五任務(wù)調(diào)度算法任務(wù)放在集中的或分散的任務(wù)池中，使用任務(wù)調(diào)度算法將池中的任務(wù)分配給特定的處理器。下面是兩種常用調(diào)度模式：經(jīng)理/雇員模式非集中模式2023/2/446現(xiàn)代密碼學(xué)理論與實踐之五7.5映射

7.5.1方法描述

7.5.2負(fù)載平衡算法

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

7.5.4映射判據(jù)2023/2/447現(xiàn)代密碼學(xué)理論與實踐之五映射判據(jù)采用集中式負(fù)載平衡方案，是否存在通訊瓶頸？采用動態(tài)負(fù)載平衡方案，調(diào)