IMP: Indirect Memory Prefetcherという論文があり、これはGather/Scatterに対してどのようにプリフェッチを出すかというものを提案した論文になっている。ちょっと読んでまとめてみようと思う。
https://ieeexplore.ieee.org/document/7856597
問題のモチベーションになっているのは、疎行列アクセスなどで使用される、データに対して間接的にアクセスするシーケンスである。
for (int i = 0; i < N; i++) { B[A[i]]; }
上記のようなアクセスにおいて、 ]のアクセスは配列をなめていくだけなので非常に単純であり、ストライドプリフェッチャで簡単に予測することができる。
一方で、
B[A[i]]のようなアクセスは簡単にBのアクセスがAの値に依存するため、非常に予測しづらい、というか基本的に予測できないと考えて良い。
このため、本論文では、Bのアドレスを予測することをあきらめ、A[i]を如何に早く検出してアドレスを計算し、Bのプリフェッチを出すかというところに焦点を当てたIMP(Indirect Memory Prefetcher)というものを提案している。
次は、IMPのコンポーネントを見ていくことにする。
