并行程序設(shè)計(jì)

并行算法實(shí)踐上篇并行程序設(shè)計(jì)導(dǎo)論2023/2/41現(xiàn)代密碼學(xué)理論與實(shí)踐之五并行算法實(shí)踐

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

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

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

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

消息標(biāo)簽－－MPI_TAG

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

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

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

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

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

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

群集通信廣播的特點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

MPI_User_function*function,//if(commute==true)Op是可交換且可結(jié)合//else按進(jìn)程號(hào)升序進(jìn)行Op操作

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

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

群集通信用戶自定義歸約示例：（1）復(fù)數(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)代密碼學(xué)理論與實(shí)踐之五4.5

群集通信用戶自定義歸約示例：（1）復(fù)數(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)代密碼學(xué)理論與實(shí)踐之五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)代密碼學(xué)理論與實(shí)踐之五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