并行開發(fā)環(huán)境和并行程序設計

并行開發(fā)環(huán)境和

并行程序設計Pitt.Chang集群與網(wǎng)格計算實驗室IntelP2P項目組HUSTWuHan1.1科學技術的發(fā)展呼喚巨大的、

不斷增長的計算能力中長期天氣預報。每增加一天，要求計算速度增加一個數(shù)量級。三天百萬次/sec，四天千萬次/sec，五天億次/sec信息戰(zhàn)。關鍵是對信息的處理速度，如雷達信息的處理地震預報預測石油勘測生物信息處理……1.2提高計算能力的基本途徑器件：新工藝（超大規(guī)模集成電路）新材料（生物計算機、光計算機）系統(tǒng)結構的改進：主要是克服VonNeumann的瓶頸問題。 流水線計算機、向量計算機、多處理 機、并行計算機、集群。1.2提高計算能力的基本途徑計算能力幾乎提高了上萬倍，但是，實際的并行計算能力提高只有幾十倍。原因：不能利用計算機的并行處理能力。也就是沒有解決并行計算中的并行程序設計的問題。其核心問題是并行算法2.并行計算機系統(tǒng)2.1并行計算機的分類2.2計算問題在并行機上的求解

2.1并行計算機的分類指令與數(shù)據(jù)

SIMD， MIMD，SPMD，MPMD存儲方式 共享內(nèi)存，分布式內(nèi)存，分布式共享內(nèi)存2.1.1指令與數(shù)據(jù)SIMD(Single-InstructionMultiple-Data)，同時用相同的指令對不同的數(shù)據(jù)進行操作MIMD(Multiple-InstructionMultiple-Data)，同時有多條指令對不同的數(shù)據(jù)進行操作SPMD(Single-ProgramMultuple-Data)，同時執(zhí)行相同的程序對不同數(shù)據(jù)操作MPMD(Multiple-ProgramMultuple-Data)，同時有多個程序對不同的數(shù)據(jù)進行操作2.1.2存儲方式共享內(nèi)存。處理單元通過對共享內(nèi)存的訪問來交換信息協(xié)調各處理器對并行任務的處理。共享內(nèi)存是性能特別是擴展性的瓶頸分布式內(nèi)存。各個處理單元擁有獨立的局部存儲器，處理器之間通過消息傳遞來交換信息，協(xié)調和控制各個處理器的執(zhí)行。有很好的擴展性和很高的性能分布式共享內(nèi)存。結合前兩者特點，提高了整個系統(tǒng)的計算能力而且可以提高系統(tǒng)的模塊性和擴展性有利于快速構造超大型的計算系統(tǒng)2.1.2存儲方式2.2物理問題在并行機上的求解3.并行算法設計SIMD并行計算機一般適合同步并行算法MIMD并行計算機適合異步并行算法對于SPMD，要設法加大計算時間相對于通信時間的比重，減少通信次數(shù)甚至以計算換通信，一個好的算法應呈現(xiàn)右圖模式：3.并行算法設計若能實現(xiàn)計算與通信的重疊，將是更理想的計算模式：對于MPMD并行算法各并行部分一般是異步執(zhí)行的，最好能夠降低通信次數(shù)，增大計算相對于通信的比重：4.MPI程序設計初步什么是MPI？ 是一個庫而不是一門語言 是一種標準或規(guī)范的代表而不特指某一個對它的具體實現(xiàn)

是一種消息傳遞編程模型并成為這種編程模型的代表和事實上的標準 對MPI的使用必須和特定的語言結合起來進行：C,JAVA,FORTRAN目前主要的MPI實現(xiàn)

MPICH:/mpi/mpich Chimp:ftp://ftp.epcc.ed.ac.uk/pub/packages/chimp/release/ Lam :http:///lam/4.1MPI基本調用從理論上說，MPI所有的通信功能可以用它的6個基本的調用來實現(xiàn): MPI_INIT MPI_FINALIZE MPI_COMM_RANK MPI_COMM_SIZE MPI_SEND MPI_RECV4.1.1MPI調用的參數(shù)說明MPI對參數(shù)說明的方式有三種：

IN:調用部分傳遞給MPI的參數(shù)，MPI除了使用該參數(shù)外不允許對這一參數(shù)做任何修改

OUT:MPI返回給調用部分的結果參數(shù)，該參數(shù)的初始值對MPI沒有任何意義

INOUT:調用部分首先將該參數(shù)傳遞給MPI，MPI對這一參數(shù)引用、修改后，將結果返回給外部調用，該參數(shù)的初始值和返回結果都有意義

4.1.1MPI調用的參數(shù)說明如果某一個參數(shù)在調用前后沒有改變，比如某個隱含對象的句柄但是該句柄指向的對象被修改了，這一參數(shù)仍然被說明為OUT或INOUTMPI函數(shù)的一個參數(shù)被一些并行執(zhí)行的進程用作IN，而被另一些同時執(zhí)行的進程用作OUT，這樣的參數(shù)語法上也記為INOUT當一個MPI參數(shù)僅對一些并行執(zhí)行的進程有意義而對其它的進程沒有意義時，不關心該參數(shù)取值的進程可以將任意的值傳遞給該參數(shù)在MPI中OUT或INOUT類型的參數(shù)不能被其它的參數(shù)作為別名使用是對于MPI的調用，允許不同的數(shù)據(jù)類型使用相同的調用，在C語言中是采用void*來實現(xiàn)4.1.2MPI初始化函數(shù)定義：

MPI_INIT() intMPI_Init(int*argc,char***argv)MPI_INIT完成MPI程序所有的初始化工作，所有MPI程序的第一條可執(zhí)行語句都是這條語句4.1.3MPI結束函數(shù)定義：

MPI_FINALIZE()

int

MPI_Finalize(void)MPI_FINALIZE結束MPI程序的運行，它是MPI程序的最后一條可執(zhí)行語句，否則程序的運行結果是不可預知的4.1.4當前進程標識函數(shù)定義：

MPI_COMM_RANK(comm,rank) IN comm

該進程所在的通信域(句柄) OUT rank 調用進程在comm中的標識號

int

MPI_Comm_rank(MPI_Comm

comm,int*rank)返回調用進程在給定的通信域中的進程標識號，根據(jù)這一標識號不同的進程就可以將自身和其它的進程區(qū)別開來實現(xiàn)各進程的并行和協(xié)作4.1.5通信域包含的進程數(shù)函數(shù)定義：

MPI_COMM_SIZE(comm,size) IN comm

通信域句柄

OUT size 通信域comm內(nèi)包括的進程數(shù)

int

MPI_Comm_size(MPI_Comm

comm,int*size)返回給定的通信域中所包括的進程的個數(shù)，不同的進程通過這一調用得知在給定的通信域中一共有多少個進程在并行執(zhí)行4.1.6消息發(fā)送函數(shù)定義：

MPI_SEND(buf,count,datatype,dest,tag,comm) INbuf

發(fā)送緩沖區(qū)的起始地址(可選類型) INcount 將發(fā)送的數(shù)據(jù)的個數(shù)(非負整數(shù)) INdatatype

發(fā)送數(shù)據(jù)的數(shù)據(jù)類型(句柄) INdest

目的進程標識號(整型) INtag 消息標志(整型) INcomm

通信域(句柄)

int

MPI_Send(void*buf,intcount,MPI_Datatype

datatype,int

dest,inttag,MPI_Commcomm)4.1.6消息發(fā)送函數(shù)MPI_SEND將發(fā)送緩沖區(qū)中的count個(不是以字節(jié)計數(shù)而是以數(shù)據(jù)類型為單位指定消息的長度)datatype數(shù)據(jù)類型的數(shù)據(jù)發(fā)送到目的進程，目的進程在通信域中的標識號是dest，本次發(fā)送的消息標志是tag，使用這一標志就可以把本次發(fā)送的消息和本進程向同一目的進程發(fā)送的其它消息區(qū)別，其中datatype數(shù)據(jù)類型可以是MPI的預定義類型也可以是用戶自定義的類型4.1.7消息接收函數(shù)定義：

MPI_RECV(buf,count,datatype,source,tag,comm,status) OUTbuf

接收緩沖區(qū)的起始地址(可選數(shù)據(jù)類型) INcount最多可接收的數(shù)據(jù)的個數(shù)(整型) INdatatype

接收數(shù)據(jù)的數(shù)據(jù)類型(句柄) INsource接收數(shù)據(jù)的來源即發(fā)送數(shù)據(jù)的進程的進程標識號(整型) INtag消息標識與相應的發(fā)送操作的表示相匹配相同(整型) INcomm

本進程和發(fā)送進程所在的通信域(句柄) OUTstatus返回狀態(tài)(狀態(tài)類型)

int

MPI_Recv(void*buf,intcount,MPI_Datatype

datatype,intsource,int

tag,MPI_Comm

comm,MPI_Status*status)4.1.7消息接收函數(shù)從指定的進程source接收消息并且該消息的數(shù)據(jù)類型和消息標識和本接收進程指定的datatype和tag相一致接收到的消息所包含的數(shù)據(jù)元素的個數(shù)最多不能超過count。MPI沒有截斷，接收到的消息大于接收緩沖區(qū)會發(fā)生溢出錯誤。如果一個短于接收緩沖區(qū)的消息到達，那么只有相應于這個消息的那些地址被修改。count可以是零，這種情況下消息的數(shù)據(jù)部分是空的4.1.8返回狀態(tài)statusMPI定義的一個數(shù)據(jù)類型，使用之前需要用戶為它分配空間。在C實現(xiàn)中，狀態(tài)變量是由至少三個域組成的結構類型，這三個域分別是:MPI_SOURCE、MPI_TAG和MPI_ERRORstatus.MPI_SOURCE、status.MPI_TAG和status.MPI_ERROR的引用就可以得到返回狀態(tài)中所包含的發(fā)送數(shù)據(jù)進程的標識，發(fā)送數(shù)據(jù)使用的tag標識和本接收操作返回的錯誤代碼4.2MPI數(shù)據(jù)類型MPI預定義類型與C語言類型轉化4.2.1MPI數(shù)據(jù)類型匹配MPI消息傳遞的過程:消息裝配，消息傳遞，消息拆卸。三個階段都需要類型匹配類型匹配有兩個方面的意思:

宿主語言的類型和通信操作所指定的類型相匹配

發(fā)送方和接收方的類型相匹配例外是對于MPI提供的MPI_BYTE和MPI_PACKED，它們可以和任何以字節(jié)為單位的存儲相匹配4.2.1MPI數(shù)據(jù)類型匹配類型匹配規(guī)則可以概括為: (1)有類型數(shù)據(jù)的通信，發(fā)送方和接收方均使用相同的數(shù)據(jù)類型

(2)無類型數(shù)據(jù)的通信，發(fā)送方和接收方均以MPI_BYTE作為數(shù)據(jù)類型

(3)打包數(shù)據(jù)的通信，發(fā)送方和接收方均使用MPI_PACKED4.2.2MPI數(shù)據(jù)轉換數(shù)據(jù)轉換包括兩個方面的意思： 數(shù)據(jù)類型的轉換，是指改變一個值的數(shù)據(jù)類型 數(shù)據(jù)表示的轉換，是指改變一個值的二進制表示在MPI中沒有限定數(shù)據(jù)表示轉換的細節(jié)，但總的目標是希望這樣的轉換保留整型、邏輯以及字符值不變，而把浮點值轉為在目標系統(tǒng)上能表示的最接近的值MPI程序在同構系統(tǒng)中運行，其所有進程運行在同一環(huán)境時，沒有轉換發(fā)生4.3MPI消息MPI消息包括信封和數(shù)據(jù)兩個部分,格式為:

信封：<源/目，標識，通信域>

數(shù)據(jù)：<起始地址，數(shù)據(jù)個數(shù)，數(shù)據(jù)類型>4.3MPI消息接收操作對消息的選擇由消息的信封管理接收者給source指定值MPI_ANY_SOURCE，標識任何進程發(fā)送的消息都可以接收給tag指定值MPI_ANY_TAG，則任何tag都是可接收不能給comm指定任意值MPI允許發(fā)送者=接收者，即一個進程可以給自己發(fā)送一個消息4.3MPI消息MPI通信域包括兩部分: (1)進程組：所有參加通信的進程的集合，進程的編號從0到N-1 (2)通信上下文：提供一個相對獨立的通信區(qū)域，不同的消息在不同的上下文中進行傳遞，不同上下文的消息互不干涉MPI初始化后會產(chǎn)生通信域MPI_COMM_WORLD，它包括了初始化時可得的全部進程用戶可以在原有的通信域的基礎上定義新的通信域5.MPI并行程序的通信模式MPI的四種通信模式： 標準通信模式：對等模式和主從模式 緩存通信模式 同步通信模式 就緒通信模式5.1標準通信模式在MPI采用標準通信模式，是否對發(fā)送的數(shù)據(jù)進行緩存是由MPI自身決定的對等模式和主從模式，絕大部分MPI的程序都是這兩種模式之一或二者的組合MPI程序一般是SPMD程序，所有的MPMD程序都可以用SPMD程序來表達5.1.1對等模式在對等模式中，各進程地位相同，功能和代碼基本相同，只是處理的數(shù)據(jù)或對象不同。典型應用如Jacobi迭代5.1.1對等模式例：Jacobi

迭代，串行算法表示：…REALA(N+1,N+1),B(N+1,N+1)…DOK=1,STEPDOJ=1,NDOI=1,N

B(I,J)=0.25*(A(I-1,J)+A(I+1,J)+A(I,J+1)+A(I,J-1))ENDDOENDDODOJ=1,NDOI=1,NA(I,J)=B(I,J)ENDDOENDDO5.1.1對等模式M*M的二維數(shù)組A(M,M)，令M=4*N，分布在四個不同進程上的數(shù)據(jù)分別是進程0:A(M,1:N),進程1:A(M,N+1:2*N),進程3:A(M,2*N+1:3*N),進程3:A(M,3*N+1:M)5.1.2主從模式具有主進程和從進程，主進程接收從進程的處理結果，并進行匯總處理典型應用如矩陣向量乘法5.1.2主從模式對于矩陣C=A*B，主進程將向量B廣播給所有的從進程，然后將矩陣A的各行依次發(fā)送給。從進程從進程計算一行和B相乘的結果然后將結果發(fā)送給主進程。主進程循環(huán)向各個從進程發(fā)送一行的數(shù)據(jù)直到將A各行的數(shù)據(jù)發(fā)送完畢。一旦主進程將A的各行發(fā)送完畢則每收到一個結果就向相應的從進程發(fā)送結束標志，從進程接收到結束標志后退出執(zhí)行主進程收集完所有的結果后也結束5.2緩存通信模式用戶直接對通信緩沖區(qū)進行申請、使用和釋放不管接收操作是否啟動，發(fā)送操作都可以執(zhí)行，但是在發(fā)送消息之前必須有緩沖區(qū)，這由用戶保證消息發(fā)送能否進行及能否正確返回，不依賴于接收進程，完全依賴于是否有足夠的通信緩沖區(qū)可用5.3同步通信模式發(fā)送不依賴于接收進程相應的接收操作是否已經(jīng)啟動，但是同步發(fā)送卻必須等到相應的接收進程開始后才可以正確返回同步發(fā)送返回后，發(fā)送緩沖區(qū)中的數(shù)據(jù)已經(jīng)全部被系統(tǒng)緩沖區(qū)緩存并且已經(jīng)開始發(fā)送5.4就緒通信模式只有當接收進程的接收操作已經(jīng)啟動時，才可以在發(fā)送進程啟動發(fā)送操作對于非阻塞發(fā)送操作的正確返回，并不意味著發(fā)送已完成，但對于阻塞發(fā)送的正確返回，則發(fā)送緩沖區(qū)可以重復使用就緒通信模式的特殊之處就在于它要求接收操作先于發(fā)送操作而被啟動幾種通訊模式比較6.MPICH的安裝和配置MPICH在linux操作系統(tǒng)下的安裝MPI程序的執(zhí)行運行命令和配置文件6.1MPICH的安裝在HP集群套件ROCKS安裝后，會自動安裝MPICH，也就是說不用另外再安裝MPICH獲取軟件包：

mpich.tar.gz

運行tarzxvf

mpich.tar.gz解壓進入mpich子目錄，建Makefile和編譯：

./configure

也可以加prefix指出安裝的位置：./configure–prefix=/usr/local/mpich-1.2.4 make6.1MPICH的安裝測試安裝是否正確

cdexamples/basic makecpi ../../bin/mpirun–np4cpi將mpich安裝到指定的目錄：

makeinstall6.2MPI程序的執(zhí)行mpicc是編譯并聯(lián)接用C編寫的MPI程序，常用的編譯選項是：

-mpilog

產(chǎn)生MPE的log文件

-mpitrace

產(chǎn)生跟蹤文件，這樣在該MPI程序執(zhí)行時會打印出其運行蹤跡信息，但是它和-mpilog在編譯時不能同時存在只能二者選一

-mpianim

產(chǎn)生實時動畫

-show顯示編譯時產(chǎn)生的命令但并不執(zhí)行它

-help給出幫助信息

-echo顯示出當前正在編譯聯(lián)接的命令信息6.2MPI程序的執(zhí)行MPI程序的執(zhí)行過程：6.2MPI程序的執(zhí)行mpirun是MPI程序的啟動腳本(1)mpirun

–machinefil