ハードウェアプリフェッチ

ハードウェアプリフェッチの分析方法としてSrinivasanらによるPTMT: Prefetch Traffic and Miss Taxonomy(*1)という手法が有名です。古典的な評価では、Coverage（本来ミスだったメモリアクセスの何割がプリフェッチで救えたか）とAccuracy（プリフェッチのうち何割が有効なプリフェッチだったか）でしか評価してなかったわけですが、PTMTではプリフェッチを行った場合と行わなかった場合の両方のケースについて同時にシミュレーションを行い、プリフェッチにより取得したキャッシュライン、プリフェッチにより追い出されたキャッシュラインそれぞれがキャッシュヒットとなったか、あるいは追い出されたかを調べて分析します。例えばあるプリフェッチにより取得したキャッシュラインがヒットしたとしても、追い出したキャッシュラインがミスを引き起こしてしまっては意味がないわけです。

これがマルチプロセッサ（SMP）環境になると、キャッシュのコヒーレンス制御が影響してきます。プリフェッチにより早期にデータを取得しても、その後のリモートプロセッサのストアによりせっかく取得したキャッシュラインをINVALID化する必要があります。このような効果も考慮したのがJergerらによるMPTMTと呼ばれる手法(*2)です。

さらにマルチコア（CMP）の場合にどうなるかというと、これはちょっと複雑で、キャッシュを共有する効果ってのも考える必要が出てきます。SMPの時のようなコヒーレンス制御の影響より、アグレッシブなプリフェッチを行った際の汚染の影響の方がクリティカルになるので、CMPならではの新しい問題、というよりはシングルコアの頃に研究されていたキャッシュのAccuracyを高めるといった手法が効果的になってくるみたいですね。そんなわけで、プリフェッチをフィルタリングして最小限度の質の高いプリフェッチを発行する、というのがプリフェッチ研究の1つの柱としてあるようです。プリフェッチのターゲットアドレス、あるいはプリフェッチを発行したPCをキーとしてプリフェッチが有効だったか否かのヒストリーをとり、そこから先は分岐予測と同じストーリー。やっぱりgshareとか使うと良い結果が出たりします(*3)。学習が入ってくるとなると、学習の種としてPTMT的な分析手法も重要になってきます。実際にインプリできるハードとして、1回の実行でどれだけ効果的に学習できるか、ですね。ちょっと前にキャッシュのセット方向の情報を使って１回の実行で様々なキャッシュサイズを想定したミス率変化グラフを書くって手法を聞きました。なんか同様のうまい方法を思いつかないかなぁ・・・なんて考えてたりしますが、一朝一夕にはいきません。

整数系のベンチマークでは、RDS: Recursive Data Structuresに着目した研究成果(*4)もあります。リストとかを辿る処理を検出して先読みする類いのやつです。この手の構造体のポインタを読み出すLoad命令をIPL: Induction Pointer Loadと呼ぶらしいです。なんか、アーキテクチャ屋さんにとっては紛らわしい略語ですね。この手の研究は学生の頃にもちょろっと調べた記憶があります。Sohi先生のとこでもやってたような。こっち方向の研究はあまり筋がよくない事が多いですよね。

*1: A Prefetch Taxonomy
*2: Friendly Fire: Understanding the Effects of Multiprocessor Prefetches
*3: Reducing Cache Pollution via Dynamic Data Prefetch Filtering
*4: Characterization of Repeating data Access Patterns in Integer Benchmarks