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

田 芳，王 晶，張偉功

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

1 引 言

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

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

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

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

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

2 相關(guān)工作

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

表1 典型Cache校驗(yàn)算法分析Table 1 Analysis of the typical algorithm of Cache

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

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

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

3 研究動(dòng)機(jī)

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

3.1 校驗(yàn)算法開銷分析

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

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

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

T=n×log2n

(1)

圖1 時(shí)間復(fù)雜度Fig.1 Time complexity

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

n=2m-1

(2)

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

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

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

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

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

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

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

4 容錯(cuò)高速緩存的壓縮校驗(yàn)技術(shù)設(shè)計(jì)

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

4.1 壓縮算法的選擇

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

圖5為不同壓縮方式存儲(chǔ)，針對(duì)于全0值和重復(fù)值這兩種冗余模式，本文只需存儲(chǔ)一個(gè)數(shù)值，其中重復(fù)值的字節(jié)數(shù)可能不同，基于數(shù)據(jù)的對(duì)齊存儲(chǔ)特性可分為4字節(jié)和8字節(jié)重復(fù)值存儲(chǔ).而對(duì)小范圍浮動(dòng)值冗余模式，需要判斷基值和差值.由于基值越多，算法越復(fù)雜，延遲時(shí)間開銷越大，壓縮率越低，基于性能和開銷的折中考慮，方案選用2個(gè)基值，一個(gè)基值為0值，另一個(gè)基值根據(jù)具體的高速緩存行進(jìn)行選取，通過基值與高速緩存行中的數(shù)據(jù)并行執(zhí)行向量減操作，得到相應(yīng)的差值，這樣，較大程度地減少源數(shù)據(jù)的信息位長度，如圖6.由于應(yīng)用程序的數(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給出了支持的壓縮方式，其中重復(fù)值冗余模式根據(jù)重復(fù)值所占字節(jié)數(shù)的不同，分為2種；小范圍浮動(dòng)值根據(jù)所選基值和對(duì)應(yīng)增值所占字節(jié)數(shù)的不同，分為6種.

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

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

圖7 標(biāo)記位設(shè)計(jì)Fig.7 Tag design

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

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

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

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

4.3 支持壓縮的容錯(cuò)Cache訪問流程設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

5 實(shí) 驗(yàn)

在Zsim[20]模擬環(huán)境中運(yùn)行SPEC CPU2006基準(zhǔn)測(cè)試程序?qū)Ρ疚姆桨高M(jìn)行評(píng)估，體系結(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)，值越低壓縮效果越好.實(shí)驗(yàn)結(jié)果顯示：采用不同方案，高速緩存中的總位數(shù)都有不同程度的減少，在1M時(shí)，本文提出的方案(RDC)壓縮率為48.8%，ZCA壓縮算法壓縮率為67.5%，F(xiàn)VC壓縮算法壓縮率為63.2%，BDI壓縮算法壓縮率為61.8%.在2M時(shí)，本文提出的方案(RDC)壓縮率為44.7%，ZCA壓縮算法壓縮率為63.2%，F(xiàn)VC壓縮算法壓縮率為59.0%，BDI壓縮算法壓縮率為59.2%.本方案在消除源數(shù)據(jù)信息位的冗余信息后，經(jīng)過BCH碼編碼產(chǎn)生的校驗(yàn)位位數(shù)也相應(yīng)降低，容錯(cuò)高速緩存存儲(chǔ)的總位數(shù)明顯的降低 .

(3)

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

圖15和圖16為高速緩存分別為1M單核和2M多核時(shí)不同壓縮算法的命中率，本文的方案相較于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多核時(shí)，系統(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í)，不同數(shù)據(jù)特征出現(xiàn)的概率.通過圖可知在2M時(shí)，滿足冗余數(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é) 論

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