データ構造とアルゴリズムにおけるキャッシュミスのカウント方法

なぜキャッシュミスの回数が重要なのか

従来のアルゴリズム解析では、実行される操作やステップの回数を数えることが基本でした。これは、コンピュータが1つの操作を実行する時間の方が、その操作に必要なデータを取り出す時間よりも長かった時代には妥当な考え方でした。しかし現代では、演算を実行するコストは、メモリからデータを取得するコストに比べてはるかに低くなっています。

その結果、多くのアルゴリズムの実行時間は、操作の回数ではなくメモリ参照の回数(キャッシュミスの回数)によって支配されるようになりました。したがって、アルゴリズムを設計する際には、操作の回数を減らすことだけでなく、メモリアクセスの回数そのものを削減することにも注力する必要があります。さらに、メモリの遅延(レイテンシ)を隠蔽できるようなアルゴリズム設計も重要なポイントとなります。

単純なコンピュータモデルによる理解

ここでは、コンピュータのメモリがL1キャッシュ・L2キャッシュ・主記憶(メインメモリ)の3層で構成される単純なモデルを想定します。このモデルでは、レジスタ(R)上のデータに対してALU(演算論理ユニット)を使い、算術演算や論理演算を実行します。

全体の構成は次のブロック図のようになります。

メモリ階層のサイズ感

この図から、各メモリ階層のおおよそのサイズも読み取ることができます。

• 主記憶: 数百MB〜数千MB規模
• L2キャッシュ: 数百KB〜数MB規模
• L1キャッシュ: 数十KB規模
• レジスタ: 数十ビット規模

プログラムを実行すると、すべてのデータはまず主記憶上に存在します。例えばADD(加算)命令を実行する場合、対象となる数値がレジスタに格納され、レジスタ上で加算が行われ、その結果が再びメモリへ書き戻されるという流れになります。

各アクセスに要するサイクル数

ここで、1サイクルを「すでにレジスタにあるデータ同士を加算するのに必要な時間」と定義します。このモデルにおける各アクセスのコストは以下の通りです。

• L1キャッシュ→レジスタ: 2サイクル
• L1キャッシュミス(L2キャッシュから取得): L2キャッシュからL1キャッシュとレジスタへ転送するのに10サイクル
• L2キャッシュミス(主記憶から取得): 主記憶からL2キャッシュ・L1キャッシュ・レジスタへ転送するのに100サイクル

必要なデータがL1キャッシュに存在しなければ「L1キャッシュミス」が発生し、L2キャッシュからデータが取り込まれます。さらにL2キャッシュにも存在しなければ「L2キャッシュミス」となり、主記憶からの読み出しが必要になります。このように、データがどの階層にあるかによってアクセスコストが桁違いに変わるため、キャッシュミスの回数を抑えることが性能向上の鍵となります。

なお、書き込み操作は1サイクルとしてカウントされます。データが主記憶に書き込まれる場合であっても、書き込みの完了を待たずに次の操作へ進めるためです。この仕組みにより、書き込みによる遅延が処理全体のボトルネックになることを回避しています。