郭福洲

摘? 要：步入信息高速快車的時代，基于MPI的并行計(jì)算是解決物聯(lián)網(wǎng)、圖像處理獲取數(shù)據(jù)，人工智能處理數(shù)據(jù)的重要途徑之一;同時也是MIMD（多指令多機(jī)）并行計(jì)算實(shí)現(xiàn)高效、高速目標(biāo)的重要策略與方法。筆者從MPI（Message-Passing-Interface 消息傳遞接口）一個跨語言的通信協(xié)議機(jī)制，通過Linux或Windows操作系統(tǒng)平臺，以C++語言平臺為基礎(chǔ)，論述并行計(jì)算實(shí)現(xiàn)幾種方法。

關(guān)鍵詞：MPI? 并行計(jì)算? 算法? 進(jìn)程? 消息? 通信

中圖分類號：TP301? ? ? ?文獻(xiàn)標(biāo)識碼：A

Abstract： In the era of information high-speed train， MPI-based parallel computing is one of the important ways to solve the Internet of Things， image processing to obtain data， and artificial intelligence to process data; It is also an important strategy and method for MIMD （multiple instruction multiple machine） parallel computing to achieve high efficiency and high speed. Starting from MPI （Message-Passing-Interface）， a cross-language communication protocol mechanism， through Linux or Windows operating system platform， based on the C++ language platform， the author discusses several ways to realize parallel computing.

Key Words： MPI; Parallel computing; Algorithm; Process; Message; Communication

1? 并行計(jì)算發(fā)展的背景

經(jīng)歷幾十年來電子信息產(chǎn)業(yè)的軟硬件相互倒逼、促進(jìn)與發(fā)展，人類在許多領(lǐng)域（如：空間氣象與遙感、圖像處理與捕捉、物聯(lián)網(wǎng)、人工智能、虛擬現(xiàn)實(shí)等）發(fā)展迅猛。但隨著人類在科學(xué)領(lǐng)域?qū)π畔⑴c數(shù)據(jù)處理數(shù)量規(guī)模與速度的要求更高，對數(shù)據(jù)處理、信息交換與傳輸效能、速度也在不斷地增加，并行計(jì)算[1]與分布式系統(tǒng)調(diào)度等新型算法與程控策略也更加日新月異。硬件搭臺（基礎(chǔ)），軟件唱戲（調(diào)度與并行計(jì)算編程），從硬件實(shí)現(xiàn)并行計(jì)算基礎(chǔ)層面來看：以網(wǎng)絡(luò)系統(tǒng)支撐重要結(jié)點(diǎn)――計(jì)算機(jī)為標(biāo)志，單機(jī)性能大幅度提升的主要舉措有：日益增加的集成電路晶體管密度、將提升信息傳遞速度增快與集成電路的散熱能力已經(jīng)達(dá)到極致，發(fā)展多核處理器;從軟件實(shí)現(xiàn)并行編程與計(jì)算層面來看：著力編寫任務(wù)并行和數(shù)據(jù)并行的程序，以期更大程度上利用多核處理器將有待解決的問題分解成的任務(wù)與數(shù)據(jù)科學(xué)分配并均衡到各個核上完成。

為實(shí)現(xiàn)這一目標(biāo)的并行硬件基礎(chǔ)構(gòu)建：主存+CPU+總線（互連設(shè)備）。采用Flynn（費(fèi)林）法基于指令和數(shù)據(jù)流方式分類，即，可以將并行計(jì)算機(jī)劃分為SISD、MISD、SIMD和MIMD四種。

除SISD系統(tǒng)外，其他三個才是真正的并行計(jì)算系統(tǒng)[2]。其中，SIMD是以同一指令進(jìn)行對多個數(shù)據(jù)執(zhí)行操作，進(jìn)而實(shí)現(xiàn)完成對多數(shù)據(jù)流進(jìn)行同時計(jì)算的目的。因此，該系統(tǒng)非常適合處理大型數(shù)組的簡單循環(huán)，從此衍生出向量處理器[3]，重點(diǎn)對數(shù)組或數(shù)據(jù)向量進(jìn)行操作。我們常說的GPU（graphics processing unit）圖形處理器計(jì)算機(jī)就是講物體表面的內(nèi)部表示為使用點(diǎn)、線、面的像素?cái)?shù)組來表示的，其初期也是一個概念上的SIMD系統(tǒng)，不過隨著技術(shù)的發(fā)展，現(xiàn)代GPU也可以有幾十個核，每個核也能獨(dú)立地執(zhí)行指令流。

在并行計(jì)算中，一般將MIMD作為主要研究對象。其中MIMD系統(tǒng)有兩種類型：共享內(nèi)存系統(tǒng)（見圖1）和分布式內(nèi)存系統(tǒng)（見圖2）。

在共享內(nèi)存系統(tǒng)中，自治的CPU通過互連網(wǎng)絡(luò)與內(nèi)存系統(tǒng)相連，每個CPU都能訪問每個內(nèi)存系統(tǒng)中的內(nèi)存。分布式內(nèi)存系統(tǒng)中，每個CPU都有自己的獨(dú)立內(nèi)存，每個單元之間的內(nèi)存訪問通過消息通信或者特殊的函數(shù)來進(jìn)行。

軟件編程實(shí)現(xiàn)并行計(jì)算的策略：無論哪一種互連，均需分布式運(yùn)算調(diào)度與并行計(jì)算作為靈魂支撐。SPMD（單程序多數(shù)據(jù)流）：指的不是在每個核上運(yùn)行不同的程序，而是一個程序僅包含一份代碼，通過一定的條件分支，使得這一份代碼再執(zhí)行的時候表現(xiàn)得像是在不同的處理器上執(zhí)行不同的代碼。

以MIMD分布式內(nèi)存系統(tǒng)來說，其CPU 各個內(nèi)核以DMA方式各自訪問自身內(nèi)存，負(fù)責(zé)處理CPU核之間通信的進(jìn)程進(jìn)行數(shù)據(jù)交換時，則只好通過消息[4]傳遞API來處理。負(fù)責(zé)消息傳遞API需提供至少一對發(fā)送函數(shù)和接收函數(shù)。并通過它們的序號（rank）來標(biāo)識。

并行計(jì)算程序的編寫主要目的當(dāng)然是為了提供它們的性能，那么我們應(yīng)該如何去評價一個并行計(jì)算程序的性能呢？答案是：加速比S=T串行T并行S=T串行T并行與效率E=T串行P×T并行E=T串行P×T并行。

理論上而言，如果使用p個進(jìn)程或者線程來運(yùn)行一個并行程序，并且每個核中之多只有一個進(jìn)程/線程，那么，S=p，E=1。但是在實(shí)際情況下，S<p， E<1。假設(shè)我們已具備如何評判由串行程序改為并行程序性能的能力，若現(xiàn)有一串行程序，為了提高性能，我們?nèi)绾螌⒋谐绦蚋臑椴⑿杏?jì)算程序獲取高性能？從理論層面策略實(shí)現(xiàn)如何分步？一般情況下，需要將工作進(jìn)行拆分，使得分布在每個進(jìn)程中的工作量均衡，并行讓它們之間的通信量最少。于是串行程序并行化設(shè)計(jì)策略展開一般按以下幾步進(jìn)行：

第一步：劃分。將串行程序細(xì)分并序化成為與為一個個具備獨(dú)立并行執(zhí)行的任務(wù)，每個任務(wù)都包含自己的指令與數(shù)據(jù)集;

第二步：通信。確定第一步識別出來的任務(wù)之間需要執(zhí)行那些通信。

第三步：凝聚/聚合。將第一步確定的任務(wù)與通信結(jié)合成上層宏觀任務(wù)。

第四步：分配。將層宏觀任務(wù)再分配至進(jìn)程/線程。這一步我們就關(guān)注：應(yīng)讓通信量最小化，并保證各個進(jìn)程/線程所領(lǐng)受的工作量基本均衡。

由務(wù)虛的理論走向務(wù)實(shí)，實(shí)現(xiàn)的手段有：MPI（Message-Passing-Interface 消息傳遞接口，后簡稱MPI）、Pthreads、OpenMP、OpenCL、GPU、Hadoop等，該文僅就MPI為主要闡述對象，討論其實(shí)現(xiàn)并行算法的途徑。

2? MPI的特性與并行編程機(jī)制

MPI（Message-Passing-Interface 消息傳遞接口）其任務(wù)是在并行計(jì)算進(jìn)程之間完成消息傳遞。傳遞層級為進(jìn)程層級。它并非編程語言，而是一個獨(dú)立且可被Fortran、C++和c#程序調(diào)用的函數(shù)庫。它主要集成了可供兩個進(jìn)程之間進(jìn)行各種情況通信處理的函數(shù)。并且其在Windows、Linux等不同平臺環(huán)境中都有對應(yīng)的庫。該文所述其應(yīng)用實(shí)踐，是以Windows10為開發(fā)環(huán)境為背景。

MPI定義了獨(dú)特的數(shù)據(jù)類型參數(shù)，不采用字節(jié)計(jì)數(shù)，而是以數(shù)據(jù)類型為單位指定消息長度;對于C和Fortran，MPI均預(yù)定義了一組數(shù)據(jù)類型和一些附加的數(shù)據(jù)類型;可以發(fā)送或接收連續(xù)的數(shù)據(jù)，還可以處理不連續(xù)的數(shù)據(jù);允許發(fā)送和接收不同的數(shù)據(jù)類型。

MPI與OpenMP并行程序的區(qū)別是：MPI是一種基于信息傳遞的并行編程技術(shù)。消息[5]傳遞接口是一種編程接口標(biāo)準(zhǔn)，并非一種具體的編程語言。簡言之，MPI標(biāo)準(zhǔn)定義了一組具有可移植性的編程接口。主要的MPI-1模型不包括共享內(nèi)存概念，MPI-2也只有有限的分布共享內(nèi)存概念。 但MPI程序經(jīng)常在共享內(nèi)存的機(jī)器上運(yùn)行。在MPI模型周邊設(shè)計(jì)程序比在NUMA架構(gòu)下設(shè)計(jì)要好，是因?yàn)镸PI鼓勵內(nèi)存本地化。盡管MPI屬于OSI參考模型的第五層（會話層）或者更高，他的實(shí)現(xiàn)可能通過傳輸層的sockets和Transmission Control Protocol （TCP）覆蓋大部分的層。大部分的MPI實(shí)現(xiàn)由一些指定慣例集（API）組成，可由有此類庫的語言比如C#， Java or Python直接調(diào)用。從通信[6]角度上，可視作為一個跨語言平臺的通信協(xié)議，用于計(jì)算機(jī)編寫程序?qū)崿F(xiàn)并行計(jì)算。支持點(diǎn)對點(diǎn)和廣播。MPI作為一個信息傳遞應(yīng)用程序接口，包括協(xié)議和和語義說明，用以說明其如何在各種實(shí)現(xiàn)中發(fā)揮其特性。MPI的特點(diǎn)是高性能、大規(guī)模性和可移植性。MPI在今天仍為高性能計(jì)算的主要模型。

MPI實(shí)現(xiàn)并行是進(jìn)程級;采用的是分布式內(nèi)存系統(tǒng)，顯式（數(shù)據(jù)分配方式）實(shí)現(xiàn)并行執(zhí)行，通過通信在進(jìn)程之間進(jìn)行消息傳遞，有較好的可擴(kuò)展性。MPI雖適合于各類機(jī)型，但其編程模型復(fù)雜：需要分析及劃分應(yīng)用程序問題，并將問題映射到分布式進(jìn)程集合;并需解決通信延遲長和負(fù)載不平衡兩大主要問題。

3? MPI安裝與設(shè)置要領(lǐng)

（1）MPI以mpich2-1.4.1p1-win-ia32.msi版本下載，地址http：//www.mpich.org/static/downloads/1.4.1p1/ ，下載完成后直接安裝，安裝過程中使用者那里選擇everyone，其他的都默認(rèn)。

（2） 以管理員的身份運(yùn)行CMD（命令行），輸入MPICH[5]的安裝路徑來到bin目錄下，然后輸入 smpd –install -phrase [你的關(guān)鍵字，默認(rèn)是behappy]。

（3）為了使計(jì)算機(jī)群能夠使用MPI，應(yīng)該給每一個安裝MPI的計(jì)算機(jī)添加一個相同的賬戶，賬戶密碼必須相同，賬戶要求是管理員的身份。比如所有的計(jì)算機(jī)都添加一個賬號為mpi，密碼是mpi的用戶。

（4）在MPICH的安裝目下的bin文件夾中找到wmpiregister.exe，將第二步注冊的賬戶密碼添加進(jìn)去，然后點(diǎn)擊確定。

（5）打開wmpiexec，在Application那一欄選擇MPICH安裝后自帶的例子，測試是否安裝成功，勾選run in an separate window，點(diǎn)擊Execute執(zhí)行。

4 結(jié)語

MPI標(biāo)準(zhǔn)，集成了核心庫的語法和語義，其函數(shù)庫可被Fortran、C調(diào)用，形成可移植的信息傳遞程序。MPI提供了適應(yīng)各種并行硬件商的基礎(chǔ)集，它們都能被有效地實(shí)現(xiàn)。這促進(jìn)了硬件廠商可以基于這一系列底層標(biāo)準(zhǔn)來創(chuàng)建高層次的慣例，從而為分布式內(nèi)存交互系統(tǒng)提供并行機(jī)型。MPI還提供了一個簡單易用的可移植接口，極大方便了程序員可以用它在高級機(jī)器上進(jìn)行高性能信息傳遞操作。但MPI接口標(biāo)準(zhǔn)定義的思想與參數(shù)定義的原則秘而不宣，也在一定程度上制約了編程開發(fā)技術(shù)人員思維的廣度、深度與拓展力。

參考文獻(xiàn)

[1]周志強(qiáng)，崔國民，楊嶺，等.一種基于并行計(jì)算的混和算法優(yōu)化有分流換熱網(wǎng)絡(luò)[J/OL].化工學(xué)報：1-20[2021-09-23].http：//kns.cnki.net/kcms/detail/11.1946.TQ.20210913.1556.002.html.

[2]李銘，丁衛(wèi)平，鞠恒榮，等.基于Spark的證據(jù)鄰域粗糙并行分類高效算法[J].南京理工大學(xué)學(xué)報，2021，45（4）：409-419.

[3] CHANG? D， LI? L， CHANG Y，et al.Implementation of MapReduce parallel computing framework based on multi-data fusion sensors and GPU cluster[J]. EURASIP Journal on Advances in Signal Processing，2021（1）：1-14.

[4]鄔江興，祁曉峰，高彥釗.異構(gòu)計(jì)算并行編程模型綜述[J].上海航天（中英文），2021，38（4）：1-11.

[5]王如斌，李瑞遠(yuǎn)，何華均，等.面向海量空間數(shù)據(jù)的分布式距離連接算法[J/OL].計(jì)算機(jī)科學(xué)：1-10[2021-09-23].http：//kns.cnki.net/kcms/detail/50.1075.TP.20210819.1850.054.html.

[6]肖漢，郭寶云，李彩林，等.面向異構(gòu)架構(gòu)的傳遞閉包并行算法[J].計(jì)算機(jī)工程，2021，47（8）：131-139.