基于FPGA的反投影算法并行化實現

魯亞楠，魯恒亞,2，潘紅兵,2，李 麗,2，何書專,2，沙 金,2，李 偉,2

(1. 南京大學電子科學與工程學院微電子設計研究所，南京 210 093；2. 江蘇省光電信息功能材料重點實驗室，南京 210 093)

基于FPGA的反投影算法并行化實現

魯亞楠1，魯恒亞1,2，潘紅兵1,2，李 麗1,2，何書專1,2，沙 金1,2，李 偉1,2

(1. 南京大學電子科學與工程學院微電子設計研究所，南京 210 093；2. 江蘇省光電信息功能材料重點實驗室，南京 210 093)

反投影算法是一種基于時域處理的雷達成像算法。針對該算法運算效率低、處理速度慢的問題，通過分析反投影算法的原理及其運算過程，提出一種算法并行化加速方法，即基于現場可編程門陣列，將算法中的反投影運算單元設計成專用的反投影運算硬件加速模塊，并通過模塊內的流水線處理及多個模塊間的并行計算提高該算法的運算效率。運用該方法對2 048×4 096大小的目標網格點進行反投影成像，成像時間為139 s，平均單點成像時間是基于GPU加速方法的3倍，并且成像結果和計算機成像結果誤差極小。實驗結果表明，該并行化方法可有效提高反投影算法的運算效率。

反投影算法；反投影運算模塊；合成孔徑雷達；批處理；并行化；現場可編程門陣列

1 概述

反投影(Back P rojection, BP)算法是一種基于時域處理的合成孔徑雷達(Synthetic Aperture Radar, SAR)成像算法，其基本原理是將雷達回波數據反向投影到成像區域的每個像素點，像素的值可通過計算雷達回波在雷達天線和圖像像素之間距離的延時累加來確定。該算法用時延代替了相位的概念，故與頻率無關，適用于載機任意運動的SAR成像，具有重要的研究價值[1-2]。盡管BP算法可以不加任何近似地應用在SAR成像中，但是它最大的缺點是計算量大、計算效率低，因此，如何快速地實現BP算法成了當前研究的熱點[3-4]。

對于運算量大的算法，可以從以下3個方面入手提高其運算效率：(1)通過改進算法本身降低算法的運算復雜度；(2)設計先進的運算架構；(3)并行化處理。文獻[5-6]從不同方面對算法進行改進，使算法的運算量從傳統BP的N3減小到N2lbN，降低了算法的復雜度，但均需特定的條件。文獻[7]基于多核，從系統架構和并行化的角度提高算法的運算效率，但消耗較多資源。文獻[8]基于圖像處理器(Graphic Processing Un it, GPU)將BP算法進行并行化處理，提高了算法的運算效率，減少了運算時間。

鑒于BP算法中各像素點的計算過程相同且相互獨立，對該算法進行并行化處理是一種非常有效的提高運算效率的方法。本文以提高算法運算速度為出發點，提出模塊內流水并行處理、模塊間流水線架構的并行化實現方案，即基于現場可編程門陣列(Field P rogrammable Ga te Arra y, FPGA)，設計專用的反投影運算模塊，通過多個反投影運算模塊的并行以及模塊內部的流水并行實現算法的加速。

本文對BP算法的原理進行簡要介紹，根據算法的特點設計硬件模塊，詳細闡述該硬件設計的思想，介紹多個模塊并行處理的運算架構，測試了該方案，并對實驗結果予以分析。

2 BP算法分析

其中，t為快時間；n為慢時間；A0為幅度；w(n)為窗函數；K0=4πf0/C ；f0為載頻；總斜距R可表示為：

圖1 移變雙基地SAR的幾何模型

對每一個目標成像點，BP算法首先計算它到收發平臺的雙程時延，將對應時域回波信號沿孔徑方向進行相干累加，使來自該像素點的回波信號同相，從而得到加強，而來自其他點的回波信號則由于相位不同，疊加結果趨于零。

算法的關鍵步驟如下：

(1)距離向匹配濾波；

(2)插值并重采樣；

(3)反投影：

1)計算各成像點的雙程時延，找到相應的回波信號；

2)對該信號進行多普勒相位補償；

3)疊加到原像素點；

(4)重復步驟(1)～步驟(3)直到所有回波數據均反投影完。

由上述分析可見，各像素點之間的反投影計算相互獨立，使該算法非常適合并行化。接下來詳細介紹反投影運算部分的并行化實現過程。

3 BP運算模塊內流水并行

反投影運算模塊是該算法的核心模塊也是基本模塊，計算過程基本上都在本模塊實現。其基本結構如圖2所示，距離計算模塊從存儲器中讀入初始坐標及目標圖像的分辨率，然后計算其距離；相位補償模塊和延時模塊計算相位補償參數及讀取相應的回波數據，將兩者相乘，將其累加到原像素點上，最后將結果存入相應的存儲器中。

圖2 BP運算模塊結構示意圖

本文通過以下2種方式實現算法的優化：(1)由于計算延時模塊和計算相位補償系數模塊相互獨立，因此將延時計算和相位補償參數計算并行處理來縮短運算時間；(2)在設計中引入批處理的概念[9]，即在BP運算前按順序(行或者列)將反投影前的像素點存儲在存儲器中，待運算開始時，相干累加模塊中的地址生成單元讀取像素點存放的首地址，然后每經一個時鐘周期后，依次產生后續每個像素點的存儲地址。而對于每種給定的運算，執行所需要的時鐘周期數是一定的，因此，按照指令流水級，從第一個像素點反投影運算完成后，每經一個時鐘周期，依次完成后續每個像素點的反投影運算。

對于反投影運算模塊，采用批處理的方式，其優點在于，可充分利用每一個時鐘周期，最大限度減少各子模塊空閑等待時間，減少了不必要的時間和資源開銷，從而提高了運算效率。本模塊中流水建立的時間為132個周期，當一次批處理4 096個像素點時，其加速比可達128，具有顯著的加速效果。

經ISE綜合，該模塊時鐘頻率可達126 MHz，占用LUT 共7 188個，寄存器10 331個，占用資源也很少。

4 BP運算模塊間的流水并行

在BP算法中，每一個像素點均需進行多次反投影運算，且各次反投影運算順序進行，適合采用流水并行的方式實現。以像素塊為單位(如4 09 6×1)，通過多個BP運算模塊的流水并行實現算法的進一步加速。考慮到大規模成像時，像素點太多，為節省片上存儲資源，可將像素點存儲在片外，需要進行某一個像素塊BP運算時，再讀取到片上存儲器進行運算。圖3給出了各模塊間流水的基本原理。

圖3 反投影運算模塊間流水示意圖

存儲器中存放的是像素塊值，第k次BP運算時，每個BP模塊從各自的源存儲器中讀取像素數據，并將反投影后的像素值存儲在相應的目的存儲器中。當所有像素點都完成BP運算后，通過頂層軟件的控制，切換各模塊的源存儲器、目的存儲器地址，然后進行下一次的BP運算。這樣，前一個BP模塊的運算結果可直接為后一個BP模塊所利用，通過這種簡單的地址切換，可有效避免數據搬運的時間消耗；另外，由于每個BP運算模塊處理點數相同，運算時間也相同，因此各BP模塊之間相互同步，從而實現各級流水線的無縫對接，獲到較高的數據吞吐率，有效地實現了算法的并行化。

5 實驗結果與分析

本實驗以ARM946[10]和Xilinx公司的Virtex-6 FPGA[11]芯片為測試平臺。

考慮到算法還涉及到距離壓縮等其他運算，本文將ARM作為主控核，以自主研發的片上系統為實驗平臺對該方案進行測試，系統架構如圖4所示[12]。

圖4 實驗系統架構

考慮到FPGA中有限的存儲資源，本次實驗僅集成8個BP模塊，若采用更高系列的FPGA，可集成更多的BP模塊。ARM通過AHB總線實現對協處理器、FFT及BP模塊的控制，完成算法中的相應運算。協處理器和FFT協同完成算法中的距離壓縮和插值部分，BP-core則完成反投影運算部分。

目標成像區域網格點大小為2 048(A)×4 096(R)。本文實驗集成8個BP反投影模塊進行測試，其中，每個BP模塊每次處理4 096個像素點。對多點目標進行BP算法成像仿真，系統參數為：R=3 000 m，V=110.0 m/s，Theta=65.5°，Tp=10 μs，B=180 MH z，Fs=200 MH z，PRF=1 00 0，F0= 9.6 GHz。最終結果如圖5所示。

圖5 成像結果

由圖5可見，并行化方案反投影成像效果非常好。實驗最終成像時間為182 s，平均每點反投影時間為21.69e–6 s。文獻[8]基于GPU的加速方法，實現1 500×1 500大小網格點反投影的時間為139 s，則平均每點的反投影時間為61.77e–6 s。

由此可見，本文實現方法的加速效果明顯。且將該成圖與計算機計算結果相比，成像質量基本一致，相似度達99%以上。

本文實驗平臺以ARM作為主控核，時鐘頻率上限不超過100 MH z。若采用更高性能的主控核，或者將該模塊封裝為IP核，獨立于ARM，則運算速度會進一步提高。另外，本文實驗僅集成8個BP模塊流水并行，若采用更高性能的FPGA，則可集成更多的BP運算模塊，并行度更高。

6 結束語

本文基于FPGA，提出一種BP算法的并行化方法。實驗結果表明，本文方法在計算速度和成像效果上都取得了令人滿意的結果，且在單個像素點的處理速度上優于基于GPU的并行化方法。但是，該方法消耗片上存儲資源較多，減少片上存儲資源的使用及進一步提高算法的并行度，是下一步需要改進之處。

[1] 粟 毅, 匡綱要, 陸仲良. 反向投影成像算法的理論分析及目標特征恢復[J]. 系統工程與電子技術, 2000, 22(2): 70-72.

[2] Yu Ding. A Fast Back-proj ection Algorithm for Bistatic SA R Imaging[C]//Proc. of Internation al Confere nce on Image Processing. Rochester, USA: IEEE Press, 2002: 449- 452.

[3] Y egulalp A F. Fast Bac kprojection Algorithm for Synthetic Aperture Ra dar[C]//Proc. of Radar Conferenc e. Waltham, USA: IEEE Press, 1999: 60-65.

[4] Ulander L M H, Froelind P O, Anders G, et al. Fast Factorized Back-projection for Bistatic SAR Processing[C]//Proc. of the 8th Europea n Conference on Synthetic Apert ure Radar. Aachen, Germany: IEEE Press, 2010: 1-4.

[5] Li Yanguan, Wang Yuming, Jin Tian, et al. Fast Back Projection Imaging for Arbitrary Aperture[J]. Systems Engine ering and Electronics, 2011, 33(7): 1443-1448.

[6] Liu Guangping, Liang Dia nnong. A F ast Back-projection Algorithm for the SAR with Lar ge Scene and High Resolution[J]. Systems Engin eering and Electro nics, 2003, 25(5): 346-349.

[7] Park J, Tang P T P, Sm elyanskiy M, et al. Efficient

Backprojection-based Synthetic Aperture Radar Computation with Many-core Processors[C]//Proc. of International Conference on High P erformance Computing, Networking, Storage and Analysis. Salt Lake City, USA: IEEE Press, 2012: 1-11.

[8] Zhang Xin, Zhang Xiaoling, Shi Jun, et al. GPU-based Parallel Back Projection A lgorithm for the Translational V ariant BiSAR Imaging[C]//Proc. of IEEE International Geoscience and Remote Sen sing Symposium. Vancouver, Canada: IEEE Press, 2011: 2841-2844.

[9] 韓正飛, 李勁松, 潘紅兵. 基于FPGA的浮點向量協處理器設計[J]. 計算機工程, 2012, 38(5): 251-254.

[10] ARM Inc.. ARM946E-S(Rev1)System-on-Chip DSP Enhanced Processor Pro duct Overview[EB/OL]. (2010-05-1 5). http:// www.arm.com/products/processors/classic/arm9/arm946.ph.

[11] X ilinx Inc.. V irtex-6 Family[EB/OL]. (2010-01-12). http:// www. xilinx.com/products/virtex6.

[12] 黃曉林, 潘紅兵, 易 偉. 基于多FPGA的NoC多核處理器驗證平臺設計[J]. 計算機工程與設計, 2012, 33(1): 180-185.

編輯 顧逸斐

Parallelization Implementation of Back Projection Algorithm Based on FPGA

LU Ya-nan1, LU Heng-ya1,2, PAN Hong-bing1,2, LI Li1,2, HE Shu-zhuan1,2, SHA Jin1,2, LI Wei1,2

(1. Institute of Microelectronic Design, School of Electronic Science and Engineering, Nanjing University, Nanjing 210093, China; 2. Jiangsu Provincial Key Laboratory of Photonic and Electronic Materials Science and Technolgy, Nanjing 210093, China)

The Back Projection(B P) algorithm is a radar imaging algorithm bas ed on time-domain processing. Aiming at the low computing efficiency and slow processing speed of BP algorithm, this paper proposes a parallel method after analyzing its princ iple and operation process. It an alyzes the parallelization feasibility of the BP algorithm, an d designs a dedicated BP operation module based on Field Programmable Gate Array(FPGA). To achieve the paralleliza tion of the algori thm water treatment w ithin a module and parall el processing between modules are adopted to speed up computations. It consumes 139 s to complete the computing of 2 048×4 096 target grid points using this method. The average time for a single-point is 3 times faster than the method based on GPU, and the imaging quality is as good as the resu lts of computer imaging. Experimental result show s that the p arallel method can ef fectively improve the op eration efficiency of the BP algorithm.

Back Projection(BP) algorithm; BP calculation module; Synthetic Aperture Radar(SAR); batch processing; parallelization; Field Programmable Gate Array(FPGA)

10.3969/j.issn.1000-3428.2014.05.059

國家自然科學基金資助項目(61176024, 61006018)；高等學校博士學科點專項科研基金資助項目(20120091110029)；江蘇高校優勢學科建設工程基金資助項目。

魯亞楠(1989－)，女，碩士研究生，主研方向：基于多核處理器的軟件設計；魯恒亞，碩士研究生；潘紅兵、李 麗，教授；何書專，工程師；沙 金，副教授；李 偉，工程師。

2013-03-05

2013-05-13E-mail：luyanan27@163.com

1000-3428(2014)05-0285-04

A

TP301.6