基于FPGA的堆排序算法實現與改進

張 鵬，龔曉峰

（四川大學 電氣信息學院，成都 610065）

0 引言

在實際應用中，為了計算數字信號的調制參數，通常需要將ADC采樣后的數據通過FPGA處理后上傳給上位機進行調制參數的計算。但是由于受到FPGA與上位機接口傳輸速率的制約，要將大量IQ數據上傳至上位機將消耗大量的時間；同時，IQ數據上傳至上位機后要經過大量的計算處理后才能得到調制參數的結果。這大大降低了使用效率，同時給上位機添加了大量的計算負擔。為此，將調制參數的計算下放至FPGA，僅僅將調制參數的計算結果上傳至上位機，如此便可克服上述的兩個難題。

在FPGA上實現調制參數的計算中，對解調后數據的排序是其中的一個難點。目前在FPGA上實現排序的算法較少，且大多排序的點數較少，無法評估大量樣本排序時FPGA所占用的資源與排序的時間[1]。

本文針對FPGA設計出一種流水線式的堆排序方法，通過時序優化與modelsim仿真驗證，最終實現將2048點排序的時間控制在2ms以內。這一結果與原ARM上位機處理速度相當，從而達到了預期設計目的。

1 堆排序的原理

堆排序是利用堆積樹這種數據結構所設計出的一種排序算法，可以利用數組的特點快速定位指定索引的元素。

堆排序包括建堆和排序兩部分。堆可以定義為一棵二叉樹，包括大根堆（父節點大于等于其左右子節點）與小根堆（父節點小于等于其左右子節點）兩種，可以用于從小到大排序與從大到小排序兩種方式。

排序部分是將堆頂的數與堆尾的數互換位置，然后將堆頂的數排除，將原來n個數的堆變為n-1個數的新堆，再將新的堆重復建堆與排序的過程直至完成排序[2]。

2 FPGA方案設計

2.1 FPGA與ARM方案對比

原始調制參數設計方案與改進后設計方案的對比圖如圖1所示。

圖1 兩種方案的對比圖

如圖1所示，如果采用原始的設計方案，當FPGA完成數字下變頻處理后，需要上傳2048組IQ數據，即4096個16位數據至上位機。由于接口速率限制，傳輸效率較低，占用了大量時間。原始IQ數據上傳至上位機后仍需在上位機上進行調制參數的計算，這將占用大量的上位機CPU資源。

而改進后的方案，由于調制參數在FPGA內計算完成，因此只需上傳調制參數的結果，即3個16位數據（調制參數，正向調制參數以及負向調制參數）至上位機，這大大節省了數據上傳的時間。同時，由于在FPGA內已經完成參數調制計算，節約了上位機的CPU資源，讓上位機只做控制與顯示功能。

2.2 FPGA總體結構的設計

當使用2048組IQ數據進行調制參數計算時，先需要對信號進行解調，得到2048個16位有符號的解調數據后進行排序。

進入排序模塊后，首先要對2048個數據進行緩存；其次從RAM中讀出數據進行建堆處理后重新存入RAM中；再次對已建好的大根堆進行排序后重新存入RAM中；最后將排好序的數依次讀出。FPGA總體結構圖如圖2所示。

圖2 FPGA總體結構設計

如圖2所示，總體結構包含了DATA_INPUT數據輸入模塊，BUILD_HEAP建堆模塊，HEAP_SORT堆排序模塊，DATA_OUTPUT數據輸出模塊以及一個RAM使用權控制模塊RAM_CONTROL。

2.3 建堆模塊的設計

建堆模塊是堆排序的核心模塊，該模塊將緩存在RAM中的2048個數據建立為一個大根堆。其處理的思路如圖3所示。

圖3 建堆模塊信號流程圖

圖4 建堆模塊狀態轉移圖

建堆模塊的實現是由一個狀態機來完成，其包括IDLE等待狀態；PRE預處理狀態；WAIT等待數據狀態；COMPARE比較狀態；LYC緩存狀態；WRITE寫入狀態；HANDLE處理狀態以及FINISH完成狀態。該模塊的狀態轉移圖以及各狀態完成的功能如下：

各狀態完成的功能：

IDLE：等待狀態。

PRE：預處理狀態，設置RAM的讀取地址。

WAIT：等待數據從RAM中讀出，需要4個周期。

COMPARE：依次讀出該數據的父根，比較該數與父根的大小關系，直到找到比該數大的父根或讀取到最頂層父根。

LYC：緩存比較結果，為后續分類處理寫入RAM模塊做好準備。

WRITE：將建堆好的數重新寫入RAM中。

HANDLE：修改記錄地址，記錄已有多少個數完成了建堆。

FINISH：操作build_ready信號并清零寄存器。

2.4 堆排序模塊的設計

堆排序模塊是建立在建堆模塊基礎之上的。根據堆排序的原理，將堆頂與堆尾數據交換；將該數兩子節點取較大的數與該數比較，如果大于子節點中較大的數則表示重新建堆完成，否則繼續向下查找直至大于其子節點或沒有子節點為止[3]。

堆排序模塊的實現同樣是由一個狀態機來完成，其包括IDLE等待狀態；PRE預處理狀態；WAIT等待數據狀態；HANDLE處理狀態；JUDGE跳轉狀態；OVER結束狀態以及FINISH完成狀態。該模塊的狀態轉移圖以及各狀態完成的功能如下：

各狀態完成的功能：

IDLE：等待狀態。

PRE：預處理狀態，設置RAM的讀取地址，并將最高地址值與記錄地址值交換。

WAIT：讀取記錄地址的兩個子根。

HANDLE：比較兩個子根的大小，并記錄大根的值與地址值。

圖5 堆排序模塊狀態轉移圖

JUDGE：比較大根值與待建堆數的大小，根據結果跳轉狀態。

OVER：將排好序的數依次重新寫入RAM中。

FINISH：操作heap_ready信號并清零寄存器。

3 仿真結果

根據上文所述，在modelsim中仿真建堆過程與排序過程如圖6所示。

圖6 兩核心模塊的仿真結果

如圖6(a)所示，BUILD_HEAP模塊取其中一個點進行建堆驗證，如第87個點的建堆，依次查找其父節點43，21，10，4，1，0；發現地址為10的父節點已經大于地址為87的點，將新的順序重新寫入RAM中。

如圖6(b)所示，HEAP_SORT模塊中首先交換堆頂與堆尾的數據（如交換0地址與1481地址的數據），然后依次找出較大子節點先緩存在寄存器中，當找到一個小于堆頂的數則重新將建堆的數據寫入RAM中。

通過圖6可以看出，建堆與排序兩個模塊運行情況與預期完全相同，完成了堆排序。

4 驗證平臺

Altera公司的Cyclone III系列芯片為主流低成本FPGA，因此我們選取EP3C40F484C8作為測試芯片[3]。而ARM處理器模塊選用Cortex-A8處理器，與FPGA進行堆排序比較，以驗證方案的可行性。

5 驗證結果與對比

5.1 FPGA堆排序

首先在MATLAB中產生一組隨機數，通過modelsim將數據讀入，驗證FPGA排序，在100MHz晶振頻率下所需時間如圖7所示。

圖7 FPGA堆排序所需時間

如圖7所示，當完成數據緩存DATA_INPUT模塊后開始計時，開始進入建堆模塊與堆排序模塊，當數據輸出模塊DATA_OUTPUT開始讀出數據停止計時；這段時間即為堆排序所需時間。從圖中可以看出，對于一組2048點的隨機數堆排序時間控制在2ms以內。

5.2 FPGA與ARM堆排序時間結果對比

堆排序為一種不定時排序，排序時間與輸入數據原始的順序有關。對此，驗證3種不同輸入數據順序，分別為2048點隨機數組，由大到小的2048點數組以及由小到大的2048點數組，測試結果如表1所示。

表1 FPGA與ARM時間對比

從表1可以看出，FPGA堆排序與ARM堆排序時間相當，這是由于為了節約FPGA邏輯資源而采用流水線的工作模式；但如前文所述，此方案大大降低了數據上傳所需時間以及ARM上位機的計算負擔，達到了預期結果。

6 結束語

本文針對FPGA與上位機接口傳輸速率受限問題以及上位機沉重的計算負擔，將調制參數的計算下放至FPGA中進行處理，極大的解決了上述問題。而針對FPGA調制參數計算中的排序處理，采用了2048點的流水線式堆排序，排序時間與主流ARM處理器相當，排序結果正常；證明了該方案的可行性，達到了克服FPGA與上位機接口傳輸速率受限問題，以及減小上位機計算負擔的目的。

[1] 吳彥宏,陳相寧.QoS保障機制中的FPGA堆排序實現[J].計算機工程, 2009,35(12):223-225

[2] 黎佩南.一種快速排序算法的實現及其應用[J].電訊技術,2012,52(2):225-229.

[3] 吳彥宏,陳相寧.QoS中堆排序的脈動陣列結構在FPGA上的實現[J].科學技術與工程, 2008,8(19):5435-5438.