lecnote10mpi并行程序開發(fā)基礎(chǔ)

lecnote10mpi并行程序開發(fā)基礎(chǔ)分布式計(jì)算的概念廣義地說，任何一個(gè)基于網(wǎng)絡(luò)技術(shù)(包括廣域網(wǎng)絡(luò)和局域網(wǎng)絡(luò))的計(jì)算都稱為分布式的計(jì)算。大體上可劃分成四種類型狹義的分布式計(jì)算。傳統(tǒng)意義上講，分布式計(jì)算是在局域網(wǎng)絡(luò)環(huán)境上開展的計(jì)算活動(dòng)網(wǎng)絡(luò)環(huán)境穩(wěn)定：計(jì)算機(jī)的數(shù)量、每臺(tái)計(jì)算機(jī)的功能和性能都是確定的異構(gòu)性：每臺(tái)計(jì)算機(jī)可以具有不同的計(jì)算功能和性能。例如，一臺(tái)計(jì)算機(jī)是數(shù)據(jù)庫服務(wù)器、一臺(tái)計(jì)算機(jī)是圖形工作站、五臺(tái)機(jī)器是高性能計(jì)算工作站編寫程序時(shí)，為每個(gè)子任務(wù)明確指定計(jì)算機(jī)P2P計(jì)算:關(guān)注的重點(diǎn)是數(shù)據(jù)的存儲(chǔ)與訪問(多數(shù)情況下)網(wǎng)絡(luò)環(huán)境是動(dòng)態(tài)的：計(jì)算機(jī)隨時(shí)可能加入、退出自治性：每臺(tái)計(jì)算機(jī)都能感知其他機(jī)器的加入、退出，具備獨(dú)立的計(jì)算能力同構(gòu)性：每臺(tái)計(jì)算機(jī)在計(jì)算功能方面可以認(rèn)為是相同的實(shí)際的計(jì)算機(jī)一般是異構(gòu)的，CPU、擁有的內(nèi)存、甚至OS都是不同的站在P2P應(yīng)用(例如BT)的角度看，這些機(jī)器是同構(gòu)的計(jì)算模式：計(jì)算機(jī)在求解問題P時(shí)，向周圍的“鄰居”請求，幫助完成子任務(wù)Ti至今為止，主要用于數(shù)據(jù)密集型應(yīng)用：文件下載、在線視頻播放、……實(shí)例：下載軟件BT并行計(jì)算:更側(cè)重于求解程序的行為特征,以提高性能為主要目標(biāo)網(wǎng)絡(luò)環(huán)境是局域、專用、穩(wěn)定、高效的計(jì)算機(jī)之間是同構(gòu)的：性能、功能計(jì)算模式：計(jì)算機(jī)在求解問題P時(shí)，子任務(wù)Ti在任何機(jī)器上都能完成，具體的分配取決于并行算法主要用在科學(xué)工程計(jì)算領(lǐng)域。在非科學(xué)工程領(lǐng)域，例如銀行和圖書館等領(lǐng)域要求數(shù)據(jù)庫支持大規(guī)模并發(fā)用戶，并行計(jì)算更關(guān)注于SMP這樣的平臺(tái)網(wǎng)格計(jì)算/云計(jì)算(網(wǎng)格:電力網(wǎng);云:用云代表互聯(lián)網(wǎng)):以網(wǎng)絡(luò)環(huán)境為基礎(chǔ)的計(jì)算,以降低成本為主要目標(biāo)網(wǎng)絡(luò)環(huán)境是動(dòng)態(tài)、異構(gòu)、低效的基于廣域網(wǎng)絡(luò)計(jì)算模式：計(jì)算機(jī)在求解問題P時(shí)，子任務(wù)Ti在其中某臺(tái)、或某幾臺(tái)機(jī)器上都能完成，具體的分配取決于網(wǎng)格計(jì)算支撐中間件在今天，網(wǎng)格計(jì)算的概念還不清晰，幾乎所有基于網(wǎng)絡(luò)的計(jì)算都扯上網(wǎng)格。但在網(wǎng)格技術(shù)的最初階段，一般指科學(xué)工廠領(lǐng)域的高性能計(jì)算云計(jì)算是近年興起的概念,主要是商業(yè)公司在熱捧，特別是被網(wǎng)絡(luò)搜索公司熱捧。目前有一些成功的案例，主要是以數(shù)據(jù)為導(dǎo)向的REDUCTION類計(jì)算網(wǎng)絡(luò)環(huán)境的傳輸效率：網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)膸捙c處理器數(shù)據(jù)處理速度的比重溫multi-computer的概念是一個(gè)關(guān)于并行計(jì)算機(jī)模型的概念由多臺(tái)VonNeumann計(jì)算機(jī)共同承擔(dān)計(jì)算任務(wù)。每臺(tái)VonNeumann有一顆處理器/執(zhí)行內(nèi)核P和一塊局部存儲(chǔ)空間MP只能訪問M中的數(shù)據(jù)計(jì)算任務(wù)的數(shù)據(jù)由各VonNeumann的局部存儲(chǔ)空間共同存儲(chǔ)各個(gè)VonNeumann之間通過網(wǎng)絡(luò)交換各自局部存儲(chǔ)空間的數(shù)據(jù)是并行程序開發(fā)人員眼中的并行計(jì)算機(jī)，與實(shí)際的計(jì)算機(jī)體系結(jié)構(gòu)有可能不一致可以同時(shí)執(zhí)行多個(gè)進(jìn)程每個(gè)進(jìn)程只能訪問自己存儲(chǔ)空間中的數(shù)據(jù)進(jìn)程之間可以通過“網(wǎng)絡(luò)”的消息傳遞，交換各自存儲(chǔ)空間中的數(shù)據(jù)同一個(gè)OS支撐的進(jìn)程之間：SOCKET/CHANNEL不同OS支撐的進(jìn)程之間：SOCKET并行程序的結(jié)構(gòu)可以是SPMD的、也可以是MPMD的并行計(jì)算機(jī)的行為一般是MIMD的現(xiàn)實(shí)中multi-computer的例子集群MPP站在編程的角度看，所謂multi-computer上的并行程序開發(fā)，就是進(jìn)程并行程序設(shè)計(jì)一臺(tái)VonNeumann計(jì)算機(jī)：一個(gè)進(jìn)程并行算法實(shí)現(xiàn)面臨的關(guān)鍵問題包括：這個(gè)并行程序運(yùn)行過程中，共有哪些進(jìn)程進(jìn)程相互之間如何識(shí)別進(jìn)程之間如何交換消息消息可以是算法運(yùn)行邏輯的進(jìn)度信號(hào)、控制轉(zhuǎn)移條件信號(hào)消息可以是被算法處理的部分?jǐn)?shù)據(jù)但是，multi-computer與CELL處理器又有類似之處：VonNeumann計(jì)算機(jī)VSSPESPU只能訪問LS的數(shù)據(jù)SPU執(zhí)行MFC實(shí)現(xiàn)LS之間的數(shù)據(jù)交換但SPE不具備VonNeumann計(jì)算機(jī)的一些重要能力SPE的存儲(chǔ)空間有限：256KBSPE不能夠獨(dú)立執(zhí)行計(jì)算任務(wù)，不運(yùn)行OS、依靠PPEMPI是什么MPI：MessagePassingInterface,aninterfacespecificationforprogrammingdistributedmemorysystem，consistingofacollectionofroutinesforfacilitatingcommunication(exchangeofdataandsynchronizationoftasks)amongtheprocessorsinadistributedmemoryparallelprogram.Distributedmemorysystem(分布式存儲(chǔ)的并行計(jì)算系統(tǒng))：一種并行計(jì)算系統(tǒng)有多個(gè)CPU每個(gè)CPU都有自己能夠直接訪問的局部內(nèi)存；并且只能夠訪問自己局部內(nèi)存的數(shù)據(jù)CPU之間可以通過網(wǎng)絡(luò)交換局部內(nèi)存的數(shù)據(jù)例如BEOWULF、MPPMPI在并行程序開發(fā)中扮演的角色為實(shí)現(xiàn)并行算法提供一個(gè)MPI_COMM_WORLD：在程序中表達(dá)并行計(jì)算機(jī)(串行程序不需要表達(dá)計(jì)算機(jī)，缺省都是VonNeumann計(jì)算機(jī))，支持子任務(wù)到計(jì)算資源的映射由一組processor組成，每個(gè)processor上運(yùn)行一個(gè)進(jìn)程這些processor從0開始順序編號(hào)每個(gè)processor映射到一臺(tái)physicalcomputer上，不同的processor可以映射到相同的physicalcomputer上實(shí)現(xiàn)processor之間的消息交換一個(gè)C語言的MPI程序示例Programgreeting#include<stdio.h>#include“mpi.h”Main(intargc,char**argv){Intmy_rank;Intp;Intsource;Intdest;Inttag=50;Charmessage[100];MPI_Statusstatus;MPI_init(&argc,&argv);MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);MPI_Comm_size(MPI_COMM_WORLD,&p);If(my_rank!=0){Sprintf(message,“greetingsfromprocess%d!”,my_rank);Dest=0;MPI_Send(message,strlen(message)+1,MPI_CHAR,dest,tag,MPI_COMM_WORLD);}else{For(source=1;source<p;source++){MPI_Recv(message,100,MPI_CHAR,source,tag,MPI_COMM_WORLD,&status);Printf(“%s\n”,message);}}MPI_Finalize();}在四個(gè)處理器上的運(yùn)行結(jié)果greetingsfromprocess1greetingsfromprocess2greetingsfromprocess3在不同的并行計(jì)算系統(tǒng)上，編譯運(yùn)行上述程序的方法各不相同，以MPICH為例編譯連接：mpicc–ogreetinggreeting.c運(yùn)行：mpirun–np4greeting在四個(gè)處理器上執(zhí)行并行程序greeting具體的計(jì)算機(jī)由運(yùn)行環(huán)境設(shè)置machinelist決定machinelist中所列計(jì)算機(jī)的數(shù)量M

4：取前4臺(tái)計(jì)算機(jī)，依次運(yùn)行進(jìn)程0、1、2、3machinelist中所列計(jì)算機(jī)的數(shù)量M

4，比如M=3：三臺(tái)計(jì)算機(jī)上依次運(yùn)行進(jìn)程0、1、2，第3個(gè)進(jìn)程被分配給第1臺(tái)計(jì)算機(jī)MPI程序是如何運(yùn)行的？OSSHELL:mpirun，使用OS命令啟動(dòng)并行的進(jìn)程，根據(jù)不同的運(yùn)行環(huán)境，具體的命令和運(yùn)行參數(shù)不同。以MPICH和CLUSTER為例在執(zhí)行mpirun之前，首先把可執(zhí)行程序greeting拷貝到各個(gè)節(jié)點(diǎn)上，greeting在各個(gè)節(jié)點(diǎn)上的存儲(chǔ)路徑相同，(如果各節(jié)點(diǎn)的可執(zhí)行代碼不同，如一個(gè)節(jié)點(diǎn)運(yùn)行Linux，另一個(gè)運(yùn)行SCOUNIX，則需要分別為這兩個(gè)操作系統(tǒng)編譯greeting的可執(zhí)行代碼)mpirun完成下列工作根據(jù)-np參數(shù)確定需要運(yùn)行多少進(jìn)程根據(jù)環(huán)境中的machinelist確定每個(gè)進(jìn)程所在的節(jié)點(diǎn)，machinelist記錄了cluster中的各個(gè)節(jié)點(diǎn)在啟動(dòng)mpirun的節(jié)點(diǎn)上，直接運(yùn)行g(shù)reeting，啟動(dòng)本地的進(jìn)程在其它節(jié)點(diǎn)上，則使用rsh或其他異地程序啟動(dòng)命令(例如SSH)，啟動(dòng)異地進(jìn)程MPI_init()：啟動(dòng)MPI的支持對進(jìn)程進(jìn)行編號(hào)0,1,…,N-1初始化通信子(communicator)MPI_COMM_WORLD：表示并行程序、及其全部進(jìn)程，每個(gè)進(jìn)程有一個(gè)唯一的標(biāo)號(hào)，從０開始編號(hào)MPI程序運(yùn)行時(shí)，需要一組進(jìn)程。OS在創(chuàng)建一個(gè)進(jìn)程時(shí)，自動(dòng)分配一個(gè)PIDMPI程序中每個(gè)進(jìn)程的標(biāo)識(shí)：執(zhí)行進(jìn)程的節(jié)點(diǎn)＋進(jìn)程在該節(jié)點(diǎn)上的進(jìn)程號(hào)MPI_Comm_rank(MPI_Commcomm,intrank)：查詢當(dāng)前進(jìn)程在通信子comm中編號(hào)，供進(jìn)程在執(zhí)行過程中識(shí)別自己MPI_Comm_size(MPI_Commcomm,intsize)：查詢在整個(gè)通信子comm中的進(jìn)程數(shù)量MPI_Send(void*buff,intcount,MPI_Datatypedatatype,intdest,inttag,MPI_Commcomm)從當(dāng)前進(jìn)程發(fā)送消息messagemessage=data+envelopedata:存儲(chǔ)在buff起始的一個(gè)緩沖區(qū)中，共有count個(gè)元素，每個(gè)元素的類型是datatypeenvelop:把消息發(fā)送到comm中的第dest號(hào)進(jìn)程，消息的標(biāo)簽是tag要求：當(dāng)前進(jìn)程也是通信子comm中的一個(gè)進(jìn)程１２…count…buff…一個(gè)類型為datatype的元素MPI_Recv(void*buff,intcount,MPI_Datatypedatatype,intsource,inttag,MPI_Commcomm,MPI_Status*status)接收一條消息messagemessage是從comm中的第source號(hào)進(jìn)程發(fā)送來的，且其標(biāo)簽為tag把message中的數(shù)據(jù)存儲(chǔ)在從buff起始的一個(gè)緩沖區(qū)中，緩沖區(qū)的長度為count，緩沖區(qū)元素的類型是datatype要求：當(dāng)前進(jìn)程也是通信子comm中的一個(gè)進(jìn)程實(shí)際所接收消息中的數(shù)據(jù)元素的數(shù)量可以比count少status中記錄消息處理的結(jié)果，包括：實(shí)際接收的數(shù)據(jù)元素的數(shù)量、消息的發(fā)送者、消息通信異常時(shí)的異常代碼MPI_Finalize():結(jié)束MPI的計(jì)算支持MPI_CHAR：描述被傳遞數(shù)據(jù)的類型，目的是解決異構(gòu)計(jì)算節(jié)點(diǎn)之間的數(shù)據(jù)交換。以int型數(shù)據(jù)為例：有的編譯系統(tǒng)以16bit表示、有的以32bit表示對于以16bit表示的int，有些OS在內(nèi)存中把高位放在第一個(gè)byte，另一些則把低位放在第一個(gè)byte高位低位被發(fā)送的整數(shù)MPI_INT數(shù)據(jù)打包MPI程序運(yùn)行示意圖MPI_sendMPI_recvSend-runrecv-run處理器I處理器J并行程序代碼MPI運(yùn)行庫代碼低位高位被接收的整數(shù)MPI_INT數(shù)據(jù)解包數(shù)據(jù)傳輸基本數(shù)據(jù)類型(MPIbasicdatatype)C語言MPI_CHAR,MPI_UNSIGNED_CHARMPI_SHORT,MPI_INT,MPI_LONG,MPI_UNSIGNED_SHORT,MPI_UNSIGNED,MPI_UNSIGNED_LONG,MPI_FLOAT,MPI_DOUBLE,MPI_LONG_DOUBLEMPI_BYTEMPI_PACKEDFortran語言MPI_INTEGERMPI_REAL,MPI_DOUBLE_PRECISIONMPI_COMPLEX,MPI_LOGICALMPI_CHARACTERMPI_BYTEMPI_PACKED消息的識(shí)別從用戶進(jìn)程的角度看，三員組(source,dest,tag)可以唯一標(biāo)識(shí)一條消息MPI_send：souce是執(zhí)行該調(diào)用的當(dāng)前進(jìn)程，發(fā)送參數(shù)包含了dest和tagMPI_recv：dest是執(zhí)行該調(diào)用的當(dāng)前進(jìn)程，接收參數(shù)包含了souce和tagMPI運(yùn)行庫除了實(shí)現(xiàn)應(yīng)用程序中的消息傳遞之外，自己還會(huì)產(chǎn)生一些消息傳遞，通過communicator，可以把應(yīng)用程序進(jìn)程的消息與MPI運(yùn)行庫自身的消息區(qū)別開來有利于模塊化的程序開發(fā)：把函數(shù)庫中的消息與主程序中的消息分開(后面的課程中將具體介紹)為了簡化編程，應(yīng)用程序中可以定義MPI_COMM_WORLD之外的通信子，同一個(gè)進(jìn)程，在不同通信子中的編號(hào)可能不同(后面的課程中將具體介紹)sendrecvSend-run1recv-run1處理器I處理器J并行程序代碼MPI運(yùn)行庫代碼Usermessage(I,J,tag,comm_user)Usermessage(I,J,tag,comm_user)Send-run2recv-run2MPIRUN-TIMEmessage(I,J,tag,comm_run)系統(tǒng)規(guī)定每次發(fā)送最多128KB，send語句要發(fā)送496KBmsg1:要進(jìn)行一次數(shù)據(jù)傳輸，共有4個(gè)數(shù)據(jù)包msg2~msg5:分別傳輸一部分?jǐn)?shù)據(jù)包序號(hào)源標(biāo)簽通信子1數(shù)據(jù)MPI_Comm_size、MPI_Comm_rank考慮問題：矩陣加C=A+B，A、B、C都是大小為nn的矩陣。并行計(jì)算時(shí)，希望每個(gè)處理器分別做一個(gè)矩陣片段的加法運(yùn)算m個(gè)處理器，為了達(dá)到提高計(jì)算效率的目的，我們希望在各個(gè)處理器之間均分計(jì)算任務(wù)MPI并行程序運(yùn)行時(shí)使用的處理器數(shù)量m是由輸入?yún)?shù)確定的，因此需要根據(jù)輸入?yún)?shù)計(jì)算每個(gè)處理器分別負(fù)責(zé)多大片段的計(jì)算、該片段的起始下標(biāo)Load-balanceScalability：m越大，每個(gè)處理器上的計(jì)算任務(wù)就越少M(fèi)PI_Comm_size：用來動(dòng)態(tài)確定每個(gè)處理器所負(fù)責(zé)子任務(wù)的大小需要存儲(chǔ)多大規(guī)模的數(shù)據(jù)需要執(zhí)行的運(yùn)算量：迭代空間的大小MPI_Comm_rank：用來動(dòng)態(tài)確定每個(gè)處理器具體負(fù)責(zé)的任務(wù)具體存儲(chǔ)的問題數(shù)據(jù)：數(shù)組下標(biāo)的范圍執(zhí)行的數(shù)據(jù)運(yùn)算：迭代空間的范圍、或者執(zhí)行的代碼程序示例MPI并行程序的結(jié)構(gòu)MPI_init(&argc,&argv);MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);//執(zhí)行第my_rank個(gè)子任務(wù)的局部計(jì)算，包括依據(jù)my_rank判斷分配到當(dāng)前進(jìn)程上的子任務(wù){(diào)//執(zhí)行初始輸入數(shù)據(jù)的分發(fā)If(my_rank==0){

…}else{…}…MPI_send(…)…MPI_recv(…)…//執(zhí)行計(jì)算結(jié)果的收集If(my_rank==0){…}else{…}}MPI_Finalize()每個(gè)進(jìn)程中只在開始執(zhí)行MPI操作前執(zhí)行一次MPI_init只在完成MPI操作后，執(zhí)行一次MPI_finalize()可以執(zhí)行任意多次的MPI_send()，但對每個(gè)MPI_send()，都需要在其他某個(gè)進(jìn)程中有對應(yīng)的MPI_recv()可以執(zhí)行任意多次的MPI_recv()，但對每個(gè)MPI_recv()，都需要在其他某個(gè)進(jìn)程中有對應(yīng)的MPI_send()MPI的作用提供了表示MAPPING(從計(jì)算任務(wù)到處理器的映射)的方法用MPI_COMM_WORLD表示一個(gè)并行程序的全部進(jìn)程，為每個(gè)進(jìn)程分配一個(gè)唯一的標(biāo)號(hào)RANK每個(gè)進(jìn)程執(zhí)行一個(gè)串行的程序代碼，使用MPI_Comm_rank()識(shí)別自己由進(jìn)程在執(zhí)行過程中根據(jù)標(biāo)號(hào)RANK確定自己的局部任務(wù)提供了子任務(wù)之間交換數(shù)據(jù)的機(jī)制用消息實(shí)現(xiàn)子任務(wù)之間的數(shù)據(jù)交換，每條消息包括兩部分?jǐn)?shù)據(jù)部分：存儲(chǔ)空間的地址buffer、存儲(chǔ)空間中元素的數(shù)量count和存儲(chǔ)空間中元素的類型datatype封裝部分：消息的發(fā)送者source、消息的接收者dest、消息發(fā)送者和接收者所在的通信子comm、消息的標(biāo)簽tag使用MPI_send()發(fā)送消息使用MPI_recv()接收消息MPI的組成MPI共包括129個(gè)調(diào)用其中六個(gè)基本的調(diào)用MPI_init()MPI_Comm_rank()MPI_Comm_size()MPI_send()MPI_recv()MPI_finalize()實(shí)際上，任何MPI程序都可以用這六條基本語句實(shí)現(xiàn)MPI提供了C語言和Fortran語言的接口MPI：SPMD、MIMD采用MPI開發(fā)并行程序時(shí)，一般采用SPMD的形式表示并行程序MPI并行程序運(yùn)行時(shí)，行為的特征通常表現(xiàn)為MIMD并行程序開發(fā)Parallelprogramming:theactivityofconstructingaparallelprogramfromagivenalgorithm并行處理目標(biāo)：提高處理問題規(guī)模和速度措施：進(jìn)行計(jì)算任務(wù)分解，把一個(gè)復(fù)雜的問題劃分成一組相對簡單的并發(fā)子問題，分別由不同的部件并行執(zhí)行三種并行程序POSIX線程并行程序：基于Cache的多核處理器、SMPCELLBE線程并行程序：CELLBE處理器MPI并行程序：進(jìn)程并行程序集群、MPP基于Cache的多核處理器、SMP：現(xiàn)代的OS都支持多個(gè)用戶進(jìn)程，每個(gè)處理器執(zhí)行內(nèi)核上運(yùn)行一個(gè)進(jìn)程與串行程序開發(fā)相比，并行程序開發(fā)增加了并行算法設(shè)計(jì)：把一個(gè)復(fù)雜的計(jì)算問題劃分成一組相對簡單的并發(fā)子任務(wù)輸入矩陣規(guī)模INPUT一組無關(guān)的子任務(wù)COMPUTINGi，每個(gè)子任務(wù)分別完成一個(gè)矩陣片段的計(jì)算通信問題：子任務(wù)之間通常不是完全獨(dú)立的，一個(gè)子任務(wù)在執(zhí)行自己的局部計(jì)算時(shí)，常常需要使用問題域中其它子任務(wù)的中間結(jié)果COMPUTINGi需要INPUT的結(jié)果確定自己的迭代空間大小同步問題——子任務(wù)之間存在數(shù)據(jù)/控制相關(guān)，需要協(xié)調(diào)并發(fā)子任務(wù)的執(zhí)行進(jìn)度INPUT完成之后，才能開始COMPUTINGi的執(zhí)行子任務(wù)分配問題