基于區(qū)域協(xié)作的Cache壓縮①

曾 露 李 鵬 王煥東

(*計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室(中國(guó)科學(xué)院計(jì)算技術(shù)研究所) 北京 100190) (**中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京 100190) (***中國(guó)科學(xué)院大學(xué) 北京 100049) (****龍芯中科技術(shù)有限公司 北京 100190)

?

基于區(qū)域協(xié)作的Cache壓縮①

曾 露②******李 鵬******王煥東****

(*計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室(中國(guó)科學(xué)院計(jì)算技術(shù)研究所) 北京 100190) (**中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京 100190) (***中國(guó)科學(xué)院大學(xué) 北京 100049) (****龍芯中科技術(shù)有限公司 北京 100190)

為提高Cache的有效容量，進(jìn)行了Cache壓縮研究，并提出了一種區(qū)域協(xié)作壓縮(RCC)方法，以提升最后一級(jí)緩存的壓縮率。與傳統(tǒng)的Cache壓縮算法不同，RCC方法利用了緩存區(qū)域的壓縮局部性，使用緩存區(qū)域中第一個(gè)緩存塊的字典信息來協(xié)作壓縮緩存區(qū)域中的其他各個(gè)緩存塊，而不需要對(duì)緩存區(qū)域進(jìn)行整體壓縮。RCC有效發(fā)掘了緩存區(qū)域內(nèi)緩存塊之間的數(shù)據(jù)冗余，實(shí)現(xiàn)了接近以緩存區(qū)域?yàn)閴嚎s粒度的字典壓縮的壓縮率，然而壓縮、解壓縮延時(shí)卻仍然和壓縮單個(gè)緩存塊時(shí)相當(dāng)。實(shí)驗(yàn)結(jié)果表明，與單緩存塊壓縮算法C-PACK相比，RCC方法的壓縮率平均提升了12.34%，系統(tǒng)的性能提升了5%。與2倍容量的非壓縮Cache相比，有效容量提升了27%，系統(tǒng)性能提升了8.6%，而面積卻減少了63.1%。

數(shù)據(jù)壓縮， 字典壓縮， 區(qū)域協(xié)作壓縮(RCC)， 高速緩存壓縮， 訪存優(yōu)化

0 引 言

長(zhǎng)期以來，處理器運(yùn)算性能的快速提高與訪存帶寬的緩慢增長(zhǎng)之間一直存在著剪刀差，而且這種現(xiàn)象正愈演愈烈。計(jì)算性能與訪存性能的不平衡導(dǎo)致了系統(tǒng)整體性能的下降，即使有強(qiáng)大的計(jì)算能力也沒有辦法高效利用，大量的時(shí)間被浪費(fèi)在等待數(shù)據(jù)從存儲(chǔ)系統(tǒng)中加載到流水線中。因此，大量的研究工作致力于訪存系統(tǒng)的優(yōu)化，提高訪存的帶寬，降低訪存的延時(shí)。

由于半導(dǎo)體工藝的進(jìn)步，片內(nèi)可以集成更大的高速緩存(Cache)。增強(qiáng)動(dòng)態(tài)隨機(jī)存取存儲(chǔ)器(eDRAM)技術(shù)的成熟使得動(dòng)態(tài)隨機(jī)存取存儲(chǔ)器(DRAM)的高集成度技術(shù)被引用到Cache的設(shè)計(jì)中，進(jìn)一步增加了Cache的容量?，F(xiàn)代的計(jì)算機(jī)應(yīng)用通常擁有超大的工作集，提供更大的Cache容量總是能夠帶來更好的程序運(yùn)行性能。在體系結(jié)構(gòu)層面上探索更高的Cache利用效率與半導(dǎo)體工藝追求更高的片內(nèi)容量并不矛盾，反而兩者相輔相成，共同為性能的提升做出貢獻(xiàn)。然而Cache的設(shè)計(jì)面臨著面積、功耗與延時(shí)之間的權(quán)衡取舍。通常接近處理器核訪存部件的緩存需要更小的延時(shí)，從而減少流水線的空等待。為保證延時(shí)，其容量不能做到太大。而遠(yuǎn)離處理器核的緩存層次對(duì)訪存延時(shí)較為不敏感，通?？梢栽O(shè)計(jì)更大，然而更大的面積的Cache卻面臨著靜態(tài)功耗和翻轉(zhuǎn)功耗的問題。

數(shù)據(jù)壓縮是降低數(shù)據(jù)存儲(chǔ)空間的有效手段。而在片上Cache中利用數(shù)據(jù)壓縮的技術(shù)理論上可以使得固定大小的Cache存儲(chǔ)更多數(shù)據(jù)，即可以提升Cache的有效容量。已有研究表明，壓縮緩存的邏輯容量可以達(dá)到其物理存儲(chǔ)空間的一倍以上，而代價(jià)僅僅是略微增加了訪問延時(shí)(主要是從壓縮Cache中讀取時(shí)解壓縮的延時(shí))和少量的tag位等元數(shù)據(jù)。由此可見壓縮緩存的好處是顯而易見的，尤其是對(duì)訪問延時(shí)相對(duì)不敏感的最后一級(jí)緩存(Last Level Cache，LLC)，增加幾個(gè)時(shí)鐘周期的訪問延時(shí)對(duì)于整個(gè)訪存系統(tǒng)的性能影響很小。因此，大量的研究[1-5]通過實(shí)現(xiàn)高效管理壓縮數(shù)據(jù)的Cache結(jié)構(gòu)和適配于Cache的數(shù)據(jù)壓縮/解壓縮算法以實(shí)現(xiàn)更高的壓縮率、更低的訪問延時(shí)、功耗與面積開銷以及更高的Cache性能。因此，數(shù)據(jù)壓縮在提升Cache尤其是最后一級(jí)緩存(LLC)的有效容量，控制設(shè)計(jì)大容量Cache帶來的功耗，最終有效提升系統(tǒng)性能上具有很大的意義。本文將探索在LLC中實(shí)現(xiàn)高效數(shù)據(jù)壓縮的方法。

1 Cache壓縮

1.1 Cache壓縮的挑戰(zhàn)

傳統(tǒng)數(shù)據(jù)壓縮算法經(jīng)過幾十年的研究，已經(jīng)發(fā)展的較為成熟。諸如LZ77[6]算法以及在其基礎(chǔ)上衍生的LZXX算法簇，和基于統(tǒng)計(jì)信息編碼的Huffman算法在某些情形下甚至能夠獲得接近信息熵的壓縮率。這些算法及其衍生算法被廣泛應(yīng)用于壓縮軟件中對(duì)計(jì)算機(jī)數(shù)據(jù)進(jìn)行壓縮，如DEFLATE。然而針對(duì)Cache數(shù)據(jù)的壓縮，則面臨與傳統(tǒng)數(shù)據(jù)壓縮不同的挑戰(zhàn)。

首先，硬件實(shí)現(xiàn)壓縮算法要在取得一定壓縮率的同時(shí)，需要兼顧壓縮算法的實(shí)現(xiàn)復(fù)雜度以及壓縮、解壓縮的速度。過于復(fù)雜的壓縮算法的硬件實(shí)現(xiàn)成本和復(fù)雜度更高，且延時(shí)和面積開銷甚至使得數(shù)據(jù)壓縮得不償失；而簡(jiǎn)單的算法雖然高效快速，但是壓縮率通常較低。另外，緩存的讀操作是訪存的關(guān)鍵路徑，解壓縮延時(shí)對(duì)系統(tǒng)性能的影響大，因此壓縮算法還需要具有較短的解壓縮延時(shí)。

其次，壓縮數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)不同。通常緩存都是多路組相聯(lián)結(jié)構(gòu)，連續(xù)的緩存塊被映射到不同的組(set)，壓縮算法的壓縮粒度難以擴(kuò)展到更大的數(shù)據(jù)范圍，通常僅以緩存塊為單位進(jìn)行壓縮。而軟件壓縮算法可以在一個(gè)較長(zhǎng)的數(shù)據(jù)窗口中發(fā)掘冗余數(shù)據(jù)，甚至可以遍歷數(shù)據(jù)來統(tǒng)計(jì)頻率信息，使用占用空間最小的編碼方式。

最后，緩存的數(shù)據(jù)是動(dòng)態(tài)變化的，數(shù)據(jù)的修改需要將數(shù)據(jù)重新壓縮。新數(shù)據(jù)與舊數(shù)據(jù)的壓縮大小往往不同:如果壓縮數(shù)據(jù)變小，Cache中會(huì)空出小塊的存儲(chǔ)空間，而它們往往不足以存儲(chǔ)新的緩存塊，這就導(dǎo)致了碎片化；如果壓縮數(shù)據(jù)變大，還需要在組內(nèi)額外分配空間，如果空間不足，還會(huì)導(dǎo)致緩存塊的替換，進(jìn)一步增加了設(shè)計(jì)的復(fù)雜度。

因此，Cache壓縮需要綜合考慮壓縮率、解壓縮延時(shí)、面積開銷和實(shí)現(xiàn)復(fù)雜度等因素。僅側(cè)重某一方面，而其他方面開銷大，最終性能可能不好，甚至更差。

1.2 Cache壓縮算法

傳統(tǒng)數(shù)據(jù)壓縮算法可以采用更大的數(shù)據(jù)塊和更復(fù)雜的編碼方法，而緩存壓縮算法由于需要同時(shí)滿足較低的硬件實(shí)現(xiàn)復(fù)雜度和較好的壓縮率以及壓縮、解壓縮延時(shí)，因此，Cache壓縮算法通常以緩存塊為數(shù)據(jù)壓縮單位，并對(duì)有限的常見數(shù)據(jù)模式進(jìn)行編碼。

零值在Cache中所占比例較大，在某些應(yīng)用中，零值在Cache中甚至可以占到40%以上的空間。零內(nèi)容增強(qiáng)高速緩存(ZCA)[7]使用一個(gè)額外的緩存記錄Cache中為0的緩存塊的地址，而不需要在Cache中存儲(chǔ)零值，從而實(shí)現(xiàn)基本的壓縮。然而，由于僅能夠壓縮零緩存塊，ZCA受限于特定的應(yīng)用，并不廣泛適用。

然而，含有零值的緩存塊仍廣泛存在于Cache中，幾乎所有的Cache壓縮算法都會(huì)對(duì)零值進(jìn)行優(yōu)先壓縮，使其占用最少的空間。

常見模式壓縮(frequent pattern compression, FPC[8])將幾種較為常見的模式進(jìn)行定長(zhǎng)編碼，如連續(xù)的0、小值數(shù)據(jù)或重復(fù)值等共分為8類通過3bit的前綴來表示。據(jù)此將緩存行以數(shù)據(jù)字(32bit)為單位劃分，依次根據(jù)對(duì)應(yīng)的數(shù)據(jù)模式進(jìn)行匹配壓縮，生成相應(yīng)的前綴和壓縮數(shù)據(jù)。

C-PACK[2]算法(一種高性能微處理器高速緩存壓縮算法)首先采用和常見模式壓縮(FPC)類似的常見模式匹配，直接匹配壓縮0值和小值數(shù)據(jù)。對(duì)于不能匹配的數(shù)據(jù)，引入了字典壓縮。壓縮時(shí)所有未匹配的數(shù)據(jù)將插入字典，后面的數(shù)據(jù)字除匹配0與小值數(shù)據(jù)外，同時(shí)與字典中的項(xiàng)進(jìn)行匹配。字典項(xiàng)支持部分匹配，即匹配擁有相同高字節(jié)而低字節(jié)不同的數(shù)據(jù)，僅存儲(chǔ)低字節(jié)不同的部分，從而實(shí)現(xiàn)相似數(shù)據(jù)的壓縮。如表1所示，數(shù)據(jù)壓縮以4字節(jié)為單位，除0、小值數(shù)據(jù)和無法壓縮的情況為固定模式壓縮，其他三項(xiàng)為字典匹配，分別表示完全匹配，匹配高兩字節(jié)和匹配高三字節(jié)。由于字典的引入，大量相似的數(shù)據(jù)可以被壓縮，依次可以實(shí)現(xiàn)不錯(cuò)的壓縮率。C-PACK雖然增加了壓縮、解壓縮延時(shí)，但對(duì)于延時(shí)相對(duì)不敏感的最后一級(jí)緩存(LLC)，提高的數(shù)據(jù)壓縮率相對(duì)帶來的好處更大。

表1 C-PACK編碼表

注： 壓縮模式中每個(gè)字母代表一個(gè)字節(jié)，z表示為0，x表示當(dāng)前字節(jié)未匹配，m表示當(dāng)前字節(jié)匹配了字典項(xiàng)。壓縮后大小為使用16項(xiàng)字典時(shí)的值。

BDI(Base-Delta-Immediate)壓縮[3]認(rèn)為，大量Cache行中的數(shù)據(jù)擁有低動(dòng)態(tài)范圍(low dynamic range)的數(shù)據(jù)特性，即數(shù)據(jù)字之間的差值通常比這些數(shù)據(jù)本身的值要小。BDI 為緩存塊中固定大小(如2，4，8字節(jié))的數(shù)據(jù)字確定公共基值，而數(shù)據(jù)字可由占用較小空間的偏移值來表示。緩存塊的數(shù)據(jù)可以被壓縮為一個(gè)公共基值和若干個(gè)數(shù)據(jù)字的偏移值的形式。BDI要求緩存塊中所有數(shù)據(jù)字都必須壓縮成相同大小的偏移值，因此在解壓縮時(shí)所有的偏移值可以直接并行讀取并與公共基值進(jìn)行運(yùn)算完成解壓縮，可以實(shí)現(xiàn)2個(gè)時(shí)鐘周期的解壓縮延時(shí)。BDI的公共基值+偏移量的方式和C-PACK中字典項(xiàng)的部分匹配擁有一定相似性，不過由于BDI的基值數(shù)量固定，對(duì)于數(shù)值分散度較大的緩存塊壓縮效果較差，因此其壓縮率不如C-PACK。BDI的一個(gè)改進(jìn)策略是額外增加0作為公共基值，首先以0為基值計(jì)算偏移值優(yōu)先過濾小值數(shù)據(jù)，再確定剩余數(shù)據(jù)字的公共基值進(jìn)行壓縮。

FVC (frequent value compression，常見值壓縮)[5]通過預(yù)先計(jì)算出的常見值來配置常見值表。在程序執(zhí)行的過程中，該字典的內(nèi)容不變，對(duì)匹配的緩存數(shù)據(jù)進(jìn)行壓縮。FVC能夠?qū)Τ绦驁?zhí)行過程中最常見的值進(jìn)行壓縮。然而，通常程序的執(zhí)行隨著時(shí)間的變化，存儲(chǔ)在Cache中最多的值通常會(huì)發(fā)生變化，因此使用固定的值作為字典進(jìn)行壓縮不如動(dòng)態(tài)字典的壓縮效率高。

SC2(一個(gè)統(tǒng)計(jì)壓縮緩存方案)[4]使用定期采樣的統(tǒng)計(jì)信息進(jìn)行Huffman編碼來進(jìn)行數(shù)據(jù)壓縮。Huffman編碼的生成需要對(duì)數(shù)據(jù)進(jìn)行采樣來生成統(tǒng)計(jì)信息，而由于緩存中的數(shù)據(jù)在程序執(zhí)行時(shí)是動(dòng)態(tài)變化的，該算法需要每隔一段時(shí)間定期對(duì)緩存數(shù)據(jù)進(jìn)行重新采樣，更新Huffman編碼，使用新的編碼進(jìn)行數(shù)據(jù)壓縮。SC2需要使用一塊較大的RAM來存儲(chǔ)采樣的統(tǒng)計(jì)信息，在面積上不具有優(yōu)勢(shì)，但SC2能夠?qū)崿F(xiàn)較高的壓縮率。因此，該方案在適用性上有較大限制，需要考慮到其實(shí)現(xiàn)的面積開銷與復(fù)雜度。

常見的Cache設(shè)計(jì)中指令和數(shù)據(jù)在LLC中不加區(qū)分的存儲(chǔ)，Cache并不記錄某個(gè)地址是指令還是數(shù)據(jù)，并且有時(shí)指令還可以被當(dāng)作數(shù)據(jù)動(dòng)態(tài)地進(jìn)行修改。然而指令和數(shù)據(jù)擁有不同的壓縮特性。指令在編碼時(shí)已經(jīng)考慮到存儲(chǔ)的效率，因此指令本身的信息熵已經(jīng)很大，其壓縮性不足。然而，處理器運(yùn)行所需的指令類型在指令集中并非均勻分布，大多數(shù)時(shí)間僅運(yùn)行了少數(shù)類型的指令，而這些指令在Cache中冗余度很高，對(duì)于其中出現(xiàn)頻率較高的指令進(jìn)行編碼壓縮，可以較好地壓縮指令所需的存儲(chǔ)空間。Benini等在文獻(xiàn)[9]中探索了指令壓縮的方法。

1.3 壓縮Cache的結(jié)構(gòu)

Cache壓縮算法決定了數(shù)據(jù)最大可以被壓縮的大小。而有效的壓縮Cache結(jié)構(gòu)為壓縮算法實(shí)現(xiàn)數(shù)據(jù)壓縮提供了基礎(chǔ)。如果Cache組織不合理，要么限制了最大的壓縮率，要么需要消耗大量的元數(shù)據(jù)(額外的壓縮信息，用于索引壓縮緩存子塊的指針等)。因此，設(shè)計(jì)合理有效的壓縮Cache結(jié)構(gòu)才能配合Cache壓縮算法實(shí)現(xiàn)高效快速的Cache壓縮。

可壓縮Cache的結(jié)構(gòu)需要解決壓縮緩存塊的存儲(chǔ)與索引、壓縮緩存塊的修改與替換和壓縮策略的選擇的問題，接下來將分別進(jìn)行說明。

1.3.1 壓縮緩存塊的存儲(chǔ)與索引

由于壓縮后的緩存塊大小不一，且壓縮Cache的tag數(shù)量需要大于未壓縮的數(shù)據(jù)塊數(shù)量以存儲(chǔ)壓縮數(shù)據(jù)，傳統(tǒng)Cache的tag與data一一映射的方式不適合壓縮Cache。壓縮Cache通常使用解耦(decoupled)方式進(jìn)行tag與data的映射。

VSC[8]使用tag中的size字段來表示壓縮的緩存塊所占用的段(segment，4字節(jié))數(shù)目。VSC的緩存塊的偏移地址通過累加組內(nèi)該緩存塊之前所有緩存塊的size字段得到。第k路緩存塊的偏移地址為第1路至第k-1路緩存塊的size字段的和：

(1)

緩存塊的偏移和大小為offset(k)和size(k)。

SCC(skewed compressed cache, 偏移壓縮緩存)[10]根據(jù)相鄰數(shù)據(jù)的壓縮率相近的特性，將連續(xù)地址的壓縮數(shù)據(jù)塊集中存儲(chǔ)在一個(gè)物理緩存塊中，使用一個(gè)tag來表示超級(jí)緩存塊。根據(jù)緩存塊壓縮率的不同，tag可表示1,2,4,8個(gè)緩存塊。然而，SCC針對(duì)大緩存塊中壓縮率不同的緩存塊需要通過偏移映射的方式單獨(dú)存儲(chǔ)。SCC所需的元數(shù)據(jù)較少，不需要提供額外的tag，即可支持較高的壓縮率。

Pair-matching[2]限制一個(gè)物理緩存塊最多保存兩個(gè)壓縮緩存塊，在tag與data之間維持了二對(duì)一的固定映射，避免了壓縮緩存塊的索引開銷。然而，固定的映射決定了其理想情形下2倍壓縮率的上限，而且兩個(gè)壓縮緩存塊存儲(chǔ)在一個(gè)物理塊內(nèi)的限制決定了它放棄了大量的壓縮機(jī)會(huì)。

1.3.2 壓縮緩存塊的修改與替換

在系統(tǒng)運(yùn)行過程中緩存塊的內(nèi)容會(huì)發(fā)生變化，而對(duì)修改數(shù)據(jù)進(jìn)行重新壓縮后的大小也會(huì)發(fā)生變化。如果變小，那么剩余出來的空間需要通過執(zhí)行緊縮(compaction)或重映射來回收以避免浪費(fèi)；如果變大，則需要占用額外的空閑空間，甚至可能需要替換掉現(xiàn)有的一個(gè)或多個(gè)緩存塊。

Cache的緊縮需要讀寫組內(nèi)大部分的數(shù)據(jù)，因此該操作代價(jià)巨大。即使該過程可以與讀寫關(guān)鍵路徑并行，其巨大的功耗與復(fù)雜邏輯開銷仍然使得代價(jià)過大。SCC和Pair-matching均對(duì)緩存塊的大小有限制，不允許任意大小的緩存塊，因此避免了復(fù)雜的緊縮操作。

壓縮Cache的替換策略除考慮時(shí)間局部性因素外，還需要考慮緩存塊自身的壓縮大小，使用最少的替換次數(shù)滿足插入緩存塊的空間需求，以及考慮緩存的存儲(chǔ)布局，選擇合適的替換塊避免碎片的產(chǎn)生導(dǎo)致需要緊縮。ECM(effective capacity maximizer)[11]提出了大小可感知的壓縮緩存替換策略，同時(shí)利用最不常用(least recently used, LRU)信息和壓縮信息大小決定替換策略，保留盡可能多并且被重復(fù)利用的緩存塊，從而從另一個(gè)角度提升了系統(tǒng)的性能。

1.3.3 壓縮策略的選擇。

Cache壓縮算法通常都不能普遍適用于所有情形。對(duì)于不同的應(yīng)用，不同的數(shù)據(jù)類型以及不同的執(zhí)行時(shí)間點(diǎn)，數(shù)據(jù)的壓縮特性都有不同。有些應(yīng)用的工作集較小，數(shù)據(jù)壓縮帶來的額外空間沒有意義，反而產(chǎn)生了額外的延時(shí)，Alaa[8]提出了動(dòng)態(tài)方式判斷應(yīng)用是否得益于壓縮來決定是否壓縮數(shù)據(jù)。Nitta[12]根據(jù)緩存行中超過50%數(shù)據(jù)的數(shù)據(jù)類型選擇是否壓縮、如何壓縮，如針對(duì)整形、浮點(diǎn)和指針類型，采用不同的壓縮算法。

2 區(qū)域協(xié)作壓縮

2.1 Cache壓縮的粒度對(duì)壓縮率的影響

盡管固定大小的緩存塊可以使得Cache管理相對(duì)簡(jiǎn)單而且高效，使用更大粒度的緩存數(shù)據(jù)進(jìn)行壓縮通常可以獲得更高的壓縮率。應(yīng)用程序在訪存中大多呈現(xiàn)較強(qiáng)的空間局部，即地址相近的數(shù)據(jù)總會(huì)被相繼訪問。尤其是具有流式訪存行為的應(yīng)用(如applu, equake, ocean, radiosity, raytrace等)，它們會(huì)連續(xù)訪問大片的數(shù)據(jù)，且由于程序特性，連續(xù)訪問的相鄰數(shù)據(jù)擁有相似的特性，如擁有相同的高字節(jié)，而僅僅是低字節(jié)不同，或者是完全相同的數(shù)據(jù)。這類數(shù)據(jù)通常不僅僅存在于一個(gè)緩存行內(nèi)部，而通常存在于多個(gè)緩存塊范圍，從而產(chǎn)生了區(qū)域壓縮(region compression)的概念。

圖1 C-PACK壓縮算法在塊粒度和區(qū)域粒度下壓縮率對(duì)比

如圖 1所示，以C-PACK壓縮算法為基礎(chǔ)，分別為使用緩存塊為粒度進(jìn)行壓縮(C-PACK Blk)，使用16路組相聯(lián)的組為粒度進(jìn)行壓縮(C-PACK Set)和使用16個(gè)連續(xù)地址的緩存區(qū)域進(jìn)行壓縮(C-PACK Reg)在各個(gè)應(yīng)用程序下壓縮率的對(duì)比?？梢杂^察到C-PACK Reg方式對(duì)壓縮率有較大的提升，最高可達(dá)21%，平均也有17.96%的壓縮率提升；而同樣為16個(gè)緩存塊為粒度的C-PACK Set方式則提升很小，平均在5%以下。

因此，對(duì)更大的數(shù)據(jù)塊進(jìn)行壓縮，可以獲得比單獨(dú)壓縮一個(gè)緩存塊更好的壓縮性，特別是使用連續(xù)地址進(jìn)行壓縮，比在一個(gè)組內(nèi)相對(duì)隨意地址的多個(gè)緩存塊壓縮，具有更高的壓縮率，從而反映了數(shù)據(jù)壓縮的局部特性。本文認(rèn)為，數(shù)據(jù)壓縮局部性是除時(shí)間局部性、空間局部性之外，訪存系統(tǒng)特別是可壓縮訪存系統(tǒng)需要深入挖掘的第三種局部性。

然而，現(xiàn)有的Cache壓縮算法大都使用緩存行為單位進(jìn)行數(shù)據(jù)壓縮，因?yàn)檫@樣可以在不改變現(xiàn)有Cache架構(gòu)的情形下實(shí)現(xiàn)數(shù)據(jù)壓縮，而不引入額外的復(fù)雜性。在類似常見模式壓縮(FPC)這種固定模式的壓縮算法下，不同的壓縮數(shù)據(jù)的粒度對(duì)壓縮率沒有影響；而在基于字典的壓縮算法(如C-PACK, BDI)中，被壓縮的數(shù)據(jù)粒度越大，可以發(fā)掘的數(shù)據(jù)冗余越多。而基于單一緩存行的壓縮算法不能有效壓縮跨多個(gè)緩存行的冗余數(shù)據(jù)，需要在每個(gè)緩存行中單獨(dú)進(jìn)行存儲(chǔ)字典項(xiàng)，從而造成了Cache空間的浪費(fèi)。

利用數(shù)據(jù)壓縮局部性壓縮多個(gè)連續(xù)緩存塊可以提升可壓縮Cache的壓縮率，然而該技術(shù)面臨如下挑戰(zhàn)：

首先，由于緩存行中替換和修改數(shù)據(jù)塊是比較頻繁的，且替換和修改需要對(duì)數(shù)據(jù)重新進(jìn)行壓縮、解壓縮。如果以較大的數(shù)據(jù)塊為單位進(jìn)行整體壓縮和解壓縮，其代價(jià)顯然過大，在結(jié)構(gòu)設(shè)計(jì)中應(yīng)當(dāng)避免。Cache的壓縮和解壓縮多個(gè)緩存行會(huì)帶來較大功耗與延時(shí)開銷，然而可以借助其他緩存塊的壓縮信息以協(xié)助當(dāng)前緩存行的壓縮和解壓縮。

其次，連續(xù)緩存塊通常被映射到不同的set，通常難以通過一次訪問獲取多個(gè)連續(xù)的緩存塊數(shù)據(jù)或者壓縮信息。在設(shè)計(jì)中應(yīng)綜合考慮壓縮性與延時(shí)的平衡：獲取更多連續(xù)緩存塊的信息可以實(shí)現(xiàn)更高的壓縮率，然而需要更多的訪問延時(shí)。需要在保證一定壓縮率的提升下盡量減少對(duì)其他緩存塊的訪問。

2.2 區(qū)域協(xié)作的壓縮算法

本文提出了一種區(qū)域協(xié)作壓縮(region cooperative compression, RCC)算法，該算法利用了緩存的數(shù)據(jù)壓縮局部性，可以以較小的代價(jià)獲得比以緩存塊粒度進(jìn)行字典壓縮更高的壓縮率。

區(qū)域協(xié)作壓縮(RCC)的原理是利用緩存區(qū)域內(nèi)第一個(gè)緩存塊(first block in region, FBR)壓縮時(shí)所生成的字典項(xiàng)來協(xié)助壓縮區(qū)域內(nèi)后續(xù)緩存塊(successive block in region, SBR)的數(shù)據(jù)，由于緩存的壓縮局部性，該方法可以近似達(dá)到對(duì)整個(gè)緩存區(qū)域共同使用一個(gè)字典進(jìn)行壓縮的壓縮率。

RCC同時(shí)兼顧了延時(shí)、功耗與壓縮率。首先，緩存塊的壓縮、解壓縮僅針對(duì)當(dāng)前命中的緩存塊，不會(huì)修改組內(nèi)的其他緩存塊，而需要額外讀取的FBR字典項(xiàng)可以通過多路命中的方式覆蓋延時(shí)，因此延時(shí)并沒有增加；其次，緩存塊在壓縮、解壓縮時(shí)僅額外讀取了FBR的字典項(xiàng)，帶來少量的功耗開銷；最后，由于FBR的協(xié)作壓縮，SBR能夠利用FBR字典項(xiàng)進(jìn)行壓縮，其壓縮率可以更高。

2.2.1 壓縮

RCC過程以C-PACK算法為基礎(chǔ)，所不同的是在壓縮FBR和SBR時(shí)對(duì)字典的不同處理過程。

FBR的壓縮是一個(gè)獨(dú)立的過程，和C-PACK一樣，根據(jù)讀取到的數(shù)據(jù)字生成字典進(jìn)行后續(xù)數(shù)據(jù)字的壓縮。FBR作為協(xié)作者，如果插入Cache時(shí)已有該緩存區(qū)域中的其他塊存在，則SBR的壓縮有所不同，在壓縮前如果在Cache中存在FBR，則需要將FBR的字典項(xiàng)讀取到壓縮器的字典中。如圖 2所示，在執(zhí)行壓縮時(shí)，若存在FBR，其字典項(xiàng)會(huì)被讀取到字典中。如果命中，則直接使用該字典項(xiàng)進(jìn)行壓縮；如果沒有命中，處理方式與C-PACK相同。

圖2 RCC器的字典

由于FBR的字典項(xiàng)需要在SBR壓縮時(shí)使用，F(xiàn)BR的壓縮方式與SBR有所不同。FBR的壓縮僅針對(duì)自身，不需要從其他緩存塊讀取字典項(xiàng)。然而，由于FBR需要在SBR進(jìn)行壓縮時(shí)被快速訪問，因此，F(xiàn)BR在壓縮時(shí)，選擇字典中計(jì)數(shù)器值最大的兩個(gè)字典項(xiàng)放置在數(shù)據(jù)塊的頭部，在讀取SBR字典時(shí)，僅讀取數(shù)據(jù)頭的8個(gè)字節(jié)作為SBR字典項(xiàng)。

2.2.2 解壓縮

解壓縮的過程與C-PACK相同，只是在為SBR進(jìn)行解壓縮前需要讀取FBR的字典項(xiàng)。然而，如果該過程順序執(zhí)行，將增加額外的延時(shí)。解壓縮過程是訪存的關(guān)鍵路徑，解壓縮延時(shí)將直接影響Cache的訪問延時(shí)，從而影響性能。為此，當(dāng)讀取SBR時(shí)，F(xiàn)BR字典項(xiàng)的讀取需要與SBR同步進(jìn)行以避免增加額外的延時(shí)。

為實(shí)現(xiàn)SBR與FBR的壓縮信息同步讀取，消除額外的等待延時(shí)，需要Cache支持多路命中機(jī)制。多路命中的意思是在Cache訪問SBR時(shí)，同時(shí)命中FBR(若存在)，使得兩者的讀取可以同步進(jìn)行。由于cache的每一路都是獨(dú)立的RAM，在訪問Cache時(shí)，可以使得部分路訪問SBR所映射組的索引，另一部分路訪問FBR所映射組的索引。通過在分配時(shí)通過地址哈希函數(shù)確定FBR和SBR各自允許存放的路數(shù)，使得不同緩存區(qū)域的FBR和SBR的路映射不同，從而在整個(gè)Cache范圍內(nèi)消除了路限制帶來的潛在沖突。映射為FBR的路的tag與FBR的tag比較，映射為SBR的路與SBR的tag比較，最終根據(jù)各自的命中情況讀取FBR的壓縮信息和SBR的數(shù)據(jù)。

定義W={w1, w2, …, wn}為所有路的集合，WFBR和WSBR分別表示FBR和SBR的候選可分配的way，且定義wk=wk-1+1, w1=wn+1。那么有：

WFBR={w1+h, w2+h,…,wn/2+h}

(2)

其中h=hash(addr[39:10])且0

WSBR=W-WFBR

(3)

WFBR和WSBR的值根據(jù)地址10-40位的哈希運(yùn)算得到，因此不同緩存區(qū)域，F(xiàn)BR和SBR所能分配的候選路不同。而在命中查找時(shí)，根據(jù)hash運(yùn)算得到相應(yīng)的WFBR和WSBR，然后再根據(jù)FBR和SBR的索引分別對(duì)WFBR和WSBR的路進(jìn)行訪問，即可實(shí)現(xiàn)一次訪問，同時(shí)命中FBR和SBR。

2.3 Cache組織結(jié)構(gòu)

RCC采用基于VSC[8]的壓縮Cache結(jié)構(gòu)，tag的數(shù)量為data的4倍，以最高支持4倍壓縮率。

圖3所示為RCC的tag字段。addr標(biāo)識(shí)緩存塊地址，可據(jù)此判斷該塊是FBR還是SBR；state記錄緩存塊的狀態(tài)和一致性信息；LRU保存訪問歷史以實(shí)現(xiàn)LRU替換算法；size是該緩存塊被壓縮的大小，以segment為單位，所在塊的偏移通過將其之前所有塊的size相加得到。

圖3 RCC的tag字段

對(duì)于擁有8個(gè)64字節(jié)緩存塊的組，由于提供了4倍的tag，每個(gè)組有32個(gè)tag用來保存壓縮塊的信息。由于RCC使用了多路命中的機(jī)制，F(xiàn)BR僅會(huì)在其中16個(gè)tag中進(jìn)行查找，SBR則會(huì)在另外16個(gè)tag中進(jìn)行查找。多路命中技術(shù)對(duì)兩個(gè)地址分別進(jìn)行16路的全相聯(lián)比較，而不是各自進(jìn)行32項(xiàng)的全相聯(lián)比較，從而避免了額外的延時(shí)和功耗開銷。

由于SBR的壓縮利用了FBR的字典項(xiàng)，如果FBR發(fā)生替換，所有使用FBR字典項(xiàng)壓縮的SBR都需要進(jìn)行壓縮數(shù)據(jù)的恢復(fù)，而恢復(fù)的代價(jià)很大。RCC通過以下3種途徑解決該問題：

(1) 采用修改的LRU算法，發(fā)生替換時(shí)如果LRU隊(duì)尾是FBR，則向LRU隊(duì)列前面查找，直到找到非FBR為止。如果不存在非FBR的緩存塊，在FBR的tag中記錄了被SBR使用的次數(shù)(usage count，UC，如圖 3)，優(yōu)先選擇UC為0的FBR進(jìn)行替換。

(2) FBR被充分哈希到不同的組，采用如下映射方式：index =hash(addr[39:10]) + addr[9:6]，使得不同緩存區(qū)域的FBR均等的映射到所有的組中，且相同緩存區(qū)域內(nèi)的塊被映射到不同的組。

(3) 將被替換的FBR插入victim buffer，直到SBR依次被替換，UC降為0后FBR才被替換。

2.4 存儲(chǔ)開銷

表2列出了RCC, C-PACK, 2X Base與Base存儲(chǔ)空間需求比較結(jié)果。RCC在比Base多22.6%的面積開銷，對(duì)于4MB的Cache，RCC需要多消耗992kB的存儲(chǔ)空間，以實(shí)現(xiàn)大于2倍的壓縮率。不過，相比2X Base，RCC的面積開銷大大降低，減少了63.1%。

表2 RCC, C-PACK, 2X Base與Base存儲(chǔ)空間需求比較 (Base為4MB存儲(chǔ)，8路組相聯(lián)，64B緩存塊)

3 實(shí)驗(yàn)數(shù)據(jù)

3.1 實(shí)驗(yàn)平臺(tái)

本文采用MIT大學(xué)發(fā)布的Graphite分布式多核模擬器[13]，Graphite可以直接在主機(jī)上運(yùn)行被模擬的程序，基于動(dòng)態(tài)插樁的方式獲取執(zhí)行過程中的信息，模擬目標(biāo)結(jié)構(gòu)的運(yùn)行機(jī)制，從而獲取性能等參數(shù)。該模擬器的特性是系統(tǒng)開銷小，可并行模擬多核結(jié)構(gòu)，速度較快，但是由于它不是時(shí)鐘精確類型的模擬器，對(duì)于模擬要求具有精確時(shí)鐘信息的結(jié)構(gòu)如流水線結(jié)構(gòu)模擬準(zhǔn)確性較差。然而該模擬器提供了完整的多處理器多路組相聯(lián)Cache的行為模型和一致性模型，支持對(duì)壓縮Cache的行為進(jìn)行建模，因此該模擬器能夠滿足本文的實(shí)驗(yàn)要求。

本文主要研究數(shù)據(jù)壓縮在LLC中的運(yùn)用，以提升緩存的有效大小，從而降低其失效率最終實(shí)現(xiàn)性能的提升。而處理器核的微結(jié)構(gòu)以及緩存一致性協(xié)議則不在考察的范圍內(nèi)，因此相關(guān)參數(shù)僅采用比較常用的設(shè)計(jì)參數(shù)。具體的配置如表3所示。

表3 目標(biāo)系統(tǒng)的參數(shù)配置

3.2 壓縮率

如圖4所示，與C-PACK相比，RCC壓縮率有較大提升。如radiosity, lu_non_contiguous, water-nsquared的壓縮率提升超過了13%，對(duì)于所有測(cè)試程序，壓縮率平均提升了12.34%，壓縮率從2.2倍提升到2.54倍。實(shí)驗(yàn)結(jié)果說明了RCC對(duì)壓縮率的提升是擁有普遍好處的，這是由Cache的空間局部性與壓縮局部性決定的。雖然Cache仍然使用緩存塊為粒度進(jìn)行存儲(chǔ)和壓縮，但是其壓縮率已經(jīng)接近直接對(duì)緩存區(qū)域進(jìn)行壓縮，而代價(jià)僅僅是每次訪問需要同時(shí)多讀一個(gè)tag和FBR的字典項(xiàng)。

圖4 RCC與C-PACK壓縮率實(shí)驗(yàn)結(jié)果對(duì)比

3.3 性能分析

與C-PACK相比，RCC需要在壓縮SBR時(shí)同時(shí)讀取FBR的字典項(xiàng)來協(xié)作壓縮，如果該過程串行，至少需要增加2拍延時(shí)(SBR需要等待FBR命中和字典項(xiàng)的讀取)，而多路命中很好地并行化了該過程。任意SBR可以和FBR同時(shí)被命中，F(xiàn)BR字典項(xiàng)的讀取延時(shí)剛好被SBR的讀取延時(shí)覆蓋，SBR在壓縮、解壓縮時(shí)，F(xiàn)BR的字典項(xiàng)已經(jīng)在字典中就緒。因此，RCC的延時(shí)與C-PACK相同。而且，實(shí)驗(yàn)結(jié)果表明，RCC的缺失率相比C-PACK更低，這是由于Cache中存儲(chǔ)了更多數(shù)據(jù)，有用數(shù)據(jù)被替換的概率降低。如圖5所示均一化的IPC數(shù)據(jù)，RCC相比Base均有10%～30%不等的性能提升，而與2X Base相比，barnes, cholesky, ocean, radiosity, radix, raytrace, volrend等程序均有5%～13%不等的性能提升，而fft, lu, water等程序則有3%左右的性能下降，這是由于程序壓縮率的不同導(dǎo)致。壓縮率高的程序能帶來更低的缺失率，從而從整體上增加IPC；而壓縮率較低的程序?qū)?shù)據(jù)壓縮不敏感，反而由于解壓縮等帶來的開銷降低了系統(tǒng)性能。這種問題可以通過動(dòng)態(tài)關(guān)閉數(shù)據(jù)壓縮來解決，且與本文的方案相容，可以共同提升系統(tǒng)的整體性能。

圖5 RCC, C-PACK, Base和2X Base的均一化IPC數(shù)據(jù)

4 結(jié) 論

本文總結(jié)了目前壓縮緩存的結(jié)構(gòu)與算法研究進(jìn)展，并基于數(shù)據(jù)在緩存中呈現(xiàn)的壓縮局部特性，提出了區(qū)域協(xié)作的Cache壓縮。相比C-PACK壓縮，RCC有明顯的壓縮率提升，同時(shí)沒有帶來額外的延時(shí)，因而帶來了近乎“免費(fèi)”的性能提升。另外，RCC對(duì)于所有基于字典的Cache壓縮算法和結(jié)構(gòu)都具有適應(yīng)性，而不僅限于特定的結(jié)構(gòu)和算法。

未來的工作包括進(jìn)一步的發(fā)掘數(shù)據(jù)壓縮的粒度，與虛擬內(nèi)存的特性結(jié)合，在頁(yè)內(nèi)尋找壓縮的可能性；對(duì)緩存數(shù)據(jù)進(jìn)行分類，對(duì)指令、浮點(diǎn)數(shù)據(jù)這類數(shù)據(jù)使用專用的壓縮算法；以及在保證壓縮率的同時(shí)，探索進(jìn)一步降低解壓縮延時(shí)的方法。

[1] Alaa R A, David A W. Frequent Pattern Compression: A Significance-Based Compression Scheme for L2 Caches. In: Technical Report 1500, Computer Sciences Department, UW-Madison, 2004

[2] Chen X, Yang L, Dick R P, et al. C-pack: A high-performance microprocessor cache compression algorithm.IEEETransactionsonVeryLargeScaleIntegration(VLSI)Systems, 2010, 18(8): 1196-1208

[3] Pekhimenko G, Seshadri V, Mutlu O, et al. Base-delta-immediate compression: practical data compression for on-chip caches. In: Proceedings of the 21st International Conference on Parallel Architectures and Compilation Techniques, Minneapolis, USA, 2012. 377-388

[4] Arelakis A, Stenstrom P. SC2: A statistical compression cache scheme. In: Proceedings of the 41st Annual International Symposium on Computer Architecuture, Minneapolis, USA, 2014. 145-156

[5] Yang J, Zhang Y, Gupta R. Frequent value compression in data caches. In: Proceedings of the 33rd Annual ACM/IEEE International Symposium on Microarchitecture, Monterey, USA, 2000. 258-265

[6] Ziv J, Lempel A. A universal algorithm for sequential data compression.IEEETransactionsoninformationtheory, 1977, 23(3): 337-343

[7] Dusser J, Piquet T, Seznec A. Zero-content augmented caches. In: Proceedings of the 23rd International Conference on Supercomputing, Yorktown, Heights, USA, 2009. 46-55

[8] Alaa R A, David A W. Adaptive cache compression for high-performance processors. In: Proceedings of the 31st Annual International Symposium on Computer Architecture, Munich, Germany, 2004. 212-223

[9] Benini L, Macii A, Macii E, et al. Selective instruction compression for memory energy reduction in embedded systems. In: Proceedings of the 1999 International Symposium on Low Power Electronics and Design, San Diego, USA, 1999. 206-211

[10] Sardashti S, Seznec A, Wood D. Skewed compressed caches. In: Proceedings of the 47th Annual IEEE/ACM International Symposium on Microarchitecture, Cambridge, UK, 2014. 331-342

[11] Baek S, Lee H G, Nicopoulos C, et al. ECM: Effective capacity maximizer for high-performance compressed caching. In: Proceedings of the IEEE 19th International Symposium on High Performance Computer Architecture, Shenzhen, China, 2013. 131-142

[12] Nitta C, Farrens M. Techniques for increasing effective data bandwidth. In: Proceedings of the IEEE International Conference on Computer Design, Lake Tahoe, USA, 2008. 514-519

[13] Miller J E, Kasture H, Kurian G, et al. Graphite: A distributed parallel simulator for multicores. In: Proceedings of the IEEE 16th International Symposium on High Performance Computer Architecture, Bangarlore, India, 2010. 1-12

The Cache compression based on region cooperation

Zeng Lu******, Li Peng******, Wang Huandong****

(*State Key Laboratory of Computer Architecture(Institute of Computing Technology,Chinese Academy of Science), Beijing 100190) (**Institute of Computing Technology, Chinese Academy of Science, Beijing 100190) (***University of Chinese Academy of Science, Beijing 100049) (****Loongson Technology Corporation Limited, Beijing 100190)

The Cache compression was studied to increase Cache’s effective capacity, and a region cooperative compression (RCC) algorithm was proposed to improve the compression ratio of the last level Cache. Different to traditional Cache compression algorithms, the RCC algorithm exploits the compression locality to compress Cache blocks in a Cache region by the cooperation of the first block in the region, instead of compressing the whole Cache region. RCC effectively explores the duplications across the Cache blocks in a Cache region and shows a comparable compression ratio with dictionary compression approaches with the whole Cache region as the compression granularity, whereas the (de)compression latency is not increased. The experimental results show that RCC provides the better average compression ratio than the compression algorithm of C-PACK by 12.34%, which causes the performance improvement of 5%. Compared to the non-compressive Cache with double size, the effective capacity increases by 27%, the performance increases by 8.6% and the area decreases by 63.1%.

data compression, dictionary compression, region cooperative compression (RCC), Cache compression, memory access optimization

10.3772/j.issn.1002-0470.2016.05.003

①國(guó)家“核高基”科技重大專項(xiàng)課題(2014ZX01020201, 2014ZX01030101)，國(guó)家自然科學(xué)基金(61232009, 61432016)和863計(jì)劃(2013AA014301)資助項(xiàng)目。

2016-01-18)

②男，1987年生，博士生；研究方向：計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)；聯(lián)系人，E-mail: zenglu@ict.ac.cn