錢孝桃，劉 超

（南京電子技術(shù)研究所 江蘇 南京 210039）

在雷達(dá)抗干擾處理以及空時(shí)二維處理過(guò)程中數(shù)據(jù)排序?qū)⒈夭豢擅鈁1]，在傳統(tǒng)的DSP、CPU等常規(guī)軟件排序已經(jīng)不能夠滿足雷達(dá)系統(tǒng)實(shí)時(shí)性要求，使用FPGA排序的趨勢(shì)將勢(shì)不可當(dāng)。FPGA由于具有較高的并行處理能力，目前已成為雷達(dá)陣列信號(hào)處理中的主流處理器件。計(jì)算耗費(fèi)的時(shí)間和消耗的硬件資源成為處理的主要矛盾，如何解決這個(gè)矛盾，本人將提出解決方案。

1 算法描述與分析

排序就是將數(shù)據(jù)元素的一個(gè)任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列[2]。各種傳統(tǒng)串行排序算法如冒泡，大多都是以兩兩之間順序比較為基礎(chǔ)[3]，不能滿足實(shí)時(shí)性要求。如果將傳統(tǒng)的串行排序在FPGA中進(jìn)行分段串行排序再排序，可以減少排序時(shí)間，但卻大大增加設(shè)計(jì)難度。本文提出基于并行比較思路，通過(guò)將邏輯比較結(jié)果求和，用此和值確定排序結(jié)果的位置，從而達(dá)到實(shí)現(xiàn)排序結(jié)果的目的。

圖1 算法示意圖Fig.1 Algorithm diagram

假設(shè)待排序數(shù)據(jù)元素個(gè)數(shù)為N，全并行比較就是在同一時(shí)刻將N個(gè)數(shù)兩兩比較，再在下一時(shí)刻進(jìn)行累加求和以確定排序結(jié)果。這樣需要耗費(fèi)N*N個(gè)比較器，如果元素個(gè)數(shù)較多，將耗費(fèi)大量邏輯資源。本算法采用N個(gè)比較器，用N倍時(shí)間實(shí)現(xiàn)比較。算法如上圖所示。

不同的比較器將有不同的比較結(jié)果輸出，下表列出了4種比較器輸出結(jié)果形式。

表1 4種比較器結(jié)果形式Tab.1 The format of result for four comparisons

2 工程實(shí)現(xiàn)

排序算法在FPGA內(nèi)進(jìn)行，整個(gè)實(shí)現(xiàn)過(guò)程如下圖。使用verilog語(yǔ)言設(shè)計(jì)，做到模塊化、參數(shù)化，以適應(yīng)不同數(shù)量的排序以及各自邏輯資源的控制，主要有以下幾步：

1)將流水線上的待排序的N個(gè)數(shù)據(jù)存儲(chǔ)到RAM中，同時(shí)對(duì)相等值數(shù)量的RAM寫(xiě)零；

2)讀取N個(gè)賦給N個(gè)變量準(zhǔn)備比較；

3)讀取數(shù)據(jù)和N個(gè)變量同時(shí)比較；

4)將比較結(jié)果累加求和；

5)將和值作為地址讀取此數(shù)據(jù)的個(gè)數(shù)，將此個(gè)數(shù)和累加和相加寫(xiě)到排序結(jié)果RAM中，同時(shí)將個(gè)數(shù)加1寫(xiě)入相等值數(shù)量的RAM中。

圖2 工程實(shí)現(xiàn)框圖Fig.2 Project realizing frame

相等值數(shù)量RAM主要處理待排序數(shù)據(jù)流有過(guò)個(gè)相同數(shù)值大小的數(shù)據(jù)排序的情況。

讀取N個(gè)賦給N個(gè)變量準(zhǔn)備比較需要N個(gè)時(shí)鐘周期，比較需要N個(gè)時(shí)鐘周期，多級(jí)累加需要3*N個(gè)時(shí)鐘周期（N≤512），相同數(shù)值排序需要3*N個(gè)時(shí)鐘周期，合計(jì)需要8*N個(gè)時(shí)鐘周期。

3 仿真與驗(yàn)證

本算法Verilog代碼以及IP核模塊的新建基于Xilinx vp690[4]，功能級(jí)仿真在Modsim[5]中完成。圖3是待排序數(shù)據(jù)流截圖，待排序數(shù)據(jù)是從20到319的300個(gè)遞增數(shù)據(jù)，圖4是圖3輸入數(shù)據(jù)的從小到大的排序結(jié)果，其中m_data_h是是排序后原先數(shù)據(jù)的序號(hào)，m_data_l是排序后從小到大的結(jié)果；為了驗(yàn)證相同數(shù)值的排序情況，將上述待排序數(shù)據(jù)的第2、39個(gè)數(shù)改成和第1個(gè)數(shù)相同，即20，再排序，其結(jié)果如圖5所示，圓圈標(biāo)出了相同數(shù)據(jù)及相同數(shù)據(jù)的排序結(jié)果。

圖3 待排序數(shù)據(jù)流Fig.3 The data stream waiting for sorting

圖4 排序結(jié)果Fig.4 The result of sort

圖5 有相同數(shù)據(jù)的排序結(jié)果Fig.5 The result of sort with same data in data stream

4 算法在工程應(yīng)用中的性能分析

通過(guò)實(shí)際建立工程，綜合、仿真分析分別得出128點(diǎn)、256點(diǎn)以及512點(diǎn)排序，分別使用全并行算法、串行（冒泡）算法和本文串并結(jié)合的算法得到的邏輯資源使用情況以及運(yùn)算時(shí)鐘周期。從表中可以看出，全并行算法速度最快，但數(shù)據(jù)點(diǎn)數(shù)翻倍時(shí)消耗的資源消耗平方級(jí)翻倍，256點(diǎn)排序已經(jīng)超出了芯片的范圍；串行冒泡算法消耗的資源較少，但數(shù)據(jù)點(diǎn)數(shù)翻倍時(shí)消耗的時(shí)間卻是平方級(jí)翻倍；只有本文提出的算法消耗的資源和時(shí)鐘周期都能接收，具有可行性意義。

表2 不同算法消耗的資源和時(shí)間Tab.2 The resource and time of different algorithm

采用240 MHz時(shí)鐘，512點(diǎn)排序，只需要8μs。

5 結(jié)束語(yǔ)

排序在雷達(dá)信號(hào)處理過(guò)程中只是其中的一個(gè)功能，這要求我們邏輯資源不能消耗太多，而雷達(dá)的實(shí)時(shí)性要求又要求我們必須快速的完成排序。從上述論述可知，單純的串行和并行排序[6]都不能滿足要求，只有本文這種基于FPGA技術(shù)的串并行結(jié)合處理排序算法才能夠滿足實(shí)際工程要求，達(dá)到了實(shí)時(shí)排序的效果。該算法具有通用性，可以應(yīng)用到各種數(shù)據(jù)快速排序運(yùn)算領(lǐng)域。

[1]吳順君，梅曉春.雷達(dá)信號(hào)處理和數(shù)據(jù)處理計(jì)數(shù)[M].北京：電子工業(yè)出版社，2004.

[2]周建欽.超快速排序算法[J].計(jì)算機(jī)工程與應(yīng)用，2006，42(29)：41-42.

[3]王昌厚.無(wú)符號(hào)整數(shù)按位快速排序算法[J].計(jì)算機(jī)應(yīng)用與軟件，2006，23(8)：120-124.

[4]喝賓.Xinlinx FPGA設(shè)計(jì)權(quán)威指南[M].北京：清華大學(xué)出版社，2012.

[5]于斌，米秀杰.ModSim電子系統(tǒng)分析及仿真[M].北京：電子工業(yè)出版社，2011.

[6]師延偉，金長(zhǎng)江.基于FPGA并行全比較排序算法[J].數(shù)字技術(shù)與應(yīng)用，2013(10)：126-127.