キャッシュの構造や働き(上級編) - データの局所性とプリフェッチ

本連載はHisa Ando氏による連載「コンピュータアーキテクチャ」の初掲載(2005年9月20日掲載)から第72回(2007年3月31日掲載)までの原稿を再掲載したものとなります。第73回以降、最新のものにつきましては、コチラにて、ご確認ください。

データの局所性(Locality)

最初に、「キャッシュはメモリの一部の頻繁に使われるデータを格納する高速の小規模メモリ」と書いたが、これが可能な理由は、一般的なプログラムでのメモリアクセスは隣接したアドレスのメモリを比較的頻繁にアクセスするという場所的局所性(Spatial Locality)と、同じメモリアドレスのデータを比較的短時間のうちに繰り返してアクセスするという時間的局所性(Temporal Locality)があるからである。隣接するアドレスや一部のデータが短時間に繰り返してアクセスされる頻度が高ければ、その部分をキャッシュに入れれば平均より高い確率でキャッシュにヒットする。

しかし、いつもこれが上手く行くとは限らない。上手く行かない典型的な例は、オーディオデータの処理のように流れ(ストリーム)として入ってくるデータを処理する場合で、一度処理を終わるとそのデータは捨てられてしまい、再利用されないデータを扱う場合である。このようなケースでは、データはキャッシュに読み込まれるが、一度しか利用されず、局所性が生きない。但し、このようなケースでもキャッシュにはキャッシュラインサイズの単位で読み込まれるので、例えば4バイトとか8バイトというデータ要素ごとにメインメモリから読んでくる場合に比べると効率的であり、全く効果がないわけではないが、単なるフェッチバッファとして機能しておりキャッシュ本来の働きではない。

この例のようなストリームや、あるいは科学技術計算でよく使われる行列などでは、次にどのアドレスのデータが必要になるかが予め分かっていることが多い。また、単純に次のアドレスのデータが必要となるというケースも多い。このように次に必要なデータのアドレスが分かっている場合に、事前にキャッシュにデータを持ってくるのが、次に述べるプリフェッチである。

話は多少それるが、スパコンの性能を多面的に評価するHPC Challengeベンチマークの中にRandom Updateというプログラムがある。このプログラムは暗号解読の性能律速部分をモデル化したものと言われているが、メモリの全域にわたって全くランダムにアクセスして内容を書き替える。このようなプログラムでは、場所的局所性も時間的局所性も無く、データキャッシュが効果を発揮できない例である。しかし、このケースでも命令は局所性があり、命令キャッシュは有効である。

プリフェッチ(Pre-fetch)

プロセサが次の命令を要求したり、必要なデータを要求したりした場合は、既にその情報がキャッシュに無ければ、前述のようにメモリからキャッシュにデータが読み込まれる。しかし、その場合は、遅いメモリからデータを読み出してくるので、時間が掛かるという問題がある。

次に必要となるデータがどれであるか判らない場合は、やむを得ないが、次に必要になりそうなデータが、確実ではなくともある程度判っている場合は、本当に必要になる前にキャッシュにデータを入れておけば時間が節約でき性能があがる。という考えに基づいて、事前にキャッシュにデータを読み込むのがプリフェッチという手法である。

プリフェッチには、ハードウェアが勝手に推測してやるものと、プリフェッチ命令という専用の命令を設けて、ソフトウェアがその命令を発行してデータをキャッシュに読み込む方法があり、最近の高性能プロセサでは、これらの両方をサポートしているのが普通である。

プログラムの命令にしろ、データにしろ、連続的に番地が増加する方向にメモリをアクセスするというのが基本的なメモリアクセスパターンである。このため、ハードウェアによるプリフェッチは、ある番地をキャッシュに読み込むと、その次のキャッシュラインも使われるという見込みのもとに、自動的に次のキャッシュラインも読み込むというNext Line Fetchという方法が一般的に用いられる。

また、2次元以上の配列を扱う場合は、一方の添え字の方向にはメモリアドレスが連続しているが、もう一方の添え字の方向には一定間隔の離れたアドレスになる。このようなケースに対しても効率よく動くように、メモリアクセスの番地を監視し、一定間隔のアクセスがある程度続くと、その間隔で次のキャッシュラインを自動的に読み込むというプリフェッチを行うプロセサもある。

しかし、ハードウェアで自動的にやるプリフェッチはこの程度が限界であり、より複雑なパターンのアクセスの場合に精度の良いプリフェッチを行うには、プリフェッチ命令が使われる。例えば、ループを回る処理の場合、ループの開始時点で、今回ではなく次回に必要となるデータに対してプリフェッチ命令を発行し、メモリアクセスを開始する。そうすると、その回の処理を終わり、ループバックして次の回の処理を開始するころには、プリフェッチしたデータがキャッシュに入っており、キャッシュミスによるメモリアクセスの待ち時間なしに処理を開始することができる。ループの最後では、無駄に次のデータがプリフェッチされたりするが、単にキャッシュに読み込まれるだけであり、計算処理結果の正しさには影響しない。また、メモリアクセス時間がループ1回の処理時間より長い場合は、数回あとのデータをプリフェッチするようにすれば良い。

このように次に使われるデータの番地が判っている場合には、プリフェッチを使って事前にキャッシュにデータを持ってきておけば、キャッシュミスが起こらず、性能を上げることが出来る。