伍衛(wèi)國(guó) 王超輝 王今雨 聶世強(qiáng) 胡 壯

1(西安交通大學(xué)電子與信息工程學(xué)院 西安 710049) 2 (國(guó)家數(shù)據(jù)廣播工程技術(shù)研究中心(西安交通大學(xué)) 西安 710049) (wgwu@mail.xjtu.edu.cn)

近10年來(lái)，普適計(jì)算和物聯(lián)網(wǎng)的興起促進(jìn)了嵌入式系統(tǒng)的發(fā)展，基于嵌入式系統(tǒng)的應(yīng)用正在迅速占據(jù)著傳統(tǒng)IT行業(yè)的市場(chǎng)份額.可重構(gòu)計(jì)算(reconfigurable computing, RC)是繼通用計(jì)算和專用集成電路(application specific integrated circuit, ASIC)之后的第3種計(jì)算模式，其綜合了通用計(jì)算與ASIC的優(yōu)點(diǎn)，一定程度上實(shí)現(xiàn)了計(jì)算速度與靈活性的并存.使用可重構(gòu)計(jì)算技術(shù)的系統(tǒng)被稱為可重構(gòu)系統(tǒng)，主流的可重構(gòu)系統(tǒng)依托于現(xiàn)場(chǎng)可編程門陣列(field programmable gate array, FPGA)，實(shí)現(xiàn)了硬件資源的重復(fù)使用.在嵌入式應(yīng)用中，可重構(gòu)系統(tǒng)已經(jīng)應(yīng)用到汽車、醫(yī)療、廣播、航空航天、高性能計(jì)算、數(shù)據(jù)存儲(chǔ)、無(wú)線通信以及家庭網(wǎng)絡(luò)等領(lǐng)域中，其應(yīng)用價(jià)值的重要性不言而喻.

經(jīng)典動(dòng)態(tài)可重構(gòu)系統(tǒng)模型如圖1所示，其中包括應(yīng)用任務(wù)的軟硬件劃分、調(diào)度與布局、布線、加載以及運(yùn)行五大部分(如圖1中虛線框1～5).應(yīng)用程序中的任務(wù)按照自身屬性，由任務(wù)劃分器劃分為軟件任務(wù)或者硬件任務(wù)，軟件任務(wù)添加到軟件任務(wù)隊(duì)列中，然后在軟件運(yùn)行環(huán)境中(一般為CPU)運(yùn)行；硬件任務(wù)的執(zhí)行需要經(jīng)過5個(gè)階段：1)硬件任務(wù)的調(diào)度.虛線框1為任務(wù)的調(diào)度過程.2)調(diào)度后的任務(wù)根據(jù)硬件資源需求，由布局器布局在FPGA的某塊空閑資源區(qū)中，虛線框2中即為任務(wù)的調(diào)度與布局部分.3)布局后的任務(wù)需要與I/O資源或者內(nèi)部其他硬件資源通信，這就涉及到重新布線的問題，虛線框3中為任務(wù)的布線部分.4)當(dāng)布線完成后，需要將新生成的二進(jìn)制配置文件配置到FPGA可重構(gòu)資源的存儲(chǔ)區(qū)中，確定各個(gè)可重構(gòu)資源的邏輯功能，虛線框4為二進(jìn)制配置文件的加載過程.5)當(dāng)任務(wù)被配置到FPGA上，按照預(yù)先定義的邏輯功能運(yùn)行，直到任務(wù)計(jì)算完成，虛線框5為任務(wù)在FPGA上運(yùn)行過程.

Fig. 1 Flow chart of classical dynamic reconfigurable system圖1 經(jīng)典動(dòng)態(tài)可重構(gòu)系統(tǒng)流程圖

Fig. 2 Reconfigurable file configuration process (no compression)圖2 可重構(gòu)文件配置過程(不含壓縮)

隨著大規(guī)模集成電路技術(shù)的迅猛發(fā)展，F(xiàn)PGA工藝也在不斷提高.Xilinx公司于2003年推出的Spartan3系列處理器采用90 nm工藝，到最新的VIRTEX系列可編程FPGA系列采用16～28 nm工藝.工藝上的提升不僅降低了能耗，最主要是增加了集成度，Spartan3系列處理器中的邏輯單元(logic cells, LC)個(gè)數(shù)最多為53 712個(gè)，而Virtex UltraScale處理器中LC數(shù)量為4 432 680個(gè)，與之對(duì)應(yīng)的配置文件大小相當(dāng)Spartan3系列處理器配置文件大小的82倍.考慮到其他硬件資源(I/O資源、布線資源、DSP資源、存儲(chǔ)器資源和硬核微處理器資源等)的增加，近10年配置文件大小已經(jīng)增加了百倍以上[1].圖2為不含壓縮過程的配置文件配置過程,在該過程中，主要有2個(gè)階段耗時(shí)：1)配置文件從片外存儲(chǔ)器或PC機(jī)傳送到片內(nèi)配置控制器(配置存儲(chǔ)器)；2)配置過程，即在配置控制器作用下將配置信息寫入可編程邏輯塊中并進(jìn)行初始化操作(可編程邏輯塊、寄存器、I/O緩存).JTAG(joint test action group)為FPGA常見配置文件下載方式之一.JTAG下載方式為串行傳輸模式，在測(cè)試時(shí)鐘一定的情況下，配置文件傳輸時(shí)間完全由配置文件大小決定.這樣，為了減少第1階段耗費(fèi)的時(shí)間，目前的解決方案為壓縮配置文件.各大可編程邏輯設(shè)備(programmable logic device, PLD)制造商(Xilinx，Intel等)也意識(shí)到了壓縮配置文件的重要性，在配置文件生成階段都可以設(shè)置配置文件壓縮方案.圖3為含壓縮過程的配置文件配置過程：

現(xiàn)在主流的FPGA處理器考慮到設(shè)計(jì)的安全性，對(duì)配置文件也進(jìn)行了加密處理，這樣可以防止設(shè)計(jì)拷貝以及逆向工程等非法操作.Xilinx公司和Intel公司FPGA處理器均采用了256b AES對(duì)稱加密算法[2-3].加密解密消耗的時(shí)間不僅與算法本身相關(guān)，而且與加密文件大小相關(guān).在加密前對(duì)配置文件進(jìn)行壓縮處理，可以大幅度減少加密和解密過程的時(shí)間代價(jià).Xilinx公司和Intel公司最新FPGA處理器同時(shí)支持配置文件壓縮與加密.由此可見，采用壓縮方法對(duì)于解決第1階段的耗時(shí)性還是很有幫助的.

1 國(guó)內(nèi)外現(xiàn)狀研究

可重構(gòu)系統(tǒng)配置文件壓縮技術(shù)的使用不僅在一定程度上減少系統(tǒng)配置時(shí)間，提高系統(tǒng)運(yùn)行速率，滿足實(shí)時(shí)性應(yīng)用需求，而且降低了配置控制器內(nèi)部存儲(chǔ)代價(jià)，節(jié)約存儲(chǔ)資源.對(duì)于配置文件壓縮必須滿足2個(gè)條件：1)無(wú)損壓縮；2)解壓算法實(shí)現(xiàn)代價(jià)低.在FPGA二進(jìn)制配置文件配置過程中，最小的配置單位為幀.配置幀中的每1b二進(jìn)制數(shù)據(jù)都代表著芯片中某個(gè)可配置資源中寄存器的高低位，即配置幀信息的改變就有可能改變可配置資源的功能.為了保證可重構(gòu)系統(tǒng)正常運(yùn)行和可重構(gòu)模塊功能不受改變，壓縮算法必須采用無(wú)損壓縮方式.配置文件經(jīng)過壓縮后可以在一定程度上減少系統(tǒng)配置時(shí)間，但并不是配置文件經(jīng)過壓縮處理過后就能夠提高配置速率，解壓縮過程也是很重要的一個(gè)環(huán)節(jié).若解壓縮過程所消耗的時(shí)間代價(jià)過大或者消耗硬件資源過多，那么該壓縮算法就不適合對(duì)配置文件壓縮.近幾年，國(guó)內(nèi)外學(xué)術(shù)界對(duì)壓縮配置文件提高可重構(gòu)系統(tǒng)配置速率展開了廣泛的研究，現(xiàn)有的壓縮技術(shù)分別側(cè)重4個(gè)方面：壓縮算法、降低解壓縮代價(jià)、動(dòng)態(tài)可重構(gòu)和修改硬件結(jié)構(gòu).

1) 提升壓縮率

研究主要集中在通過改進(jìn)經(jīng)典的壓縮算法降低配置文件壓縮率，從而達(dá)到提高配置速率、減少存儲(chǔ)代價(jià)為目標(biāo).Vliegen等人[4]提出一種基于單片機(jī)遠(yuǎn)程配置FPGA的解決方案，其壓縮算法采用了行程編碼壓縮算法，該算法易于實(shí)現(xiàn)并且可以達(dá)到較為理想的壓縮效果;Tefan[5]針對(duì)Xilinx公司Virtex 4系列FPGA器件提出了2種專用壓縮算法，基于LZW的壓縮算法和基于二進(jìn)制算術(shù)編碼器壓的縮算法，該作者使用了較少的硬件資源分別實(shí)現(xiàn)了這2種壓縮算法;有些學(xué)者通過提出新的配置環(huán)境或者劃分配置文件等預(yù)處理操作，然后結(jié)合基于字典的壓縮算法實(shí)現(xiàn)高壓縮比[6-7];Jia等人[8]通過在JTAG配置模式中分別增加基于定長(zhǎng)行程編碼與解碼方案實(shí)現(xiàn)配置文件的壓縮與解壓縮；采用該種思路的還有文獻(xiàn)[9-11].從壓縮算法出發(fā)來(lái)解決配置文件壓縮的優(yōu)勢(shì)在于可以充分利用壓縮文件自身的特征，結(jié)合現(xiàn)有的優(yōu)秀壓縮算法進(jìn)行壓縮處理，獲得較為理想的壓縮率.但是，這往往會(huì)導(dǎo)致在提高壓縮率的同時(shí)忽略了解壓縮過程在配置過程中的重要地位，造成解壓縮電路復(fù)雜，時(shí)間開銷大.

2) 降低解壓縮代價(jià)

FPGA中的配置控制器需要對(duì)可配置資源中所有可編程資源進(jìn)行重新配置，需要輸出完整的配置信息，因此解壓縮過程是必要的環(huán)節(jié).解壓縮算法是通過FPGA內(nèi)部硬件邏輯資源實(shí)現(xiàn)的，解壓縮算法的性能與復(fù)雜程度也是嚴(yán)重影響配置性能的關(guān)鍵因素之一.國(guó)內(nèi)外許多學(xué)者以解壓縮效率為重點(diǎn)研究目標(biāo)，對(duì)壓縮算法進(jìn)行了大量研究.Jafri[12]采用LZSS壓縮算法對(duì)配置文件進(jìn)行壓縮，其優(yōu)勢(shì)在于可以針對(duì)LZSS算法實(shí)現(xiàn)高效的并行解壓縮算法；Qin等人[13]提出了一種具有解壓感知的壓縮算法，目的是為了更高效的完成解壓縮算法；Nabina等人[14]在傳統(tǒng)的配置控制器里結(jié)合了基于ICAP (internal configuration access port)優(yōu)化的解壓縮算法，實(shí)現(xiàn)了高速率的配置文件解壓縮過程；Jordan等人[15]從硬件實(shí)現(xiàn)角度進(jìn)行改進(jìn)，通過將固定硬件實(shí)現(xiàn)解壓算法與基于LUT實(shí)現(xiàn)解壓算法相結(jié)合的思想達(dá)到了靈活性與資源代價(jià)平衡的目的.

3) 動(dòng)態(tài)可重構(gòu)配置

動(dòng)態(tài)可重構(gòu)系統(tǒng)配置文件由2部分構(gòu)成：靜態(tài)可重構(gòu)區(qū)域配置信息和動(dòng)態(tài)可重構(gòu)配置信息.靜態(tài)可重構(gòu)區(qū)域配置信息完全相同，對(duì)多個(gè)配置文件而言這部分內(nèi)容為冗余數(shù)據(jù).許多研究者就從這個(gè)角度出發(fā)進(jìn)行關(guān)于動(dòng)態(tài)可重構(gòu)系統(tǒng)配置文件壓縮研究.Liu等人[16]實(shí)現(xiàn)了基于FPGA重構(gòu)技術(shù)的雷達(dá)信號(hào)處理系統(tǒng)，通過分析雷達(dá)信號(hào)處理的核心算法，找出不同算法對(duì)應(yīng)配置文件的重復(fù)部分并刪除，達(dá)到壓縮配置文件的目的;Sellers等人[17]對(duì)靜態(tài)可重構(gòu)部分的配置信息進(jìn)行了分析，通過刪除初始化配置信息中所有“0”幀信息和相關(guān)的寫入命令達(dá)到了壓縮初始化配置信息的目的;Gu等人[18]從3個(gè)層次進(jìn)行配置文件壓縮：配置幀內(nèi)、配置幀間和配置文件級(jí)壓縮;Beckhoff等人[19]通過分析靜態(tài)可重構(gòu)區(qū)域配置信息和動(dòng)態(tài)可重構(gòu)配置區(qū)域各自的特征，對(duì)這2部分采用不同的壓縮算法以提高整體壓縮率.

4) 修改硬件結(jié)構(gòu)

還有一些壓縮方案是通過修改配置系統(tǒng)結(jié)構(gòu)或者考慮其他配置因素從而進(jìn)一步提高壓縮率.Xie等人[20]用可尋址配置文件寄存器替代傳統(tǒng)移位寄存器，并且在FPGA內(nèi)部實(shí)現(xiàn)了以幀為單位的解壓電路，從而提高了配置速率.

本文依據(jù)各種壓縮思路的優(yōu)缺點(diǎn)，選用行程編碼壓縮思想(run length encoding, RLE)為核心對(duì)配置文件進(jìn)行壓縮.首先通過統(tǒng)計(jì)配置文件信息，確定定長(zhǎng)RLE壓縮算法相關(guān)參數(shù).然后對(duì)定長(zhǎng)RLE壓縮算法進(jìn)行優(yōu)化，結(jié)合Huffman編碼方式實(shí)現(xiàn)變長(zhǎng)RLE壓縮算法.最后，采用掩碼思想對(duì)變長(zhǎng)RLE壓縮結(jié)果進(jìn)行2次壓縮，進(jìn)一步降低壓縮率.

2 配置文件壓縮算法

FPGA配置文件是在用戶前期開發(fā)結(jié)束后，通過集成開發(fā)工具生成的用于配置FPGA芯片中可重構(gòu)資源的二進(jìn)制文件[21].FPGA配置時(shí)需要將配置文件從本地開發(fā)環(huán)境(運(yùn)行在PC或工作站上的EDA軟件)，或外部存儲(chǔ)系統(tǒng)傳輸?shù)紽PGA內(nèi)部存儲(chǔ)空間，然后再由內(nèi)部控制器進(jìn)行配置控制.對(duì)配置文件壓縮處理可以減少外部傳輸時(shí)間，提高配置速率.本節(jié)首先對(duì)可重構(gòu)系統(tǒng)配置過程進(jìn)行詳細(xì)介紹;然后針對(duì)動(dòng)態(tài)可重構(gòu)系統(tǒng)特征與要求，結(jié)合行程編碼壓縮算法探索多位壓縮元配置文件最優(yōu)壓縮參數(shù);然后對(duì)壓縮文件進(jìn)行深入分析，對(duì)行程編碼壓縮算法進(jìn)行改善，最終實(shí)現(xiàn)二進(jìn)制配置文件高效壓縮.

2.1 可重構(gòu)系統(tǒng)配置流程

本節(jié)首先從整體上介紹FPGA動(dòng)態(tài)可重構(gòu)系統(tǒng)的通用配置模型，然后通過Xilinx Virtex -Ⅱ系列FPGA的配置模型詳細(xì)介紹配置過程[10]，Virtex -Ⅱ系列FPGA為Xilinx 高端FPGA的入門級(jí)產(chǎn)品，其硬件結(jié)構(gòu)最具有代表性，最后以該模型為基礎(chǔ)，對(duì)動(dòng)態(tài)可重構(gòu)系統(tǒng)的配置時(shí)間代價(jià)進(jìn)行分析，提出優(yōu)化配置時(shí)間方案.

圖4為動(dòng)態(tài)可重構(gòu)系統(tǒng)的通用配置模型圖，主要由內(nèi)外2部分組成.外部主要由非易失性存儲(chǔ)器與存儲(chǔ)控制器組成，非易失性存儲(chǔ)器存儲(chǔ)配置文件，存儲(chǔ)控制器控制片外存儲(chǔ)器的工作.內(nèi)部FPGA部分主要由配置控制器、片內(nèi)高速緩存、配置端口以及配置單元存儲(chǔ)區(qū)組成.傳統(tǒng)的配置控制器和配置端口協(xié)議均由軟核IP實(shí)現(xiàn)，目前FPGA為了減少系統(tǒng)配置時(shí)間，這2部分采用硬件實(shí)現(xiàn)并集成在FPGA芯片中[22].片內(nèi)高速緩存的核心作用是存儲(chǔ)從片外高速存儲(chǔ)器傳輸?shù)呐渲脭?shù)據(jù)，配置控制器與片內(nèi)高速緩存通信，將配置數(shù)據(jù)發(fā)送給配置端口.配置控制器也與配置端口通信，當(dāng)配置端口內(nèi)部緩沖區(qū)飽和時(shí)，配置控制器控制片內(nèi)高速緩存停止向配置端口發(fā)送數(shù)據(jù).配置端口將配置信息傳送至相應(yīng)的可重構(gòu)單元配置存儲(chǔ)區(qū)，實(shí)現(xiàn)可重構(gòu)單元邏輯功能.

Fig. 5 Virtex -Ⅱ series PPGA dynamic reconfigurable system圖5 Virtex -Ⅱ系列PPGA動(dòng)態(tài)可重構(gòu)系統(tǒng)配置

動(dòng)態(tài)可重構(gòu)系統(tǒng)配置過程可以被劃分為2個(gè)階段：1)通過片外存控制器進(jìn)行配置數(shù)據(jù)下載，他控制片外高速存儲(chǔ)器將配置數(shù)據(jù)傳輸給片內(nèi)高速緩存；2)為配置控制器將高速緩存區(qū)配置數(shù)據(jù)通過配置端口加載至可重構(gòu)單元配置存儲(chǔ)區(qū).2部分以流水線方式同時(shí)運(yùn)行，直至配置文件被全部傳輸至配置單元存儲(chǔ)區(qū)或者第1階段全部配置數(shù)據(jù)被傳輸至片內(nèi)高速緩存.配置過程中2個(gè)階段是分離的，第1階段可以在第2階段開始前將全部配置數(shù)據(jù)下載至片內(nèi)高速緩存(在片內(nèi)緩存容量充足前提下)，提高系統(tǒng)配置速率.

Fig. 4 General configuration model of dynamic reconfigurable system圖4 動(dòng)態(tài)可重構(gòu)系統(tǒng)通用配置模型

圖5為Xilinx Virtex -Ⅱ系列FPGA動(dòng)態(tài)可重構(gòu)系統(tǒng)配置圖[23].灰色部分為FPGA外圍設(shè)備，白色部分為FPGA內(nèi)部結(jié)構(gòu). PPC(PowerPC)為嵌入式處理器，控制整個(gè)配置流程，其功能也可使用軟核嵌入式處理器Microblaze實(shí)現(xiàn).PLB_BRAM controller分別與PLB總線與PPC Memory相連，控制雙方數(shù)據(jù)傳輸.OPBHWICAP是一種配置協(xié)議控制器[24]，他采用有限狀態(tài)機(jī)控制ICAP對(duì)動(dòng)態(tài)可重構(gòu)區(qū)域(partially reconfigurable regions, PRR)與靜態(tài)區(qū)域(static part)進(jìn)行配置.OPBHWICAP中的BRAM為配置緩沖區(qū)，一般由FPGA內(nèi)部BRAM組成，大小為2KB. SysACEcntlr( system advanced configuration environment controller)是Xilinx提供的高級(jí)配置環(huán)境，實(shí)現(xiàn)外部微型存儲(chǔ)器(compact flash，CF)與內(nèi)部總線之間的高速通信[25].FPGA重構(gòu)配置過程可劃分為3個(gè)階段(如圖5所示):

1) PPC向System ACE cntlr發(fā)出指令，將外部存儲(chǔ)器中配置數(shù)據(jù)以塊(block)為單位傳輸至FPGA內(nèi)部存儲(chǔ)器PPC Memory.

2) PPC控制PLB_BRAM controller將配置數(shù)據(jù)以字(word)為單位傳輸至ICAP配置緩存器BRAM.

3) 當(dāng)ICAP配置緩存器飽和時(shí)，PPC控制OPBHWICAP將配置數(shù)據(jù)通過ICAP加載至可重構(gòu)單元配置存儲(chǔ)區(qū).

3個(gè)階段以流水線方式執(zhí)行，直到配置文件全部加載到配置存儲(chǔ)區(qū)，配置過程結(jié)束[26].

根據(jù)上述配置過程描述，F(xiàn)PGA配置過程3個(gè)階段可被簡(jiǎn)化為EM-PPC，PPC-ICAP，ICAP-CM，其中EM(external memory)為外部存儲(chǔ)器，RT(reconfigure time)表示可重構(gòu)系統(tǒng)配置時(shí)間：

RT=RTEM-PPC+RTPPC-ICAP+RTICAP-CM,

(1)

其中，RTEM-PPC，RTPPC-ICAP，RTICAP-CM分別表示配置階段EM-PPC,PPC-ICAP，ICAP-CM所需時(shí)間.文獻(xiàn)[24]對(duì)3個(gè)階段占據(jù)整個(gè)配置時(shí)間的比例進(jìn)行統(tǒng)計(jì)，結(jié)果如表1所示：

Table 1 Statistics of Configuration Time Ratio, Port Throughput and Theoretical Throughput

表1中的外部存儲(chǔ)器為CF卡.從表1可知:1)EM-PPC階段時(shí)間代價(jià)最高，約占可重構(gòu)配置時(shí)間的77.28%；2)EM-PPC階段吞吐量利用率最低，僅占理論吞吐量的0.52%.由表1可得，對(duì)EM-PPC配置階段進(jìn)行優(yōu)化，可大幅度提高配置速率,依據(jù)Amdahl定律:

(2)

其中,P為EM-PPC所占時(shí)間百分比，S為該階段優(yōu)化時(shí)間加速比，滿足S≥1.

可以采用2種思路對(duì)該階段傳輸速率進(jìn)行優(yōu)化：1)提高吞吐量；2)壓縮配置文件.表1中采用CF卡的最大傳輸速率為64 MBps，若將配置文件提前傳輸?shù)紻DR2@ 800 MBps高速存儲(chǔ)器中，則EM-PPC加速比S=12.5，對(duì)應(yīng)的Speedup=3.46，即配置時(shí)間減少到原始配置時(shí)間的28.9%.如將配置文件壓縮為原始配置文件大小的50%，則配置時(shí)間減少到原始配置時(shí)間的72.72%.本文旨在不修改硬件結(jié)構(gòu)的前提下，對(duì)通用動(dòng)態(tài)可重構(gòu)系統(tǒng)配置時(shí)間進(jìn)行優(yōu)化，本文選用配置文件壓縮思想進(jìn)行配置時(shí)間優(yōu)化.

2.2 RLE配置文件壓縮算法

通過對(duì)動(dòng)態(tài)可重構(gòu)系統(tǒng)配置過程分析，本文選用壓縮配置文件思路減少系統(tǒng)配置時(shí)間.通過對(duì)國(guó)內(nèi)外研究現(xiàn)狀分析，本文根據(jù)2級(jí)制配置文件的特征，采用行程編碼無(wú)損壓縮算法RLE進(jìn)行配置文件壓縮.本節(jié)首先對(duì)RLE壓縮算法進(jìn)行介紹.其次依據(jù)benchmark中二進(jìn)制配置文件特征選擇RLE壓縮算法參數(shù).然后對(duì)定長(zhǎng)RLE壓縮算法結(jié)果進(jìn)行分析，結(jié)合Huffman編碼思想實(shí)現(xiàn)變長(zhǎng)RLE壓縮算法.最后，根據(jù)變長(zhǎng)RLE壓縮結(jié)果中“0”“1”分布規(guī)律，采用掩碼壓縮思想實(shí)行2次壓縮，實(shí)現(xiàn)掩碼變長(zhǎng)RLE壓縮算法.

RLE壓縮算法是一種簡(jiǎn)單高效的無(wú)損壓縮算法，該算法將壓縮信息視為字符串序列，核心思想是將字符串序列中連續(xù)相同字符統(tǒng)計(jì)表示，實(shí)現(xiàn)文本壓縮目標(biāo).對(duì)于連續(xù)相同字符采用字符加計(jì)數(shù)方式進(jìn)行表示，對(duì)于不重復(fù)字符，計(jì)數(shù)為1.RLE壓縮結(jié)果可采用元組(C,L)表示，C為被壓縮字符，L為計(jì)數(shù).例如字符串“AAAAABBCCCCD”經(jīng)過壓縮后，結(jié)果為“A5B2C4D1”.本文將RLE壓縮算法移植到對(duì)二進(jìn)制配置文件的壓縮，字符串序列轉(zhuǎn)換為位序列，壓縮單位由字節(jié)轉(zhuǎn)換為位.不同于字符串壓縮，二進(jìn)制文件壓縮結(jié)果中C與L使用二進(jìn)制表示.如位序列“11111100011111000000”經(jīng)過壓縮后的中間結(jié)果為“16031506”，然后將計(jì)數(shù)L采用二進(jìn)制表示，結(jié)果為“111001111010110.序列壓縮前長(zhǎng)度為20 b，壓縮后位長(zhǎng)度為15 b，實(shí)現(xiàn)壓縮的目的.在解壓過程中，由于C與L均為二進(jìn)制表示，無(wú)明確分界點(diǎn)，解壓失敗.解決思路有2種：1)采用壓縮標(biāo)記位的定長(zhǎng)壓縮表示格式，如圖6(a)所示；2)采用無(wú)壓縮標(biāo)記位的定長(zhǎng)壓縮表示格式，如圖6(b)所示.

Fig. 6 RLE binary compressed format圖6 RLE二進(jìn)制壓縮表示格式

本文采用帶標(biāo)記位的定長(zhǎng)壓縮表示方法，減少未重復(fù)數(shù)據(jù)帶來(lái)的計(jì)數(shù)位長(zhǎng)度代價(jià)，本文后續(xù)所指定長(zhǎng)壓縮均為帶標(biāo)記位的定長(zhǎng)壓縮.采用定長(zhǎng)壓縮方法得到的壓縮率的取值范圍：

(3)

其中，m∈+，n∈+.此時(shí)，壓縮率RRLE的取值范圍：

(4)

同樣，在最糟糕的情況下仍然會(huì)出現(xiàn)壓縮膨脹.

定長(zhǎng)RLE壓縮算法中的壓縮元C長(zhǎng)度m與計(jì)數(shù)L長(zhǎng)度n可根據(jù)配置文件特征進(jìn)行選擇，追求最小壓縮率.本節(jié)以Xilinx 系列FPGA配置文件為代表，對(duì)配置文件的分類和組成進(jìn)行相關(guān)介紹，對(duì)benchmark中重復(fù)數(shù)據(jù)進(jìn)行分析，采用理論結(jié)合實(shí)驗(yàn)的方式來(lái)確定最優(yōu)m，n組合.

Xilinx FPGA應(yīng)用程序開發(fā)工具(ISE和Vivado)可以按照需求不同生成5種格式配置文件，對(duì)應(yīng)后綴名分別為：bit，rbt，bin，mcs，hex，不同配置文件對(duì)應(yīng)不同配置環(huán)境.bit文件包含配置文件組成中的所有部分:冗余頭部信息、配置信息、CRC校驗(yàn)信息和冗余尾部信息.冗余頭部信息主要包括當(dāng)前工程名稱、芯片型號(hào)和編譯時(shí)間等信息，由于工程名長(zhǎng)度不定，一般頭部信息長(zhǎng)度約為72 B.配置信息為配置文件的主體部分，進(jìn)行可重構(gòu)計(jì)算單元、路由單元以及存儲(chǔ)單元的信息配置.校驗(yàn)信息對(duì)配置信息進(jìn)行校驗(yàn).冗余尾部信息由12個(gè)32 b的空操作組成，這部分不會(huì)被加載到FPGA中，目的是給予配置器充足的時(shí)間完成配置過程.本文以.bit格式配置文件為原始數(shù)據(jù)進(jìn)行二進(jìn)制配置文件壓縮研究.

圖8為Xilinx Kintex-7 XC7K325T 芯片部分二進(jìn)制配置文件片段[2](16進(jìn)制表示、Xilinx官網(wǎng)提供).FPGA配置以幀為最小配置單位，每幀大小為32 b.從圖8中可以得出2個(gè)結(jié)論：1)配置幀幀內(nèi)存在大量的重復(fù)數(shù)據(jù)；2)配置幀幀間也存在大量重復(fù)數(shù)據(jù).根據(jù)配置幀長(zhǎng)度和幀內(nèi)重復(fù)的特征，本文擬給壓縮元長(zhǎng)度m分別賦值為1,2,4,8,16，32.依據(jù)壓縮元連續(xù)出現(xiàn)的頻數(shù)計(jì)算獲取相應(yīng)的計(jì)數(shù)L長(zhǎng)度n值，從中選出1組理論壓縮率最低的(m,n)元組作為定長(zhǎng)壓縮參數(shù).本文采用理論結(jié)合實(shí)驗(yàn)的方法選取最優(yōu)參數(shù)組合，實(shí)驗(yàn)數(shù)據(jù)為V5_DES56.bit.壓縮率RREL計(jì)算為

(5)

其中，Luncompress為未壓縮表示格式長(zhǎng)度，Lcompress為壓縮表示格式長(zhǎng)度.

Fig. 8 Kintex-7 XC7K325T binary configuration file圖8 Kintex-7 XC7K325T 二進(jìn)制配置文件片段

當(dāng)m=1時(shí)，不需要對(duì)配置文件做任何處理，直接統(tǒng)計(jì)壓縮元(0或1)在不同計(jì)數(shù)L下的重復(fù)頻數(shù)，并計(jì)算對(duì)應(yīng)配置數(shù)據(jù)占配置文件大小百分比.當(dāng)壓縮元重復(fù)頻數(shù)大于計(jì)數(shù)L可表示范圍時(shí)，采用截?cái)喾椒ㄌ幚?如當(dāng)n=8時(shí)，可表示的最大數(shù)值為256，當(dāng)統(tǒng)計(jì)頻數(shù)大于256時(shí)，采取截?cái)嗵幚?，重新壓縮.因?yàn)椴粫?huì)出現(xiàn)計(jì)數(shù)L=0的情況，所以本文采用(L-1)對(duì)應(yīng)的二進(jìn)制數(shù)表示計(jì)數(shù)L.如連續(xù)260個(gè)“1”被壓縮為(1,1,11111111)(1,1,00101011).當(dāng)m=1,n=8時(shí)，統(tǒng)計(jì)結(jié)果如表2所示.

當(dāng)m=1,n=8，壓縮標(biāo)記為“0”時(shí)，壓縮格式長(zhǎng)度為2；壓縮標(biāo)記為“1”時(shí)，壓縮格式長(zhǎng)度為10.此時(shí)理論壓縮率：

(6)

其中，Pi為L(zhǎng)=i對(duì)應(yīng)配置數(shù)據(jù)大小占據(jù)配置文件百分比.將表中相關(guān)數(shù)據(jù)帶入式(6)，計(jì)算可得RRLE值為109.42%，即采m=1,n=8元組時(shí)，理論壓縮率為109.42%，出現(xiàn)壓縮膨脹現(xiàn)象.究其原因，主要是因?yàn)楫?dāng)n=8時(shí)，壓縮格式長(zhǎng)度為10，若原始數(shù)據(jù)連續(xù)長(zhǎng)度小于10的重復(fù)數(shù)據(jù)均會(huì)產(chǎn)生壓縮膨脹現(xiàn)象，而此部分所占比例為38.41%，膨脹部分占據(jù)比例過高.后續(xù)需要將n值減小，降低膨脹部分所占比例.當(dāng)n值分別取3,4,5,6,7時(shí)對(duì)應(yīng)的壓縮率如表3所示.

Table 2 Statistics of Corresponding Data (m=1,n=8)表2 m=1,n=8對(duì)應(yīng)數(shù)據(jù)統(tǒng)計(jì)表

Table 3 Different n Value Compression Rate (m=1)表3 m=1對(duì)應(yīng)不同n值壓縮率表

從上述計(jì)算結(jié)果可知，當(dāng)壓縮元C長(zhǎng)度m=1時(shí)，計(jì)數(shù)L長(zhǎng)度n=5時(shí)壓縮率最低，壓縮效果最好.當(dāng)n=1或者n=2時(shí)，附加壓縮標(biāo)記位，在任何情況下都是壓縮膨脹.同樣，隨著n值越來(lái)越大，壓縮格式長(zhǎng)度n+2值也會(huì)增大，計(jì)數(shù)L

同理，計(jì)算當(dāng)m分別為2，4，8，16，32，n分別為1～10時(shí)的壓縮率并進(jìn)行匯總，當(dāng)m分別為2，4，8，16，32時(shí)的最佳壓縮率如表4所示:

Table 4 The Optimal (m,n) Compression Ratio Statistics表4 最優(yōu)(m,n)元組壓縮率統(tǒng)計(jì)表

由上述理論計(jì)算結(jié)果可知，當(dāng)m=4,n=4時(shí)定長(zhǎng)RLE壓縮算法取得最優(yōu)壓縮效果.本文后續(xù)將m=4作為通用二進(jìn)制配置文件的最佳壓縮元長(zhǎng)度向變長(zhǎng)RLE壓縮算法進(jìn)行改善，進(jìn)一步降低壓縮率.

2.3 H-RLE壓縮算法

定長(zhǎng)RLE壓縮格式后n位為計(jì)數(shù)長(zhǎng)度，可以表示計(jì)數(shù)范圍為[1,2n].當(dāng)采用定長(zhǎng)壓縮方案m=4,n=4時(shí)，計(jì)數(shù)L=2的二進(jìn)制表示為“0001”，其中前3個(gè)“0”起到占位作用.當(dāng)計(jì)數(shù)L=3或4時(shí)，前2個(gè)“0”起到占位作用，他們的存在與否并不會(huì)對(duì)計(jì)數(shù)值產(chǎn)生影響，只是起到輔助解壓的作用.根據(jù)統(tǒng)計(jì)結(jié)果可以預(yù)測(cè)，當(dāng)計(jì)數(shù)長(zhǎng)度為n，計(jì)數(shù)L∈[2,2n-1]占據(jù)配置文件比例遠(yuǎn)高于L∈[2n-1+1,2n]，并且對(duì)于同一個(gè)m值，隨著n值增大，前半部分占據(jù)的比例會(huì)越來(lái)越高.L∈[2,2n-1]時(shí)，計(jì)數(shù)格式都會(huì)存在占位“0”，若可以將占位“0”刪除掉，會(huì)對(duì)壓縮效果產(chǎn)生明顯改善，降低壓縮率.

定長(zhǎng)RLE壓縮格式的優(yōu)勢(shì)在于解壓縮簡(jiǎn)單，只需按照相應(yīng)標(biāo)記位長(zhǎng)度、壓縮元長(zhǎng)度m和計(jì)數(shù)長(zhǎng)度n進(jìn)行解釋實(shí)現(xiàn)解壓過程.例如，當(dāng)m=4,n=4時(shí)的壓縮數(shù)據(jù)如圖9(a)所示，按照定長(zhǎng)RLE壓縮算法，對(duì)應(yīng)的解壓數(shù)據(jù)如圖9(b)所示.如果將壓縮數(shù)據(jù)中的占位“0”刪除，則壓縮數(shù)據(jù)如圖9(c)所示.解壓時(shí)，前1個(gè)壓縮格式中的計(jì)數(shù)長(zhǎng)度不能確定，前1個(gè)壓縮格式中的計(jì)數(shù)部分與后1個(gè)壓縮格式中的壓縮標(biāo)記位甚至壓縮元重合(圖9(c)陰影部分)，無(wú)法正確解壓.如果可以動(dòng)態(tài)識(shí)別計(jì)數(shù)部分長(zhǎng)度，如圖9(d)所示，就可在不增加附加信息的前提下正確解壓.本文采用Huffmam編碼方式對(duì)計(jì)數(shù)部分進(jìn)行編碼，解決動(dòng)態(tài)識(shí)別計(jì)數(shù)部分長(zhǎng)度問題.

Fig. 9 Compression and decompression圖9 RLE壓縮與解壓縮示意圖

Huffman編碼是David Huffman于1952年提出的一種變長(zhǎng)信息編碼方式.Huffman編碼首先統(tǒng)計(jì)編碼字符在文件中出現(xiàn)的頻率.依據(jù)統(tǒng)計(jì)信息構(gòu)建一棵二叉樹，該二叉樹又被稱為Huffman樹.通過Huffman樹為每個(gè)字符提供唯一的二進(jìn)制編碼.將編碼文件中的每個(gè)字符用對(duì)應(yīng)的二進(jìn)制編碼替換，得到編碼文件.Huffman編碼核心思想是將出現(xiàn)頻率高的字符用較短的二進(jìn)制表示，出現(xiàn)頻率低的字符用較長(zhǎng)的二進(jìn)制表示，保證編碼文件最小.Huffman編碼又被稱為最優(yōu)前綴編碼，因?yàn)镠uffman樹確保每個(gè)字符對(duì)應(yīng)的二進(jìn)制編碼都不會(huì)是其他二進(jìn)制編碼的前綴.本文利用Huffman編碼的帶權(quán)路徑最短與前綴性解決RLE壓縮格式中計(jì)數(shù)部分長(zhǎng)度動(dòng)態(tài)識(shí)別問題，提出變長(zhǎng)Huffman Run Length Encoding (H-RLE)壓縮算法.通過m=4,n=4的統(tǒng)計(jì)結(jié)果介紹H-RLE壓縮思想.當(dāng)m=4,n=4時(shí)，計(jì)數(shù)L不同長(zhǎng)度出現(xiàn)次數(shù)的概率Q如表5所示:

Table 5 Frequency of Different L表5 不同L對(duì)應(yīng)頻率統(tǒng)計(jì)表

然后依據(jù)Huffman編碼算法對(duì)2～16分別編碼，結(jié)果如表6所示：

Table 6 Huffman of Different L表6 不同L對(duì)應(yīng)Huffman編碼

然后根據(jù)式(7)計(jì)算理論壓縮率：

(7)

其中，|C(i)|表示計(jì)數(shù)重復(fù)次數(shù)i對(duì)應(yīng)的編碼位數(shù).將相關(guān)數(shù)據(jù)帶入計(jì)算式得出RRLE為58.76%，計(jì)算結(jié)果表明，采用Huffman編碼表示計(jì)數(shù)部分可以降低壓縮率.

H-RLE跳出了定長(zhǎng)RLE壓縮算法計(jì)數(shù)部分n位限制，消除了占位“0”，降低了壓縮率.上述示例中重復(fù)數(shù)據(jù)出現(xiàn)頻數(shù)被限制在了L∈[1,16](n=4).依據(jù)m=4，n=8的統(tǒng)計(jì)結(jié)果可知，L=256出現(xiàn)的頻數(shù)為1586，占據(jù)整個(gè)配置文件的19.4%.按照上述壓縮表示方式，連續(xù)256個(gè)壓縮元被劃分為16(256/16)個(gè)L=16的8 b長(zhǎng)度壓縮格式，壓縮后的長(zhǎng)度為128 b，該部分壓縮率為12.5%.如果可以將L=256進(jìn)行Huffman編碼(假設(shè)256對(duì)應(yīng)的Huffman編碼長(zhǎng)度為20 b)，那么該部分的壓縮率就可達(dá)到2.44%.本文綜合考慮Huffman編碼長(zhǎng)度與配置文件統(tǒng)計(jì)結(jié)果選擇最大L值.當(dāng)L=512時(shí)出現(xiàn)的頻率為973，占據(jù)整個(gè)配置文件的23.8%；當(dāng)L=1024時(shí)出現(xiàn)的頻率為458，占據(jù)整個(gè)配置文件的22.4%；當(dāng)L=2048時(shí)出現(xiàn)的頻率為212，占據(jù)整個(gè)配置文件的20.74%；當(dāng)L=4096時(shí)出現(xiàn)的頻率為78，占據(jù)整個(gè)配置文件的15.26%.假設(shè)當(dāng)L=2048時(shí)對(duì)應(yīng)的Huffman編碼長(zhǎng)度為25 b，該部分的壓縮率可達(dá)到0.37%；當(dāng)L=4096時(shí)對(duì)應(yīng)的編碼長(zhǎng)度為26 b，該部分對(duì)應(yīng)的壓縮率為0.19%，相對(duì)于L=2048，文件整體壓縮率降約低了0.18%，改善不大.本文選擇最大L=2048，并根據(jù)此數(shù)據(jù)對(duì)測(cè)試文件進(jìn)行重新統(tǒng)計(jì)，獲取較優(yōu)Huffman編碼.表7給出L為部分?jǐn)?shù)值時(shí)對(duì)應(yīng)頻率：

Table 7 Frequency of Extended L表7 擴(kuò)展的L值對(duì)應(yīng)頻率統(tǒng)計(jì)表

對(duì)應(yīng)的Huffman編碼如表8所示：

Table 8 Huffman Coding of Extended L表8 擴(kuò)展的L值對(duì)應(yīng)Huffman編碼

當(dāng)計(jì)數(shù)L>2 048時(shí)，按照截?cái)喾椒ㄌ幚?從表8可知，當(dāng)L>16時(shí)并沒有采用等差增長(zhǎng)的方式進(jìn)行統(tǒng)計(jì)，而是采用了公比為2的等比增長(zhǎng)方式統(tǒng)計(jì).假如按照等差增長(zhǎng)方式，編碼位數(shù)增長(zhǎng)較快，當(dāng)L=2 048時(shí)，需要上千位編碼表示.采用公比為2的等比增長(zhǎng)方式有2個(gè)優(yōu)勢(shì)：1)隨著L值的等比增長(zhǎng)，編碼位數(shù)增加緩慢，減少編碼長(zhǎng)度，降低壓縮率；2)當(dāng)統(tǒng)計(jì)數(shù)據(jù)不屬于編碼數(shù)據(jù)中的某一數(shù)值時(shí)，可采用較少次數(shù)的截?cái)喾椒ū硎驹摂?shù)據(jù)(類似于二分查找思想).例如當(dāng)統(tǒng)計(jì)次數(shù)為448時(shí)，可以采用256-128-64這種2次截?cái)?個(gè)壓縮格式的方式表示，表示長(zhǎng)度為48 b.如果不存在L=64 b和L=128 b對(duì)應(yīng)的Huffman編碼，需要采用256-32-32-32-32-32-32這種6次截?cái)?個(gè)壓縮格式表示，表示長(zhǎng)度為100 b.L∈[2,16]采用等差增長(zhǎng)是因?yàn)樵摬糠炙碱l率占據(jù)了[2,2 048]中的99.3%，若采用截?cái)喾绞?，?huì)增加表示長(zhǎng)度.本文根據(jù)統(tǒng)計(jì)結(jié)果以及編碼方式，將L≤2 048中未編碼的值采用截?cái)嗵幚恚缓笥?jì)算理論壓縮率：

(8)

其中,S為經(jīng)過編碼處理的L值集合.將相應(yīng)的數(shù)據(jù)帶入式(8)可得其壓縮率為53.43%.

2.4 MH-RLE壓縮算法

按照H-RLE壓縮算法對(duì)測(cè)試文件進(jìn)行壓縮，理論計(jì)算得到的最小壓縮率為53.43%.其中包含未壓縮部分的40.93%與壓縮部分的12.50%.從式(8)可以得出2點(diǎn)結(jié)論：1)原始文件中未壓縮部分P1占據(jù)32.74%，這部分導(dǎo)致壓縮率RREL>40.93%；2)其余67.26%部分被壓縮至12.50%，表明配置文件中連續(xù)重復(fù)的“0”或者“1”較多，“0”，“1”分布并不均勻.由結(jié)論1可知，如果不對(duì)未壓縮部分進(jìn)行處理，壓縮率將不會(huì)產(chǎn)生明顯改善.本文后續(xù)對(duì)H-RLE壓縮結(jié)果進(jìn)行分析，依據(jù)分析結(jié)果采用掩碼壓縮思想，提出Mask Huffman Run Length Encoding (MH-RLE)壓縮算法進(jìn)行2次壓縮，進(jìn)一步降低壓縮率，提升壓縮效果.

掩碼壓縮最初提出主要是為了優(yōu)化靜態(tài)字典壓縮算法，采用掩碼的方法，提高字典的覆蓋范圍.在靜態(tài)字典壓縮算法中，需要將原始數(shù)據(jù)與字典條目進(jìn)行匹配，若匹配成功，用該條目在字典中的位置表示該數(shù)據(jù).在二進(jìn)制靜態(tài)字典壓縮過程中會(huì)存在許多數(shù)據(jù)與字典中數(shù)據(jù)僅相差n位，這樣的數(shù)據(jù)不能被壓縮.將這些數(shù)據(jù)與字典中的某1條目進(jìn)行異或操作，可以得出n個(gè)差異位置.由于異或操作具有可逆性，解壓時(shí)只需將對(duì)應(yīng)位置的“0”修改為“1”，然后與字典數(shù)據(jù)進(jìn)行異或運(yùn)算.例如假設(shè)字典條目為“01000100”，原始數(shù)據(jù)為“01000000”，異或結(jié)果為“00000100”，即數(shù)據(jù)不同位為第5位.解壓時(shí)只需將“00000000”中第5位修改為1，然后字典條目“01000100”進(jìn)行異或運(yùn)算，得出結(jié)果為原始數(shù)據(jù)“01000000”.

本文根據(jù)原始文件“0”，“1”分布不均勻的特征，對(duì)壓縮后的文件進(jìn)行統(tǒng)計(jì)分析，得出“0”占據(jù)變長(zhǎng)RLE壓縮后文件的21.14%，“1”占據(jù) 78.86%.根據(jù)“0”,“1”分別所占比例，本文以5 b為單位長(zhǎng)度，以1 b為掩碼長(zhǎng)度進(jìn)行掩碼壓縮，壓縮格式如圖10所示：

Fig. 10 Mask format圖10 掩碼格式

掩碼標(biāo)識(shí)為“0”表示5 b原始數(shù)據(jù)未被處理，即5 b原始數(shù)據(jù)與“00000”進(jìn)行異或運(yùn)算，得出結(jié)果中含有“1”的數(shù)量count≥2.掩碼標(biāo)識(shí)為“1”表示異或運(yùn)算結(jié)果中含有“1”數(shù)量為0或1.3 b數(shù)據(jù)表示“1”出現(xiàn)位置，即“001”至“101”表示“1”從左至右出現(xiàn)的位置.本文用“000”表示5 b原始數(shù)據(jù)為“00000”，用“111”表示5 b原始數(shù)據(jù)為“11111”.由于配置文件是以配置幀為單位進(jìn)行配置，而配置幀的大小為32 b，非5的整數(shù)倍，本文對(duì)于剩余位數(shù)采取掩碼為“0”的非壓縮處理并且不采用補(bǔ)位處理，保證后續(xù)配置過程的正確性.

當(dāng)掩碼格式確定后，本文對(duì)H-RLE壓縮后的結(jié)果進(jìn)行重新處理，實(shí)現(xiàn)MH-RLE壓縮算法：1)對(duì)每5 b數(shù)據(jù)與“00000”進(jìn)行異或運(yùn)算；2)統(tǒng)計(jì)運(yùn)算結(jié)果中“1”的數(shù)量count，當(dāng)count≥2，輸出0，count≥1時(shí)輸出為1；3)統(tǒng)計(jì)輸出結(jié)果中0和1所占百分比.根據(jù)處理結(jié)果可知，0所占百分比為27.21%，1所占百分比為 72.79%.然后計(jì)算理論壓縮率：

(9)

其中,RREL_MASK表示MH-RLE壓縮率.將上述統(tǒng)計(jì)結(jié)果以及RREL=53.43%帶入式(9)，計(jì)算理論壓縮率為48.56%.

3 MH-RLE壓縮算法性能測(cè)試與評(píng)價(jià)

可重構(gòu)系統(tǒng)配置文件壓縮過程在集成開發(fā)環(huán)境中通過軟件壓縮算法實(shí)現(xiàn)，壓縮時(shí)間代價(jià)對(duì)動(dòng)態(tài)可重構(gòu)系統(tǒng)配置性能沒有影響.本節(jié)不考慮壓縮時(shí)間，僅從壓縮率角度評(píng)價(jià)本文提出的MH-RLE壓縮算法性能.本節(jié)首先對(duì)測(cè)試數(shù)據(jù)集中的二進(jìn)制配置文件進(jìn)行簡(jiǎn)單介紹，然后通過本文提出的壓縮算法對(duì)所有測(cè)試文件進(jìn)行壓縮，最后將壓縮結(jié)果與多種優(yōu)秀的壓縮算法的壓縮結(jié)果進(jìn)行對(duì)比，評(píng)價(jià)本文壓縮算法的優(yōu)劣.

3.1 實(shí)驗(yàn)數(shù)據(jù)

本次實(shí)驗(yàn)測(cè)試數(shù)據(jù)集來(lái)源于Department of Computer Science 12[27].為了保證壓縮算法對(duì)不同應(yīng)用程序的有效性，測(cè)試集包含了3種FPGA應(yīng)用領(lǐng)域程序模塊，其中包括加密模塊DES和RC5、信號(hào)處理模塊FFT與FIR、網(wǎng)絡(luò)通信模塊Net(network router)與Xbar (crossbar).上述6種應(yīng)用程序占據(jù)LUT資源90%以上.測(cè)試集增加了SoC模塊配置文件，占據(jù)LUT資源70%左右，確保在不同資源利用率下的壓縮算法性能.為了體現(xiàn)壓縮算法對(duì)各種FPGA芯片對(duì)應(yīng)配置文件壓縮效果，測(cè)試數(shù)據(jù)分別由2個(gè)生產(chǎn)商的4個(gè)系列FPGA芯片組成，分別為：Altera Cyclone -Ⅱ，Xilinx Spartan-3，Xilinx Virtex -Ⅱ，Xilinx Virtex-V.表9～12介紹各種應(yīng)用模塊在不同F(xiàn)PGA芯片上對(duì)應(yīng)可重構(gòu)資源利用比例信息.

Table 9 Resources Using Rate of 7 Applications in Altera Cyclone -Ⅱ

Table 10 Resources Using Rate of 7 Applications in Xilinx Spartan-3

Table 11 Resources Using Rate of 7 Applications in Xilinx Virtex -Ⅱ

Table 12 Resources Using Rate of 7 Applications in Xilinx Virtex-V

3.2 測(cè)試與評(píng)價(jià)

圖11為9種壓縮算法分別在4個(gè)系列FPGA芯片測(cè)試環(huán)境下的壓縮率比較圖.9種壓縮算法分別為T-RLE,T-RLE*,F-RLE,LZSS8,LZSS16,HUFF8,EPC16,GZIP和本文提出的MH-RLE.其中HUFF8為Huffman壓縮算法的實(shí)現(xiàn)，之中的8表示以8b為單位建立Huffman樹.GZIP為L(zhǎng)inux環(huán)境下常用壓縮程序，實(shí)驗(yàn)中使用的GZIP版本為1.3.5.為了忽略各種壓縮算法對(duì)個(gè)別配置文件具有較低壓縮率，實(shí)驗(yàn)采用均值(AV)比較各個(gè)壓縮算法的性能(圖11中每幅圖的最右邊類別).從圖11中可以看出，各種壓縮算法對(duì)不同配置文件的壓縮性能表現(xiàn)各不一樣，不能依據(jù)某1組實(shí)驗(yàn)結(jié)果確定某個(gè)壓縮算法的性能，本節(jié)主要參考AV值來(lái)分析MH-RLE壓縮算法性能.MH-RLE在Altera Cyclone -Ⅱ,Xilinx Spartan-3,Virtex -Ⅱ,Virtex-V FPGA芯片的平均壓縮率分別為：54.36%，57.32%，41.98%，45.61%.

首先，從圖11可得，MH-RLE壓縮率高于HUFF8與GZIP.在二進(jìn)制配置文件壓縮算法中，Huffman算法首先將配置信息全部遍歷，然后根據(jù)指定壓縮元長(zhǎng)度統(tǒng)計(jì)壓縮元頻數(shù)，建立相應(yīng)的靜態(tài)Huffman樹，最后依據(jù)Huffman樹進(jìn)行壓縮，也可以在第1次變量過程中動(dòng)態(tài)建立Huffman樹.Huffman壓縮算法具有較優(yōu)的壓縮率，但是解壓硬件資源消耗過大.配置文件解壓過程需要由硬件完成，Huffman解壓過程需要將Huffman樹存入硬件資源，需要耗費(fèi)大量的硬件資源，Huffman解壓所需硬件資源為其他壓縮算法對(duì)應(yīng)解壓資源的40倍左右.GZIP核心思想是通過LZSS壓縮算法的變形算法對(duì)配置文件進(jìn)行首次壓縮，然后將壓縮結(jié)果采用Huffman壓縮算法進(jìn)行2次壓縮，所以GZIP壓縮算法雖然具有較優(yōu)的壓縮率，但是解壓縮硬件代價(jià)比Huffman壓縮代價(jià)更高，在可重構(gòu)系統(tǒng)中一般不會(huì)采用GZIP壓縮算法.MH-RLE壓縮算法雖然也采用了Huffman壓縮思想，但是Huffman樹對(duì)應(yīng)的葉子節(jié)點(diǎn)僅有22個(gè)，并且靜態(tài)建立，即該Huffman樹對(duì)所有配置文件壓縮與解壓均有效，不會(huì)因?yàn)榕渲梦募煌匦滦薷慕鈮核惴ǖ膶?shí)現(xiàn).

Fig. 11 Compression ratio comparison圖11 壓縮率比較圖

其次，相對(duì)于Xilinx系列FPGA對(duì)應(yīng)配置文件，在Altera系列FPGA對(duì)應(yīng)配置文件中，MH-RLE壓縮算法性能明顯下降.圖11(a)中MH-RLE壓縮算法壓縮率比T-RLE*，LZSS8，LZSS16，EPC16壓縮算法壓縮率低，比T-RLE和F-RLE壓縮算法壓縮率高.在圖11(b)～(d)中，MH-RLE壓縮率僅高于HUFF8和GZIP壓縮算法，主要原因是MH-RLE壓縮算法中的所有參數(shù)均來(lái)源于對(duì)Xilinx系列FPGA配置文件數(shù)據(jù)的統(tǒng)計(jì)，而Altera系列對(duì)應(yīng)的配置文件描述方式(非公開)與Xilinx系列有所不同，所以MH-RLE壓縮算法針對(duì)Altera系列FPGA配置文件的壓縮性能不如Xilinx系列FPGA配置文件.

最后，本節(jié)通過具體數(shù)據(jù)表現(xiàn)MH-RLE壓縮算法相對(duì)于其他8種壓縮算法壓縮率降低比例，數(shù)據(jù)計(jì)算方式為RMH-RLE-Rother，計(jì)算結(jié)果如表13所示，其中，“-”表示壓縮率降低.

Table 13 Comparison of Compression Ratio Optimization表13 MH-RLE壓縮率優(yōu)化比較表 %

4 解壓電路介紹

根據(jù)本文提出的FPGA配置文件壓縮算法，進(jìn)行相應(yīng)的硬件解壓縮電路設(shè)計(jì)，由于配置文件是以1幀二進(jìn)制數(shù)據(jù)(32 b)的形式進(jìn)行數(shù)據(jù)存儲(chǔ)和傳輸，因此，結(jié)合MH-RLE壓縮算法的特點(diǎn)，將解壓電路設(shè)計(jì)為外部、內(nèi)部2個(gè)部分，其中解壓縮外部電路如圖12所示，由隊(duì)列緩存(queue buffer)、輸入緩存(input buffer)、解壓縮模塊(MH-RLE decoder)、輸出緩存(output buffer)組成，其中隊(duì)列緩存按配置幀緩存被壓縮后的配置文件數(shù)據(jù)，輸入緩存以配置幀為單位依次從隊(duì)列緩存中抽取數(shù)據(jù)，解壓縮模塊實(shí)現(xiàn)MH-RLE解壓縮算法，輸出緩存放置原始配置文件數(shù)據(jù)，等待后續(xù)電路讀取.

圖13為解壓縮內(nèi)部電路實(shí)現(xiàn)，開發(fā)工具為XILINX ISE Design Suite 13.4，開發(fā)語(yǔ)言為VHDL，以解壓縮模塊的頂層電路設(shè)計(jì)圖形式進(jìn)行展示.其中InputBuffer用于接收1幀(32b)二進(jìn)制數(shù)據(jù)，Judgment判斷是否進(jìn)行了掩碼壓縮和Huffman壓縮，根據(jù)判斷結(jié)果通過使能信號(hào)(EN)調(diào)用Mask或Huffman進(jìn)行相應(yīng)的解壓縮實(shí)現(xiàn)，由于本文的壓縮算法為2次壓縮，因此需要Mbuffer對(duì)中間數(shù)據(jù)進(jìn)行暫存，OutputBuffer進(jìn)行解壓后的數(shù)據(jù)存儲(chǔ).

Fig. 12 External decode circuit圖12 解壓縮外部電路

Fig. 13 Internal decode circuit圖13 解壓縮內(nèi)部電路

將上述解壓縮電路與文獻(xiàn)[28-29]中的解壓縮電路進(jìn)行硬件資源使用量對(duì)比，文獻(xiàn)[28]采用了掩碼壓縮與Huffman編碼相結(jié)合的方式實(shí)現(xiàn)壓縮算法，其解壓電路所需的Slice數(shù)量為250個(gè)，針對(duì)Huffman編碼的解壓電路需要將整個(gè)Huffman樹存入硬件，從而耗費(fèi)大量的硬件資源，本文提出的MH-RLE壓縮算法對(duì)Huffman壓縮進(jìn)行了改進(jìn)，解壓電路所需Slice只占到其解壓電路所需Slice的1/3(84個(gè)).而與傳統(tǒng)的基于LZSS壓縮算法的解壓縮電路實(shí)現(xiàn)[29]占用45個(gè)Slice相比，MH-RLE解壓電路所需硬件略高，但是為了提高壓縮比，減少數(shù)據(jù)傳輸時(shí)間，在現(xiàn)有的硬件資源相對(duì)充足的前提下，以犧牲少許資源為代價(jià)來(lái)得到更快的運(yùn)行速率是值得的.

5 結(jié)論與展望

本文以RLE壓縮算法為基礎(chǔ)，提出MH-RLE配置文件壓縮算法.首先，針對(duì)優(yōu)化定長(zhǎng)RLE壓縮算法的性能，本文采用統(tǒng)計(jì)方式對(duì)測(cè)試文件進(jìn)行統(tǒng)計(jì)，以理論計(jì)算的方式選擇出最優(yōu)的壓縮元長(zhǎng)度m與計(jì)數(shù)長(zhǎng)度n.然后，針對(duì)定長(zhǎng)壓縮算法計(jì)數(shù)部分“0”占位的缺憾，采用Huffman編碼方式對(duì)計(jì)數(shù)表示部分進(jìn)行編碼，實(shí)現(xiàn)變長(zhǎng)H-RLE壓縮算法.本文依據(jù)壓縮元連續(xù)分布信息，選取22個(gè)編碼單位并進(jìn)行Huffman編碼，該方式的優(yōu)勢(shì)在提高壓縮率的前提下，減少解壓縮硬件消耗代價(jià).對(duì)H-RLE壓縮后的數(shù)據(jù)進(jìn)行分析，采用掩碼壓縮思想進(jìn)行2次壓縮，實(shí)現(xiàn)了最終的配置文件壓縮算法MH-RLE.仿真實(shí)驗(yàn)表明，MH-RLE壓縮算法相對(duì)于大多數(shù)配置文件壓縮算法均有較好的壓縮性能，并且更適合于Xilinx系列FPGA配置文件壓縮.MH-RLE的平均壓縮率為49.82%，相較于其他6種壓縮算法均有不同程度的提升，最多可提升12.4%.后續(xù)研究可以針對(duì)Altera系列FPGA重新設(shè)計(jì)MH-RLE壓縮算法參數(shù)，使得該算法可以對(duì)Altera系列FPGA配置文集也有較低的壓縮效率.

[1]Xilinx Inc. Expanding the all programmable SoC portfolio[EB/OL]. [2016-05-21]. http://www.xilinx.com/products/silicon-devices/soc/zynq-7000/silicon-devices/index.htm

[2]Xilinx Inc. 7 series FPGAs configurable logic block user guide,version1.8: Userguide[EB/OL].[2016-05-21]. http://china.xilinx.com/support/documentation/user_guides/ug474_7Series_CLB.pdf

[3]Altera Corporation. Configuration, design security, and remote system Upgrades in ArriaII devices[EB/OL]. 2012-07 [2016-05-21]. https://www.altera.com/content/dam/altera-www/global/en_US/pdfs/literature/hb/arria-ii-gx/aiigx_51009.pdf

[4]Vliegen J, Mentcns N, Verbauwhede I. A single-chip solution for the secure remote configuration of FPGAs using bitstream compression[C] //Proc of the 8th IEEE ReConFig. Piscataway, NJ: IEEE, 2013

[5]Tefan R. Bitstream compression techniques for Virtex 4 FPGAs[C] //Proc of the 18th IEEE FPL. Piscataway, NJ: IEEE, 2008: 323-328

[6]Tajammul M A, Jafri S M A H, Hemani A, et al. Private configuration environments (PCE) for efficient reconfi-guration, in CGRAs[C] //Proc of the 24th IEEE ASAP. Piscataway, NJ: IEEE, 2013: 227-236

[7]Inoue H, Yamada J, Yoneda H, et al. Test compression for dynamically reconfigurable processors[J]. ACM Trans on Reconfigurable Technology and Systems, 2011, 4(4): 205-210

[8]Jia Rui, Wang Fei, Chen Rui, et al. JTAG-based bitstream compression for FPGA configuration[C] //Proc of the 11th IEEE Int Conf on Solid-State and Integrated Circuit Technology. Piscataway, NJ: IEEE, 2012

[9]Wu Weiguo, Yang Zhihua, Yu Guoliang. A reconfigurable configuration compression algorithm based on contextually adaptive arithmetic coding[J]. High Technology Letters, 2011, 21(5): 443-450 (in Chinese)

(伍衛(wèi)國(guó), 楊志華, 余國(guó)良. 基于上下文自適應(yīng)算術(shù)編碼的可重構(gòu)配置信息壓縮算法[J]. 高技術(shù)通信, 2011, 21(5): 443-450)

[10]Duhem F, Muller F, Lorenzini P. Reconfiguration time overhead on field programmable gate arrays: Reduction and cost model[J]. LET Computers & Digital Techniques, 2012, 6(2): 105-113

[11]Abdelhadi A, Lemieux G G F. Configuration bitstream reduction for SRAM-based FPGAs by enumerating LUT input permutations[C] //Proc of the 6th IEEE ReConFig. Piscataway, NJ: IEEE, 2011: 20-26

[12]Jafri S M A H, Hemani A, Paul K, et al. Compression based efficient and agile configuration mechanism for coarse grained reconfigurable architectures[C] //Proc of the 2nd IEEE IPDPSW. Piscataway, NJ: IEEE, 2011: 290-293

[13]Qin Xiaoke, Muthry C, Mishra P. Decoding-aware compression of FPGA bitstreams[J]. IEEE Trans on Very Large Scale Integration (VLSI) Systems, 2011, 19(3): 411-419

[14]Nabina A, Nuńez-Yańez J L. Dynamic reconfiguration optimisation with streaming data decompression[C] //Proc of the 20th IEEE FPL. Piscataway, NJ: IEEE, 2010: 602-607

[15]Jordan M C, Vaidyanathan R. MU-decoders: A class of fast and efficient configurable decoders[C] //Proc of the 1st IEEE Int Symp on Parallel & Distributed. Processing. Piscataway, NJ: IEEE, 2010

[16]Liu Bo, Zhu Wanyu, Liu Yang, et al. A configuration compression approach for coarse-grain reconfigurable architecture for radar signal processing[C] //Proc of the 6th IEEE Int Conf on Cyber-Enabled Distributed Computing and Knowledge Discovery. Piscataway, NJ: IEEE, 2014: 448-453

[17]Sellers B, Heiner J, Wirthlin M, et al. Bitstream compression through frame removal and partial reconfiguration[C] //Proc of the 19th Int Conf on Field Programmable Logic and Applications. Piscataway, NJ: IEEE, 2009: 476-480

[18]Gu Haiyun, Chen Shurong. Partial reconfiguration bitstream compression for Virtex FPGAs[C] //Proc of the 1st IEEE Image and Signal Processing. Piscataway, NJ: IEEE, 2008: 183-185

[19]Beckhoff C, Koch D, Torresen J. Portable module relocation and bitstream compression for Xilinx FPGAs[C] //Proc of the 24th IEEE Int Conf on Field Programmable Logic and Applications. Piscataway, NJ: IEEE, 2014

[20]Jing Xie, Wang Yabin, Chen Liguang, et al. Fast configuration architecture of FPGA suitable for bitstream compression[C] //Proc of the 8th IEEE ASICON. Piscataway, NJ: IEEE, 2009: 126-130

[21]Xu Wenbo, Tian Geng, Xilinx FPGA: Development and Application[M]. 2nd ed. Beijing: Tsinghua University Press, 2012: 85-102 (in Chinese)

(徐文波, 田耘. Xilinx FPGA開發(fā)實(shí)用教程[M]. 2版. 北京: 清華大學(xué)出版社, 2012: 85-102)

[22]Delorme J, Nafkha A, Leray P, et al. New OPBHWICAP interface for realtime Partial reconfiguration of FPGA[C] //Proc of the 4th IEEE ReConFig. Piscataway, NJ: IEEE, 2009: 386-391

[23]Xilinx Inc. System ACE configuration solution for Xilinx FPGAs,version3.0.1[EB/OL]. (2007-12-17)[2016-05-21]. http://china.xilinx.com/support/documentation/white_papers/wp151.pdf

[24]Hemnath P, Prabhu V. Compression of fpga bitstreams using improved rle algorithm[C] //Proc of the 2nd IEEE Int Conf on Information Communication and Embedded Systems. Piscataway, NJ: IEEE, 2013: 834-839

[25]Xilinx Inc.Vivado design suite user guide embeded processor hardware design[EB/OL]. (2007-12-17)[2016-05-21]. http://china.xilinx.com/support/documentation/sw_manuals/xilinx2015_4/ug898-vivado-embedded-design.pdf

[26]Xilinx Inc. Xilinx FPGA configuration details.[EB/OL].[2016-05-21]. http://www.eefocus.com/sxl630828191/blog/12-12/290582_7f03c.html (in Chinese)

(Xilinx. Xilinx FPGA配置細(xì)節(jié)詳解[EB/OL].[2016-05-21]. http://www.eefocus.com/sxl630828191/blog/12-12/290582_7f03c.html)

[27]Department of Computer Science in University of Erlangen Nuremberg. Design methodology for embedded systems made upon small networks of hardware reconfigurable nodes and connections[EB/OL]. [2016-05-21]. http://www.reconets.de/bitstreamcompression/

[28]Seong S W, Mishra P. Bitmask-based code compression for embedded systems[J]. IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(4): 673-685

[29]Koch D, Beckhoff C, Teich J. Bitstream decompression for high speed FPGA configuration from slow memories[C] //Proc of the 6th IEEE FPT. Piscataway, NJ: IEEE, 2008: 161-168