一種新型的FPGA配置位流壓縮算法

王 馳，王 健，楊 萌，來(lái)金梅

(復(fù)旦大學(xué)專(zhuān)用集成電路與系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，上海201203)

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

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

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

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

1 維度壓縮算法

1.1 位流特征

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

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

圖1 8選1 MUX MOS級(jí)電路結(jié)構(gòu)圖Fig.1 MOS-level schematic of 8 to 1 MUX

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

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

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

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

圖2 資源利用率和SRAM翻轉(zhuǎn)率的關(guān)系圖Fig.2 Relationship between resource utilization and SRAM overturn ratio

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

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

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

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

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

1.2 編碼方法

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

圖4 采用單進(jìn)編碼的前綴編碼樹(shù)Fig.4 Prefix encoding tree using unary coding

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

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

其中，r為行號(hào)，c為列號(hào)，Ls為符號(hào)長(zhǎng)度.

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

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

圖5 2維符號(hào)編碼示意圖Fig.5 Encoding of 2-D symbol

其中，Alphabet(1)為長(zhǎng)度為1的符號(hào)全集，且按照字符串升序，同時(shí)也是二進(jìn)制升序排列.返回的encode_table中各符號(hào)元素的編碼值即為該元素的下標(biāo).

研究發(fā)現(xiàn)，當(dāng)符號(hào)維度大于某個(gè)值時(shí)，壓縮效率不再明顯改善，因?yàn)榉?hào)出現(xiàn)頻次較低，且編碼CR不高，因此沒(méi)有必要對(duì)維度超過(guò)該值的符號(hào)進(jìn)行編碼.我們將停止編碼的起始維度稱(chēng)為維度編碼的壓縮閾值，在實(shí)驗(yàn)結(jié)果中我們會(huì)給出T對(duì)CR造成的影響.

1.3 壓縮效率

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

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

因此，CR可以表示為CR=E/Ls.可見(jiàn)，對(duì)于同一個(gè)位流來(lái)說(shuō)，T和Ls的選擇會(huì)對(duì)CR產(chǎn)生影響，并且CR的值不小于1/Ls.

2 結(jié)果

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

2.1 符號(hào)長(zhǎng)度

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

圖6 符號(hào)長(zhǎng)度的選取對(duì)CR的影響Fig.6 Symbol length's effect on CR

2.2 壓縮閾值

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

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

2.3 和LZSS比較

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

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

3 結(jié)論

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