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

1、,,,,,,,單擊此處編輯母版標題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,*,*,,基于,MPI,的并行程序設計,王振海,,西北工業(yè)大學理學院,,西北工業(yè)大學高性能計算研究與發(fā)展中心,2024/9/18,1,,MPI,并行編程,環(huán)境,,進程與消息傳遞,,,MPI,并行程序設計入門,,初步的,MPI,消息傳遞函數(shù),,先進的,MPI,函數(shù),,MPI,并行程序示例,,面向性能的程序設計,,主要內容,2024/9/18,2,,目前，高性能并行機主要可以分為對稱多處理共享存儲并行機（,SMP, Symmetric,MultiProcessor,）、,分布式共享存儲多處

2、理機 （,DSM,,Distributied,Shared Memory）、,大規(guī)模并行處理機（,MPP, Massively Parallel Processor）,和微機機群（,Cluster）,等四類。在這些并行機上，并行程序設計平臺主要可分為消息傳遞、共享存儲和數(shù)據(jù)并行三類，其中消息傳遞具有很好的可移植性，它能被所有這些類型的并行機所支持，而共享存儲只能在在,SMP,和,DSM,并行機中使用，數(shù)據(jù)并行只能在,SMP，DSM,和,MPP,并行機上使用。,并行編程,環(huán)境簡介,2024/9/18,3,,消息傳遞并行編程環(huán)境（,MPI：Message Passing Interface）,是目

3、前國際上最流行、可移植性和可擴展性很好的并行程序設計平臺，并被當前流行的所有高性能并行機所支持。它是在標準串行程序設計語言（,C，F(xiàn)ortran，C++）,的基礎上，再加入實現(xiàn)進程間通信的,MPI,消息傳遞庫函數(shù)，就構成了,MPI,并行程序設計所依賴的并行編程環(huán)境。,,MPI,已經在,Windows,系列的非,Unix、Linux,平臺上實現(xiàn)，其程序設計語言支持,C, Fortran,和,Java。,在國產的三大并行機系列神威、銀河和曙光上也都實現(xiàn)了對,MPI,和支持。,MPI,并行編程,環(huán)境,2024/9/18,4,,MPI,并行,環(huán)境的應用現(xiàn)狀,,MPI,是全球工業(yè)、政府和科研部門聯(lián)合推出

4、的適合進程間進行標準消息傳遞的并行程序設計平臺，最初版,MPI 1.0,本于,1994,年,6,月推出，目前最新的為,MPI 2.0,版，于,1998,年10月推出。,,MPI,的,具體實現(xiàn),：,MPICH,和,LAMMPI，,目前均已實現(xiàn),MPI 1.2,版，適用于任何并行計算平臺；部分并行機已實現(xiàn),MPI 2.0,版。,,MPI,是目前應用最廣的并行程序設計平臺，幾乎被所有并行計算環(huán)境（共享和分布式存儲并行機、,MPP、,機群系統(tǒng)等）和流行的多進程操作系統(tǒng)（,UNIX、Windows NT）,所支持，基于它開發(fā)的應用程序具有最佳的可移植性。,2024/9/18,5,,MPI,并行,環(huán)境的應

5、用現(xiàn)狀（續(xù)）,,目前高效率的超大規(guī)模并行計算（,1000,個處理器）最可信賴的平臺。,,工業(yè)、科學與工程計算部門的大量科研和工程軟件（氣象、石油、地震、空氣動力學、核等）目前已經移植到,MPI,平臺，發(fā)揮了重要作用。,,,MPI,的,優(yōu)點,：（1）具有很好的可移植性，幾乎被所有的并行環(huán)境支持；（2）具有很好的可擴展性，是目前高效率的大規(guī)模并行計算最可信賴的平臺；（3）比其它消息傳遞系統(tǒng)好用；（4）有完備的異步通信功能；（5）有精確的定義，從而為并行軟件產業(yè)的發(fā)展提供了必要的條件。,2024/9/18,6,,MPI,并行,環(huán)境的應用現(xiàn)狀（續(xù)）,,MPI 2.0,版在1.0版的基礎上，增加了如下的

6、消息傳遞功能,：（1）并行,I/O：,允許多個進程同時讀寫同一個文件；（2）線程安全：允許,MPI,進程的多個線程執(zhí)行，即支持與,OpenMP,的混合并行編程；（3）動態(tài)進程管理：允許并行應用程序在執(zhí)行過程中，動態(tài)地增加和刪除進程個數(shù)；（4）單邊通信：允許某個進程對其它進程的局部內存單元直接執(zhí)行讀寫訪問，而步需要對方進程的顯式干預；（5）并行應用程序之間,的動態(tài)互操作：允許各個,MPI,并行應用程序之間動態(tài)地建立和刪除消息傳遞通道。,,目前，各類并行機，特別式微機機群，只實現(xiàn)了,MPI 2.0,的部分功能。本中心機群所支持的為,MPI 1.2.5,版本。,2024/9/18,7,,MPI,并行

7、編程,環(huán)境,,進程與消息傳遞,,,MPI,并行程序設計入門,,初步的,MPI,消息傳遞函數(shù),,先進的,MPI,函數(shù),,MPI,并行程序示例,,面向性能的程序設計,2024/9/18,8,,單個進程（,process,）,進程,是一個程序，同時包含它的執(zhí)行環(huán)境（內存、寄存器、程序計數(shù)器等），是操作系統(tǒng)中獨立存在的可執(zhí)行的基本程序單位。,,通俗理解：串行應用程序編譯形成的可執(zhí)行代碼，分為“指令”和“數(shù)據(jù)”兩個部分，并在程序執(zhí)行時“獨立地申請和占有”內存空間，且所有計算均局限于該內存空間。,進程,1,,內存,,進程,2,,2024/9/18,9,,單機內多個進程,,多個進程可以,同時存在于單機內同一

8、操作系統(tǒng),：,由操作系統(tǒng)負責調度分時共享處理機資源（,CPU,、,內存、存儲、外設等）。,,進程間相互獨立,（,內存空間不相交）,：,在操作系統(tǒng)調度下各自獨立地運行，例如多個串行應用程序在同一臺計算機中運行,。,,進程間可以相互交換信息,：例如數(shù)據(jù)交換、同步等待，,消息,是這些交換信息的基本單位，,消息傳遞,是指這些信息在進程間的相互交換，是實現(xiàn)進程間通信的唯一方式,。,2024/9/18,10,,最基本的消息傳遞操作,：發(fā)送消息（,send,）、,接受消息（,receive,）、,進程同步（,barrier,）、,規(guī)約（,reduction,）,。,,消息傳遞的實現(xiàn),：共享內存或信號量，用戶

9、不必關心,。,單機內多個進程（續(xù)）,2024/9/18,11,,包含于通過網絡聯(lián)接的不同計算機的多個進程,,進程獨立存在,：進程位于不同的計算機，由各自獨立的操作系統(tǒng)調度，享有獨立的,CPU,和內存資源。,,進程間相互信息交換,：消息傳遞,。,,消息傳遞的實現(xiàn),：基于網絡,socket,機制,,,用戶不必關心。,2024/9/18,12,,消息傳遞庫函數(shù),,應用程序接口,（,API）：,提供給應用程序（,FORTRAN、C、C++,語言）的可直接調用的完成進程間消息傳遞的某項特定功能的函數(shù)。,,消息傳遞庫,：,所有定義的消息傳遞函數(shù)編譯形成的軟件庫，調用其內部函數(shù)的應用程序，通過與之聯(lián)接，即可

10、成為可并行執(zhí)行的程序。,,目前流行的消息傳遞函數(shù)庫,：,PVM 3.3.11、,MPICH 1.2,、LAMMPI 6.4,等。,2024/9/18,13,,標準消息傳遞界面,MPI,MPI,標準,：根據(jù)應用程序對消息傳遞功能的需求，全球工業(yè)、應用和研究部門聯(lián)合推出標準的消息傳遞界面函數(shù)，不考慮其具體實現(xiàn)，以保證并行應用程序的可移植性,。,,MPI,的具體實現(xiàn),：消息傳遞庫函數(shù)，目前有影響的為,MPICH,和,LAMMPI,，,我們注重,MPICH,系列,。,2024/9/18,14,,基于消息傳遞的并行程序執(zhí)行模式,,SPMD,模式：單程序多數(shù)據(jù)流,2024/9/18,15,,基于消息傳遞的

11、并行程序執(zhí)行模式（續(xù)）,,MPM,模式,：多程序多數(shù)據(jù)流，除初始啟動多個可執(zhí)行代碼，其余與,SPMD,模式一致。,2024/9/18,16,,共享存儲與分布式存儲,,屬于并行機體系結構的范疇，與消息傳遞并行程序設計平臺無關,。,2024/9/18,17,,消息傳遞是相對于,進程間通信方式,而言的，與具體并行機存儲模式無關，任何支持進程間通信的并行機，均可支持消息傳遞并行程序設計,。,,幾乎所有共享和分布存儲并行計算環(huán)境均支持進程間的消息傳遞通信,。,共享存儲與分布式存儲（續(xù)）,,2024/9/18,18,,MPI,并行編程,環(huán)境,,進程與消息傳遞,,,MPI,并行程序設計入門,,初步的,MPI

12、,消息傳遞函數(shù),,先進的,MPI,函數(shù),,MPI,并行程序示例,,面向性能的程序設計,2024/9/18,19,,MPI,并行程序設計平臺由,標準消息傳遞函數(shù)及相關輔助函數(shù),構成，多個進程通過調用這些函數(shù)（類似調用子程序），進行通信。,,SPMD,執(zhí)行模式,：一個程序同時啟動多份，形成多個獨立的進程，在不同的處理機上運行，擁有獨立的內存空間，進程間通信通過調用,MPI,函數(shù)來實現(xiàn)。,,每個進程開始執(zhí)行時，將獲得一個唯一的序號（,rank）。,例如啟動,P,個進程，序號依次為0，1，…，,P-1。,MPI,并行程序,2024/9/18,20,,MPI,并行程序,例,1,進程0發(fā)送一個整數(shù)給進程1

13、；進程1將該數(shù)加1，傳遞給進程2；進程2再將該數(shù)加1，再傳遞給進程3；依次類推，最后，進程,P-1,將該數(shù)傳遞給進程0，由進程0負責廣播該數(shù)給所有進程，并打印輸出。,program example1,,include “,mpif,.h” !! MPI,系統(tǒng)頭文件,,,integer status(MPI_STATUS_SIZE), my_rank,p,,integer source,,dest,,tag,,ierr,,data,,c,2024/9/18,21,,MPI,并行程序,例,1（續(xù)）,c-------,進入,MPI,系統(tǒng),,,call MPI_Init(,ierr

14、,),,call MPI_,Comm,_rank(MPI_COMM_WORLD,my_rank,,ierr,),,call MPI_,Comm,_size(MPI_COMM_WORLD,p,,ierr,),,c-------,數(shù)據(jù)交換,,,data=0,,tag = 5,,source= my_rank-1,,if(source.,eq,.-1) source=p-1,,,dest,=my_rank+1,,if(,dest,.,eq,.p),dest,=0,2024/9/18,22,,,if(my_rank.,eq,.0) then,,call MPI_Send(data,1,MPI_IN

15、TEGER,,dest,,tag,MPI_COMM_WORLD,,ierr,),,call MPI_,Recv,(data,1,MPI_INTEGER,source,tag,MPI_COMM_WORLD,status,,ierr,),,else,,call MPI_,Recv,(data,1,MPI_INTEGER,source,tag,MPI_COMM_WORLD,status,,ierr,),,data=data+1,,call MPI_Send(data,1,MPI_INTEGER,,dest,,tag,MPI_COMM_WORLD,,ierr,),,,endif,,c,,MPI,并行程

16、序,例,1（續(xù)）,2024/9/18,23,,c-------,廣播數(shù)據(jù),,,call MPI_,Bcast,(data,1,MPI_INTEGER,0,MPI_COMM_WORLD,,ierr,),,c------,打印輸出,,,if(my_rank.,eq,.0) then,,if(data.,eq,.p-1) then,,print *,”Successful, data=”,data,,else,,print *,”Failure, data=”,data,,,endif,,endif,,c,,call MPI_Finalize(,ierr,),,end,MPI,并行程序,例,1（續(xù)）

17、,2024/9/18,24,,MPI,并行程序的運行,MPI,編譯命令,:,mpif77 -o exam.e example.f,,運行命令,:,mpirun,–,np,4 exam.e,,運行效果,：,MPI,系統(tǒng)選擇相同或不同的4個處理機，在每個處理機上運行程序代碼,exam.e。,,運行結果,：,Successful, data=3,,2024/9/18,25,,運行分析,2024/9/18,26,,MPI,重要概念,進程序號,（,rank）,：,各進程通過函數(shù),MPI_,Comm,_rank(),獲取各自的序號。,,消息號,：,消息的標號。,,通信器,(,Communicato

18、r),：,1),理解為一類進程的集合，且在該集合內，進程間可以相互通信；類比：郵局、電話局、國際網；,2),任何,MPI,通信函數(shù)均必須在某個通信器內發(fā)生；,3),MPI,系統(tǒng)提供省缺的通信器,MPI_COMM_WORLD,，,所有啟動的,MPI,進程通過調用函數(shù),MPI_Init(),包含在該通信器內；,4),各進程通過函數(shù),MPI_,Comm,_size(),獲取通信器包含的,(,初始啟動,),的,MPI,進程個數(shù)。,2024/9/18,27,,消息,：,分為,數(shù)據(jù)（,data,）,和,包裝（,envelope,）,兩個部分，其中，包裝由,接收進程序號,、,發(fā)送進程序號,、,消息標號,和,

19、通信器,四部分組成，數(shù)據(jù)包含用戶將要傳遞的內容,。,,進程組,：,一類進程的集合，在它的基礎上，可以定義新的通信器。,,基本數(shù)據(jù)類型,：,對應于,FORTRAN,和,C,語言的內部數(shù)據(jù)類型（,INTEGER，REAL，DOUBLE PRECISION，COMPLEX，LOGICAL，CHARACTER），MPI,系統(tǒng)提供已定義好的對應數(shù)據(jù)類型（,MPI_INTEGER，MPI_REAL，MPI_DOUBLE_PRECISION，MPI_COMPLEX，MPI_LOGICAL，MPI_CHARACTER）,。,MPI,重要概念（續(xù)）,2024/9/18,28,,MPI,重要概念（續(xù)）,自定義數(shù)據(jù)

20、類型,：,基于基本數(shù)據(jù)類型，用戶自己定義的數(shù)據(jù)類型（后面介紹）,。,,MPI,對象,：,MPI,系統(tǒng)內部定義的數(shù)據(jù)結構，包括數(shù)據(jù)類型、進程組、通信器等，它們對用戶不透明，在,FORTRAN,語言中，所有,MPI,對象均必須說明為“整型變量,INTEGER”,。,,MPI,聯(lián)接器（,handle,）,：,聯(lián)接,MPI,對象和用戶的橋梁，用戶可以通過它訪問和參與相應,MPI,對象的具體操作；例如，,MPI,系統(tǒng)內部提供的通信器,MPI_COMM_WORLD；,在,FORTRAN,語言中，所有,MPI,聯(lián)接器均必須說明為“,整型變量,INTEGER,”,。,2024/9/18,29,,MPI,重要概

21、念（續(xù)）,進程拓撲結構,：,進程組內部進程之間的一種相互連接結構，如,3,?,3,網格，將在后面介紹,。,,,,,3×3,網格拓撲結構,,靜態(tài)進程個數(shù),：,進程數(shù)由命令“,mpirun,–,np xxx,”,初始確定為,xxx,個，程序執(zhí)行過程中,不能動態(tài)改變,進程的個數(shù) 。,2024/9/18,30,,MPI,重要概念（續(xù)）,消息緩存區(qū),：,應用程序產生的消息包含的數(shù)據(jù)所處的內存空間,。,,標準輸入,：所有進程的標準輸入,read(*,*),均省缺為當前終端屏幕，且只能由0號進程執(zhí)行該操作，其他進程需要這些輸入參數(shù)，只能由0號進程執(zhí)行數(shù)據(jù)廣播操作。,,標準輸出,：,所有進程可以獨立執(zhí)行標準

22、輸出,write（*，*），,但其省缺為當前終端屏幕。,2024/9/18,31,,MPI,函數(shù)格式,FORTAN,語言中，最后一個參數(shù)為該函數(shù)調用是否成功的標志：0表示成功，其它表示各種可能的錯誤。,,C,語言中，該標志有函數(shù)參數(shù)返回。,,C ：,ierr,=MPI_,Comm,_rank(,myrank,),,F : MPI_,Comm,_rank(,myrank,,,ierr,),2024/9/18,32,,MPI,函數(shù)的使用查詢,,由函數(shù)名查詢：,man,,函數(shù)名 （,MPI_,Xxxx,）,,注意大小寫,例如,,man MPI_,Comm,_rank,,man MPI

23、_Send,,man MPI_,recv,2024/9/18,33,,MPI,函數(shù)的學習與使用,,注重,MPI,函數(shù)的各類功能，由應用程序的通信需求出發(fā)，尋找匹配的函數(shù)類型，在查找具體函數(shù)名，采用,man,命令可以查詢該函數(shù)的具體參數(shù)含義和使用方法。,2024/9/18,34,,一般的,MPI,程序設計流程圖,程序參數(shù)說明,Call MPI_Init ( ),進入,MPI,系統(tǒng),通信器,MPI_COMM_WORLD,形成,,Call MPI_,Comm,_rank ( ),,Call MPI_,Comm,_size ( ),建立新的通信器、定義新的數(shù)據(jù)類型和進程拓撲結構,2024/9/18,

24、35,,一般的,MPI,程序設計流程圖（續(xù)）,應用程序實體：,,．計算控制程序體；,,．進程間通信；,Call MPI_Finalize ( ),End,退出,MPI,系統(tǒng),,2024/9/18,36,,MPI,并行編程,環(huán)境,,進程與消息傳遞,,,MPI,并行程序設計入門,,初步的,MPI,消息傳遞函數(shù),,先進的,MPI,函數(shù),,MPI,并行程序示例,,面向性能的程序設計,2024/9/18,37,,點對點通信（,point-to-point）,定義,：給定屬于同一通信器內的兩個進程，其中一個發(fā)送消息，一個接收消息,。,,MPI,系統(tǒng)定義的所有通信方式均建立在點對點通信之上。,,四種模式,：

25、,標準模式,、緩存區(qū)模式、同步模式、就緒模式。,2024/9/18,38,,標準模式點對點通信,進程可以隨意地發(fā)送（接收）消息，與是否存在匹配的消息接收（發(fā)送）進程無關。,,發(fā)收匹配：,,發(fā)收不匹配：,,進程0,進程1,進程0,進程1,進程2,2024/9/18,39,,標準模式點對點通信,的分類,阻塞式,：消息發(fā)送函數(shù)返回，用戶可以對消息緩存區(qū)進行處理，不會影響已發(fā)送的消息數(shù)據(jù)；接收函數(shù)返回，用戶可以使用接收到的消息數(shù)據(jù),。,,非阻塞式,：發(fā)送和接受函數(shù)返回后，必須調用另一類函數(shù)來確保它們的正確完成。,2024/9/18,40,,標準模式點對點通信,的分類舉例,2024/9/18,41,,點

26、對點通信函數(shù)舉例,阻塞式標準消息發(fā)送函數(shù),,MPI_Send（,buf,，count，,datatype,，,dest,，tag，,comm,，,ierr,）,,Real*8（integer，…）,buf,:,消息發(fā)送緩存區(qū)起始地址,,(,Fortran,,用戶的待發(fā)送的第一個數(shù)據(jù)),,integer count ：,buf,起始的數(shù)據(jù)單元個數(shù),,integer,datatype,：,數(shù)據(jù)類型（基本或用戶定義的）,,integer,dest,:,接收進程序號,,integer tag :,消息的標號,,integer,comm,:,通信器,,integer,i

27、err,:,函數(shù)調用返回錯誤碼,2024/9/18,42,,,real *8 a(100,100),,integer b(60,60),,c-----,發(fā)送50個雙精度數(shù)“,a(5,20) : a(54,20)”,到2號進程,,call MPI_Send( a (5,20),50,MPI_DOUBLE_PRECISION,2,,,& 99999,MPI_COMM_WORLD,,ierr,),,c-----,發(fā)送20個整型數(shù)“,b(20,40) : b(39,40)”,到5號進程,,call MPI_Send( b (20,40),20,MPI_DOUBLE_PRECI

28、SION,5,,,& 99999,MPI_COMM_WORLD,,ierr,),阻塞式標準消息發(fā)送函數(shù)舉例,2024/9/18,43,,MPI_,Recv,（,buf,，count，,datatype,，,dest,，tag，,comm,，status,,ierr,）,,Real*8（integer，…）,buf,:,消息接收緩存區(qū)起始地址,,(,Fortran,,用戶用于接受的第一個數(shù)據(jù)),,,integer count ：,buf,起始的數(shù)據(jù)單元個數(shù),,,integer,datatype,：,數(shù)據(jù)類型（基本或用戶定義的）,,,integer,dest,:

29、,發(fā)送進程序號,,,integer tag :,消息的標號,,,integer,comm,:,通信器,,,integer status(MPI_STATUS_SIZE) :,接收狀態(tài)數(shù)組;,,,integer,ierr,:,函數(shù)調用返回錯誤碼,阻塞式標準消息接收函數(shù),,2024/9/18,44,,阻塞式標準消息接收函數(shù)舉例,,real *8 a(100,100),,integer b(60,60),,c-----,從2號進程接收50個雙精度數(shù)到“,a(5,20) : a(54,20)”,,call MPI_,Recv,( a (5,20),50,MPI_DOUBLE_

30、PRECISION,2,,,& 99999,MPI_COMM_WORLD,status,,ierr,),,c-----,從5號進程接收20個整型數(shù)到“,b(20,40) : b(39,40)”,,call MPI_,Recv,( b (20,40),20,MPI_DOUBLE_PRECISION,5,,,& 99999,MPI_COMM_WORLD,status,,ierr,),其他點對點通信函數(shù)：參考手冊。,2024/9/18,45,,聚合通信（,Collective Communication）,定義,：屬于同一通信器的所有,MPI,進程均必須參

31、與的通信操作,。,,參與方式,：調用同一聚合通信函數(shù)。,,函數(shù)類型,：,,同步通信函數(shù),：,所有進程在某個程序點上同步。,,,,MPI_Barrier (,comm,,,ierr,),,全局通信函數(shù),,全局規(guī)約函數(shù),,,2024/9/18,46,,全局通信函數(shù),廣播,:,MPI_,Bcast,(,buf,,count,,dtype,,,root,,,comm,,,ierr,),,root,發(fā)送,,other,接收,,收集,：,MPI_Gather(,bufs,,,bufr,,count,,dtype,,root,,comm,,,ierr,),,all,發(fā)送大小一致的數(shù)據(jù)塊,,root,接收并按

32、序號連續(xù)存放,,全收集：,MPI_,Allgather,(),,all,發(fā)送,,all,接收,2024/9/18,47,,全局通信函數(shù)（續(xù)）,索引收集,:,MPI_,Gatherv,(),,all,發(fā)送大小不等的數(shù)據(jù)塊,,root,接收并按索引間斷存放,,索引全收集,:,MPI_,Allgatherv,(),,all,發(fā)送大小不等的數(shù)據(jù)塊,,all,接收并按索引間斷存放,2024/9/18,48,,全局通信函數(shù)（續(xù)）,分散,:,MPI_Scatter(,bufs,,,bufr,,count,,dtype,,root,,comm,,,ierr,),,root,發(fā)送連續(xù)的大小一致的數(shù)據(jù)塊,,all

33、,接收,,索引分散,:,MPI_,Scatterv,(),,root,發(fā)送間斷的的大小不一致的數(shù)據(jù)塊,,all,接收,,全交換,:,MPI_,Scatterv,(),,all,發(fā)送大小一致數(shù)據(jù)塊到各進程,,all,接收大小一致數(shù)據(jù)塊并按序號連續(xù)存放,2024/9/18,49,,全局規(guī)約,(,global reduction),函數(shù),規(guī)約,:,MPI_Reduce(,sbuf,,,rbuf,,count,,dtype,,,op,,,root,,,comm,,,ierr,),,規(guī)約操作類型,op,: MPI_SUM, MPI_MIN, MPI_MAX,,,MPI_PROD,等12種。,,全規(guī)約,

34、：,MPI_,Allreduce,(),,除要求將結果返回到所有進程外,與,MPI_Reduce(),一致,,規(guī)約分散,：,MPI_Reduce_scatter(),,將規(guī)約結果分散到各進程。,,,并行前綴計算,：,MPI_Scan(),2024/9/18,50,,MPI,并行編程,環(huán)境,,進程與消息傳遞,,,MPI,并行程序設計入門,,初步的,MPI,消息傳遞函數(shù),,先進的,MPI,函數(shù),,MPI,并行程序示例,,面向性能的程序設計,2024/9/18,51,,自定義數(shù)據(jù)類型,定義,:,在,MPI,系統(tǒng)已定義的基本數(shù)據(jù)類型（,MPI_INTEGER,MPI_REAL,MPI_DOUBLE_P

35、RECISION,MPI_CHARACTER,等）基礎上，用戶根據(jù)需求，自己定義的數(shù)據(jù)類型,。,,在用戶已定義好的數(shù)據(jù)類型基礎上，還可以進一步定義新的數(shù)據(jù)類型。,,用戶定義的數(shù)據(jù)類型，必須由函數(shù),MPI_Type_Commit(),提交給,MPI,系統(tǒng)；此后，就可以象基本數(shù)據(jù)類型一樣，在消息傳遞函數(shù)中重復使用；并由函數(shù),MPI_Type_free(),釋放。,,具體自定義數(shù)據(jù)類型函數(shù)，請參考手冊。,2024/9/18,52,,自定義數(shù)據(jù)類型（續(xù)）,,real a(1000),,,發(fā)送:,a(5:9),,,call MPI_Send(a(5), 5, MPI_ REAL,…..)

36、 OK,,發(fā)送:,a(5),a(7),a(9),a(11),a(13),a(15),,do i=5, 15, 2,,call MPI_Send(a(i),1,MPI_REAL,….) OK,,,enddo,,缺點,: 多次發(fā)送，效率低，程序設計繁瑣,,改進,：用戶定義新的數(shù)據(jù)類型,,call MPI_Type_vector(5,1,2,MPI_REAL,,newtype,,,ierr,),,call MPI_Type_commit(,newtype,,,ierr,),提交,,call MPI_Send(a(5), 1,,newtype,,….),,call

37、 MPI_Type_free(,newtype,,,ierr,),釋放,2024/9/18,53,,進程拓撲結構,,定義,：根據(jù)應用程序的特征，在進程間建立的一種虛擬拓撲連接方式，以方便并行程序設計和提高并行計算性能。,,例,：二維規(guī)則區(qū)域，3*3 區(qū)域分解，9個進程，建立,Cartesion,坐標，進程（,i,j）,的相鄰進程為(,i-1,j), (i+1,j), (i,j-1), (i,j+1)。,2024/9/18,54,,并行,I/O,各進程可以類似于串行程序獨立地讀,/,寫,不同,的文件,。,,MPICH 1.2,以上版本支持所有進程并行讀寫同一個文件,。,2024/9/18,55,

38、,MPI,并行編程,環(huán)境,,進程與消息傳遞,,,MPI,并行程序設計入門,,初步的,MPI,消息傳遞函數(shù),,先進的,MPI,函數(shù),,MPI,并行程序示例,,面向性能的程序設計,2024/9/18,56,,MPI,并行程序,例,2,矩陣乘積,：,A,為,M×N,階矩陣，,B,為,N×L,階矩陣，,C,為,M×L,階矩陣。計算矩陣乘積,C＝AB。,,算法描述,：假設使用,nprocs,個,MPI,進程，為簡單起見假定,M,和,L,均為,nprocs,的倍數(shù)。,A,和,C,按行等分成子塊分別存儲在不同的進程中，而,B,則按列等分成子塊分別存儲在不同的進程中。,A，B,和,C,的子塊大小分別為,mlo

39、c,×N，N×,lloc,和,mloc,×L，,其中,mloc,＝M/,nprocs,，,lloc,＝L/,nprocs,。,具體存儲方式為（,k＝0,…,,nprocs,-1）：,,,存儲在進程,k,的數(shù)組,A,中,,存儲在進程,k,的數(shù)組,B,中,,存儲在進程,k,的數(shù)組,C,中,2024/9/18,57,,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,C

40、1,A2×B0 A2×B1 A2×B2,C2,A0,,B0,,B2,,B1,A1,,B1,,B0,,B2,A2,,B2,,B1,,B0,進程1,進程2,進程3,2024/9/18,58,,MPI,并行程序,例,2（續(xù)）,MPI,并行程序,：主程序負責分配存儲單元并生成矩陣,A,和,B,的子塊，然后調用子程序,matmul,完成矩陣的乘法運算。其中,nprocs,為,MPI,進程數(shù)，,myrank,為當前進程的,MPI,進程號。數(shù)組,A，B,和,C,分別存儲矩陣,A，B,和,C,的子塊。,work,為工作數(shù)組，大小與數(shù)組,B,一樣。,,乘法子程序使用,MPI_,Sendrecv,_replace

41、。（ex1.f）,,使用異步通信函數(shù),MPI_,Isend,/MPI_,Irecv,，,在適當?shù)挠布h(huán)境下它可以使得計算與通信重疊進行。（,ex2.f）,,調用,BLAS,庫函數(shù)完成矩陣子塊的乘積。選用適當?shù)?BLAS,庫可以大幅度提高程序的實際運行性能。注意，編譯該程序時必須與,BLAS,庫連接。（,ex3.f）,2024/9/18,59,,MPI,并行程序,例3,,一維,Dirichlet,問題,：,,,,算法,:均勻網格有限差分離散,,Jacobi,迭代求解。,,區(qū)域分解,：,nproc,=4, n = 21, ns = (n-1)/,nproc,+1 =6,,源程序：1,dpoisso

42、n,.f,2024/9/18,60,,MPI,并行編程,環(huán)境,,進程與消息傳遞,,,MPI,并行程序設計入門,,初步的,MPI,消息傳遞函數(shù),,先進的,MPI,函數(shù),,MPI,并行程序示例,,面向性能的程序設計,2024/9/18,61,,設計高性能并行程序的要點與技術,,劃分階段的性能問題,,在多存儲系統(tǒng)中的數(shù)據(jù)訪問和通信,,,性能的整合,,,從處理器角度看到的性能因素,,,程序設計模型的影響,,2024/9/18,62,,在分解和分配步驟中，我們可以將并行計算機系統(tǒng)簡單地看作是一個相互合作的處理器集合，不用考慮程序設計模型和硬件系統(tǒng)組織。我們只需知道在處理器之間的通信開銷是很大的。此時，在

43、算法方面的三個基本要素是：,,平衡負載，減少花在等待同步事件上的時間,,減少通信開銷,,減少由確定和管理分配所帶來的附加工作,,不幸的是，即使這三種基本目標也是相互沖突的，必須進行折衷權衡。,,劃分階段的性能問題,2024/9/18,63,,平衡負載和減少同步等待時間的過程分為四步,在分解中識別足夠的并發(fā)性（數(shù)據(jù)并行和功能并行）；,,決定管理并發(fā)性的方式(,靜態(tài)分配和動態(tài)分配的對比,)；,,確定并發(fā)性開發(fā)的粒度；,,降低序列化和同步代價。,,2024/9/18,64,,在多存儲系統(tǒng)中的數(shù)據(jù)訪問和通信,多處理器系統(tǒng)也是多存儲器系統(tǒng)，多緩存系統(tǒng)。系統(tǒng)這些組成部分的作用對程序執(zhí)行性能是十分重要的，并

44、且其重要性與程序設計模型無關（盡管程序設計模型可能影響某些性能折衷考慮的特性）。在這里，我們從一種不同的角度來看多處理器系統(tǒng)。,,多處理器系統(tǒng)看成為擴展的存儲層次結構,,,在擴展的存儲層次中的附加通信,,,用工作集的觀念看人為的通信和數(shù)據(jù)的復制,2024/9/18,65,,性能的整合,減少人為通信：,開發(fā)時間局部性與空間局部性；,,將通信結構化以降低開銷：通過減少通信開銷和降低延遲，增加帶寬，減少占有度，提供機制來分散沖突，用計算和通信來重疊通信 。,2024/9/18,66,,從處理器角度看到的性能因素,,在我們通常的分布存儲并行系統(tǒng)結構上，并行執(zhí)行時間有五個分量：,,忙有用,：處理器花在執(zhí)

45、行指令上的時間，那些指令本來在串行程序中也是要執(zhí)行的。假設一個直接從串行算法中導出的確定性的并行程序，所有處理器的有用忙時間之和等于串行執(zhí)行的有用忙時間。,,忙開銷,：處理器花在執(zhí)行那些在串行程序中不需要的指令上的時間。這直接對應于并行程序中的額外工作部分。,,數(shù)據(jù)局部,：等待數(shù)據(jù)引用被它自己的存儲系統(tǒng)滿足的時間；即等待的引用不會產生和其它節(jié)點的通信,。,,數(shù)據(jù)遠程,：等待數(shù)據(jù)通信的時間，無論是固有通信還是附加通信。這代表處理器看到的通信代價。,2024/9/18,67,,同步,：等待其它進程給出某個事件發(fā)生的信號，有了該信號，本進程才能推進。這包括負載不平衡和程序中的串行化現(xiàn)象，還有實際花在

46、執(zhí)行同步操作和訪問同步變量上的時間。當它等待的時候，一個處理器可能重復檢測某個變量的值，直到改變—這就要執(zhí)行指令—或者它停滯等待，這取決于同步的實現(xiàn)方式。,,,同步、忙開銷、遠程數(shù)據(jù)訪問分量是由于并行所引入的開銷，在串行程序在單處理器上執(zhí)行沒有。固有通信大多數(shù)包含在遠程數(shù)據(jù)分量中，它的某些（通常很?。┎糠挚赡芤苍跀?shù)據(jù)局部分量中體現(xiàn)出來。,從處理器角度看到的性能因素（續(xù)）,,2024/9/18,68,,程序設計模型的影響,經驗表明，隨著應用變得更復雜和更非規(guī)則，透明命名和復制的有用性增加，這是傾向于共享存儲的觀點。然而，由于通信自然是細粒度的（特別是非規(guī)則應用），還由于大粒度通信和一致性引起的性

47、能問題，支持共享空間就要求有大膽的通信系統(tǒng)結構，用硬件來支持大多數(shù)功能。許多計算機公司現(xiàn)在正建造這樣的機器，作為它們的高端系統(tǒng)。在另一方面，便宜的工作站或者多處理器群也正在逐步流行起來。這些系統(tǒng)通常是消息傳遞程序設計的，這是由于消息傳遞的性能模型比較好定義，可以用大消息來分攤開銷，程序員有顯式的控制，以及不同的機器操作粒度對性能的相對影響不大。,2024/9/18,69,,總結評述,,我們已經看到，性能的方方面面是相互制約的，設計好的并行程序的藝術在于在相互矛盾的要求中獲得適當?shù)恼壑浴Ｒ愿咝阅転槟繕说某绦蛟O計也是一個逐步求精的過程：在后面所發(fā)現(xiàn)的系統(tǒng)或者程序的特點，可能導致在前一個步驟中作的決定被修改。將性能的潛力都發(fā)揮出來可能需要很大的努力，這取決于應用和系統(tǒng)兩個方面。進而，不同技術一起發(fā)揮作用的程度和方式能夠大大影響表現(xiàn)給系統(tǒng)結構的負載的特點。,,2024/9/18,70,,問題討論,,請聯(lián)系,,王振海、趙俊峰,,Tel:88493550-17 Email:,zhwang,@nwpu.,edu,.,cn,,zhaojf,_77@,2024/9/18,71,,Thanks!,2024/9/18,72,,