IMP: Indirect Memory Prefetcherという論文があり、これはGather/Scatterに対してどのようにプリフェッチを出すかというものを提案した論文になっている。ちょっと読んでまとめてみようと思う。
https://ieeexplore.ieee.org/document/7856597
前回の続き、どのようにA[B[i]]のアドレスを算出するのかを考えていく。この配列Aは最終的にどのような式でアドレスが計算されるのかを定式化する。
ADDR(A[B[i]]) = B[i] * Coeff + BaseAddr
この時、CoeffはA配列の各要素のサイズ、BaseAddrはA[0]のアドレスとなる。
ここで、CoeffとBaseAddrが決定できれば、B[i]に基づいてプリフェッチが出せるということがわかる。
したがって、ポイントとなるのは:
B[i]にアクセスするロード命令はどれなのか。B[i]に継続するA[B[i]]をロードする命令はどれなのか
を算出するということになる。特にB[i]に続くA[B[i]]をどのようにとらえるのかは、パタンマッチのような形で進めていくことになる。
以下がパタンを検出するためのテーブルだ。
まず、B[i]に相当するストライドを持つロード命令を検出すると、IPD(Indirect Pattern Predictor)の新しいエントリに格納する。
この時、idx1にB[i]に相当するアドレスを書き込む。このとき、B[i] = idx1 = 1であるとする。
この命令に続くロード命令でミスを発生したものについて、BaseAddr Arrayに相当するテーブルにそのアドレスをPushし、候補となるBaseAddrを検出する。
例えば、B[i]のロードに続いて0x100, 0x120 ...にアクセスした場合、Coeffの値の候補(=4, 8, 16, 1/8)に応じてBaseAddrの候補を逆算しテーブルに書き込んでいく。
ここでは、0x100にアクセスした場合には、Coeff=4で0xfc, Coeff=8で0xf8がBaseAddrの候補となる。
さらに、0x120にアクセスした場合には、Coeff=4で0x11c, Coeff=8で0x118がBaseAddrの候補となる。
さらに、同様にB[i+1]へのアクセスがあった場合（これは同じPCでのアクセスであると思われる）、このときの値をidx2に書き込む（ここではB[i+1]=16であるとする）。
さらに同様に後続のロード命令でミスが発生したものをテーブルに書き込み、BaseAddrの候補を計算する。
例えば後続のアドレスが0x13cである場合、B[i+1]=16の場合BaseAddrを逆算すると、Coeff=4で0xfcが候補となり、上記の0x100のアクセス時に算出したBaseAddrと一致する。
これにより、上記の0x100と0x13cが同じA[B[i]]へのアクセスであり、さらにCoeff=4, BaseAddr=0xfcであることがわかる。
そこで、この情報に基づいてB[n]のアドレスが決定時にプリフェッチを出すということになる。
