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

4：取前4臺計算機，依次運行進程0、1、2、3machinelist中所列計算機的數量M

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

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