メモリプリフェッチ最適化

プログラミング

CPUの動作速度と比較して、メインメモリは遅い。
PCで使われているスカラ型CPUは内部にキャッシュを持ち、メインメモリとの動作速度の差を吸収しようとしている。
キャッシュにヒットすれば即座に読み出せるが、ヒットしなければメインメモリからの読み込み待ちとなり、膨大なウェイトが入る。
CPUのL1キャッシュは物によって違うがだいたい32byteか64byteあたりのキャッシュラインサイズで、メインメモリのどこか1つでも読まれると、32/64byteがキャッシュにロードされる。
普通は近いアドレスへのアクセスが多いだろうから、このようにすることで、連続したメモリに対するアクセスを高速化しているわけだ。
逆に言えば、完全にランダムなメモリアクセスをするプログラムはキャッシュ効率が非常に悪く、スカラ型CPUはキャッシュにヒットしなければゴミ同然で、このへんを考えることは実行速度にとっては重要だ。
まあ、L2キャッシュとかもあるし、相当運が悪くないと意識せず死ぬほどマズいコードを書いてしまうことはあんまりないとは思うが。


スーパーコンピュータもスカラ型CPUが使われるようになって久しい。
地球シミュレータが世界一になってた頃はベクトルかスカラかで騒いでいたが、そもそもベクトル型というのは大量のデータをCPUに流し込んで、膨大な演算器で一気に計算して、出力する、というのがウリのアーキテクチャなのだから、その性能はメモリの帯域幅があってこそ。
CPUの速度向上にメモリが追いつかないのは20年以上前からわかっていたことで、ピン数を増やすことでどうにかできるのはできるが、スーパーコンピュータはコストパフォーマンスが大切な市場。
つまり大事なのは、同じ金をつぎ込んで最も高い性能が得られる方式は何か、であり、お高いCPU、お高いメモリで1CPUの性能は高くなっても、金額あたりの性能が低くては意味が無い。
メモリとCPUの性能差が大きくなればなるほど、それを力技でどうにかするためのコストは膨れ上がるから、今ではメモリの速度や演算パワーの高いCPUに金をかけるより、その分を他に（主にCPUの数）に回したほうが効率いいんじゃね？って感じになっていて、実際そのほうが性能が出る。
もちろんこのへんはアプリによるから、安くて小さいスカラ型CPUがたくさんあるよりベクトル型のほうがいい分野もある。


スカラ型CPUはメモリの帯域幅は細くとどめておいて、内部キャッシュにデータを置いて引きこもり、自分の中だけで高速回転する。
従って、上のほうで述べたように、キャッシュにことごとくヒットしないプログラムは面白いように効率が下がる。
例えば1byteずつ順番にアクセスする場合を考えると、1/32(or1/64)でミスヒットする。使おうとしたデータが使えないとウェイトがかかるから、単純に順番にアクセスすればメモリの速度に依存することになる。
データのアクセスを局所的なアドレス範囲に押さえ込むことでキャッシュ効率は上がる。大きな構造体の配列をソートするときは構造体へのポインタをソートするが、ソートのキーが構造体の中にあるとキャッシュ効率が下がる。この時にポインタとソートキーを一緒に持たせてソートすれば構造体にアクセスする必要が無くなり効率は上がる。ソートキーが構造体の中にあるとそれ以外の構造体のデータはキャッシュにロードするだけ無駄だからだ。


順番にメモリアクセスする場合、キャッシュのミスヒットは避けられないが、キャッシュラインのロードを処理と平行して走らせることはできる。
どうするのかと言うと、処理をキャッシュラインサイズ単位に区切り、次に処理するアドレスの更に次を先読みしておく。これは読むだけでよい。そうすると、次のデータを処理している間にその次のデータはキャッシュラインにロードされている。当然、ロード時間より速く処理が終わってしまうとウェイトが発生して意味が無いから、この処理はそれなりに時間がかかる処理でなくてはならない。
実際にコードを書いて試してみた。これが今回の本題。

#include <windows.h>
#include <mmsystem.h>
#include <memory.h>
#include <stdio.h>

void main(void)
{
	__int64 time1, time2;
	char *buf, temp = 0;
	int i, j;

	// テキトーに初期化
	buf = (char *)malloc( 1024 * 1024 * 10 );
	for( i = 0; i < 1024 * 1024 * 10; i++ )
	{
		*(buf+i) = i;
	}

	QueryPerformanceCounter( (LARGE_INTEGER *)&time1 );

	for( i = 0; i < 1024 * 1024 * 10 / 32 - 1; i++ )
	{
//		↓これがプリフェッチのコード
//		volatile char dummy = *(buf + 32);
		for( j = 0; j < 32; j++ )
		{
			temp += *buf * temp * temp * temp;
			buf++;
		}
	}
	for( j = 0; j < 32; j++ )
	{
		temp += *buf * temp * temp * temp;
		buf++;
	}

	QueryPerformanceCounter( (LARGE_INTEGER *)&time2 );
	printf("%u\n", time2 - time1);

	return;
}

コード自体に意味は無い。
片っ端からメモリを読んで適当に掛け算しまくって足し算する。
真ん中あたりでコメントアウトしてあるのが例のプリフェッチのコードで、volatileをつけないと最適化で消されてしまうような、確実に無駄なコードだ。
上の状態で実行すると、結果はこのような数字になる。10回ほど実行した平均で、Windowsの高性能カウンタの差、つまり実行時間のようなものだ。

237343.625

んで、コメントの行を有効にするとこうなる。

220560.875

ウチのPC(AthlonII X2 240e)での数字なので、物によっては速くも遅くもなるだろうが、無駄なコードを足すことで速くなるという実例だ。


キャッシュについては、物理的なアーキテクチャによるものであるから、ハードウェア決め打ちじゃないとカツカツに最適化するのは難しい。
が、基本的な考え方というのはだいたいどのCPUでも同じで、とにかくメモリアクセスは局所化する、キャッシュラインを使わないデータで埋めない、といったあたりをちょっと考慮するだけで、実行速度は向上する。
これはハードウェア寄りのデータ構造とアルゴリズムの話であり、CPUでプログラムを走らせるならCPUのことを少しは知っておいたほうがいい、という話だ。
まあ、Rubyとか使ってたらあんまり関係ないんだけど。