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

CPUキャッシュとは、メインメモリ内の頻繁に使用されるデータの一部を、より小さく高速なメモリの「キャッシュ」に保持することで、メモリ内のデータへのアクセス時間を短縮するハードウェアのことです。

コンピュータ システムのパフォーマンスは、整数演算、分岐演算、浮動小数点演算などの実行ユニット、I/O ユニット、バス、キャッシュ、メモリ システムなど、すべての個々のユニットのパフォーマンスに依存します。プロセッサの速度とメイン メモリの速度の差は指数関数的に拡大しています。2001～2005 年までは、クロック周波数で測定される CPU 速度は年間 55% 増加しましたが、メモリ速度は 7% しか増加しませんでした。^{[ 1 ]}この問題はメモリ ウォールとして知られています。キャッシュとその階層の動機は、この速度の差を埋め、メモリ ウォールを克服することです。

高性能コンピュータのほとんどにおいて、最も重要な構成要素はキャッシュです。キャッシュは速度ギャップを埋めるために存在するため、キャッシュサイズ、アソシアティビティ、置換ポリシーなどのさまざまなパラメータを設計および選択する際には、その性能測定と指標が重要になります。キャッシュ性能は、システム性能に制約を与える要因であるキャッシュヒットとキャッシュミスに依存します。キャッシュヒットとは、キャッシュ内で実際にデータを見つけたキャッシュへのアクセス回数であり、キャッシュミスとは、キャッシュ内でブロックを見つけられなかったアクセス回数です。これらのキャッシュヒットとミスは、平均アクセス時間（AAT）、別名AMAT（平均メモリアクセス時間）という用語に影響を与えます。AMATは、その名の通り、メモリにアクセスするのにかかる平均時間です。プロセッサ速度が上がるにつれてこの数値が非常に重要になるため、これはキャッシュ性能測定における主要な指標の1つです。

パフォーマンスをテストする上で役立つもう一つの指標は、キャッシュミスのべき乗則です。これは、いずれかのキャッシュサイズにおけるミス数が既知である場合に、キャッシュサイズを変更したときのミス数を示します。同様に、異なるアソシアティビティにおけるミス数の観点からキャッシュのパフォーマンスをテストしたい場合は、スタック距離プロファイリングが使用されます。

キャッシュ階層によるプロセッサのパフォーマンス向上は、キャッシュからのブロック要求を満たすキャッシュへのアクセス数（キャッシュヒット）と満たさないアクセス数に依存します。キャッシュからのデータ読み書きの試行が失敗すると（キャッシュミス）、下位レベルまたはメインメモリへのアクセスが発生し、レイテンシが増加します。キャッシュミスには、3Cs [ ^{2 ]と}呼ばれる 3 つの基本的なタイプと、あまり一般的ではないその他のキャッシュミスがあります。

これらのキャッシュミスは、命令あたりのサイクル数（CPI）の増加に直接相関します。ただし、キャッシュミスがCPIに与える影響の度合いは、命令レベル並列性（ILP）によってキャッシュミスのどれだけが計算とオーバーラップできるか、またメモリレベル並列性によって他のキャッシュミスのどれだけがオーバーラップできるかにも依存します。^{[ 2 ]}これらの影響を両方とも無視すると、平均メモリアクセス時間が重要な指標となります。これは、メモリシステムと階層のパフォーマンスの尺度を提供します。これは、メモリアクセスを実行するのにかかる平均時間を指します。これは、メモリ命令の実行時間とメモリストールサイクルの合計です。実行時間はキャッシュアクセスにかかる時間であり、メモリストールサイクルには、キャッシュミスを処理してメモリの下位レベルにアクセスする時間が含まれます。アクセスレイテンシ、ミス率、およびミス ペナルティがわかっている場合、平均メモリアクセス時間は次のように計算できます。

$${\displaystyle \mathrm {AMAT} =T_{L1}+MR_{L1}\cdot MP_{L1}}$$

どこ${\displaystyle T_{L1}}$レベル1キャッシュのアクセスレイテンシは、$MR_L1$レベル 1 キャッシュのミス率と${\displaystyle MP_{L1}}$これは、上位レベルでのミスが上位レベルでのヒットと比較して処理されるまでに要する追加サイクルであり、以下の式で計算されます。

$${\displaystyle MP_{L1}=T_{L2}+MR_{L2}\cdot MP_{L2}}$$

この式はさらに拡張して、メモリ階層のすべての後続レベルに対して再帰的に使用してAMAT を取得できます。 ^{[ 6 ]}

キャッシュミスのべき乗法則は、 キャッシュサイズによって影響を受けるプログラムの特定のアプリケーションにおける容量ミスの傾向を示します。この経験的観察から、ミス率とキャッシュサイズの関係を示すべき乗法則の数学的形式が導き出されました。それは次のように表すことができます。

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

ここで、MはサイズCのキャッシュのミス率、M ₀はベースライン キャッシュのミス率です。指数αはワークロードに固有のもので、通常は 0.3 ～ 0.7 の範囲で、平均は 0.5 です。べき乗則は、多くの実世界のベンチマークで検証されています。^{[ 7 ]}

この関係は、キャッシュサイズを一定量増やしても、キャッシュミスのごく一部しか解消できないことを示しています。この法則は、キャッシュサイズが一定の有限範囲内にある場合にのみ成り立ち、その範囲内ではミス率は横ばいになりません。ミス率は、ある一定の十分な大きさのキャッシュサイズで最終的に横ばいになり、それ以降はこの関係は正確な推定値を与えません。

スタック距離プロファイルは、キャッシュミスがキャッシュサイズによってどのように影響を受けるかをより適切に表現します。キャッシュミスのべき乗則は、同じことを大まかに近似したにすぎません。スタック距離プロファイルは、完全連想キャッシュまたはセット連想キャッシュにおけるアプリケーションの一時的な再利用動作を捉えます。^{[ 8 ]}

より時間的な再利用動作を示すアプリケーションは、一般的に最近使用されたデータにアクセスします。キャッシュの連想性を次のように仮定しましょう。${\displaystyle A}$このキャッシュのスタック距離プロファイル情報を収集するには、LRU置換ポリシーを採用していると仮定します。${\displaystyle A+1}$カウンターは以下から使用されます${\displaystyle C_{0}}$に${\displaystyle C_{A}}$カウンターが1つ追加されます${\displaystyle C_{<}A}$ミスをカウントするカウンター。${\displaystyle C_{i}}$ヒットがあったときに増加します${\displaystyle i^{th}}$方法とカウンター${\displaystyle C_{<}A}$は、ミスが発生するたびに増加します。スタック距離プロファイルは、ヒットの傾向を示し、最も最近使用されたデータから最も最近使用されていないデータへと減少します。このスタック距離プロファイル情報を使用して、アソシアティビティを持つキャッシュのキャッシュミスを測定できます。${\displaystyle A{'}}$また、LRU交換ポリシーでは、${\displaystyle A{'}<A}$計算すると次のようになります。

${\displaystyle miss=C_{<}A+\sum _{i=A{'}+1}^{A}C_{i}}$

このプロファイリング情報には、異なる連想関係における時間的再利用しか捉えられないという限界がある。その他の目的においては、時間的再利用をより詳細に調査する必要がある。

• キャッシュ階層