データ・プリフェッチの技法であるBingoの論文を読んでいるので、概要をまとめる。
https://ieeexplore.ieee.org/document/8675188
PPHのイベントの話に戻る。図2は、様々な種類のイベントと、その時のマッチ確率を示したものである。
横軸のイベントは、右側ほど短い周期でイベントが発生しやすい。
- PC+Addressでは、イベントがマッチしてプリフェッチが駆動する機会は最も少ないが(黒棒のMatch Probabilityが最も低い)、プリフェッチの精度は最も高い(灰色のAccuracyが最も高い)。
- 一方、Offsetのみを使用すると、イベントがマッチする確率は非常に高いが、プリフェッチの精度は50％と悪化する。
このため、本研究では、複数のイベントと関連付けることを考える。ページのフットプリントを「PC+Address」「PC+Offset」「PC」の3つに関連付けて履歴テーブルに保存する。
次にトリガ・アクセスは、まずPC+Addressがマッチするかを検索し、ヒットすればそれを使用してプリフェッチを行う。そうでなければ、次に長いPC+Offsetを使用してプリフェッチを行い、さらにヒットしなければPCを使って検索する、ということになる。
Figure 3.は、イベントの数を1から5まで変化させた場合の空間プリフェッチャのカバレッジ範囲と制度を示している。イベントが1つしかないというのは、最長のPC+Addressイベントのみを使用しているということであり、この時はカバレッジ範囲は低いが精度は高い。一方でイベント数を5つまで増やすと、カバレッジ範囲を増やしつつ精度を上げることができているということが分かる。
ただしイベント数を増やせば増やすほどいいという訳ではない。イベント数の2以降は、あまりカバレッジの精度も上がっていないので、Bingoでは最大でも2つのイベント(つまり、PC+AddressとPC+Offset)を使用する。
PC+Offsetの方がイベントが緩いので、精度が低い(つまり、同一PC+Offsetであるが異なるフットプリントが存在し、それを利用してしまう)の場合、一応プリフェッチの発行はされるが精度は低いということになる。
この場合、各イベントで履歴テーブルを持つ必要があるが、これをまとめる方法を考える。つまり、単一のテーブルを複数のイベントで何度も検索するという方式である。例えば、PC+OffsetはPC+Addressに包含されているので、PC+Addressが分かれば、PC+Offsetも知ることができる。
このために、履歴テーブルは「最短イベント(PC+Offset)」のハッシュでインデックスされ、「最長イベント(PC+Address)」でタグ付けされるようにする。予測するときは、まずは履歴テーブルを最も長いイベント(PC+Address)で検索する。一致するイベントがあればそれでよい。そうでなければ、次に長いイベント(PC+Offset)で履歴テーブルを検索する。
図5が提案手法を良く表現していると思う。まずはトリガ・アクセスからPC+Offsetで検索し、PC+Addressでハッシュを検査し、ハッシュ値が一致すればそのままプリフェッチデータとして使用する。そうでなければ、PC＋AddressからPC+Offsetの情報を抽出*1し、それに基づいてPC+Offsetの値と比較することでプリフェッチデータを生成する。
*1:おそらくそのためには、PC+Addressのハッシュ値からAddressの情報を引き抜くことができるようなフォーマットでないといけないだろう。
