基于FPGA的反投影算法并行化實現(xiàn)

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

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

基于FPGA的反投影算法并行化實現(xiàn)

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

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

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

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

1 概述

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

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

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

本文對BP算法的原理進(jìn)行簡要介紹，根據(jù)算法的特點設(shè)計硬件模塊，詳細(xì)闡述該硬件設(shè)計的思想，介紹多個模塊并行處理的運算架構(gòu)，測試了該方案，并對實驗結(jié)果予以分析。

2 BP算法分析

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

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

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

算法的關(guān)鍵步驟如下：

(1)距離向匹配濾波；

(2)插值并重采樣；

(3)反投影：

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

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

3)疊加到原像素點；

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

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

3 BP運算模塊內(nèi)流水并行

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

圖2 BP運算模塊結(jié)構(gòu)示意圖

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

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

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

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

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

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

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

5 實驗結(jié)果與分析

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

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

圖4 實驗系統(tǒng)架構(gòu)

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

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

圖5 成像結(jié)果

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

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

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

6 結(jié)束語

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

[1] 粟 毅, 匡綱要, 陸仲良. 反向投影成像算法的理論分析及目標(biāo)特征恢復(fù)[J]. 系統(tǒng)工程與電子技術(shù), 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的浮點向量協(xié)處理器設(shè)計[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多核處理器驗證平臺設(shè)計[J]. 計算機工程與設(shè)計, 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

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

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

2013-03-05

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

1000-3428(2014)05-0285-04

A

TP301.6