大規模并行RWG矩量法矩陣填充優化

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

(西安電子科技大學天線與微波技術重點實驗室,陜西西安 710071)

大規模并行RWG矩量法矩陣填充優化

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

(西安電子科技大學天線與微波技術重點實驗室,陜西西安 710071)

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

RWG矩量法;并行;矩陣填充方案;優化;冗余積分

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

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

圖1　第n個RWG基函數

1　并行RWG矩量法

1.1RWG基函數

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

RWG基函數的定義式為

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

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

圖2　二維分塊循環分布方案

2　基于網格編號優化的并行填充方案

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

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

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

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

圖3　三角形二重積分與公共邊索引關系

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

綜上所述，金屬礦山礦下生產作業的核心實質是穩固安全。而電氣自動化控制技術能有效地解決相關的安全問題。通過對礦下排水系統、通風系統與運輸機械設備的遠程自動化控制，可以有效預防與緩解礦下危險事故的發生，為其提高礦業產量與企業壯大發展打下堅持的保障基礎

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

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

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

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

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

圖4　公共邊編號優化示例

3　算例仿真

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

3.1飛機I的散射特性

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

圖5　飛機Ⅰ仿真模型及雙站雷達散射截面結果

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

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

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

3.2飛機Ⅱ的散射特性

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

圖6　飛機Ⅱ仿真模型及雙站雷達散射截面結果

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

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

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

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

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

4　總 結

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

[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]林中朝,陳巖,張玉,等.國產CPU平臺中并行高階矩量法研究[J].西安電子科技大學學報,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 網絡出版時間:2015-12-10

國家高技術研究發展計劃(863計劃)資助項目(2012AA01A308);國家自然科學基金資助項目(61301069,61072019);教育部新世紀優秀人才支持計劃資助項目(NCET-13-0949);陜西省青年科技新星資助項目(2013KJXX-67);中央高校基本科研業務費專項資金重點資助項目(JY10000902002)

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

網絡出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20151210.1529.018.html