利用數(shù)據(jù)冗余性的高速緩存壓縮校驗技術(shù)

田 芳，王 晶，張偉功

1(首都師范大學 信息工程學院，北京 100048)2(北京成像技術(shù)高精尖創(chuàng)新中心，北京 100048)3(首都師范大學 電子系統(tǒng)可靠性技術(shù)北京市重點實驗室，北京 100048)

1 引 言

空間環(huán)境中存在大量的高能帶電粒子，高速緩存作為占據(jù)芯片面積50%以上的關(guān)鍵部件，極易發(fā)生單粒子翻轉(zhuǎn)故障，導致存儲數(shù)據(jù)發(fā)生多位的錯誤.與此同時，"功耗墻"問題使整個計算機行業(yè)面臨巨大的能源危機.降低電壓是減少能耗最有效的手段之一，然而電壓的降低卻導致故障率的指數(shù)級增加，當供電電壓下降到正常電壓的50%時能效性可以提高10倍，但1位錯誤率從1/108增加到10%，遠高于系統(tǒng)可容忍的0.1%，且會引發(fā)0.01～0.001%的3位和4位故障[1].

電路級容錯是較為簡單且廣泛使用的方案，然而底層電路的全加固會導致面積和能耗開銷成倍增加.體系結(jié)構(gòu)級方案，如容錯校驗碼ECC，能夠根據(jù)系統(tǒng)可靠性的需求，結(jié)合應用程序的特性，更加靈活的實現(xiàn)性能與功耗的權(quán)衡，廣泛應用在高速緩存中.然而ECC的容錯開銷會隨著故障的復雜度和保護的信息位位數(shù)增加而線性增長.對于經(jīng)典的BCH碼，對63位數(shù)據(jù)實現(xiàn)糾4檢5的保護時，所需校驗位為碼長的38.1%；而當糾錯能力增加到10位時，校驗位將增加到71.4%，此外能耗、面積等開銷也會隨著糾錯算法的復雜度增加同比上升.針對校驗算法的高開銷問題，本文提出一種基于數(shù)據(jù)冗余特征的高速緩存的壓縮校驗方案.本文主要貢獻如下：

1) 針對在民用智能設備、航天、國防等領域中廣泛應用的經(jīng)典BCH糾錯算法的空間開銷和時間開銷進行分析，量化了信息位、容錯能力與開銷之間的關(guān)系.

2) 提出基于數(shù)據(jù)存儲特征的壓縮校驗算法，針對全零型、重復性和數(shù)據(jù)的相似性等不同的冗余模式選擇壓縮算法，提升單一壓縮算法的數(shù)據(jù)壓縮率.

3) 設計了支持多標簽的高速緩存結(jié)構(gòu)，和基于數(shù)據(jù)模式校驗的高速緩存訪問流程，動態(tài)權(quán)衡容錯高速緩存空間開銷與壓縮算法時間開銷，提高了存儲空間利用率.

2 相關(guān)工作

目前國內(nèi)外主流的處理器高速緩存大多采用糾一檢二的海明碼或EDAC碼，算法簡單、開銷低，但是糾錯能力有限.為了在容錯能力和開銷之間實現(xiàn)權(quán)衡，學術(shù)界提出大量的編碼算法，表1總結(jié)了典型的Cache校驗算法.

表1 典型Cache校驗算法分析Table 1 Analysis of the typical algorithm of Cache

基于空間的交叉校驗、CPPC和2D算法只能處理特定模式的錯誤，基于備份的HER和FLAIR方法空間開銷成倍增加.Intel提出的MS-ECC方案根據(jù)高性能模式和低功耗模式故障率的差別，對分段后的高速緩存采用不同校驗碼，高性能模式采用糾一檢二檢驗算法，低功耗模式采用正交拉丁方編碼.譯碼時，將數(shù)據(jù)行與對應的ECC行放在譯碼器中，判斷是否有錯誤位.相比于以往方案MS-ECC能夠降低容錯開銷，但仍需消耗約50%的緩存空間[4].Hi-ECC方案是將錯誤分為多位錯誤和小于2位的錯誤.多位錯誤使用較為復雜，延遲較長的算法，1位錯誤使用快速糾錯算法，方案將已讀取的數(shù)據(jù)所在的高速緩存行的地址存儲在最近訪問緩存行表(RALT)中，每次讀取數(shù)據(jù)時，先從RALT中遍歷是否有該數(shù)據(jù)的地址，如果有，直接將數(shù)據(jù)發(fā)送到CPU中，不需要再次檢錯.如果讀取到不同緩存行的數(shù)據(jù)，則將此行的地址存儲在RALT中.這種方式減少了讀取數(shù)據(jù)的檢錯次數(shù)，減低了能耗.然而，Hi-ECC在更新ECC位時所需要的讀寫修改操作代價大，導致讀操作的延遲和帶寬需求增加[5].可變長度糾錯碼(VS-ECC)方案是對每一條高速緩存行進行糾一檢二的編碼，對敏感數(shù)據(jù)或易發(fā)生故障的Cache行則進行多位的編碼.此方案提出3種模式，分別是固定可變長度糾錯碼，關(guān)閉可變長度糾錯碼，可變長度糾錯碼.固定可變長度糾錯碼是對確定的幾行進行校驗；關(guān)閉可變長度糾錯碼，是指當某一高速緩存行產(chǎn)生的錯誤個數(shù)大于2時，關(guān)閉此行，避免錯誤；可變長度糾錯碼，具有較高的精確率，需要先判斷高速緩存行產(chǎn)生的錯誤個數(shù)，之后選擇對應的糾檢碼.然而VS-ECC是對硬故障采用校驗碼糾正，犧牲了軟錯誤的處理能力[6].Doe et.al提出的方案是將復雜編碼存儲在DRAM中.此方案將保護機制分為兩類，第一類錯誤編碼是低延遲，低功耗編碼，它可以糾正1位錯誤；第二類錯誤編碼容錯能力較高，可以糾正多位錯誤，但是開銷較大，性能平均下降1.3%，訪問末級緩存次數(shù)平均增加了36%，延遲幾乎增加了6%，而且需要額外的內(nèi)存操作，第二類錯誤讀、寫操作分別增加整體DRAM通信的0.1%和1.4%[7].

由于應用程序數(shù)據(jù)局部性，高速緩存中的數(shù)據(jù)存在大量的冗余信息，比如大量的數(shù)組通常初始化為全0，多媒體等應用中某個區(qū)域的像素值數(shù)據(jù)值完全相同，或當連續(xù)地址訪問時地址之間的數(shù)值差別很小而基址較大，或者是針對計數(shù)器等情況分配的存儲空間遠大于實際數(shù)值占用空間[13,14].這些冗余數(shù)據(jù)為壓縮帶來了可能，通過壓縮能夠消除高速緩存中冗余信息縮短信息位，從而降低容錯開銷.典型的Cache壓縮算法包括：ZCA壓縮算法針對的存儲數(shù)據(jù)值大多為0，或NULL[8]，對其他數(shù)據(jù)特征無法進行高效壓縮；FVC壓縮算法[9]可將存儲的大量重復數(shù)據(jù)進行壓縮[10]，以此減少源數(shù)據(jù)所占的空間，但無法對小范圍浮動值等冗余信息進行有效壓縮； FPC壓縮算法[11]試圖把幾種可壓縮的模式進行壓縮，比如4位符號擴展，一個字節(jié)符號擴展等[12]，但延遲開銷較大；B△I壓縮算法[13]壓縮數(shù)據(jù)值差別較小的緩存行，對全0值和重復值冗余模式的開銷較大.

針對上述問題，本文提出一種基于數(shù)據(jù)存儲特征的糾檢錯策略.該方案通過分析數(shù)據(jù)特征，動態(tài)選擇壓縮算法，采用糾錯算法對高速緩存進行容錯.

3 研究動機

針對現(xiàn)有容錯方案的高開銷問題，本文從校驗算法的時間開銷，空間開銷兩個方面分析，同時分析了程序數(shù)據(jù)的冗余度，為低開銷的壓縮校驗奠定了基礎.

3.1 校驗算法開銷分析

目前常用的EDAC碼有海明碼、奇偶校驗碼、BCH碼、循環(huán)冗余校驗碼等.隨著電壓的降低、晶體管尺寸的減少，多位錯誤發(fā)生的概率增加，校驗碼產(chǎn)生的復雜度與開銷越來越大.因此，對經(jīng)典的BCH碼進行開銷分析.BCH碼是Bose、Chaudhurl和Hocquenghem于1959年發(fā)現(xiàn)的一種循環(huán)碼[14]，是一類糾錯效果不錯的線性分組碼.由于BCH糾錯算法可對任意糾錯強度進行配置，也可糾正多位隨機錯誤，尤其在短和中等碼長下，性能很接近于理論值，并且構(gòu)造方便，編碼簡單，BCH算法成為當前NAND flash主控制器中主流的糾錯算法[15].但是，BCH糾錯算法時間開銷與空間開銷很大.

BCH糾錯算法的空間開銷和延遲開銷都由源數(shù)據(jù)信息位的長度決定，校驗位數(shù)目是由信息位的長度k和糾錯能力t共同決定；算法的時間復雜度則隨著編碼的長度的增加而增加.

BCH碼的時間復雜度通常可以表示為信息位的函數(shù)，糾錯時間如公式(1)，其中n為碼長，由圖1碼長和時間的曲線可知，隨著編碼長度的增加，時間復雜度同比增加.

T=n×log2n

(1)

圖1 時間復雜度Fig.1 Time complexity

空間開銷方面,對任何正整數(shù)m和t,一定存在一個二進制BCH碼，它以α,α3,…,α2t-1為根，其碼長n(n=2m-1)或是2m-1的因子，能糾正t個隨機錯誤，校驗位數(shù)目至多為m*t個，n和m之間的關(guān)系如公式2，(n：碼長，k：信息位，m：有限域的次數(shù) GF(2m))[16].

n=2m-1

(2)

圖2 BCH算法不同糾錯能力和信息位下的空間開銷Fig.2 Different error correcting capability and the space overhead bits of BCH algorithm

圖2為BCH算法不同糾錯能力和信息位下的空間開銷，通過圖可知，不同糾錯能力，所需要的檢驗碼不同，進而帶來的空間開銷也不盡相同.例如，當源數(shù)據(jù)為1MB，碼長為63位時，糾錯能力為1，校驗位數(shù)需1572864位，總位數(shù)為9961472位，校驗位占總位數(shù)的15.8%；糾錯能力為4，校驗位數(shù)需6291456位，總位數(shù)為14680064位，校驗位占總位數(shù)的42.9%.

3.2 應用程序數(shù)據(jù)冗余模式分析

應用程序的數(shù)據(jù)存在大量的冗余，通過對典型應用的數(shù)據(jù)分析發(fā)現(xiàn)，如圖3所示的三種冗余數(shù)據(jù)模式在應用程序出現(xiàn)最為頻繁[12].在應用程序中，0值出現(xiàn)的概率非常大，比如，系統(tǒng)初始化時，局部變量聲明會賦值為0或初始化為空指針或false布爾值，因此高速緩存行中會存儲大量的0；圖像或視頻處理程序中，臨近像素通常具有相同或相似的顏色，也會使高速緩存存儲大量相同的數(shù)值；而數(shù)組地址數(shù)值之間差異小，因此會出現(xiàn)高速緩存中相鄰數(shù)據(jù)之間值相似，偏差較小的情況.

圖3 應用程序數(shù)據(jù)冗余模式Fig.3 Data redundancy model of the application

以64B高速緩存行為例，通過對以上三種冗余模式采用不同壓縮算法進行壓縮，得到圖4的壓縮結(jié)果，其中全0值壓縮后所占空間為原有的1.56%；重復值壓縮后占原存儲空間的6.25%到12.5%；而由于基值和增值字節(jié)數(shù)不同，小范圍浮動值冗余模式占原有字節(jié)數(shù)的25%～62.5%.由此可見壓縮算法可以有效降低擁有顯著冗余模式的源數(shù)據(jù)信息位長度，能夠達到減少校驗位長度的從而提高系統(tǒng)的性能的目的.

圖4 不同壓縮算法信息位位數(shù)Fig.4 Bits of information in different compression algorithms

4 容錯高速緩存的壓縮校驗技術(shù)設計

通過對BCH糾錯算法的分析可知，常見的線性分組碼時間和空間的開銷都由源數(shù)據(jù)信息位的長度決定[18].而由于數(shù)據(jù)局部性和相似性特征，高速緩存中的數(shù)據(jù)存在著一定冗余信息.因此，本文提出一種基于數(shù)據(jù)存儲特征的糾檢錯策略：分析數(shù)據(jù)的存儲特征，選擇相應的壓縮算法.既消除源數(shù)據(jù)信息位的冗余信息，減少源數(shù)據(jù)的信息位，又保證數(shù)據(jù)的正確性，達到減少空間開銷和延遲時間，提高容錯高速緩存性能的目的.

4.1 壓縮算法的選擇

現(xiàn)有壓縮算法只針對具有某一種數(shù)據(jù)特征的存儲塊進行設計，因此，單一壓縮算法針對在不同應用程序中其所能達到的壓縮率是不同的.在運行基準測試過程中，發(fā)現(xiàn)全0值，重復值，小范圍浮動值這三類數(shù)據(jù)特征出現(xiàn)概率較大.為了達到較高壓縮率，本文對這三類冗余模式進行壓縮，由于高速緩存是簡單、快速、有效的存儲器件，因此，本文采用的壓縮算法均為簡單的向量加減操作.

圖5為不同壓縮方式存儲，針對于全0值和重復值這兩種冗余模式，本文只需存儲一個數(shù)值，其中重復值的字節(jié)數(shù)可能不同，基于數(shù)據(jù)的對齊存儲特性可分為4字節(jié)和8字節(jié)重復值存儲.而對小范圍浮動值冗余模式，需要判斷基值和差值.由于基值越多，算法越復雜，延遲時間開銷越大，壓縮率越低，基于性能和開銷的折中考慮，方案選用2個基值，一個基值為0值，另一個基值根據(jù)具體的高速緩存行進行選取，通過基值與高速緩存行中的數(shù)據(jù)并行執(zhí)行向量減操作，得到相應的差值，這樣，較大程度地減少源數(shù)據(jù)的信息位長度，如圖6.由于應用程序的數(shù)據(jù)存在多樣性，因而支持多種數(shù)據(jù)長度，基值可支持2字節(jié)、4字節(jié)和8字節(jié)，而增量值分別為1字節(jié)、2字節(jié)和4字節(jié)，共6種情況.

表2 壓縮方式Table 2 Compression mode

圖6 基值為4字節(jié)，增值為1字節(jié)壓縮方式Fig.6 Cache line compressed with B+Δ

表2給出了支持的壓縮方式，其中重復值冗余模式根據(jù)重復值所占字節(jié)數(shù)的不同，分為2種；小范圍浮動值根據(jù)所選基值和對應增值所占字節(jié)數(shù)的不同，分為6種.

4.2 支持壓縮的容錯Cache結(jié)構(gòu)設計

與傳統(tǒng)未壓縮高速緩存相比，壓縮高速緩存可以在相同數(shù)據(jù)容量下存儲更多的高速緩存行信息.為了有效利用壓縮節(jié)省的緩存空間，提出支持多個標記的Cache結(jié)構(gòu)[17]，通過額外的標記位獲得更多緩存行.由于壓縮算法的基值選擇為2個，因此Cache的標記位增加一倍.每一標記位均包含額外1位記錄是否壓縮以及額外3位記錄壓縮大小，數(shù)據(jù)數(shù)組分成八字節(jié)段，根據(jù)壓縮方式不同，緩存行壓縮為1-8個段.圖7為標記位存儲與數(shù)據(jù)位存儲，以4路組相聯(lián)為例，每一標記位存儲起始段，比如tag1存儲S1段.

圖7 標記位設計Fig.7 Tag design

在Cache的相聯(lián)度方面，組相聯(lián)映射比直接映射、全相聯(lián)映射命中率高，超標量體系結(jié)構(gòu)微處理器中高速緩存通常使用組相聯(lián)映射，因此，本文采用組相聯(lián)模式.然而，組相聯(lián)模式中的每一路對應著相同的映射關(guān)系，造成一定程度上的數(shù)據(jù)沖突.而高關(guān)聯(lián)度高速緩存在不同路使用不同映射函數(shù)，在一定程度上降低數(shù)據(jù)沖突發(fā)生概率[19].因此，本文同時采用高關(guān)聯(lián)度高速緩存進行對比.

圖8 組相聯(lián)映射Fig.8 Set-associative Cache

圖9 高相聯(lián)度映射Fig.9 Skewed-associative Cache

以2路組相聯(lián)為例，圖8為組相聯(lián)模式，當數(shù)據(jù)塊A0，A1，A2同時需要存儲在高速緩存中，由于組相連模式所有路使用同一函數(shù)映射，數(shù)據(jù)塊均存儲在組2中，此時，則需替換一路數(shù)據(jù)，造成數(shù)據(jù)沖突.而高關(guān)聯(lián)度進行存儲，由于不同路采用不同的哈希函數(shù)，在不同路中對應的組號則不同，假設路0中組0已存有數(shù)據(jù)，而數(shù)據(jù)塊A在路0中映射到組0，發(fā)生數(shù)據(jù)沖突.如果數(shù)據(jù)A映射到路1，由于映射關(guān)系不同，所對應的組號不同，數(shù)據(jù)沖突發(fā)生概率較小，如圖9.

4.3 支持壓縮的容錯Cache訪問流程設計

圖10為容錯高速緩存壓縮技術(shù)的結(jié)構(gòu)設計.由于校驗算法的空間開銷和時間開銷由源數(shù)據(jù)信息位的長度決定，而在運行基準測試時發(fā)現(xiàn)：全0值、重復值、小范圍浮動值這三種冗余模式出現(xiàn)頻率較大.壓縮這三種冗余信息位，源數(shù)據(jù)信息位數(shù)將會顯著降低，進而減少校驗位數(shù)，降低空間開銷和時間開銷.

圖10 結(jié)構(gòu)設計Fig.10 Architectural design

圖11為9種壓縮方式和未壓縮總位數(shù)(信息位與校驗位之和).以源數(shù)據(jù)的信息位長度為64B，BCH碼可以糾正4位錯誤為例，檢驗位位數(shù)為48B.通過分析緩存行中存儲的數(shù)據(jù)特征，選擇對應壓縮算法，比如高速緩存行數(shù)據(jù)的冗余模式是基值為8字節(jié)，增值為1字節(jié)的小范圍浮動值，首先判斷冗余模式，其次選擇基值，由于基值為8字節(jié)，因此，緩存行中數(shù)據(jù)以8字節(jié)為單位，與基值進行向量減操作，并對對應的增值進行存儲，所得到的壓縮數(shù)據(jù)為16B，是未壓縮數(shù)據(jù)的25%，最后通過對壓縮數(shù)據(jù)進行BCH碼編碼進行容錯，校驗位為12B，總位數(shù)為由112B降低為28B.

圖11 不同壓縮方式總位數(shù)Fig.11 Total bits of different compression modes

圖12為基于數(shù)據(jù)模式校驗的高速緩存控制流程.

1) 為CPU一般訪問流程：CPU讀取數(shù)據(jù)時，先從L1 Cache中獲取數(shù)據(jù)，如果不命中，則從L2 Cache中獲取數(shù)據(jù)，如果L2 Cache沒命中，則從內(nèi)存中獲取數(shù)據(jù).本文提出的基于數(shù)據(jù)模式校驗的高速緩存控制流程;

2)為L2 Cache從內(nèi)存中讀取數(shù)據(jù)：首先判斷數(shù)據(jù)特征，對不同數(shù)據(jù)特征采用不用壓縮算法，消除冗余信息，減少源數(shù)據(jù)信息位位數(shù)；其次，對壓縮后的數(shù)據(jù)進行校驗算法的編碼階段，保證數(shù)據(jù)的正確性；最后將數(shù)據(jù)傳送到L2 Cache中.

3)為L2 Cache往L1 Cache中寫數(shù)據(jù)：首先進行糾檢錯譯碼階段，保證數(shù)據(jù)的正確性，其次對壓縮的數(shù)據(jù)進行對應解壓縮操作，恢復源數(shù)據(jù)；最后將源數(shù)據(jù)傳送到L1 Cache中.

4)為L1 Cache往L2 Cache寫數(shù)據(jù)，具體過程與(2)類似.

5)為L2 Cache往內(nèi)存寫數(shù)據(jù)，具體過程與(3)類似.

圖12 支持壓縮的容錯Cache訪問流程Fig.12 Access process in fault tolerant Cache supporting compression

5 實 驗

在Zsim[20]模擬環(huán)境中運行SPEC CPU2006基準測試程序?qū)Ρ疚姆桨高M行評估，體系結(jié)構(gòu)參數(shù)具體如表3所示.

表3 體系結(jié)構(gòu)參數(shù)Table 3 Architecture parameter

圖13和圖14分別是高速緩存為1M和2M情況下的壓縮率.壓縮率定義為壓縮后數(shù)據(jù)量和壓縮前數(shù)量量的比值，如

圖13 1M壓縮率Fig.13 Compression ratio for 1MB Cache

公式(3)，值越低壓縮效果越好.實驗結(jié)果顯示：采用不同方案，高速緩存中的總位數(shù)都有不同程度的減少，在1M時，本文提出的方案(RDC)壓縮率為48.8%，ZCA壓縮算法壓縮率為67.5%，F(xiàn)VC壓縮算法壓縮率為63.2%，BDI壓縮算法壓縮率為61.8%.在2M時，本文提出的方案(RDC)壓縮率為44.7%，ZCA壓縮算法壓縮率為63.2%，F(xiàn)VC壓縮算法壓縮率為59.0%，BDI壓縮算法壓縮率為59.2%.本方案在消除源數(shù)據(jù)信息位的冗余信息后，經(jīng)過BCH碼編碼產(chǎn)生的校驗位位數(shù)也相應降低，容錯高速緩存存儲的總位數(shù)明顯的降低 .

(3)

圖14 2M壓縮率Fig.14 Compression ratio for 2MB Cache

圖15和圖16為高速緩存分別為1M單核和2M多核時不同壓縮算法的命中率，本文的方案相較于ZCA分別將命中率提高了1.47%和1.53%,相比于FVC分別將命中率提高了7.94%和8.31%,相比于BDI壓縮算法分別將命中率提高了7.93%和8.36%.

圖15 1M單核不同壓縮算法命中率Fig.15 Hit rate of single-core different compression algorithm for 1MB L2 Cache

圖16 2M多核不同壓縮算法命中率Fig.16 Hit rate of multi-core different compression algorithm for 2MB L2 Cache

圖17和圖18是高速緩存分別為1M單核、2M多核時，系統(tǒng)的性能，采用歸一化IPC表示.結(jié)果顯示，RDC均不同程度地提升IPC值，1M單核相比ZCA壓縮算法提升7.9%，F(xiàn)VC壓縮算法6.6%,提升BDI壓縮算法10.1%，2M多核分別提升19.4%，6.9%，14.5%.

圖17 1M單核IPCFig.17 IPC of single-core for 1MB L2 Cache

圖18 2M多核IPCFig.18 IPC of multi-core for 2MB L2 Cache

圖19分析了高速緩存分別為1M、2M時，不同數(shù)據(jù)特征出現(xiàn)的概率.通過圖可知在2M時，滿足冗余數(shù)據(jù)特征的概率較大，2M冗余數(shù)據(jù)特征出現(xiàn)的概率平均為79.4%，1M冗余數(shù)據(jù)特征出現(xiàn)的概率平均為75.1%.

圖19 不同數(shù)據(jù)特征出現(xiàn)的概率Fig.19 Probability of the appearance of different data features

6 結(jié) 論

高速緩存的容錯設計在空間等苛刻計算環(huán)境中具有重要意義，現(xiàn)有系統(tǒng)多采用校驗算法，但隨著錯誤復雜度的增加，時間與空間開銷等比增加.為此本文提出一種基于數(shù)據(jù)模式的高速緩存壓縮校驗方案，分析數(shù)據(jù)冗余特征，設計了根據(jù)數(shù)據(jù)冗余模式的動態(tài)壓縮算法選擇方式，并對壓縮數(shù)據(jù)進行校驗，模擬環(huán)境中的評測顯示本文方法將高速緩存的占用率平均降低了53.2%，單核IPC平均提升15.1%，多核IPC平均提升16.7%，命中率平均提升了5.92%.既保證了系統(tǒng)的可靠性，又降低了容錯開銷，提高了系統(tǒng)性能.