【正文】 ?? 1,)1(|,? ?l l o ckjl l o ckNib ji ??????? )1(,1|,? ?Ljm l o ckim l o ckc ji ??????? 1,)1(|,2021/11/10 58 MPI并行程序 例 2（續(xù)） 算法 ：矩陣 A和 C的子塊不動，矩陣 B的子塊在各個進程間循環(huán)移動。如圖，是當 nprocs＝ 3時的計算流程示意圖。 A0 A1 A2 B0 B1 B2 ＝ A0 B0 A0 B1 A0 B2 C0 A1 B0 A1 B1 A1 B2 C1 A2 B0 A2 B1 A2 B2 C2 A0 B0 B2 B1 A1 B1 B0 B2 A2 B2 B1 B0 進程 1 進程 2 進程 3 2021/11/10 59 MPI并行程序 例 2（續(xù)） MPI并行程序 ：主程序負責分配存儲單元并生成矩陣 A和 B的子塊，然后調(diào)用子程序 matmul完成矩陣的乘法運算。其中 nprocs為 MPI進程數(shù)， myrank為當前進程的MPI進程號。數(shù)組 A， B和 C分別存儲矩陣 A， B和 C的子塊。 work為工作數(shù)組，大小與數(shù)組 B一樣。 ?乘法子程序使用 MPI_Sendrecv_replace。（ ） ?使用異步通信函數(shù) MPI_Isend/MPI_Irecv， 在適當?shù)挠布h(huán)境下它可以使得計算與通信重疊進行。（ ） ?調(diào)用 BLAS庫函數(shù)完成矩陣子塊的乘積。選用適當?shù)腂LAS庫可以大幅度提高程序的實際運行性能。注意，編譯該程序時必須與 BLAS庫連接。（ ） 2021/11/10 60 MPI并行程序 例 3 一維 Dirichlet問題 ： 算法 :均勻網(wǎng)格有限差分離散 ,Jacobi迭代求解 。 區(qū)域分解 ： nproc=4, n = 21, ns = (n1)/nproc+1 =6 源程序： ????????????)(,)1(,)0()1,0(),()(xfuuxxfxu2021/11/10 61 MPI并行編程 環(huán)境 進程與消息傳遞 MPI并行程序設計入門 初步的 MPI消息傳遞函數(shù) 先進的 MPI函數(shù) MPI并行程序示例 面向性能的程序設計 2021/11/10 62 設計高性能并行程序的要點與技術(shù) ?劃分階段的性能問題 ?在多存儲系統(tǒng)中的數(shù)據(jù)訪問和通信 ?性能的整合 ?從處理器角度看到的性能因素 ?程序設計模型的影響 2021/11/10 63 在分解和分配步驟中 ， 我們可以將并行計算機系統(tǒng)簡單地看作是一個相互合作的處理器集合 ， 不用考慮程序設計模型和硬件系統(tǒng)組織 。 我們只需知道在處理器之間的通信開銷是很大的 。 此時 ， 在算法方面的三個基本要素是： ?平衡負載 ， 減少花在等待同步事件上的時間 ?減少通信開銷 ?減少由確定和管理分配所帶來的附加工作 不幸的是，即使這三種基本目標也是相互沖突的，必須進行折衷權(quán)衡。 劃分階段的性能問題 2021/11/10 64 平衡負載和減少同步等待時間的過程分為四步 ?在分解中識別足夠的并發(fā)性 （ 數(shù)據(jù)并行和功能并行 ） ； ?決定管理并發(fā)性的方式 (靜態(tài)分配和動態(tài)分配的對比 )； ?確定并發(fā)性開發(fā)的粒度； ?降低序列化和同步代價 。 2021/11/10 65 在多存儲系統(tǒng)中的數(shù)據(jù)訪問和通信 多處理器系統(tǒng)也是多存儲器系統(tǒng) ， 多緩存系統(tǒng) 。系統(tǒng)這些組成部分的作用對程序執(zhí)行性能是十分重要的 ， 并且其重要性與程序設計模型無關 （ 盡管程序設計模型可能影響某些性能折衷考慮的特性 ） 。 在這里 ， 我們從一種不同的角度來看多處理器系統(tǒng) 。 ?多處理器系統(tǒng)看成為擴展的存儲層次結(jié)構(gòu) ?在擴展的存儲層次中的附加通信 ?用工作集的觀念看人為的通信和數(shù)據(jù)的復制 2021/11/10 66 性能的整合 ?減少人為通信： 開發(fā)時間局部性與空間局部性； ?將通信結(jié)構(gòu)化以降低開銷：通過減少通信開銷和降低延遲，增加帶寬，減少占有度，提供機制來分散沖突，用計算和通信來重疊通信 。 2021/11/10 67 從處理器角度看到的性能因素 在我們通常的分布存儲并行系統(tǒng)結(jié)構(gòu)上 ， 并行執(zhí)行時間有五個分量： ?忙有用 ：處理器花在執(zhí)行指令上的時間 ， 那些指令本來在串行程序中也是要執(zhí)行的 。 假設一個直接從串行算法中導出的確定性的并行程序 ， 所有處理器的有用忙時間之和等于串行執(zhí)行的有用忙時間 。 ?忙開銷 ：處理器花在執(zhí)行那些在串行程序中不需要的指令上的時間 。 這直接對應于并行程序中的額外工作部分 。 ?數(shù)據(jù)局部 ：等待數(shù)據(jù)引用被它自己的存儲系統(tǒng)滿足的時間；即等待的引用不會產(chǎn)生和其它節(jié)點的通信 。 ?數(shù)據(jù)遠程 ：等待數(shù)據(jù)通信的時間 ， 無論是固有通信還是附加通信 。 這代表處理器看到的通信代價 。 2021/11/10 68 ?同步 ：等待其它進程給出某個事件發(fā)生的信號 ， 有了該信號 ，本進程才能推進 。 這包括負載不平衡和程序中的串行化現(xiàn)象 ，還有實際花在執(zhí)行同步操作和訪問同步變量上的時間 。 當它等待的時候 ， 一個處理器可能重復檢測某個變量的值 ， 直到改變 —這就要執(zhí)行指令 —或者它停滯等待 ， 這取決于同步的實現(xiàn)方式 。 同步、忙開銷、遠程數(shù)據(jù)訪問分量是由于并行所引入的開銷，在串行程序在單處理器上執(zhí)行沒有。固有通信大多數(shù)包含在遠程數(shù)據(jù)分量中，它的某些（通常很?。┎糠挚赡芤苍跀?shù)據(jù)局部分量中體現(xiàn)出來。 從處理器角度看到的性能因素（續(xù)） 2021/11/10 69 程序設計模型的影響 經(jīng)驗表明 ， 隨著應用變得更復雜和更非規(guī)則 ， 透明命名和復制的有用性增加 ， 這是傾向于共享存儲的觀點 。 然而 ， 由于通信自然是細粒度的 （ 特別是非規(guī)則應用 ） ， 還由于大粒度通信和一致性引起的性能問題 ， 支持共享空間就要求有大膽的通信系統(tǒng)結(jié)構(gòu) ， 用硬件來支持大多數(shù)功能 。 許多計算機公司現(xiàn)在正建造這樣的機器 ， 作為它們的高端系統(tǒng) 。 在另一方面 ， 便宜的工作站或者多處理器群也正在逐步流行起來 。 這些系統(tǒng)通常是消息傳遞程序設計的 ，這是由于消息傳遞的性能模型比較好定義 ， 可以用大消息來分攤開銷 ， 程序員有顯式的控制 ， 以及不同的機器操作粒度對性能的相對影響不大 。 2021/11/10 70 總結(jié)評述 我們已經(jīng)看到，性能的方方面面是相互制約的，設計好的并行程序的藝術(shù)在于在相互矛盾的要求中獲得適當?shù)恼壑?。以高性能為目標的程序設計也是一個逐步求精的過程：在后面所發(fā)現(xiàn)的系統(tǒng)或者程序的特點，可能導致在前一個步驟中作的決定被修改。將性能的潛力都發(fā)揮出來可能需要很大的努力，這取決于應用和系統(tǒng)兩個方面。進而，不同技術(shù)一起發(fā)揮作用的程度和方式能夠大大影響表現(xiàn)給系統(tǒng)結(jié)構(gòu)的負載的特點。 2021/11/10 71 問題討論 請聯(lián)系 王振海、趙俊峰 Tel:8849355017 Email: 2021/11/10 72 Thanks!