周文榮

摘 要：并行計(jì)算作為現(xiàn)代科學(xué)計(jì)算的一種重要方法，常用于解決復(fù)雜和計(jì)算量大的問題。MPI程序包含了并行計(jì)算的思想，文章對(duì)并行計(jì)算與MPI進(jìn)行了研究，了解了MPI程序思想，對(duì)并行計(jì)算意義較大。

關(guān)鍵詞：并行計(jì)算；MPI；并行算法

1 并行計(jì)算簡介

并行計(jì)算與串行計(jì)算的區(qū)別在于，串行計(jì)算只在單個(gè)CPU上進(jìn)行求解，而并行計(jì)算則是同一個(gè)時(shí)間段內(nèi)在多個(gè)CPU上求解；從硬件角度上來講，串行計(jì)算就是在普通計(jì)算機(jī)上求解，并行計(jì)算則是于并行計(jì)算機(jī)上求解。需要并行計(jì)算求解的問題須能分成很多并行子問題[1]。

在20世紀(jì)50年代之后，日益提升的計(jì)算速度逐漸成為互聯(lián)網(wǎng)、娛樂游戲、科學(xué)計(jì)算領(lǐng)域的決定因素。例如畫面優(yōu)美反應(yīng)靈敏的電腦游戲、精確及時(shí)的引擎搜索、清晰明了的醫(yī)學(xué)成像等方方面面都離不開計(jì)算性能的提升。中國的現(xiàn)代生活很多都在和計(jì)算產(chǎn)生著關(guān)聯(lián)，例如在生物醫(yī)藥方面，醫(yī)學(xué)專家可以利用計(jì)算分析的相關(guān)知識(shí)通過患者的基因找到不會(huì)對(duì)人體產(chǎn)生損傷的替代藥物，通過提高計(jì)算性能來提高分析蛋白質(zhì)結(jié)構(gòu)的能力；在能源方面，快速的計(jì)算能力能在太陽能電池、風(fēng)力發(fā)電機(jī)和蓄電池方面幫助開發(fā)人員進(jìn)行更加準(zhǔn)確的建模，得到更加高效清潔的能源信息。在新聞報(bào)刊上經(jīng)常提到的高性能計(jì)算其實(shí)和并行計(jì)算意思相同，這樣表述的原因是高性能計(jì)算和超級(jí)計(jì)算都用到并行計(jì)算。

并行計(jì)算的特點(diǎn)主要表現(xiàn)在：（1）并行計(jì)算由相對(duì)獨(dú)立的模塊獨(dú)立分開管理控制；（2）在并行計(jì)算中會(huì)存在多個(gè)模塊同時(shí)異步進(jìn)行，該并行能有效降低運(yùn)行耗費(fèi)的時(shí)間；（3）所有的模塊與模塊之間存在一定的交互；（4）并行計(jì)算可能由于并發(fā)和交互導(dǎo)致錯(cuò)誤發(fā)生[2-3]。

并行計(jì)算采用的并行方法主要包括：（1）資源共享，是指用軟件方法實(shí)現(xiàn)資源在某段時(shí)間內(nèi)可以同時(shí)訪問；（2） 資源重復(fù)，是指通過重復(fù)設(shè)置和利用硬件和軟件資源，以此來提高計(jì)算機(jī)系統(tǒng)的性能；（3）時(shí)間重疊，例如不同的進(jìn)程在時(shí)間上相同資源的使用相互錯(cuò)開或者輪流重復(fù)利用某硬件資源，來提升速度。并行遺傳算法是并行計(jì)算的一個(gè)分支應(yīng)用，將會(huì)大大減少得到最優(yōu)解所需要的時(shí)間。

本文既然涉及并行計(jì)算，肯定也會(huì)涉及并行體系。并行體系的主要特點(diǎn)為：（1）并行性，多流水、超標(biāo)量是提升CPU并行性能的重中之重。在新型并行體系中，根據(jù)并行的程度分級(jí)；（2）可擴(kuò)展性，是指增加資源時(shí)，性能和功能得到提升。認(rèn)識(shí)可擴(kuò)展性應(yīng)該認(rèn)識(shí)到成本伸縮的比例應(yīng)該小于線性比例。

早期的微處理器的計(jì)算性能以平均每年50%的速度提升。后來受到摩爾定律的限制，微處理性能提升速度漸漸變慢，在進(jìn)入21世紀(jì)之后，主流的微處理器制造商已決定通過并行處理來快速提升微處理器的計(jì)算性能，以求進(jìn)一步提升計(jì)算能力。由此可見并行計(jì)算對(duì)現(xiàn)代科學(xué)計(jì)算至關(guān)重要。

2 系統(tǒng)分類

并行計(jì)算在專門的平臺(tái)上完成，完成整個(gè)并行過程的平臺(tái)一般稱為并行計(jì)算機(jī)。串行計(jì)算機(jī)主要包含3個(gè)方面：處理器、內(nèi)存及數(shù)據(jù)通道。并行計(jì)算機(jī)主要含有3個(gè)大類：共享存儲(chǔ)的多處理機(jī)、分布式存儲(chǔ)的多處理機(jī)和集群[4]。

自20世紀(jì)70年代起，并行的硬件平臺(tái)就處于高速發(fā)展階段，各種硬件平臺(tái)相繼出現(xiàn)，向量機(jī)、單指令多數(shù)據(jù)流系統(tǒng)和多指令多數(shù)據(jù)流系統(tǒng)等相繼面世。隨著時(shí)間的腳步慢慢向前邁進(jìn)，向量機(jī)和單指令多數(shù)據(jù)流系統(tǒng)慢慢被淘汰，而多指令多數(shù)據(jù)流系統(tǒng)越來越受到大家的推崇。

3 并行算法

3.1 同步并行

主要是因?yàn)椴煌倪M(jìn)程完成速度不同，在使用同步命令之后，速度快的進(jìn)程需要等速度慢的進(jìn)程結(jié)束之后再與速度慢的進(jìn)程同時(shí)進(jìn)行下一步。

3.2 異步并行

主要是由于并行計(jì)算的獨(dú)立性產(chǎn)生的，進(jìn)程之間相互獨(dú)立，也沒有執(zhí)行同步命令，各個(gè)進(jìn)程可以按照各自的節(jié)奏有序地進(jìn)行。

3.3 數(shù)值并行

主要是因?yàn)楝F(xiàn)實(shí)生活中很多模型是用數(shù)學(xué)模型表示的，而這些數(shù)學(xué)模型大部分能用數(shù)值來計(jì)算。

3.4 非數(shù)值并行

主要是指除去數(shù)值計(jì)算之外的計(jì)算，例如關(guān)系計(jì)算、邏輯計(jì)算等。

并行算法的主要特點(diǎn)是：（1）并行算法與計(jì)算機(jī)的結(jié)構(gòu)有很大的關(guān)系，針對(duì)同一問題，當(dāng)所使用的并行計(jì)算機(jī)的結(jié)構(gòu)不同時(shí)，最后所使用的算法不同；（2）并行算法比較復(fù)雜，并行算法和任務(wù)分配、數(shù)據(jù)分配、數(shù)據(jù)結(jié)構(gòu)等有著較多聯(lián)系，而數(shù)據(jù)的分配、任務(wù)的分配和數(shù)據(jù)的結(jié)構(gòu)都比較復(fù)雜，只要有一種不同就可能會(huì)導(dǎo)致算法的并行效果完全不同。

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

消息傳遞接口（Multi Point Interface，MPI）是一種基于并行計(jì)算的模型。MPI標(biāo)準(zhǔn)公布之后，很多MPI實(shí)現(xiàn)相繼出現(xiàn)，例如使用LAM和MPICH實(shí)現(xiàn)MPI變得越發(fā)流行[5]。

由俄亥俄州的州立大學(xué)超級(jí)計(jì)算中心開發(fā)的LAM可以免費(fèi)實(shí)現(xiàn)MPI。LAM在異構(gòu)網(wǎng)絡(luò)集群環(huán)境下，向使用者提供MPI實(shí)現(xiàn)所需要的編程界面以及實(shí)現(xiàn)過程中所需要的調(diào)試環(huán)境。LAM是免費(fèi)的、開放的、開源的，且具有不錯(cuò)的擴(kuò)展特點(diǎn)，能動(dòng)態(tài)擴(kuò)充虛擬機(jī)與進(jìn)程組。

MPICH是具有可移植性的MPI實(shí)現(xiàn)，由美國密西根州立大學(xué)和美國國家實(shí)驗(yàn)室在制定MPI標(biāo)準(zhǔn)的過程中聯(lián)合開發(fā)，MPICH出現(xiàn)的主要目的是為MPI提供一個(gè)具有高的可移植性和高效率的接口。

MPI的目標(biāo)是實(shí)現(xiàn)較高的移植性和較高的通信效率。MPI在發(fā)展的過程中有效地結(jié)合了實(shí)用性，并巧妙利用了之前開發(fā)的消息傳遞系統(tǒng)中消息通信的知識(shí)，成功地變成一種通用的標(biāo)準(zhǔn)。

MPI是一種集合，此集合包含了很多不同的函數(shù)庫，這些函數(shù)可以被C或FORTRAN調(diào)用?？梢詫PI理解為具有可移植性和擴(kuò)展性的消息傳遞模型。這樣的消息傳遞模型同時(shí)也是并行計(jì)算的標(biāo)準(zhǔn)。MPI代表的是一種規(guī)范，所以很多產(chǎn)商都對(duì)它予以肯定。

1997年形成的MPI-2包含有大概200多個(gè)函數(shù)，其中最基本的是6個(gè)函數(shù)。只要使用這6個(gè)基本函數(shù)，就代表一個(gè)完整的MPI程序。

MPI的主要優(yōu)點(diǎn)為高效的通信性、便捷的實(shí)用性、較高的移植性和準(zhǔn)確的定義等。

MPI的目的是指MPI標(biāo)準(zhǔn)的目的。MPI標(biāo)準(zhǔn)的目的為：（1）通信效率的提高；（2）由于它的可移植性，它必須能在異構(gòu)的環(huán)境下實(shí)現(xiàn)；（3）MPI需要在不同的進(jìn)程之間傳遞消息，所以MPI需要具有消息傳遞接口；（4）MPI的接口必須可以用C語言或者FORTRAN語言調(diào)用；（5）因?yàn)镸PI具有可擴(kuò)展性，所以MPI的接口需要可以進(jìn)行延伸；（6）設(shè)計(jì)出的接口一定為安全有效的；（7）設(shè)計(jì)接口的語言必須是獨(dú)立的。這樣的接口能夠在多平臺(tái)上實(shí)現(xiàn)，能夠被直接調(diào)用。

MPI不僅可以在PC/Windows系統(tǒng)下的并行機(jī)上實(shí)現(xiàn)，而且也可以在Linux系統(tǒng)下的并行機(jī)上實(shí)現(xiàn)。一個(gè)用C或者FORTRAN開發(fā)的MPI程序不僅可以在一個(gè)PC機(jī)上實(shí)現(xiàn)，也可以在并行機(jī)上實(shí)現(xiàn)，同時(shí)可以在集群上實(shí)現(xiàn)，不管此平臺(tái)是哪家公司制造的，不管是哪種操作系統(tǒng)，只要保持原樣進(jìn)行移植就能成功編譯。

5 MPI基本函數(shù)

MPI中包含6個(gè)基本函數(shù)，這些基本函數(shù)如下[5]：

5.1 MPI初始化函數(shù)

MPI初始化函數(shù)的原型是int MPI_Init（int *argc， char **argv）。MPI_Init是MPI的程序中使用的第一個(gè)MPI函數(shù)，該函數(shù)會(huì)對(duì)MPI程序和MPI的環(huán)境進(jìn)行初始化。

5.2 MPI結(jié)束函數(shù)

MPI結(jié)束函數(shù)的函數(shù)原型是：int MPI_Finalize（void）。當(dāng)MPI程序需要結(jié)束時(shí)就會(huì)調(diào)用結(jié)束函數(shù)MPI_Finalize。結(jié)束函數(shù)位于涉及MPI代碼的最后面，是MPI代碼執(zhí)行過程中所用到的最后一個(gè)函數(shù)。

5.3 MPI獲取當(dāng)前進(jìn)程編號(hào)的函數(shù)

MPI獲取當(dāng)前進(jìn)程編號(hào)的函數(shù)模型如下：MPI_COMM_rank（MPI_COMM comm， int *rank）。第一個(gè)參數(shù)comm表示進(jìn)程處于的唯一通信域；第二個(gè)參數(shù)表示在這個(gè)通信域中的進(jìn)程所代表的編號(hào)。MPI獲取當(dāng)前編號(hào)函數(shù)的目的是求出此進(jìn)程在該通信域中的編號(hào)，然后將這個(gè)編號(hào)賦給第二個(gè)參數(shù)rank。

5.4 MPI獲取通信域中所包含的進(jìn)程數(shù)目的函數(shù)

MPI得到位于通信域中的進(jìn)程的數(shù)目的函數(shù)模型為int MPI_Comm_size（MPI_Comm comm， int *size）。MPI獲取通信域中所包含的進(jìn)程的個(gè)數(shù)的函數(shù)的模型中第一個(gè)參數(shù)comm表示的是通信域，后面一個(gè)參數(shù)size代表comm中的含有進(jìn)程個(gè)數(shù)。此函數(shù)返回一個(gè)通信域中的進(jìn)程總體的數(shù)目給size。只要是位于此通信域里面的進(jìn)程都可以用此函數(shù)來獲取這個(gè)通信域包含有幾個(gè)進(jìn)程。

5.5 發(fā)送消息函數(shù)

發(fā)送消息函數(shù)的函數(shù)原型為：int MPI_Send（void *buf， int count， MPI_Datatype datatype， int deat， int tag， MPI_Comm comm）。

buf —所發(fā)送的數(shù)據(jù)的首地址

Count—所發(fā)送的數(shù)據(jù)的個(gè)數(shù)

Datatype—所發(fā)送的數(shù)據(jù)的數(shù)據(jù)類型

dest—需要發(fā)送到的目標(biāo)進(jìn)程的編號(hào)

Tag—所發(fā)送的消息的標(biāo)志

Comm—通信域

5.6 接收消息函數(shù)

接收消息函數(shù)的函數(shù)模型為：int MPI_Recv（void *buf， int count， MPI_Datatype datatype， int source， int tag， MPI_Comm comm， MPI_Status *status）。

Buf—所接收的數(shù)據(jù)的首地址

Count—所接收的數(shù)據(jù)的個(gè)數(shù)

Datatype—所接收的數(shù)據(jù)的類型

Source—所接收的數(shù)據(jù)的來源進(jìn)程編號(hào)

Tag—所接收的消息的編號(hào)

Comm—通信域

Status—接收數(shù)據(jù)的時(shí)候返回的狀態(tài)

6 MPI并行模式

MPI程序在編寫過程中分為兩種不同模式：對(duì)等模式和主從模式。

6.1 對(duì)等模式

在這種模式中，進(jìn)程與進(jìn)程之間地位平等，能相互聯(lián)系。對(duì)等體現(xiàn)在不同進(jìn)程地位相同，MPI代碼功能類似上，唯一的不同體現(xiàn)為不同的進(jìn)程所處理的處理對(duì)象和數(shù)據(jù)不同[6-7]。在消息模型中存在4個(gè)對(duì)等結(jié)點(diǎn)時(shí)，對(duì)等節(jié)點(diǎn)之間的通信模式如圖1所示。

在對(duì)等模式中，各個(gè)對(duì)等節(jié)點(diǎn)相互通信，并將結(jié)果和控制信息進(jìn)行傳遞。其中有一個(gè)對(duì)等點(diǎn)的任務(wù)是將任務(wù)進(jìn)行分配，在完成之后又在此節(jié)點(diǎn)上進(jìn)行結(jié)果匯總。

6.2 主從模式

在主從模式中，不同的節(jié)點(diǎn)功能和地位不同[8]。在主從模式中會(huì)存在1個(gè)主進(jìn)程和1個(gè)或多個(gè)從進(jìn)程，主進(jìn)程與從進(jìn)程之間的關(guān)系如圖2所示。

在主從模式中，主進(jìn)程主要進(jìn)行控制，從進(jìn)程主要進(jìn)行計(jì)算。主進(jìn)程的任務(wù)是對(duì)所有進(jìn)程進(jìn)行初始化，將計(jì)算任務(wù)分到從進(jìn)程；從進(jìn)程根據(jù)主進(jìn)程的要求完成計(jì)算任務(wù)，并將最后取得的結(jié)果返回到主進(jìn)程。

[參考文獻(xiàn)]

[1]陳國良.并行計(jì)算：結(jié)構(gòu)·算法·編程[M].北京：高等教育出版社，1999.

[2]DARRIBA D，TABOADA GL，DOALLO R，et al. Model Test 2：more models，new heuristics and parallel computing[J].Nature Methods，2012（8）：772-772.

[3]GOLUB GH，ORTEGA JM. Scientific computing：an introduction with parallel computing[M]. Amsterdam： Elsevier，2014.

[4]ROBERGE V，TARBOUCHI M， LABONT? G. Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning[J].Industrial Informatics，2013（1）：132-141.

[5]STEVENS B，GIORGETTA M，ESCH M，et al. Atmospheric component of the MPI-M earth system model：ECHAM6[J].Journal of Advances in Modeling Earth Systems，2013（2）：146-172.

[6]GUNARATHNE T，ZHANG B，WU TL，et al. Scalable parallel computing on clouds using twister4Azure iterative mapreduce[J].Future Generation Computer Systems，2013（4）：1035-1048.

[7]CHANDY KM，TAYLOR S. An introduction to parallel programming[J].Jones and Bartlet，1992（4）：361-370.

[8]CANTPAZ E. A survey of parallel genetic algorithms[J].Calculateurs Paralleles Reseaux Et Systems Repartis，1998（4）：429-449.

Abstract： As an important method of modern scientific computing， parallel computing is often used to solve the complex and large amount of computational problems. The MPI program contains the idea of parallel computing. In this paper， the parallel computing and MPI are studied， and the idea of MPI is find out， which is of great significance to parallel computing.

Key words： parallel computing； MPI； parallel algorithm