PC7-PCAM并行程序設計方法學

并行計算

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

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

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

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

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

2023/2/42現代密碼學理論與實踐之五第七章并行算法的一般設計過程

7.1PCAM設計方法學

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結

2023/2/43現代密碼學理論與實踐之五

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

PCAM設計過程2023/2/45現代密碼學理論與實踐之五第七章并行算法的一般設計過程

7.1PCAM設計方法學

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結

2023/2/46現代密碼學理論與實踐之五7.2劃分

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

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

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

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

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

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

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

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

7.1PCAM設計方法學

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結

2023/2/418現代密碼學理論與實踐之五7.3通訊

7.3.1方法描述

7.3.2四種通訊模式

7.3.3通訊判據

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

7.3.1方法描述

7.3.2四種通訊模式

7.3.3通訊判據

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

7.3.1方法描述

7.3.2四種通訊模式

7.3.3通訊判據

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

7.1PCAM設計方法學

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結2023/2/429現代密碼學理論與實踐之五7.4組合

7.4.1方法描述

7.4.2表面-容積效應

7.4.3重復計算

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

7.4.1方法描述

7.4.2表面-容積效應

7.4.3重復計算

7.4.4組合判據2023/2/432現代密碼學理論與實踐之五表面-容積效應通訊量與任務子集的表面成正比，計算量與任務子集的體積成正比；增加重復計算有可能減少通訊量；2023/2/433現代密碼學理論與實踐之五7.4組合

7.4.1方法描述

7.4.2表面-容積效應

7.4.3重復計算

7.4.4組合判據2023/2/434現代密碼學理論與實踐之五重復計算重復計算減少通訊量，但增加了計算量，應保持恰當的平衡；重復計算的目標應減少算法的總運算時間；2023/2/435現代密碼學理論與實踐之五重復計算示例：二叉樹上N個處理器求N個數的全和，要求每個處理器均保持全和。

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

蝶式結構求和，使用了重復計算，共需logN步2023/2/437現代密碼學理論與實踐之五7.4組合

7.4.1方法描述

7.4.2表面-容積效應

7.4.3重復計算

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

7.1PCAM設計方法學

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結2023/2/440現代密碼學理論與實踐之五7.5映射

7.5.1方法描述

7.5.2負載平衡算法

7.5.3任務調度算法

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

7.5.1方法描述

7.5.2負載平衡算法

7.5.3任務調度算法

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

7.5.1方法描述

7.5.2負載平衡算法

7.5.3任務調度算法

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

7.5.1方法描述

7.5.2負載平衡算法

7.5.3任務調度算法

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