《并行計算基礎知識講座1》由會員分享，可在線閱讀，更多相關《并行計算基礎知識講座1（50頁珍藏版）》請在裝配圖網上搜索。

1、,,,,,,,單擊此處編輯母版標題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,*,并 行 計 算 基 礎 知 識,,趙俊鋒,,,西北工業(yè)大學理學院,,zhaojf,_77@,sina,.com,,,主要內容,,并行計算環(huán)境,,并行算法基礎,,什么問題可以并行化,,串行程序如何改為并行程序,,,為什么需要并行計算機,,問題: 科學和工程問題的數值模擬與仿真,,計算密集,,數據密集,,網絡密集,,三種混合,,要求:在合理的時限內完成計算任務,,秒級 制造業(yè),,分鐘級 短時天氣預報(當天),,小時級 中期天氣預報(3~10日),,盡可能快 長期天氣預報(氣候)

2、,,可計算 湍流模擬,,,,什么任務適合在超級計算環(huán)境內運行？,一般來說，計算量極大而使,PC,不能滿足要求或者根本不能計算的任務是適合在超級計算環(huán)境中運行的。比如，,,,,（1）需要分布式并行處理的科學計算任務，包括：由于對計算資源要求過大而使現在的硬件條件無法滿足要求的計算任務，通過將串行源代碼改編為并行源代碼來進行計算，或者有通行的并行計算程序（商業(yè)或非商業(yè)）；,,（2）雖然可以計算但是時間過長的問題等。,,,并行計算機的分類,并行向量機（,PVP）,,對稱多處理共享存儲多處理機（,SMP）,,大規(guī)模并行處理機（,MPP）,,工作站（微機）機群（,COW）,,分布式共享存儲多處理機（,

3、DSM）,,,COW(,Cluster of Workstation,),,一個節(jié)點可以是一臺,PC,或,SMP；,,各節(jié)點一般由商品化的網絡互連；機群節(jié)點通過使用標準網絡協(xié)議（,TCP/IP）,來通信。使用的是千兆網。,,每個節(jié)點一般有本地磁盤；,,節(jié)點上的網絡接口是松散耦合到,I/O,總線上；,,每個節(jié)點有一個完整的操作系統(tǒng),但是通過中間層實現了單一系統(tǒng)映像（,SSI）。,,單一系統(tǒng)映像,單一系統(tǒng)映像（,Single System Image,，,SSI,）,并不是指系統(tǒng)中僅有唯一的操作系統(tǒng)映像駐留在內存，而只是感覺上，像一個單一系統(tǒng)。,,其基本特征是單一系統(tǒng)、單一控制、對稱性、位置透明。

4、采用,SSI,的主要目的，是使機群的使用、控制和維護似乎和一臺工作站一樣。,,單一系統(tǒng)映像包括單一入口點、單一文件層次結構、單一,I/O,空間、單一網絡、單一作業(yè)管理系統(tǒng)、單一存儲空間和單一進程空間。,,,,,定 制 網 絡,P/C,M,B,MB,LD,NIC,IOB,P/C,M,B,MB,LD,NIC,IOB,,,,并行機軟件環(huán)境,,操作系統(tǒng)方面：,RatHat9.0,,程序設計語言：,Fortran 77、 Fortran 90、C/C++,等,,,什么是并行算法,,算法是解題的精確描述，是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問題的一系列運算。并行計算時可同時求解的諸進程的集合，這些進

5、程相互作用和協(xié)調動作，并最終獲得問題的求解,,并行算法就是對并行計算過程的精確描述,,,并行算法的分類,,非數值計算并行算法,,數值計算并行算法，基于矩陣運算、多項式求解、線性方程組求解等代數關系運算的計算問題。,,,進程 1,,,,發(fā)送信息,進程 2,,,,接收信息,,傳統(tǒng)的,串行計算,，,分為“指令”,,和“數據”兩個部分，并在程序,,執(zhí)行時“獨立地申請和占有”內,,存空間，且所有計算均局限于,,該內存空間。,,并行計算,將,進程相對獨立的,,分配于不同的節(jié)點上，由,,各自獨立的操作系統(tǒng)調度，,,享有獨立的,CPU,和內存資源,,（內存可以共享）；進程間,,相互信息交換通過消息傳遞,；,,

6、,進程 1,,,,,,進程 2,,,,,,進程間通信,,現代操作系統(tǒng)提供基本的系統(tǒng)調用函數，允許位于同一臺處理機或不同處理機的多個進程之間相互交流信息，操作具體表現為三種形式：通信、同步和聚集。,,以上的三種形式統(tǒng)稱為進程間通信，操作的具體數據對象為消息，具體的操作為消息傳遞。,,,通信,,進程間的數據傳遞稱為進程間通信。,,在同一臺處理機中，通信可以讀/寫操作系統(tǒng)提供的共享數據緩存區(qū)來實現。,,不同處理機中，通信可以通過網絡來實現。,,,同步,,同步是使位于相同或不同處理機中的多個進程之間的相互等待的操作，它要求進程的所有操作均必須等待到達某一控制狀態(tài)之后才并行。,,,聚集,,聚集將位于相同

7、后不同處理機中的多個進程的局部結果綜合起來，通過某種操作，例如最大值、最小值、累加和，產生一個新的結果，存儲在某個指定的或者所有的進程變量中。,,,,共享存儲,的模型和語言(適于,PVP, SMP, DSM),,X3H5,,Pthread,,OpenMP,,消息傳遞,的模型和語言(適于,MPP, Cluster, COW),,MPI (,Fortran, C,,Gamess,,,Vasp,),,PVM (,Fortran, C,),,數據并行,的模型和語言(適于在,MPP/Cluster,上實現,SPMD,應用),,Fortran 90,,HPF(High Performance Fortra

8、n),并行編程環(huán)境,,MPI(Message Passing Interface),,在當前所有的消息傳遞軟件中, 最重要最流行的是,MPI,,它能運行在所有的并行平臺上。,,程序設計語言支持,C, Fortran,等,。,,,,MPI,已經成為一種標準，,,它以與語言獨立的形式來定義這個接口庫, 這個定義不包含任何專用于某個特別的制造商、操作系統(tǒng)或硬件的特性. 由于這個原因,,MPI,在并行計算界被廣泛地接受.,,,MPI,標準的實現包括,MPICH、LAM、IBM MPL,等多個版本，最常用和穩(wěn)定的是,MPICH。,它,提供了與,C、Fortran,語言的綁定。,,,我們可以將,MPI,看

9、成一個“庫” ，目前使用的消息傳遞庫是,MPICH 1.2,，,共有上百個接口，在,FORTRAN 77,和,C,語言中可以直接對這些函數進行調用。多個進程通過調用這些函數（類似調用子程序），進行通信；,,Include,文件,C,語言應用程序應有#,include “,mpi,.h”,,Fortran,語言應用程序應有#,include ‘,mpif,.h’,,,MPI,并行編程模式,,單程序多數據流模式（,SPMD）,,多程序多數據流模式（,MPMD）,,,,,為了降低使用和維護并行應用軟件的復雜度，一般采用,SPMD,模式,,MPI,程序的,SPMD,執(zhí)行模式,,一個程序同時啟動多份,,

10、形成多個獨立的進程，在不同的處理機上運行，擁有獨立的內存空間，進程間通信通過調用,MPI,函數來實現；,,,SPMD,模式：單程序多數據流,,,例一,進程0發(fā)送一個整數給進程1；進程1將該數加1，傳遞給進程2；進程2再將該數加1，再傳遞給進程3；依次類推，最后，進程,N-1,將該數傳遞給進程0，由進程1負責廣播該數給所有進程，并打印輸出,。,,,,,進程 1,,傳遞信息,,進程 3,,傳遞信息,,進程 2,,傳遞信息,,進程 0,,傳遞信息,,編譯運行命令,mpif77 –o exam exam.f,,mpirun,–,np,4 exam,,其中，,exam.f,指需要編譯的源文件，－

11、,o,表示生成輸出文件，,exam,指輸出文件名，－,np,表示進程數。,,使用,mpicc,和,mpif77,省略了有關,MPI,的路徑設置,,,,什么可以并行,能否將順序執(zhí)行的程序轉換成語義等價的、可并行執(zhí)行的程序，主要取決于程序的結構形式，特別是其中的數據相關性。,,P1,：,A,＝,B+C,,P2,：,D,＝,A×B,,,其中，變量,A,是導致,P1,和,P2,發(fā)生數據相關的原因。為了保證程序執(zhí)行的語義正確性，變量,A,必須是先在,P1,中寫入后方可從,P2,中讀出，即必須先寫后讀。,,顯然，,P1,和,P2,不能并行執(zhí)行。,,數據相關,,數據反相關,,P1,：,A,＝,B×C,,P2

12、,：,C,＝,E+D,,P1,通過變量,C,數據相關于,P2,。,為保證語義正確性，必須等,P1,將變量,C,讀出后，,P2,方可向變量,C,進行寫入操作，即必須先讀后寫。,,也不可并行化,,,數據輸出相關,P1,：,A,＝,B+C,,P2,：,A,＝,D×E,,,為保證語義正確性，必須保證,P1,先寫入,A,，,然后允許,P2,再寫入,A,。,,,,除了上述,3,種相關外，還存在一種特殊情況，即兩個程序段的輸入變量互為輸出變量。此時，兩者必須并行執(zhí)行，方可保證語義的正確性。這就要求硬件機構能保證兩者進行同步讀寫。但若兩個處理機各帶有局部存儲器，則可降低同步要求。,,相關性與可并行化,伯恩斯坦

13、準則,,,,I1∩O2,＝,Φ,，,即,P1,的輸入變量集與,P2,的輸出變量集不相交；,,I2∩O1,＝,Φ,，,即,P2,的輸入變量集與,P1,的輸出變量集不相交；,,O1∩O2,＝,Φ,，,即,P1,和,P2,的輸出變量集不相交,,,可并行處理,,如何將串行程序改為并行,,為理解創(chuàng)建一個并行程序中的步驟，,,讓我們首先定義三個重要的概念,:,任務，,,進程和處理器。,,,任務,,任務是程序要完成的一個工作，,,其內容和大小是隨意的，,,它是并行程序所能處理的并發(fā)性最小的單元,;,即一個任務只能由一個處理器執(zhí)行，,,處理器之間的并發(fā)性只能在,任務之間開發(fā)。,,進程,,進程,(,我們也稱為線

14、程,),是一個完成任務的實體。一個并行程序由許多合作的進程構成，,,每個完成程序中任務的一個子集。,,通過某種分配機制，,,任務被分配給進程,。,,進程完成其任務的方式是通過在機器的物理處理器上執(zhí)行,,,,,進程與處理器的區(qū)別,,并行化的觀點，,：,處理器是物理資源，,,進程是抽象，,,或者虛擬化多處理器的一種方便的方式,:,我們通過進程，,,而不是處理器來寫并行程序,;,將進程映射到處理器是下一步。,,在一次程序的執(zhí)行中，,,進程數不一定要等于處理器數。,,如果進程多，,,一個處理器有可能要執(zhí)行多個進程,;,如果進程少，,,某些處理器則要閑置,,串行程序并行化的幾個步驟,,,從一個串行程序得

15、到一個并行程序的工作由四個步驟構成：,,1.,,將計算的問題分解成任務,,,2.,,將任務分配給進程,,,3.,,在進程之間組織必要的數據訪問，,,通信，,,和同步。,,4.,,將進程映射或綁定到處理器,,在以上的幾個步驟中，并沒有考慮并行的效率問題。,,考慮到消息傳遞的開銷是計算開銷的10倍以上，一般來說，如果在應用的一部分中，計算的時間是分鐘級的而數據傳輸的時間是秒級的，那么這一部分可以并行執(zhí)行。,,,估計并行的效率,,,例二：矩陣相乘,,C,=,A B,,其中,A,和,B,分別是,m k,和,k,,n,矩陣,,,C,是,m,,n,矩陣,.,不失一般性,,,假設,m,=,m,,p

16、,,,k,=,k,,p,和,n,=,n,,p,。,,,串行程序,double a[N][N],b[N][N],c[N][N];,,for (i=0; i

17、述：,,1、將問題（矩陣乘法）分成,p,個任務，即將,C,的求解分成,p,塊。,,2、每個進程對應一個,C,塊的求解。,,,,組織進程間的通訊。即將,B,的各個子塊,send(),到各個進程。,,通過,mpirun,運行,將進程映射到處理器上。,,,,,,,并行描述,,for,i,= 0,to,p,－,1,do,,l,＝,i,+,myid,mod,p,,C,l,,=,A,*,B,, mp1,＝,myid,+1 mod,p,, mm1,＝,myid,-1 mod,p,,if,i,！,=,p－,,1,, send(,B,, mm1),,recv,(,B,, mp1),,End,for,,,,,謝謝！,,