メモリアクセスパターン

超高性能プログラミング技術のメモ（１０）
技術を忘れないようにノートに書き残しています。

かなり時間が経ってしまいましたが、案外読まれているようなので、また少しずつ追加していこうと思います。プログラミング初心者向けではないので、読者はいないだろうと思っていました。

今回は、メモリアクセスパターンの違いによる性能の違いについて簡単に書きたいと思います。

メモリアクセス速度

パソコンを使っていて処理速度が遅いと、メインメモリ容量を増やして解決しようと考えがちです。しかし、メインメモリ容量を増やすと、メモリアクセス速度は低下していきます。

なぜ、容量が増えると速度が落ちるのかというと、データの格納場所を検索する処理時間が増えるためです。

森博嗣の小説「すべてがFになる」（1996）の中では、128KBのメモリが大容量として扱われていますが、今や40倍〜80倍の4MBや8MBが当たり前の世界になりました。このため、数十倍はメモリアクセス速度が低下（メモリが「遠い」と表現されます）しています。

逆に、CPUの速度は、クロック周波数だけで比べてみても、Pentium Proの60MHzから、Skylakeの4.0GHzまで、100倍くらい速くなりました。これは、100倍速いメモリアクセスを必要としていることを表しています。

CPU速度は速くなったのに、メモリアクセス速度が低下したため性能がでない問題（メモリウォール問題といいます）を解決するために、導入されたのが多層キャッシュメモリです。

そのため、「いかにキャッシュメモリを効率的に利用するか」が高性能化のポイントになっています。

参考：超高性能プログラミング技術のメモ（２）−キャッシュ構造とアラインメント

シーケンシャル・アクセス

シーケンシャル・アクセスとは、メモリ配置の順序にデータにアクセスすることです。自動的にプリフェッチ（メインメモリからキャッシュメモリへのデータ転送）されるキャッシュライン（転送されるデータ、32B×2ラインが転送される）を無駄にすることなく使用するため、最も効率の良いアクセスパターンです。

例として、C言語で２次元配列をコピーする場合を考えます。

#define M 512
#define N 512
void main(){
  double x[M][N] = {0};
  double y[M][N] = {0};
  for( int i=0; i<M; i++ ){  
    for( int j=0; j<N; j++ ){
      y[i][j] = x[i][j];
    }
  }
}

C言語の２次元配列は、２次元目の添字（上記コードではj）がメモリ配置の連続方向になっているため、上記コードは、添字jのループでシーケンシャル・アクセスをしていることになります。

ストライド・アクセス

ストライド・アクセスとは、一定の間隔でジャンプしてメモリを使用するアクセスパターンです。キャッシュラインの先頭部分だけ使用し、キャッシュラインの後続部分を使用しないため、とても非効率になります。

倍精度浮動小数点のdouble型は１要素が8Bなので、8要素以上の間隔でストライド・アクセスすると、キャッシュライン容量64Bのうち87.5%（56B）を使用しません。

上記同様に、C言語の２次元配列のコピーを例にします。

#define M 512
#define N 512
void main(){
  double x[M][N] = {0};
  double y[M][N] = {0};
  for( int j=0; j<N; j++ ){  
    for( int i=0; i<M; i++ ){
      y[i][j] = x[i][j];
    }
  }
}

シーケンシャル・アクセスのコードで、添字iループと添字jループを入れ換えただけですが、これはストライド・アクセスになります。

この例では、添字jの連続メモリ配置の方向に、512要素×8B＝4KBのデータが配置されているため、添字iループは4KBずつジャンプしながらメモリアクセスすることになります。そのため、キャッシュラインは全く有効活用できません。

ランダム・アクセス

ランダム・アクセスとは、その名の通り、ランダムにメモリにアクセスするパターンのことです。連想配列とか間接参照といった方法でプログラムが書かれていると、多くの場合、ランダム・アクセスになります。

ランダム・アクセスも、キャッシュラインの先頭部分だけしか使用しないため、とても非効率になります。

例えば、以下のような、間接参照によるプログラムはランダム・アクセスになります。

#define M 512
#define N 512
#define L 1024
void main(){
  double x[M][N] = {0};
  double y[M][N] = {0};
　i[L] = {1,4,8,2,13,23,290,248,0,432,....};
  j[L] = {0,133,24,5,5,29,40,403,33,278,....};
  for( int k=0; k<L; k++ ){
    y[ i[k] ][ j[k] ] = x[ i[k] ][ j[k] ];
  }
}

間接参照は、ループの反復数が減るので、配列要素の大部分が０な疎データの場合によく用いられます。しかし、疎データが密データ（全配列要素が０以外）に近づくにつれて、このコードは劇的に非効率になっていきます。

メモリアクセスを効率化するには

シーケンシャル・アクセスに変更できないか検討しましょう。変更可能かどうかはアルゴリズム次第なため、必ずしも変更できるとは限りません。

シーケンシャル・アクセスをさらに効率化するには、メモリブロッキング技術やキャッシュ・コントロール技術を使います。

参考：
超高性能プログラミング技術のメモ（７）−ストリップマイニング
超高性能プログラミング技術のメモ（８）−メモリブロッキング技術
超高性能プログラミング技術のメモ（９）−キャッシュをコントロールする技術