基于FPGA的堆排序算法實現(xiàn)與改進

張 鵬，龔曉峰

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

0 引言

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

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

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

1 堆排序的原理

堆排序是利用堆積樹這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計出的一種排序算法，可以利用數(shù)組的特點快速定位指定索引的元素。

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

排序部分是將堆頂?shù)臄?shù)與堆尾的數(shù)互換位置，然后將堆頂?shù)臄?shù)排除，將原來n個數(shù)的堆變?yōu)閚-1個數(shù)的新堆，再將新的堆重復(fù)建堆與排序的過程直至完成排序[2]。

2 FPGA方案設(shè)計

2.1 FPGA與ARM方案對比

原始調(diào)制參數(shù)設(shè)計方案與改進后設(shè)計方案的對比圖如圖1所示。

圖1 兩種方案的對比圖

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

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

2.2 FPGA總體結(jié)構(gòu)的設(shè)計

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

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

圖2 FPGA總體結(jié)構(gòu)設(shè)計

如圖2所示，總體結(jié)構(gòu)包含了DATA_INPUT數(shù)據(jù)輸入模塊，BUILD_HEAP建堆模塊，HEAP_SORT堆排序模塊，DATA_OUTPUT數(shù)據(jù)輸出模塊以及一個RAM使用權(quán)控制模塊RAM_CONTROL。

2.3 建堆模塊的設(shè)計

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

圖3 建堆模塊信號流程圖

圖4 建堆模塊狀態(tài)轉(zhuǎn)移圖

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

各狀態(tài)完成的功能：

IDLE：等待狀態(tài)。

PRE：預(yù)處理狀態(tài)，設(shè)置RAM的讀取地址。

WAIT：等待數(shù)據(jù)從RAM中讀出，需要4個周期。

COMPARE：依次讀出該數(shù)據(jù)的父根，比較該數(shù)與父根的大小關(guān)系，直到找到比該數(shù)大的父根或讀取到最頂層父根。

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

WRITE：將建堆好的數(shù)重新寫入RAM中。

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

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

2.4 堆排序模塊的設(shè)計

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

堆排序模塊的實現(xiàn)同樣是由一個狀態(tài)機來完成，其包括IDLE等待狀態(tài)；PRE預(yù)處理狀態(tài)；WAIT等待數(shù)據(jù)狀態(tài)；HANDLE處理狀態(tài)；JUDGE跳轉(zhuǎn)狀態(tài)；OVER結(jié)束狀態(tài)以及FINISH完成狀態(tài)。該模塊的狀態(tài)轉(zhuǎn)移圖以及各狀態(tài)完成的功能如下：

各狀態(tài)完成的功能：

IDLE：等待狀態(tài)。

PRE：預(yù)處理狀態(tài)，設(shè)置RAM的讀取地址，并將最高地址值與記錄地址值交換。

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

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

圖5 堆排序模塊狀態(tài)轉(zhuǎn)移圖

JUDGE：比較大根值與待建堆數(shù)的大小，根據(jù)結(jié)果跳轉(zhuǎn)狀態(tài)。

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

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

3 仿真結(jié)果

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

圖6 兩核心模塊的仿真結(jié)果

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

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

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

4 驗證平臺

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

5 驗證結(jié)果與對比

5.1 FPGA堆排序

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

圖7 FPGA堆排序所需時間

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

5.2 FPGA與ARM堆排序時間結(jié)果對比

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

表1 FPGA與ARM時間對比

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

6 結(jié)束語

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

[1] 吳彥宏,陳相寧.QoS保障機制中的FPGA堆排序?qū)崿F(xiàn)[J].計算機工程, 2009,35(12):223-225

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

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