沈鎮(zhèn)，柴志雷

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，無錫214122)

基于FPGA的低秩矩陣恢復(fù)算法研究與應(yīng)用

沈鎮(zhèn)，柴志雷

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，無錫214122)

低秩矩陣恢復(fù)算法主要包括魯棒主成分分析、矩陣補(bǔ)全、低秩表示，由于矩陣補(bǔ)全是一個(gè)NP難的問題，低秩表示涉及到字典矩陣，復(fù)雜度高，因此本文主要針對魯棒主成分分析在FPGA上的研究與應(yīng)用進(jìn)行了描述，并且在CPU以及FPGA上實(shí)現(xiàn)了圖像恢復(fù)。實(shí)驗(yàn)結(jié)果表明，基于FPGA的HLS設(shè)計(jì)相對于傳統(tǒng)CPU在速度上得到了數(shù)十倍的提高。

低秩矩陣恢復(fù)；魯棒主成分分析；FPGA；HLS

引 言

低秩矩陣恢復(fù)算法[1]在信號(hào)處理、圖像修復(fù)、計(jì)算機(jī)視覺、機(jī)器學(xué)習(xí)、人工智能等方面有著極其廣泛的應(yīng)用。通常把魯棒主成分分析[2]、低秩表示和矩陣補(bǔ)全統(tǒng)稱為低秩矩陣恢復(fù)算法，然而由于矩陣補(bǔ)全是一個(gè)NP難的問題以及低秩表示涉及到字典矩陣，其復(fù)雜度高，因此魯棒主成分分析得到廣泛使用。

FPGA(Field-Programmable Gate Array,現(xiàn)場可編程門陣列)是在PAL、GAL、CPLD等可編器件的基礎(chǔ)上進(jìn)一步發(fā)展的產(chǎn)物。由于支持細(xì)粒度并行及硬件重構(gòu)，是一種常用的硬件加速平臺(tái)，系統(tǒng)設(shè)計(jì)師可以根據(jù)需要,通過可編輯的連接把FPGA內(nèi)部的邏輯塊連接起來。

本文使用的是Xilinx開發(fā)的Vivado HLS[4]工具，Vivado HLS工具的出現(xiàn)和發(fā)展突破了以往在使用FPGA進(jìn)行設(shè)計(jì)時(shí)使用HDL語言進(jìn)行設(shè)計(jì)實(shí)現(xiàn)的瓶頸。在Xilinx FPGA[5]上構(gòu)建數(shù)字系統(tǒng)時(shí)，首先使用C/C++/System C語言進(jìn)行建模，然后通過Vivado HLS工具將C/C++/System C模型直接轉(zhuǎn)換為RTL級(jí)的HDL描述,因此，大大提高了FPGA設(shè)計(jì)的效率。

1 HLS介紹

1.1 Vivado HLS設(shè)計(jì)流程及其功能

高級(jí)綜合(High Level Synthesis，HLS)是Xilinx公司推出的新一代FPGA設(shè)計(jì)工具。利用System C語言進(jìn)行數(shù)字系統(tǒng)的描述，并可以將其自動(dòng)轉(zhuǎn)換成RTL級(jí)代碼，其處理流程如圖1所示。

圖1 HLS的處理流程圖

該綜合工具主要有以下4個(gè)功能：

① 從C語言描述級(jí)別的源代碼創(chuàng)建一個(gè)RTL級(jí)實(shí)現(xiàn)。

② 從C源代碼提取出控制和數(shù)據(jù)流。

③ 基于默認(rèn)和用戶定義的命令實(shí)現(xiàn)設(shè)計(jì)。

④ 從相同的源代碼描述中，可以實(shí)現(xiàn)很多的設(shè)計(jì)，即開發(fā)者使用C/C++高級(jí)語言在源文件以及測試文件中進(jìn)行編程。源文件用來實(shí)現(xiàn)IP核的功能，可以采用工具優(yōu)化或手動(dòng)優(yōu)化從而滿足性能指標(biāo),之后通過測試文件在源代碼級(jí)進(jìn)行仿真驗(yàn)證保證IP功能正確，功能仿真后再通過高層綜合工具綜合生成RTL級(jí)代碼同時(shí)運(yùn)行RTL級(jí)仿真，在滿足功能時(shí)序要求之后可以導(dǎo)出RTL級(jí)的IP核。

1.2 Vivado HLS優(yōu)點(diǎn)

HLS可以用于將C語言函數(shù)轉(zhuǎn)換成硬件模塊。它能夠基于現(xiàn)有的 C/C++的代碼編寫的算法，按照Vivado HLS編譯工具的規(guī)范進(jìn)行簡單修改后，就可以快速、直接地生成IP核或者綜合后的結(jié)果(.dcp文件)。對于嵌入式系統(tǒng)的開發(fā)者來說，這樣就可以快速地完成現(xiàn)有算法到 FPGA 中的移植，既能顯著縮短開發(fā)時(shí)間，又能利用FPGA的性能幾十倍上百倍地提高算法性能。

2 低秩矩陣恢復(fù)算法

2.1 算法流程

奇異值分解[3]步驟分為兩大步：首先利用Householder變換把矩陣A約化成雙對角線矩陣,即

每次迭代的時(shí)候，經(jīng)過初始變換V0,1，將在第0列的主對角線下方出現(xiàn)一個(gè)非零元素。在變換V0,1時(shí)，選擇位移值u的計(jì)算公式如下：

最后再對奇異值按非遞增次序排序。

2.2 算法并行性分析

首先，定義一個(gè)深度為256的雙口RAM來保存每個(gè)灰度值的像素點(diǎn)個(gè)數(shù)，具體操作是將每個(gè)像素點(diǎn)的灰度值作為其中一個(gè)端口的讀地址，讀取RAM單元中的計(jì)數(shù)，將其值增加1，接著將更新后的計(jì)數(shù)從另一個(gè)端口寫入同一單元。

其次，由于在統(tǒng)計(jì)處理每個(gè)像素點(diǎn)時(shí)，都要執(zhí)行3個(gè)步驟：讀取計(jì)數(shù)、更新計(jì)數(shù)、寫回計(jì)數(shù)。只有完成當(dāng)前像素點(diǎn)的3個(gè)步驟之后，才能進(jìn)行下一個(gè)像素點(diǎn)的處理。而FPGA的并行性能夠解決此類處理延時(shí)導(dǎo)致的低效率，即在模塊內(nèi)部構(gòu)建3個(gè)功能相同的統(tǒng)計(jì)模塊，每個(gè)模塊各自負(fù)責(zé)相鄰的3個(gè)像素點(diǎn)，從而構(gòu)成一條流水線，使得每個(gè)子模塊都有3個(gè)時(shí)鐘周期來統(tǒng)計(jì)1個(gè)像素點(diǎn)。讀取計(jì)數(shù)、更新計(jì)數(shù)、寫回計(jì)數(shù)3個(gè)步驟的邏輯被劃分到各自的時(shí)鐘周期來完成，從而提高了處理效率。

3 算法硬件加速單元的HLS設(shè)計(jì)與實(shí)現(xiàn)

3.1 硬件加速單元設(shè)計(jì)

考慮到算法使用流水結(jié)構(gòu)，用一個(gè)32位寬度的行緩沖來存儲(chǔ)前一行所產(chǎn)生的圖像灰度值，從而能夠在硬件當(dāng)中實(shí)現(xiàn)流水計(jì)算，硬件計(jì)算模塊如圖2所示。

圖2 硬件計(jì)算模塊圖

3.2 硬件加速單元的HLS實(shí)現(xiàn)

Vivado HLS中的基本系統(tǒng)構(gòu)建塊是C/C++函數(shù)，構(gòu)建一個(gè)由模塊和子模塊組成的系統(tǒng)，意味著需要用一個(gè)頂層函數(shù)來調(diào)用底層函數(shù)，因此要先準(zhǔn)備好用來生成硬件模塊的函數(shù)，它需要保存在一個(gè)單獨(dú)的文件里。在創(chuàng)建工程時(shí)，指定它為頂層函數(shù)，同時(shí)也要準(zhǔn)備一個(gè)實(shí)現(xiàn)相同功能的函數(shù)，它不會(huì)被生成硬件模塊，只用于驗(yàn)證硬件模塊的功能是否正確。最后還要準(zhǔn)備一個(gè)測試的main( )函數(shù)，它分別調(diào)用前面所述的兩個(gè)軟件函數(shù)，并比較它們輸出的結(jié)果是否一致。在C語言驗(yàn)證和RTL驗(yàn)證時(shí)，HLS工具都會(huì)調(diào)用它。

3.2.1 主函數(shù)定義

由于Vivado HLS中仿真與綜合的區(qū)別，仿真與綜合時(shí)輸入口數(shù)目不同，因此主函數(shù)定義略有不同。

#ifdefine DEBUG_MODE

voidsvd_filter(hls_int32 *in_pix, hls_int32 *out_pix, unsigned int byte_rdoffset, unsigned int byte_wroffset, int rows, int cols, int stride)

#elsevoidsvd_filter(volatile hls_int32 *inout_pix, unsigned int byte_rdoffset,unsigned int byte_wroffset,int rows,int cols,int stride)

#endif

上面定義函數(shù)中，hls_int32為輸入輸出像素值的數(shù)據(jù)類型，即32位整型輸入輸出，inout_pix用于存儲(chǔ)輸入/輸出數(shù)據(jù)。執(zhí)行這個(gè)函數(shù)時(shí)，CPU指令會(huì)讀寫其中的數(shù)據(jù)。

3.2.2 生成AXI4硬件接口

C語言函數(shù)轉(zhuǎn)換成硬件模塊，由于Vivado HLS工具支持3類通用類型的信號(hào)：流接口、BRAM接口、標(biāo)量I/O。在這三類中，只有標(biāo)量I/O 能夠被處理器通過AXI4-Lite接口進(jìn)行訪問，生成AXI4[7]接口，由硬件模塊自動(dòng)讀取數(shù)據(jù)，相當(dāng)于集成了一個(gè)DMA控制器；也可以生成AXI Stream接口，AXI Stream Slave接口接收其他數(shù)據(jù)源生成的數(shù)，AXI Stream Master 接口可以作為數(shù)據(jù)源。接下來主要介紹AXI4硬件接口。

① 為指針inout_pix生成AXI4接口的約束：

#pragma HLS INTERFACE m_axi depth=2048 port=inout_pix offset=off bundle=Data_Bus

byte_rdoffset是一個(gè)輸入?yún)?shù)，指定 buffer 的長度,轉(zhuǎn)換成硬件模塊后，會(huì)生成一個(gè)可寫的寄存器，可以由AXI Lite總線訪問，由CPU寫入長度。

② 為輸入、輸出參數(shù)byte_rdoffset、byte_wroffset、rows、cols創(chuàng)建AXI Lite寄存器約束：

#pragma HLS INTERFACE s_axilite register port=return offset=0x00 bundle=Ctrl_Bus

#pragma HLS INTERFACE s_axilite register port=byte_rdoffset offset=0x14 bundle=Ctrl_Bus

#pragma HLS INTERFACE s_axilite register port=byte_wroffset offset=0x1c bundle=Ctrl_Bus

#pragma HLS INTERFACE s_axilite register port=rows offset=0x24 bundle=Ctrl_Bus

#pragma HLS INTERFACE s_axilite register port=cols offset=0x2c bundle=Ctrl_Bus

#pragma HLS INTERFACE s_axilite register port=stride offset=0x34 bundle=Ctrl_Bus

如果是用戶自己的函數(shù)，雖然參數(shù)個(gè)數(shù)和類型可能都不一樣，都可以參照上述類型做約束。HLS生成的硬件模塊的寄存器都是無符號(hào)32位數(shù)據(jù)。必要的時(shí)候，可以使用C語言的 union來做類型轉(zhuǎn)換。

3.2.3 memory copy

memory copy創(chuàng)建一個(gè)突發(fā)訪問內(nèi)存，memory copy的多次調(diào)用不能流水線執(zhí)行，將順序執(zhí)行，memory copy需要一個(gè)本地緩存burst_buff_in來存儲(chǔ)輸入數(shù)據(jù)。

memcpy(burst_buff_in,(hls_uint32*)(inout_pix+byte_rdoffset/4+row*cols),BURST_NUM*sizeof(hls_uint32));

最后的輸出結(jié)果返回給輸出接口。

memcpy((hls_uint32 *)(inout_pix+byte_wroffset/4+(row-1)*cols), burst_buff_out,BURST_NUM*sizeof(hls_uint32));

3.2.4 性能優(yōu)化

約束好與CPU的接口后，需要考慮性能優(yōu)化，HLS有很多性能優(yōu)化的技巧。

① “#pragma HLS DATAFLOW”,數(shù)據(jù)流編譯指令指示Vivado HLS盡量以并行方式安排執(zhí)行該函數(shù)的所有子函數(shù)?！癷nternal”參數(shù)用于設(shè)置該模塊的初始化間隔(II),初始化間隔(II)告知 Vivado HLS該模塊必須具備的處理新輸入數(shù)據(jù)字的頻次，故決定了設(shè)計(jì)的吞吐量。

② “#pragma HLS PIPELINE”,流水線編譯指令指示Vivado HLS將該函數(shù)流水線化，讓初始化間隔為x(II=x)，即x個(gè)時(shí)鐘周期處理一個(gè)新的輸入數(shù)據(jù)字。

3.2.5 buffer的使用

模塊與模塊之間需要buffer進(jìn)行緩存，這樣有利于模塊之間的同步，提高計(jì)算效率。如輸入數(shù)據(jù)存儲(chǔ)在 buffer 中：

buff_A.insert_bottom(rgb2y(tempx),col);

最后再由 buffer 讀出:

buff_C.insert(buff_A.getval(2,col),0,2);

4 實(shí)驗(yàn)結(jié)果與分析

本文采用基于高級(jí)綜合工具HLS的C語言進(jìn)行編寫，采用的器件是Zynq7030系列芯片。以256×256大小圖像為例，SVD算法在CPU上的執(zhí)行結(jié)果如圖3所示；在FPGA上的執(zhí)行結(jié)果如圖4所示。

圖3 CPU實(shí)驗(yàn)結(jié)果圖

圖4 FPGA實(shí)驗(yàn)結(jié)果圖

由此可知，同一幅圖片在FPGA上執(zhí)行的效果與在傳統(tǒng)的CPU上基本一致，然而FPGA執(zhí)行時(shí)間比傳統(tǒng)CPU提高了數(shù)10倍，表1列出了不同大小圖片在CPU與在FPGA上執(zhí)行的時(shí)間對比。

表1 不同圖片在CPU和FPGA上的執(zhí)行時(shí)間(單位：s)

通過Vivado HLS綜合分析可知，SVD在FPGA上實(shí)現(xiàn)的部分邏輯資源所占比例分別是：DSP為4%，F(xiàn)IFO為3%，LUT為11%，這大大節(jié)約了芯片的硬件資源，節(jié)省了硬件成本，使得更多的資源可用于其他硬件算法。

結(jié) 語

[1] 史加榮,鄭秀云,魏宗田,等.低秩矩陣恢復(fù)算法綜述[J].計(jì)算機(jī)應(yīng)用研究,2013(6).

[2] JinXing Liu,Yong Xu,ChunHou Zheng,et al.RPCA-based tumor classification using gene expression data[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB),2015,12(4):964.

[3] Menghan Yan,Wenqian Shang,Zhenzhong Li.Application of SVD technology in video recommendation system[C]//2016 IEEE/ACIS 15th International Conference on Computer and Information Science (ICIS),2016.

[4] 何賓.Xilinx FPGA設(shè)計(jì)權(quán)威指南[M].北京:清華大學(xué)出版社,2014.

[5] Xilinx.Zynq-7000SoC[EB/OL].[2016-08].http://www.xilinx.com/products/silicondevices/soc/zynq-7000/index.htm.

[6] R Dorado,E Torres-Jiménez,C Rus-Casas,et al.Mobile learning:Using QR codes to develop teaching material[C]//2016 Technologies Applied to Electronics Teaching (TAEE),2016.

[7] Ckristian Duran,D Luis Rueda,Giovanny Castillo,et al.A 32-bit RISC-V AXI4-lite bus-based microcontroller with 10-bit SAR ADC[C]//2016 IEEE 7th Latin American Symposium on Circuits & Systems (LASCAS),2016.

沈鎮(zhèn)(碩士研究生)，主要研究方向?yàn)榍度胧较到y(tǒng)、圖像處理；柴志雷(副教授)，主要研究方向?yàn)榍度胧较到y(tǒng)設(shè)計(jì)技術(shù)、機(jī)器視覺、FPGA操作系統(tǒng)等。

Research and Application of Low Rank Matrix Recovery Algorithm Based on FPGA

Shen Zhen,Chai Zhilei

(School of Internet of Things,Jiangnan University,Wuxi 214122,China)

The low rank matrix recovery algorithm mainly includes the robust principal component analysis,the matrix completion,the low rank representation.Because the matrix completion is a NP hard problem,the low rank said relates to the dictionary matrix,high complexity.Therefore,this paper mainly described the research and application of the robust principal component analysis in FPGA,and the CPU and FPGA image restoration is realized.The experimental results show that the speed of the design based on the FPGA HLS has been increased by tens of times compared to the traditional CPU.

low-rank matrix recovery;robust principal component analysis;FPGA;HLS

TP368

A

?士然

2016-08-26)