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

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

在雷達(dá)抗干擾處理以及空時(shí)二維處理過程中數(shù)據(jù)排序?qū)⒈夭豢擅猓趥鹘y(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)鍵字有序的序列。各種傳統(tǒng)串行排序算法如冒泡，大多都是以兩兩之間順序比較為基礎(chǔ)，不能滿足 實(shí)時(shí)性要求。如果將傳統(tǒng)的串行排序在FPGA中進(jìn)行分段串行排序再排序，可以減少排序時(shí)間，但卻大大增加設(shè)計(jì)難度。本文提出基于并行比較思路，通過將邏輯 比較結(jié)果求和，用此和值確定排序結(jié)果的位置，從而達(dá)到實(shí)現(xiàn)排序結(jié)果的目的。

假設(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é)果形式。

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

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

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

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

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

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

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

相等值數(shù)量RAM主要處理待排序數(shù)據(jù)流有過個(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核模塊的新建基于Xilinxvp690，功能級(jí)仿真在Modsim中完成。圖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é)果。

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

通過實(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í)鐘周期都能接收，具有可行性意義。

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

5 結(jié)束語

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