基于區域協作的Cache壓縮①

曾 露 李 鵬 王煥東

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

?

基于區域協作的Cache壓縮①

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

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

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

數據壓縮， 字典壓縮， 區域協作壓縮(RCC)， 高速緩存壓縮， 訪存優化

0 引 言

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

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

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

1 Cache壓縮

1.1 Cache壓縮的挑戰

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

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

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

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

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

1.2 Cache壓縮算法

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

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

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

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

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

表1 C-PACK編碼表

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

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

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

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

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

1.3 壓縮Cache的結構

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

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

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

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

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

(1)

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

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

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

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

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

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

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

1.3.3 壓縮策略的選擇。

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

2 區域協作壓縮

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

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

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

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

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

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

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

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

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

2.2 區域協作的壓縮算法

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

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

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

2.2.1 壓縮

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

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

圖2 RCC器的字典

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

2.2.2 解壓縮

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

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

定義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的值根據地址10-40位的哈希運算得到，因此不同緩存區域，FBR和SBR所能分配的候選路不同。而在命中查找時，根據hash運算得到相應的WFBR和WSBR，然后再根據FBR和SBR的索引分別對WFBR和WSBR的路進行訪問，即可實現一次訪問，同時命中FBR和SBR。

2.3 Cache組織結構

RCC采用基于VSC[8]的壓縮Cache結構，tag的數量為data的4倍，以最高支持4倍壓縮率。

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

圖3 RCC的tag字段

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

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

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

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

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

2.4 存儲開銷

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

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

3 實驗數據

3.1 實驗平臺

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

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

表3 目標系統的參數配置

3.2 壓縮率

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

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

3.3 性能分析

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

圖5 RCC, C-PACK, Base和2X Base的均一化IPC數據

4 結 論

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

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

[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)，國家自然科學基金(61232009, 61432016)和863計劃(2013AA014301)資助項目。

2016-01-18)

②男，1987年生，博士生；研究方向：計算機系統結構；聯系人，E-mail: zenglu@ict.ac.cn