初めに コンパイラの最適化 プログラミング :: 高速なプログラムを書く為に :: メモリ

3. メモリ

さて、プログラムの最適化で一番重要になってくるのは、メモリです。 はっきり言って、数値計算をするプログラムの一番のボトルネックはメモリアクセスです。 下手なプログラムを書くと、計算時間の殆どがメモリアクセスの時間という事になりかねません。

昔は、メモリの動作速度は高速でその様な事はなかったのですが、 最近では CPU の性能向上が激しく、メモリに追いつき追い越し物凄い差を付けてしまいました。 CPU の動作について行ける様な速さで動作するメインメモリは高価になってしまい作れません。

まあ、値段の問題は抜きにしたとしても、CPU の動作は速すぎます。 これは、少し計算してみれば直ぐに分かります。

今売られている CPU では、コアのクロック周波数が高い物では 4GHz になります。 例えば 4GHz の CPU で 1 clock の間に光が進む距離を考えると、 3×1010 [cm/s] / 4×109 [Hz] = 7.5 cm になります。 CPU からメインメモリまでの距離を考えると、(マザーボードによるとは思いますが、) 1 clock というのは、CPU から見てメモリが事象の地平線の中に入って来るか来ないか位の時間です。

更に、メモリーからデータを読み出す為には、読み出す要求を届けて結果を受け取るという過程が必要なので、 7.5cm という距離は往復で考えなければなりません。 メモリが瞬時に反応して結果を返信したとしても、1clock 以内に CPU がデータを読み出すには CPU とメモリの間の距離は 3.75cm 以上離れていては行けません。然し、そもそもメモリの基盤からして明らかに 4cm 以上の大きさが在ります。 1clock でメモリからデータを読み取るというのは、抑も相対論的に不可能な訳です。

其処で、現在の殆どの CPU ではキャッシュという機構を導入して、 少しでもメモリ事情を良くしようという工夫が為されています。 高速なプログラムを書くには、このキャッシュの機構がちゃんと働く様に考えて設計をしなければなりません。 数値計算の様な大量のデータを扱う様なプログラムの場合、 安易にプログラムを記述するとキャッシュが全然働かなくなって物凄く遅いプログラムになってしまいます。

キャッシュの仕組み

キャッシュの考え方を簡単に言うと「近い将来メモリアクセスされる確率が高そうな場所を予め CPU に取り込んでおこう」という物です。 キャッシュがちゃんと働くようにするためには、キャッシュ機構がメモリアクセスを予測しやすい様な、そういうコードにする必要があります。 その為には、キャッシュがどの様にしてメモリのアクセスを予測するのかという事を知っていなければなりません。

メモリ階層

キャッシュは物理的には、メモリの階層構造として実現されています。 例えば一例としては以下の様になります。

メモリ階層

※ CPU によっては、キャッシュが L3 キャッシュまであったり、 L1 キャッシュのコード用とデータ用を区別していなかったり、細かい点は色々です。 最近ではマルチコアになった為に、「L○キャッシュはコア毎に用意されているが、 L×キャッシュは全てのコアで共有している」とか更に色々な状況になっています。

↓ AMD の Phenom (4 コア) の場合の図。調べたら下みたいな形になって居るみたいです。 (参考: 「Phenom FX」「Phenom X4」のCPUダイ)

ダイ上での配置

キャッシュ機構は、アクセスする確率の高そうなデータは、出来るだけ図の右の方にコピーを配置する訳です。

メモリ階層

データの局所性

今迄アクセスの確率がどうのこうのと言ってきましたが、 「アクセスの確率が高そうな」というのはどうやって判断すればよいのでしょうか?

理想的には、プログラムのコードを完全に解析してどの瞬間に何処に触るかという時間割を作成してしまえば、完璧です。 その時刻が近付いてきたら勝手にキャッシュにデータを送る様にしておけば、 演算回路から見たら「何時でも触りたいデータが直ぐそばにある」状態になっています。 然し、これは開くまで理想でしか在りません。プログラムの動作を解析するのは、単純にプログラムを動作させる事よりもずっと大変です。 しかも、もしプログラムの完全な解析結果があるのであれば、 わざわざプログラムを動作させなくても実行結果が分かっているという事になってしまいます。

其処で、適度に簡単でまあまあアクセスの確率の高い場所を予想できるような「キャッシュアルゴリズム」が必要になってくる訳です。 とは言っても、一般のプログラムに対してアクセス位置を具体的に予想する事が出来る様な、まともなアルゴリズムは現在存在していません。 現在のキャッシュ機構は、「或る場所がアクセスされたら、 その近隣も近いうちにアクセスされる可能性が高いだろう」(データの局所性) という事のみしか考慮していません。 それでも、この予想は簡単な割によく当たるので、現在の CPU は快適に動いているのです。

所が、このデータの局所性を無視した、メモリ上のあっちやこっちを出鱈目に触るプログラムが存在したとします。 すると、キャッシュが全然働かないので、毎回メインメモリまでデータを取りに行かなければならなくなります。 そうすると、百倍ぐらい動作が遅くなると言う事態も充分考え得るのです。

キャッシュの動作

具体的な動作について説明します。 例えば、今欲しいデータ (物理アドレス X のデータ) が L2 まで来ていたとします。 其処で、欲しいデータに触ろうとするとどの様な過程を経てデータが得られるのでしょうか?

  1. 読み出し
    1. 先ず、コアがアドレス X のデータが欲しい! と要求を出します。
    2. L1 に アドレス X のデータのコピーがキャッシュされているかどうかを見ます。
    3. 今回の状況では L1 にデータは置いていません (キャッシュミスと言います)。 仕様がないので、次のキャッシュに見に行きます。
    4. L2 にアドレス X のデータのコピーが置いてあるかどうかを確認します。
    5. 今回は L2 にデータがあります (キャッシュヒットと言います)。 従って、データを其処から読み出します。
  2. キャッシュ内容の更新

    データが見つかったら、データを読み出すのと並行してキャッシュの内容が自動的に更新されます。 (キャッシュ内容の更新は、演算部がやる訳ではなくてメモリが自立して行う物なので、 本体の計算が遅くなったりと言う事はありません。)

    キャッシュの更新で何をするのかというと、 今回触ったアドレス X のデータとその周辺のデータのコピーを L1 に作成するのです。 周辺のデータというのは、大体数十バイトから百バイト程度のブロックになります。 周辺のデータもまとめてコピーするのは、先程説明した「局所性」に拠って、 アドレス X に触った時にはその周辺のアドレスのデータに触る確率も高いと期待されるからです。

    1. L1 に空きを作る為に、L1 で既に保持しているデータの一部を選んで捨てます。

      どのデータを捨てるのかという事を決める為には、また、色々アルゴリズムがある訳ですが、 基本的には、最近余りアクセスされていないデータや一番昔に L1 に持ってきたデータなどが捨てられます。

    2. L2 にあったデータと、その周辺のデータを纏めて L1 に移します。

      L2 にあったデータは捨てるという仕組みの物もあれば、 残しておく (L2 と L1 に同じ物がある) という仕組みの物もあります。

    これで、次に再びアドレス X のデータか、 その近くのデータを触ろうとした時には、 当該データが L1 に存在するという事が保証できるようになるのです。

例: キャッシュミスによる性能低下

キャッシュが働かない様な変なデータ配置にすると速度が遅くなります。 データの配置と速度の関係を実際に見てみましょう。

下のプログラムでは、 動的配列 data にアクセスする際に data[skp*i] として、 skp を変化させて同じ計算を実行させています。

#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>

const int N=0x800000;
const int M=0x000100;
const int W=0x001000;
double* data;

void test(int skp){
	std::clock_t t0=std::clock(); // 【時間計測開始】

	for(int k=0;k<W;k++){
		// 初期化
		for(int i=0;i<M;i++)data[skp*i]=0;
		data[0]=1;

		// 適当な計算
		for(int i=2;i<M;i++)
			for(int j=1;j<i;j++)
				data[skp*(j+1)]+=data[skp*j];
	}

	std::clock_t t1=std::clock(); // 【時間計測終了】
	int tik=int(0.064*(t1-t0)+0.5);
	printf("Block Size: %d bytes; Tick: %d;\n",sizeof(double)*M*skp,tik);
}

int main(){
	std::srand(2010);
	data=new double[N];

	for(int s=1;s<=N/M;s<<=1)test(s);

	printf("C\n");
	delete[] data;
	return EXIT_SUCCESS;
}
Block Size: 2048 bytes; Tick: 71;
Block Size: 4096 bytes; Tick: 71;
Block Size: 8192 bytes; Tick: 71;
Block Size: 16384 bytes; Tick: 71;
Block Size: 32768 bytes; Tick: 71;
Block Size: 65536 bytes; Tick: 79;
Block Size: 131072 bytes; Tick: 82;
Block Size: 262144 bytes; Tick: 83;
Block Size: 524288 bytes; Tick: 92;
Block Size: 1048576 bytes; Tick: 101;
Block Size: 2097152 bytes; Tick: 113;
Block Size: 4194304 bytes; Tick: 118;
Block Size: 8388608 bytes; Tick: 119;
Block Size: 16777216 bytes; Tick: 134;
Block Size: 33554432 bytes; Tick: 152;
// 以下は
const int M=0x000400;
const int W=0x000100;
// の時の結果
Block Size: 8192 bytes; Tick: 74;
Block Size: 16384 bytes; Tick: 73;
Block Size: 32768 bytes; Tick: 77;
Block Size: 65536 bytes; Tick: 79;
Block Size: 131072 bytes; Tick: 81;
Block Size: 262144 bytes; Tick: 81;
Block Size: 524288 bytes; Tick: 82;
Block Size: 1048576 bytes; Tick: 82;
Block Size: 2097152 bytes; Tick: 96;
Block Size: 4194304 bytes; Tick: 447;
Block Size: 8388608 bytes; Tick: 454;
Block Size: 16777216 bytes; Tick: 465;
Block Size: 33554432 bytes; Tick: 431;

実行した CPU の情報は以下の様になります。

メモリ階層

L1 キャッシュが 32KiB で、L2 キャッシュが 2MiB となっています。

上記の結果をグラフにすると以下の様になります。 横軸はメモリアクセスをする範囲の大きさ [bytes] (ログスケール)で、 縦軸は実行時間に比例する量です。

L1 キャッシュの限界 L2 キャッシュの限界

左側のグラフを見ると L1 キャッシュの限界の 32KiB 辺りの所で少し上がっている様に見えます。 つまり、32KiB より小さい所では L1 がちゃんと働いているけれど、 32KiB より大きい所では L1 が働かなくなって L2 に速度が依存する様になっているのです。

※ 「大して変わらないじゃん」と思われるかも知れませんが、 グラフに表示しているのはメモリアクセスの時間だけでなくて他の計算をしている時間も含まれています。 L1 キャッシュの場合には 2clk でデータを取得出来て、L2 の時は 20clk 位時間が掛かると考えると、 L1 が効いている領域では大体 99% 位は他の計算に掛かっている時間という事になります。 そう考えるとメモリアクセスの時間が滅茶苦茶増えている様に見えます。 全体としては余り変化がないというのは事実ですが。

さて、左側のグラフで見ると L2 の限界の 2MiB の近くの山がはっきり見えていません。 …どうやら、点を疎らに取りすぎた所為で全てキャッシュに載る事が出来てしまったようです。 少し点を密に取り直して計り直したのが右の図です。 はっきりと 2MiB の所に崖があるのが見えます。

キャッシュの存在について実感が湧いたでしょうか…? もしかすると、今迄にもキャッシュによる効果を経験した人がいるかも知れません。 例えば、流体計算で格子の数を二倍にしてみたら、途端に計算の速度が落ちてしまったなどという事があったら、 それは多分キャッシュにデータが載りきらなくなった為です。

プログラム例

キャッシュの仕組みについて理解したら、 実際にプログラムを書いて動作を確認してみる事にしましょう。 考えなければならないのは以下の二項目です。

本当に真面目に速度をチューニングするのであれば、 計算に使用するプロセッサのキャッシュのサイズも考慮に入れて、 データの配置を考える必要があります。

例: 一時変数は自動変数として

// ×
double x;

void f(){
	x=100;
	... /* x を使用した計算 */
}


// 
void f(){
	double x=100;
	... /* x を使用した計算 */
}

自動変数 (ローカル変数として static 等付けずに宣言すると自動変数になる) は、 メモリ上のコールスタックというデータ構造の中に確保されます。 このコールスタックの中には、計算の一時データや関数呼び出しの履歴などの情報が含まれていて、 常に使用されているメモリ領域です。 更に、自動的に近い所で使われている変数は近い場所に配置される様になっています。 従って、キャッシュヒットの確率が高いのです。

逆に、変数のインスタンスをヒープ領域に確保したり (=malloc や new で確保したり)、 静的領域 (グローバル変数, static 変数) に宣言したりして、頻繁に使用すると、 あちこちにデータが散らばってしまいキャッシュを浪費してしまいます。

その為、一時的にしか使用しない様な変数の場合にはローカル変数を使用する様にしましょう。

※ 但し、巨大なデータはヒープ領域に確保する様にしましょう。 スタックには最大サイズが設定されているので、 不用意にスタック領域に確保するとスタック溢れでプログラムが落ちます。 スタック溢れにならなくても、スタックに巨大なデータを置くと、 スタック自体でキャッシュミスが起こったりして遅くなります。

例: 二次元配列の扱い

二次元配列の要素を触る場合には、その触る順番に気を付けましょう。 上に書いた通りに、「メモリ上で連続になる様な」順番で触る様にします。

double a[M][N];

// A: ×
for(int y=0;y<N;y++){
	for(int x=0;x<M;x++){
		a[x][y]=なんとかかんとか;
	}
}

// B: 
for(int x=0;x<M;x++){
	for(int y=0;y<N;y++){
		a[x][y]=なんとかかんとか;
	}
}

二次元配列 double[M][N] というのは、実は、配列 double[N] の配列であった事を思い出しましょう。

配列構成

配列の要素の並び方が上のようになっていることを思い浮かべれば、 上のプログラムの B の方でなければならないという事が分かると思います。

※ FORTRAN では逆 (転置) になっているという事に注意しましょう。

例: 格子のデータの配置

同じセルの情報は一箇所に

流体等で格子のデータを作る場合、v_x[x][y], v_y[x][y] 等とするのは良くないです。

// ×
double v_x[M][N];
double v_y[M][N];
double rho[M][N];

// 
struct{
	double v_x;
	double v_y;
	double rho;
} data[M][N];

明らかに、v_x[x][y] と v_y[x][y] 等は近いタイミングで触る確率が大きいので、 近くに配置するべきです。

ブロック化

格子の計算をする場合には、必ず隣接セルのデータを参照する必要が出てきます。 例えば三次元の格子 M×N で単純に配列の中にデータを配置した場合、 右と左のセルのデータに関してはメモリ上で連続して配置されているので問題はありません。 しかし、上隣の下隣のセルのデータについては、N セル分離れた所に存在しています。 N が小さい時にはこれでも余り問題は起きないかも知れませんが、 N が大きくなってくるとキャッシュの動作が不安になってきます。

其処でどの様な事をするかというと、領域を適当に分割してブロック化してしまうのです。

ブロック

ブロックは、キャッシュに充分入りきるぐらいの大きさにしておきます。 (ギリギリの大きさは駄目です。プログラムは、格子のデータ以外にも色々な所にメモリアクセスする筈なので、 その分の余裕も残しておかなければなりません。) この様にしておけば、ブロックとブロックの境界を除いては、隣接セルはメモリ上で近いところにあることが保証されます。

ブロックとブロックの境界に関しては、ブロックの領域を多少オーバーラップさせて配置し、 ブロックについての計算を始める前に境界をコピーするという事も為されます。

また、この様にブロック化しておけば、プログラムを並列化する際にも楽になります。 ブロック一つに対して一つの実行単位を割り当てれば、 データの独立性・局所性を保ったまま並列化が可能だからです。

データ構造について

他は、茲の状況に応じて自分で考えて、キャッシュが出来るだけ働く様なデータの配置にする必要があります。

その為には、様々なデータ構造に対する知識があると心強いです。 特に、データ構造のメモリの使い方について知っておくと良いです。 多様なデータ構造の中から、その時に丁度あっているデータ構造を選択して使用しましょう。 更に、慣れているのであれば、問題の状況にあったデータ構造を自分で作成するという事もすると、 よりプログラムを高速に動かす事が出来る様になるでしょう。

…でも、データ構造は物凄く沢山あって、一つ一つについても語る事が沢山あるので、 茲では紹介しません。各々勉強して下さい。

4. その他

メモリと関連する物以外で、 高速にする為に参考となりそうな事を書いておきます。 思い付いた物だけですが。

整数で出来る所は整数で

浮動小数点の計算よりも、整数の計算の方が一般的に高速です。 整数で計算できるところは可能な限り整数で計算する様にしましょう。 (但し、プロセッサによっては、整数の割り算よりも浮動小数点の割り算の方が速い事もあるようです。 気になる人は、自分のプロセッサではどちらの方が速いのか調べてから除算すると良いかも知れません。)

void f(int a,int b){
	// ×
	double x=(0.5*a)*b;
	
	// 
	double x=0.5*(a*b);
}

※ 浮動小数点数と整数の間のキャストにも時間が掛かる事に注意して下さい。 従って、浮動小数点数をわざわざ整数にキャストして計算してから、 再び浮動小数点に直すというのは余り意味ないです。

条件分岐は出来るだけ少なく

条件分岐は可能な限り無くす様にしましょう。 例えば、複数の条件分岐を一つに纏めたり、ビット演算で代用したりする事が出来ます。 また、||&& の右辺が簡単な式の場合には、 |& で代用してしまうという事も考えられます。

// ×
double a=hoge?p:q; // ← 分岐 1
double c=a*10;
double b=hoge?c:r; // ← 分岐 2

// 
double a,b,c;
if(hoge){ // ← 分岐 1
	a=p;
	c=a*10;
	b=c;
}else{
	a=p;
	c=a*10;
	b=r;
}

これは、CPU の命令を読み込んでから実行するまでの仕組みに関係しています。

実は、どんなに簡単な命令でも、 命令を読み込んでその命令の実行を完了する迄に 1 clock だけで済むという事はあり得ません。 実際のプロセッサの中では、命令はバケツリレー式に処理されるのです。 命令を読み取る人、 命令を解釈する人、 命令を更に細かい命令に分解する人、 命令を実行する為に CPU 内にある回路を繋ぎ変える人、 命令を実際に実行する人、 命令の結果を特定の場所に戻す人、 …みたいな感じになっていて、1 clock 毎に次の人に手渡される訳です。

パイプライン処理

CPU のこの処理の仕方をパイプライン処理と言います。 パイプライン処理によって、1 clock 以上掛かる様な複雑な命令処理でも、 実質上一命令辺り 1 clock から実行する事が可能になっているのです。 (それでも 2 clock 以上掛かる命令も沢山ありますが。)

さて、条件分岐がある場合はどうなるでしょうか? 条件分岐命令の実行が完了するまでは、条件分岐命令の次の命令は確定していません。 命令を読み取る人は困ってしまいます。 実際には、命令を読み取る人は、取り敢えず憶測で、適当に分岐先を選んで読み取ってしまいます。 これを分岐予測と言います。 分岐予測は、基本的には過去の分岐の履歴を溜めておいて、其れを見て判断します。 分岐予測の性能は CPU の性能に大きく関わってくる為、 分岐予測については色々な研究が為されて居るみたいで、色々と複雑な予測方法があるみたいです。 (参考: 分岐予測 - Wikipedia)

条件分岐命令の結果、予測が正しかったと判明した場合はその儘命令列の実行が継続されます。 問題は、予測が外れた場合です。 予測が外れた場合には、其れまでに憶測で読み込んでしまった命令を全て破棄して、 命令を再度読み取り直さなければなりません。 すると遅延が生じてしまい、その分実行が遅くなってしまいます。

分岐予測ミス

例えば Pentium 4 の場合には、分業化が細かく 20 ステージある (パイプラインに 20 人の人がずらりと並んでいる感じになっている) ようです。 そうすると、予測ミスによって 20 clocks 程度の遅延が生じてしまいます。 (Core 2 Duo だと少し浅くなって 14 ステージだそうです。)


初めに コンパイラの最適化 プログラミング :: 高速なプログラムを書く為に :: メモリ
起稿 2010-02-14
© 2010, K. Murase myoga.murase@gmail.com
inserted by FC2 system