蘇 迪，楊 帆，陶 俊，曾 璇

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

長期以來，片外存儲器的訪問速度難以滿足計算機處理器的需求，由此造成的內(nèi)存墻問題極大地制約了處理器的性能[1].為了緩解內(nèi)存墻問題，處理器芯片提供了高速訪問數(shù)據(jù)的高速緩存，高速緩存的訪問速度一般比片外存儲器的訪問速度快兩個數(shù)量級[2].然而，受限于制造成本等因素，高速緩存的存儲空間有限.計算機體系結(jié)構(gòu)的研究者們提出在高速緩存中使用硬件數(shù)據(jù)壓縮單元，以提升高速緩存的有效存儲空間.基于這個構(gòu)想，眾多緩存壓縮技術(shù)應(yīng)運而生.有些緩存壓縮算法著重針對特定的數(shù)據(jù)類型，比如計算機應(yīng)用程序在運行過程中產(chǎn)生的零數(shù)據(jù)[3]和重復(fù)數(shù)據(jù)[4]等.此類算法硬件開銷小，但是無法壓縮非特定類型的數(shù)據(jù).另一些緩存壓縮算法致力于提升數(shù)據(jù)的壓縮比，利用字典編碼[5]和熵編碼[6]技術(shù)降低數(shù)據(jù)冗余度，代價是復(fù)雜的硬件結(jié)構(gòu)和更長的壓縮/解壓縮延時.在眾多壓縮算法當(dāng)中，BDI(Base-Delta-Immediate)壓縮算法[7]利用高速緩存行(cache line)內(nèi)數(shù)據(jù)差異小的特點，在數(shù)據(jù)壓縮比、硬件開銷以及壓縮/解壓延時之間取得了良好的折衷.

與計算機處理器類似，現(xiàn)代的現(xiàn)場可編程門陣列(Field Programmable Gate Array, FPGA)也采用多層次的存儲結(jié)構(gòu).如圖1所示，F(xiàn)PGA芯片集成了大量的塊隨機存取存儲器(Block Random Access Memory, BRAM)作為片內(nèi)高速緩存.由于成本與功耗等方面的限制，F(xiàn)PGA芯片上的BRAM空間有限.所以，F(xiàn)PGA片外存儲器有限的帶寬和高訪問延時也成為制約FPGA應(yīng)用的性能瓶頸之一.而數(shù)據(jù)壓縮技術(shù)能夠有效地緩解FPGA的這一性能瓶頸.

圖1 典型的FPGA板結(jié)構(gòu)Fig.1 A typical FPGA application board

以往對FPGA壓縮算法的研究主要考慮提升FPGA片外存儲器和高速緩存之間的帶寬.為了追求高數(shù)據(jù)壓縮比，許多研究者將各種復(fù)雜的數(shù)據(jù)壓縮算法應(yīng)用到FPGA上： Sukhwani在高速串行計算機擴展總線標(biāo)準(zhǔn)(Peripheral Component Interface Express, PCIE)接口的FPGA板上實現(xiàn)了842B算法，極大地提升了FPGA的吞吐量[8]；Guan使用混合熵編碼算法壓縮卷積神經(jīng)網(wǎng)絡(luò)(Convolutional Neural Network, CNN)參數(shù)加速數(shù)據(jù)傳輸速率[9].然而，增加有效帶寬是以犧牲大量硬件資源和數(shù)據(jù)訪問速度為代價的.某些圖像/視頻處理、高性能計算和神經(jīng)網(wǎng)絡(luò)等應(yīng)用對于計算過程的中間結(jié)果有強實時性的需求，復(fù)雜壓縮算法造成的高延時可能會抵消提升有效帶寬所帶來的收益.

另一個有效提升FPGA性能的策略是把更多數(shù)據(jù)緩存在FPGA的高速緩存之中，從而有效降低訪問片外存儲器的頻率.目前，我們還沒有發(fā)現(xiàn)高速緩存壓縮技術(shù)應(yīng)用于FPGA的相關(guān)研究.本文基于BDI算法，提出了一種新穎的適用于FPGA的快速在線數(shù)據(jù)壓縮的頁式高速緩存(Page Cache, PC)壓縮方法.與計算機處理器相比，F(xiàn)PGA訪問數(shù)據(jù)的粒度更為粗糙，訪問模式也更為規(guī)則.比如，許多FPGA的圖像應(yīng)用訪問數(shù)據(jù)的粒度是一行或者64×64的像素塊[10].針對這一粗粒度的特點，我們提出頁式高速緩存壓縮算法(Page Cache Compression, PCC)，將數(shù)據(jù)適當(dāng)切割為多個數(shù)據(jù)段(segment)，并確保每個數(shù)據(jù)段能被壓縮為標(biāo)準(zhǔn)大小的高速緩存行，從而避免其他緩存壓縮技術(shù)壓縮數(shù)據(jù)后導(dǎo)致的內(nèi)存碎片化問題.此外，我們還提出了簡化的頁式內(nèi)存管理系統(tǒng)，以解決以往新舊數(shù)據(jù)替換時存儲空間不足的問題.實驗結(jié)果表明，本文提出的頁式高速緩存壓縮算法消耗硬件資源少，壓縮/解壓縮延時低，能夠有效地壓縮圖像和矩陣數(shù)據(jù)，從而提升FPGA應(yīng)用的性能.

1 高速緩存壓縮算法背景介紹

用于片上高速緩存的壓縮算法有3點基本要求： 首先，壓縮/解壓縮的速度要足夠迅速，避免過高的延時等待抵消壓縮數(shù)據(jù)所獲得的收益；其次，壓縮算法的硬件開銷必須小于壓縮數(shù)據(jù)所節(jié)省的硬件資源，并且不會產(chǎn)生高功耗；最后，為了保證數(shù)據(jù)壓縮前后的一致性，壓縮算法必須為無損壓縮.

作為典型的片上緩存壓縮算法，BDI算法[7]的原理簡單，易于硬件實現(xiàn)，充分利用了高速緩存行內(nèi)數(shù)值動態(tài)范圍小的特點，使用基準(zhǔn)值和差值表示高速緩存行，能夠?qū)崿F(xiàn)對數(shù)據(jù)的有效壓縮，因此得到了較為廣泛的應(yīng)用.圖2展示了2類BDI算法壓縮和解壓縮的流程，每個高速緩存行由4個8bits的數(shù)據(jù)組成.以圖2(a)為例，BDI首先選擇高速緩存行的第1個數(shù)據(jù)作為基準(zhǔn)值，再將高速緩存行中所有數(shù)據(jù)通過減法器與基準(zhǔn)值做差，得到4bits長度的差值，基準(zhǔn)值和差值共同構(gòu)成壓縮后的數(shù)據(jù).壓縮后數(shù)據(jù)僅占用3個字節(jié)(Byte, B)的空間.解壓縮數(shù)據(jù)的過程即壓縮數(shù)據(jù)的逆過程，解壓縮操作簡單，只需要使用加法器將基準(zhǔn)值與差值相加即可還原初始數(shù)據(jù).

為了提升壓縮效率，差值的數(shù)據(jù)位寬在同一高速緩存行內(nèi)相同，但是在不同高速緩存行之間可能不一致.例如，圖2(a)高速緩存行中的差值數(shù)據(jù)位寬為4bits，圖2(b)高速緩存行的差值位寬僅為2bits，后者的壓縮效率高于前者.需要特別注意的是，差值的最高位為符號位，圖2(b)中最后一個差值“10”代表-2.

BDI算法是專門為計算機處理器開發(fā)的算法，對于高速緩存的在線數(shù)據(jù)，壓縮效果良好.但是，由于FPGA與計算機處理器訪問數(shù)據(jù)粒度和模式的差異，在FPGA內(nèi)實現(xiàn)高速緩存壓縮技術(shù)有以下兩點挑戰(zhàn)：

圖2 BDI算法壓縮/解壓縮的原理Fig.2 Mechanism for BDI algorithm compression and decompression

其一，內(nèi)存碎片化問題.內(nèi)存碎片化問題并非FPGA獨有，采用壓縮算法的計算機高速緩存同樣面臨著這一問題.高速緩存行被壓縮后，節(jié)省的存儲空間可能無法使用.圖2中，高速緩存行壓縮極限為1B的基準(zhǔn)值和4個1bit的差值，因為壓縮后數(shù)據(jù)長度以B計量，所以壓縮后高速緩存行最短為2B.以圖2(a)為例，壓縮高速緩存行所節(jié)省的1B空間無法緩存最小為2B高速緩存行.零散的高速緩存行空間無法被利用，這將會嚴重降低實際數(shù)據(jù)壓縮的效率.此外，普通高速緩存內(nèi)，每個高速緩存行都有一個對應(yīng)的標(biāo)簽，標(biāo)簽記錄了相應(yīng)高速緩存行是否有效等基本信息，標(biāo)簽與高速緩存行是一對一的關(guān)系.但是采用高速緩存壓縮技術(shù)后，原來一個標(biāo)準(zhǔn)高速緩存行大小的空間內(nèi)可能存在多組壓縮后的數(shù)據(jù).以圖2(b)為例，4B 的高速緩存行壓縮后只需要2B就可以存儲，剩下的2B的可用于存儲另外一個壓縮后的高速緩存行，因此在一個高速緩存行內(nèi)可能存儲了2個壓縮后的高速緩存行.已有的計算機高速緩存壓縮算法工作[2-5,7]提出的解決方案是使用2個或更多的標(biāo)簽映射同一個高速緩存行空間，即標(biāo)簽與高速緩存行是多對一的關(guān)系.除此以外，標(biāo)簽內(nèi)還必須增加壓縮數(shù)據(jù)的信息，這將產(chǎn)生額外的標(biāo)簽開銷.

其二，新舊數(shù)據(jù)替換問題.考慮到FPGA應(yīng)用程序計算產(chǎn)生的新數(shù)據(jù)的大小可能與舊數(shù)據(jù)不一致，舊數(shù)據(jù)被更新時，原來舊數(shù)據(jù)所占據(jù)的存儲空間可能無法緩存全部的新數(shù)據(jù)，必須要分配更大的空閑存儲空間給新數(shù)據(jù).當(dāng)且僅當(dāng)新數(shù)據(jù)被壓縮后的大小與舊數(shù)據(jù)完全一致時，原有存儲空間才能被充分利用.針對這一問題，在計算機處理器的內(nèi)存管理架構(gòu)中，采用分頁機制把程序所需要的內(nèi)存空間切分為大小均等的頁，將應(yīng)用程序的數(shù)據(jù)離散地裝載入內(nèi)存中，才能夠充分利用存儲空間.

2 頁式高速緩存的設(shè)計與操作

針對FPGA應(yīng)用中，現(xiàn)有緩存壓縮技術(shù)效率不高的問題，本文提出了粗粒度訪問的頁式高速緩存壓縮技術(shù).為了提升高速緩存的有效容量，這一算法在BDI算法的基礎(chǔ)上進行了兩點改進： 一是縮小數(shù)據(jù)壓縮的基本單元，不再以高速緩存行作為基本壓縮單元，更小的壓縮單元能夠減少單元內(nèi)部數(shù)據(jù)差異從而提升壓縮效率，有效緩解內(nèi)存碎片問題；二是改變數(shù)據(jù)存儲的方式，壓縮信息標(biāo)簽存入高速緩存行中，實現(xiàn)壓縮信息標(biāo)簽的動態(tài)化存儲，避免額外開辟固定大小的壓縮信息標(biāo)簽存儲區(qū)域.

2.1 頁式高速緩存的設(shè)計

圖3 頁式高速緩存的主要結(jié)構(gòu)Fig.3 Main structure of page cache

圖3是頁式高速緩存的主要結(jié)構(gòu).壓縮和解壓縮模塊受頁式內(nèi)存管理單元控制，頁式內(nèi)存管理單元根據(jù)FPGA應(yīng)用的需求，通過壓縮/解壓縮模塊在高速緩存中存/取數(shù)據(jù).

壓縮模塊將原始數(shù)據(jù)切割壓縮為若干個標(biāo)準(zhǔn)的高速緩存行.頁式內(nèi)存管理單元記錄緩存數(shù)據(jù)的標(biāo)簽，并為每個高速緩存行分配高速緩存的地址，同時控制所有涉及高速緩存的操作.FPGA應(yīng)用在運行過程中，需要讀取數(shù)據(jù)時，向頁式內(nèi)存管理單元發(fā)起請求，頁式內(nèi)存管理單元響應(yīng)FPGA應(yīng)用的請求，返回數(shù)據(jù).FPGA應(yīng)用需要向高速緩存中寫入數(shù)據(jù)時，頁式內(nèi)存管理單元提供緩存數(shù)據(jù)的地址.不過，頁式內(nèi)存管理單元并不參與FPGA應(yīng)用向片外存儲器寫回數(shù)據(jù)的過程，即FPGA應(yīng)用到片外存儲器存在一條直接單向通路.以FPGA應(yīng)用向頁式內(nèi)存管理單元請求數(shù)據(jù)的過程為例.頁式內(nèi)存管理單元首先查詢請求的數(shù)據(jù)是否存在于高速緩存中，若存在，則向解壓縮模塊提供高速緩存的地址，請求的數(shù)據(jù)解壓縮后傳給FPGA應(yīng)用.若請求數(shù)據(jù)不存在，頁式內(nèi)存管理單元會向片外存儲器請求數(shù)據(jù)，等待數(shù)據(jù)返回.需要注意的是，返回的數(shù)據(jù)存在兩條通路： 一是直接返回給FPGA應(yīng)用，從而減少FPGA應(yīng)用的等待時間；二是被壓縮模塊壓縮后緩存入高速緩存中.

因為很多FPGA應(yīng)用與圖像相關(guān)，常見圖像數(shù)據(jù)的通道數(shù)據(jù)位寬為8bits，所以本文設(shè)計了適用于數(shù)據(jù)位寬為8bits的頁式高速緩存.表1展示了8bits數(shù)據(jù)的4種壓縮模式以及對應(yīng)的編碼.“B+Δ2”代表數(shù)據(jù)壓縮后由基準(zhǔn)值B和位寬2bits的差值Δ組成，“B+Δ4”和“B+Δ6”的差值位寬分別是4bits和6bits.“NoCompr”意味著該數(shù)據(jù)塊無法使用頁式高速緩存壓縮算法進行壓縮.數(shù)據(jù)壓縮后由壓縮后數(shù)據(jù)和壓縮模式編碼兩部分組成，壓縮后數(shù)據(jù)必須籍由壓縮模式編碼才能準(zhǔn)確還原出原始數(shù)據(jù).以圖2(a) 為例，未壓縮數(shù)據(jù)按照“B+Δ4”模式壓縮后得到壓縮后數(shù)據(jù)和壓縮模式編碼“01”(圖中未出現(xiàn))，解壓縮數(shù)據(jù)時，解壓縮模塊根據(jù)壓縮模式編碼“01”確定壓縮模式后才能對位寬為4bits的差值進行解壓縮操作.

2.2 頁式高速緩存壓縮和解壓縮操作

表1 BDI編碼模式

已有的高速緩存壓縮算法[2-7](包括BDI)通常是針對標(biāo)準(zhǔn)長度的高速緩存行進行壓縮，如果節(jié)省的存儲空間無法容納新進壓縮后的高速緩存行，高速緩存行就會產(chǎn)生內(nèi)部碎片，導(dǎo)致高速緩存有效容量減少.我們注意到，這一過程中產(chǎn)生的內(nèi)存碎片必然小于數(shù)據(jù)壓縮的基本單元.因此，在高速緩存行長度不變的情況下，縮短被壓縮數(shù)據(jù)的長度就能夠減少內(nèi)存碎片.換言之，為了減少碎片，我們可以不再把一個高速緩存行長度的數(shù)據(jù)作為數(shù)據(jù)壓縮的基本單元，而是替換為長度更短的數(shù)據(jù)(又稱為子塊)，比如八分之一高速緩存行的數(shù)據(jù).如圖4所示，我們提出的頁式高速緩存壓縮算法把FPGA應(yīng)用每次訪問的原始數(shù)據(jù)細分為多個長度相等的子塊，子塊是數(shù)據(jù)壓縮的基本單元.子塊壓縮后按順序?qū)懭敫咚倬彺嫘兄?由于原始數(shù)據(jù)的長度大于高速緩存行，所以原始數(shù)據(jù)會分散存放于多個高速緩存行中，而且高速緩存行之間的子塊數(shù)量可能不相等.宏觀上看，訪問數(shù)據(jù)被切分為長度互異的數(shù)據(jù)段，壓縮后的數(shù)據(jù)段盡可能地占滿高速緩存行的存儲區(qū)域，因此頁式高速緩存壓縮算法能夠極大地減少內(nèi)部碎片.

高速緩存壓縮算法帶來的另一個不可避免的問題是新增管理高速緩存壓縮信息的標(biāo)簽.以往的研究通常會忽略新增標(biāo)簽信息對數(shù)據(jù)壓縮效率的影響[7].但是，由于頁式高速緩存的一個高速緩存行內(nèi)包含著有多個子塊，即使每個子塊只新增2bits的壓縮信息標(biāo)簽，所造成的額外開銷也不能忽視.以64B長度的高速緩存行和4B的子塊為例，假設(shè)在最理想的情況下，所有子塊均可被壓縮為“B+Δ2”模式，即壓縮后數(shù)據(jù)長度僅為原始數(shù)據(jù)的一半，那么64B的高速緩存行能存儲32個子塊.每個高速緩存行至少要預(yù)留8B 的內(nèi)存空間存放管理壓縮信息標(biāo)簽.最極端的情況下，所有子塊均無法壓縮，即64B的高速緩存行存儲了16個未壓縮子塊，此時只需求4B的空間存儲標(biāo)簽信息，剩余的4B將會被浪費.如此之高的標(biāo)簽開銷將會嚴重影響壓縮效率，甚至可能完全抵消壓縮算法的收益.因此，我們不再單獨為壓縮信息標(biāo)簽開辟額外的存儲空間，而是把標(biāo)簽與數(shù)據(jù)存儲在一起，實現(xiàn)高速緩存行內(nèi)標(biāo)簽數(shù)量的動態(tài)化.依然以所有子塊不能被壓縮的情況為例，64B的高速緩存行至多可以存儲15組未壓縮的子塊和對應(yīng)的壓縮信息標(biāo)簽，此時僅浪費2bits存儲空間.圖4中高速緩存行的末尾存儲的是各個子塊的壓縮編碼標(biāo)簽.

圖4 原始數(shù)據(jù)壓縮和解壓縮過程Fig.4 Process for compression and decompression of originnal data

圖4展示了原始數(shù)據(jù)壓縮和解壓縮的過程.壓縮模塊由若干個相同的壓縮單元組成，解壓縮模塊與之類似.壓縮/解壓縮單元內(nèi)部構(gòu)造十分簡單，由多個減法器/加法器和多路選擇器組成，具體原理見圖1.數(shù)據(jù)壓縮過程可以分為三步： 首先，將原始數(shù)據(jù)劃分為若干個大小相等、長度為xB的子塊，如圖4中的sub1，sub2，…，subi等.然后，我們尋找最長可壓縮數(shù)據(jù)段，即至多有多少個連續(xù)子塊被壓縮后能夠恰好填滿一個高速緩存行的空間.尋找最長可壓縮數(shù)據(jù)段的過程，以64B長度的高速緩存行和4B的子塊為例，64B的高速緩存行至多能存儲32個子塊，那么至少需要32個壓縮單元同時壓縮子塊數(shù)據(jù)，這里解壓縮單元數(shù)目與同壓縮單元相同.壓縮模塊根據(jù)各個壓縮單元生成子塊的壓縮信息即可確定最長可壓縮數(shù)據(jù)段.如圖4中，最長可壓縮數(shù)據(jù)段為sub1到subi；最后，壓縮模塊把最長可壓縮數(shù)據(jù)段壓縮入高速緩存行.因為最長可壓縮數(shù)據(jù)段的每個子塊對應(yīng)一個壓縮單元，而且不同子塊的壓縮比取決于子塊內(nèi)部數(shù)據(jù)分布情況，所以子塊之間的壓縮模式可能并不相同.圖4中，sub1，sub2和subi的壓縮模式分別為“B+Δ2”，“B+Δ4”和“NoCompr”.高速緩存行存儲的數(shù)據(jù)可以分為兩個部分，壓縮后的子塊和子塊的壓縮模式編碼.需要注意的是，剩余子塊會重復(fù)壓縮過程的后兩步操作，直至所有子塊被壓縮而且寫入高速緩存中.數(shù)據(jù)解壓縮的過程相對簡單： 每個壓縮后的子塊對應(yīng)一個解壓縮單元，解壓縮單元會根據(jù)壓縮模式編碼判斷子塊應(yīng)該按照何種模式解壓縮.各子塊解壓縮后按原順序拼接即可.

圖5 不同大小子塊的頁式高速緩存的壓縮比比較Fig.5 Compression ratio comparison of page cache with different sizes of sub-blocks

影響頁式高速緩存有效容量的變量有兩個，其一是高速緩存行大小，其二是訪問數(shù)據(jù)被切分的細膩程度，即子塊的大小x.一般來說，高速緩存行的大小取決于FPGA應(yīng)用自身的需求，在本文中，我們將高速緩存行設(shè)為64B.為了更合理公正地評估頁式壓縮算法的壓縮效率，我們將壓縮算法所產(chǎn)生額外的標(biāo)簽開銷也計入壓縮后數(shù)據(jù)內(nèi)，即子塊的壓縮模式編碼.我們定義壓縮比(Compression Ratio)為壓縮前數(shù)據(jù)大小比上壓縮后數(shù)據(jù)大小，壓縮比越高，證明壓縮算法的壓縮效率越好.為了評估在相同條件下，不同大小的子塊的頁式高速緩存對數(shù)據(jù)壓縮比的影響，我們使用了3組圖像數(shù)據(jù)和3組CNN全連接層參數(shù)測試頁式高速緩存在子塊大小分別為4B，8B和16B時的壓縮比(即子塊內(nèi)數(shù)據(jù)分別為4，8和16個).如圖5所示，當(dāng)子塊的寬度為8B時，頁式高速緩存的壓縮比最高.16B長度的子塊內(nèi)部的數(shù)值波動范圍大，不利于算法壓縮.4B長度的子塊相比8B長度的子塊，標(biāo)簽數(shù)量多一倍，且長度可能過小，無法充分挖掘數(shù)據(jù)的可壓縮性.所以，我們最終選定頁式高速緩存的基本壓縮單元長度為8B，內(nèi)部的高速緩存行長度定為64B.

3 頁式內(nèi)存管理策略

圖6 頁式高速緩存的內(nèi)存管理策略Fig.6 The pattern for memory management of page cache

新舊數(shù)據(jù)替換是另一個導(dǎo)致高速緩存有效容量降低的重要問題.無論是否采用高速緩存壓縮算法，F(xiàn)PGA程序運行過程中必然會存在新舊數(shù)據(jù)長短不一致的情況.若新數(shù)據(jù)長度大于舊數(shù)據(jù)，那么舊數(shù)據(jù)原有的存儲空間無法容納新數(shù)據(jù)，一方面，我們必須為新數(shù)據(jù)尋找更大的空閑存儲區(qū)域；另一方面，被替換后的舊數(shù)據(jù)原有的存儲空間可能難以利用.在計算機操作系統(tǒng)中，分頁技術(shù)將進程劃分對應(yīng)為多個頁，并可以為進程分配不連續(xù)的物理內(nèi)存地址同時保證邏輯地址連續(xù).我們參考計算機的內(nèi)存分頁機制，采用簡化的頁式內(nèi)存管理系統(tǒng)管理頁式高速緩存的存儲空間.

如圖6，假設(shè)原始數(shù)據(jù)被劃分為3個數(shù)據(jù)段S1，S2和S3后，又被壓縮為3個高速緩存行長度的壓縮數(shù)據(jù)，即cS1，cS2，cS3.與計算機分頁技術(shù)的類似，我們不再為cS1，cS2，cS3分配連續(xù)的物理地址，而是將它們分散緩存于數(shù)據(jù)存儲區(qū)(data store)的空閑存儲空間內(nèi).但是，不連續(xù)地物理地址會給對數(shù)據(jù)讀取造成困難.因此，我們對標(biāo)簽存儲區(qū)(tag store)進行了改造.標(biāo)簽存儲區(qū)內(nèi)每一個標(biāo)簽與數(shù)據(jù)存儲區(qū)內(nèi)每一個高速緩存行是一一對應(yīng)的關(guān)系，我們在標(biāo)簽的末尾增加指向下一個標(biāo)簽的地址.圖6中，F(xiàn)PGA應(yīng)用可以通過Tag1末尾的地址跳轉(zhuǎn)到下一個標(biāo)簽Tag2.具體來說，頁式內(nèi)存管理單元獲得Tag1末尾的Tag2地址后，立即通過Tag2地址索引標(biāo)簽Tag2同時從數(shù)據(jù)存儲區(qū)提取下一個數(shù)據(jù)段cS2.依次類推，我們可以由Tag2繼續(xù)索引Tag3.需要注意的是，Tag3是最后一個標(biāo)簽，其末尾的地址無效.最終，F(xiàn)PGA應(yīng)用可以通過標(biāo)簽提供的跳轉(zhuǎn)地址，完整讀取壓縮后的數(shù)據(jù).

4 實驗結(jié)果及分析

為了評估本文提出的頁式高速緩存壓縮技術(shù)在FPGA應(yīng)用中壓縮數(shù)據(jù)的效率.我們在Xilinx VC707開發(fā)板上實現(xiàn)了頁式高速緩存，并測試了其對圖像和CNN的全連接層參數(shù)的壓縮效果.根據(jù)第2.2節(jié)中的分析，本章節(jié)實驗采用頁式高速緩存的高速緩存行長度為64B，對訪問數(shù)據(jù)的切分粒度為8B.

表2 硬件資源使用情況

表2給出了256B大小的頁式高速緩存的硬件資源使用情況.這里頁式高速緩存的容量由實際應(yīng)用的需求決定，并非定值.查找表(Look Up Table, LUT)和觸發(fā)器(Flip Flop, FF)的資源使用率約為BRAM資源使用率的六分之一，后者幾乎全部用于構(gòu)建標(biāo)簽存儲區(qū)與數(shù)據(jù)存儲區(qū).因此可以認為頁式高速緩存相較于其它普通的高速緩存額外消耗硬件資源低.需要注意的一點是，頁式高速緩存并不占用數(shù)字信號處理器(Digital Signal Processor, DSP)資源.因為基于DSP實現(xiàn)的計算單元運算速度更快，所以許多FPGA應(yīng)用中會使用大量的DSP模塊[11].為了避免占用更高效的DSP資源，頁式高速緩存的加/減法器采用效率更低的LUT實現(xiàn).

該高速緩存最高工作頻率可達150MHz，壓縮和解壓縮的延時僅為4和3個時鐘周期.

為測試頁式高速緩存壓縮算法的有效壓縮比，我們選擇了3幅常用于圖像處理應(yīng)用的典型圖像以及3組量化為8bits的CNN全連接層參數(shù)測試，結(jié)果如表3所示.頁式壓縮算法對圖像的平均壓縮比為1.47，CNN全連接層參數(shù)平均壓縮比為1.68.綜合考慮硬件開銷，壓縮和解壓縮延時以及壓縮比等3個方面的實驗數(shù)據(jù)，我們認為本文的頁式壓縮算法滿足片上高速緩存的壓縮算法的3點基本要求.

此外，我們還將頁式高速緩存與圖像處理應(yīng)用K-means結(jié)合，驗證了頁式高速緩存對K-means應(yīng)用具有加速效果.K-means聚類算法是一種非常流行的基本的聚類技術(shù)，被廣泛應(yīng)用于圖像處理之中[12].K-mean 聚類算法中包含有K個集群中心，數(shù)據(jù)集中的每個點被分到距離最近的集群中心所在的集群中.

表3 不同測例的有效壓縮比

然后，每個集群內(nèi)部根據(jù)中心點到各個點平方距離總和最小化的原則，重新計算產(chǎn)生新的集群中心.不斷重復(fù)這兩個步驟，直到中心點不再移動，則認為聚類完成.K值為8的情況下，我們對表3中3幅典型圖像重復(fù)聚類20次，得到的平均收斂時間比普通高速緩存少34%.

5 結(jié) 語

已有的FPGA壓縮算法主要關(guān)注FPGA片內(nèi)片外之間有效帶寬的提升[8-9]，但是有效帶寬增加的同時也帶來了高延時的問題，因此，不適用于實時性高的FPGA應(yīng)用.針對這一問題，本文在BDI算法的基礎(chǔ)上改進提出了粗粒度訪問的頁式高速緩存壓縮算法，并應(yīng)用于FPGA片內(nèi)高速緩存，實現(xiàn)了能夠有效加速FPGA應(yīng)用的頁式高速緩存.國際上尚沒有應(yīng)用于FPGA的高速緩存壓縮算法，本文提出將高速緩存壓縮算法應(yīng)用于FPGA高速緩存領(lǐng)域.頁式高速緩存通過合理劃分被訪問數(shù)據(jù)并進行壓縮，避免了以往計算機的高速緩存壓縮算法遇到的內(nèi)存碎片化問題，同時采用頁式內(nèi)存管理單元解決了新舊數(shù)據(jù)替換的問題.經(jīng)過實驗驗證，該頁式高速緩存算法硬件資源開銷小，壓縮和解壓縮延時低，同時能夠有效地壓縮圖像和矩陣數(shù)據(jù).