以下の論文を読んでみることにした：
はじめに
グラフ解析や疎行列演算などの分野で頻繁に登場する「間接メモリアクセス（IMA）」は、アクセスパターンが不規則で、キャッシュの恩恵を受けにくい。そのため、DRAMへのアクセスが増え、システム全体のパフォーマンスを大きく左右する要因となっている。
これまで、IMAに特化したハードウェアプリフェッチャが数多く提案されてきたが、どれも特定のアクセスパターンにしか対応できず、回路規模や設計の複雑さが課題となっていた。そこで本研究では、IMAの検出とスケジューリングを効率的に行う新しいソフトウェアプリフェッチャ「Magellan」を提案する。
Magellanの特徴は、ループをまたいだ依存関係グラフを抽出し、複雑なIMAパターンを的確に捉える点にある。さらに、ループの構造を理解し、現在だけでなく将来のループ反復に対してもプリフェッチを行うことで、従来手法では難しかったパフォーマンス向上を実現している。
実際に、ソーシャルネットワークやWebグラフ由来の実データセットを用いた14種類のメモリ集約型ベンチマークで評価した結果、Magellanは既存の最良ソフトウェアプリフェッチャと比べてキャッシュミスを平均25%、動的命令数を14%削減し、平均1.14倍（最大1.41倍）の性能向上を達成した。
背景と動機
IMAは、インデックス配列の値を使って別の配列にアクセスする手法であり、そのアクセス方法によって「ローカル間接アクセス」と「グローバル間接アクセス」に分類できる。
ローカルIMAは、各インデックス値が単一のデータ要素の取得に使われるパターンである。たとえば、以下のようなコードが該当する。
for (i = 0; i < num; i++) { idx = a[i]; result += x[idx]; }
一方、グローバルIMAは、インデックスが基準アドレスとなり、内側ループの変数がオフセットとして使われて複数の連続要素にアクセスするパターンである。
for (i = 0; i < num; i++) { for (j = 0; j < size; j++) { idx = a[i] + j; result += x[idx]; } }
多くのスパースアプリケーションやグラフ処理では、こうした2重ループ構造が一般的である。たとえば、ノードごとにオフセットとサイズを決め、内側ループで複数の要素にアクセスするようなケースが典型例だ。
従来のソフトウェアプリフェッチ手法は、主に内側ループのローカルIMAに着目しており、入れ子ループ構造を十分に活用できていなかった。しかし、実際には外側ループと内側ループの間に依存関係が存在し、これを解析することで新たなプリフェッチの機会が生まれる。
本研究では、現在および将来の内側ループに対して積極的にプリフェッチを発行する「inner-free prefetching」という新しいアプローチを提案する。この手法の有効性を検証するため、GAPベンチマークスイートから4つのスパースアプリケーションを選び、大規模Webグラフを用いて複数のプリフェッチ戦略の性能を比較した。
その結果、プリフェッチ戦略の効果はアプリケーションごとに大きく異なり、場合によっては性能劣化も見られた。したがって、効率的なIMAプリフェッチを実現するには、入れ子ループ構造のパターンを正確に識別し、適切な戦略を選択することが不可欠である。
