一種Zynq SoC片內(nèi)硬件加速的二維傅里葉變換*

，

(南京航空航天大學 民航學院，南京 211106)

引 言

二維離散傅里葉變換作為頻域分析的重要工具之一，廣泛應(yīng)用于數(shù)字圖像處理的各個領(lǐng)域。隨著數(shù)字圖像數(shù)據(jù)量的增長，傳統(tǒng)基于處理器實現(xiàn)的軟件算法逐漸遇到實時性不足的問題，尤其是在一些對體積與功耗有嚴格限制的嵌入式應(yīng)用場合中，處理器的性能大幅受限。

近年來人們不斷嘗試使用新的硬件結(jié)構(gòu)來加速這一算法的實現(xiàn)過程。例如，參考文獻[2]針對GPU多核處理器架構(gòu)，分析合并內(nèi)存訪問事務(wù)大小與占用率之間的關(guān)系，優(yōu)化使用GPU存儲器資源，對小數(shù)據(jù)量2次冪二維復數(shù)FFT在GPU上的實現(xiàn)進行改進[2]。而相對于GPU的高功耗，低主頻低功耗的FPGA加速具有更大的實用價值，參考文獻[3-4]分別嘗試使用FPGA邏輯資源獨立完成二維FFT[3]與卷積神經(jīng)網(wǎng)絡(luò)算法的實現(xiàn)[4]，并將結(jié)果與GPU、DSP等方式進行了對比，驗證了顯著的加速效果。為了便于在利用邏輯資源加速后引入復雜算法，人們也逐漸嘗試在使用FPGA加速的同時結(jié)合CPU來進行任務(wù)調(diào)度，如在大鄰域圖像加速設(shè)計中使用NIOS II軟核處理器[5]，在結(jié)合片內(nèi)硬核ARM處理器與FPGA的SoC器件上分別嘗試對閾值分割[6]、LS-SVM[7]或車輛識別[8]等算法進行加速，均取得了一定成效。

綜上，純粹利用專用集成電路(ASIC)或可編程邏輯門陣列(FPGA)來實現(xiàn)算法的方式雖然能滿足速度需求，但也存在著開發(fā)周期長，且不利于后期動態(tài)調(diào)整的缺點。針對這一問題，本文基于近年來流行的集成高性能ARM與FPGA的片上系統(tǒng)(System on Chip, SoC)平臺，嘗試一種同時兼顧軟件開發(fā)靈活與硬件實現(xiàn)效率高的二維傅里葉變換新方法?？紤]到二維傅里葉變換的可拆分性質(zhì)，在FPGA側(cè)通過搭建多路流水線形式的一維快速傅里葉變換IP核來實現(xiàn)并行計算加速，在處理器系統(tǒng)一側(cè)通過搭載嵌入式Linux系統(tǒng)來快速實現(xiàn)GUI顯示等人機交互的接口，并借助于Linux系統(tǒng)豐富的軟件開發(fā)生態(tài)環(huán)境，后續(xù)更加復雜的圖像算法可以方便地借助于流行的(諸如OpenCV，OpenGL等)軟件庫加快開發(fā)周期。

1 二維傅里葉變換拆解

離散傅里葉變換(Discrete Fourier Transform, DFT)是將離散時域信號轉(zhuǎn)換為頻域信號的經(jīng)典工具，對于常見的一維信號，其計算公式如下：

(1)

其中，x(n)為信號的離散時域序列(n=0,1,2,…,N-1)，X[k]為其變換后的離散頻域序列(k=0,1,2,…,N-1)。

而對一幅N×N大小的數(shù)字圖像進行二維離散傅里葉變換為：

(2)

其中，g(u, v)為原圖像在第u行，第v列的像素灰度大小，G(m,n)為原圖像變換后在橫向和縱向兩個方向上對應(yīng)的頻域離散分布。

分解上式的指數(shù)項得到：

(3)

結(jié)合式(3)與式(1)可以將二維離散傅里葉變換分解為水平和垂直兩部分運算，上式中方括號內(nèi)的項表示在圖像的行上計算實數(shù)序列的DFT，方括號外的求和項則表示在計算完所有行DFT的基礎(chǔ)上，對所得結(jié)果進行列方向上的復數(shù)序列的DFT。這樣的分解也表明可以用一維的快速傅里葉變換(Fast Fourier Transform, FFT)來快速實現(xiàn)二維離散傅里葉變換。而且，由上式可以看出在行方向(或列方向)上對各行(或各列)進行的變換計算是獨立的，因此結(jié)合FPGA的特點，可以設(shè)置多個的一維快速傅里葉變換IP核來加速完成兩個方向上的計算過程。

2 系統(tǒng)設(shè)計介紹

2.1 總體設(shè)計及功能劃分

由于Zynq平臺內(nèi)的處理器系統(tǒng)包含浮點處理單元，又考慮到運算精度對后續(xù)算法擴展的影響，因此選用符合IEEE754標準的32位浮點數(shù)作為整個運算過程中的數(shù)據(jù)格式。由上文介紹可以得知，利用兩個方向上的一維傅里葉變換來完成二維傅里葉變換過程中需要對前一個方向的變換結(jié)果進行緩存，然后在此基礎(chǔ)上完成另一個方向上的計算。由于緩存的中間結(jié)果是一組雙通道(分為實、虛部)二維浮點數(shù)組，對于某些分辨率較高的圖像，其消耗的存儲空間是巨大的，例如對于一幅1024×1024大小的圖像，經(jīng)過一維傅里葉變換后得到一組大小為1024×1024×2×4=8 MB的二維數(shù)組，這對于XC7Z020可編程邏輯側(cè)有限的片內(nèi)存儲邏輯資源是一個巨大且不必要的消耗(注：XC7Z020的PL側(cè)存儲資源主要有140個大小為36 KB的Block RAM，合計總?cè)萘繛?.9 MB)。因此，結(jié)合Zynq的互聯(lián)結(jié)構(gòu)優(yōu)勢，可以利用直接存儲器訪問(Direct Memory Access, DMA)將中間結(jié)果存入PS側(cè)的大小為512 MB的DDR3外擴RAM，這樣既大量降低了片內(nèi)存儲資源的消耗，也便于PL側(cè)與PS側(cè)進行大規(guī)模的數(shù)據(jù)共享。

整個系統(tǒng)的結(jié)構(gòu)設(shè)計如圖1所示，主要工作流程如下：PS側(cè)的程序?qū)⒋幚淼膱D像數(shù)據(jù)與多路一維快速傅里葉變換模塊的配置信息寫入DDR3存儲器，然后利用PL側(cè)的Xillybus總線先后將配置信息與圖像數(shù)據(jù)分別傳入設(shè)計好的復位配置模塊與多路FFT計算模塊，完成配置與單方向上的一維傅里葉變換后，再由Xillybus總線將中間結(jié)果寫回到DDR3存儲器中，然后由PS側(cè)的程序?qū)χ虚g結(jié)果完成二維矩陣轉(zhuǎn)置后，再控制Xillybus將數(shù)據(jù)傳輸至多路FFT計算模塊完成另一方向上的一維傅里葉變換，并將最終結(jié)果寫回進DDR3存儲器供PS側(cè)的程序讀取。

圖1 系統(tǒng)總體結(jié)構(gòu)框圖

2.2 硬件計算模塊設(shè)計

由圖1可以看出，PL側(cè)的硬件系統(tǒng)主要由三部分組成：Xillybus、復位配置模塊、多路FFT計算模塊，接下來將分別對它們進行介紹。

Xillybus是一個基于DMA或者PCIe總線的IP核，主要用于完成FPGA與Linux或Windows系統(tǒng)之間的數(shù)據(jù)通信任務(wù)，由Xillybus公司開發(fā)并提供驅(qū)動。傳統(tǒng)的DMA在完成數(shù)據(jù)傳輸時要求內(nèi)存中待傳輸數(shù)據(jù)的物理地址連續(xù)，而常見操作系統(tǒng)(如Linux)則通過地址映射的方式為用戶空間的程序分配內(nèi)存空間(通常無法保證數(shù)據(jù)的物理地址連續(xù))，因此，需要在操作系統(tǒng)啟動時就預留固定大小的內(nèi)存空間用來進行DMA傳輸。這樣的方式在需要傳輸大量數(shù)據(jù)時會大幅縮減系統(tǒng)的可用內(nèi)存，而Xillybus驅(qū)動通過將待傳輸?shù)拇罅繑?shù)據(jù)分批次拷貝至特定的緩沖區(qū)完成后續(xù)的數(shù)據(jù)傳輸，在一定程度上提高了內(nèi)存的使用效率。

復位配置模塊的主要功能是：經(jīng)由Xillybus總線接收用戶程序的配置信息，并根據(jù)收到的信息對多路FFT計算模塊中的所有子模塊進行相應(yīng)的復位和配置(如傅里葉變換的長度與方向設(shè)置)，并在完成后向PS側(cè)返回應(yīng)答信號。

多路FFT計算模塊的主要功能是：將經(jīng)由Xillybus總線傳入的串行數(shù)據(jù)依次送入多個一維快速傅里葉變換的IP核(由Xilinx的開發(fā)套件提供)，分別獨立完成計算，再將計算結(jié)果按順序送回。其主要結(jié)構(gòu)如圖2所示，其中FIFO除了起到緩沖數(shù)據(jù)的作用，還負責將串行傳輸?shù)?2位寬的虛數(shù)與實數(shù)數(shù)據(jù)轉(zhuǎn)為并行64位寬的復數(shù)數(shù)據(jù)。圖中的4個FFT計算模塊是由Xilinx公司提供的IP核，可以在開發(fā)軟件Vivado附帶的文檔庫中獲取其相關(guān)參數(shù)。其中每個IP核計算序列點數(shù)與待處理圖像數(shù)據(jù)的每行(或每列)包含的像素數(shù)目相同。而IP核的數(shù)量，即FFT的通道數(shù)目可以根據(jù)實際需求結(jié)合資源使用狀況靈活選擇，圖中只畫出了4路通道的設(shè)計方案以便于展示工作流程。需要注意的是圖中虛線框內(nèi)的兩個狀態(tài)檢測及切換模塊，它們有著相似的功能：統(tǒng)計輸入或輸出數(shù)據(jù)的數(shù)目，并根據(jù)統(tǒng)計結(jié)果選擇合適的計算通道。但在具體實現(xiàn)時，輸入狀態(tài)檢測模塊被設(shè)計為時序邏輯電路，輸出狀態(tài)檢查模塊被設(shè)計為組合邏輯電路。這樣設(shè)計的主要原因是FFT模塊的輸入輸出數(shù)據(jù)所采用的AXI-Stream總線時序與FIFO的寫入讀出時序不一致。

圖2 多路FFT計算模塊結(jié)構(gòu)框圖

AXI-Stream總線的讀寫時序都是同步的，即如圖2中的FFT模塊端口所示，當Valid與Ready信號同時為高時，數(shù)據(jù)在每一次時鐘信號的上升沿被寫入或讀出。而FIFO的讀出數(shù)據(jù)時序是異步的，即當Empty信號為低且在第一個時鐘上升沿檢測到讀使能信號為高后，對應(yīng)的數(shù)據(jù)將在第二個時鐘上升沿被讀出。這一個時鐘周期的滯后正好符合常見的同步狀態(tài)機設(shè)計需求，因此輸入狀態(tài)檢測模塊采用時序邏輯電路設(shè)計。而FIFO的寫入時序是同步的，即當Full信號為低且在檢測到寫使能信號為高的同一個周期內(nèi)，數(shù)據(jù)將會被寫入FIFO。而按照時序邏輯電路的設(shè)計方式，狀態(tài)檢測與通道切換至少將消耗掉一個時鐘周期，這與同步讀寫的時序相沖突。為了避免數(shù)據(jù)丟失，在輸出狀態(tài)檢測模塊使用觸發(fā)式的組合邏輯設(shè)計來避免額外的時鐘消耗。

2.3 軟件調(diào)度功能

由于單個方向上的傅里葉變換計算由PL側(cè)的硬件完成，因此程序主要功能如圖3所示。首先讀取SD卡中的圖像信息，然后將圖像數(shù)據(jù)格式轉(zhuǎn)為灰度并用浮點數(shù)表示，創(chuàng)建同等大小的全為零的圖像數(shù)據(jù)作為虛數(shù)圖像，并與之前的轉(zhuǎn)換結(jié)果進行復數(shù)圖像數(shù)據(jù)的拼接。然后通過Xillybus總線配置PL側(cè)的多路FFT計算模塊，并隨后將復數(shù)圖像數(shù)據(jù)按一次多行的形式依次傳入多路FFT計算模塊，并按順序接收變換結(jié)果。對得到的復數(shù)形式的中間圖像數(shù)據(jù)進行矩陣轉(zhuǎn)置排序，完成后再按順序?qū)⑥D(zhuǎn)置后的數(shù)據(jù)傳入多路FFT計算模塊完成另一個方向的傅里葉變換，并得到最終的結(jié)果。

圖3 軟件功能圖

3 實驗測試與結(jié)果分析

本文采用Xilinx公司推出的Zynq-7000全可編程SoC系列器件中的XC7Z020芯片提供的異構(gòu)平臺完成整個方案的設(shè)計。其主要特點是在芯片內(nèi)集成了一顆雙核ARM Cortex-A9嵌入式處理器與一塊性能等同于Xilinx Artix-7系列的FPGA，且兩者經(jīng)由片內(nèi)AXI高速總線緊密互聯(lián)[9]。其中處理器系統(tǒng)部分的CPU主頻為667 MHz，基于ARMv7架構(gòu)。每個CPU都分別帶有支持單指令多數(shù)據(jù)功能的多媒體協(xié)處理器，獨立的存儲管理單元，32 KB的一級指令緩存與數(shù)據(jù)緩存，獨立計時器與看門狗定時器。兩個CPU共享有512 KB大小的二級緩存?？删幊踢壿嫴糠值馁Y源主要由85k個邏輯單元，220個DSP48E1 Slice，140個大小為36 KB的雙端口BRAM，53 200個查找表(LUT)構(gòu)成。

實驗測試平臺采用了Digilent公司推出的ZedBoard。ZedBoard是基于Xilinx Zynq-7000的低成本開發(fā)板設(shè)計，同時也是一個開源硬件平臺，所有設(shè)計資料完全公開，可以在ZedBoard社區(qū)獲取。該平臺主要由型號為XC7Z020CLG484的SoC器件為核心，外擴容量為512 MB的DDR3內(nèi)存，以及JTAG、VGA、USB-OTG、串口及SD卡等常用外設(shè)構(gòu)成。

實驗測試的主要目的是獲取完成計算所需要的時間。因此，在軟件設(shè)計部分利用Linux系統(tǒng)提供的函數(shù)gettimeofday()來獲取計算所消耗的實際時間，其精度為1 μs。實驗具體過程是：利用串口終端軟件Putty訪問ZedBoard上電啟動后的Linux系統(tǒng)并運行程序,得到輸出結(jié)果并進行統(tǒng)計。部分測試結(jié)果如圖4所示，圖中運行的程序功能是：對一幅分辨率為1024×1024的圖像利用雙通道FFT計算模塊進行二維快速傅里葉變換并輸出計算時間與部分計算結(jié)果。由圖可知，兩次消耗時間分別為497 927 μs與504 322 μs。同時將上述計算結(jié)果分別與使用雙精度浮點數(shù)作為數(shù)據(jù)類型的MATLAB二維傅里葉變換程序運行結(jié)果、使用單精度浮點數(shù)作為數(shù)據(jù)類型的基于OpenCV庫的C++程序運行結(jié)果進行對比，得出結(jié)果基本一致，誤差在可接受范圍內(nèi)的結(jié)論。

圖4 實驗測試部分結(jié)果截圖

分別對不同分辨率的圖像以及不同通道數(shù)目的硬件系統(tǒng)進行實驗測試，并將其結(jié)果與OpenCV提供的二維傅里葉變換的軟件實現(xiàn)在ZedBoard上的測試結(jié)果進行對比，得到表1的數(shù)據(jù)。

表1 不同分辨率下多種計算方式消耗時間統(tǒng)計(單位：μs)

由表1中的數(shù)據(jù)可以看出，通道數(shù)的增加提高了使用FPGA完成計算的速度。隨著圖像分辨率的增大，利用FPGA完成計算所消耗的時間接近線性增長，顯著低于軟件計算所消耗時間的增長率。

因此，對高分辨率圖像的處理過程中增加硬件計算部分的并行通道數(shù)，可以顯著提升計算速度。而對于低分辨率圖像，由于數(shù)據(jù)量小，變換所需的計算時間遠小于數(shù)據(jù)傳輸?shù)臅r間，在這種情況下利用多通道硬件加速的效果不明顯。所以對于低分辨率的圖像，可以通過增大緩存容量來減少傳輸次數(shù)，進而減少不必要的傳輸時間損耗。例如，對于一幅分辨率為256×256的圖像，使用單通道FFT硬件計算模塊進行變換時，通過增大PL側(cè)數(shù)據(jù)輸入輸出的FIFO深度至8 192或者更大，并提高每次傳輸數(shù)據(jù)數(shù)量至16行，可以將整個計算所需的數(shù)據(jù)傳輸次數(shù)從512次降低至8次，改進后實驗結(jié)果如圖5所示，消耗時間約為13 566 μs，由表1中的數(shù)據(jù)對比可知，這不僅遠低于4通道FFT硬件模塊計算的時間花費，也低于流行的開源視覺庫OpenCV提供的軟件計算消耗時間，起到了明顯的硬件加速效果。值得一提的是：對于高分辨率圖像，由于計算時間遠高于數(shù)據(jù)傳輸時間，因此增大緩存并不能有效地提升整個系統(tǒng)的處理速度，而且由于其數(shù)據(jù)量過大，減少同樣的傳輸次數(shù)將帶來更大的資源消耗。

圖5 提高緩存后的實驗測試結(jié)果

結(jié) 語

[1] Russell M,Fischaber S.OpenCV based road sign recognition on Zynq[C]//IEEE International Conference on Industrial Informatics.IEEE,2013:596-601.

[2] 張全,鮑華,饒長輝,等.GPU平臺二維快速傅里葉變換算法實現(xiàn)及應(yīng)用[J].光電工程,2016(2):69-75.

[3] 李碩,王茜蒨.基于FPGA的二維FFT實現(xiàn)[C]//中國電子學會青年學術(shù)年會, 2012.

[4] 方睿,劉加賀,薛志輝,等.卷積神經(jīng)網(wǎng)絡(luò)的FPGA并行加速方案設(shè)計[J].計算機工程與應(yīng)用,2015,51(8):32-36.

[5] 陳實.大鄰域圖像處理硬件加速的研究[D].北京:清華大學,2009.

[6] 吳良晶,曹云峰,丁萌,等.SoC FPGA的視覺算法加速系統(tǒng)設(shè)計[J].單片機與嵌入式系統(tǒng)應(yīng)用,2016,16(11):58-62.

[7] 王曉璐.基于Zynq的LS-SVM算法加速器設(shè)計[D].哈爾濱:哈爾濱工業(yè)大學,2015.

[8] Kryjak T,Komorkiewicz M,Gorgon M.Real-time hardware-software embedded vision system for ITS smart camera implemented in Zynq SoC[J].Journal of Real-Time Image Processing,2016:1-37.

[9] Crockett L H,Elliot R A,Enderwitz M A,et al.The Zynq Book:Embedded Processing with the Arm Cortex-A9 on the Xilinx Zynq-7000 All Programmable Soc[M].Strathclyde Academic Media,2014.

[10] Hunter T M,Denisenko D,Kannan S,et al.FPGA Acceleration of Multifunction Printer Image Processing using OpenCL,2014.

陳龍(碩士研究生)，主要研究方向為嵌入式應(yīng)用開發(fā)；曹力(教授)，主要研究方向為導航與控制、計算機視覺。