張 鵬，龔曉峰

（四川大學(xué) 電氣信息學(xué)院，成都 610065）

0 引言

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

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

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

1 堆排序的原理

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

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

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

2 FPGA方案設(shè)計(jì)

2.1 FPGA與ARM方案對(duì)比

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

圖1 兩種方案的對(duì)比圖

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

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

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

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

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

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

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

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

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

圖3 建堆模塊信號(hào)流程圖

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

建堆模塊的實(shí)現(xiàn)是由一個(gè)狀態(tài)機(jī)來(lá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個(gè)周期。

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

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

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

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

FINISH：操作build_ready信號(hào)并清零寄存器。

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

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

堆排序模塊的實(shí)現(xiàn)同樣是由一個(gè)狀態(tài)機(jī)來(lá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：讀取記錄地址的兩個(gè)子根。

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

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

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

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

FINISH：操作heap_ready信號(hào)并清零寄存器。

3 仿真結(jié)果

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

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

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

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

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

4 驗(yàn)證平臺(tái)

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

5 驗(yàn)證結(jié)果與對(duì)比

5.1 FPGA堆排序

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

圖7 FPGA堆排序所需時(shí)間

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

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

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

表1 FPGA與ARM時(shí)間對(duì)比

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

6 結(jié)束語(yǔ)

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

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

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

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