孫旭敏，潘小敏，盛新慶

(北京理工大學(xué) 信息與電子學(xué)院，電磁仿真中心，北京 100081)

?

電特大天線增益的高效求解

孫旭敏，潘小敏，盛新慶

(北京理工大學(xué) 信息與電子學(xué)院，電磁仿真中心，北京 100081)

為解決電特大天線輻射特性計(jì)算效率低的問題，提出并實(shí)現(xiàn)了一種基于多極子的聚集思想快速求解遠(yuǎn)場(chǎng)信息的高效并行算法. 根據(jù)目標(biāo)在并行多層快速多極子中幾何樹的特征，提出高層遠(yuǎn)場(chǎng)模式直接聚集，并且按行并行插值的混合MPI-OpenMP并行計(jì)算方案. 將該算法應(yīng)用于大射電天文望遠(yuǎn)鏡FAST(five-hundred-meter aperture spherical telescope)的遠(yuǎn)場(chǎng)方向圖和增益的計(jì)算，通過與等效電流直接積分法計(jì)算對(duì)比展示其計(jì)算精度與效率. 結(jié)果驗(yàn)證該算法的遠(yuǎn)場(chǎng)輻射特性計(jì)算精度，且同等遠(yuǎn)場(chǎng)計(jì)算任務(wù)量下，平均單方向計(jì)算效率提高近萬倍.

并行多層快速多極子；MPI并行；OpenMP并行；電特大；增益

隨著計(jì)算機(jī)并行技術(shù)的發(fā)展，為了滿足大目標(biāo)尤其是電特大目標(biāo)特性的精確計(jì)算對(duì)高效算法的要求，基于集群系統(tǒng)的消息傳遞(message passage interface，MPI)模型的多進(jìn)程并行技術(shù)以及多核處理器的共享內(nèi)存(OpenMP)多線程并行技術(shù)的應(yīng)用[1-5]，并行MLFMA對(duì)目標(biāo)散射特性的計(jì)算能力已達(dá)到未知數(shù)為十億數(shù)量級(jí).

文獻(xiàn)[6]中利用并行MLFMA來分析500 m口徑射電天文望遠(yuǎn)鏡(five-hundred-meter aperture spherical telescope，F(xiàn)AST)的輻射特性，此天線主瓣電平高波束窄，為了保證其計(jì)算精度，該文獻(xiàn)的做法是在最大增益附近處dθ=±10°內(nèi)計(jì)算更密的遠(yuǎn)場(chǎng)信息，這樣需要較大遠(yuǎn)場(chǎng)信息量的耗時(shí)計(jì)算，而且方向數(shù)量的多少直接影響其精度，如此人為的因素就需要考慮，在精度和效率之間需要找到一個(gè)平衡點(diǎn)，對(duì)于程序的使用者來說這無疑是比較繁瑣的.

對(duì)于上述問題，文獻(xiàn)[7]中已實(shí)現(xiàn)其計(jì)算目標(biāo)散射的MPI并行算法的研究，該方法與電流直接積分求解相比，計(jì)算電大目標(biāo)效率提高很客觀. 為解決應(yīng)用目前的MPI-OpenMP并行架構(gòu)MLFMA計(jì)算電特大輻射目標(biāo)效率低的問題，采用該遠(yuǎn)場(chǎng)計(jì)算方法，其實(shí)現(xiàn)過程中平面波聚集方案的選取與實(shí)現(xiàn)則直接影響算法的計(jì)算精度與效率. 多極子幾何樹結(jié)構(gòu)最高層(盒子尺寸最大的層)具有特殊性，計(jì)算輻射問題時(shí)需要重新考慮負(fù)載平衡的實(shí)現(xiàn)，經(jīng)分析高層遠(yuǎn)場(chǎng)模式不同的聚集方案所需的計(jì)算資源，包括按分層逐次/單層直接聚集以及改進(jìn)型的按行/按列并行插值方案，選取最優(yōu)的MPI并行方案，并重點(diǎn)致力于對(duì)OpenMP并行的研究，最終實(shí)現(xiàn)高效匹配的MPI-OpenMP并行方案，將其應(yīng)用于求解電特大輻射問題，在保證所需內(nèi)存最小化的情況下，實(shí)現(xiàn)了對(duì)其輻射特性的精確高效計(jì)算.

1 基于并行MLFMA高效求解輻射問題

與并行MFLMA計(jì)算散射問題相比，應(yīng)用其計(jì)算輻射問題的主要區(qū)別就是饋源和計(jì)算指標(biāo)不同. 饋源部分選用簡(jiǎn)化的電壓源模型，該模型采用δ函數(shù)源，饋源端口處的RWG邊作為激勵(lì)邊來初始化矩陣方程的右端項(xiàng)；在計(jì)算天線輻射特性時(shí)，以方向性系數(shù)近似作為天線軸向增益，其數(shù)值計(jì)算公式如下：

(1)

(2)

此外，并行MLFMA中應(yīng)用多極子思想處理遠(yuǎn)相互作用中，通過各基函數(shù)聚集而得的遠(yuǎn)場(chǎng)模式公式為

(3)

對(duì)比上述兩式，可知計(jì)算天線方向性增益時(shí)所需的全向遠(yuǎn)場(chǎng)模值可通過計(jì)算多極子中結(jié)合所有基函數(shù)貢獻(xiàn)的遠(yuǎn)場(chǎng)模式，通過乘以常數(shù)因子可得，來提高計(jì)算效率.

2 基于多極子快速求解增益的并行

基于并行MLFMA的多極子思想計(jì)算輻射問題，實(shí)現(xiàn)重點(diǎn)就是應(yīng)用多極子的聚集思想，根據(jù)等效電流并行求解天線的遠(yuǎn)場(chǎng)信息. 基于MPI-OpenMP并行架構(gòu)的遠(yuǎn)相互作用處理的聚集、轉(zhuǎn)移操作高效所得的第2層遠(yuǎn)場(chǎng)模式，已包含所有未知數(shù)的貢獻(xiàn)，因此需適當(dāng)選擇實(shí)現(xiàn)高層(第2層到第0層即目標(biāo)本身)遠(yuǎn)場(chǎng)模式的聚集方案，并通過適當(dāng)選取零層截?cái)嘞禂?shù)以保證高斯面積分方法所對(duì)應(yīng)的遠(yuǎn)場(chǎng)模式方向數(shù)可滿足精度要求. 并對(duì)聚集過程所需計(jì)算資源進(jìn)行分析驗(yàn)證以確定最優(yōu)方案，其中插值系數(shù)矩陣的計(jì)算資源由父層和子層遠(yuǎn)場(chǎng)模式數(shù)量決定，平移系數(shù)由父層與子層盒子空間關(guān)系及父層遠(yuǎn)場(chǎng)模式?jīng)Q定，其實(shí)現(xiàn)中涉及的主要問題：高層聚集方式選取——分層逐次聚集與單層直接聚集；聚集過程的MPI并行方案——按盒子并行與按平面波并行；不同MPI并行方案下OpenMP并行實(shí)現(xiàn)的負(fù)載均衡問題.

目標(biāo)總體遠(yuǎn)場(chǎng)模式的計(jì)算，可以由第二層遠(yuǎn)場(chǎng)模式通過分層逐次聚集與單層直接聚集兩種方式來實(shí)現(xiàn)(圖1中2D結(jié)構(gòu)樹). 而對(duì)于電大輻射問題高層的遠(yuǎn)場(chǎng)模式數(shù)較多，單層聚集在構(gòu)造插值系數(shù)與平移系數(shù)及聚集過程中節(jié)省大量的計(jì)算資源，主要考察其與分層聚集的計(jì)算精度. 通過以sph-0242與sph-10(金屬球半徑電長(zhǎng)度分別為2.42，10.00)的散射問題為例，比較兩種方案相對(duì)于電流直接積分法和解析所得的RCS結(jié)果，這兩種方案相對(duì)于解析解的相對(duì)誤差基本<5%，而誤差較大的方向均由于RCS接近于0 dB，并且直接聚集和電流積分的誤差相差不大，而對(duì)于其他數(shù)值算例以及電大目標(biāo)的散射計(jì)算也驗(yàn)證單層直接聚集方案可以保證計(jì)算精度要求，故選取該方案，并在此基礎(chǔ)上討論并行方案的選取與實(shí)現(xiàn).

2.1 基于多極子快速求解增益的MPI并行方案

基于并行MLFMA采用的是高層平均分配平面波，低層平均分配盒子的混合MPI并行方案，由過渡層(iTrsLev)與第2層關(guān)系決定高層聚集過程的MPI并行方案. 當(dāng)iTrsLev<2，高層按盒子并行，除了進(jìn)程間盒子相互依賴關(guān)系外，其插值和平移過程與原盒子并行類似，每層的全部遠(yuǎn)場(chǎng)模式方向數(shù)同樣作用于所有進(jìn)程；當(dāng)iTrsLev≥2，高層按平面波并行，針對(duì)大部分目標(biāo)尤其是電大目標(biāo)，其高層遠(yuǎn)場(chǎng)模式數(shù)量較多均為平面波并行，且這些層盒子尺寸大數(shù)量少，當(dāng)以盒子并行時(shí)隨著線程數(shù)增加其效率下降. 并行MLFMA的層間插值系數(shù)存儲(chǔ)方式，按盒子并行時(shí)以父層平面波作為負(fù)載，其關(guān)于子層平面波的插值系數(shù)共享，采用按所有父層平面波即按行存儲(chǔ)方式；按平面波并行則以該進(jìn)程父層平面波作為負(fù)載，分別保存其關(guān)于所有對(duì)其有貢獻(xiàn)的所有子層平面波的插值系數(shù)，采用按這些子層平面波即按列存儲(chǔ)方式，以此方案來節(jié)省計(jì)算資源. 而高層結(jié)構(gòu)樹的特殊性(父層即第0層只有一個(gè)盒子，子層即第2層所有盒子均是其子盒子)使得在采用相應(yīng)并行方案的同時(shí)，需要對(duì)其聚集過程中計(jì)算資源進(jìn)行估計(jì)并改進(jìn)算法，包括構(gòu)造相應(yīng)插值以及平移矩陣的內(nèi)存及時(shí)間，以及聚集過程中循環(huán)次序的調(diào)整，以實(shí)現(xiàn)線程并行的負(fù)載均衡及并行效率的提高.

按盒子并行方案的插值系數(shù)依舊采用原始按行插值形式，其總平面波方向數(shù)較少，聚集后采用歸約操作(MPI_Reduce)對(duì)完整的遠(yuǎn)場(chǎng)再進(jìn)行數(shù)據(jù)后處理部分；按平面波并行方案是本文重點(diǎn)，由于高層結(jié)構(gòu)樹的特殊性以及此時(shí)父層遠(yuǎn)場(chǎng)模式數(shù)較多，需要改進(jìn)其并行聚集方案，其中對(duì)于插值系數(shù)矩陣、聚集過程以及數(shù)據(jù)通信部分的并行實(shí)現(xiàn)進(jìn)行探討及驗(yàn)證.

其中分塊插值系數(shù)矩陣均為稀疏矩陣，改進(jìn)型按行插值與按列插值的并行插值系數(shù)矩陣選取及存儲(chǔ)方案如圖2(a)所示，改進(jìn)的按行方案先以父層所有平面波進(jìn)行搜索，若對(duì)其插值有貢獻(xiàn)的子層平面波(數(shù)目≤16)有在本地的則進(jìn)行保存，否則將不保存，則本進(jìn)程所有被貢獻(xiàn)的父層平面波都將被保存，其中包含與之左右相鄰進(jìn)程的部分平面波，以這些局部父層平面波為一維索引，得到對(duì)應(yīng)的子層平面波與插值系數(shù)，相對(duì)于原按行方案，于父層平面波的局部性以節(jié)省內(nèi)存需求；圖2(b)所示，改進(jìn)的按列方案為減少通信開銷，以本地子層平面波為貢獻(xiàn)項(xiàng)，即以本進(jìn)程子層平面波為一維索引，得到其所有有貢獻(xiàn)的父層平面波與插值系數(shù). 相對(duì)于改進(jìn)型的插值方案，平移過程均以父層局部平面波作為整體負(fù)載，按子層全部盒子進(jìn)行循環(huán)，平移之后按盒子貢獻(xiàn)疊加得到局部平面波. 從本質(zhì)來看，兩種插值方式的信息一致，子層都無需進(jìn)行通信，父層均得到局部平面波信息，不過其相對(duì)應(yīng)的聚集過程中插值方案選取將直接影響并行計(jì)算資源，于線程并行中詳細(xì)討論.

對(duì)于電特大輻射問題，遠(yuǎn)場(chǎng)模式聚集方法的零層方向由截?cái)嘞禂?shù)決定，該方向數(shù)很大，區(qū)別于散射問題對(duì)于遠(yuǎn)場(chǎng)信息的歸約處理，為實(shí)現(xiàn)節(jié)省計(jì)算資源，需要對(duì)聚集得到的局部平面波進(jìn)行通信(MPI_Sendrecv)得到按進(jìn)程并行的平面波信息，即將局部平面波不屬于本進(jìn)程的部分平面波發(fā)送給對(duì)應(yīng)進(jìn)程，該進(jìn)程對(duì)應(yīng)疊加接收到的平面波來進(jìn)行處理. 最終將各進(jìn)程的遠(yuǎn)場(chǎng)模式通過數(shù)據(jù)收集(MPI_Gatherv)操作將主極化和交叉極化的場(chǎng)值均集中于主進(jìn)程(0號(hào)進(jìn)程)，此時(shí)得到整個(gè)三維空間的全向遠(yuǎn)場(chǎng)，通過天線增益計(jì)算公式即可得增益.

2.2 基于多極子快速求解增益的OpenMP加速技術(shù)

高層聚集應(yīng)用基于共享內(nèi)存的指導(dǎo)性調(diào)度線程并行OpenMP來加快計(jì)算，為了充分實(shí)現(xiàn)其最佳并行效率，需先確定計(jì)算密集區(qū)，并保證達(dá)到負(fù)載均衡的任務(wù)量來實(shí)現(xiàn)線程同步. 高層聚集包括插值系數(shù)矩陣填充、方向向量填充、平面波聚集、遠(yuǎn)場(chǎng)模式數(shù)據(jù)處理這四部分，其中平面波聚集最耗時(shí)，在數(shù)據(jù)后處理總時(shí)間中占60%多，且其遠(yuǎn)場(chǎng)方向數(shù)足夠大可保證并行的任務(wù)量，因此對(duì)按行與按列兩種聚集方案的OpenMP并行實(shí)現(xiàn)均進(jìn)行分析和討論.

按行插值聚集中，單線程方案中以子層盒子作為循環(huán)對(duì)象，插值系數(shù)以父層平面波作為一維索引，插值過程以父層局部平面波作為整體進(jìn)行. 線程并行化的實(shí)現(xiàn)，首先需要確定負(fù)載任務(wù)的并行分配：由于父層為單盒子，子層盒子間為獨(dú)立計(jì)算，子層盒子數(shù)(3D最大為64)數(shù)目有限，而且根據(jù)插值系數(shù)的特征，父層平面波可作為獨(dú)立計(jì)算負(fù)載，此時(shí)需要調(diào)整循環(huán)次序，以父層局部平面波為一階循環(huán)來進(jìn)行負(fù)載匹配，子層盒子為二階循環(huán)，再應(yīng)用已獨(dú)立保存的平面波方向和盒子位置信息來進(jìn)行平移操作. 因此應(yīng)用按行插值聚集方案通過循環(huán)次序的調(diào)整不僅可按最大任務(wù)量實(shí)現(xiàn)最佳并行，而且減少了平移的計(jì)算時(shí)間.

按列插值聚集中，區(qū)別在于其插值系數(shù)的一維索引是子層平面波，故無法通過循環(huán)次序的變換將父層平面波負(fù)載作為線程匹配對(duì)象，因此考慮到線程并行共享內(nèi)存的模式與子層盒子的獨(dú)立性，只能仍以子層盒子數(shù)作為并行的循環(huán)對(duì)象，且需要對(duì)將寫入的父層局部平面波分配與線程數(shù)一致的內(nèi)存空間，獨(dú)立存儲(chǔ)，聚集完成后再以各線程結(jié)果求和來實(shí)現(xiàn)子層貢獻(xiàn)的疊加，該方案由于并行對(duì)象有限以及求和計(jì)算增加，并行效率明顯隨著線程數(shù)增加而下降，且對(duì)內(nèi)存的要求增大.

由于父層平面波數(shù)目較大，為了節(jié)省內(nèi)存，采用了原遠(yuǎn)相互作用中的內(nèi)存循環(huán)技術(shù)，若結(jié)構(gòu)體中遠(yuǎn)場(chǎng)模式除目前子層平面波后內(nèi)存足夠則無需另開內(nèi)存，而按列插值聚集并行過程中該內(nèi)存需求與線程數(shù)成正比，無法保證在提高并行計(jì)算效率的同時(shí)不提高內(nèi)存的消耗. 因此基于并行效率和內(nèi)存需求的多方面分析，最優(yōu)的并行方案為結(jié)合MPI-OpenMP并行技術(shù)的改進(jìn)型按行插值聚集方案.

3 算例的數(shù)值分析

計(jì)算飛機(jī)散射問題來測(cè)試其遠(yuǎn)場(chǎng)計(jì)算的線程并行效率，電尺寸為240λ，未知數(shù)為450萬，根據(jù)節(jié)點(diǎn)資源，線程數(shù)從2～12變化，其高層按平面波并行時(shí)線程并行效率如圖3，當(dāng)線程到達(dá)12時(shí)，并行效率仍高于83%，該并行策略較成功實(shí)現(xiàn)了并行加速.

計(jì)算反射面天線FAST-300(反射面光滑，口徑為300 m)的輻射特性，與電流直接積分法計(jì)算結(jié)果比較來驗(yàn)證本文并行算法的精度和效率. 該反射面天線于焦點(diǎn)以天文臺(tái)提供的階梯喇叭作為饋源，分析頻率為300 MHz，天線電尺寸為300λ，結(jié)構(gòu)樹層數(shù)為10層，平均剖分尺寸為0.13λ，總未知數(shù)為1 737萬，用64個(gè)進(jìn)程6個(gè)線程并行計(jì)算，E-plane遠(yuǎn)場(chǎng)方向圖結(jié)果如圖4，計(jì)算增益為58.19 dBi，與電流直接積分法和商業(yè)軟件FEKO(PO法)所得的58.28 dBi和58.22 dBi相比，其誤差均小于1‰，輻射特性結(jié)果吻合較好.

其中兩種方法所需的計(jì)算資源如表1，快速的遠(yuǎn)場(chǎng)聚集方案在遠(yuǎn)場(chǎng)計(jì)算中應(yīng)用了遠(yuǎn)場(chǎng)模式的內(nèi)存循環(huán)技術(shù)，不過保存高層插值與平移系數(shù)需要額外的內(nèi)存，其中電流直接積分法為保證最大輻射方向的精度，仍計(jì)算兩次遠(yuǎn)場(chǎng)信息，表中統(tǒng)計(jì)一次計(jì)算時(shí)間，方向選取(θ，φ)步進(jìn)為1°，快速遠(yuǎn)場(chǎng)計(jì)算中方向以高斯取點(diǎn)決定，其平均遠(yuǎn)場(chǎng)計(jì)算時(shí)間提高約為1.6萬倍，總時(shí)間亦如預(yù)期提高，因此若計(jì)算結(jié)構(gòu)更復(fù)雜或精度要求更高的輻射問題時(shí)，同等計(jì)算任務(wù)量下該算法更具優(yōu)勢(shì).

表1 FAST-300天線計(jì)算資源

4 結(jié) 論

為實(shí)現(xiàn)應(yīng)用并行MLFMA高效準(zhǔn)確地計(jì)算電特大輻射問題，采用了快速的多極子遠(yuǎn)場(chǎng)聚集求解方案. 基于并行結(jié)構(gòu)樹的高層特殊性，對(duì)于高層不同聚集方案的資源需求進(jìn)行分析，并通過算例驗(yàn)證，確定以改進(jìn)型按行插值的單層直接聚集作為最優(yōu)方案，為進(jìn)一步提高計(jì)算效率，于計(jì)算密集區(qū)通過循環(huán)次序調(diào)整結(jié)合線程并行，并應(yīng)用了內(nèi)存循環(huán)技術(shù)來節(jié)省額外內(nèi)存.

通過計(jì)算理想金屬目標(biāo)的散射問題，驗(yàn)證其遠(yuǎn)場(chǎng)聚集的線程并行效率，在線程數(shù)為12時(shí)依然高達(dá)83%的并行效率；以電特大反射面天線FAST的計(jì)算，驗(yàn)證了其對(duì)于多方向遠(yuǎn)場(chǎng)需求計(jì)算的高效性，與電流直接積分法相比，輻射特性精度和效率均得到顯著提高，數(shù)據(jù)后處理部分將同等計(jì)算任務(wù)量條件下，效率提高近萬倍.

[1] Song J M，Chew W C. Multilevel fast-multipole algorithm for solving combined field integral equations of electromagnetic scattering [J].Microwave and Optical Technology Letter，1995，10(1):14-19.

[2] 潘小敏，盛新慶.一種多層快速多極子的高效并行方案[J].電子學(xué)報(bào)，2007，35(3):567-571.

Pan Xiaomin，Sheng Xinqing. A highly efficient parallel approach of multi-level fast multipole algorithm[J]. Acta Electronica Sinica，2007，35(3):567-571. (in Chinese)

[3] 潘小敏，盛新慶. 一種高性能并行多層快速多極子算法[J].電子學(xué)報(bào)，2010，38(3):580-584.

Pan Xiaomin，Sheng Xinqing. A high-performance parallel multi-level fast multipole algorithm[J]. Acta Electronica Sinica，2010，38(3):580-584. (in Chinese)

[4] 潘小敏，皮維超，盛新慶.基于共享內(nèi)存的高效OpenMP并行多層快速多極子算法[J].北京理工大學(xué)學(xué)報(bào)，2012，32(2):164-169.

Pan Xiaomin，Pi Weichao，Sheng Xinqing. Efficient parallelization of multi-level fast multipole algorithm based on OpenMP[J]. Transactions of Beijing Institute of Technology，2012，32(2):164-169. (in Chinese)

[5] Pan Xiaomin，Pi Weichao，Yang Minglin，et al. Solving problems with over one billion unknowns by the MLFMA[J]. IEEE Transactions on Antennas and Propagation，2012，60(5):2571-2574.

[6] 段猛，李斌，盛新慶，等.基于并行多層快速多極子的大射電天文望遠(yuǎn)鏡FAST的計(jì)算[C]∥2011年全國(guó)天線年會(huì).南京:[s.n.],2011:666-669.

Duan Meng，Li Bin，Sheng Xinqing，et al. The computation of large spherical radio telescope FAST antenna based on the parallel MLFMA[C]∥Proceedings of The 2011 National Conference on Antennas. Nanjing: [s.n.], 2011:666-669. (in Chinese)

[7] Velamparambil S，Chew W C，Song J. 10 million unknowns: is it that big？[J]. IEEE Antennas and Propagation Magazine，2003，45(2):43-58.

(責(zé)任編輯：劉芳)

Efficient Solution for Extremely Electric Large Antenna Gain

SUN Xu-min，PAN Xiao-min，SHENG Xin-qing

(Center for Electromagnetic Simulation，School of Information and Electronics，Beijing Institute of Technology，Beijing 100081，China)

An efficient parallel algorithm to accelerate the calculation of the far-fields was proposed and implemented for solving the electric large antenna radiation problem，based on the upward pass or the aggregation phase of the parallel multilevel fast multipole algorithm(MLFMA). According to the geometry tree structure of the parallel MLFMA，an efficient hybrid MPI-OpenMP parallelization algorithm was designed with the direct aggregation of coarser level far-field radiation pattern and parallel in-row interpolation. The computation of far-field radiation pattern and antenna gain of the extremely large parabolic reflector of FAST by this algorithm shows the accuracy and efficiency of the parallel program，compared with the computation by the equivalent current direct integration method. The numerical results demonstrate that the presented approach has good accuracy for the radiation characteristics，and the computational efficiency has improved about ten thousand times for single direction under same far-field calculation task compared to the equivalent current direct integration method.

parallel multi-level fast multi-pole algorithm (parallel MLFMA)；MPI parallel；OpenMP parallel；extremely electric large；gain

2014-03-17

國(guó)家“九七三”計(jì)劃項(xiàng)目(2012CB720702)

孫旭敏(1989—)，女，博士生，E-mail: sunxm1989@foxmail.com.

盛新慶(1968—)，男，教授，博士生導(dǎo)師，E-mail: xsheng@bit.edu.cn.

O 441.4

A

1001-0645(2016)07-0718-05

10.15918/j.tbit1001-0645.2016.07.011