Exploiting superword level parallelism with multimedia instruction sets

Samuel Larsen and Saman Amarasinghe. In Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, pages 145-156. 2000.

近年のプロセッサによく搭載されているSIMD命令をコンパイラが利用する場合、これまではベクトル化コンパイラの手法を適用してループのイテレーション間の並列性を見つけていたが、どうせ４並列とか８並列とかしか無いんだからもっと簡単に解析できるんじゃね？というのがキモか。

for (i = 0; i < 16; i++) {
  diff[i] = ref[i] - curr[i];
}

が

for (i = 0; i < 16; i += 4) {
  diff[i+0] = ref[i+0] + curr[i+0];
  diff[i+1] = ref[i+1] + curr[i+1];
  diff[i+2] = ref[i+2] + curr[i+2];
  diff[i+3] = ref[i+3] + curr[i+3];
}

になって、SIMD命令に変換される、というだけの話。実際にはもうちょっと複雑でベクトル化できないループも、アンローリングして一部だけSIMD命令を用いるようにすることが可能となる。

基本的なアルゴリズムは、まずループを４回とか８回とかアンローリングする。次に、隣り合うアドレスへのメモリ参照のペアの集合を見つける。さらにuse-def, def-use関係をたどって同型な命令もペアにしていく。基本ブロック内の解析しかしない。AltiVec向けのコンパイラに実装し、SPECのswimで1.24倍、tomcatvで1.57倍等々のスピードアップを達成した。イテレーション間だけでなく基本ブロック内の並列性も見つけることができるため、従来のベクトル化コンパイラと比べて削減命令数が動的カウントで倍近くになることもある。著者は実装の簡単さも強調したいようだ。

非常に真っ当というか当たり前の手法ではある。これって本当に既存研究が無いのか？結局はアラインメントやパック/アンパックのコストが問題になる。