摘要：基于FPGA硬件技術，以資源和時間相結合的思路，提出了一種串并結合的比較排序算法。該算法通過對數據的分時并行比較，計算出每個數據在排序中的位置實現數據排序。該算法可在較短的時間內實現數字序列的排序，通過實驗證明，資源消耗少，實時性號，通用性強。
關鍵詞：排序;FPGA;并行;串行
在雷達抗干擾處理以及空時二維處理過程中數據排序將必不可免，在傳統(tǒng)的DSP、CPU等常規(guī)軟件排序已經不能夠滿足雷達系統(tǒng)實時性要求，使用 FPGA排序的趨勢將勢不可當。FPGA由于具有較高的并行處理能力，目前已成為雷達陣列信號處理中的主流處理器件。計算耗費的時間和消耗的硬件資源成為 處理的主要矛盾，如何解決這個矛盾，本人將提出解決方案。
1 算法描述與分析
排序就是將數據元素的一個任意序列，重新排列成一個按關鍵字有序的序列。各種傳統(tǒng)串行排序算法如冒泡，大多都是以兩兩之間順序比較為基礎，不能滿足 實時性要求。如果將傳統(tǒng)的串行排序在FPGA中進行分段串行排序再排序，可以減少排序時間，但卻大大增加設計難度。本文提出基于并行比較思路，通過將邏輯 比較結果求和，用此和值確定排序結果的位置，從而達到實現排序結果的目的。
假設待排序數據元素個數為N，全并行比較就是在同一時刻將N個數兩兩比較，再在下一時刻進行累加求和以確定排序結果。這樣需要耗費N*N個比較器，如果元素個數較多，將耗費大量邏輯資源。本算法采用N個比較器，用N倍時間實現比較。算法如上圖所示。
不同的比較器將有不同的比較結果輸出，下表列出了4種比較器輸出結果形式。
2 工程實現
排序算法在FPGA內進行，整個實現過程如下圖。使用verilog語言設計，做到模塊化、參數化，以適應不同數量的排序以及各自邏輯資源的控制，主要有以下幾步：
1)將流水線上的待排序的Ⅳ個數據存儲到RAM中，同時對相等值數量的RAM寫零;
2)讀取N個賦給N個變量準備比較;
3)讀取數據和N個變量同時比較;
4)將比較結果累加求和;
5)將和值作為地址讀取此數據的個數，將此個數和累加和相加寫到排序結果RAM中，同時將個數加1寫入相等值數量的RAM中。
相等值數量RAM主要處理待排序數據流有過個相同數值大小的數據排序的情況。
讀取N個賦給N個變量準備比較需要N個時鐘周期，比較需要N個時鐘周期，多級累加需要3*N個時鐘周期(N≤512)，相同數值排序需要3*N個時鐘周期，合計需要8*N個時鐘周期。
3 仿真與驗證
本算法Verilog代碼以及IP核模塊的新建基于Xilinxvp690，功能級仿真在Modsim中完成。圖3是待排序數據流截圖，待排序數據 是從20到319的300個遞增數據，圖4是圖3輸入數據的從小到大的排序結果，其中m_data_h是是排序后原先數據的序號，m_data_l是排序 后從小到大的結果;為了驗證相同數值的排序情況，將上述待排序數據的第2、39個數改成和第1個數相同，即20，再排序，其結果如圖5所示，圓圈標出了相 同數據及相同數據的排序結果。
4 算法在工程應用中的性能分析
通過實際建立工程，綜合、仿真分析分別得出128點、256點以及512點排序，分別使用全并行算法、串行(冒泡)算法和本文串并結合的算法得到的 邏輯資源使用情況以及運算時鐘周期。從表中可以看出，全并行算法速度最快，但數據點數翻倍時消耗的資源消耗平方級翻倍，256點排序已經超出了芯片的范 圍;串行冒泡算法消耗的資源較少，但數據點數翻倍時消耗的時間卻是平方級翻倍;只有本文提出的算法消耗的資源和時鐘周期都能接收，具有可行性意義。
采用240 MHz時鐘，512點排序，只需要8μs。
5 結束語
排序在雷達信號處理過程中只是其中的一個功能，這要求我們邏輯資源不能消耗太多，而雷達的實時性要求又要求我們必須快速的完成排序。從上述論述可 知，單純的串行和并行排序都不能滿足要求，只有本文這種基于FPGA技術的串并行結合處理排序算法才能夠滿足實際工程要求，達到了實時排序的效果。該算法 具有通用性，可以應用到各種數據快速排序運算領域。
下載文檔
