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

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

msyksphinz.hatenablog.com

5. XORキャッシュアーキテクチャ

バンク内で任意の2つのラインをXOR可能にするため、XORキャッシュはタグ・アレイとデータ・アレイを分離した構造を採用し、類似候補を特定するためのマップテーブルを用いる(図8a参照)。

タグ・アレイ
- タグ・アレイはリンクリストとして管理され、図8(b)に示すようなエントリを持つ。
- XORed (1-bit) は、そのラインが他のラインとXORされているかを示す1ビットのフラグ。
- XORptr (log2(T)-bit) はXORペア相手のタグエントリを指すポインタである。
- 本実装では、1ラインが持つペアは最大1つとし、2以上の複数ラインとのXORについては将来の課題とする。
- DataPtr (log2(D)-bit) は対応するデータ・アレイのエントリを指す。
データ・アレイ
- 図8(c)に示すように、データ・アレイエントリは逆方向にタグ・アレイを指す tagptr (log2(T)-bit) を持つ。
- データ・アレイにはランダム置換ポリシーを採用している。他の圧縮方式と組み合わせる場合、XORキャッシュは可変サイズのデータエントリを扱う必要がある。
- このため、Thesaurusと同様に8バイト単位で分割管理し、セットごとのstartmapでオーディナルインデックスをセグメントIDに変換する方式を採用している。
- 詳細は省略するが、これについては先行研究 [24] に記載されている。データの拡張・圧縮後の再配置(データコンパクション)は、エビクション後に実行する。
5.1.3 マップテーブルとマップ関数

マップテーブルは、類似するXOR候補を特定するための小型ストレージ構造である(図8a)。マップ関数をキャッシュラインに適用して生成されるマップ値は、ラインの値を表すシグネチャとなり、マップテーブルのインデックスとして使用される。

データ挿入時、まずマップ関数でマップ値を生成し、マップテーブルを参照する。ヒットした場合はXOR圧縮が発動し、テーブルエントリはクリアされる。ヒットしなければ、スタンドアロンラインとして格納され、テーブルに新しいエントリが確保される。

マップ関数には以下の4種類を検討している：

ランダム射影に基づく局所性敏感ハッシュ(LSH-RP)
ビットサンプリングに基づく局所性敏感ハッシュ(LSH-BS)
バイトラベリング(BL)：各バイトが0x0なら0、そうでなければ1のブール値を生成し、これを並べた後、XORフォールディングを適用してマップ値とする。
スパースバイトラベリング(SBL)：単語ごとに最上位の6バイトのみを対象とし、低エントロピーな高位ビットに基づいてシグネチャを生成する。低位ビットはエントロピーが高いため、除外することでノイズを除去する。

マップ値のビット数はパラメータとして調整可能であり、その詳細な感度解析については第6.2節で議論されている。

操作フロー

XORキャッシュは他の圧縮キャッシュと同様に、データ要求時に伸長処理を行う。本節ではリード、unXORing、挿入などの動作を説明する。

読み出し: 図10aに示すように、LLCにリード要求が届くと、ディレクトリとタグ・アレイで並行検索を行う。ディレクトリヒットの場合、ラインはMまたはS状態であることを意味する。
- M状態の場合(w1)、要求はOwnerにフォワードされる (スヌープ)。
- S状態の場合(w2)、ラインがスタンドアロン(wa)かXOR化されている(wb)かで処理が異なる。
  - スタンドアロン: データ・アレイからデータを取得し、通常フローで応答する。
  - XOR化されている: XORptrでパートナーのタグを参照し、パートナーの共有者状態に応じて3種類のフォワーディングシナリオ(第4.3節)を実施する。
  - ディレクトリミスかつタグヒットの場合もS0状態として同様の分岐処理が必要である。
書き込みとアップグレード
- IまたはM状態への書き込み要求は通常通りメモリまたはOwnerにフォワードする。
- 一方、XOR化されたラインに対する書き込み要求では、XORペアを解除(unXORing)し、LLCタグおよびデータ・アレイからエントリを除去し、ディレクトリのみが保持する。
ライトバック
- クリーンライトバック(putS)は、ディレクトリが正確な共有者を追跡するために必要なデータなしメッセージである。
- XOR化されたラインの最後のライトバックでは、ペアのコヒーレンス状態を確認し、unXORingが必要な場合はネガティブACKを送り、プライベートキャッシュに再送を指示する。
- ダーティライトバック(putM)は、挿入フローに準じてXOR候補を探す。
XOR化されたラインの共起エビクション(co-eviction)
- 必要に応じてunXORingを行い、元のデータを復元してメモリにライトバックする。
- タグは、ペアの逆/順方向ポインタで同時に除去される。
挿入
- 挿入はメモリからのフェッチまたはライトバックで発生する(図11)。
- マップ関数でマップ値を生成し、マップテーブルに照合する。ヒットすれば、タグポインタを参照しデータをXORしてデータ・アレイに格納し、タグを更新する。
- 候補が存在しなければ、そのままスタンドアロンとして挿入され、マップテーブルに新規エントリが追加される。