李太全，陳 威 (長江大學(xué)物理科學(xué)與技術(shù)學(xué)院，湖北 荊州 434023)

隱含變向時域有限差分方法的MPI實現(xiàn)

李太全，陳 威 (長江大學(xué)物理科學(xué)與技術(shù)學(xué)院，湖北 荊州 434023)

在MPI環(huán)境中，研究了適合于隱含變向時域有限差分算法(ADI-FDTD)的虛擬拓?fù)浜凸?jié)點間的數(shù)據(jù)通信。將并行對角占優(yōu)算法(PDD)應(yīng)用于ADI-FDTD，極大地減少了并行節(jié)點間的數(shù)據(jù)通信。進(jìn)一步分析數(shù)據(jù)通信的傳輸速率，提出了數(shù)據(jù)成批傳送方案，實現(xiàn)了ADI-FDTD的高效率并行計算。

MPI；隱含變向時域有限差分算法;三對角方程組;并行對角占優(yōu)算法

時域有限差分算法(FDTD)[1]在電磁場輻射和散射、微波電路以及電磁兼容等領(lǐng)域獲得了非常成功的應(yīng)用。然而，較長的計算時間和較大的存儲空間是FDTD在PC系統(tǒng)上求解復(fù)雜電磁場問題的瓶頸。 解決這一問題的有效方法之一是采用并行FDTD方法[2-3]實現(xiàn)FDTD的分布運算。隨著計算機網(wǎng)絡(luò)的迅速發(fā)展，基于消息傳遞接口(MPI)[4]的編程環(huán)境被廣泛采用，是目前最重要的并行編程工具，該系統(tǒng)具有移植性好、功能強大、效率高等諸多優(yōu)點，已經(jīng)成為國際上一種并行程序標(biāo)準(zhǔn)，被越來越多的硬件生產(chǎn)廠商和計算機用戶所接受。

顯式FDTD的時間步長受Courant條件限制，在精細(xì)結(jié)構(gòu)的電磁分析中，由于空間步長遠(yuǎn)小于電磁波波長，其計算效率顯著降低。隱含變向時域有限差分算法(ADI-FDTD)[5-6]的提出，打破Courant條件限制，計算效率得到了明顯提高。然而，ADI-FDTD算法需要求解一組三對角方程，這組方程導(dǎo)致了并行ADI-FDTD方法復(fù)雜化。筆者將應(yīng)用三對角矩陣并行算法，實現(xiàn)ADI-FDTD的并行計算。

1 子區(qū)域劃分與虛擬拓?fù)?/h2>

將整個FDTD 計算區(qū)域劃分為若干個子區(qū)域，每個進(jìn)程(或線程)計算其中的一個子區(qū)域，各個進(jìn)程之間通過通信傳遞交界面上的電磁場量，以實現(xiàn)FDTD 中電磁場量的遞推。子區(qū)域的分解方法應(yīng)根據(jù)計算區(qū)域的尺度，在權(quán)衡運算開銷和通信開銷的前提下選擇劃分方案。一般采用圖1所示的方法[2]，將計算區(qū)域沿著3個方向分解為子區(qū)域。MPI提供了迪卡兒拓?fù)浜蛨D拓?fù)洌鶕?jù)上述的子區(qū)域劃分，每個子區(qū)域?qū)?yīng)一個進(jìn)程，而每個進(jìn)程對應(yīng)拓?fù)渲械囊粋€節(jié)點，所以，應(yīng)選擇笛卡兒拓?fù)洹?/p>

2 ADI-FDTD的三對角方程組與PDD算法

隱含變向時域有限差分算法將一個時間步的電磁場量遞推分為2個亞時間步[4]，在每個亞時間步的遞推運算中，6個電磁場分量有3個需要求解三對角方程，如果在第一個亞時間步選定Ex、Ey、Ez應(yīng)用方程組求解，則Hx、Hy、Hz可以直接計算。以Ex為例，對應(yīng)的三對角方程可表示為：

(1)

式中，α、β、γ、p、q是與空間步長、時間步長和介質(zhì)的電磁特性相關(guān)的系數(shù)。

第2個亞時間步計算式與式(1)類似。關(guān)于方程組(1)的求解，由于在z軸方向上Ex相互牽連，需要將圖1中沿z軸位于同一直線的子區(qū)域合并考慮，如圖2所示。

圖1 子區(qū)域分解 圖2 求解Ex相關(guān)聯(lián)的子區(qū)域

求解方程(1)可采用并行對角占優(yōu)算法(PDD)[7]。對確定的i、j，方程(1)可表示如下：

(2)

將矩陣A分解為：

V=[αmum,γm-1um-1,…,αm(Np-1)um(Np-1),γm(Np-1)um(Np-1)-1]

U=[um-1,um,…,um(Np-1)-1,um(Np-1)]

式中，A(p)為m×m階三對角矩陣，對應(yīng)圖2中的一個子區(qū)域；(p)表示子區(qū)域編號；um為Nz個元素的列向量，且除第n元素為1外，其他元素均為0。

式(2)的解可以寫成：

(3)

(4)

(5)

αk=-Δt/(μ(i+0.5,j,k-0.5)Δz2)

γk=-Δt(μ(i+0.5,j,k+0.5)Δz2)

(6)

1)確定當(dāng)前節(jié)點p對應(yīng)子區(qū)域中網(wǎng)格i、j對應(yīng)的A(p)和d(p)；

移動網(wǎng)絡(luò)的網(wǎng)絡(luò)節(jié)點是人，而不是網(wǎng)頁，也就是說人人都是數(shù)據(jù)的產(chǎn)生著和攜帶者，無論是微信、照片、微博等任何網(wǎng)絡(luò)相聯(lián)系的，都已成為數(shù)據(jù)的產(chǎn)生者。所涉及到的資料總量是目前任何一個軟件都不可能接受、管理、處理、總結(jié)的。有國外機構(gòu)預(yù)測，全球的數(shù)據(jù)量將在2020年擴大到目前的五十倍，這樣就意味著大數(shù)據(jù)時代的容量將會更多、更大、更難處理。

2)求解方程組：

(7)

4)求解方程組：

(8)

(9)

tC=2NxNytα+12NxNytβ

(10)

式中，tα為通信響應(yīng)時間；tβ為一字節(jié)數(shù)據(jù)的傳輸時間(浮點數(shù)為4字節(jié)單精度實數(shù))。對試驗網(wǎng)絡(luò)測試，tα=26.3μs，tβ=0.0875μs。由于tα?tβ，將數(shù)據(jù)成批傳送會大大提高通信效率。為此，采用如下步驟求解方程(1)：

3)對i、j循環(huán)，求解方程(8)，并存儲y0，y1；

這樣， 原來的2×Ny×Ny次數(shù)據(jù)通信減少為2次，此時通信時間開銷為tC=2tα+12NxNytβ。

3 效率分析與數(shù)值試驗

設(shè)子區(qū)域內(nèi)FDTD網(wǎng)格數(shù)為Nx×Ny×Nz，在一次循環(huán)迭代中，運算開銷約為6(te+th)NxNyNz，其中te、th分別為一個電場、磁場計算所需時間，通信開銷約為18tα+28tβ(NxNy+NyNz+NzNy)，算法的效率可以表示為:

圖3 在Nx=Ny=Nz=N時，效率與網(wǎng)格數(shù)N的關(guān)系

可見，當(dāng)子區(qū)域的網(wǎng)格數(shù)Nx=Ny=Nz時，算法效率最高。

由個人計算機組成10個節(jié)點的集群系統(tǒng)，每個節(jié)點的CPU主頻2GHz，內(nèi)存1024MHz，100/1000M網(wǎng)卡，100M交換機。在該系統(tǒng)中測得，te=0.583μs，th=0.104μs，tα=26.3μs，tβ=0.0875μs。在該系統(tǒng)中，取Nx=Ny=Nz=N時，算法的效率如圖3所示，在N>25時，算法已具有較高的效率。進(jìn)一步檢驗算法的效率，筆者計算了如圖4所示的環(huán)形天線。在相對介電常數(shù)為εr=4.5、邊長為1000m、厚為h=50m的正方形基板上，有一個線寬b=12m、邊長a=500m的正方形環(huán)帶狀線天線，激勵點位于底邊的中點E。激勵源輸出阻抗Z=100Ω，輸出電壓v(t)=exp(-4π(t-t0)2/τ2)，其中τ=100ps。將整個空間劃分為Nx×Ny×Nz=300×40×300網(wǎng)格，且Δx=Δy=4m，Δz=10m。取時間步長Δt=2×Δx/c，將空間在XY面等分為2、4、9個子區(qū)域。對該系統(tǒng)進(jìn)行200時間步迭代，運算時間如表1所示。

表1 不同區(qū)域劃分的運算時間比較

圖5是在上述4種情況下，分別得到天線輸入口的S11，4種情況下的良好一致性說明了上述算法的正確性。

4 結(jié) 語

采用MPI編程環(huán)境，實現(xiàn)了ADI-FDTD的并行計算。將PDD算法應(yīng)用于并行ADI-FDTD，極大地減少了節(jié)點間的數(shù)據(jù)傳送量，減小了通信開銷。并采用交換信息的成批傳送，減少通信次數(shù)，雖然需要額外內(nèi)存開銷暫存臨時數(shù)據(jù)，但可以顯著提高了計算效率。

圖4 環(huán)形天線結(jié)構(gòu) 圖5 4種情況下天線的S11

[1]葛德彪, 閆玉波.電磁波時域有限差分方法[M].西安：西安電子科技大學(xué)出版社, 2002.

[2] 張玉, 李斌, 梁昌洪. PC集群系統(tǒng)中MPI并行FDTD 性能研究[J].電子學(xué)報, 2005, 33(9):1694-1697.

[3] 楊利霞, 葛德彪, 鄭奎松，等.電各向異性介質(zhì)FDTD 并行算法的研究[J].電波科學(xué)學(xué)報, 2006, 21(1):43-48.

[4] 都志輝.高性能計算并行編程技術(shù)[M].北京：清華大學(xué)出版社, 2001.

[5] Namiki T.3-D ADI-FDTD Method Unconditionally Stable Time-Domain Algorithm for Solving Full Vector Maxwells Equations[J].IEEE Transactions on Microwave Theory and Techniques, 2000, 48(10): 1743-1747.

[6] Namiki T.A New FDTD Algorithm Based on Alternating-Direction Implicit Method[J].IEEE Trans- actions on Microwave Theory and Techniques, 1999, 47(10): 2003-2007.

[7] Sun X H, Zhang H, Ni L.Efficient Tri- diagonal Solvers on Multicomputers[J].IEEE Trans-actions on Computers, 1992, 41(3): 286-296.

2012-10-15

國家自然科學(xué)基金項目(41140034)。

李太全(1961-)，男，博士，副教授，現(xiàn)主要從事電子技術(shù)方面的教學(xué)與研究工作。

TN911.2

A

1673-1409(2013)01-0006-04

[編輯] 洪云飛