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

并行算法的一般設(shè)計(jì)過程第1頁，共47頁，2023年，2月20日，星期四第二篇并行算法的設(shè)計(jì)

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

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

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

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

第2頁，共47頁，2023年，2月20日，星期四第七章并行算法的一般設(shè)計(jì)過程

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

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結(jié)

第3頁，共47頁，2023年，2月20日，星期四

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

PCAM設(shè)計(jì)過程2023/4/75第5頁，共47頁，2023年，2月20日，星期四第七章并行算法的一般設(shè)計(jì)過程

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

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結(jié)

第6頁，共47頁，2023年，2月20日，星期四7.2劃分

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

7.2.4劃分判據(jù)第7頁，共47頁，2023年，2月20日，星期四劃分方法描述充分開拓算法的并發(fā)性和可擴(kuò)放性；先進(jìn)行數(shù)據(jù)分解(稱域分解)，再進(jìn)行計(jì)算功能的分解(稱功能分解)；使數(shù)據(jù)集和計(jì)算集互不相交；劃分階段忽略處理器數(shù)目和目標(biāo)機(jī)器的體系結(jié)構(gòu)；能分為兩類劃分：域分解(domaindecomposition)功能分解(functionaldecomposition)2023/4/78第8頁，共47頁，2023年，2月20日，星期四7.2劃分

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

7.2.4劃分判據(jù)第9頁，共47頁，2023年，2月20日，星期四域分解劃分的對(duì)象是數(shù)據(jù)，可以是算法的輸入數(shù)據(jù)、中間處理數(shù)據(jù)和輸出數(shù)據(jù)；將數(shù)據(jù)分解成大致相等的小數(shù)據(jù)片；劃分時(shí)考慮數(shù)據(jù)上的相應(yīng)操作；如果一個(gè)任務(wù)需要?jiǎng)e的任務(wù)中的數(shù)據(jù)，則會(huì)產(chǎn)生任務(wù)間的通訊；2023/4/710第10頁，共47頁，2023年，2月20日，星期四域分解示例：三維網(wǎng)格的域分解，各格點(diǎn)上計(jì)算都是重復(fù)的。下圖是三種分解方法：2023/4/711第11頁，共47頁，2023年，2月20日，星期四域分解不規(guī)則區(qū)域的分解示例：2023/4/712第12頁，共47頁，2023年，2月20日，星期四7.2劃分

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

7.2.4劃分判據(jù)第13頁，共47頁，2023年，2月20日，星期四功能分解劃分的對(duì)象是計(jì)算，將計(jì)算劃分為不同的任務(wù)，其出發(fā)點(diǎn)不同于域分解；劃分后，研究不同任務(wù)所需的數(shù)據(jù)。如果這些數(shù)據(jù)不相交的，則劃分是成功的；如果數(shù)據(jù)有相當(dāng)?shù)闹丿B，意味著要重新進(jìn)行域分解和功能分解；功能分解是一種更深層次的分解。2023/4/714第14頁，共47頁，2023年，2月20日，星期四功能分解示例1：搜索樹示例2：氣候模型2023/4/715第15頁，共47頁，2023年，2月20日，星期四7.2劃分

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

7.2.4劃分判據(jù)第16頁，共47頁，2023年，2月20日，星期四劃分判據(jù)劃分是否具有靈活性？劃分是否避免了冗余計(jì)算和存儲(chǔ)？劃分任務(wù)尺寸是否大致相當(dāng)？任務(wù)數(shù)與問題尺寸是否成比例？功能分解是一種更深層次的分解，是否合理？2023/4/717第17頁，共47頁，2023年，2月20日，星期四第七章并行算法的一般設(shè)計(jì)過程

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

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結(jié)第18頁，共47頁，2023年，2月20日，星期四7.3通訊

7.3.1方法描述

7.3.2四種通訊模式

7.3.3通訊判據(jù)

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

7.3.1方法描述

7.3.2四種通訊模式

7.3.3通訊判據(jù)

第21頁，共47頁，2023年，2月20日，星期四四種通訊模式局部/全局通訊結(jié)構(gòu)化/非結(jié)構(gòu)化通訊靜態(tài)/動(dòng)態(tài)通訊同步/異步通訊2023/4/722第22頁，共47頁，2023年，2月20日，星期四局部通訊通訊限制在一個(gè)鄰域內(nèi)2023/4/723第23頁，共47頁，2023年，2月20日，星期四全局通訊通訊非局部的例如：AlltoAllMaster-Worker537212023/4/724第24頁，共47頁，2023年，2月20日，星期四結(jié)構(gòu)化通訊每個(gè)任務(wù)的通訊模式是相同的；下面是否存在一個(gè)相同通訊模式？2023/4/725第25頁，共47頁，2023年，2月20日，星期四非結(jié)構(gòu)化通訊沒有一個(gè)統(tǒng)一的通訊模式例如：無結(jié)構(gòu)化網(wǎng)格2023/4/726第26頁，共47頁，2023年，2月20日，星期四7.3通訊

7.3.1方法描述

7.3.2四種通訊模式

7.3.3通訊判據(jù)

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

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

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結(jié)第29頁，共47頁，2023年，2月20日，星期四7.4組合

7.4.1方法描述

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

7.4.3重復(fù)計(jì)算

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

7.4.1方法描述

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

7.4.3重復(fù)計(jì)算

7.4.4組合判據(jù)第32頁，共47頁，2023年，2月20日，星期四表面-容積效應(yīng)通訊量與任務(wù)子集的表面成正比，計(jì)算量與任務(wù)子集的體積成正比；增加重復(fù)計(jì)算有可能減少通訊量；2023/4/733第33頁，共47頁，2023年，2月20日，星期四7.4組合

7.4.1方法描述

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

7.4.3重復(fù)計(jì)算

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

二叉樹上求和，共需2logN步2023/4/736第36頁，共47頁，2023年，2月20日，星期四重復(fù)計(jì)算示例：二叉樹上N個(gè)處理器求N個(gè)數(shù)的全和，要求每個(gè)處理器均保持全和。

蝶式結(jié)構(gòu)求和，使用了重復(fù)計(jì)算，共需logN步2023/4/737第37頁，共47頁，2023年，2月20日，星期四7.4組合

7.4.1方法描述

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

7.4.3重復(fù)計(jì)算

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

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

7.2劃分

7.3通訊

7.4組合

7.5映射

7.6小結(jié)第40頁，共47頁，2023年，2月20日，星期四7.5映射

7.5.1方法描述

7.5.2負(fù)載平衡算法

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

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

7.5.1方法描述

7.5.2負(fù)載平衡算法

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

7.5.4映射判據(jù)第43頁，共47頁，2023年，2月20日，星期四負(fù)載平衡算法靜態(tài)的：事先確定；概率的：隨機(jī)確定；動(dòng)態(tài)的：執(zhí)行期間動(dòng)態(tài)負(fù)載；基于域分解的：遞歸對(duì)剖局部算法概率方法循環(huán)映射2023/4/744第44頁，共47頁，2023年，2月20日，星期四7.5映射

7.5.1方法描述

7.5.2負(fù)載平衡算法

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