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

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

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

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

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

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

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

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

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結(jié)

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

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

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

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

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結(jié)

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

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

7.2.4劃分判據(jù)第七頁，共四十七頁，2022年，8月28日劃分方法描述充分開拓算法的并發(fā)性和可擴(kuò)放性；先進(jìn)行數(shù)據(jù)分解(稱域分解)，再進(jìn)行計算功能的分解(稱功能分解)；使數(shù)據(jù)集和計算集互不相交；劃分階段忽略處理器數(shù)目和目標(biāo)機(jī)器的體系結(jié)構(gòu)；能分為兩類劃分：域分解(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ù)上的相應(yīng)操作；如果一個任務(wù)需要別的任務(wù)中的數(shù)據(jù)，則會產(chǎn)生任務(wù)間的通訊；2023/2/510第十頁，共四十七頁，2022年，8月28日域分解示例：三維網(wǎng)格的域分解，各格點(diǎn)上計算都是重復(fù)的。下圖是三種分解方法：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日功能分解劃分的對象是計算，將計算劃分為不同的任務(wù)，其出發(fā)點(diǎn)不同于域分解；劃分后，研究不同任務(wù)所需的數(shù)據(jù)。如果這些數(shù)據(jù)不相交的，則劃分是成功的；如果數(shù)據(jù)有相當(dāng)?shù)闹丿B，意味著要重新進(jìn)行域分解和功能分解；功能分解是一種更深層次的分解。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ù)劃分是否具有靈活性？劃分是否避免了冗余計算和存儲？劃分任務(wù)尺寸是否大致相當(dāng)？任務(wù)數(shù)與問題尺寸是否成比例？功能分解是一種更深層次的分解，是否合理？2023/2/517第十七頁，共四十七頁，2022年，8月28日第七章并行算法的一般設(shè)計過程

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

7.2劃分

7.3通訊

7.4組合

7.5映射

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

7.3.1方法描述

7.3.2四種通訊模式

7.3.3通訊判據(jù)

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

7.3.1方法描述

7.3.2四種通訊模式

7.3.3通訊判據(jù)

第二十一頁，共四十七頁，2022年，8月28日四種通訊模式局部/全局通訊結(jié)構(gòu)化/非結(jié)構(gòu)化通訊靜態(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日結(jié)構(gòu)化通訊每個任務(wù)的通訊模式是相同的；下面是否存在一個相同通訊模式？2023/2/525第二十五頁，共四十七頁，2022年，8月28日非結(jié)構(gòu)化通訊沒有一個統(tǒng)一的通訊模式例如：無結(jié)構(gòu)化網(wǎng)格2023/2/526第二十六頁，共四十七頁，2022年，8月28日7.3通訊

7.3.1方法描述

7.3.2四種通訊模式

7.3.3通訊判據(jù)

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

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

7.2劃分

7.3通訊

7.4組合

7.5映射

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

7.4.1方法描述

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

7.4.3重復(fù)計算

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

7.4.1方法描述

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

7.4.3重復(fù)計算

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

7.4.1方法描述

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

7.4.3重復(fù)計算

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

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

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

7.4.1方法描述

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

7.4.3重復(fù)計算

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

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

7.2劃分

7.3通訊

7.4組合

7.5映射

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

7.5.1方法描述

7.5.2負(fù)載平衡算法

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

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

7.5.1方法描述

7.5.2負(fù)載平衡算法

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

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

7.5.1方法描述

7.5.2負(fù)載平衡算法

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