劉 鵬 闞亞斌 張世燎

（大連艦艇學(xué)院 大連 116018）

1 引言

MPI是目前集群系統(tǒng)最流行的并行編程環(huán)境之一。而且隨著科學(xué)與工程技術(shù)的發(fā)展，對(duì)計(jì)算量的需求越來越大。因此基于分布存儲(chǔ)的MPI并行編程模型也逐漸被廣泛應(yīng)用。由于MPI是基于消息傳遞的并行模型，所以進(jìn)程之間的通信必須通過顯示的調(diào)用MPI消息傳遞庫中的通信函數(shù)來實(shí)現(xiàn)。因此，如何在MPI并行程序中充分利用MPI提供的函數(shù)庫，如何從MPI函數(shù)庫提供的多種通信函數(shù)中有效的選擇通信函數(shù)，以及如何通過盡量減少通信開銷來提高并行程序性能已成為該領(lǐng)域研究熱點(diǎn)之一。本文兩次改進(jìn)DNS的MPI程序?qū)崿F(xiàn)，減少了程序的通信開銷，提高了程序性能，并通過兩次改進(jìn)提出一個(gè)優(yōu)化MPI并行程序的一般思路與方法。

2 只用Send和Receive調(diào)用來實(shí)現(xiàn)通信部分

盡管MPI函數(shù)庫提供了多種消息傳遞函數(shù)，但點(diǎn)對(duì)點(diǎn)通信仍然是所有通信函數(shù)的基礎(chǔ)[2]，所以本文先完全以點(diǎn)對(duì)點(diǎn)通信函數(shù)來實(shí)現(xiàn)DNS算法的通信部分，用以和改進(jìn)后的程序做比較。由MPI函數(shù)庫為每種阻塞通信形式都提供了相應(yīng)的非阻塞通信形式[3]，盡管非阻塞通信方式可以實(shí)現(xiàn)計(jì)算與通信的重疊，從而提高程序的性能，但是由于DNS算法本身計(jì)算和通信重疊的可能性不大，即使采用非阻塞的通信方式效率也不可能得以提高，所以本文選用阻塞的點(diǎn)對(duì)點(diǎn)通信 MPI＿Send／MPI＿Recv來實(shí)現(xiàn)DNS。

在程序中，由于只采用點(diǎn)對(duì)點(diǎn)通信函數(shù) MPI＿Send／MPI＿Recv，所以起初的分布數(shù)據(jù)是由根進(jìn)程root通過p－1（p：進(jìn)程數(shù)）次 MPI＿Send函數(shù)調(diào)用來將數(shù)據(jù)發(fā)送給其它進(jìn)程的，而非root進(jìn)程通過一次MPI＿Recv函數(shù)調(diào)用來完成數(shù)據(jù)接收。各進(jìn)程運(yùn)算結(jié)束后，由根進(jìn)程root通過p－1次MPI＿Recv函數(shù)調(diào)用來完成數(shù)據(jù)收集，非root進(jìn)程通過一次MPI＿Send函數(shù)調(diào)用來將結(jié)果發(fā)送給root進(jìn)程。

3 通過集群通信函數(shù)來改進(jìn)程序

MPI函數(shù)庫不僅提供了點(diǎn)對(duì)點(diǎn)通信函數(shù)，還提供了豐富的集群通信函數(shù)，這些集群通信函數(shù)和點(diǎn)對(duì)點(diǎn)通信的一個(gè)重要區(qū)別就在于集群通信需要一個(gè)特定組內(nèi)的所有進(jìn)程同時(shí)參加通信，而不是像點(diǎn)對(duì)點(diǎn)通信那樣只涉及到發(fā)送方和接收方兩個(gè)進(jìn)程。集群通信在各個(gè)不同進(jìn)程的調(diào)用形式完全相同，而不像點(diǎn)到點(diǎn)通信那樣在形式上就有發(fā)送和接收的區(qū)別。這就為編程提供了方便性，也提高了程序的可讀性和移植性。

MPI提供的集群通信函數(shù)基本分為四類[4]：

1）一對(duì)多的通信操作，根進(jìn)程發(fā)送相同數(shù)據(jù)到所有進(jìn)程或分發(fā)不同數(shù)據(jù)到所有進(jìn)程。例如廣播操作MPI＿Bcast和數(shù)據(jù)分發(fā)操作MPI＿Scatter。

2）多對(duì)一的通信操作，根進(jìn)程從所有進(jìn)程接收數(shù)據(jù)。例如數(shù)據(jù)聚集操作MPI＿Gather。

3）多對(duì)多的通信操作，進(jìn)程組中各進(jìn)程從每個(gè)進(jìn)程接收數(shù)據(jù)，或者各進(jìn)程向每個(gè)進(jìn)程分發(fā)數(shù)據(jù)并從每個(gè)進(jìn)程接收數(shù)據(jù)。例如多對(duì)多的數(shù)據(jù)聚集操作MPI＿Allgather和多對(duì)多的數(shù)據(jù)分發(fā)與聚集操作MPI＿Alltoall。

4）進(jìn)程組中所有進(jìn)程進(jìn)行全局?jǐn)?shù)據(jù)運(yùn)算，運(yùn)算結(jié)果返回給根進(jìn)程或所有進(jìn)程，例如多對(duì)一的全局運(yùn)算操作MPI＿Reduce和多對(duì)多的全局運(yùn)算操作MPI＿Allreduce。

本文對(duì)程序的第一次改進(jìn)是將通過調(diào)用點(diǎn)對(duì)點(diǎn)通信實(shí)現(xiàn)的數(shù)據(jù)分布和收集操作分別用 MPI＿Scatter和 MPI＿Gather操作來代替。本文對(duì)改進(jìn)前后的程序性能做了對(duì)比，對(duì)比結(jié)果如圖1。

圖1 第一次改進(jìn)后的性能優(yōu)化

由圖1可見，改進(jìn)后程序的運(yùn)行時(shí)間比改進(jìn)前有了明顯的縮短，這說明在實(shí)現(xiàn)集群通信時(shí)使用MPI提供的集群通信函數(shù)比使用點(diǎn)對(duì)點(diǎn)通信函數(shù)的性能好。但是隨著節(jié)點(diǎn)數(shù)的增加，兩者的差距逐漸縮小，甚至當(dāng)節(jié)點(diǎn)數(shù)增加到足夠多時(shí)，修改后程序的運(yùn)行時(shí)間有可能比修改前更長(zhǎng)。這是因?yàn)樵诔绦蛑惺褂眉和ㄐ藕瘮?shù)時(shí)，通信域的參數(shù)直接使用了 MPI＿COMM＿WORLD，而該算法只要部分進(jìn)程通信，因而增加了無效數(shù)據(jù)的傳輸開銷，且該開銷隨著節(jié)點(diǎn)數(shù)的增加而增大。

4 利用派生數(shù)據(jù)類型和建立新通信域來改進(jìn)程序

4.1 通過派生數(shù)據(jù)類型減少通信次數(shù)

盡管MPI庫函數(shù)提供的所有通信函數(shù)在進(jìn)行調(diào)用的時(shí)候，都有一個(gè)參數(shù)count和datatype。這兩個(gè)參數(shù)允許用戶把基本類型相同的多個(gè)數(shù)據(jù)項(xiàng)打包成一個(gè)基本的消息項(xiàng)。但是為了使用這項(xiàng)功能，被打包的數(shù)據(jù)項(xiàng)必須被存儲(chǔ)在連續(xù)的內(nèi)存空間。因此，要發(fā)送存儲(chǔ)在非連續(xù)的內(nèi)存空間中的多個(gè)數(shù)據(jù)項(xiàng)時(shí)，以上方法就無能為力了，就必須考慮使用MPI提供的兩種處理不連續(xù)數(shù)據(jù)的方法[5]：一是允許用戶自定義新的數(shù)據(jù)類型（又稱派生數(shù)據(jù)類型）；二是數(shù)據(jù)的打包與解包，即在發(fā)送方將不連續(xù)的數(shù)據(jù)打包到連續(xù)的區(qū)域，然后發(fā)送出去，在接收方將打包后的連續(xù)數(shù)據(jù)解包到不連續(xù)的存儲(chǔ)空間。程序中由于兩矩陣之間數(shù)據(jù)的不連續(xù)性，導(dǎo)致進(jìn)程間數(shù)據(jù)的傳輸需要兩次通信過程才能完成，降低了程序的性能。因此，本文考慮采用以上兩種方法之一來解決非連續(xù)數(shù)據(jù)的傳輸問題，以進(jìn)一步提高程序效率。鑒于使用數(shù)據(jù)的打包與解包過程開銷相對(duì)過大，因此本文選擇使用派生數(shù)據(jù)類型的方法來改進(jìn)程序。新數(shù)據(jù)類型的聲明，生成與提交如下：

程序中使用數(shù)據(jù)類型生成器MPI＿Type＿Contiguous派生出一個(gè)由兩個(gè)連續(xù)的整型數(shù)據(jù)構(gòu)成的新數(shù)據(jù)類型。這樣，新建立的MPI數(shù)據(jù)類型可用于 MPI的任何通信函數(shù)中。當(dāng)用它的時(shí)候，需要在數(shù)據(jù)類型參數(shù)的位置上寫上派生的數(shù)據(jù)類型。

4.2 通過分割通信域避免無效數(shù)據(jù)的傳輸

由于該程序中數(shù)據(jù)的分布與收集實(shí)際上只需要通信域中的部分進(jìn)程參與，而程序中使用的集群通信函數(shù)的通信域的參數(shù)是預(yù)定義組內(nèi)通信域 MPI＿COMM＿WORLD，這就意味著所有的進(jìn)程都參與了該集群操作，其中n＊n＊（n－1）進(jìn)程發(fā)送和接收了許多無效數(shù)據(jù)，增加了通信開銷。

為了解決這一問題，避免這種沒有必要的開銷，本文考慮使用MPI函數(shù)庫提供的用于建立新通信域與新進(jìn)程組的相關(guān)函數(shù) MPI＿Comm＿split（comm.，color，key，newcomm）。MPI＿Comm＿split對(duì)于通信域comm中的每一個(gè)進(jìn)程都要執(zhí)行，每一個(gè)進(jìn)程都要指定一個(gè)color值，根據(jù)color值的不同，此調(diào)用首先將具有相同color值的進(jìn)程形成一個(gè)新的進(jìn)程組，新產(chǎn)生的通信域與這些進(jìn)程組一一對(duì)應(yīng)，新通信域中各個(gè)進(jìn)程的順序編號(hào)是由key決定的。程序中通過調(diào)用MPI＿Comm＿split函數(shù)建立了一個(gè)由n＊n個(gè)進(jìn)程組成的新進(jìn)程組與通信域。這樣在很大程度上改善了程序的性能。本文對(duì)改進(jìn)前后的程序性能做了對(duì)比，對(duì)比結(jié)果如圖2。

圖2 程序修改前后運(yùn)行時(shí)間比

由圖2可見，程序經(jīng)過兩次改進(jìn)獲得了性能的提升，而且隨著節(jié)點(diǎn)數(shù)的增加，性能提升的幅度越大。

5 優(yōu)化MPI并行程序的一般思路與方法

1）盡量使用MPI函數(shù)庫提供的集群通信函數(shù)。盡管有實(shí)驗(yàn)表明MPI并沒有對(duì)集群通信操作的執(zhí)行性能進(jìn)行加速[6]，但是在MPI并行程序設(shè)計(jì)當(dāng)中，由于開發(fā)人員通常沒有考慮而且也不易設(shè)計(jì)出更優(yōu)化的集群通信操作，所以在一般情況下，MPI并行程序選用MPI提供的集群通信函數(shù)比單純使用點(diǎn)對(duì)點(diǎn)通信函數(shù)能獲得更優(yōu)的性能。而且集群通信函數(shù)給用戶提供了一個(gè)方便地進(jìn)行集群通信的界面，在一定程度上簡(jiǎn)化開發(fā)難度，也提高了程序的可讀性和移植性[7]。

2）通過數(shù)據(jù)打包以減少通信次數(shù)。據(jù)測(cè)試，發(fā)送一次消息的通信開銷相當(dāng)于幾千次計(jì)算量的開銷[8]。然而，在實(shí)際編程的過程中，不可避免地要發(fā)送多個(gè)數(shù)據(jù)，并且這多個(gè)數(shù)據(jù)的基本類型可能相同，也可能不同。在這種情況下，應(yīng)該盡可能地將多個(gè)單獨(dú)的數(shù)據(jù)項(xiàng)打包成一個(gè)單獨(dú)的信息項(xiàng)，從而在保證不減少消息量的 前提下，減少了通信次數(shù)。具體應(yīng)用中可以考慮使用派生數(shù)據(jù)類型或者 MPI＿PACK／MPI＿UNPACK等方法將數(shù)據(jù)打包，從而降低通信過程中的開銷。

3）考慮通過建立新的進(jìn)程組和通信域來避免無效通信。進(jìn)程組是通信域的組成部分，MPI的通信是在通信域的控制和維護(hù)下進(jìn)行的，因此所有的MPI通信都用到通信域這一參數(shù)。由于MPI預(yù)定義組內(nèi)通信域是MPI＿COMM＿WORLD，它包括所有的進(jìn)程。而程序中經(jīng)常會(huì)遇到部分進(jìn)程需要通信的問題，無論選擇點(diǎn)對(duì)點(diǎn)通信還是簡(jiǎn)單地使用集群通信都難以得到較好的性能。為了解決這一問題，可以通過對(duì)通信域的重組，以非常簡(jiǎn)單的方式方便地實(shí)現(xiàn)通信任務(wù)的劃分，從而提高通信效率[9]。

4）選取適當(dāng)?shù)耐ㄐ欧绞?，充分發(fā)掘程序中通信與計(jì)算重疊的可能性。MPI中每種阻塞通信函數(shù)都有與其對(duì)應(yīng)的非阻塞通信函數(shù)。程序中由于通信經(jīng)常需要較長(zhǎng)的時(shí)間，在阻塞通信結(jié)束之前，處理器只能等待，這樣就浪費(fèi)了處理器的計(jì)算資源。對(duì)于非阻塞通信，不必等到通信操作完成便可以返回，這樣處理器可以同時(shí)進(jìn)行計(jì)算操作，實(shí)現(xiàn)了計(jì)算與通信的重疊，大大地提高了程序執(zhí)行的效率[10]。然而，要合理地選擇通信方式需要開發(fā)人員對(duì)程序中計(jì)算與通信重疊的可能性進(jìn)行詳細(xì)的分析，由于DNS算法中計(jì)算與通信重疊的可能性不大，因此在對(duì)以上程序優(yōu)化的過程中并未使用該優(yōu)化方法。

6 結(jié)語

本文討論了MPI并行程序的性能優(yōu)化問題，尤其是其中的通信優(yōu)化問題，并通過具體的實(shí)驗(yàn)為MPI程序開發(fā)人員提出了優(yōu)化MPI并行程序的一般思路與方法。本文設(shè)計(jì)的并行程序有很好的加速效果，適合于大規(guī)?？茖W(xué)與工程計(jì)算。未來的工作：對(duì)虛擬進(jìn)程拓?fù)溥M(jìn)行深入的研究，以簡(jiǎn)化并行程序設(shè)計(jì)，提高程序效率；對(duì) MPI通信函數(shù)的源碼進(jìn)行分析與研究，設(shè)計(jì)效率更高的通信函數(shù)，尤其是集群通信函數(shù)；通過對(duì)MPI中的動(dòng)態(tài)進(jìn)程管理作深入的研究，分析如何通過有效地利用動(dòng)態(tài)進(jìn)程管理以提高M(jìn)PI并行程序的效率。

[1]Ghanbari M.The Cross－search Algorithm for Motion Estimation[J].IEEE Trans.Commun.1990.38：950－953.

[2]羅省賢，李錄明.基于MPI的并行計(jì)算集群通信及應(yīng)用[J].計(jì)算機(jī)應(yīng)用，2003，23（6）：51－53.

[3]羅省賢，何大可.基于MPI的網(wǎng)絡(luò)并行計(jì)算環(huán)境及應(yīng)用[M].成都：西南交通大學(xué)出版社，2001：35－44.

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

[5]陳國(guó)良，吳俊敏，章鋒等.并行計(jì)算機(jī)體系結(jié)構(gòu)[M].北京：高等教育出版社，2002：125－－146.

[6]任波，王乘.MPI集群通信性能分析[J].計(jì)算機(jī)工程，2004，30（11）：71－73.

[7]蔣英，雷永梅.MPI中的3種數(shù)據(jù)打包發(fā)送方式及其性能分析[J].計(jì)算機(jī)工程，2002，28（8）：261－263.

[8]都志輝.高性能計(jì)算并行編程技術(shù)[M].北京：清華大學(xué)出版社，2001：178－187.

[9]雒戰(zhàn)平，劉之行.有限元并行計(jì)算的MPI程序設(shè)計(jì)[J].西安交通大學(xué)學(xué)報(bào)，2004，38（8）：873－876.

[10]楊愛民，劉韌.集群系統(tǒng)中基于MPI的并行GMRES（m）計(jì)算通信的研究及應(yīng)用[J].微電子學(xué)與計(jì)算機(jī)，2009，26（9）：129－131.