基于可重構(gòu)計(jì)算的純方位目標(biāo)要素解算方法

宋奐寰, 王樹宗

?

基于可重構(gòu)計(jì)算的純方位目標(biāo)要素解算方法

宋奐寰, 王樹宗

(海軍工程大學(xué) 兵器新技術(shù)研究所, 湖北 武漢, 430033)

目標(biāo)運(yùn)動(dòng)要素解算所使用的數(shù)據(jù)處理技術(shù)的性能直接關(guān)系到潛艇作戰(zhàn)系統(tǒng)的反應(yīng)時(shí)間。目前, 對(duì)目標(biāo)運(yùn)動(dòng)要素解算問題的研究多集中在改進(jìn)或使用性能更優(yōu)越的估計(jì)算法。本文在現(xiàn)有算法基礎(chǔ)上, 利用可重構(gòu)計(jì)算技術(shù)作為目標(biāo)運(yùn)動(dòng)要素解算模塊的加速器, 分析純方位平差算法的輸入數(shù)據(jù)流, 通過脈動(dòng)陣列簡(jiǎn)化標(biāo)量運(yùn)算, 充分利用并行流水線機(jī)制, 最終實(shí)現(xiàn)了純方位平差法的可重構(gòu)計(jì)算。試驗(yàn)結(jié)果證明了使用可重構(gòu)計(jì)算能夠提高算法的解算速度。

純方位目標(biāo); 運(yùn)動(dòng)要素解算; 可重構(gòu)計(jì)算; 流水線; 脈動(dòng)陣列

0 引言

目標(biāo)運(yùn)動(dòng)要素解算是潛艇作戰(zhàn)系統(tǒng)的核心任務(wù)之一。作戰(zhàn)系統(tǒng)目標(biāo)運(yùn)動(dòng)要素解算模塊的功能是根據(jù)綜合聲納、綜合雷達(dá)系統(tǒng)的自動(dòng)跟蹤信息或手動(dòng)輸入的數(shù)據(jù)信息解算目標(biāo)的運(yùn)動(dòng)參數(shù),特點(diǎn)是該模塊為數(shù)據(jù)密集型計(jì)算。目標(biāo)運(yùn)動(dòng)要素解算所使用的數(shù)據(jù)處理技術(shù)的性能直接關(guān)系到潛艇作戰(zhàn)系統(tǒng)的反應(yīng)時(shí)間。一直以來, 對(duì)目標(biāo)運(yùn)動(dòng)要素解算問題的研究多集中在改進(jìn)已有的估計(jì)算法或使用性能更優(yōu)越的估計(jì)算法, 使要素解算獲得更好的收斂速度和解算精度, 例如最小二乘估計(jì)、擴(kuò)展卡爾曼濾波、極大似然估計(jì)、而偽線性估計(jì)是其中的典型算法代表。

可重構(gòu)計(jì)算是一種全新計(jì)算方式, 近年來隨著微電子技術(shù)和計(jì)算機(jī)技術(shù)的發(fā)展, 可重構(gòu)計(jì)算的研究條件日趨成熟, 國(guó)內(nèi)外掀起了對(duì)可重構(gòu)計(jì)算的研究熱潮[1]。可重構(gòu)計(jì)算使用集成了可編程硬件的系統(tǒng)進(jìn)行計(jì)算, 該可編程硬件的功能可由一系列實(shí)時(shí)變化的物理可控點(diǎn)來定義, 其底層技術(shù)是現(xiàn)場(chǎng)可編程門陣列(field-programmable gate array, FPGA)技術(shù)[2]。以FPGA為先導(dǎo)的可重構(gòu)計(jì)算技術(shù)的優(yōu)點(diǎn)是, 硬件設(shè)計(jì)的實(shí)現(xiàn)基于軟件的靈活性, 并且保持了傳統(tǒng)的基于硬件方法的執(zhí)行速度, 已經(jīng)成為計(jì)算密集/數(shù)據(jù)密集型算法的加速器。本文基于可重構(gòu)計(jì)算設(shè)計(jì)和實(shí)現(xiàn)目標(biāo)運(yùn)動(dòng)要素的解算算法, 利用可重構(gòu)計(jì)算的并行執(zhí)行特性加速要素解算算法的解算速度, 利用可重構(gòu)計(jì)算柔性重構(gòu)特性, 提高算法精度。利用可重構(gòu)計(jì)算系統(tǒng)開發(fā)應(yīng)用的關(guān)鍵在于設(shè)計(jì)一套適合可重構(gòu)計(jì)算系統(tǒng)實(shí)現(xiàn)的并行算法。本文以基于最小二乘估計(jì)的純方位平差法為研究對(duì)象, 對(duì)于極大似然估計(jì)、擴(kuò)展卡爾曼濾波、偽線性估計(jì)等算法同樣可設(shè)計(jì)合適的并行算法, 在可重構(gòu)計(jì)算系統(tǒng)上得到算法的加速實(shí)現(xiàn)。

1 純方位目標(biāo)運(yùn)動(dòng)要素解算問題描述

取北-東坐標(biāo)系, 假設(shè)當(dāng)本艇先后處于0,1, …,O位置時(shí)測(cè)得目標(biāo)方位分別為0,1, …,b, 并記下各位置的對(duì)應(yīng)時(shí)刻t和本艇位置坐標(biāo)(x,y), Δt=t-t, Δb=b-b, Δx=x-x, Δy=y-y運(yùn)用此算法可求得目標(biāo)的運(yùn)動(dòng)參數(shù)。在目標(biāo)勻速直線運(yùn)動(dòng)假定下, 由方位量測(cè)方程[3]

得到

其中

取待估計(jì)參數(shù)

則基于最小二乘估計(jì)的目標(biāo)運(yùn)動(dòng)要素解算問題就轉(zhuǎn)化為對(duì)下述方程組的解算問題。

=(7)

其中

2 純方位目標(biāo)運(yùn)動(dòng)要素解算并行算法設(shè)計(jì)

利用可重構(gòu)計(jì)算求解方程組=, 關(guān)鍵是把熟知的在通用處理器上串行執(zhí)行的程序(如C語言程序)轉(zhuǎn)換成適合于可重構(gòu)計(jì)算系統(tǒng)的并行執(zhí)行程序(如VHDL, Verilog語言程序), 這種轉(zhuǎn)換需要首先設(shè)計(jì)出高效簡(jiǎn)潔的并行算法。但是, 最小二乘法需要在輸入數(shù)據(jù)間進(jìn)行大量運(yùn)算, 而這不是目標(biāo)運(yùn)動(dòng)要素解算問題所期望的, 因此, 并行算法需要簡(jiǎn)化對(duì)這些輸入數(shù)據(jù)的計(jì)算, 以降低硬件設(shè)計(jì)復(fù)雜度和在不影響計(jì)算高效性的情況下, 使算法使用的可重構(gòu)單元最少。引入通過分解得到的輸入矩陣的直角三角形, 將系數(shù)矩陣轉(zhuǎn)換為一個(gè)上三角矩陣, 可以消除輸入矩陣的一些元素, 從而減少最小二乘法輸入數(shù)據(jù)間的運(yùn)算量[4]。

對(duì)式(7)進(jìn)行如下變換(其中是酉矩陣,是上三角矩陣)

由于是一個(gè)上三角矩陣, 即

因此, 求解就只需進(jìn)行下面的回代過程

根據(jù)上述分析, 利用方程組=解向量就轉(zhuǎn)換為利用方程組=￠解向量, 即對(duì)矩陣求其分解的矩陣(三角陣)和(酉矩陣), 其中￠=。這樣的過程可以通過一系列Givens變換來實(shí)現(xiàn)。Givens矩陣是標(biāo)準(zhǔn)正交矩陣, 也叫平面旋轉(zhuǎn)矩陣, 它是通過坐標(biāo)旋轉(zhuǎn), 將元素的數(shù)值等效到元素上, Givens變換每次只能將一個(gè)元素變?yōu)?。Givens旋轉(zhuǎn)的基本原理如下[4]

式(20)的一個(gè)解為

旋轉(zhuǎn)后兩行矩陣的新值為

3 并行算法的可重構(gòu)計(jì)算實(shí)現(xiàn)

脈動(dòng)陣列可看成算法的硬件實(shí)現(xiàn)結(jié)構(gòu), 它把算法中包含的操作并行性用具有同樣處理功能的處理單元通過簡(jiǎn)單和規(guī)則的通訊互聯(lián)起來[5], 故脈動(dòng)陣列很適合可重構(gòu)計(jì)算系統(tǒng)設(shè)計(jì)。用脈動(dòng)陣列實(shí)現(xiàn)方程組=到=￠的轉(zhuǎn)化如圖1所示。

脈動(dòng)陣列由2種節(jié)點(diǎn)組成: 邊界節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn), 它們對(duì)輸入矩陣和輸入向量的每個(gè)元素執(zhí)行旋轉(zhuǎn)操作, 濾去矩陣中的部分元素, 將矩陣轉(zhuǎn)換為上三角矩陣形式, 對(duì)矩陣的元素進(jìn)行旋轉(zhuǎn)的目的是保證方程組等式成立(對(duì)執(zhí)行某種變換, 對(duì)也需執(zhí)行相同的變換)。

圓形節(jié)點(diǎn)為邊界節(jié)點(diǎn), 是對(duì)輸入數(shù)據(jù)執(zhí)行向量操作, 即將輸入數(shù)據(jù)轉(zhuǎn)化為旋轉(zhuǎn)角度輸出到內(nèi)部節(jié)點(diǎn)(求解上文提到的Givens變換的旋轉(zhuǎn)矩陣)。

方形節(jié)點(diǎn)為內(nèi)部節(jié)點(diǎn), 功能是利用來自邊界節(jié)點(diǎn)的旋轉(zhuǎn)角對(duì)輸入數(shù)據(jù)進(jìn)行旋轉(zhuǎn), 所得數(shù)據(jù)從上到下、從左到右傳遞 (執(zhí)行上文所述Givens變換中矩陣乘法操作)。圖中最后一列內(nèi)部結(jié)點(diǎn)對(duì)方程組=等式右邊的向量進(jìn)行旋轉(zhuǎn), 更新向量的元素(執(zhí)行上文所述Givens變換矩陣乘法操作)。

圖1 純方位目標(biāo)運(yùn)動(dòng)要素解算的脈動(dòng)陣列

依次類推, 將式(24)的3個(gè)矩陣依次移入脈動(dòng)陣列。若不計(jì)正/余弦函數(shù)的CORDIC解算時(shí)間, 轉(zhuǎn)換3×3 D方程組到三角矩陣的形式只需15個(gè)處理周期。

綜上所述, 在可重構(gòu)計(jì)算系統(tǒng)上實(shí)現(xiàn)了從方程=到=￠的轉(zhuǎn)化, 下面介紹在可重構(gòu)計(jì)算系統(tǒng)上求解向量的計(jì)算方法。

式(16)的整個(gè)求解過程從矩陣(25)右下角開始, 從下往上, 從左到右逐步展開。

1) 第1次迭代, 取第3列和第4列的元素

取33和3￠時(shí), 經(jīng)除法運(yùn)算得到

2) 第2次迭代, 取第2列的元素

3) 第3次迭代, 取第1列的元素

在可重構(gòu)計(jì)算系統(tǒng)上實(shí)現(xiàn)上述迭代計(jì)算需要進(jìn)行乘法操作、除法操作和減法操作, 另外還需要存儲(chǔ)器和寄存器存放輸入的方位信息數(shù)據(jù)和解算過程的中間結(jié)果, 多路選擇器用于對(duì)多組輸入數(shù)據(jù)進(jìn)行選擇性輸出。在可重構(gòu)計(jì)算系統(tǒng)上實(shí)現(xiàn)回代法解線性方程組, 只有在輸出穩(wěn)定后才能輸入新的數(shù)據(jù)進(jìn)行下一次計(jì)算, 即算法的節(jié)拍必須大于運(yùn)算電路的延遲, 但如果采用流水線, 就有可能將一個(gè)操作分解為一些小規(guī)模的基本操作, 將中間值存儲(chǔ)在寄存器中, 并在下一個(gè)處理周期內(nèi)繼續(xù)運(yùn)算, 這樣就可以提高電路的利用效率。如圖2所示, 使用了兩個(gè)觸發(fā)器實(shí)現(xiàn)流水線結(jié)構(gòu)。只需6個(gè)處理周期就可完成方程組的迭代求解。

圖2 流水線實(shí)現(xiàn)線性方程組的回代求解

Fig. 2 Pipeline back substitution to realize linear equations

4 試驗(yàn)與算法性能分析

為了證明可重構(gòu)計(jì)算系統(tǒng)可以作為目標(biāo)運(yùn)動(dòng)要素解算模塊的加速器, 本文設(shè)計(jì)選用Xilinx公司的Vertex-4 SX35, Vertex-4 SX35器件。

1) 使用的參數(shù)見表1。

表1 仿真參數(shù)

2) 態(tài)勢(shì)仿真及試驗(yàn)數(shù)據(jù)獲取。根據(jù)表1描述的參數(shù), 生成作戰(zhàn)態(tài)勢(shì)仿真如圖3所示, 仿真顯控臺(tái)上直線航跡是目標(biāo)航跡, 折線航跡是我艇為使純方位平差算法收斂而采取的本艇機(jī)動(dòng)航跡。對(duì)該固定態(tài)勢(shì)進(jìn)行要素解算, 聲納系統(tǒng)獲得的目標(biāo)方位變化率如圖4所示。

圖3 態(tài)勢(shì)圖

記錄每一時(shí)刻我艇位置、推算的目標(biāo)位置、聲納探測(cè)的目標(biāo)方位數(shù)據(jù), 作為輸入信息加載到Vertex-4 SX35器件的Block RAM存儲(chǔ)器。

3) 試驗(yàn)結(jié)果及性能分析

整個(gè)并行算法所使用的可重構(gòu)單元、布線資源等資源如表2所示。該設(shè)計(jì)吞吐量為0.13 M/s, 通過流水線設(shè)計(jì), 吞吐量提高到0.15 M/s。生成上三角矩陣的時(shí)延為777個(gè)處理周期, 回代過程耗費(fèi)156個(gè)處理周期。在實(shí)艇裝備中, 不考慮傳感器系統(tǒng)的處理瓶頸, 在普通臺(tái)式機(jī)上, 利用VC++平臺(tái)運(yùn)行程序目標(biāo)運(yùn)動(dòng)要素解算模塊的仿真程序, 耗時(shí)約125000ns, 因此, 可重構(gòu)計(jì)算系統(tǒng)可以使目標(biāo)運(yùn)動(dòng)要素解算模塊執(zhí)行速度提高約14.9%。

圖4 量測(cè)方位信息圖

表2 資源占用情況及試驗(yàn)結(jié)果

注: 時(shí)鐘頻率: 200 MHz; 時(shí)鐘周期: 368；消耗時(shí)間: 1840 ns

5 結(jié)束語

本文通過研究基于最小二乘估計(jì)的純方位平差算法, 設(shè)計(jì)了專用的運(yùn)算單元, 充分利用并行機(jī)制, 在Vertex-4 SX35器件上實(shí)現(xiàn)了純方位平差算法, 試驗(yàn)結(jié)果證明了設(shè)計(jì)合理的并行算法, 利用可重構(gòu)計(jì)算可以提高目標(biāo)運(yùn)動(dòng)要素解算模塊的執(zhí)行速度。

[1] 王志遠(yuǎn), 王建華, 余旸. 可重構(gòu)計(jì)算綜述[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2009, 30(6): 1203-1207.

Wang Zhi-yuan, Wang Jian-hua, Yu Yang. Reconfigurable Computing Summarizing[J]. Journal of Chinese Computer Systems, 2009, 30(6): 1203-1207.

[2] Compton K, Hauck S. Reconfigurable Computing: A Survey of Systems and Software[J]. ACM Computing Surveys, 2002, 34(2): 171-120.

[3] 李洪瑞. 水下目標(biāo)運(yùn)動(dòng)分析關(guān)鍵技術(shù)研究[D]. 南京: 南京理工大學(xué), 2009: 16-30.

[4] Xilinx. AccelWare Reference Designs User Guide[M]. China: Xilinx, 2009.

[5] H T, W M. Matrix Trangularization by Systolic Arrays[C]// Proceedings of the Meeting, United States, 1981.

Bearing-only Target Motion Elements Solver Based on Reconfigurable Computing

SONG Huan-huan, WANG Shu-zong

(Naval Research Institute of New Weaponry Technology and Application, Navy University of Engineering, Wuhan 430033, China)

Reaction time of submarine combat system depends on data processing technology used in target motion elements solver. Based on existing algorithms, reconfigurable computing system is taken as accelerator of target motion elements solver to analyze the input data stream of bearing-adjustment algorithm, and simplify scalar operation of systolic array. Reconfigurable computing of bearing-adjustment algorithm is implemented by using pipeline parallel principle. Experimental results verify that reconfigurable computing can accelerate execution speed of the algorithm.

bearing-only target; motion elements solver; reconfigurable computing; pipeline; systolic array

E925.66; O141.4

A

1673-1948(2012)03-0236-05

2012-01-10;

2012-02-22.

國(guó)防973項(xiàng)目(613660202); 中國(guó)博士后科學(xué)基金項(xiàng)目(200902668).

宋奐寰(1983-), 女, 在讀博士, 主要研究方向?yàn)闈撏ё鲬?zhàn)系統(tǒng)目標(biāo)跟蹤.

(責(zé)任編輯: 許妍)