Increasing and Detecting Memory Address Congruence

Samuel Larsen, Emmett Witchel, and Saman Amarasinghe. In Proceedings of the 11th International Conference on Parallel Architectures and Compilation Techniques, pages 18-29. 2002.

昨日の論文の続きというか、アラインメントの問題を解決する論文。Memory congruenceとは、あるメモリアクセスがあるアラインメント中の特定のオフセットにのみアクセスすることを指す。例えば、

int a[100];
for (i = 0; i < 100; i++) {
  a[i] = 0.0;
}

のa[i]は4n+0という、4バイトアラインメント中のオフセット0にアクセスするが、

int a[100];
for (i = 0; i < 100; i+=4) {
  a[i+0] = 0.0;
  a[i+1] = 0.0;
  a[i+2] = 0.0;
  a[i+3] = 0.0;
}

とするとそれぞれは16n+0, 16n+4, 16n+8, 16n+12という、16バイトアラインメント中の各オフセットにアクセスすることになる。Congruentなメモリアクセスをプログラム変形により増やして検出することで、キャッシュの消費電力の削減やSIMD最適化に利用することができる。

著者らはまずcongruenceを検出するアルゴリズムを提案している。メモリアクセスのアドレス変数に対してデータフロー解析を行う。各変数には8n+2, 8n+6などの属性が付加され、例えば8n+2の変数と8n+6の変数が合流すれば4n+2となる。さらに、congruentな命令を増やすプログラム変形を幾つか提案している。基本はループアンローリングだが、本体に突入する前にアラインメントを合わせるためのpre-loopを挿入する。こんな感じ：

void init(double *x)
{
  int i;
  for (i = 0; i < 100; i++) {
    if ((int)&x[i] % 32) == 0)
      break;
    x[i] = 0.0;
  }
  for ( ; i < 100; i+=4) {
    x[i+0] = 0.0;
    x[i+1] = 0.0;
    x[i+2] = 0.0;
    x[i+3] = 0.0;
  }
}

pre-loopは以前からある手法だが、実際には複数のメモリアクセスがある場合にどれを優先してアラインメントを取るか、などなどの問題がある。著者らはプロファイル情報を用いて最適な条件を探索する。実験によると、32バイトアラインメントの場合に何もしないと高々20数パーセント（動的カウント）のメモリアクセスがcongruentであったのが、変形により平均で60%以上がcongruentとなった。さらに、検出アルゴリズムによってそのうちの95%をcongruentであると判定できた。

あまり大したアイデアは無いが、結果はなかなか魅力的。