基于可重構計算的純方位目標要素解算方法

宋奐寰, 王樹宗

?

基于可重構計算的純方位目標要素解算方法

宋奐寰, 王樹宗

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

目標運動要素解算所使用的數據處理技術的性能直接關系到潛艇作戰系統的反應時間。目前, 對目標運動要素解算問題的研究多集中在改進或使用性能更優越的估計算法。本文在現有算法基礎上, 利用可重構計算技術作為目標運動要素解算模塊的加速器, 分析純方位平差算法的輸入數據流, 通過脈動陣列簡化標量運算, 充分利用并行流水線機制, 最終實現了純方位平差法的可重構計算。試驗結果證明了使用可重構計算能夠提高算法的解算速度。

純方位目標; 運動要素解算; 可重構計算; 流水線; 脈動陣列

0 引言

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

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

1 純方位目標運動要素解算問題描述

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

得到

其中

取待估計參數

則基于最小二乘估計的目標運動要素解算問題就轉化為對下述方程組的解算問題。

=(7)

其中

2 純方位目標運動要素解算并行算法設計

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

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

由于是一個上三角矩陣, 即

因此, 求解就只需進行下面的回代過程

根據上述分析, 利用方程組=解向量就轉換為利用方程組=￠解向量, 即對矩陣求其分解的矩陣(三角陣)和(酉矩陣), 其中￠=。這樣的過程可以通過一系列Givens變換來實現。Givens矩陣是標準正交矩陣, 也叫平面旋轉矩陣, 它是通過坐標旋轉, 將元素的數值等效到元素上, Givens變換每次只能將一個元素變為0。Givens旋轉的基本原理如下[4]

式(20)的一個解為

旋轉后兩行矩陣的新值為

3 并行算法的可重構計算實現

脈動陣列可看成算法的硬件實現結構, 它把算法中包含的操作并行性用具有同樣處理功能的處理單元通過簡單和規則的通訊互聯起來[5], 故脈動陣列很適合可重構計算系統設計。用脈動陣列實現方程組=到=￠的轉化如圖1所示。

脈動陣列由2種節點組成: 邊界節點和內部節點, 它們對輸入矩陣和輸入向量的每個元素執行旋轉操作, 濾去矩陣中的部分元素, 將矩陣轉換為上三角矩陣形式, 對矩陣的元素進行旋轉的目的是保證方程組等式成立(對執行某種變換, 對也需執行相同的變換)。

圓形節點為邊界節點, 是對輸入數據執行向量操作, 即將輸入數據轉化為旋轉角度輸出到內部節點(求解上文提到的Givens變換的旋轉矩陣)。

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

圖1 純方位目標運動要素解算的脈動陣列

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

綜上所述, 在可重構計算系統上實現了從方程=到=￠的轉化, 下面介紹在可重構計算系統上求解向量的計算方法。

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

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

取33和3￠時, 經除法運算得到

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

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

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

圖2 流水線實現線性方程組的回代求解

Fig. 2 Pipeline back substitution to realize linear equations

4 試驗與算法性能分析

為了證明可重構計算系統可以作為目標運動要素解算模塊的加速器, 本文設計選用Xilinx公司的Vertex-4 SX35, Vertex-4 SX35器件。

1) 使用的參數見表1。

表1 仿真參數

2) 態勢仿真及試驗數據獲取。根據表1描述的參數, 生成作戰態勢仿真如圖3所示, 仿真顯控臺上直線航跡是目標航跡, 折線航跡是我艇為使純方位平差算法收斂而采取的本艇機動航跡。對該固定態勢進行要素解算, 聲納系統獲得的目標方位變化率如圖4所示。

圖3 態勢圖

記錄每一時刻我艇位置、推算的目標位置、聲納探測的目標方位數據, 作為輸入信息加載到Vertex-4 SX35器件的Block RAM存儲器。

3) 試驗結果及性能分析

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

圖4 量測方位信息圖

表2 資源占用情況及試驗結果

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

5 結束語

本文通過研究基于最小二乘估計的純方位平差算法, 設計了專用的運算單元, 充分利用并行機制, 在Vertex-4 SX35器件上實現了純方位平差算法, 試驗結果證明了設計合理的并行算法, 利用可重構計算可以提高目標運動要素解算模塊的執行速度。

[1] 王志遠, 王建華, 余旸. 可重構計算綜述[J]. 小型微型計算機系統, 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] 李洪瑞. 水下目標運動分析關鍵技術研究[D]. 南京: 南京理工大學, 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.

國防973項目(613660202); 中國博士后科學基金項目(200902668).

宋奐寰(1983-), 女, 在讀博士, 主要研究方向為潛艇作戰系統目標跟蹤.

(責任編輯: 許妍)