1、并行算法實踐上篇 并行程序設計導論國家高性能計算中心（合肥）22022/9/5并行算法實踐上篇 并行程序設計導論單元I 并行程序設計基礎單元II 并行程序編程指南單元III 并行程序開發(fā)方法國家高性能計算中心（合肥）32022/9/5單元I 并行程序設計基礎第一章 并行計算機系統與結構模型第二章 PC機群的搭建第三章 并行程序設計簡介國家高性能計算中心（合肥）42022/9/5第三章 并行程序設計簡介3.1 并行程序開發(fā)方法3.1.1 并行層次與代碼粒度3.1.2 并行程序開發(fā)策略3.1.3 并行編程模式3.1.4 并行應用編程過程3.2 并行程序設計模型3.2.1 計算樣本程序3.2.2 數

2、據并行模型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 數據相關分析3.4.2 .數據劃分與處理器指派3.4.3 循環(huán)重構國家高性能計算中心（合肥）52022/9/5并行層次與代碼粒度國家高性能計算中心（合肥）62022/9/5并行層次粒度（指令數）并行實施編程支持甚細粒度指令級并行幾十條，如多指令發(fā)射、內存交叉存取硬件處理器細粒度數據級并行幾百條，如循環(huán)指令塊編譯器共享變量中粒度控制級并行幾千條，如過程、函數程序員（編譯器）共

3、享變量、消息傳遞粗粒度任務級并行數萬條，如獨立的作業(yè)任務操作系統消息傳遞國家高性能計算中心（合肥）72022/9/5并行程序開發(fā)策略國家高性能計算中心（合肥）82022/9/5并行編程模式主-從式（Master-Slave）單程序多數據流（Single Program Multiple Data ）數據流水線（Data Pipelining）分治策略（Divide and Conquer）國家高性能計算中心（合肥）92022/9/5主-從式（Master-Slave）其基本思想是將一個待求解的任務分成一個主任務（主進程）和一些從任務（子進程）。主進程負責將任務的分解、派發(fā)和收集諸子任務的求解結

4、果并最后匯總得到問題的最終解。諸子進程接收主進程發(fā)來的消息；并行進行各自計算；向主進程發(fā)回各自的計算結果。 國家高性能計算中心（合肥）102022/9/5單程序多數據流（SPMD）亦稱為單控制流多數據流模式，其基本思想是并行運行的進程均執(zhí)行相同的代碼段，但卻操作在各自不同的數據上。這種編程模式首先需要將應用程序的數據預先分配給各個計算進程（處理器）；然后諸計算進程并行的完成各自的計算任務，包括計算過程中各進程間的數據交換（施行通信同步）；最后才將各計算結果匯集起來。 國家高性能計算中心（合肥）112022/9/5數據流水線（Data Pipelining）其基本思想是將各計算進程組織成一條流水

5、線，每個進程執(zhí)行一個特定的計算任務，相應于流水線的一個階段。一個計算任務在功能上劃分成一些子任務（進程），這些子任務完成某種特定功能的計算工作，而且一旦前一個子任務完成，后繼的子任務就可立即開始。在整個計算過程中各進程之間的通信模式非常簡單，僅發(fā)生在相鄰的階段之間，且通信可以完全異步地進行。 國家高性能計算中心（合肥）122022/9/5國家高性能計算中心（合肥）132022/9/5分治策略（Divide and Conquer）其基本思想是將一個大而復雜的問題分解成若干個特性相同的子問題分而治之。若所得的子問題規(guī)模仍嫌過大，則可反復使用分治策略，直至很容易求解諸子問題為止。問題求解可分為三步

6、：將輸入分解成若干個規(guī)模近于相等的子問題；同時遞歸地求解諸子問題；歸并各子問題的解成為原問題的解。國家高性能計算中心（合肥）142022/9/5并行應用編程過程PCAM設計并行應用的四個階段劃分(Partitioning)通信(Communication)組合(Agglomeration)映射(Mapping)劃分：分解成小的任務，開拓并發(fā)性；通信：確定諸任務間的數據交換，監(jiān)測劃分的合理性；組合：依據任務的局部性，組合成更大的任務；映射：將每個任務分配到處理器上，提高并行性能。國家高性能計算中心（合肥）152022/9/5 PCAM設計過程國家高性能計算中心（合肥）162022/9/5 劃分方

7、法描述充分開拓算法的并發(fā)性和可擴放性；先進行數據分解(稱域分解)，再進行計算功能的分解(稱功能分解)；使數據集和計算集互不相交；劃分階段忽略處理器數目和目標機器的體系結構；能分為兩類劃分：域分解(Domain Decomposition)功能分解(Functional Decomposition)國家高性能計算中心（合肥）172022/9/5域分解 劃分的對象是數據，可以是程序中的輸入數據、中間處理數據和輸出數據；將數據分解成大致相等的小數據片；劃分時考慮數據上的相應操作；如果一個任務需要別的任務中的數據，則會產生任務間的通信；國家高性能計算中心（合肥）182022/9/5域分解 示例：三維網

8、格的域分解，各格點上計算都是重復的。下圖是三種分解方法：國家高性能計算中心（合肥）192022/9/5域分解 不規(guī)則區(qū)域的分解示例：國家高性能計算中心（合肥）202022/9/5功能分解 劃分的對象是計算（亦稱為任務分解或計算劃分），將計算劃分為不同的任務，其出發(fā)點不同于域分解；劃分后，研究不同任務所需的數據。如果這些數據不相交的，則劃分是成功的；如果數據有相當的重疊， 意味著存在大量的通信開銷，要重新進行域分解和功能分解；功能分解是一種更深層次的分解。國家高性能計算中心（合肥）212022/9/5功能分解 示例1：搜索樹示例2：氣候模型國家高性能計算中心（合肥）222022/9/5劃分判據

9、劃分是否具有靈活性？劃分是否避免了冗余計算和存儲？劃分任務尺寸是否大致相當？任務數與問題尺寸是否成比例？功能分解是一種更深層次的分解，是否合理？國家高性能計算中心（合肥）232022/9/5 通信分析通信是PCAM設計過程的重要階段；劃分產生的諸任務，一般不能完全獨立執(zhí)行，需要在任務間進行數據交流；從而產生了通信；功能分解確定了諸任務之間的數據流；諸任務是并發(fā)執(zhí)行的，通信則限制了這種并發(fā)性；國家高性能計算中心（合肥）242022/9/5 四種通信模式局部/全局通信結構化/非結構化通信靜態(tài)/動態(tài)通信同步/異步通信國家高性能計算中心（合肥）252022/9/5局部通信通信限制在一個鄰域內國家高性能

10、計算中心（合肥）262022/9/5全局通信通信非局部的例如：All to AllMaster-Worker53721國家高性能計算中心（合肥）272022/9/5結構化通信每個任務的通信模式是相同的；下面是否存在一個相同通信模式？國家高性能計算中心（合肥）282022/9/5非結構化通信沒有一個統一的通信模式例如：無結構化網格國家高性能計算中心（合肥）292022/9/5靜態(tài)/動態(tài)通信通信伙伴的身份不隨時間改變；動態(tài)通信中，通信伙伴的身份則可能由運行時所計算的數據決定且是可變的。 國家高性能計算中心（合肥）302022/9/5同步/異步通信同步通信時，接收方和發(fā)送方協同操作；異步通信中，接收

11、方獲取數據無需與發(fā)送方協同。國家高性能計算中心（合肥）312022/9/5通信判據 所有任務是否執(zhí)行大致相當的通信?是否盡可能的局部通信？通信操作是否能并行執(zhí)行?同步任務的計算能否并行執(zhí)行？國家高性能計算中心（合肥）322022/9/5任務組合 組合是由抽象到具體的過程，是將組合的任務能在一類并行機上有效的執(zhí)行；合并小尺寸任務，減少任務數。如果任務數恰好等于處理器數，則也完成了映射過程；通過增加任務的粒度和重復計算，可以減少通信成本；保持映射和擴展的靈活性，降低軟件工程成本；國家高性能計算中心（合肥）332022/9/5表面-容積效應通信量與任務子集的表面成正比，計算量與任務子集的體積成正比；

12、增加重復計算有可能減少通信量；國家高性能計算中心（合肥）342022/9/5重復計算重復計算減少通信量，但增加了計算量，應保持恰當的平衡；重復計算的目標應減少算法的總運算時間；國家高性能計算中心（合肥）352022/9/5重復計算示例：二叉樹上N個處理器求N個數的全和，要求每個處理器均保持全和。 二叉樹上求和，共需2logN步國家高性能計算中心（合肥）362022/9/5重復計算示例：二叉樹上N個處理器求N個數的全和，要求每個處理器均保持全和。 蝶式結構求和，使用了重復計算，共需logN步國家高性能計算中心（合肥）372022/9/5組合判據 增加粒度是否減少了通信成本？重復計算是否已權衡了其

13、得益？是否保持了靈活性和可擴放性？組合的任務數是否與問題尺寸成比例?是否保持了類似的計算和通信？有沒有減少并行執(zhí)行的機會？國家高性能計算中心（合肥）382022/9/5處理器映射 每個任務要映射到具體的處理器，定位到運行機器上；任務數大于處理器數時，存在負載平衡和任務調度問題；映射的目標：減少算法的執(zhí)行時間并發(fā)的任務 不同的處理器任務之間存在高通信的 同一處理器映射實際是一種權衡，屬于NP完全問題；國家高性能計算中心（合肥）392022/9/5負載平衡 靜態(tài)的：事先確定；概率的：隨機確定；動態(tài)的：執(zhí)行期間動態(tài)負載；基于域分解的：遞歸對剖局部算法概率方法循環(huán)映射國家高性能計算中心（合肥）4020

14、22/9/5任務分配與調度負載平衡與任務分配/調度密切相關，任務分配通常有靜態(tài)的和動態(tài)的兩種方法。靜態(tài)分配一般是任務到進程的算術映射。靜態(tài)分配的優(yōu)點是沒有運行時任務管理的開銷，但為了實現負載平衡，要求不同任務的工作量和處理器的性能是可以預測的并且擁有足夠的可供分配的任務。靜態(tài)調度（Static Scheduling）方案一般是靜態(tài)地為每個處理器分配個連續(xù)的循環(huán)迭代，其中為迭代次數，是處理器數。也可以采用輪轉（Round-robin）的方式來給處理器分配任務，即將第i個循環(huán)迭代分配給第i mod p個處理器。國家高性能計算中心（合肥）412022/9/5任務分配與調度動態(tài)分配與調度相對靈活，可以

15、運行時在不同處理器間動態(tài)地進行負載的調整。各種動態(tài)調度（Dynamic Scheduling）技術是并行計算研究的熱點，包括基本自調度SS（Self Scheduling）、塊自調度BSS（Block Self Scheduling）、 指導自調度GSS（Guided Self Scheduling）、因子分解調度FS（Factoring Scheduling）、梯形自調度TSS（Trapezoid Self Scheduling）、 耦合調度AS（Affinity Scheduling）、安全自調度SSS（Safe Self Scheduling）和自適應耦合調度AAS（Adapt Affi

16、nity Scheduling）。國家高性能計算中心（合肥）422022/9/5經理/雇員模式任務調度 任務放在集中的或分散的任務池中，使用任務調度算法將池中的任務分配給特定的處理器。國家高性能計算中心（合肥）432022/9/5映射判據 采用集中式負載平衡方案，是否存在通信瓶頸？采用動態(tài)負載平衡方案，調度策略的成本如何？國家高性能計算中心（合肥）442022/9/5并行程序設計模型數據并行模型（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數據并行（Data Parallel）概況：SIMD的自然模型，也可運行于SPMD、MIMD機器上局部計算和數據選路操作適合于使用規(guī)則網絡，模板和多維信號及圖像數據集來求解細粒度的應用

18、問題數據并行操作的同步是在編譯時而不是在運行時完成的 特點：單線程并行操作于聚合數據結構（數組）松散同步全局命名空間隱式相互作用隱式/半隱式數據分布國家高性能計算中心（合肥）482022/9/5計算的數據并行代碼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的自然模型，也可應用于共享變量多機系統，適合開發(fā)大粒度的并行性廣泛使用的標準消息傳遞庫MPI和PVM特點：多線程異步并行性分開的地址空間顯式相互作用顯式數據映射和負載分配常采用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異步單一共享地址空間顯式同步隱式/隱式數據分布隱式通信（共享變量的讀/寫）國家高性能計算中心（合肥）522022/9/5計算的共享變量程序代碼# define N 100000 mai