王 馳，王 健，楊 萌，來金梅

(復旦大學專用集成電路與系統(tǒng)國家重點實驗室，上海201203)

現(xiàn)場可編程門列陣(Field Programmable Gate Array，F(xiàn)PGA)是由可編程功能塊(Configurable Logic Block，CLB)、可編程互聯(lián)單元以及可編程輸入輸出單元組成的模塊陣列.為了滿足應用電路日益復雜的資源和性能需求，F(xiàn)PGA的CLB陣列規(guī)模不斷擴大，并越來越多地使用具有某些特定功能的可編程知識產(chǎn)權(Intellectual Property，IP)核來取代CLB實現(xiàn).在這樣的發(fā)展趨勢下，F(xiàn)PGA中的靜態(tài)隨機存儲單元(Static Random Access Memory，SRAM)以及配置位流中需要承載的配置信息隨之增多［1］，由此人們提出了位流壓縮的概念，即先對原有位流文件進行無損壓縮后存儲，下載時再由解壓縮電路還原后傳送給編程下載模塊.壓縮FPGA的配置位流能夠有效減少其存儲空間和下載時間，這在芯片規(guī)模和密度日益增大的今天變得更加具有研究和應用價值.在一些對存儲器要求較為苛刻的環(huán)境下，例如航空電子領域，較小存儲需求意味著更低的存儲器成本和更強的魯棒性.同時，位流壓縮還能減少FPGA配置時間.由于從存儲器中讀取位流數(shù)據(jù)的速度相對較慢，而解壓縮過程使用硬件實現(xiàn)，速度很快，因此位流的傳輸時間才是構成配置性能的瓶頸.壓縮后的位流數(shù)據(jù)量減少，意味著位流文件的傳輸時間減少，從而減少了整體的配置時間.

目前所提出的位流壓縮算法均基于已有的文本壓縮算法.Huffman編碼［2］以及算術編碼［3］是基于統(tǒng)計模型的壓縮方法，根據(jù)符號出現(xiàn)的統(tǒng)計頻率生成編碼樹，在解壓縮時除了需要傳輸壓縮后的位流外還應提供編碼樹信息.LZ77/LZSS壓縮算法［4］以滑動窗口數(shù)據(jù)作為待壓縮數(shù)據(jù)的字典，將待壓縮數(shù)據(jù)編碼成字典窗口位置、長度表示的碼字.因為LZ77/LZSS能夠獲得可觀的壓縮比，且解壓縮硬件實現(xiàn)也不復雜，所以被公認為具有實用價值的算法.例如Xilinx的System ACE MPM配置解決方案已采用LZ77算法，并在配置電路中嵌入了相應的解壓縮模塊［5］.文獻［6］針對Virtex-4(V4)FPGA位流［7］，對Huffman編碼、算術編碼以及LZSS的壓縮效率做了一些比較.也有人嘗試將多種算法結合以提高壓縮效率，例如文獻［8］嘗試將LZSS與Run-length編碼相結合，文獻［9］嘗試將LZ與Golomb編碼相結合.

和普通文本不同，由于陣列的重復特性，位流的排布也會呈現(xiàn)一些規(guī)律性，若加以利用可以有效改善原有壓縮效率.文獻［8］和［10］均以幀為位流的劃分單位，分析了幀與幀之間的相似程度，由此發(fā)現(xiàn)相似幀擺放在一起可以改善位流的壓縮效率，從而提出了各自的幀重排算法.文獻［11］同樣利用了位流規(guī)律性，采用了BMC+RLE算法，在字典匹配時使用合適的掩碼，從而增加了壓縮時的統(tǒng)計字典的匹配命中率.文獻［12］發(fā)現(xiàn)位流中約95%的數(shù)據(jù)為0，因此采用RLE編碼對重復0數(shù)據(jù)進行具有針對性的壓縮.壓縮比(Compression Ratio，CR)為壓縮后位流大小占原始位流大小的百分比，是衡量壓縮算法的主要指標之一，然而具體采用何種壓縮算法還應當充分考慮解壓縮復雜程度和的硬件消耗.

本文對V4系列FPGA位流中存在的局部稀疏特性做了一些分析，并在此基礎上提出一種新型壓縮算法——符號維度壓縮算法(Symbol Dimension Compression，SDC)，對出現(xiàn)頻次較高的少1符號進行壓縮編碼，并對SDC壓縮效率做了相應的數(shù)學分析.SDC的解碼算法十分簡單，易于硬件實現(xiàn).并通過實驗分析了符號長度、壓縮閾值以及資源利用率對本文算法CR的影響，發(fā)現(xiàn)符號長度及壓縮閾值合適的選值能夠獲得較為理想的結果.同時本文還與另外一種實用的位流壓縮算法LZSS算法進行了比較，發(fā)現(xiàn)壓縮效率普遍提高了8%～12%.

1 維度壓縮算法

1.1 位流特征

雖然FPGA中的可配置資源理論上能夠工作在2n(n為控制該資源的SRAM個數(shù))個狀態(tài)，但其實際工作狀態(tài)只會有一種，因此配置必然具有一定的局部性，體現(xiàn)在兩方面:(1)需要配置的單元的分布存在局部性.以CLB的一個邏輯片(slice)為例，雖然能夠實現(xiàn)多種功能，如5輸入以內(nèi)任意組合或時序邏輯、16比特或32比特隨機存儲器(Random Access Memory，RAM)或移位寄存器、移位鏈邏輯等，但實際工作時大部分情況下只會用到這其中的某一項功能，其他可配置單元處于“閑置”狀態(tài).(2)同一配置單元相關SRAM的配置也存在局部性.如一個8選1的多路選擇器(Multiplexer，MUX)可能的MOS結構如圖1所示，該MUX的選通路徑由10個SRAM控制.假設默認上電時SRAM的初始值使得所有MOS管均處在關斷狀態(tài)，當需要選通一個路徑時，只需要翻轉兩個SRAM值便能使其導通，也就是說只有少數(shù)SRAM需要重新確定配置值，而其他SRAM處在上電默認狀態(tài)即可.

實際上，F(xiàn)PGA可以看成是以MUX為基本可配置單元構成的復雜可配置電路.例如，配置邏輯片中4輸入查找表(Look-Up Table，LUT)本質上就是一個16選1的MUX，而其他互聯(lián)路徑或數(shù)據(jù)路徑的選擇同樣是以MUX來實現(xiàn).FPGA位流由0、1比特組成，其中配置部分的每一個比特對應FPGA中的一個SRAM，因此SRAM翻轉分布的局部性特征必然會反映到位流中.

圖1 8選1 MUX MOS級電路結構圖Fig.1 MOS-level schematic of 8 to 1 MUX

Xilinx公司V4作為典型的現(xiàn)代商用FPGA芯片，其電路結構具有相當?shù)拇硇?因此，本文選用V4系列FPGA的位流作為實驗對象.即使資源利用率使用達到94%，V4位流中需要由默認值翻轉的SRAM數(shù)量也不到總數(shù)的7%，如圖2所示.

從圖2中還可以看出，SRAM翻轉率和資源利用率呈現(xiàn)一定的正相關性.資源利用率越高，需要配置的SRAM也就越多.

為了驗證位流中存在的局部性，對V4若干位流進行了統(tǒng)計分析，發(fā)現(xiàn)了一些共性，這里以rsdecode位流為例.我們先對原二進制位流按照一定的比特長度進行打包后轉換成符號流，這里我們分別選取符號長度Ls分別為8，16，24.V4位流以0為默認值，我們將符號中含1的個數(shù)稱為符號的維度Ds.通過分析這些符號出現(xiàn)的頻率，我們得到圖3的統(tǒng)計結果，并發(fā)現(xiàn):

(1)符號Ds越高，出現(xiàn)頻率往往越小;

圖2 資源利用率和SRAM翻轉率的關系圖Fig.2 Relationship between resource utilization and SRAM overturn ratio

(2)0維符號的出現(xiàn)頻率遠大于其他維度符號;

(3)當Ds大于某值之后，符號的出現(xiàn)頻率不再顯著，如Ls=8，當Ds＞2后符號出現(xiàn)頻率接近于0;

(4)Ds越大，0維符號的出現(xiàn)頻率會越小.

圖3 不同維度符號的頻率分布Fig.3 Frequency distribution of symbols with different dimensions

上面的發(fā)現(xiàn)表明，在位流中確實存在很明顯的局部稀疏性質，并且少1符號出現(xiàn)的頻次占符號總數(shù)較大比重，這為之后的符號維度壓縮算法提供了實際的統(tǒng)計依據(jù).

1.2 編碼方法

Huffman編碼已經(jīng)被證明為最優(yōu)的壓縮編碼方法［2］，但若要將其應用到位流壓縮中，不僅需要大量統(tǒng)計符號頻率，解壓縮時解壓縮電路還需要解析Huffman樹，因此實現(xiàn)復雜度較高，且解析過程需要多個時鐘周期，制約解壓縮電路的性能.本文借鑒了Huffman的編碼思想，即使用較少的比特來表示出現(xiàn)頻次較高的符號.但和Huffman編碼不同的是，根據(jù)上一節(jié)中分析得出的局部性結論，我們先將符號按維度劃分后再用單進編碼方法(Unary Coding)對這些類別進行前綴編碼，其編碼樹如圖4所示.單進編碼為霍夫曼編碼的一種特殊情況，當元素概率分布呈現(xiàn)為P(n)=2－n時其壓縮效率達到最優(yōu).圖3中已經(jīng)呈現(xiàn)出符號頻率分布一定的指數(shù)趨勢，且單進編碼的編碼樹結構固定，可直接固化在解壓縮電路中，故本文加以采用.

圖4 采用單進編碼的前綴編碼樹Fig.4 Prefix encoding tree using unary coding

圖4中，S(n)={s|s∈A，D(s)=n}，其中A為符號全集，D(s)為符號s的維度.我們可以從比特值為1的位置出發(fā)對原碼進行編碼.為了分析方便，我們暫時取符號長度為8，表1為具體編碼方式.S(0)不需要進行額外編碼.S(1)的1可能存在于8個位置上，因此需要3比特來對位置進行編碼.S(2)有兩個1，因此1的位置是一個二維坐標，同理對于n≥1的S(n)，都可以表示為n維向量，這也是為什么稱1的個數(shù)為維度的原因.S(2)可以表示成圖5那樣的二維矩陣，其中行號為第一個出現(xiàn)的1的位置，列號為第2個出現(xiàn)的1的位置，劃斜杠的方格表示不可能存在的情況.在這種情況下，S(1)有28種可能，因此需要用5比特來進行編碼.其具體編碼已經(jīng)按照一定順序標注在圖5的方框中.我們可以推導出，位置編號p可以直接表示為

表1 壓縮編碼示意Tab.1 Example of compression encoding

其中，r為行號，c為列號，Ls為符號長度.

解碼時，同樣可以通過p以及圖5提供的查找表迅速還原成原碼，可以直接通過簡單的組合邏輯來實現(xiàn)，和LZSS的解碼電路［13］相比更加簡單.

對于更高維度的符號，同樣可以利用1位置組成的向量進行編碼.更一般地，n維符號(n≥1)編碼方法可以表示為如下偽代碼:

圖5 2維符號編碼示意圖Fig.5 Encoding of 2-D symbol

其中，Alphabet(1)為長度為1的符號全集，且按照字符串升序，同時也是二進制升序排列.返回的encode_table中各符號元素的編碼值即為該元素的下標.

研究發(fā)現(xiàn)，當符號維度大于某個值時，壓縮效率不再明顯改善，因為符號出現(xiàn)頻次較低，且編碼CR不高，因此沒有必要對維度超過該值的符號進行編碼.我們將停止編碼的起始維度稱為維度編碼的壓縮閾值，在實驗結果中我們會給出T對CR造成的影響.

1.3 壓縮效率

維度壓縮算法本質上是一種熵編碼.其熵值可以表示為

其中，Ls為符號的原碼長度，n為維度，LW(n)為符號壓縮碼長度，即前綴碼和編碼長度之和，Rs(n)為符號出現(xiàn)的頻率.假設T為編碼閾值，那么

因此，CR可以表示為CR=E/Ls.可見，對于同一個位流來說，T和Ls的選擇會對CR產(chǎn)生影響，并且CR的值不小于1/Ls.

2 結果

實驗在VS2010開發(fā)環(huán)境下采用C++編寫主要壓縮算法.所用測試用例均來源于opencores等開源網(wǎng)站.

2.1 符號長度

研究發(fā)現(xiàn)，Ls的選取既不能過小，也不能過大.Ls過小，前綴碼加上壓縮編碼的長度很容易就超過Ls，起不到壓縮的作用.Ls過大，Ps(0)會相應減小，從而反作用于CR.因此需要通過實驗數(shù)據(jù)來選取一個較優(yōu)解.本文選取不同的Ls對測試用例的位流進行壓縮，圖6給出了其中6個不同資源利用率的結果.可以看出，在Ls=22時，rsdecode的CR為32.2%，在所有不同Ls對應的所有CR值中最小，其余例子也都在Ls=22時呈現(xiàn)最低CR.因此，對于V4位流來說，當Ls為22時整體壓縮效率最理想.

圖6 符號長度的選取對CR的影響Fig.6 Symbol length's effect on CR

2.2 壓縮閾值

符號的維度越高，表示一個符號的坐標需要信息也就越多，因而會使得它的壓縮編碼的效率變低.同時，由于維度高的符號出現(xiàn)頻率較低，因此高維度符號的壓縮對整體壓縮的貢獻并不大.我們在Ls分別為12，16，20時選用不同壓縮閾值對測試用例進行壓縮，得到圖7.可以看到當T大于某個值時，所有例子的壓縮效率已經(jīng)不再隨T的增大而有明顯改善.如Ls=12，T＞2后壓縮效率沒有明顯變化.

圖7 壓縮閾值T對CR的影響Fig.7 Compression threshold's effect on CR

2.3 和LZSS比較

LZSS算法因具有可觀的壓縮比和簡單的解壓縮過程，被公認為是具有實用價值的壓縮算法［11］.將SDC算法和LZSS算法的壓縮效率進行了比較，得到圖8的結果，可以看出，在rsdecode例子中SDC算法的CR比LZSS低8%，而其他例子的CR均低于LZSS算法CR 12%左右.不同資源利用率的位流文件大小是相同的，因此，資源利用率越低位流中的冗余信息就越多.SDC算法能夠有效抑制這些冗余信息，從圖8中還可以看出隨著資源利用率降低SDC壓縮效率也在逐步提高.這是因為在資源利用率不高的情況下SRAM翻轉率變低，因而Ps(0)會相應增大，更有利于壓縮.

圖8 SDC和LZSS壓縮效率的比較Fig.8 CR comparison between SDC and LZSS

3 結論

通過對V4 FPGA若干位流的統(tǒng)計分析，首次發(fā)現(xiàn)了其中存在的局部稀疏特性，并由此提出了一套新型的壓縮方法，根據(jù)符號中1的個數(shù)對符號進行分類和編碼，為位流壓縮提供了一種全新的思路.本文分別對符號長度、壓縮閾值以及資源利用率對SDC壓縮效率可能產(chǎn)生的影響進行了實驗分析及論證，得出如下結論:(1)符號長度太大太小壓縮效率均不理想，其值可以通過統(tǒng)計分析來進行選取;(2)當壓縮閾T值大于某值時，壓縮效率不再隨著T的增大得到明顯改善，因此可以僅對維度在以內(nèi)的符號進行編碼;(3)SDC能夠有效抑制低資源利用率時產(chǎn)生的冗余信息.此外，本文算法相應的解壓縮算法比較簡單，易于硬件實現(xiàn).

［1］Sellers B，Heiner J，Wirthlin M，et al.Bitstream compression through frame removal and partial reconfiguration［C］∥Field Programmable Logic and Applications.Prague，Czech Republic:IEEE Press，2009:476-480.

［2］Huffman D A.A method for the construction of minimum redundancy codes［J］.Proc IRE，1952，40(9):1098-1101.

［3］Witten I H，Neal R M，Cleary JG.Arithmetic Coding for Data Compression［J］.Communications of the ACM，1987，30:520-540.

［4］Ziv J，Lempel A.A universal algorithm for sequential data compression［J］.IEEE Transactions on Information Theory，1977，23(3):337-343.

［5］Xilinx Corporation.Xilinx FPGA Configuration Data Compression and Decompression［EB/OL］.(2003-01-01)［2014-01-01］.http:∥www.cs.york.ac.uk/rts/docs/Xilinx-datasource-2003-q1/whitepapers/wp152.pdf.

［6］Li Z，Hauck S.Configuration Compression for Virtex FPGAs［C］∥Field-Programmable Custom Computing Machines.California，USA:IEEE，2001:147-159.

［7］Xilinx Corporation.Virtex-4 FPGA Configuration User Guide［EB/OL］.(2008-04-01)［2014-01-01］.http:∥www.xilinx.com/support/documentation/user_guides/ug070.pdf.

［8］Hauck S，Wilson W D.Runlength compression techniques for FPGA configurations［C］∥Field-Programmable Custom Computing Machines.California，USA:IEEE，1999:286-287.

［9］Mao J，Zhou H，Ye H，et al.FPGA bitstream compression and decompression using LZ and golomb coding［C］∥Proceedings of the ACM/SIGDA international symposium on Field programmable gate arrays.California，USA:IEEE Press，2013:265-265.

［10］Pan J H，Mitra T，Wong W F.Configuration bitstream compression for dynamically reconfigurable FPGAs［C］∥International Conference on Computer-Aided Design.California，USA:IEEE Press，2004:766-773.

［11］Qin X，Muthry C，Mishra P.Decoding-Aware Compression of FPGA Bitstreams［J］.IEEE Transactions on Very Large Scale Integration Systems，2011，19(3):411-419.

［12］Jia R，Wang F，Chen R.JTAG-based bitstream compression for FPGA configuration［C］∥Solid-State and Integrated Circuit Technology.Xi'an，China:IEEE，2012:1-3.

［13］Huebner M，Ullmann M，Weissel F，et al.Real-time configuration code decompression for dynamic FPGA selfreconfiguration［C］∥Parallel and Distributed Processing Symposium.New Mexico，USA:IEEE，2004:26-30.