劉 帥， 李 智， 王 晶

（1.裝備學院 研究生管理大隊，北京101416； 2.裝備學院 重點實驗室，北京101416； 3.91336部隊）

在求解拋物型波動方程時，Hardin和Tappert于1973年提出了一種分步傅里葉變換算法［1］，該算法是一種采用FFT技術的頻域算法，其計算不受波長限制，在求解大區(qū)域電波傳播問題中得到了廣泛的應用。該算法屬于一種步進迭代算法，當計算區(qū)域采樣點數(shù)或迭代次數(shù)增加時，計算速度便會下降。

FFTW是由麻省理工學院（MIT）的Frigo和Johnson基于C語言開發(fā)的程序庫［2］，能夠高效地進行任意維數(shù)的離散傅里葉變換（DFT）、離散正弦變換（DST）以及離散余弦變換（DCT），是目前公認的最有效的變換工具。它能夠根據(jù)用戶的底層硬件屬性如緩存、內(nèi)存、寄存器大小等，自動調(diào)整算法參數(shù)，以獲得最優(yōu)方案。FFTW2.1.5和最新的FFTW3.3Alpha測試版還能夠支持共享存儲多線程并行和分布式存儲MPI（消息傳遞接口）并行［3］。

為解決適應波動方程計算量大、計算速度慢的問題，作者借助于FFTW庫研究了SSFT算法的并行方案，測試結果表明，所設計方案是有效的。

1 SSFT算法介紹

為闡述方便，先對SSFT算法的計算過程做簡要的介紹。無論是三維還是二維情況，采用Feit－Fleck近 似 的 拋 物 型 波 動 方 程［4－6］都 可 以 化為如下形式

這樣拋物方程的解可以近似為

稱B為折射算子，A為繞射算子。在SSFT算法中，折射部分的計算在空間域內(nèi)進行，繞射部分，也就是exp（ΔxA）u部分的計算在變換域即頻域內(nèi)進行，最終結果為

在一個計算步長Δx內(nèi)，計算被分解成4個步驟：

1）計算初始場分布的傅氏變換U0＝F（u）；

2）繞射步計算T1＝exp（ΔxA）F（u）；

3）對T1計 算 其 傅 氏 反 變 換T2＝F－1（exp（ΔxA）F（u））；

4）折射步計算u（x＋Δx）＝exp（ΔxB）·F－1（exp（ΔxA）F（u））。

本文提出的并行方案正是立足于上述計算步驟，通過將數(shù)組拆分成較小規(guī)模的子數(shù)組，分布到多個進程分別計算，實現(xiàn)循環(huán)級的并行粒度。對于第2）和第4）步驟，由于只涉及對應點之間簡單的復數(shù)乘法運算，在各個進程內(nèi)部的數(shù)組上便可完成，無需進程間的通信，故有著直觀的獨立性或并發(fā)性。而第1）、第3）步的傅氏變換，依據(jù)定義，計算一個點需要變換前數(shù)組的所有點參與，將數(shù)組分發(fā)到各個進程后，這種計算必然涉及通信，事實上，通信正是影響傅氏變換并行算法的關鍵所在，因而第1）、第3）步構成了整個SSFT算法的計算核心。

2 基于FFTW庫的并行方案

在介紹并行方案之前先給出評價并行算法的一個關鍵指標，即并行加速比，該值越大表明并行算法越高效。

并行加速比［7－8］：設串行執(zhí)行時間為Ts，使用P個進程（或處理器）并行執(zhí)行的時間為Tp（P），則加速比為

本文測試環(huán)境是實驗室配備的銀河集群機的一個機組，包含10個節(jié)點。每個節(jié)點集成2個Intel新一代Xeon高性能64位微處理器，配置有24G內(nèi) 存、146G硬 盤。

文中所提出的SSFT算法并行方案核心，就是利用支持分布式存儲的FFTW并行庫實現(xiàn)計算過程中傅氏變換的計算，具體有2種思路。

1）串－并－串模式：即只對第1）、第3）步傅氏變換部分采用并行計算，其余步驟仍然在單個節(jié)點計算，算法流程圖如圖1，其中黑色雙向箭頭表示進程之間的通信。

圖1 串－并－串模式流程圖

2）分布式模式：此種模式下，除了傅氏變換的步驟外，繞射項和折射項的計算過程也分布到各個進程內(nèi)進行，即預先將繞射項、折射項的指數(shù)數(shù)組計算好并分發(fā)到各個進程。此模式由于省去了各進程與主進程間的通信，整個算法的效率要高于第一種模式，流程圖如圖2。

圖2 分布式模式流程圖

本文所提并行方案具備通用性，在任何集群環(huán)境下都可以適用。

3 測試結果

為了測試方案的效果，需要不同的測試條件，包括采樣點數(shù)、啟動的進程數(shù)以及循環(huán)的步數(shù)。在不影響評價算法性能的前提下，本文取定循環(huán)的步數(shù)為Ns＝1 000。所有計時工作都是基于墻上時鐘進行的。表1、表2為二維情況測試結果，表3為三維情況測試結果，其中P欄表示啟動的進程數(shù)，P＝1即表示串行執(zhí)行。

表1 串－并－串模式并行方案測試結果

表2 分布式模式并行方案測試結果

表3 3DSSFT基于FFTW庫并行方案測試結果

由表1中數(shù)據(jù)可知，當高度方向采樣點數(shù)N一定時，隨著啟動的進程數(shù)的增加，加速比呈上升趨勢；當進程數(shù)一定時，隨著采樣點數(shù)的增加，加速比也呈上升趨勢，這符合預期的設想。

表2亦表明，隨著問題規(guī)模（N）的擴大和進程數(shù)（P）的增加，加速比也隨之增大。對比表2中的數(shù)據(jù)，同等測試條件下分布式模式的加速比要優(yōu)于串－并－串模式，這得益于第二種模式省去了一些全局收集操作，節(jié)約了通信開支。

由表3可看出，并行加速比是進程數(shù)和問題規(guī)模的增函數(shù)，隨著問題規(guī)模的增大和進程數(shù)的增加，并行加速比呈上升趨勢，且由于三維情況涉及的計算量更大，采用并行計算后速度提升更明顯。

4 結 論

拋物型波動方程在電波傳播預測、電磁環(huán)境數(shù)據(jù)生成等領域有著重要的應用，而用于求解此類方程的SSFT算法逐漸成為研究的熱點。為了使求解過程更加快速，本文將并行計算技術引入到SSFT算法中，基于FFTW庫研究了2種并行方案：串－并－串模式和分布式模式。測試結果表明，本文方案能夠有效實現(xiàn)SSFT求解過程的加速，為相關問題研究提供思路。下一步工作將繼續(xù)完成多種條件下方案的測試，以期得到方案的性能曲線，找到最佳配置狀態(tài)。

（

）

［1］HARDIN R H，TAPPERT F D.Applications of the splitstep Fourier method to the numerical solution of nonlinear and variable coefficient wave equations［J］.SIAM Review Chronicle，1973，15：423.

［2］FRIGO M，JOHNSON S.FFTW：An adaptive software architecture for the FFT［C］／／IEEE.Proceedings of the IEEE International Conference on Acoustics，Speech，and Signal Processing.Seattle，WA，USA：IEEE，1998：1381－1384.

［3］FRIGO M.FFTW home page［EB／OL］.［2010－10－20］.http：／／www.fftw.org.

［4］胡繪斌.預測復雜環(huán)境下電波傳播特性的算法研究［D］.長沙：國防科技大學，2006：18－19.

［5］LEVY M F.Parabolic equation methods for electromagnetic wave propagation［M］.London：London IEE Press，2000：21－22.

［6］THIEM K B.A 3Dparabolic equation（PE）based technique for predicting propagation path loss in an urban area［D］.California：Naval Postgraduate School，2001：6－9.

［7］陳國良.并行算法的設計與分析［M］.北京：高等教育出版社，1994：16.

［8］李曉梅，吳建平.數(shù)值并行算法與軟件［M］.北京：科學出版社，2007：22.