大規(guī)模并行RWG矩量法矩陣填充優(yōu)化

陳 巖,張 玉,王 永,趙勛旺,林中朝

(西安電子科技大學(xué)天線與微波技術(shù)重點(diǎn)實驗室,陜西西安 710071)

大規(guī)模并行RWG矩量法矩陣填充優(yōu)化

陳 巖,張 玉,王 永,趙勛旺,林中朝

(西安電子科技大學(xué)天線與微波技術(shù)重點(diǎn)實驗室,陜西西安 710071)

針對并行RWG矩量法進(jìn)程間冗余積分問題,通過優(yōu)化網(wǎng)格編號提出了一種高效的并行矩陣填充方案.在矩陣塊循環(huán)分布并行策略基礎(chǔ)上,對三角形公共邊進(jìn)行重新編號,使得需要相同三角形積分的矩陣元素分布在同一進(jìn)程上,從而大幅度地減少進(jìn)程間的冗余積分計算.數(shù)值結(jié)果表明,該并行矩陣填充方案消除了絕大部分的進(jìn)程間冗余積分,提高了并行矩陣填充的效率.

RWG矩量法;并行;矩陣填充方案;優(yōu)化;冗余積分

作為電磁模擬中最精確的數(shù)值方法,矩量法(Method of Moment,Mo M)可以有效地處理各種復(fù)雜的電磁問題.但是,矩量法的計算復(fù)雜度和內(nèi)存需求會隨著電磁目標(biāo)電尺寸的增大而急劇增長[1-2].傳統(tǒng)的串行RWG(Rao-Wilton-Glisson)矩量法[3]在處理復(fù)雜電磁問題時會產(chǎn)生很大的未知量,受計算機(jī)單機(jī)計算資源的限制,難以有效解決電大尺寸規(guī)模的問題.隨著當(dāng)今計算機(jī)軟硬件的快速發(fā)展,利用大規(guī)模并行計算技術(shù)可以大幅度提高矩量法的計算規(guī)模和計算速度,從而高效地完成一系列具有挑戰(zhàn)性的大規(guī)模電磁工程應(yīng)用難題[2,4-5].

矩量法處理電磁問題的核心環(huán)節(jié)是矩陣填充和矩陣方程求解.對于矩陣方程求解,筆者已經(jīng)有深入的研究[2,4],這里筆者重點(diǎn)關(guān)注矩陣的填充過程.RWG矩量法需要將電磁模型剖分成許多三角形面片,并在具有公共邊的三角形對上定義RWG基函數(shù).眾所周知,在串行RWG矩量法中,利用循環(huán)三角形替代循環(huán)公共邊的方法可以大大減少矩陣填充過程中的冗余積分計算[2],從而提高矩陣填充的效率.在并行RWG矩量法中,對于并發(fā)執(zhí)行的各進(jìn)程采用這一方案后,各進(jìn)程內(nèi)部的冗余積分計算也可以完全消除.然而,并行RWG矩量法在進(jìn)程之間也引入了大量新的冗余計算,即不同進(jìn)程之間存在相同的積分計算,這些進(jìn)程間的冗余計算是無法通過三角形循環(huán)消除的.在消除進(jìn)程間冗余積分方面,鮮有有效工作內(nèi)容發(fā)表,這主要是因為進(jìn)程間冗余積分涉及到幾何建模的過程,使得問題變得異常復(fù)雜,而且當(dāng)并行規(guī)模較小時,這一問題并不突出.但是當(dāng)采用大規(guī)模并行計算技術(shù)解決實際電磁工程難題時,進(jìn)程間冗余積分變得十分嚴(yán)重,冗余計算甚至大大地超過有效計算.為此,筆者詳細(xì)分析了并行RWG矩量法在進(jìn)程間引入新的冗余計算的原因,并給出了有效的解決方案.該方案在不改變現(xiàn)有矩陣塊循環(huán)分布并行策略的基礎(chǔ)上對算法進(jìn)行優(yōu)化,通過對公共邊重新編號,盡可能地保證包含相同三角形積分的矩陣元素分布在同一進(jìn)程上,從而減少進(jìn)程間的冗余計算,大大地提高了并行矩陣填充效率.

圖1　第n個RWG基函數(shù)

1　并行RWG矩量法

1.1RWG基函數(shù)

圖1給出了相鄰于第n條公共邊的一對三角形T+n和T-n.

RWG基函數(shù)的定義式為

其中,ln表示一對相鄰三角形的公共邊長度,和分別為三角形和的面積.,是從三角形的頂點(diǎn)指向點(diǎn)r的矢量,是從三角形的頂點(diǎn)指向點(diǎn)r的矢量.這種定義方式表明電流是從三角形經(jīng)過公共邊流向三角形.在與三角形對之外,基函數(shù)為0.

筆者采用的并行編程模型為消息傳遞接口(Message Passing Interface,MPI)[6],它是基于分布式內(nèi)存的并行編程模型,理論上可以擴(kuò)展到具有任意節(jié)點(diǎn)數(shù)目的計算平臺上.在并行RWG矩量法中,必須首先將矩陣分布到各個進(jìn)程上.一種有效的數(shù)據(jù)分布方式就是將大規(guī)模稠密矩陣以二維分塊循環(huán)分布[2,7]的方式分配到所有進(jìn)程上.假定9×9的矩陣A以2×2的分塊大小劃分為多個矩陣塊,并將其以2×3的進(jìn)程網(wǎng)格分配到6個進(jìn)程上,如圖2(a)所示,其中小矩形框中的數(shù)字代表矩陣元素的索引,圖中每一個分塊由方框圈出,最外面的虛線表示這些分塊未被填滿.圖2(b)是每個進(jìn)程上分配的矩陣元素的索引.

圖2　二維分塊循環(huán)分布方案

2　基于網(wǎng)格編號優(yōu)化的并行填充方案

RWG基函數(shù)定義于具有公共邊的三角形對上,因此阻抗矩陣元素是按公共邊編號索引的.當(dāng)計算阻抗矩陣元素時,需要在兩個三角形對上進(jìn)行二重面積分.以電場積分方程(Electric Field Integral Equation,EFIE)[8-9]矩量法為例,阻抗矩陣元素Zmn計算過程為

式(2)表明,兩個三角形對上的二重面積分可以化為4項.不失一般性,考慮第一項積分,有

圖3給出了三角形二重積分與公共邊索引關(guān)系,圖中的小寫英文字母表示公共邊編號,大寫英文字母表示三角形編號.對于第(m,n)個矩陣元素Zmn,首先根據(jù)式(2)計算出4組積分IQ、IJ、PQ、PJ;每組積分包含4個積分結(jié)果,將這4個積分結(jié)果與第m條公共邊、第n條公共邊以及它們對應(yīng)的頂點(diǎn)等信息按照一定的運(yùn)算規(guī)則進(jìn)行運(yùn)算,然后累加4組計算結(jié)果,便可計算出矩陣元素Zmn.

考慮三角形積分PQ,它可用于(m,n)、(m,t)、(m,r)、(k,n)、(k,t)、(k,r)、(l,n)、(l,t)、(l,r)這9個矩陣元素的計算.可見填充矩陣時,若按公共邊循環(huán)計算阻抗元素,積分PQ最多可能被計算9次,顯然這種填充方式引入了大量冗余計算.若按三角形循環(huán)來進(jìn)行相關(guān)計算,可首先計算出積分PQ,再將積分值累加到對應(yīng)的矩陣元素中,這樣遍歷全部三角形后,便可保證所有矩陣元素都被求出.與按公共邊循環(huán)的方式相比,按三角形循環(huán)來填充矩陣,面積分計算一次可使用9次,有效地避免了冗余積分計算.

圖3　三角形二重積分與公共邊索引關(guān)系

然而,在并行填充方案中,這9個矩陣元素并不一定被分配到同一進(jìn)程中,這時不同進(jìn)程都需要計算積分PQ,造成冗余計算.一種有效的解決方案便是想辦法讓這9個元素被分配到同一進(jìn)程中.矩陣元素索引直接和公共邊編號相關(guān),為了保證這9個矩陣元素被分配到同一進(jìn)程上,需要對公共邊進(jìn)行重新編號,只要公共邊編號變了,對應(yīng)的矩陣元素索引就會變,矩陣元素分配的進(jìn)程也會變.只要公共邊重新編號得當(dāng),便可最大程度地使這9個元素分配到一個進(jìn)程上,從而避免冗余計算.

綜上所述，金屬礦山礦下生產(chǎn)作業(yè)的核心實質(zhì)是穩(wěn)固安全。而電氣自動化控制技術(shù)能有效地解決相關(guān)的安全問題。通過對礦下排水系統(tǒng)、通風(fēng)系統(tǒng)與運(yùn)輸機(jī)械設(shè)備的遠(yuǎn)程自動化控制，可以有效預(yù)防與緩解礦下危險事故的發(fā)生，為其提高礦業(yè)產(chǎn)量與企業(yè)壯大發(fā)展打下堅持的保障基礎(chǔ)

通過以上分析可見,幾何上連續(xù)(歸屬于同一個三角形)的公共邊對應(yīng)的矩陣元素不在同一個進(jìn)程上時,就會導(dǎo)致進(jìn)程間冗余計算.消除冗余計算的關(guān)鍵需要解決兩個問題:哪些公共邊是幾何上連續(xù)的公共邊;公共邊重新編號對應(yīng)的新索引應(yīng)如何獲得.

公共邊的重新編號必須結(jié)合矩陣在進(jìn)程上的分布方式進(jìn)行,矩陣是按照二維塊循環(huán)的方式分布到二維進(jìn)程網(wǎng)格上的.為消除冗余計算,需使得“幾何上連續(xù)的公共邊”以矩陣元素在進(jìn)程中的索引順序進(jìn)行編號,即公共邊重新編號對應(yīng)的新索引為矩陣元素在進(jìn)程中的索引.每個矩陣元素有行和列兩個方向的索引,因此需要先確定一個方向再對公共邊進(jìn)行重新編號.一般情況下選擇行向,因為矩陣方程求解往往要求行向進(jìn)程數(shù)大于列向進(jìn)程數(shù),這種選擇能更好地消除進(jìn)程間的冗余計算.

不失一般性,假設(shè)幾何上連續(xù)的公共邊重新編號之前的索引大致也是連續(xù)的.基于這一假設(shè),在實現(xiàn)公共邊重新編號時,用新的索引編號直接替換原來連續(xù)的索引即可.下面給出一個具體的示例,選擇行向索引對公共邊重新編號.考慮圖2中所示的9×9的矩陣及其分布方式,圖4(a)給出了一個與圖2相對應(yīng)的公共邊編號示例.

結(jié)合圖2和圖4(a),只關(guān)心(5,2)和(5,3)兩個矩陣元素,考慮三角形二重積分PQ,可以用于(5,2)和(5,3)的計算,但是(5,2)分配到了進(jìn)程P00上,而(5,3)分配到了進(jìn)程P01上,這兩個進(jìn)程都要計算這一積分.為了避免冗余計算,只需要將公共邊3的索引變?yōu)?即可.這樣,三角形二重積分PQ便可以用于矩陣元素(5,2)和(5,7),而這兩個矩陣元素都分配在進(jìn)程P00上.

假設(shè)原來在幾何上連續(xù)的公共邊,其編號索引也是連續(xù)的,則對這個示例應(yīng)按照如圖4(c)所示的重新編號方案實施.圖4(b)中箭頭下方的數(shù)字,就來源于圖2(b)中的行向矩陣索引.公共邊重新編號后的結(jié)果如圖4(c)所示.這種編號方案保證了幾何上連續(xù)的公共邊所對應(yīng)的矩陣元素能盡可能地分配到同一個進(jìn)程上.這樣的重新編號雖然不能完全消除冗余計算,但可以消除大部分.這在未知量較小的情況下并不明顯,但當(dāng)未知量很大時,冗余計算明顯地減少了.

圖4　公共邊編號優(yōu)化示例

3　算例仿真

這里以兩個飛機(jī)模型的散射特性的計算為例,來驗證基于公共邊重新編號優(yōu)化的并行矩陣填充方案避免進(jìn)程間冗余積分計算的有效性.

3.1飛機(jī)I的散射特性

此處選取的計算模型為飛機(jī)Ⅰ,電磁仿真模型如圖5(a)所示.飛機(jī)Ⅰ表面為理想導(dǎo)體(Perfect Electric Conductor,PEC),尺寸為11.60 m×7.00 m×2.93 m,計算飛機(jī)Ⅰ在500 MHz入射平面波(沿機(jī)頭方向入射)水平極化情況下的雙站雷達(dá)散射截面(Radar Cross Section,RCS),相應(yīng)的電尺寸為1.93λ×1.17λ× 0.49λ.該模型被剖分為25 606個三角形,共有34 824條公共邊,故阻抗矩陣大小為34 824×34 824.計算得到飛機(jī)Ⅰ的雙站RCS結(jié)果如圖5所示,可見重新編號前后的計算結(jié)果吻合良好.

圖5　飛機(jī)Ⅰ仿真模型及雙站雷達(dá)散射截面結(jié)果

表1給出了公共邊編號前后不同進(jìn)程數(shù)、不同進(jìn)程網(wǎng)格和不同分塊大小的情況下,所有進(jìn)程在矩陣填充過程中的積分次數(shù)測試情況.串行算法沒有冗余積分,因此稱為有效積分.表格中冗余積分次數(shù)為所有進(jìn)程中的總積分次數(shù)減去有效積分次數(shù),冗余積分比例為冗余積分次數(shù)除以總積分次數(shù).

表1　公共邊編號前后矩陣填充過程中的積分次數(shù)測試

由表1中編號后的測試結(jié)果可見,冗余積分次數(shù)可減少約60%,減少程度相當(dāng)明顯.這表明了筆者提出的算法在減少冗余積分計算方面的高效性.

3.2飛機(jī)Ⅱ的散射特性

此處選取的計算模型為飛機(jī)模型Ⅱ,電磁仿真模型如圖6(a)所示.飛機(jī)Ⅱ表面為理想導(dǎo)體,尺寸為18.92 m×14.56 m×5.05 m,計算飛機(jī)Ⅱ在500 MHz入射平面波(沿機(jī)頭方向入射)水平極化情況下的雙站雷達(dá)散射截面,相應(yīng)的電尺寸為3.07λ×2.43λ×0.84λ.該模型被剖分為125 214個三角形,共有187 821條公共邊,故阻抗矩陣大小為187 821×187 821.計算得到飛機(jī)Ⅱ的雙站雷達(dá)散射截面結(jié)果如圖6所示,可見重新編號前后的計算結(jié)果吻合良好.

圖6　飛機(jī)Ⅱ仿真模型及雙站雷達(dá)散射截面結(jié)果

表2給出了公共邊重新編號前后的算法在不同進(jìn)程數(shù)、不同進(jìn)程網(wǎng)格的情況下,所有進(jìn)程在矩陣填充過程中的積分次數(shù)測試情況.表3給出了公共邊編號前后矩陣填充時間對比情況.

表2　公共邊編號前后矩陣填充過程中的積分次數(shù)測試

表3　公共邊編號前后矩陣填充時間對比

由表2可見,當(dāng)并行規(guī)模達(dá)到數(shù)百進(jìn)程甚至上千進(jìn)程時,冗余積分比例已經(jīng)上升到了70%以上.當(dāng)進(jìn)程網(wǎng)格為方形時,冗余積分次數(shù)減少更為明顯,減少約90%,冗余計算幾乎被完全消除;當(dāng)進(jìn)程網(wǎng)格不為方陣時,冗余積分次數(shù)減少率約為66%,減少也很明顯,但與進(jìn)程網(wǎng)格為方陣時相比較差.前面曾指出,對公共邊重新編號后,只能保證行向或列向中的一個實現(xiàn)冗余計算降低,除非進(jìn)程網(wǎng)格為方陣,此時行向和列向的進(jìn)程數(shù)、分塊大小都一樣,公共邊重新編號對兩個方向都有效,這一結(jié)論在此處得到了驗證.

由表3可以看出,填充時間與總積分次數(shù)具有一致的下降比例,這說明消除進(jìn)程間冗余計算所付出的代價極低,公共邊重新編號的方案大大提高了并行RWG矩量法矩陣填充效率.

4　總 結(jié)

并行RWG矩量法在并行規(guī)模增大時,矩陣填充過程中進(jìn)程間冗余計算迅速增多,使得矩陣填充效率急劇下降.筆者詳細(xì)分析了并行RWG矩量法在并行矩陣填充過程中進(jìn)程間存在冗余積分計算的原因,并提出了消除進(jìn)程間冗余計算的方案.在不改變并行RWG矩量法矩陣塊循環(huán)分布并行策略的基礎(chǔ)上,采用基于網(wǎng)格編號優(yōu)化的矩陣并行填充方案,使得“幾何上連續(xù)的公共邊”對應(yīng)的矩陣元素盡可能地分配到同一進(jìn)程,從而使得需要同一個積分的矩陣元素分布在同一個進(jìn)程上,大幅度減少了進(jìn)程間的冗余計算.測試結(jié)果也表明了這一方案的有效性.

[1]HARRINGTON R F.Field Computation by Moment Methods[M].New York:IEEE Press Series on Electromagnetic Wave Theory,1993.

[2]ZHANG Y,SARKAR T K.Parallel Solution of Integral Equation Based EM Problems in the Frequency Domain[M]. Hoboken,NJ:Wiley-IEEE Press,2009.

[3]RAO S M,WILTON D R,GLISSON A W.Electromagnetic Scattering by Surfaces of Arbitrary Shape[J].IEEE Transactions on Antennas and Propagation,1982,30(3):409-418.

[4]ZHANG Y,LIN Z C,ZHAO X W,et al.Performance of a Massively Parallel Higher-order Method of Moments Code Using Thousands of CPUs and Its Applications[J].IEEE Transactions on Antennas and Propagation,2014,62(12): 6317-6324.

[5]林中朝,陳巖,張玉,等.國產(chǎn)CPU平臺中并行高階矩量法研究[J].西安電子科技大學(xué)學(xué)報,2015,42(3):43-47. LIN Zhongchao,CHEN Yan,ZHANG Yu,et al.Study of the Parallel Higher-order Mo M on a Domestically-made CPU Platform[J].Journal of Xidian University,2015,42(3):43-47.

[6]GROPP W,HOEFLER T,THAKUR R,et al.Using Advanced MPI:Modern Features of the Message-passing Interface[M].Cambridge:the MIT Press,2014.

[7]DONGARRA J.Linear Algebra Libraries for High-performance Computers:a Personal Perspective[J].IEEE Parallel and Distributed Technology:Systems and Applications,1993,1(1):17-24.

[8]ECHEVERRI-BAUTISTA M A,FRANCAVILLA M A,VIPIANA F,et al.A Hierarchical Fast Solver for EFIE-Mo M Analysis of Multiscale Structures at Very Low Frequencies[J].IEEE Transactions on Antennas and Propagation,2014,62(3):1523-1528.

[9]YANG K,SHENG W T,ZHU Z Y,et al.Electromagnetic Analysis for Inhomogeneous Interconnect and Packaging Structures Based on Volume-surface Integral Equations[J].IEEE Transactions on Components,Packaging and Manufacturing Technology,2013,3(8):1364-1371.

(編輯:郭 華)

Optimization of matrix filling in the large scale parallel RWG basis based method of moments

CHEN Yan,ZH ANG Yu,WANG Yong,ZHAO Xunwang,LIN Zhongchao
(Science and Technology on Antenna and Microwave Lab.,Xidian Univ.,Xi’an 710071,China)

To solve the issue of inter-process redundant integrals in the parallel Method of Moments (Mo M)using RWG basis functions,an efficient parallel matrix filling scheme is proposed through mesh index optimization.Based on a block-cyclic matrix distribution strategy,the common edges of triangles are renumbered to make the matrix elements that need the same triangular integrals be assigned to one process,thus drastically reducing the inter-process redundant integrals.Numerical results show that the proposed scheme eliminates most of the inter-process redundant integrals and greatly improves the efficiency of parallel matrix filling.

RWG method of moments;parallel;matrix filling scheme;optimization;redundant integral

TN820

A

1001-2400(2016)05-0046-06

10.3969/j.issn.1001-2400.2016.05.009

2015-08-26 網(wǎng)絡(luò)出版時間:2015-12-10

國家高技術(shù)研究發(fā)展計劃(863計劃)資助項目(2012AA01A308);國家自然科學(xué)基金資助項目(61301069,61072019);教育部新世紀(jì)優(yōu)秀人才支持計劃資助項目(NCET-13-0949);陜西省青年科技新星資助項目(2013KJXX-67);中央高校基本科研業(yè)務(wù)費(fèi)專項資金重點(diǎn)資助項目(JY10000902002)

陳 巖(1990-),男,西安電子科技大學(xué)博士研究生,E-mail:yuseexidian@163.com.

網(wǎng)絡(luò)出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20151210.1529.018.html