キャッシュメモリの性能と制御

キャッシュメモリは、CPUと主記憶の速度差を埋めるために、主記憶の一部のデータを小容量で高速なメモリに保持する仕組みである。CPUが要求したデータがキャッシュにあることをヒット、なければミスと呼び、ヒット率と各メモリのアクセス時間によって平均的なアクセス時間が決まる。性能と制御の問題では、置換アルゴリズム、実効アクセス時間の計算、書込み方式の三点が中心となる。

置換アルゴリズムの仕組み

キャッシュが満杯の状態で新しいブロックをロードするには、追い出すブロックを一つ選ぶ必要がある。その選び方を決めるものが置換アルゴリズムであり、代表的なものにFIFO、LIFO、LFU、LRUがある。FIFOはロードされた時刻が最も古いブロックを追い出す方式であり、LIFOはロード時刻が最も新しいブロックを追い出す方式である。LFUは参照回数が最も少ないブロックを、LRUは最後に参照された時刻が最も古いブロックを追い出す方式である。FIFOはロード時刻だけで判断するため、直近に参照されたかどうかは考慮しない。この点がLRUと結果を分ける要因となる。 LRUは最後の参照時刻が最も古いブロックを選ぶため、直近に使われたデータを残しやすい。同じ参照履歴を与えられた場合でも、ロード時刻の順と参照時刻の順は一致しないことがあるため、どの情報で判断する方式かを区別する必要がある。

実効アクセス時間の計算

実効アクセス時間は、ヒット時の時間とミス時の時間をそれぞれの割合で重み付けした平均である。キャッシュのアクセス時間を主記憶の時間に対する比で表し、ミス時は主記憶へのアクセス時間を基準とすると、計算の見通しがよくなる。キャッシュのアクセス時間が主記憶の1/30でヒット率が95%の場合、実効時間は主記憶のアクセス時間の約0.08倍になる。 キャッシュ照会の時間を含めて計算しても、結果は約0.08倍となり、答えは変わらない。このため、ミス時に主記憶へ達する前のキャッシュ照会時間が小さい場合、実効時間は主記憶の時間にほぼ支配される。 ヒット率そのものを実効時間の倍率とみなすことは誤りである。ヒット率は時間の比ではなく割合であり、時間に変換するにはそれぞれのアクセス時間を掛けて平均する必要がある。 キャッシュのアクセス時間だけに相当する比を答えとすることも誤りである。ミスした場合の主記憶へのアクセスが反映されないためである。