キャッシュミスのべき乗則

べき乗法則とは、2つの量の間の数学的な関係であり、一方の量が他方の量に比例するというものです。キャッシュミスのべき乗法則は、1974年のCK Chowの論文^{[ 1 ]}で初めて確立され、1971年にRichard Mattsonが行ったスタック処理のヒット率に関する実験データによって裏付けられました^{[ 2 ]。}キャッシュミスのべき乗法則は、許容可能なミス率を前提として、単一プロセッサシステムのキャッシュ階層を設計する際の初期段階の1つとして、キャッシュサイズを実用的な範囲に絞り込むために使用できます^{[ 3 ]}。

キャッシュミスのべき乗則は次のように表すことができます。

${\displaystyle M=M_{0}C^{-\alpha }}$

ここで、MはサイズCのキャッシュのミス率であり、M ₀はベースライン キャッシュのミス率です。指数αはワークロードに固有のもので、通常は 0.3 ～ 0.7 の範囲です。^{[ 4 ]}

べき乗則は、キャッシュサイズのある一定の値までしかミス率の推定値を与えることができません。十分な大きさのキャッシュがあれば容量ミスは解消され、べき乗則の予測に反して、キャッシュサイズをさらに大きくしてもミス率はそれ以上低下しません。^{[ 3 ]}

キャッシュミスのべき乗則の妥当性は、特定のプロセスにおけるワーキングメモリセットのサイズと、プロセス内のキャッシュブロックの一時的な再参照パターンにも依存します。プロセスのワーキングメモリセットがキャッシュサイズに比べて小さい場合、容量ミスは発生しにくく、べき乗則は成り立ちません。

連想性が高まるにつれて衝突のミスは減少するものの、Hartsteinら^{[ 4 ]}は、べき乗則は集合の連想性に関係なく成り立つことを示した。

Hartstein らは、多数のワークロードについてキャッシュブロックの再アクセス回数と再参照時間をプロットし、そのほとんどが指数関数的な関係に従うことを発見した。^{[ 4 ]}

${\displaystyle R(t)=R_{0}t^{-\beta }}$

ここで、R ( t )は再参照率である。指数βは1.7から1.3の範囲であることがわかった。理論的には、キャッシュ再参照とキャッシュミス率のべき乗則は次の式で関係付けられることが証明された。${\displaystyle \alpha =1-\beta }$つまり、再参照のべき乗則に従わないワークロードの場合、キャッシュミスのべき乗則は成り立たないということです。

マルチレベルキャッシュ階層では、上位レベルキャッシュのミスパターンが、直下の下位レベルキャッシュの再参照パターンになります。Hartstein ら^{[ 4 ]}は、下位レベルのキャッシュミスは厳密なべき乗則に従わないものの、下位レベルキャッシュが上位レベルキャッシュよりもかなり大きい限り、ミス率関数はべき乗則に近似できることを発見しました。

• キャッシュ階層
• キャッシュのパフォーマンス測定と指標