并行計算與MPI研究

周文榮

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

關鍵詞：并行計算；MPI；并行算法

1 并行計算簡介

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

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

并行計算的特點主要表現在：（1）并行計算由相對獨立的模塊獨立分開管理控制；（2）在并行計算中會存在多個模塊同時異步進行，該并行能有效降低運行耗費的時間；（3）所有的模塊與模塊之間存在一定的交互；（4）并行計算可能由于并發和交互導致錯誤發生[2-3]。

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

本文既然涉及并行計算，肯定也會涉及并行體系。并行體系的主要特點為：（1）并行性，多流水、超標量是提升CPU并行性能的重中之重。在新型并行體系中，根據并行的程度分級；（2）可擴展性，是指增加資源時，性能和功能得到提升。認識可擴展性應該認識到成本伸縮的比例應該小于線性比例。

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

2 系統分類

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

自20世紀70年代起，并行的硬件平臺就處于高速發展階段，各種硬件平臺相繼出現，向量機、單指令多數據流系統和多指令多數據流系統等相繼面世。隨著時間的腳步慢慢向前邁進，向量機和單指令多數據流系統慢慢被淘汰，而多指令多數據流系統越來越受到大家的推崇。

3 并行算法

3.1 同步并行

主要是因為不同的進程完成速度不同，在使用同步命令之后，速度快的進程需要等速度慢的進程結束之后再與速度慢的進程同時進行下一步。

3.2 異步并行

主要是由于并行計算的獨立性產生的，進程之間相互獨立，也沒有執行同步命令，各個進程可以按照各自的節奏有序地進行。

3.3 數值并行

主要是因為現實生活中很多模型是用數學模型表示的，而這些數學模型大部分能用數值來計算。

3.4 非數值并行

主要是指除去數值計算之外的計算，例如關系計算、邏輯計算等。

并行算法的主要特點是：（1）并行算法與計算機的結構有很大的關系，針對同一問題，當所使用的并行計算機的結構不同時，最后所使用的算法不同；（2）并行算法比較復雜，并行算法和任務分配、數據分配、數據結構等有著較多聯系，而數據的分配、任務的分配和數據的結構都比較復雜，只要有一種不同就可能會導致算法的并行效果完全不同。

4 MPI并行程序設計

消息傳遞接口（Multi Point Interface，MPI）是一種基于并行計算的模型。MPI標準公布之后，很多MPI實現相繼出現，例如使用LAM和MPICH實現MPI變得越發流行[5]。

由俄亥俄州的州立大學超級計算中心開發的LAM可以免費實現MPI。LAM在異構網絡集群環境下，向使用者提供MPI實現所需要的編程界面以及實現過程中所需要的調試環境。LAM是免費的、開放的、開源的，且具有不錯的擴展特點，能動態擴充虛擬機與進程組。

MPICH是具有可移植性的MPI實現，由美國密西根州立大學和美國國家實驗室在制定MPI標準的過程中聯合開發，MPICH出現的主要目的是為MPI提供一個具有高的可移植性和高效率的接口。

MPI的目標是實現較高的移植性和較高的通信效率。MPI在發展的過程中有效地結合了實用性，并巧妙利用了之前開發的消息傳遞系統中消息通信的知識，成功地變成一種通用的標準。

MPI是一種集合，此集合包含了很多不同的函數庫，這些函數可以被C或FORTRAN調用。可以將MPI理解為具有可移植性和擴展性的消息傳遞模型。這樣的消息傳遞模型同時也是并行計算的標準。MPI代表的是一種規范，所以很多產商都對它予以肯定。

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

MPI的主要優點為高效的通信性、便捷的實用性、較高的移植性和準確的定義等。

MPI的目的是指MPI標準的目的。MPI標準的目的為：（1）通信效率的提高；（2）由于它的可移植性，它必須能在異構的環境下實現；（3）MPI需要在不同的進程之間傳遞消息，所以MPI需要具有消息傳遞接口；（4）MPI的接口必須可以用C語言或者FORTRAN語言調用；（5）因為MPI具有可擴展性，所以MPI的接口需要可以進行延伸；（6）設計出的接口一定為安全有效的；（7）設計接口的語言必須是獨立的。這樣的接口能夠在多平臺上實現，能夠被直接調用。

MPI不僅可以在PC/Windows系統下的并行機上實現，而且也可以在Linux系統下的并行機上實現。一個用C或者FORTRAN開發的MPI程序不僅可以在一個PC機上實現，也可以在并行機上實現，同時可以在集群上實現，不管此平臺是哪家公司制造的，不管是哪種操作系統，只要保持原樣進行移植就能成功編譯。

5 MPI基本函數

MPI中包含6個基本函數，這些基本函數如下[5]：

5.1 MPI初始化函數

MPI初始化函數的原型是int MPI_Init（int *argc， char **argv）。MPI_Init是MPI的程序中使用的第一個MPI函數，該函數會對MPI程序和MPI的環境進行初始化。

5.2 MPI結束函數

MPI結束函數的函數原型是：int MPI_Finalize（void）。當MPI程序需要結束時就會調用結束函數MPI_Finalize。結束函數位于涉及MPI代碼的最后面，是MPI代碼執行過程中所用到的最后一個函數。

5.3 MPI獲取當前進程編號的函數

MPI獲取當前進程編號的函數模型如下：MPI_COMM_rank（MPI_COMM comm， int *rank）。第一個參數comm表示進程處于的唯一通信域；第二個參數表示在這個通信域中的進程所代表的編號。MPI獲取當前編號函數的目的是求出此進程在該通信域中的編號，然后將這個編號賦給第二個參數rank。

5.4 MPI獲取通信域中所包含的進程數目的函數

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

5.5 發送消息函數

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

buf —所發送的數據的首地址

Count—所發送的數據的個數

Datatype—所發送的數據的數據類型

dest—需要發送到的目標進程的編號

Tag—所發送的消息的標志

Comm—通信域

5.6 接收消息函數

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

Buf—所接收的數據的首地址

Count—所接收的數據的個數

Datatype—所接收的數據的類型

Source—所接收的數據的來源進程編號

Tag—所接收的消息的編號

Comm—通信域

Status—接收數據的時候返回的狀態

6 MPI并行模式

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

6.1 對等模式

在這種模式中，進程與進程之間地位平等，能相互聯系。對等體現在不同進程地位相同，MPI代碼功能類似上，唯一的不同體現為不同的進程所處理的處理對象和數據不同[6-7]。在消息模型中存在4個對等結點時，對等節點之間的通信模式如圖1所示。

在對等模式中，各個對等節點相互通信，并將結果和控制信息進行傳遞。其中有一個對等點的任務是將任務進行分配，在完成之后又在此節點上進行結果匯總。

6.2 主從模式

在主從模式中，不同的節點功能和地位不同[8]。在主從模式中會存在1個主進程和1個或多個從進程，主進程與從進程之間的關系如圖2所示。

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

[參考文獻]

[1]陳國良.并行計算：結構·算法·編程[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