https://msyksphinz.hatenablog.com/entry/2025/07/05/040000

ISCA 2025で発表された "The XOR Cache A Catalyst for Compression" を読んでみることにした。

現代の計算機システムは、ラスト・レベル・キャッシュ(LLC)に対して多大なリソースを割り当てている。このLLCを圧縮する可能性について考え、プライベートキャッシュおよび包含性によって生じる冗長性を活用し、この冗長性をXOR圧縮により活用するための、XORキャッシュを提案する。

ラインペアのビット単位のXOR値を格納し、ライン間の相互圧縮により格納ライン数を半減させる
他の圧縮手法と組み合わせることで、類似した値のラインをXORすることにより、圧縮前にデータのエントロピーを低減させ、ライン内圧縮率を向上させる

評価の結果、XORキャッシュは非圧縮の大型キャッシュと比較して、LLCの面積を1.93倍、電力を1.92倍削減しつつ、性能オーバヘッドを2.06%に抑えることが示された。

1. はじめに

現代の計算機システムにおいて、大面積に占めるキャッシュの割合は大きい。例えば、AMDのZen3においては、32MBのL3キャッシュを搭載しており、大面積の約40%を占める。キャッシュの容量が大きくなるからと言ってそれに比例して性能が向上するわけではなく、アクセス・レイテンシは増加は増加する。これらの要因により、従来型の大規模キャッシュは将来のシステムにおいて非効率となる可能性がある。この効率性のギャップを埋めるために、キャッシュ・フットプリントと消費電力を削減しつつ性能を維持する、より良いキャッシュ階層最適化手法が求められている。

1.1. キャッシュ階層における冗長性 (ライン間圧縮)

LLCは通常はInclusiveキャッシュだり、上位レベルキャッシュに存在するキャッシュラインを含むか、一部を含んでいる(非包含・非排他的LLC: NINE)。従来の圧縮研究では、単一キャッシュレベル内の冗長性のみを活用するものであった。この研究では、キャッシュ・レベル間でのさらなる圧縮の機会が発生する。これを活用するために、XORキャッシュでは、挿入時に挿入されるラインとは別に選択されるラインとのビット単位のXORを行い、その結果をLLCデータ配列に格納する。これにより、物理的に1スロット内に2つのキャッシュラインを共存させることができる。圧縮されたラインペアは、少なくとも1つの元のラインが上位レベルで共有されている限り、圧縮状態を維持できる。この状態を「最小シェアラー不変条件」とと呼ぶ。このInter-line compression 状態では、最良のケースではLLCのデータ配列を半分に縮小できる。

ちょっと分かりにくいが、図1の状態だと、L1DキャッシュにラインAが存在しており、ラインAはLLCにてラインBと共有状態にある。つまり、LLCにはAとBのXOR (A⊕B) が格納されている状態である。この場合、キャッシュラインBを読み込む場合、LLCからA⊕Bのラインを持ってくれば、もともと存在しているL1D内のAとXORをすることによりBが引き出せる、という訳だ。

1.2. XOR圧縮の相乗効果 (Intra-line compression)

キャッシュの圧縮効果は、他の手法と組み合わせることで他の圧縮方式の圧縮比を促進(Catalyst)できる。図1bに示されているのは、キャッシュのラインAとラインBが類似している場合 (A~=B)、XORされたラインA⊕Bは小さいエントロピーを示すため、さらに圧縮することができる。これによりライン内圧縮 (intra-line compression)が可能である。

この相乗効果は図2に示されている (同じバンクまたは同じセット内の2つのラインが、最小シェアラー不変条件を満たさずともXOR可能であると仮定している)。例として、BΔIやBit-plane(BPC)といったライン内圧縮方式、およびThesaurusのようなライン間圧縮方式とXORキャッシュの相乗効果を示している。 - BΔI: キャッシュライン内の値のダイナミックレンジの低さを活用し、単一の基準値と小さいデルタの配列でラインを符号化する。 - BPC: データの可逆変換を3段階で行い、ランレングス符号化や頻出パターン圧縮を用いて圧縮する。 - Thesaurus: 局所性敏感ハッシュを用いてキャッシュラインを動的にクラスタリングし、代表値と比較して圧縮する。

XORペア選択ポリシーはどの2つのキャッシュラインをXORするかを決定するものであり、XORキャッシュ設計の要となる。 - randBank: ラインは同じバンク内の別のラインをランダムに選んでXORする - idealSet: 同じセット内の全ラインを候補とし、最も圧縮性が高くなるXOR候補を選ぶ。 - idealBank: 同じバンク内の全ラインを候補とし、最もサイズが小さくなる相手を選ぶ。理想的な候補を見つけるために探索する範囲が広いため、idealBankはidealSetより高い圧縮比を達成できる。しかし、idealBankは実装コストが大きいという課題がある。

1.3. 課題

相乗効果を実現するXORポリシーの設計
コヒーレンスプロトコル設計
- XOR圧縮は単一キャッシュレベルの境界を超えるため、コヒーレンスプロトコルを大幅に再設計する必要がある。