曾 露 李 鵬 王煥東

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

?

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

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

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

為提高Cache的有效容量，進行了Cache壓縮研究，并提出了一種區(qū)域協(xié)作壓縮(RCC)方法，以提升最后一級緩存的壓縮率。與傳統(tǒng)的Cache壓縮算法不同，RCC方法利用了緩存區(qū)域的壓縮局部性，使用緩存區(qū)域中第一個緩存塊的字典信息來協(xié)作壓縮緩存區(qū)域中的其他各個緩存塊，而不需要對緩存區(qū)域進行整體壓縮。RCC有效發(fā)掘了緩存區(qū)域內(nèi)緩存塊之間的數(shù)據(jù)冗余，實現(xiàn)了接近以緩存區(qū)域為壓縮粒度的字典壓縮的壓縮率，然而壓縮、解壓縮延時卻仍然和壓縮單個緩存塊時相當(dāng)。實驗結(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 引 言

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

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

數(shù)據(jù)壓縮是降低數(shù)據(jù)存儲空間的有效手段。而在片上Cache中利用數(shù)據(jù)壓縮的技術(shù)理論上可以使得固定大小的Cache存儲更多數(shù)據(jù)，即可以提升Cache的有效容量。已有研究表明，壓縮緩存的邏輯容量可以達到其物理存儲空間的一倍以上，而代價僅僅是略微增加了訪問延時(主要是從壓縮Cache中讀取時解壓縮的延時)和少量的tag位等元數(shù)據(jù)。由此可見壓縮緩存的好處是顯而易見的，尤其是對訪問延時相對不敏感的最后一級緩存(Last Level Cache，LLC)，增加幾個時鐘周期的訪問延時對于整個訪存系統(tǒng)的性能影響很小。因此，大量的研究[1-5]通過實現(xiàn)高效管理壓縮數(shù)據(jù)的Cache結(jié)構(gòu)和適配于Cache的數(shù)據(jù)壓縮/解壓縮算法以實現(xiàn)更高的壓縮率、更低的訪問延時、功耗與面積開銷以及更高的Cache性能。因此，數(shù)據(jù)壓縮在提升Cache尤其是最后一級緩存(LLC)的有效容量，控制設(shè)計大容量Cache帶來的功耗，最終有效提升系統(tǒng)性能上具有很大的意義。本文將探索在LLC中實現(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)計信息編碼的Huffman算法在某些情形下甚至能夠獲得接近信息熵的壓縮率。這些算法及其衍生算法被廣泛應(yīng)用于壓縮軟件中對計算機數(shù)據(jù)進行壓縮，如DEFLATE。然而針對Cache數(shù)據(jù)的壓縮，則面臨與傳統(tǒng)數(shù)據(jù)壓縮不同的挑戰(zhàn)。

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

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

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

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

1.2 Cache壓縮算法

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

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

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

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

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

表1 C-PACK編碼表

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

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

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

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

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

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

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

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

1.3.1 壓縮緩存塊的存儲與索引

由于壓縮后的緩存塊大小不一，且壓縮Cache的tag數(shù)量需要大于未壓縮的數(shù)據(jù)塊數(shù)量以存儲壓縮數(shù)據(jù)，傳統(tǒng)Cache的tag與data一一映射的方式不適合壓縮Cache。壓縮Cache通常使用解耦(decoupled)方式進行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ù)塊集中存儲在一個物理緩存塊中，使用一個tag來表示超級緩存塊。根據(jù)緩存塊壓縮率的不同，tag可表示1,2,4,8個緩存塊。然而，SCC針對大緩存塊中壓縮率不同的緩存塊需要通過偏移映射的方式單獨存儲。SCC所需的元數(shù)據(jù)較少，不需要提供額外的tag，即可支持較高的壓縮率。

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

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

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

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

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

1.3.3 壓縮策略的選擇。

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

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

2.1 Cache壓縮的粒度對壓縮率的影響

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

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

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

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

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

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

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

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

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

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

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

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

2.2.1 壓縮

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

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

圖2 RCC器的字典

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

2.2.2 解壓縮

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

為實現(xiàn)SBR與FBR的壓縮信息同步讀取，消除額外的等待延時，需要Cache支持多路命中機制。多路命中的意思是在Cache訪問SBR時，同時命中FBR(若存在)，使得兩者的讀取可以同步進行。由于cache的每一路都是獨立的RAM，在訪問Cache時，可以使得部分路訪問SBR所映射組的索引，另一部分路訪問FBR所映射組的索引。通過在分配時通過地址哈希函數(shù)確定FBR和SBR各自允許存放的路數(shù)，使得不同緩存區(qū)域的FBR和SBR的路映射不同，從而在整個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位的哈希運算得到，因此不同緩存區(qū)域，F(xiàn)BR和SBR所能分配的候選路不同。而在命中查找時，根據(jù)hash運算得到相應(yīng)的WFBR和WSBR，然后再根據(jù)FBR和SBR的索引分別對WFBR和WSBR的路進行訪問，即可實現(xiàn)一次訪問，同時命中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)識緩存塊地址，可據(jù)此判斷該塊是FBR還是SBR；state記錄緩存塊的狀態(tài)和一致性信息；LRU保存訪問歷史以實現(xiàn)LRU替換算法；size是該緩存塊被壓縮的大小，以segment為單位，所在塊的偏移通過將其之前所有塊的size相加得到。

圖3 RCC的tag字段

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

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

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

(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 存儲開銷

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

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

3 實驗數(shù)據(jù)

3.1 實驗平臺

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

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

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

3.2 壓縮率

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

圖4 RCC與C-PACK壓縮率實驗結(jié)果對比

3.3 性能分析

與C-PACK相比，RCC需要在壓縮SBR時同時讀取FBR的字典項來協(xié)作壓縮，如果該過程串行，至少需要增加2拍延時(SBR需要等待FBR命中和字典項的讀取)，而多路命中很好地并行化了該過程。任意SBR可以和FBR同時被命中，F(xiàn)BR字典項的讀取延時剛好被SBR的讀取延時覆蓋，SBR在壓縮、解壓縮時，F(xiàn)BR的字典項已經(jīng)在字典中就緒。因此，RCC的延時與C-PACK相同。而且，實驗結(jié)果表明，RCC的缺失率相比C-PACK更低，這是由于Cache中存儲了更多數(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)性能。這種問題可以通過動態(tài)關(guān)閉數(shù)據(jù)壓縮來解決，且與本文的方案相容，可以共同提升系統(tǒng)的整體性能。

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

4 結(jié) 論

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

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

[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

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

2016-01-18)

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