摘要：基于FPGA硬件技術(shù)，以資源和時間相結(jié)合的思路，提出了一種串并結(jié)合的比較排序算法。該算法通過對數(shù)據(jù)的分時并行比較，計算出每個數(shù)據(jù)在排序中的位置實(shí)現(xiàn)數(shù)據(jù)排序。該算法可在較短的時間內(nèi)實(shí)現(xiàn)數(shù)字序列的排序，通過實(shí)驗(yàn)證明，資源消耗少，實(shí)時性號，通用性強(qiáng)。

關(guān)鍵詞：排序;FPGA;并行;串行

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

1 算法描述與分析

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

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

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

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

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

1)將流水線上的待排序的Ⅳ個數(shù)據(jù)存儲到RAM中，同時對相等值數(shù)量的RAM寫零;

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

3)讀取數(shù)據(jù)和N個變量同時比較;

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

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

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

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

3 仿真與驗(yàn)證

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

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

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

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

5 結(jié)束語

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