IMP: Indirect Memory Prefetcherという論文があり、これはGather/Scatterに対してどのようにプリフェッチを出すかというものを提案した論文になっている。ちょっと読んでまとめてみようと思う。
https://ieeexplore.ieee.org/document/7856597
前回はプリフェッチのためのベース情報の取得に成功したので、次はプリフェッチの生成に取り組む。
3.2.3 間接プリフェッチ
図5にPTの内容を示す。各エントリーの一部はストリームテーブルを構成する。これは、ストリームにアクセスする命令のプログラム・カウンタ（pc）と、ストリームから最近アクセスされたインデックスのアドレス（addr）を格納することで、インデックス・ストリームを追跡する。 また、閾値に達したときにストリーム・プリフェッチをトリガするストリーム・ヒット数（hit cnt）も追跡する。
各PTエントリの残りの部分は、間接アクセスを追跡する間接テーブルを構成する。各エントリのこの部分は、IPDがこれを有効にし（すなわち、enable = Trueを設定し）、シフトとBaseAddrを格納するまで、非アクティブである。IMPがプリフェッチを開始する前に、このパターンがプリフェッチする価値があるという確信を高める必要がある。
IMPは、エントリに一致するインデックスアクセスを検出すると、インデックス値をインデックスフィールドに書き込む。それ以降のアクセスごとに、インデックス、シフト、BaseAddrに従って、アドレスが期待される間接アクセスアドレスに一致するかどうかをチェックする。一致した場合、IMPは飽和カウンタhit cntをインクリメントする。IMPが一致を見つける前に後のインデックス・アクセスでインデックスを上書きした場合、カウンタをデクリメントする。 飽和カウンタ(hit cnt)が閾値に達すると、IMPは間接プリフェッチを開始する。このようなPTエントリにマッチするインデックスアクセスごとに、IMPはそのパターンに対して1つ以上のプリフェッチを発行する。プリフェッチ距離（現在のアクセスとプリフェッチするアクセスとの間のアクセスストリームの距離）は、最初は小さく、同じパターンへのヒットが増えるにつれて直線的に増加する。プリフェッチ距離∆が与えられると、IMPはインデックス要素B[i+∆]を読み取り、式(2)を使用して間接プリフェッチアドレスを計算する。IMP はプリフェッチされたキャッシュラインをキャッシュに入れるが、代わりにプリフェッチバッファを使用することもできる。
従来のストリームプリフェッチャと同様に、IMP はデータを共有状態または排他状態のいずれかでロードできる。この決定には、単純な読み書き予測器を使用する。IMPはSIMD命令（スキャッタやギャザなど）にも使用できるが、それに応じてアーキテクチャを調整する必要がある。 プリフェッチャは仮想アドレスでも物理アドレスでも動作可能である。物理アドレスで動作させると、アドレス変換の必要性がなくなるが、ページ境界でプリフェッチを停止せざるを得なくなる。仮想アドレスで動作させると、長いストリームが可能になる。本稿では、間接的なアクセスは異なるページに触れる可能性が高いため、IMPはストリーミングと間接的なプリフェッチの両方のアドレスを仮想空間に生成する。その結果、IMPはアドレス変換をサポートするキャッシュ、つまりL1キャッシュに接続する必要がある。
3.3 最適化
次に、IMPの最適化をいくつか紹介する。
3.3.1 入れ子ループ
間接プリフェッチが機能するためには、ストリーミングパターンと間接パターンの両方をキャプチャする必要がある。通常、検出には複数のループ反復が必要であり、この学習フェーズではプリフェッチは行われない。短いループの場合、学習フェーズの長さがIMPの性能向上を制限する（リスト1）。
for (int i = 0; i < N; i++) for ( int j = f(i); j < f(i+1); j++) load A[B[j]]
セクション3.2.3ですでに示したように、この問題に対する我々の解決策は、ストリーム・パターンをストリーム・アクセスのPCに関連付けることである。これは既存のストリームプリフェッチャ [6] では一般的である。
IMP は間接パターンを検出すると、インデックス・アクセスの PC を PT に格納する。アプリケーションが外側ループの反復を完了し、次のループを開始するとき、インデックス配列へのストリーミングパターンは中断され、jの値が一時停止を見るため、おそらく異なるポイントで再開される。しかし、インデックス・アクセスは以前と同じ命令（PC）から行われる。したがって、IMPはパターンを再学習するのではなく、ストリーム・テーブルのaddrフィールドを更新することで、インデックス配列内の位置を変更するだけである(図5)。
3.3.2 マルチウェイおよびマルチレベル・インダイレクト
多くの間接アクセスはA[B[i]]パターンに厳密に従うが、このパターンのいくつかの変形も観察され る。
以下のコード・スニペットに示すように、マルチウェイ間接処理とマルチレベル間接処理である。マルチウェイ・インダイレクト（リスト2）では、2つの間接パターンが同じインデックス配列を使用する。マルチレベル・インダイレクト（リスト3）では、間接アクセスで読み込んだ値が別のデータ配列のインデックスになる。このようなプリフェッチ値の追加的な使い方を、セカンダリー・インダイレクトと呼ぶ。
for (i = 0; i < N; i++) load A[B[i]] load C[B[i]]
for (i = 0; i < N; i++) load A[B[C[i]]]
これらの複雑なパターンをサポートするために、PTの構造を変更する。具体的には、PTのいくつかの項目を二次間接表現に特化する。また、図6に示すように、各エントリーにいくつかのフィールドを追加する。
ind型は、エントリーが一次（デフォルトの間接パターン）か、多方向か、多レベルかを示す。残りのフィールドは、関連するPTエントリーを、プライマリーエントリーをルートとするツリーでリンクする。next wayフィールドとnext levelフィールドは子のPTエントリ番号を保持し、 prevフィールドは親エントリを示す。
プライマリパターンのプリフェッチがトリガーされると、IMP はそれに接続されているセカンダリパターンのツリーをトラバースする。IMPは、すべての2次間接が親と同じインデックス値を共有しているため、親に対するプリフェッチの直後に、各2次間接に対してプリフェッチを発行する。各第2レベル間接について、IMPは親のプリフェッチによってアクセスされたインデックス値を必要とするため、親のプリフェッチが戻った後にのみ第2レベルのプリフェッチを発行できる。 IMPはプライマリパターンと同様にセカンダリパターンを検出する。IMPはプライマリパターンを検出した後、IPDに別のエントリを割り当てることでセカンダリパターンを検出しようとする。
