版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、并行算法實踐上篇 并行程序設(shè)計導(dǎo)論國家高性能計算中心(合肥)22022/9/5并行算法實踐上篇 并行程序設(shè)計導(dǎo)論單元I 并行程序設(shè)計基礎(chǔ)單元II 并行程序編程指南單元III 并行程序開發(fā)方法國家高性能計算中心(合肥)32022/9/5單元I 并行程序設(shè)計基礎(chǔ)第一章 并行計算機系統(tǒng)與結(jié)構(gòu)模型第二章 PC機群的搭建第三章 并行程序設(shè)計簡介國家高性能計算中心(合肥)42022/9/5第三章 并行程序設(shè)計簡介3.1 并行程序開發(fā)方法3.1.1 并行層次與代碼粒度3.1.2 并行程序開發(fā)策略3.1.3 并行編程模式3.1.4 并行應(yīng)用編程過程3.2 并行程序設(shè)計模型3.2.1 計算樣本程序3.2.2 數(shù)
2、據(jù)并行模型3.2.3 消息傳遞模型3.2.4 共享變量模型3.3 并行編程語言和環(huán)境概述3.3.1 早期并行編程語言3.3.2 近代并行編程語言與環(huán)境3.3.3 并行說明性語言環(huán)境3.4 循環(huán)程序并行化的一般方法3.4.1 數(shù)據(jù)相關(guān)分析3.4.2 .數(shù)據(jù)劃分與處理器指派3.4.3 循環(huán)重構(gòu)國家高性能計算中心(合肥)52022/9/5并行層次與代碼粒度國家高性能計算中心(合肥)62022/9/5并行層次粒度(指令數(shù))并行實施編程支持甚細粒度指令級并行幾十條,如多指令發(fā)射、內(nèi)存交叉存取硬件處理器細粒度數(shù)據(jù)級并行幾百條,如循環(huán)指令塊編譯器共享變量中粒度控制級并行幾千條,如過程、函數(shù)程序員(編譯器)共
3、享變量、消息傳遞粗粒度任務(wù)級并行數(shù)萬條,如獨立的作業(yè)任務(wù)操作系統(tǒng)消息傳遞國家高性能計算中心(合肥)72022/9/5并行程序開發(fā)策略國家高性能計算中心(合肥)82022/9/5并行編程模式主-從式(Master-Slave)單程序多數(shù)據(jù)流(Single Program Multiple Data )數(shù)據(jù)流水線(Data Pipelining)分治策略(Divide and Conquer)國家高性能計算中心(合肥)92022/9/5主-從式(Master-Slave)其基本思想是將一個待求解的任務(wù)分成一個主任務(wù)(主進程)和一些從任務(wù)(子進程)。主進程負責(zé)將任務(wù)的分解、派發(fā)和收集諸子任務(wù)的求解結(jié)
4、果并最后匯總得到問題的最終解。諸子進程接收主進程發(fā)來的消息;并行進行各自計算;向主進程發(fā)回各自的計算結(jié)果。 國家高性能計算中心(合肥)102022/9/5單程序多數(shù)據(jù)流(SPMD)亦稱為單控制流多數(shù)據(jù)流模式,其基本思想是并行運行的進程均執(zhí)行相同的代碼段,但卻操作在各自不同的數(shù)據(jù)上。這種編程模式首先需要將應(yīng)用程序的數(shù)據(jù)預(yù)先分配給各個計算進程(處理器);然后諸計算進程并行的完成各自的計算任務(wù),包括計算過程中各進程間的數(shù)據(jù)交換(施行通信同步);最后才將各計算結(jié)果匯集起來。 國家高性能計算中心(合肥)112022/9/5數(shù)據(jù)流水線(Data Pipelining)其基本思想是將各計算進程組織成一條流水
5、線,每個進程執(zhí)行一個特定的計算任務(wù),相應(yīng)于流水線的一個階段。一個計算任務(wù)在功能上劃分成一些子任務(wù)(進程),這些子任務(wù)完成某種特定功能的計算工作,而且一旦前一個子任務(wù)完成,后繼的子任務(wù)就可立即開始。在整個計算過程中各進程之間的通信模式非常簡單,僅發(fā)生在相鄰的階段之間,且通信可以完全異步地進行。 國家高性能計算中心(合肥)122022/9/5國家高性能計算中心(合肥)132022/9/5分治策略(Divide and Conquer)其基本思想是將一個大而復(fù)雜的問題分解成若干個特性相同的子問題分而治之。若所得的子問題規(guī)模仍嫌過大,則可反復(fù)使用分治策略,直至很容易求解諸子問題為止。問題求解可分為三步
6、:將輸入分解成若干個規(guī)模近于相等的子問題;同時遞歸地求解諸子問題;歸并各子問題的解成為原問題的解。國家高性能計算中心(合肥)142022/9/5并行應(yīng)用編程過程PCAM設(shè)計并行應(yīng)用的四個階段劃分(Partitioning)通信(Communication)組合(Agglomeration)映射(Mapping)劃分:分解成小的任務(wù),開拓并發(fā)性;通信:確定諸任務(wù)間的數(shù)據(jù)交換,監(jiān)測劃分的合理性;組合:依據(jù)任務(wù)的局部性,組合成更大的任務(wù);映射:將每個任務(wù)分配到處理器上,提高并行性能。國家高性能計算中心(合肥)152022/9/5 PCAM設(shè)計過程國家高性能計算中心(合肥)162022/9/5 劃分方
7、法描述充分開拓算法的并發(fā)性和可擴放性;先進行數(shù)據(jù)分解(稱域分解),再進行計算功能的分解(稱功能分解);使數(shù)據(jù)集和計算集互不相交;劃分階段忽略處理器數(shù)目和目標(biāo)機器的體系結(jié)構(gòu);能分為兩類劃分:域分解(Domain Decomposition)功能分解(Functional Decomposition)國家高性能計算中心(合肥)172022/9/5域分解 劃分的對象是數(shù)據(jù),可以是程序中的輸入數(shù)據(jù)、中間處理數(shù)據(jù)和輸出數(shù)據(jù);將數(shù)據(jù)分解成大致相等的小數(shù)據(jù)片;劃分時考慮數(shù)據(jù)上的相應(yīng)操作;如果一個任務(wù)需要別的任務(wù)中的數(shù)據(jù),則會產(chǎn)生任務(wù)間的通信;國家高性能計算中心(合肥)182022/9/5域分解 示例:三維網(wǎng)
8、格的域分解,各格點上計算都是重復(fù)的。下圖是三種分解方法:國家高性能計算中心(合肥)192022/9/5域分解 不規(guī)則區(qū)域的分解示例:國家高性能計算中心(合肥)202022/9/5功能分解 劃分的對象是計算(亦稱為任務(wù)分解或計算劃分),將計算劃分為不同的任務(wù),其出發(fā)點不同于域分解;劃分后,研究不同任務(wù)所需的數(shù)據(jù)。如果這些數(shù)據(jù)不相交的,則劃分是成功的;如果數(shù)據(jù)有相當(dāng)?shù)闹丿B, 意味著存在大量的通信開銷,要重新進行域分解和功能分解;功能分解是一種更深層次的分解。國家高性能計算中心(合肥)212022/9/5功能分解 示例1:搜索樹示例2:氣候模型國家高性能計算中心(合肥)222022/9/5劃分判據(jù)
9、劃分是否具有靈活性?劃分是否避免了冗余計算和存儲?劃分任務(wù)尺寸是否大致相當(dāng)?任務(wù)數(shù)與問題尺寸是否成比例?功能分解是一種更深層次的分解,是否合理?國家高性能計算中心(合肥)232022/9/5 通信分析通信是PCAM設(shè)計過程的重要階段;劃分產(chǎn)生的諸任務(wù),一般不能完全獨立執(zhí)行,需要在任務(wù)間進行數(shù)據(jù)交流;從而產(chǎn)生了通信;功能分解確定了諸任務(wù)之間的數(shù)據(jù)流;諸任務(wù)是并發(fā)執(zhí)行的,通信則限制了這種并發(fā)性;國家高性能計算中心(合肥)242022/9/5 四種通信模式局部/全局通信結(jié)構(gòu)化/非結(jié)構(gòu)化通信靜態(tài)/動態(tài)通信同步/異步通信國家高性能計算中心(合肥)252022/9/5局部通信通信限制在一個鄰域內(nèi)國家高性能
10、計算中心(合肥)262022/9/5全局通信通信非局部的例如:All to AllMaster-Worker53721國家高性能計算中心(合肥)272022/9/5結(jié)構(gòu)化通信每個任務(wù)的通信模式是相同的;下面是否存在一個相同通信模式?國家高性能計算中心(合肥)282022/9/5非結(jié)構(gòu)化通信沒有一個統(tǒng)一的通信模式例如:無結(jié)構(gòu)化網(wǎng)格國家高性能計算中心(合肥)292022/9/5靜態(tài)/動態(tài)通信通信伙伴的身份不隨時間改變;動態(tài)通信中,通信伙伴的身份則可能由運行時所計算的數(shù)據(jù)決定且是可變的。 國家高性能計算中心(合肥)302022/9/5同步/異步通信同步通信時,接收方和發(fā)送方協(xié)同操作;異步通信中,接收
11、方獲取數(shù)據(jù)無需與發(fā)送方協(xié)同。國家高性能計算中心(合肥)312022/9/5通信判據(jù) 所有任務(wù)是否執(zhí)行大致相當(dāng)?shù)耐ㄐ?是否盡可能的局部通信?通信操作是否能并行執(zhí)行?同步任務(wù)的計算能否并行執(zhí)行?國家高性能計算中心(合肥)322022/9/5任務(wù)組合 組合是由抽象到具體的過程,是將組合的任務(wù)能在一類并行機上有效的執(zhí)行;合并小尺寸任務(wù),減少任務(wù)數(shù)。如果任務(wù)數(shù)恰好等于處理器數(shù),則也完成了映射過程;通過增加任務(wù)的粒度和重復(fù)計算,可以減少通信成本;保持映射和擴展的靈活性,降低軟件工程成本;國家高性能計算中心(合肥)332022/9/5表面-容積效應(yīng)通信量與任務(wù)子集的表面成正比,計算量與任務(wù)子集的體積成正比;
12、增加重復(fù)計算有可能減少通信量;國家高性能計算中心(合肥)342022/9/5重復(fù)計算重復(fù)計算減少通信量,但增加了計算量,應(yīng)保持恰當(dāng)?shù)钠胶?;重?fù)計算的目標(biāo)應(yīng)減少算法的總運算時間;國家高性能計算中心(合肥)352022/9/5重復(fù)計算示例:二叉樹上N個處理器求N個數(shù)的全和,要求每個處理器均保持全和。 二叉樹上求和,共需2logN步國家高性能計算中心(合肥)362022/9/5重復(fù)計算示例:二叉樹上N個處理器求N個數(shù)的全和,要求每個處理器均保持全和。 蝶式結(jié)構(gòu)求和,使用了重復(fù)計算,共需logN步國家高性能計算中心(合肥)372022/9/5組合判據(jù) 增加粒度是否減少了通信成本?重復(fù)計算是否已權(quán)衡了其
13、得益?是否保持了靈活性和可擴放性?組合的任務(wù)數(shù)是否與問題尺寸成比例?是否保持了類似的計算和通信?有沒有減少并行執(zhí)行的機會?國家高性能計算中心(合肥)382022/9/5處理器映射 每個任務(wù)要映射到具體的處理器,定位到運行機器上;任務(wù)數(shù)大于處理器數(shù)時,存在負載平衡和任務(wù)調(diào)度問題;映射的目標(biāo):減少算法的執(zhí)行時間并發(fā)的任務(wù) 不同的處理器任務(wù)之間存在高通信的 同一處理器映射實際是一種權(quán)衡,屬于NP完全問題;國家高性能計算中心(合肥)392022/9/5負載平衡 靜態(tài)的:事先確定;概率的:隨機確定;動態(tài)的:執(zhí)行期間動態(tài)負載;基于域分解的:遞歸對剖局部算法概率方法循環(huán)映射國家高性能計算中心(合肥)4020
14、22/9/5任務(wù)分配與調(diào)度負載平衡與任務(wù)分配/調(diào)度密切相關(guān),任務(wù)分配通常有靜態(tài)的和動態(tài)的兩種方法。靜態(tài)分配一般是任務(wù)到進程的算術(shù)映射。靜態(tài)分配的優(yōu)點是沒有運行時任務(wù)管理的開銷,但為了實現(xiàn)負載平衡,要求不同任務(wù)的工作量和處理器的性能是可以預(yù)測的并且擁有足夠的可供分配的任務(wù)。靜態(tài)調(diào)度(Static Scheduling)方案一般是靜態(tài)地為每個處理器分配個連續(xù)的循環(huán)迭代,其中為迭代次數(shù),是處理器數(shù)。也可以采用輪轉(zhuǎn)(Round-robin)的方式來給處理器分配任務(wù),即將第i個循環(huán)迭代分配給第i mod p個處理器。國家高性能計算中心(合肥)412022/9/5任務(wù)分配與調(diào)度動態(tài)分配與調(diào)度相對靈活,可以
15、運行時在不同處理器間動態(tài)地進行負載的調(diào)整。各種動態(tài)調(diào)度(Dynamic Scheduling)技術(shù)是并行計算研究的熱點,包括基本自調(diào)度SS(Self Scheduling)、塊自調(diào)度BSS(Block Self Scheduling)、 指導(dǎo)自調(diào)度GSS(Guided Self Scheduling)、因子分解調(diào)度FS(Factoring Scheduling)、梯形自調(diào)度TSS(Trapezoid Self Scheduling)、 耦合調(diào)度AS(Affinity Scheduling)、安全自調(diào)度SSS(Safe Self Scheduling)和自適應(yīng)耦合調(diào)度AAS(Adapt Affi
16、nity Scheduling)。國家高性能計算中心(合肥)422022/9/5經(jīng)理/雇員模式任務(wù)調(diào)度 任務(wù)放在集中的或分散的任務(wù)池中,使用任務(wù)調(diào)度算法將池中的任務(wù)分配給特定的處理器。國家高性能計算中心(合肥)432022/9/5映射判據(jù) 采用集中式負載平衡方案,是否存在通信瓶頸?采用動態(tài)負載平衡方案,調(diào)度策略的成本如何?國家高性能計算中心(合肥)442022/9/5并行程序設(shè)計模型數(shù)據(jù)并行模型(Data Parallel)消息傳遞模型(Message Passing)共享變量模型(Shared Variable)國家高性能計算中心(合肥)452022/9/5的計算國家高性能計算中心(合肥)4
17、62022/9/5計算的串行C代碼#define N 1000000main() double local, pi = 0.0, w;long i;w=1.0/N;for (i = 0; iN; i +) local = (i + 0.5)*w;pi = pi + 4.0/(1.0+local * local);printf(“pi is %f n”, pi *w);國家高性能計算中心(合肥)472022/9/5數(shù)據(jù)并行(Data Parallel)概況:SIMD的自然模型,也可運行于SPMD、MIMD機器上局部計算和數(shù)據(jù)選路操作適合于使用規(guī)則網(wǎng)絡(luò),模板和多維信號及圖像數(shù)據(jù)集來求解細粒度的應(yīng)用
18、問題數(shù)據(jù)并行操作的同步是在編譯時而不是在運行時完成的 特點:單線程并行操作于聚合數(shù)據(jù)結(jié)構(gòu)(數(shù)組)松散同步全局命名空間隱式相互作用隱式/半隱式數(shù)據(jù)分布國家高性能計算中心(合肥)482022/9/5計算的數(shù)據(jù)并行代碼main( ) long i,j,t,N=100000; double local N,temp N,pi,w; A: w=1.0/N; B: forall (i=0;iN ; i+) P: locali=(i+0.5)*w; Q: tempi=4.0/(1.0+locali*locali); C: pi = sum (temp); D: printf (“pi is %f n”,pi
19、 * w ); / *main( ) * /國家高性能計算中心(合肥)492022/9/5消息傳遞(Message Passing)概況:MPP, COW的自然模型,也可應(yīng)用于共享變量多機系統(tǒng),適合開發(fā)大粒度的并行性廣泛使用的標(biāo)準消息傳遞庫MPI和PVM特點:多線程異步并行性分開的地址空間顯式相互作用顯式數(shù)據(jù)映射和負載分配常采用SPMD形式編碼國家高性能計算中心(合肥)502022/9/5計算的MPI代碼 # define N 100000 main ( ) double local=0.0,pi,w,temp=0.0; long i ,taskid,numtask; A: w=1.0/N;
20、MPI_ Init(&argc,& argv); MPI _Comm _rank (MPI_COMM_WORLD,&taskid); MPI _Comm _Size (MPI_COMM_WORLD,&numtask); B: for (i= taskid; i N; i=i + numtask) P: temp = (i+0.5)*w; Q: local=4.0/(1.0+temp*temp)+local; C: MPI_Reduce (&local,&pi,1,MPI_Double,MPI_SUM,0, MPI_COMM_WORLD); D: if (taskid = =0) printf(“pi is %f n”,pi* w); MPI_Finalize ( ) ; / * main ( )*/國家高性能計算中心(合肥)512022/9/5共享變量(Shared Variable)概況:PVP, SMP, DSM的自然模型特點:多線程:SPMD, MPMD異步單一共享地址空間顯式同步隱式/隱式數(shù)據(jù)分布隱式通信(共享變量的讀/寫)國家高性能計算中心(合肥)522022/9/5計算的共享變量程序代碼# define N 100000 mai
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年度美容院美容師實習(xí)生實習(xí)考核及就業(yè)保障合同4篇
- 江蘇省無錫市江陰市要塞片2019-2020學(xué)年八年級下學(xué)期期中物理試題【含答案、解析】
- 2025版國際貿(mào)易信用證抵押融資服務(wù)合同樣本3篇
- 2025年度旅游車輛租賃合同(含景點導(dǎo)覽系統(tǒng))4篇
- 《新生兒氣胸》課件
- 2025版小學(xué)生校車租賃合同范本編制3篇
- 2025年度木工支模工程綠色施工與評價合同4篇
- 2025年分銷商分潤協(xié)議范例
- 2025年分銷合同的法律適用
- 2025版幼兒托管班信息化管理及數(shù)據(jù)共享協(xié)議3篇
- 2024年國家工作人員學(xué)法用法考試題庫及參考答案
- 國家公務(wù)員考試(面試)試題及解答參考(2024年)
- 《阻燃材料與技術(shù)》課件 第6講 阻燃纖維及織物
- 人教版五年級上冊遞等式計算100道及答案
- 2024年新課標(biāo)全國Ⅰ卷語文高考真題試卷(含答案)
- 湖南省退休人員節(jié)日慰問政策
- QB/T 5998-2024 寵物尿墊(褲)(正式版)
- 道路通行能力手冊第4章-高速公路基本路段
- 傳感器與測試技術(shù)試卷及答案
- 2020年普通高等學(xué)校招生全國統(tǒng)一數(shù)學(xué)考試大綱
- GB/T 679-2002化學(xué)試劑乙醇(95%)
評論
0/150
提交評論