メモリアクセスがアウトオブオーダにより入り乱れた際のプリフェッチ手法について

ちょっと気になっていたことではあるのだが、アウトオブオーダ実行ではメモリアクセスのリクエストもアウトオブオーダになり、ストライド検出器によって正しいストライド値を検出できないことがある。

LSUのパイプラインが3本あるような場合、メモリアクセスがプログラム順序的にはシーケンシャルであったとしても、それらの順番がアウト・オブ・オーダ実行によって入れ替わると、ストライド・プリフェッチが正しいメモリアクセスを検出できない。

ストライド・プリフェッチャ以外では正しく動作する可能性はある。例えば空間データ・プリフェッチャであれば空間を認識するだけなので各メモリ・リクエストの差分を考慮する必要はない。ストリーム・プリフェッチャについても、特定範囲内でのアクセスを認識できれば適当な場所にプリフェッチを出せるので問題はなさそうな気がしている。問題はストライド・プリフェッチャである。

この課題をいろいろと調査していると、この問題に焦点を当てた論文を見つけたので読んでみることにする。「SelSMaP: A Selective Stride Masking Prefetching Scheme」という論文だ。

https://ieeexplore.ieee.org/document/8119236

https://dl.acm.org/doi/10.1145/3274650

この論文では、例えばメモリアクセスのアウト・オブ・オーダ実行により、メモリアクセスのストライドが、

A, A+2, A+4, A+6, A+8, A+10,A+12

となるべきものが、実際には、

A+4, A, A+2, A+6, A+10, A+8 ,A+12

となるような問題に焦点を当てている。これを解決するために、以下の4つのモジュールを搭載している。

1. Stride Reference Table(SRT)
1. Stride Mask Logic (SML)
1. DML (Decision Making Logic)
1. Prefetch Address Calculation (PAC)

1. ストライド参照テーブル（SRT）: Region Tagによって管理させるメモリ・アクセスのフットプリントを記録するためのテーブル。以下の4つのフィールドを持っている。
2. Region Tag Fieldは、そのエントリーにどの領域が保持されているかについてのアクセス情報を示す。
3. Stride Reference Fieldは、その領域の投機的ストライドパターンを保持する。
4. Previous Access Fieldは、最後にアクセスされたキャッシュラインを示す部分アドレスを保存する。
5. Access History Fieldは、その領域内のどのキャッシュラインが時間の経過とともにアクセスされたかを記録する。

Access History Fieldはそのリージョン内のアクセスを記録するためのビットマップで、Stride Reference Fieldは各アクセスでの最小メモリアクセスストライドを保持している。

最小メモリ・アクセス・ストライドによって、次に、B.SMLによってストライドビットマップを作成する。

1. Stride Mask Logic (SML): SRTによって検出された最小ストライドアクセスによって、Stride Maskを作成する。例えば、最小ストライド値が2の場合は101010101...であり、最小ストライド値が3の場合は100100100100100...となる。

この値を用いて、DMLを使ってストライドの方向を決定する。

1. Decision Making Logic(DML): 簡潔にはSMLによって作られたストライドとSRTのアクセス・ヒストリを比較して方向を予測するのだが、SRTで直近に追加されたビットを使って順方向か逆方向のストライドかを判定する。以下の図を見るとなんとなく想像がつくのだが、アクセス・ヒストリの中から直近で追加されたビットを基準に右シフトと左シフトを行い、マスクビットとのANDをとる。そうすると、ストライドにマッチするビットが順方向と逆方向に何個存在しているのがわかり、それでストライドの方向を決めている（方向を決めるロジックとしては少し適当過ぎないかなあ...?）