1 引言

近幾十年來，計(jì)算機(jī)技術(shù)飛速發(fā)展，計(jì)算速度不斷提高，內(nèi)存容量不斷增大；但同時(shí)，在科學(xué)研究和工程應(yīng)用中越來越需要對(duì)大型艦只、車輛、航空航天器等目標(biāo)進(jìn)行電磁散射特性分析。這些目標(biāo)電尺寸非常巨大，求解問題所含未知量動(dòng)輒以百萬、千萬計(jì)，現(xiàn)有水平下單臺(tái)PC機(jī)很難應(yīng)對(duì)如此龐大的計(jì)算量。鑒于此，越來越多的科研、工程人員希望在改進(jìn)算法的同時(shí)能夠擁有高效的并行計(jì)算環(huán)境。巨型并行計(jì)算機(jī)存儲(chǔ)容量大、運(yùn)算速度快，但價(jià)格昂貴。網(wǎng)絡(luò)并行計(jì)算應(yīng)運(yùn)而生，它是近幾年國內(nèi)外計(jì)算機(jī)科學(xué)研究與應(yīng)用領(lǐng)域中最引人注目的前沿課題之一。網(wǎng)絡(luò)并行計(jì)算以網(wǎng)絡(luò)為基礎(chǔ)，這種并行計(jì)算環(huán)境的顯著優(yōu)點(diǎn)是投資較少、靈活性強(qiáng)等。

作為數(shù)值方法，多層快速多極子法(MLFMA)具有數(shù)值誤差可控、計(jì)算精度高、通用性強(qiáng)和應(yīng)用范圍寬的優(yōu)點(diǎn)。它們對(duì)軟硬件環(huán)境要求低，在一般的PC機(jī)即可開展復(fù)雜目標(biāo)電磁仿真。目標(biāo)散射分析能力主要受限于計(jì)算機(jī)內(nèi)存大小。

一般情況下，MLFMA單機(jī)處理的未知量數(shù)目最大為40萬左右。因此，降低并行MLFMA單機(jī)的內(nèi)存需求，計(jì)算更大未知量的問題就成為我們的主要目的。MLFMA的內(nèi)在并行性包括不變項(xiàng)求解中含有的內(nèi)在并行性。我們很容易發(fā)現(xiàn)平移因子、聚合因子以及配置因子的計(jì)算都是獨(dú)立的，可在多臺(tái)計(jì)算機(jī)上異步進(jìn)行。另外，用MLFMA求解矩陣矢量乘法時(shí)也存在內(nèi)在并行性。

1997年，美國伊利諾依大學(xué)W.C. Chew教授與Demaco公司聯(lián)合推出高效高精度電磁數(shù)值分析軟件FISC，在伊利諾依大學(xué)超級(jí)計(jì)算機(jī)應(yīng)用中心的SGI Cray Origin 2000型計(jì)算機(jī)上求解了203萬未知量的散射問題，而且成功求解了VFY218模型飛機(jī)在8GHz平面波照射下的雙站RCS，未知量高達(dá)999萬。FISC正是基于MLFMA技術(shù)的。其后，S.V. Velamparambil、J.M. Song和W.C. Chew還開發(fā)了FISC的并行版本ScaleME，并行MLFMA得到了迅猛發(fā)展。在這種大趨勢下，本文研究了網(wǎng)絡(luò)并行計(jì)算技術(shù)在MLFMA中的應(yīng)用，給出含240萬未知量金屬球的雙站RCS曲線，初步測試、驗(yàn)證了并行求解大未知量問題的可行性與準(zhǔn)確性。

2 并行多層快速多極子技術(shù)

我們依據(jù)如下步驟進(jìn)行設(shè)計(jì)（可參見表1）：

A. 讀入數(shù)據(jù)，并對(duì)其分層分組

各計(jì)算進(jìn)程同時(shí)讀入RWG網(wǎng)格剖分信息，并為目標(biāo)結(jié)構(gòu)上的RWG單元建立八叉樹結(jié)構(gòu)。

建立八叉樹結(jié)構(gòu)的過程是：首先，選擇能夠包含該結(jié)構(gòu)的最小立方體，即第0層盒子；然后，將這個(gè)盒子均分成8個(gè)子立方體，即第1層盒子；再將第1層盒子均分8部分得到第2層盒子；如此反復(fù)，直到最小盒子的邊長為0.25λ～0.45λ。在各層盒子中，不包含基函數(shù)的盒子將被拋棄。

B. 劃分任務(wù)

在保留原串行算法中八叉樹結(jié)構(gòu)的基礎(chǔ)上，在適當(dāng)層上將整棵樹劃分為多個(gè)子樹，并以子樹為基本單位劃分任務(wù)給各個(gè)從機(jī)。

例如，我們將第1層的8個(gè)盒子分配給8個(gè)從機(jī)分別進(jìn)行處理，此時(shí)我們區(qū)分出各個(gè)從機(jī)所要各自處理的各層非空盒子，并單獨(dú)編號(hào)，完成其與全局各層非空盒子之間的相互索引。

C. 近場矩陣填充及遠(yuǎn)場不變項(xiàng)處理

初始化各從機(jī)處理的近場矩陣，給出各從機(jī)近場矩陣的大小及非零元素位置的索引。

用MLFMA生成的近場矩陣一般都是稀疏化的，如果直接存儲(chǔ)會(huì)造成內(nèi)存的浪費(fèi)，所以要把稀疏化矩陣壓縮存儲(chǔ)。稀疏化矩陣壓縮存儲(chǔ)一般有兩種方法：行壓縮存儲(chǔ)和列壓縮存儲(chǔ).，我們采用行壓縮存儲(chǔ)。

遠(yuǎn)場不變項(xiàng)的處理主要涉及當(dāng)前層的轉(zhuǎn)移因子，父子層之間的平移因子。由于它們占用內(nèi)存相對(duì)較小，我們可以預(yù)先計(jì)算這些遠(yuǎn)場不變項(xiàng)，需要時(shí)即可直接調(diào)用。

表1 并行MLFMA的主機(jī)及從機(jī)流程比較

D. 矩陣矢量乘的處理

首先，各從機(jī)計(jì)算本地存儲(chǔ)的近場矩陣與電流未知量的乘積，再發(fā)送至主機(jī)匯總進(jìn)行處理比較，然后進(jìn)行其他運(yùn)算。