キャッシュ汚染

キャッシュ汚染とは、実行中のコンピュータプログラムがCPUキャッシュに不必要なデータをロードし、^[1]他の有用なデータがキャッシュからメモリ階層の下位レベルに追い出され、パフォーマンスが低下する状況を指します。たとえば、マルチコアプロセッサでは、1つのコアが他のコアによってフェッチされたブロックを共有キャッシュに置き換えたり、プリフェッチされたブロックがキャッシュからデマンドフェッチされたブロックを置き換えたりすることがあります。

次の図を考えてみましょう。

T[0] = T[0] + 1;
 i in 0.. sizeof (CACHE)の場合
   C[i] = C[i] + 1;
 T[0] = T[0] + C[(CACHE)のサイズ-1];

(ここでの前提は、キャッシュが 1 つのレベルのみで構成され、ロック解除されており、置換ポリシーが疑似 LRUであり、すべてのデータがキャッシュ可能であり、キャッシュのセット連想性が N (N > 1) であり、プログラム値を格納するために最大 1 つのプロセッサ レジスタが使用可能であるということです)。

ループ開始直前に、T[0] がメモリからキャッシュにフェッチされ、その値が更新されます。ただし、ループの実行中、ループが参照するデータ要素の数によっては、キャッシュ全体をその容量まで埋める必要があるため、T[0] を含むキャッシュ ブロックを削除する必要があります。したがって、プログラムが次に T[0] の更新を要求すると、キャッシュ ミスが発生し、キャッシュ コントローラはデータ バスに要求して、対応するキャッシュ ブロックをメイン メモリから再度取得する必要があります。

この場合、キャッシュは「汚染されている」と言われます。T[0] の最初の更新をループと 2 番目の更新の間に配置することで、データ アクセスのパターンを変更し、非効率性を排除できます。

i in 0.. sizeof (CACHE)の場合
   C[i] = C[i] + 1;
 T[0] = T[0] + 1;
 T[0] = T[0] + C[(CACHE)のサイズ-1];

前述のコード再構築以外に、キャッシュ汚染の解決策としては、再利用度の高いデータのみがキャッシュに保存されるようにすることです。これは、特別なキャッシュ制御命令、オペレーティング システムのサポート、またはハードウェアのサポートを使用することで実現できます。

特殊なハードウェア命令の例には、PowerPC AltiVecが提供する「lvxl」があります。この命令は、128 ビット幅の値をレジスタにロードし、対応するキャッシュ ブロックを「最も最近使用されていない」、つまり、キャッシュ セットからブロックを退避する必要がある場合に退避する主な候補としてマークします。上記の例のコンテキストでこの命令を適切に使用するには、ループによって参照されるデータ要素をこの命令を使用してロードする必要があります。このように実装すると、ループの実行によって T[0] がキャッシュから早期に退避されることがないため、キャッシュ汚染は発生しません。ループが進むにつれて、C 内の要素のアドレスが同じキャッシュ ウェイにマップされ、実際には古い (ただし「最も最近使用されていない」とマークされていない) データは他のウェイにそのまま残るため、これは回避されます。最も古いデータ (この例には関係ありません) のみがキャッシュから退避されます。T[0] は、ループの開始直前に更新されるため、キャッシュのメンバーではありません。

同様に、オペレーティング システム (OS) のサポートを使用すると、 C データ配列に対応するメイン メモリ内のページを「キャッシュ禁止」、つまりキャッシュ不可としてマークできます。同様に、ハードウェア レベルでは、プログラム アクセス パターンに基づいて再利用率の低いデータを識別し、キャッシュからバイパスするキャッシュ バイパス スキームを使用できます。また、共有キャッシュを分割して、実行中のアプリケーション間の破壊的な干渉を回避することもできます。これらのソリューションのトレードオフは、OS ベースのスキームではレイテンシが大きくなり、キャッシュ汚染回避によって得られる利点が打ち消される可能性がある (メモリ領域が最初からキャッシュ不可でない限り) 一方、ハードウェア ベースの手法では、プログラム制御フローとメモリ アクセス パターンのグローバル ビューが得られない可能性があることです。

キャッシュ汚染制御は、いわゆる「メモリ ウォール」によって生じるペナルティが拡大し続けるため、ますます重要になっています。チップ メーカーは、メモリと CPU の相対的な遅延がますます増大するのを克服するために、新しいトリックを考案し続けています。そのために、キャッシュ サイズを増やし、ソフトウェア エンジニアが CPU にデータが到着して留まる方法を制御できる便利な方法を提供しています。キャッシュ汚染制御は、(主に組み込みの) プログラマーが利用できる数多くのデバイスの 1 つです。ただし、他の方法も使用されていますが、そのほとんどは独自のものであり、ハードウェアとアプリケーションに大きく依存しています。