大規(guī)模稀疏矩陣在并行應用中的通信優(yōu)化研究

摘要：為了提高并行應用系統的效率，研究了針對大型稀疏矩陣的壓縮通信問題。通過對矩陣壓縮通信過程中矩陣稀疏度、網絡帶寬、處理器計算能力之間的關系進行定量分析，推導出稀疏度下界計算公式。通過對不同稀疏度情況下算法所取得的效率進行分析，總結出壓縮通信中稀疏度與通信效率之間的函數關系。結合油藏數值模擬的應用實例，設計實現了稀疏矩陣的壓縮通信算法。結果表明本算法在稀疏矩陣通信方面效率有明顯的提高。

關鍵詞：并行計算；通信優(yōu)化；油藏數值模擬；稀疏度

中圖分類號：TP301．6文獻標志碼：A

文章編號：1001－3695(2008)01－0074－04



并行計算在油藏數值模擬、數值天氣預報等工程和科學計算領域得到越來越廣泛的應用。反過來，工程（科學）計算的發(fā)展對并行程序性能的要求也越來越高。并行程序性能優(yōu)化的一個主要方向就是通信優(yōu)化。其中包括減少通信量和優(yōu)化通信調度等方面。在工程和科學計算中，矩陣運算是一種普遍存在的計算形式，其運算結果或計算過程中的矩陣通常是稀疏的。本文通過對計算中的稀疏矩陣進行壓縮通信，減少需要傳輸的數據量，從而提高通信效率。目前國外這方面的研究主要集中在對矩陣的壓縮算法優(yōu)化上[1，2]。國內在油藏模擬并行化過程中也有使用壓縮通信的[8]，但沒有對壓縮通信進行定量研究。本文設計實現了稀疏矩陣的壓縮通信算法。該算法的基本思路是將計算過程中的稀疏矩陣分步壓縮，然后將壓縮后不同數據類型、不同地址空間中的分散數據打包到一個連續(xù)的地址空間集中發(fā)送；接收進程對接收到的數據采取解包、解壓縮的方式還原出發(fā)送數據。這種通信方式從實質上減少了通信數據量，從而降低程序執(zhí)行過程中通信的代價。然而發(fā)送端對稀疏矩陣的壓縮、打包需要消耗一定的處理時間；接收端對數據解包、解壓縮也需要消耗一定的計算時間。這就造成了減少實際通信時間的同時會增加一定的數據處理時間。這里給出一種性能評估方法，通過對時間復雜度和空間復雜度的計算給出一個壓縮通信的稀疏度臨界值。以這個稀疏度臨界值為依據對矩陣進行動態(tài)壓縮通信。

1稀疏矩陣的壓縮通信技術

對大規(guī)模稀疏矩陣分塊進行壓縮、打包，然后集中傳輸，接收端進行解包、解壓縮，可有效地提高稀疏矩陣的通信效率。然而，并不是對任何數據都進行打包。因為如果一個分塊的稀疏度不夠大的話，采用壓縮的方法反而會增加通信代價。給出一個稀疏度臨界值，在壓縮打包過程中動態(tài)判斷一個數據塊是否采用壓縮方式。這個稀疏度臨界值是與軟硬件環(huán)境相關的，總通信時間包括消息處理時間和實際傳輸時間。消息處理時間與算法及CPU的處理能力有關；實際傳輸時間與網絡帶寬有關。消息處理時間的增量必須小于實際傳輸時間的減少量，從而可以推導出稀疏度和帶寬及CPU處理能力的關系。以下詳細介紹性能評估方法與稀疏度臨界值計算公式、稀疏矩陣壓縮技術、MPI打包與解包函數。

1．1矩陣稀疏度臨界值計算方法

式（8）中網絡帶寬BW、算法每字節(jié)壓縮和解壓縮消耗時間l′1均可通過實驗測得。對于一定的硬件環(huán)境和算法可以認為BW、l′1總是一定的。因此可以確定矩陣稀疏度的下界值。只有矩陣稀疏度sparsity大于這個下界值時，使用壓縮傳輸才能提高通信效率。也就是說對于一定的軟硬件環(huán)境，矩陣的稀疏度達到多大時采用壓縮通信的方法可以提升通信效率。

1．2稀疏矩陣的壓縮方法

為了減小消息發(fā)送的數據量，需要對稀疏矩陣進行壓縮。其中最基本的方法是三元組表示法[5]：在記錄非零元素的同時，記錄非零元素所在的行號、列號，這樣才能確定一個非零元素是矩陣中的哪一個元素。其中每一個非零元素所在的行號、列號和值組成一個三元組(i，j，aij)，并由此三元組惟一確定。如果將表示稀疏矩陣的非零元素的三元組按行優(yōu)先(或列優(yōu)先)的順序排列(跳過零元素)，并依次存放在向量中，這種稀疏矩陣的順序存儲結構稱為三元組表。圖1(a)所示的稀疏矩陣A的三元組表表示如圖1(b)所示。

以上是傳統的稀疏矩陣壓縮方法。為了能方便地按行列的方式訪問這個結構，采用了將行列都存儲的方式。在這里，為了進一步減少消息傳輸中的數據量，將一個二維矩陣轉換為一維數組。壓縮時可以只記錄數組的一維索引。如上所述的矩陣A，其中有非零元素6個，三元組的記錄方法除了要記錄非零元素外，還需要記錄2×6個整數作為其行和列的索引。如果將該矩陣轉換為一維數組則只需要記錄6個整數作為其索引，如圖1(c)所示。

如果用d表示壓縮后索引數據占用的空間，那么壓縮后數據占用的空間大小為M′+d，則壓縮率可表示為R=M/(M′+d)。

1．3數據的打包傳輸

MPI通信庫的打包/解包函數為發(fā)送不連續(xù)數據提供了一種可能的實現方法[5]。在這種系統下，用戶在發(fā)送前顯式地把數據包裝到一個連續(xù)的緩沖區(qū)，在接收后從連續(xù)緩沖區(qū)中解包。例如在本算法中，一個消息可以被分成幾個部分來接收，后面部分數據的接收操作可能依賴于前一部分的內容。 尤其是在程序運行期間，這些信息是動態(tài)的，而且只有發(fā)送節(jié)點知道這些數據的具體長度、格式等信息。如果用自定義數據類型的方法是非常不方便的。這時可以將這些與信息格式相關的數據打包到連續(xù)數據空間的開始，真正要傳輸的數據信息緊接著格式信息打包。這樣接收端只要查看數據包的前幾個信息就可以確定數據的接收長度、格式以及如何對數據進行處理等信息。

1）MPI的數據打包函數

MPI_PACK(inbuf， incount， datatype， outbuf，outcount， position， comm)

IN inbuf輸入緩沖區(qū)起始

IN incount輸入數據項數目

IN datatype每個輸入數據項的類型

OUT outbuf輸出緩沖區(qū)開始

IN outcount輸出緩沖區(qū)大小

INOUT position緩沖區(qū)當前位置

IN comm 打包消息的通信子

MPI_PACK將由inbuf、incount、datatype指定的發(fā)送緩沖區(qū)中的消息打包到outbuf和outcount指定的緩沖區(qū)空間。輸入緩沖區(qū)可以是MPI_SEND允許的任何通信緩沖區(qū)。輸出緩沖區(qū)是一個連續(xù)的存儲空間，含有outcount個字節(jié)，起始地址為outbuf (長度是以字節(jié)為單位的，而不是以元素為單位，就像它是一個為MPI_PACKED類型的通信而準備的緩沖區(qū))。入口參數position的值是輸出緩沖區(qū)中用于打包的起始地址，其值隨著打包消息的大小而增加；出口參數position的值是被打包的消息占用的輸出緩沖區(qū)后面的第一個地址。comm參數是用于發(fā)送數據的通信子。

2）MPI的數據解包函數

MPI_UNPACK(inbuf， insize， position， outbuf，outcount， datatype， comm)

IN inbuf輸入緩沖區(qū)起始

IN insize輸入數據項數目

INOUT position 緩沖區(qū)當前位置

OUT outbuf輸出緩沖區(qū)開始

IN outcount輸出緩沖區(qū)大小

IN datatype每個輸入數據項的類型

IN comm打包消息的通信子

MPI_UNPACK從inbuf和insize指定的緩沖區(qū)空間解包一個消息到outbuf、outcount、datatype指定的緩沖區(qū)中。輸出緩沖區(qū)可以是MPI_RECV允許的任何通信緩沖區(qū)。輸入緩沖區(qū)是一個連續(xù)的存儲空間，大小為insize字節(jié)，開始地址為inbuf。入口參數position的值是輸出緩沖區(qū)中被打包消息占用的起始地址。comm參數是用于接收消息的通信子。

2算法實現

針對油藏數值模擬的應用實例，本文實現了稀疏矩陣的壓縮通信算法。圖2、3所示的是發(fā)送和接收的流程圖。對于大型二維或三維矩陣，即在每一維的長度都很大的情況下采取按行打包的方式，如三維矩陣C(L ，M， N)，在以N、M為上限的二重循環(huán)中，每次打包C矩陣的L個元素，最后一次性將打包緩存區(qū)的數據發(fā)送到接收端。下面的發(fā)送和接收都是針對矩陣中的行進行的，也就是一個一維數組進行的。

發(fā)送端首先遍歷要發(fā)送的矩陣，同時對數據進行壓縮，將非零元素記錄到壓縮數組COM，相應非零元素的索引記錄到索引數組COMINDEX的對應位置，非零元素的總個數記錄到一個整型變量COMLEN。這個過程是必需的，因為至少要對數組處理一遍才知道該怎樣發(fā)送它。

3稀疏度與通信性能關系及實例

稀疏度的下界計算公式只能提供不同軟硬件環(huán)境下采用壓縮通信的臨界稀疏度。分析和優(yōu)化并行程序的性能時，往往需要預測優(yōu)化后帶來的效率，以便權衡是否值得采用優(yōu)化技術。例如，在本方法中往往希望知道矩陣稀疏度和性能增長效率之間的關系。為此本文對上述實驗數據進行分析，并從中擬合出效率與稀疏度之間的函數關系。實驗環(huán)境為基于SMP的千億次計算機集群系統。其中每16個計算節(jié)點各擁有兩個Intel Xeon 2.8 GHz CPU，節(jié)點之間由千兆以太網連接；該集群的計算理論峰值為1 792億次，INPACK實測峰值為995億次。

測試數據來自油藏數值模擬中的真實數據。其中模擬網格規(guī)模為364、相數為3、組分數為13。如表1中的數據所示，本文對7個不同的稀疏度進行了測試，每一次測試的數據是對模擬迭代中的51次濃度矩陣C(364，13，3)進行取樣，總計723 996個雙精度浮點數。為了觀察在稀疏度很小情況下的傳輸效率，又根據上次采樣數據（40.16%）手動生成一個稀疏度為4.92%的矩陣進行測試。

由表1中的數據可以看出，在稀疏度達到99.45%時，程序傳輸效率提高了33.02%。隨著測試矩陣稀疏度的下降，程序取得的通信效率也在下降。圖5中的實驗數據曲線是以表中稀疏度和相應效率提升百分比繪制的。可以看出，在稀疏度下降到0.52左右時，程序的效率提升百分比降為0。這個值要大于公式計算出的稀疏度下限0.37。這是由于系統中的其他開銷造成的。

4結束語

大規(guī)模并行應用系統中普遍存在著對矩陣的操作。實際應用中，這些矩陣通常是稀疏矩陣。有效地處理這些零元素，有利于提高并行程序的性能。本文給出了一個通過對稀疏矩陣壓縮通信的方法，定量分析解決了稀疏矩陣壓縮傳輸中稀疏度的臨界值問題，根據稀疏度臨界值的動態(tài)判斷實現了壓縮傳輸算法，并給出稀疏度與傳輸效率之間的關系。通過對油藏數值模擬中的實時數據測試表明，這種壓縮發(fā)送的方法能顯著地提高節(jié)點間數據通信的效率。為了使壓縮矩陣的時間盡量少，本文采用了最簡單的壓縮處理方法。下一步的工作準備尋找更加快速、高效的數據壓縮算法，將本方法推廣到一般數據的壓縮通信過程中。

參考文獻：

［1］KE Jian，BURTSCHER M，SPEIGHT E.Runtime compression of MPI messages to improve the performance and scalability of parallel applications[C]//Proc of High Performance Computing，Networking and Storage Conference.2004.

[2]LIN Chun yuan，CHUNG Y C.Efficient data compression methods for multidimensional sparse array operations based on the EKMR scheme[J].IEEE Trans on Computers，2003， 52(12):1640 1646.

[3]GROPP W，DOSS N，SKJELLUM A.MPICH model MPI implementation reference manual，UC－405.[R].[S.l.]:Argonne National Laboratory，Mathematics and Computer Science，2005.

[4]BAI Z，DEMMEL J，DONGARRA J，et al.Templates for the solution of algebraic eigenvalue problems:a practical guide[C]//Proc of SIAM.2000:780 784.

[5]都志輝.高性能計算并行編程技術——MPI并行程序設計[M].北京:清華大學出版社，2001：177 180.

[6]曹建文，潘峰，姚繼鋒，等.并行油藏模擬軟件的實現及在國產高性能計算機上的應用[J].計算機研究與發(fā)展，2002，39（8）：973－980.

[7]曹建文，孫家昶.油藏數值模擬軟件的并行化探索[C]//全國第六屆并行算法學術會議論文集.長沙：國防科技大學出版社，2000:246－250.

[8]楊耀忠，韓子臣，周維四.多層二維二相油藏數值模擬并行技術[J].油氣地質與采收率，2001，8(6)：52－54.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”