《并行計(jì)算基礎(chǔ)知識(shí)講座1》由會(huì)員分享，可在線閱讀，更多相關(guān)《并行計(jì)算基礎(chǔ)知識(shí)講座1（50頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、,,,,,,,單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級(jí),,第三級(jí),,第四級(jí),,第五級(jí),,,*,并 行 計(jì) 算 基 礎(chǔ) 知 識(shí),,趙俊鋒,,,西北工業(yè)大學(xué)理學(xué)院,,zhaojf,_77@,sina,.com,,,主要內(nèi)容,,并行計(jì)算環(huán)境,,并行算法基礎(chǔ),,什么問題可以并行化,,串行程序如何改為并行程序,,,為什么需要并行計(jì)算機(jī),,問題: 科學(xué)和工程問題的數(shù)值模擬與仿真,,計(jì)算密集,,數(shù)據(jù)密集,,網(wǎng)絡(luò)密集,,三種混合,,要求:在合理的時(shí)限內(nèi)完成計(jì)算任務(wù),,秒級(jí) 制造業(yè),,分鐘級(jí) 短時(shí)天氣預(yù)報(bào)(當(dāng)天),,小時(shí)級(jí) 中期天氣預(yù)報(bào)(3~10日),,盡可能快 長期天氣預(yù)報(bào)(氣候)
2、,,可計(jì)算 湍流模擬,,,,什么任務(wù)適合在超級(jí)計(jì)算環(huán)境內(nèi)運(yùn)行？,一般來說，計(jì)算量極大而使,PC,不能滿足要求或者根本不能計(jì)算的任務(wù)是適合在超級(jí)計(jì)算環(huán)境中運(yùn)行的。比如，,,,,（1）需要分布式并行處理的科學(xué)計(jì)算任務(wù)，包括：由于對(duì)計(jì)算資源要求過大而使現(xiàn)在的硬件條件無法滿足要求的計(jì)算任務(wù)，通過將串行源代碼改編為并行源代碼來進(jìn)行計(jì)算，或者有通行的并行計(jì)算程序（商業(yè)或非商業(yè)）；,,（2）雖然可以計(jì)算但是時(shí)間過長的問題等。,,,并行計(jì)算機(jī)的分類,并行向量機(jī)（,PVP）,,對(duì)稱多處理共享存儲(chǔ)多處理機(jī)（,SMP）,,大規(guī)模并行處理機(jī)（,MPP）,,工作站（微機(jī)）機(jī)群（,COW）,,分布式共享存儲(chǔ)多處理機(jī)（,
3、DSM）,,,COW(,Cluster of Workstation,),,一個(gè)節(jié)點(diǎn)可以是一臺(tái),PC,或,SMP；,,各節(jié)點(diǎn)一般由商品化的網(wǎng)絡(luò)互連；機(jī)群節(jié)點(diǎn)通過使用標(biāo)準(zhǔn)網(wǎng)絡(luò)協(xié)議（,TCP/IP）,來通信。使用的是千兆網(wǎng)。,,每個(gè)節(jié)點(diǎn)一般有本地磁盤；,,節(jié)點(diǎn)上的網(wǎng)絡(luò)接口是松散耦合到,I/O,總線上；,,每個(gè)節(jié)點(diǎn)有一個(gè)完整的操作系統(tǒng),但是通過中間層實(shí)現(xiàn)了單一系統(tǒng)映像（,SSI）。,,單一系統(tǒng)映像,單一系統(tǒng)映像（,Single System Image,，,SSI,）,并不是指系統(tǒng)中僅有唯一的操作系統(tǒng)映像駐留在內(nèi)存，而只是感覺上，像一個(gè)單一系統(tǒng)。,,其基本特征是單一系統(tǒng)、單一控制、對(duì)稱性、位置透明。
4、采用,SSI,的主要目的，是使機(jī)群的使用、控制和維護(hù)似乎和一臺(tái)工作站一樣。,,單一系統(tǒng)映像包括單一入口點(diǎn)、單一文件層次結(jié)構(gòu)、單一,I/O,空間、單一網(wǎng)絡(luò)、單一作業(yè)管理系統(tǒng)、單一存儲(chǔ)空間和單一進(jìn)程空間。,,,,,定 制 網(wǎng) 絡(luò),P/C,M,B,MB,LD,NIC,IOB,P/C,M,B,MB,LD,NIC,IOB,,,,并行機(jī)軟件環(huán)境,,操作系統(tǒng)方面：,RatHat9.0,,程序設(shè)計(jì)語言：,Fortran 77、 Fortran 90、C/C++,等,,,什么是并行算法,,算法是解題的精確描述，是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問題的一系列運(yùn)算。并行計(jì)算時(shí)可同時(shí)求解的諸進(jìn)程的集合，這些進(jìn)
5、程相互作用和協(xié)調(diào)動(dòng)作，并最終獲得問題的求解,,并行算法就是對(duì)并行計(jì)算過程的精確描述,,,并行算法的分類,,非數(shù)值計(jì)算并行算法,,數(shù)值計(jì)算并行算法，基于矩陣運(yùn)算、多項(xiàng)式求解、線性方程組求解等代數(shù)關(guān)系運(yùn)算的計(jì)算問題。,,,進(jìn)程 1,,,,發(fā)送信息,進(jìn)程 2,,,,接收信息,,傳統(tǒng)的,串行計(jì)算,，,分為“指令”,,和“數(shù)據(jù)”兩個(gè)部分，并在程序,,執(zhí)行時(shí)“獨(dú)立地申請(qǐng)和占有”內(nèi),,存空間，且所有計(jì)算均局限于,,該內(nèi)存空間。,,并行計(jì)算,將,進(jìn)程相對(duì)獨(dú)立的,,分配于不同的節(jié)點(diǎn)上，由,,各自獨(dú)立的操作系統(tǒng)調(diào)度，,,享有獨(dú)立的,CPU,和內(nèi)存資源,,（內(nèi)存可以共享）；進(jìn)程間,,相互信息交換通過消息傳遞,；,,
6、,進(jìn)程 1,,,,,,進(jìn)程 2,,,,,,進(jìn)程間通信,,現(xiàn)代操作系統(tǒng)提供基本的系統(tǒng)調(diào)用函數(shù)，允許位于同一臺(tái)處理機(jī)或不同處理機(jī)的多個(gè)進(jìn)程之間相互交流信息，操作具體表現(xiàn)為三種形式：通信、同步和聚集。,,以上的三種形式統(tǒng)稱為進(jìn)程間通信，操作的具體數(shù)據(jù)對(duì)象為消息，具體的操作為消息傳遞。,,,通信,,進(jìn)程間的數(shù)據(jù)傳遞稱為進(jìn)程間通信。,,在同一臺(tái)處理機(jī)中，通信可以讀/寫操作系統(tǒng)提供的共享數(shù)據(jù)緩存區(qū)來實(shí)現(xiàn)。,,不同處理機(jī)中，通信可以通過網(wǎng)絡(luò)來實(shí)現(xiàn)。,,,同步,,同步是使位于相同或不同處理機(jī)中的多個(gè)進(jìn)程之間的相互等待的操作，它要求進(jìn)程的所有操作均必須等待到達(dá)某一控制狀態(tài)之后才并行。,,,聚集,,聚集將位于相同
7、后不同處理機(jī)中的多個(gè)進(jìn)程的局部結(jié)果綜合起來，通過某種操作，例如最大值、最小值、累加和，產(chǎn)生一個(gè)新的結(jié)果，存儲(chǔ)在某個(gè)指定的或者所有的進(jìn)程變量中。,,,,共享存儲(chǔ),的模型和語言(適于,PVP, SMP, DSM),,X3H5,,Pthread,,OpenMP,,消息傳遞,的模型和語言(適于,MPP, Cluster, COW),,MPI (,Fortran, C,,Gamess,,,Vasp,),,PVM (,Fortran, C,),,數(shù)據(jù)并行,的模型和語言(適于在,MPP/Cluster,上實(shí)現(xiàn),SPMD,應(yīng)用),,Fortran 90,,HPF(High Performance Fortra
8、n),并行編程環(huán)境,,MPI(Message Passing Interface),,在當(dāng)前所有的消息傳遞軟件中, 最重要最流行的是,MPI,,它能運(yùn)行在所有的并行平臺(tái)上。,,程序設(shè)計(jì)語言支持,C, Fortran,等,。,,,,MPI,已經(jīng)成為一種標(biāo)準(zhǔn)，,,它以與語言獨(dú)立的形式來定義這個(gè)接口庫, 這個(gè)定義不包含任何專用于某個(gè)特別的制造商、操作系統(tǒng)或硬件的特性. 由于這個(gè)原因,,MPI,在并行計(jì)算界被廣泛地接受.,,,MPI,標(biāo)準(zhǔn)的實(shí)現(xiàn)包括,MPICH、LAM、IBM MPL,等多個(gè)版本，最常用和穩(wěn)定的是,MPICH。,它,提供了與,C、Fortran,語言的綁定。,,,我們可以將,MPI,看
9、成一個(gè)“庫” ，目前使用的消息傳遞庫是,MPICH 1.2,，,共有上百個(gè)接口，在,FORTRAN 77,和,C,語言中可以直接對(duì)這些函數(shù)進(jìn)行調(diào)用。多個(gè)進(jìn)程通過調(diào)用這些函數(shù)（類似調(diào)用子程序），進(jìn)行通信；,,Include,文件,C,語言應(yīng)用程序應(yīng)有#,include “,mpi,.h”,,Fortran,語言應(yīng)用程序應(yīng)有#,include ‘,mpif,.h’,,,MPI,并行編程模式,,單程序多數(shù)據(jù)流模式（,SPMD）,,多程序多數(shù)據(jù)流模式（,MPMD）,,,,,為了降低使用和維護(hù)并行應(yīng)用軟件的復(fù)雜度，一般采用,SPMD,模式,,MPI,程序的,SPMD,執(zhí)行模式,,一個(gè)程序同時(shí)啟動(dòng)多份,,
10、形成多個(gè)獨(dú)立的進(jìn)程，在不同的處理機(jī)上運(yùn)行，擁有獨(dú)立的內(nèi)存空間，進(jìn)程間通信通過調(diào)用,MPI,函數(shù)來實(shí)現(xiàn)；,,,SPMD,模式：?jiǎn)纬绦蚨鄶?shù)據(jù)流,,,例一,進(jìn)程0發(fā)送一個(gè)整數(shù)給進(jìn)程1；進(jìn)程1將該數(shù)加1，傳遞給進(jìn)程2；進(jìn)程2再將該數(shù)加1，再傳遞給進(jìn)程3；依次類推，最后，進(jìn)程,N-1,將該數(shù)傳遞給進(jìn)程0，由進(jìn)程1負(fù)責(zé)廣播該數(shù)給所有進(jìn)程，并打印輸出,。,,,,,進(jìn)程 1,,傳遞信息,,進(jìn)程 3,,傳遞信息,,進(jìn)程 2,,傳遞信息,,進(jìn)程 0,,傳遞信息,,編譯運(yùn)行命令,mpif77 –o exam exam.f,,mpirun,–,np,4 exam,,其中，,exam.f,指需要編譯的源文件，－
11、,o,表示生成輸出文件，,exam,指輸出文件名，－,np,表示進(jìn)程數(shù)。,,使用,mpicc,和,mpif77,省略了有關(guān),MPI,的路徑設(shè)置,,,,什么可以并行,能否將順序執(zhí)行的程序轉(zhuǎn)換成語義等價(jià)的、可并行執(zhí)行的程序，主要取決于程序的結(jié)構(gòu)形式，特別是其中的數(shù)據(jù)相關(guān)性。,,P1,：,A,＝,B+C,,P2,：,D,＝,A×B,,,其中，變量,A,是導(dǎo)致,P1,和,P2,發(fā)生數(shù)據(jù)相關(guān)的原因。為了保證程序執(zhí)行的語義正確性，變量,A,必須是先在,P1,中寫入后方可從,P2,中讀出，即必須先寫后讀。,,顯然，,P1,和,P2,不能并行執(zhí)行。,,數(shù)據(jù)相關(guān),,數(shù)據(jù)反相關(guān),,P1,：,A,＝,B×C,,P2
12、,：,C,＝,E+D,,P1,通過變量,C,數(shù)據(jù)相關(guān)于,P2,。,為保證語義正確性，必須等,P1,將變量,C,讀出后，,P2,方可向變量,C,進(jìn)行寫入操作，即必須先讀后寫。,,也不可并行化,,,數(shù)據(jù)輸出相關(guān),P1,：,A,＝,B+C,,P2,：,A,＝,D×E,,,為保證語義正確性，必須保證,P1,先寫入,A,，,然后允許,P2,再寫入,A,。,,,,除了上述,3,種相關(guān)外，還存在一種特殊情況，即兩個(gè)程序段的輸入變量互為輸出變量。此時(shí)，兩者必須并行執(zhí)行，方可保證語義的正確性。這就要求硬件機(jī)構(gòu)能保證兩者進(jìn)行同步讀寫。但若兩個(gè)處理機(jī)各帶有局部存儲(chǔ)器，則可降低同步要求。,,相關(guān)性與可并行化,伯恩斯坦
13、準(zhǔn)則,,,,I1∩O2,＝,Φ,，,即,P1,的輸入變量集與,P2,的輸出變量集不相交；,,I2∩O1,＝,Φ,，,即,P2,的輸入變量集與,P1,的輸出變量集不相交；,,O1∩O2,＝,Φ,，,即,P1,和,P2,的輸出變量集不相交,,,可并行處理,,如何將串行程序改為并行,,為理解創(chuàng)建一個(gè)并行程序中的步驟，,,讓我們首先定義三個(gè)重要的概念,:,任務(wù)，,,進(jìn)程和處理器。,,,任務(wù),,任務(wù)是程序要完成的一個(gè)工作，,,其內(nèi)容和大小是隨意的，,,它是并行程序所能處理的并發(fā)性最小的單元,;,即一個(gè)任務(wù)只能由一個(gè)處理器執(zhí)行，,,處理器之間的并發(fā)性只能在,任務(wù)之間開發(fā)。,,進(jìn)程,,進(jìn)程,(,我們也稱為線
14、程,),是一個(gè)完成任務(wù)的實(shí)體。一個(gè)并行程序由許多合作的進(jìn)程構(gòu)成，,,每個(gè)完成程序中任務(wù)的一個(gè)子集。,,通過某種分配機(jī)制，,,任務(wù)被分配給進(jìn)程,。,,進(jìn)程完成其任務(wù)的方式是通過在機(jī)器的物理處理器上執(zhí)行,,,,,進(jìn)程與處理器的區(qū)別,,并行化的觀點(diǎn)，,：,處理器是物理資源，,,進(jìn)程是抽象，,,或者虛擬化多處理器的一種方便的方式,:,我們通過進(jìn)程，,,而不是處理器來寫并行程序,;,將進(jìn)程映射到處理器是下一步。,,在一次程序的執(zhí)行中，,,進(jìn)程數(shù)不一定要等于處理器數(shù)。,,如果進(jìn)程多，,,一個(gè)處理器有可能要執(zhí)行多個(gè)進(jìn)程,;,如果進(jìn)程少，,,某些處理器則要閑置,,串行程序并行化的幾個(gè)步驟,,,從一個(gè)串行程序得
15、到一個(gè)并行程序的工作由四個(gè)步驟構(gòu)成：,,1.,,將計(jì)算的問題分解成任務(wù),,,2.,,將任務(wù)分配給進(jìn)程,,,3.,,在進(jìn)程之間組織必要的數(shù)據(jù)訪問，,,通信，,,和同步。,,4.,,將進(jìn)程映射或綁定到處理器,,在以上的幾個(gè)步驟中，并沒有考慮并行的效率問題。,,考慮到消息傳遞的開銷是計(jì)算開銷的10倍以上，一般來說，如果在應(yīng)用的一部分中，計(jì)算的時(shí)間是分鐘級(jí)的而數(shù)據(jù)傳輸?shù)臅r(shí)間是秒級(jí)的，那么這一部分可以并行執(zhí)行。,,,估計(jì)并行的效率,,,例二：矩陣相乘,,C,=,A B,,其中,A,和,B,分別是,m k,和,k,,n,矩陣,,,C,是,m,,n,矩陣,.,不失一般性,,,假設(shè),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,個(gè)任務(wù)，即將,C,的求解分成,p,塊。,,2、每個(gè)進(jìn)程對(duì)應(yīng)一個(gè),C,塊的求解。,,,,組織進(jìn)程間的通訊。即將,B,的各個(gè)子塊,send(),到各個(gè)進(jìn)程。,,通過,mpirun,運(yùn)行,將進(jìn)程映射到處理器上。,,,,,,,并行描述,,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,,,,,謝謝！,,
并行計(jì)算基礎(chǔ)知識(shí)講座1
