二維泊松問題的并行共軛梯度算法

摘要：該論文研究了利用并行共軛梯度算法求解二維泊松方程的方法，在由24臺微機組成的機群上進行了實驗。實驗數據表明并行共軛梯度算法適用于求解二維泊松方程，它具有收斂快，可擴展性強的特點。在實驗的基礎上提出并驗證了適用于并行共軛梯度算法的合理計算節點數的選擇函數。

關鍵詞：并行計算；共軛梯度算法；二維泊松方程

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)27-1937-04

Parallel Conjugate Gradient Algorithm of 2D Poisson Problem

ZHAO Hang-tao

(1.Jiangnan University，Wuxi 214122，China;2.Wuxi Professional College of Science and Technology，Wuxi 214028，China)

Abstract: This thesis researches on using parallel conjugate gradient algorithm to solve 2D Possion problems，which is experimented on cluster of workstation made up of 24 micro-computers.The data of experiment indicates that parallel conjugate gradient algorithm is applicable to solve 2D Possion problems. And the algorithm is quick in astringency and good in scalability.The thesis brings forth and proves selection functions of reasonable unit of computation node applied to parallel conjugate gradient algorithm on thebase of experiments.

Key words: parallel computing;conjugate gradient algorithm;2D poisson problem

1 二維泊松問題

二維泊松問題是求解一個簡單的橢圓型偏微分方程，它是解決流體、靜電學、均衡熱流等物理問題的重要方法，在工程領域的數值計算中得到了廣泛的應用。

求解二維泊松方程的方法主要有：有限差分法、有限元方法、邊界元法和矩量法。考慮到用邊界元法和矩量法得到的系數矩陣不是稀疏矩陣，運算量比較大，使用有限元方法則要進行大矩陣的逆運算，運算量也比較大[1]，而用有限差分法得到的系數矩陣是一個對稱正定稀疏矩陣，不用求矩陣的逆，計算的工作量比較小，并適合于并行計算[2]。

有限差分法求解二維泊松方程的基本原理是用差分代替微分，只要自變量的增量很小，各階的差分就近似等于同階的微商，從而達到離散微分方程的目的。有限差分法是求解二維泊松方程的基本過程：首先用網格將場區域進行離散化，用各離散點上待求函數的差分方程近似該點的偏微分方程，同時把要求解的邊值問題轉化為求一組相應的差分方程問題。特別要提出的是二維泊松方程經有限差分法轉化后得到的差分方程組的系數矩陣是對稱正定稀疏矩陣，因此可以使用并行共軛梯度迭代法求解此差分方程組[3]，得到各離散點上待求函數值，即得到所求邊值問題的數值解。本論文重點研究了在普通機群中，使用并行共軛梯度迭代法求解直維泊松問題，并對實驗結果進行了分析，最后找到了一個在機群中選擇合理計算節點的函數。

2 二維泊松方程的有限差分線性方程組的推導

二維泊松方程

3 共軛梯度算法

顯然式（3）中的系數矩陣是對稱正定稀疏矩陣，可以使用迭代算法求解式（3）。求解式（3）的迭代算法主要有雅可比法、超松弛法、Gauss-Seidel法和共軛梯度法等，其中共軛梯度法的收斂速度最快，在工程計算中得致函廣泛的應用[4-5]。共軛梯度迭代算法如下：

其中， 為共軛方向向量，r為剩余向量。對于n階對稱正定矩陣，上述算法至多r+1步收斂。在運算中每次迭代的運算相同，一次迭代主要包括一次矩陣與向量的乘（n2次浮點乘和n2次浮點加法）和10n次浮點運算，假設浮點乘和浮點加所需的時間相同，此算法每次迭代的計算量約是：(2n2+10n)f，其中f為一次浮點運算的平均時間；另外在每次迭運算中矩陣A保持不變。根據上述特點，共軛梯度算法十分適合并行計算，可以將A矩陣按行分解到每個節點上，在各個節點上分別計算矩陣與向量的積，然后通過全局通訊將結果分發到每個節點上。并行共軛梯度算法如下：

上述并行算法和前面的串行算法相比，每次迭代的計算量沒有變化，但是在每次迭代運算中要進行一次全局收集和二次全局歸約運算。機群內一次全局收集操作的通訊成本為Tp=Tslogp+n(p-1)Tw，一次全局歸約操作的通訊成本Tp=2(Ts logp +nTw)+nf，其中Ts為通信啟動時間，p為機群內節點的個數，Tw為每字節的通訊時間，n為問題的規模（向量的大小）。上述并行算法每次迭代的總通訊成本為

雖然Ts比Tw大好幾倍，但由于通常用于工程計算的機群節點數比較少（p<24），問題規模比較大（n>512），因此5Tslogp的值可以忽略不計，每次迭代的通訊成本可以簡化為

顯然Tp和n（問題規模）與p（節點數）成正比。此并行算法的加速比可以寫出成

s=(2n2+10n)f /( n(p+3) Tw +((2n2+10n)/p)f)。

4 實驗與數值分析

以求解二維三溫能量方程組[6，8]為例，使用中心差分格式進行離散，網格的規模分別取512*512、1024*1024、2048*2048和10000*10000，離散后形成大型對稱正定稀疏線性方程組，按行劃分數據，采用并行共軛梯度算法求解。實驗的機群由16臺聯想啟天Intel P42.0GHZ，512MDDR內存的微機組成，局域網采用D_Linke100M交換機，Win2000操作系統[9]，并行編程環境為MPICH2.0[7]，程序使用VC6.0語言編寫。實驗結果見表1。

通過表1數據表明，并行共軛梯度算法對于泊松方程的求解是十分有效的，和并行雅可比迭代法相比可以大大縮短其計算時間。例如矩陣規模為10000時，使用16個節點并行計算，用了37.0784秒，只有串行算法耗時的十分之一都不到。為了更好地分析并行共軛梯度算法的性能，根據表1數據計算出了對應的加速比和并行效率，見表2。

通過表2可以看出，并行共軛梯度算法具有較好的擴展性。當問題規模一定時，隨著計算節點的增加加速比增大，計算節點的并行效率下降，當節點數超過某個值后，由于機群內通訊量急劇增加，加速比開始降低。例如，問題規模為512時，使用8個計算節點時具有最高的加速比，隨后加速比逐漸減小。當節點的數量一定時，隨著問題規模的增加，加速比增加，每個節點的并行效率逐漸也增大。

5 并行共軛梯度算法的合理計算節點數選擇函數

在一般的工程數值分析中，矩陣的規模是變化，機群計算節點也是不固定的，一般要根據計算需要臨時搭建機群，因此在實際工程計算如何科學得確定機群節點的數量顯得十分迫切。

從表2中可以看出，當加速比達最大時，并行計算的成本大幅度增加（節點數量），因此加速比最大時的節點數并不是合理的。同時可以在表2中發現，在不同規模下可以找到即加速比比較大，計算成本又比較低的節點數，即合理節點數，根據一般經驗計算節點的平行效率在0.75左右時，機群的節點數是比較合理的，機群的計算成本是比較低。例如在網格規模為512時合理節點數為4個節點、網格規模為2048*2048時合理節點數為8個節點。據此對表2中的數據采用對數方程擬合法，建立如下的合理節點數選擇函數：

根據公式（4）對網格規模為6000*6000的對稱正定稀疏矩陣進行測試驗證。根據公式（4）計算可得合理節點數約為12.3948。在機群上進行了實驗，實驗結果見表3。

表3數據表明網格規模為6000*6000的合理計算節點約為12。實驗結果與公式（4）的計算結果基本一致，說明建立的合理計算節點數選擇函數對于機群并行共軛梯度算法是有效的。對于不同的機群，由于網絡性能和計算性能不同，合理計算節點的選擇函數是不同的，可以通過實驗找到適合的選擇函數。

5 結論

通過實驗可以得出如下結論：在普通機群中，使用并行共軛梯度算法求解二維泊松方程可以大幅度降低計算時間；當計算節點數量不變，問題規模增加時，算法的加速比提高，當總是規模不變，計算節點增加時，在一定范圍內加速比增加，但超過某個值后加速比反而下降；通過實驗可以得到一個適于機群的選擇合理計算節點數的算法。

參考文獻：

[1] George I，Costache.Finite element method applid to skin-effect problems is strip transmission lines[J].IEEe Trans.MIT，1987，35(12):1009-1013.

[2] M Naghed and I Wolff.Equivalent capacitances of coplanar waveguids discontinouties and interdigitated capacitors using a 3d finite difference method[J].IEEE Trans.On MTT，1990，38(12).

[3] Chronopoulos A T，Cear C W.On the efficient implementation of pre-condition s-step conjugate gradient methods on mulitiprocessors with memory hierarchy[J]，Parallel Computing，1989，11:37-53.

[4] Dazevedo E.，Eijkhout V.，Romaine C.，Reducing communication costs in the conjugate gradient algorithm on distributed memory multiprocessors[J]. University Tennessce，Knoxville:LAPACK Working Note 56，1992.

[5] Merurant G.，Multitasking the conjugate gradient on the Cray X-MP/48[J].Parallel Computing，1987，5(2):267-280.

[6] Duan Qing-sheng，Yuan Guo-xing.The study of solutions for difference system of 2-D heat conduction coupled three-temper-ature[J].Chinese Journal of Computational Physics，2001，18(1):75-81(in chinese).

[7] 王小牛，馮百明.基于LINUX的NOW系統的構建[J].西北師范大學學報(自然科學版)，2002(1):35-37.

[8] 袁光偉，杭旭旭凳.熱傳導方程基于界面修正的迭代并行計算方法[J].數值計算與計算機應用，2006(1):67-60.

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