并行程序設計

并行算法實踐上篇并行程序設計導論2023/2/41現(xiàn)代密碼學理論與實踐之五并行算法實踐

上篇并行程序設計導論單元I并行程序設計基礎單元II并行程序編程指南單元III并行程序開發(fā)方法2023/2/42現(xiàn)代密碼學理論與實踐之五單元II并行程序編程指南第四章MPI編程指南第五章PVM編程指南第六章HPF編程指南第七章OpenMP編程指南2023/2/43現(xiàn)代密碼學理論與實踐之五第四章MPI編程指南4.1引言4.26個基本函數(shù)組成的MPI子集4.3MPI消息4.4點對點通信4.5群集通信4.6MPI擴展4.7小結2023/2/44現(xiàn)代密碼學理論與實踐之五4.1引言MPI(MessagePassingInterface)是一個消息傳遞接口標準MPI提供一個可移植、高效、靈活的消息傳遞接口庫MPI以語言獨立的形式存在，可運行在不同的操作系統(tǒng)和硬件平臺上MPI提供與C/C++和Fortran語言的綁定2023/2/45現(xiàn)代密碼學理論與實踐之五4.1引言MPI的版本MPICH：/mpi/mpichLAM(LocalAreaMulticomputer):Open-MPI:/CHIMP:ftp://ftp.epcc.ed.ac.uk/pub/chimp/release/2023/2/46現(xiàn)代密碼學理論與實踐之五4.26個基本函數(shù)組成的MPI子集#include"mpi.h"/*MPI頭函數(shù)，提供了MPI函數(shù)和數(shù)據(jù)類型定義*/intmain(intargc,char**argv){intrank,size,tag=1;intsenddata,recvdata;MPI_Statusstatus;MPI_Init(&argc,&argv);/*MPI的初始化函數(shù)*/MPI_Comm_rank(MPI_COMM_WORLD,&rank);/*該進程編號*/MPI_Comm_size(MPI_COMM_WORLD,&size);/*總進程數(shù)目*/2023/2/47現(xiàn)代密碼學理論與實踐之五4.26個基本函數(shù)組成的MPI子集if(rank==0){senddata=9999;MPI_Send(&senddata,1,MPI_INT,1,tag,MPI_COMM_WORLD);/*發(fā)送數(shù)據(jù)到進程1*/}if(rank==1)MPI_Recv(&recvdata,1,MPI_INT,0,tag,MPI_COMM_WORLD,&status);/*從進程0接收數(shù)據(jù)*/MPI_Finalize();/*MPI的結束函數(shù)*/return(0);}2023/2/48現(xiàn)代密碼學理論與實踐之五4.26個基本函數(shù)組成的MPI子集MPI初始化：通過MPI_Init函數(shù)進入MPI環(huán)境并完成所有的初始化工作。intMPI_Init(int*argc,char***argv)MPI結束：通過MPI_Finalize函數(shù)從MPI環(huán)境中退出。intMPI_Finalize(void)2023/2/49現(xiàn)代密碼學理論與實踐之五4.26個基本函數(shù)組成的MPI子集獲取進程的編號：調(diào)用MPI_Comm_rank函數(shù)獲得當前進程在指定通信域中的編號，將自身與其他程序區(qū)分。intMPI_Comm_rank(MPI_Commcomm,int*rank)獲取指定通信域的進程數(shù)：調(diào)用MPI_Comm_size函數(shù)獲取指定通信域的進程個數(shù)，確定自身完成任務比例。intMPI_Comm_size(MPI_Commcomm,int*size)2023/2/410現(xiàn)代密碼學理論與實踐之五4.26個基本函數(shù)組成的MPI子集消息發(fā)送：MPI_Send函數(shù)用于發(fā)送一個消息到目標進程。intMPI_Send(void*buf,intcount,MPI_Datatypedataytpe,intdest,inttag,MPI_Commcomm)消息接受:MPI_Recv函數(shù)用于從指定進程接收一個消息intMPI_Recv(void*buf,intcount,MPI_Datatypedatatyepe,intsource,inttag,MPI_Commcomm,MPI_Status*status)2023/2/411現(xiàn)代密碼學理論與實踐之五4.3MPI消息一個消息好比一封信消息的內(nèi)容即信的內(nèi)容，在MPI中稱為消息緩沖(MessageBuffer)消息的接收/發(fā)送者即信的地址，在MPI中稱為消息信封(MessageEnvelop)2023/2/412現(xiàn)代密碼學理論與實踐之五4.3MPI消息MPI中，消息緩沖由三元組<起始地址，數(shù)據(jù)個數(shù)，數(shù)據(jù)類型>標識消息信封由三元組<源/目標進程，消息標簽，通信域>標識三元組的方式使得MPI可以表達更為豐富的信息，功能更強大2023/2/413現(xiàn)代密碼學理論與實踐之五4.3MPI消息(數(shù)據(jù)類型)MPI的消息類型分為兩種：預定義類型和派生數(shù)據(jù)類型(DerivedDataType)預定義數(shù)據(jù)類型:MPI支持異構計算(HeterogeneousComputing)，它指在不同計算機系統(tǒng)上運行程序，每臺計算可能有不同生產(chǎn)廠商，不同操作系統(tǒng)。MPI通過提供預定義數(shù)據(jù)類型來解決異構計算中的互操作性問題，建立它與具體語言的對應關系。派生數(shù)據(jù)類型：MPI引入派生數(shù)據(jù)類型來定義由數(shù)據(jù)類型不同且地址空間不連續(xù)的數(shù)據(jù)項組成的消息。2023/2/414現(xiàn)代密碼學理論與實踐之五4.3MPI消息(數(shù)據(jù)類型)2023/2/415現(xiàn)代密碼學理論與實踐之五4.3MPI消息(數(shù)據(jù)類型)MPI提供了兩個附加類型:MPI_BYTE和MPI_PACKED

。MPI_BYTE表示一個字節(jié)，所有的計算系統(tǒng)中一個字節(jié)都代表8個二進制位。MPI_PACKED預定義數(shù)據(jù)類型被用來實現(xiàn)傳輸?shù)刂房臻g不連續(xù)的數(shù)據(jù)項。2023/2/416現(xiàn)代密碼學理論與實踐之五4.3MPI消息(數(shù)據(jù)類型)doubleA[100];MPI_Pack_size(50,MPI_DOUBLE,comm,&BufferSize);TempBuffer=malloc(BufferSize);j=sizeof(MPI_DOUBLE);Position=0;for(i=0;i<50;i++)

MPI_Pack(A+i*j,1,MPI_DOUBLE,TempBuffer,BufferSize,&Position,comm);MPI_Send(TempBuffer,Position,MPI_PACKED,destination,tag,comm);

MPI_Pack_size函數(shù)來決定用于存放50個MPI_DOUBLE數(shù)據(jù)項的臨時緩沖區(qū)的大小調(diào)用malloc函數(shù)為這個臨時緩沖區(qū)分配內(nèi)存for循環(huán)中將數(shù)組A的50個偶序數(shù)元素打包成一個消息并存放在臨時緩沖區(qū)2023/2/417現(xiàn)代密碼學理論與實踐之五4.3MPI消息(數(shù)據(jù)類型)消息打包，然后發(fā)送MPI_Pack(buf,count,dtype,//以上為待打包消息描述packbuf,packsize,packpos,//以上為打包緩沖區(qū)描述communicator)消息接收，然后拆包 MPI_Unpack(packbuf,packsize,packpos,//以上為拆包緩沖區(qū)描述buf,count,dtype,//以上為拆包消息描述communicatior)2023/2/418現(xiàn)代密碼學理論與實踐之五4.3MPI消息(數(shù)據(jù)類型)派生數(shù)據(jù)類型可以用類型圖來描述，這是一種通用的類型描述方法，它是一系列二元組<基類型，偏移>的集合，可以表示成如下格式：{<基類型0,偏移0>，···，<基類型n-1,偏移n-1>}在派生數(shù)據(jù)類型中，基類型可以是任何MPI預定義數(shù)據(jù)類型，也可以是其它的派生數(shù)據(jù)類型，即支持數(shù)據(jù)類型的嵌套定義。如圖，陰影部分是基類型所占用的空間，其它空間可以是特意留下的，也可以是為了方便數(shù)據(jù)對齊。2023/2/419現(xiàn)代密碼學理論與實踐之五4.3MPI消息(數(shù)據(jù)類型)MPI提供了全面而強大的構造函數(shù)(ConstructorFunction)來定義派生數(shù)據(jù)類型。函數(shù)名含義MPI_Type_contiguous定義由相同數(shù)據(jù)類型的元素組成的類型MPI_Type_vector定義由成塊的元素組成的類型，塊之間具有相同間隔MPI_Type_indexed定義由成塊的元素組成的類型，塊長度和偏移由參數(shù)指定MPI_Type_struct定義由不同數(shù)據(jù)類型的元素組成的類型MPI_Type_commit提交一個派生數(shù)據(jù)類型MPI_Type_free釋放一個派生數(shù)據(jù)類型2023/2/420現(xiàn)代密碼學理論與實踐之五4.3MPI消息(數(shù)據(jù)類型)doubleA[100];MPI_DatatypeEvenElements;···MPI_Type_vector(50,1,2,MPI_DOUBLE,&EvenElements);MPI_Type_commit(&EvenElements);MPI_Send(A,1,EvenElements,destination,···);首先聲明一個類型為MPI_Data_type的變量EvenElements調(diào)用構造函數(shù)MPI_Type_vector(count,blocklength,stride,oldtype,&newtype)來定義派生數(shù)據(jù)類型新的派生數(shù)據(jù)類型必須先調(diào)用函數(shù)MPI_Type_commit獲得MPI系統(tǒng)的確認后才能調(diào)用MPI_Send進行消息發(fā)送2023/2/421現(xiàn)代密碼學理論與實踐之五4.3MPI消息(數(shù)據(jù)類型)調(diào)用構造函數(shù)MPI_Type_vector(count,blocklength,stride,oldtype,&newtype)來定義派生數(shù)據(jù)類型。該newtype由count個數(shù)據(jù)塊組成。而每個數(shù)據(jù)塊由blocklength個oldtype類型的連續(xù)數(shù)據(jù)項組成。參數(shù)stride定義了兩個連續(xù)數(shù)據(jù)塊的起始位置之間的oldtype類型元素的個數(shù)。因此，兩個塊之間的間隔可以由(stride-blocklength)來表示。MPI_Type_vector(50,1,2,MPI_DOUBLE,&EvenElements)函數(shù)調(diào)用產(chǎn)生了派生數(shù)據(jù)類型EvenElements，它由50個塊組成，每個塊包含一個雙精度數(shù)，后跟一個(2－1)MPI_DOUBLE(8字節(jié))的間隔，接在后面的是下一塊。上面的發(fā)送語句獲取數(shù)組A的所有序號為偶數(shù)的元素并加以傳遞。2023/2/422現(xiàn)代密碼學理論與實踐之五4.3MPI消息(數(shù)據(jù)類型)MPI_Type_vector(count,blocklength,stride,oldtype,&newtype)oldtype……oldtypeblocklength……oldtypeblocklengthstride……oldtype……count2023/2/423現(xiàn)代密碼學理論與實踐之五4.3MPI消息(數(shù)據(jù)類型)01234567890123456789左圖10×10整數(shù)矩陣的所有偶序號的行:MPI_Type_vector(5,//count10,//blocklength20,//strideMPI_INT,//oldtype&newtype)2023/2/424現(xiàn)代密碼學理論與實踐之五4.3MPI消息(數(shù)據(jù)類型)MPI_Type_struct(count,//成員數(shù)array_of_blocklengths,//成員塊長度數(shù)組array_of_displacements,//成員偏移數(shù)組array_of_types,//成員類型數(shù)組newtype//新類型)

2023/2/425現(xiàn)代密碼學理論與實踐之五MPI_Type_structtype1type1type2type3type3type3structcount=3array_of_blocklengths={2,1,3}array_of_displacement={?,?,?}array_of_type={type1,type2,type3}2023/2/426現(xiàn)代密碼學理論與實踐之五type1type1type2type3type3type3structarray_of_displacement={?,?,?}MPI_Address(成員，偏移)2023/2/427現(xiàn)代密碼學理論與實踐之五4.3MPI消息(消息標簽)為什么需要消息標簽？當發(fā)送者連續(xù)發(fā)送兩個相同類型消息給同一個接收者，如果沒有消息標簽，接收者將無法區(qū)分這兩個消息這段代碼打算傳送A的前32個字節(jié)進入X，傳送B的前16個字節(jié)進入Y。但是，盡管消息B后發(fā)送，但可能先到達進程Q，就會被第一個接收函數(shù)接收在X中。使用標簽可以避免這個錯誤ProcessP:Send(A,32,Q)Send(B,16,Q)ProcessQ:recv(X,32,P)recv(Y,16,P)ProcessP:send(A,32,Q,tag1)send(B,16,Q,tag2)ProcessQ:recv(X,32,P,tag1)recv(Y,16,P,tag2)2023/2/428現(xiàn)代密碼學理論與實踐之五4.3MPI消息(消息標簽)添加標簽使得服務進程可以對兩個不同的用戶進程分別處理，提高靈活性2023/2/429現(xiàn)代密碼學理論與實踐之五4.3MPI消息(通信域)通信域(Communicator)包括進程組(ProcessGroup)和通信上下文(CommunicationContext)等內(nèi)容，用于描述通信進程間的通信關系。通信域分為組內(nèi)通信域和組間通信域，分別用來實現(xiàn)MPI的組內(nèi)通信(Intra-communication)和組間通信(Inter-communication)。2023/2/430現(xiàn)代密碼學理論與實踐之五4.3MPI消息(通信域)進程組是進程的有限、有序集。有限意味著，在一個進程組中，進程的個數(shù)n是有限的，這里的n稱為進程組大小(GroupSize)。有序意味著，進程的編號是按0，1，…，n-1排列的一個進程用它在一個通信域(組)中的編號進行標識。組的大小和進程編號可以通過調(diào)用以下的MPI函數(shù)獲得：MPI_Comm_size(communicator,&group_size)MPI_Comm_rank(communicator,&my_rank)

2023/2/431現(xiàn)代密碼學理論與實踐之五4.3MPI消息(通信域)通信上下文：安全的區(qū)別不同的通信以免相互干擾通信上下文不是顯式的對象，只是作為通信域的一部分出現(xiàn)進程組和通信上下文結合形成了通信域MPI_COMM_WORLD是所有進程的集合2023/2/432現(xiàn)代密碼學理論與實踐之五4.3MPI消息(通信域)MPI提供豐富的函數(shù)用于管理通信域函數(shù)名含義MPI_Comm_size獲取指定通信域中進程的個數(shù)MPI_Comm_rank獲取當前進程在指定通信域中的編號MPI_Comm_compare對給定的兩個通信域進行比較MPI_Comm_dup復制一個已有的通信域生成一個新的通信域，兩者除通信上下文不同外，其它都一樣。MPI_Comm_create根據(jù)給定的進程組創(chuàng)建一個新的通信域MPI_Comm_split從一個指定通信域分裂出多個子通信域，每個子通信域中的進程都是原通信域中的進程。MPI_Comm_free釋放一個通信域2023/2/433現(xiàn)代密碼學理論與實踐之五4.3MPI消息(通信域)一個在MPI中創(chuàng)建新通信域的例子MPI_CommMyWorld,SplitWorld;intmy_rank,group_size,Color,Key;MPI_Init(&argc,&argv);MPI_Comm_dup(MPI_COMM_WORLD,&MyWorld);MPI_Comm_rank(MyWorld,&my_rank);MPI_Comm_size(MyWorld,&group_size);Color=my_rank%3;Key=my_rank/3;MPI_Comm_split(MyWorld,Color,Key,&SplitWorld);2023/2/434現(xiàn)代密碼學理論與實踐之五4.3MPI消息(通信域)MPI_Comm_dup(MPI_COMM_WORLD,&MyWorld)創(chuàng)建了一個新的通信域MyWorld，它包含了與原通信域MPI_COMM_WORLD相同的進程組，但具有不同的通信上下文。MPI_Comm_split(MyWorld,Color,Key,&SplitWorld)函數(shù)調(diào)用則在通信域MyWorld的基礎上產(chǎn)生了幾個分割的子通信域。原通信域MyWorld中的進程按照不同的Color值處在不同的分割通信域中，每個進程在不同分割通信域中的進程編號則由Key值來標識。RankinMyWorld0123456789Color0120120120Key0001112223RankinSplitWorld(Color=0)0123RankinSplitWorld(Color=1)012RankinSplitWorld(Color=2)0122023/2/435現(xiàn)代密碼學理論與實踐之五4.3MPI消息(通信域)組間通信域是一種特殊的通信域，該通信域包括了兩個進程組，分屬于兩個進程組的進程之間通過組間通信域實現(xiàn)通信。一般把調(diào)用進程所在的進程組稱為本地進程組，而把另外一個稱為遠程進程組。函數(shù)名含義MPI_Comm_test_inter判斷給定的通信域是否為組間通信域MPI_Comm_remote_size獲取指定組間通信域中遠程進程組的大小MPI_Comm_remote_group返回給定組間通信域的遠程進程組MPI_Intercomm_creat根據(jù)給定的兩個組內(nèi)通信域生成一個組間通信域。MPI_Intercomm_merge將給定組間通信域包含的兩個進程組合并，形成一個新的組內(nèi)通信域2023/2/436現(xiàn)代密碼學理論與實踐之五4.3MPI消息(消息狀態(tài))消息狀態(tài)(MPI_Status類型)存放接收消息的狀態(tài)信息，包括: 消息的源進程標識－－MPI_SOURCE

消息標簽－－MPI_TAG

錯誤狀態(tài)－－MPI_ERROR 其他－－包括數(shù)據(jù)項個數(shù)等，但多為系統(tǒng)保留的。是消息接收函數(shù)MPI_Recv的最后一個參數(shù)。當一個接收者從不同進程接收不同大小和不同標簽的消息時，消息的狀態(tài)信息非常有用。2023/2/437現(xiàn)代密碼學理論與實踐之五4.3MPI消息(消息狀態(tài))假設多個客戶進程發(fā)送消息給服務進程請求服務，通過消息標簽來標識客戶進程，從而服務進程采取不同的服務while(true){MPI_Recv(received_request,100,MPI_BYTE,MPI_Any_source,MPI_Any_tag,comm,&Status);switch(Status.MPI_Tag){casetag_0:performservicetype0;casetag_1:performservicetype1;casetag_2:performservicetype2;}}2023/2/438現(xiàn)代密碼學理論與實踐之五4.4點對點通信MPI的點對點通信(‘Point-to-PointCommunication)同時提供了阻塞和非阻塞兩種通信機制。同時也支持多種通信模式。不同通信模式和不同通信機制的結合，便產(chǎn)生了非常豐富的點對點通信函數(shù)。2023/2/439現(xiàn)代密碼學理論與實踐之五4.4點對點通信(通信模式)通信模式(CommunicationMode)指的是緩沖管理，以及發(fā)送方和接收方之間的同步方式。共有下面四種通信模式同步(synchronous)通信模式緩沖(buffered)通信模式標準(standard)通信模式就緒(ready)通信模式2023/2/440現(xiàn)代密碼學理論與實踐之五4.4點對點通信(通信模式)同步通信模式：只有相應的接收過程已經(jīng)啟動，發(fā)送過程才正確返回。因此，同步發(fā)送返回后，表示發(fā)送緩沖區(qū)中的數(shù)據(jù)已經(jīng)全部被系統(tǒng)緩沖區(qū)緩存，并且已經(jīng)開始發(fā)送。當同步發(fā)送返回后，發(fā)送緩沖區(qū)可以被釋放或者重新使用。SRSynchronous1232023/2/441現(xiàn)代密碼學理論與實踐之五4.4點對點通信(通信模式)緩沖通信模式：緩沖通信模式的發(fā)送不管接收操作是否已經(jīng)啟動都可以執(zhí)行。但是需要用戶程序事先申請一塊足夠大的緩沖區(qū)，通過MPI_Buffer_attch實現(xiàn)，通過MPI_Buffer_detach來回收申請的緩沖區(qū)。SRBuffer122023/2/442現(xiàn)代密碼學理論與實踐之五4.4點對點通信(通信模式)標準通信模式：是否對發(fā)送的數(shù)據(jù)進行緩沖由MPI的實現(xiàn)來決定，而不是由用戶程序來控制。發(fā)送可以是同步的或緩沖的，取決于實現(xiàn)StandardSR12023/2/443現(xiàn)代密碼學理論與實踐之五4.4點對點通信(通信模式)就緒通信模式：發(fā)送操作只有在接收進程相應的接收操作已經(jīng)開始才進行發(fā)送。當發(fā)送操作啟動而相應的接收還沒有啟動，發(fā)送操作將出錯。就緒通信模式的特殊之處就是接收操作必須先于發(fā)送操作啟動。SRReady122023/2/444現(xiàn)代密碼學理論與實踐之五4.4點對點通信(通信模式)阻塞和非阻塞通信的主要區(qū)別在于返回后的資源可用性阻塞通信返回的條件：通信操作已經(jīng)完成，即消息已經(jīng)發(fā)送或接收調(diào)用的緩沖區(qū)可用。若是發(fā)送操作，則該緩沖區(qū)可以被其它的操作更新；若是接收操作，該緩沖區(qū)的數(shù)據(jù)已經(jīng)完整，可以被正確引用。2023/2/445現(xiàn)代密碼學理論與實踐之五4.4點對點通信(通信模式)MPI的發(fā)送操作支持四種通信模式，它們與阻塞屬性一起產(chǎn)生了MPI中的8種發(fā)送操作。而MPI的接收操作只有兩種：阻塞接收和非阻塞接收。非阻塞通信返回后并不意味著通信操作的完成，MPI還提供了對非阻塞通信完成的檢測，主要的有兩種：MPI_Wait函數(shù)和MPI_Test函數(shù)。2023/2/446現(xiàn)代密碼學理論與實踐之五4.4點對點通信(通信模式)MPI的點對點通信操作MPI原語阻塞非阻塞StandardSendMPI_SendMPI_IsendSynchronousSendMPI_SsendMPI_IssendBufferedSendMPI_BsendMPI_IbsendReadySendMPI_RsendMPI_IrsendReceiveMPI_RecvMPI_IrecvCompletionCheckMPI_WaitMPI_Test2023/2/447現(xiàn)代密碼學理論與實踐之五4.4點對點通信(通信模式)在阻塞通信的情況下，通信還沒有結束的時候，處理器只能等待，浪費了計算資源。一種常見的技術就是設法使計算與通信重疊，非阻塞通信可以用來實現(xiàn)這一目的。一條三進程的流水線，一個進程連續(xù)地從左邊的進程接收一個輸入數(shù)據(jù)流，計算一個新的值，然后將它發(fā)送給右邊的進程。while(Not_Done){MPI_Irevc(NextX,…);MPI_Isend(PreviousY,…);CurrentY=Q(CurrentX);}2023/2/448現(xiàn)代密碼學理論與實踐之五4.4點對點通信(通信模式)非阻塞通信中，雙緩沖是一種常用的方法。我們需要為X和Y各自準備兩個單獨的緩沖，當接收進程向緩沖中放下一個X時，計算進程可能從另一個緩沖中讀當前的X。我們需要確信緩沖中的數(shù)據(jù)在緩沖被更新之前使用。代碼如下while(Not_Done){if(X==Xbuf0){X=Xbuf1;Y=Ybuf1;Xin=Xbuf0;Yout=Ybuf0;}else{X=Xbuf0;Y=Ybuf0;Xin=Xbuf1;Yout=Ybuf1;}MPI_Irevc(Xin,…,recv_handle);MPI_Isend(Yout,…,send_handle);Y=Q(X);/*重疊計算*/MPI_Wait(recv_handle,recv_status);MPI_Wait(send_handle,send_status);}2023/2/449現(xiàn)代密碼學理論與實踐之五4.4點對點通信(通信模式)send_handle和revc_handle分別用于檢查發(fā)送接收是否完成。檢查發(fā)送接收通過調(diào)用MPI_Wait(Handle,Status)來實現(xiàn)，它直到Handle指示的發(fā)送或接收操作已經(jīng)完成才返回。另一個函數(shù)MPI_Test(Handle,Flag,Status)只測試由Handle指示的發(fā)送或接收操作是否完成，如果完成，就對Flag賦值True，這個函數(shù)不像MPI_Wait，它不會被阻塞。2023/2/450現(xiàn)代密碼學理論與實踐之五4.4點對點通信－Send-Recv給一個進程發(fā)送消息，從另一個進程接收消息；特別適用于在進程鏈（環(huán)）中進行“移位”操作，而避免在通訊為阻塞方式時出現(xiàn)死鎖。MPI_Sendrecv(sendbuf,sendcount,sendtype,dest,sendtag,//以上為消息發(fā)送的描述recvbuf,recvcount,recvtype,source,recvtag,//以上為消息接收的描述comm,status)

2023/2/451現(xiàn)代密碼學理論與實踐之五4.5

群集通信群集通信(CollectiveCommunications)是一個進程組中的所有進程都參加的全局通信操作。群集通信一般實現(xiàn)三個功能：通信、聚集和同步。通信功能主要完成組內(nèi)數(shù)據(jù)的傳輸聚集功能在通信的基礎上對給定的數(shù)據(jù)完成一定的操作同步功能實現(xiàn)組內(nèi)所有進程在執(zhí)行進度上取得一致2023/2/452現(xiàn)代密碼學理論與實踐之五4.5

群集通信群集通信，按照通信方向的不同，又可以分為三種：一對多通信，多對一通信和多對多通信。一對多通信：一個進程向其它所有的進程發(fā)送消息，這個負責發(fā)送消息的進程叫做Root進程。多對一通信：一個進程負責從其它所有的進程接收消息，這個接收的進程也叫做Root進程。多對多通信：每一個進程都向其它所有的進程發(fā)送或者接收消息。2023/2/453現(xiàn)代密碼學理論與實踐之五4.5

群集通信類型函數(shù)名含義通信MPI_Bcast一對多廣播同樣的消息MPI_Gather多對一收集各個進程的消息MPI_GathervMPI_Gather的一般化MPI_Allgather全局收集MPI_AllgathervMPI_Allgather的一般化MPI_Scatter一對多散播不同的消息MPI_ScattervMPI_Scatter的一般化MPI_Alltoall多對多全局交換消息MPI_AlltoallvMPI_Alltoall的一般化聚集MPI_Reduce多對一歸約MPI_AllreduceMPI_Reduce的一般化MPI_Reduce_scatterMPI_Reduce的一般化MPI_Scan掃描同步MPI_Barrier路障同步2023/2/454現(xiàn)代密碼學理論與實踐之五4.5

群集通信廣播是一對多通信的典型例子，其調(diào)用格式如下：MPI_Bcast(Address,Count,Datatype,Root,Comm)2023/2/455現(xiàn)代密碼學理論與實踐之五4.5

群集通信廣播的特點

標號為Root的進程發(fā)送相同的消息給通信域Comm中的所有進程。消息的內(nèi)容如同點對點通信一樣由三元組<Address,Count,Datatype>標識。對Root進程來說，這個三元組既定義了發(fā)送緩沖也定義了接收緩沖。對其它進程來說，這個三元組只定義了接收緩沖2023/2/456現(xiàn)代密碼學理論與實踐之五4.5

群集通信收集是多對一通信的典型例子，其調(diào)用格式下:MPI_Gather(SendAddress,SendCount,SendDatatype, RecvAddress,RecvCount,RecvDatatype,Root,Comm)2023/2/457現(xiàn)代密碼學理論與實踐之五4.5

群集通信收集的特點在收集操作中，Root進程從進程域Comm的所有進程(包括它自已)接收消息。這n個消息按照進程的標識rank排序進行拼接，然后存放在Root進程的接收緩沖中。接收緩沖由三元組<RecvAddress,RecvCount,RecvDatatype>標識，發(fā)送緩沖由三元組<SendAddress,SendCount,SendDatatype>標識，所有非Root進程忽略接收緩沖。2023/2/458現(xiàn)代密碼學理論與實踐之五4.5

群集通信散播也是一個一對多操作，其調(diào)用格式如下:MPI_Scatter(SendAddress,SendCount,SendDatatype, RecvAddress,RecvCount,RecvDatatype,Root,Comm)2023/2/459現(xiàn)代密碼學理論與實踐之五4.5

群集通信散播的特點Scatter執(zhí)行與Gather相反的操作。Root進程給所有進程(包括它自已)發(fā)送一個不同的消息，這n(n為進程域comm包括的進程個數(shù))個消息在Root進程的發(fā)送緩沖區(qū)中按進程標識的順序有序地存放。每個接收緩沖由三元組<RecvAddress,RecvCount,RecvDatatype>標識，所有的非Root進程忽略發(fā)送緩沖。對Root進程，發(fā)送緩沖由三元組<SendAddress,SendCount,SendDatatype>標識。2023/2/460現(xiàn)代密碼學理論與實踐之五4.5

群集通信全局收集多對多通信的典型例子，其調(diào)用格式如下：MPI_Allgather(SendAddress,SendCount,SendDatatype, RecvAddress,RecvCount,RecvDatatype,Comm)Allgather操作相當于每個進程都作為ROOT進程執(zhí)行了一次Gather調(diào)用，即每一個進程都按照Gather的方式收集來自所有進程(包括自己)的數(shù)據(jù)。2023/2/461現(xiàn)代密碼學理論與實踐之五4.5

群集通信全局交換也是一個多對多操作，其調(diào)用格式如下:MPI_Alltoall(SendAddress,SendCount,SendDatatype, RecvAddress,RecvCount,RecvDatatype,Comm)2023/2/462現(xiàn)代密碼學理論與實踐之五4.5

群集通信全局交換的特點在全局交換中，每個進程發(fā)送一個消息給所有進程(包括它自已)。這n(n為進程域comm包括的進程個數(shù))個消息在它的發(fā)送緩沖中以進程標識的順序有序地存放。從另一個角度來看這個通信，每個進程都從所有進程接收一個消息，這n個消息以標號的順序被連接起來，存放在接收緩沖中。全局交換等價于每個進程作為Root進程執(zhí)行了一次散播操作。2023/2/463現(xiàn)代密碼學理論與實踐之五4.5

群集通信同步功能用來協(xié)調(diào)各個進程之間的進度和步伐。目前MPI的實現(xiàn)中支持一個同步操作，即路障同步(Barrier)。路障同步的調(diào)用格式如下:MPI_Barrier(Comm)在路障同步操作MPI_Barrier(Comm)中，通信域Comm中的所有進程相互同步。在該操作調(diào)用返回后，可以保證組內(nèi)所有的進程都已經(jīng)執(zhí)行完了調(diào)用之前的所有操作，可以開始該調(diào)用后的操作。2023/2/464現(xiàn)代密碼學理論與實踐之五4.5

群集通信群集通信的聚合功能使得MPI進行通信的同時完成一定的計算。MPI聚合的功能分三步實現(xiàn)首先是通信的功能，即消息根據(jù)要求發(fā)送到目標進程，目標進程也已經(jīng)收到了各自需要的消息；然后是對消息的處理，即執(zhí)行計算功能；最后把處理結果放入指定的接收緩沖區(qū)。MPI提供了兩種類型的聚合操作:歸約和掃描。2023/2/465現(xiàn)代密碼學理論與實踐之五4.5

群集通信歸約的調(diào)用格式如下:MPI_Reduce(SendAddress,RecvAddress,Count, Datatype,Op,Root,Comm)歸約的特點歸約操作對每個進程的發(fā)送緩沖區(qū)(SendAddress)中的數(shù)據(jù)按給定的操作進行運算，并將最終結果存放在Root進程的接收緩沖區(qū)(RecvAddress)中。參與計算操作的數(shù)據(jù)項的數(shù)據(jù)類型在Datatype域中定義，歸約操作由Op域定義。歸約操作可以是MPI預定義的,也可以是用戶自定義的。歸約操作允許每個進程貢獻向量值，而不只是標量值，向量的長度由Count定義。2023/2/466現(xiàn)代密碼學理論與實踐之五4.5

群集通信MPI_Reduce:root＝0，Op＝MPI_SUMMPI_Allreduce:Op＝MPI_SUM歸約前的發(fā)送緩沖區(qū)A0A1A2B0B1B2C0C1C2P0:P1:P2:2023/2/467現(xiàn)代密碼學理論與實踐之五4.5

群集通信MPI_Reduce:root＝P0，Op＝MPI_SUM歸約后的接收緩沖區(qū)A0+B0+C0A1+B1+C1A2+B2+C2

P0:P1:P2:2023/2/468現(xiàn)代密碼學理論與實踐之五4.5

群集通信MPI_Allreduce:Op＝MPI_SUM歸約后的接收緩沖區(qū)A0+B0+C0A1+B1+C1A2+B2+C2P0:A0+B0+C0A1+B1+C1A2+B2+C2P1:A0+B0+C0A1+B1+C1A2+B2+C2P2:2023/2/469現(xiàn)代密碼學理論與實踐之五4.5

群集通信MPI預定義的歸約操作操作含義操作含義MPI_MAX最大值MPI_LOR邏輯或MPI_MIN最小值MPI_BOR按位或MPI_SUM求和MPI_LXOR邏輯異或MPI_PROD求積MPI_BXOR按位異或MPI_LAND邏輯與MPI_MAXLOC最大值且相應位置MPI_BAND按位與MPI_MINLOC最小值且相應位置2023/2/470現(xiàn)代密碼學理論與實踐之五4.5

群集通信用戶自定義的歸約操作intMPI_Op_create( //用戶自定義歸約函數(shù)

MPI_User_function*function,//if(commute==true)Op是可交換且可結合//else按進程號升序進行Op操作

intcommute,MPI_Op*op)2023/2/471現(xiàn)代密碼學理論與實踐之五4.5

群集通信用戶自定義的歸約操作函數(shù)須有如下形式：typedefvoidMPI_User_function(void*invec,void*inoutvec,int*len,//從MPI_Reduce調(diào)用中傳入的countMPI_Datatype*datatype);函數(shù)語義如下：for(i=0;i<*len;i++){*inoutvec=*invecUSER_OP*inouvec;inoutvec++;invec++;}2023/2/472現(xiàn)代密碼學理論與實踐之五4.5

群集通信用戶自定義歸約示例：（1）復數(shù)乘法typedefstruct{doublereal,imag;}Complex;/*theuser-definedfunction*/voidmyProd(Complex*in,Complex*inout,int*len,MPI_Datatype*dptr){inti;Complexc;

for(i=0;i<*len;++i){

c.real=inout->real*in->real-inout->imag*in->imag;c.imag=inout->real*in->imag+inout->imag*in->real;*inout=c;

in++;inout++;}

2023/2/473現(xiàn)代密碼學理論與實踐之五4.5

群集通信用戶自定義歸約示例：（1）復數(shù)乘法/*explaintoMPIhowtypeComplexisdefined*/MPI_Type_contiguous(2,MPI_DOUBLE,&ctype);MPI_Type_commit(&ctype);/*createthecomplex-productuser-op*/MPI_Op_create(myProd,1,&myOp);MPI_Reduce(a,answer,LEN,ctype,myOp,0,MPI_COMM_WORLD);2023/2/474現(xiàn)代密碼學理論與實踐之五4.5

群集通信用戶自定義歸約示例：（2）矩陣“乘法”(c[i][j]==a[i][j]*b[i][j])voidmyProd(double*in,double*inout,int*len,MPI_Datatype*dptr){inti,j;for(i=0;i<*len;++i)for(j=0;j<LEN*LEN;j++){*inout=(*inout)*(*in);in++;inout++;}}2023/2/475現(xiàn)代密碼學理論與實踐之五4.5

群集通信用戶自定義歸約示例：（2）矩陣“乘法”MPI_Type_contiguous(LEN*LEN,MPI_DOUBLE,&ctype);MPI_Type_commit(&ctype);

/*createthesumofmatrixuser-op*/MPI_Op_create(myProd,1,&myOp);MPI_Reduce(a,answer,1,ctype,myOp,0,MPI_COMM