https://ieeexplore.ieee.org/document/1410068
プリフェッチにはいろんなアルゴリズムがあるが、プリフェッチが効果を発揮するためのいくつかの要素がある：
- 正確に次のデータを予測すること
- タイムリーにデータを取得できること
- 過度なプリフェッチを行わないこと
プリフェッチの基本は、メモリアドレスの動作に関連する履歴をテーブルに記録する。この記録する方法にはいろんな手法が存在しており、プログラムは、その命令のプログラムカウンタやミスアドレスなどをキーとしてそのテーブルにアクセスする。これをテーブル・ベース・プリフェッチイングと呼んでいる。
- ストライド・プリフェッチ：ロード命令のプログラムカウンタをキーとして、各テーブルエントリは当該ロード命令のもっとも最近のストライドおよびミスアドレスを保持する。この情報をもとに現在のミスアドレスとストライドの加算によって次のミスアドレスを予測し、プリフェッチを行う。
- 相関プリフェッチ：ロード命令のキャッシュ・ミス・メモリアドレスをキーとして、テーブルは当該アドレスの直後に発生したミスアドレスを保持する（マルコフ・プリフェッチ）。さらに一般化したディスタンス・プリフェッチは、2つの連続するミスアドレスの距離であるアドレス・デルタをテーブルのキーとして利用する。テーブルは、さらに過去のミス・アドレスとのデルタを保存しており、この情報を使って次のプリフェッチアドレスを計算する。
一方で、GHB (Global History Buffer)の考え方は異なっており、固定長のFIFOテーブルであるGHBにキャッシュミスアドレスの情報を保持する。
メモリ・アクセスがあった順番にFIFOにそのアクセス・アドレスを追加する。このFIFOはリンクリストとして動作し、古いアドレス履歴を自動的に削減する意味合いを持っている。
この方式の利点は、まずはプリフェッチテーブルを小さくすることができる点にある。また、小さなプリフェッチテーブルであったとしても競合が発生することがなく、効率的にメモリアクセスの履歴を保存することができる。
GHBは以下の2つの構造を持っている。
- インデックステーブル：ロード命令のプログラム・カウンタ、キャッシュ・ミス・アドレス、もしくはその両方を組み合わせたハッシュをキーとする。テーブルには、GHBへのポインタが含まれている。
- グローバル・ヒストリ・バッファ：最も最近のL2ミスアドレスを保持するnエントリのFIFOテーブルとして構成される。各エントリには、ミス・アドレスおよびリンク・ポインタが含まれる。リンク・ポインタによって各エントリ同士が接続される。
このようにテーブルを分けたことによって、柔軟かつより効率的に複雑なプリフェッチアルゴリズムを実装することができるようになる。
以下では、GHBの構成（つまり上記の2つのテーブル）を用いて上記の3種類のプリフェッチャを構成する方法について説明する。
- マルコフ・プリフェッチ（G/AC : グローバルアドレスを使用し、アドレス相関を取得する）
- インデックステーブル：ミス・アドレスをキーとする。エントリはGHB内の同じミス・アドレスのもっとも最近現れた場所のポインタを格納している。
- GHBエントリ：ミスアドレスを記録している。同じアドレスのエントリをポインタとして接続し、リンクリストを構成している。
- つまり、インデックステーブルで取得したGHBのポインタを参照すれば、そのリンクリストの隣接するエントリがそのミス・アドレスの次にミスが発生したアドレスである。これをプリフェッチターゲットとして使用すればよい。
