1 引言

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

作為數值方法，多層快速多極子法(MLFMA)具有數值誤差可控、計算精度高、通用性強和應用范圍寬的優點。它們對軟硬件環境要求低，在一般的PC機即可開展復雜目標電磁仿真。目標散射分析能力主要受限于計算機內存大小。

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

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

2 并行多層快速多極子技術

我們依據如下步驟進行設計（可參見表1）：

A. 讀入數據，并對其分層分組

各計算進程同時讀入RWG網格剖分信息，并為目標結構上的RWG單元建立八叉樹結構。

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

B. 劃分任務

在保留原串行算法中八叉樹結構的基礎上，在適當層上將整棵樹劃分為多個子樹，并以子樹為基本單位劃分任務給各個從機。

例如，我們將第1層的8個盒子分配給8個從機分別進行處理，此時我們區分出各個從機所要各自處理的各層非空盒子，并單獨編號，完成其與全局各層非空盒子之間的相互索引。

C. 近場矩陣填充及遠場不變項處理

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

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

遠場不變項的處理主要涉及當前層的轉移因子，父子層之間的平移因子。由于它們占用內存相對較小，我們可以預先計算這些遠場不變項，需要時即可直接調用。

表1 并行MLFMA的主機及從機流程比較

D. 矩陣矢量乘的處理

首先，各從機計算本地存儲的近場矩陣與電流未知量的乘積，再發送至主機匯總進行處理比較，然后進行其他運算。