一種Zynq SoC片內硬件加速的二維傅里葉變換*

，

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

引 言

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

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

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

1 二維傅里葉變換拆解

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

(1)

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

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

(2)

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

分解上式的指數項得到：

(3)

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

2 系統設計介紹

2.1 總體設計及功能劃分

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

整個系統的結構設計如圖1所示，主要工作流程如下：PS側的程序將待處理的圖像數據與多路一維快速傅里葉變換模塊的配置信息寫入DDR3存儲器，然后利用PL側的Xillybus總線先后將配置信息與圖像數據分別傳入設計好的復位配置模塊與多路FFT計算模塊，完成配置與單方向上的一維傅里葉變換后，再由Xillybus總線將中間結果寫回到DDR3存儲器中，然后由PS側的程序對中間結果完成二維矩陣轉置后，再控制Xillybus將數據傳輸至多路FFT計算模塊完成另一方向上的一維傅里葉變換，并將最終結果寫回進DDR3存儲器供PS側的程序讀取。

圖1 系統總體結構框圖

2.2 硬件計算模塊設計

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

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

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

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

圖2 多路FFT計算模塊結構框圖

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

2.3 軟件調度功能

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

圖3 軟件功能圖

3 實驗測試與結果分析

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

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

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

圖4 實驗測試部分結果截圖

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

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

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

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

圖5 提高緩存后的實驗測試結果

結 語

[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平臺二維快速傅里葉變換算法實現及應用[J].光電工程,2016(2):69-75.

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

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

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

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

[7] 王曉璐.基于Zynq的LS-SVM算法加速器設計[D].哈爾濱:哈爾濱工業大學,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.

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