MITが並列プログラムの最適化改善のためにLLVMのIRを拡張

MITの研究者たちがLLVMのフォークを使用して，fork-join並列処理をコンパイラの中間表現(IR)に直接埋め込む並列コード最適化の新たなアプローチに取り組んでいる。この方法を用いることで，直列的なIRレベルの最適化手法の大部分が並列プログラムでも利用可能になる，というのが彼らの主張だ。

fork-join並列処理とは並列プログラムの実行を管理する手法のひとつで，特にマージソートのような分割統治型アルゴリズムに適している。fork-join並列化は，OpenMP(#pragma omp parallel，#pragma omp parallel forなど)やClick Plus(cilk_spawn，cilk_sync)といった言語拡張セットを通じて，GCCやLLVMなどメインストリームのコンパイラでサポートされている。コンパイラのフロントエンドはこれらの言語拡張を，“より低い”並列構造のプリミティブな表現に処理した上でIRに変換する。例えば，次に示すようなClickのclick_for拡張を使用したスニペットでは，ループの各イテレーションの並列実行が可能になる。

__attribute__((const)) double norm(const double *A, int n);

void normalize(double *restrict out,
               const double *restrict in, int n) {
  cilk_for (int i = 0; i < n; ++i)
    out[i] = in[i] / norm(in, n);
  }
}

しかしながら，このアプローチの欠点のひとつは，コンパイラのミドルエンドが見るのはforループではなく，関数内のfor本体を抽象化した不明確なランタイムコールのみであり，それをループイテレーションの実行と完了後の同期処理を行なうライブラリ関数に渡すような構造になる点だ。このため，IRレベルのforループで一般に使用されるようなループ内不変コードの移動やスケジューリングといった最適化は，事実上すべて不可能になる。

Schardl，Moses，Leierson氏らによる研究は，拡張IRを使用してfork-joinモデルをミドルエンドに直接渡すことによって，並列処理に必要なコードが付け加えられる前にコードの最適化戦略をすべて使用可能にしようというものだ。もっとも，この試み自体は新しいものではなく，プログラムの並列性を表現する目的で考案されたIRはすでにいくつか存在する。

... 一般的なコンパイラに他のIRを追加する手法は，追加したIRを既存のシリアルIRと同じ基準でメンテナンスするためのエンジニアリングや開発上の負担が必要となる点から，これまでは批判の対象となってきました。

今回の試みで注目すべきなのは，既存の直列的なセマンティクスを維持しつつ，論理タスクの並列性を表現するためにLLVMのIRを拡張する手法を見出した点にある。研究者たちがTapirと呼ぶ新たなIRでは，並列タスクは非対称的に表現される。これはつまり，実行フローが同期(sync)する前にまず並列タスクが完了しなければならない，ということだ。氏らによれば，これによって，LLVMなどのシリアルミドルエンドが並列コードを効果的に最適化できるようになる。

Tapirでは３つの新たなコマンドであるdetach，reattach，syncを追加して，LLVMのIRを拡張する。detachはforkとほぼ同じ抽象化に対応するが，reattachとsyncとjoinにはわずかながら違いがある。これは直列化を可能にする上で，継続処理にブランチする前に分離された並列計算ブロックの実行を完了しなくてはならない，という要件によるものだ。従って，detachとreattachが並列タスクの開始と終了を表現し，syncがその並列コンテキスト内でタスクを同期させる。

新しいアプローチのメリットを評価するためにMITの研究者たちは，Clickを有効にしたLLVMコンパイラとTapirを使用したものを使って，20個のClickプログラムをコンパイルした場合を比較した。

20プログラム中の17では，新しい中間表現を使用したコンパイラの方が効率のよいプログラムを出力し，その３分の１では10～25パーセントの向上を確認できました。新しいコンパイラが出力したソフトウェアが効率面で劣ったプログラムにおいても，低減率は2%未満に留まっています。

TapirはGitHubで公開されており，次のコマンドを実行してビルドすることができる。

git clone --recursive https://github.com/wsmoses/Tapir-Meta.git
cd Tapir-Meta/
./build.sh
source ./setup-env.sh