Are you still parallelizing your code by hand?

by syoyo

If so, look at this. This is a promising research which makes your sequential program into multi-threaded program automatically.

Matthew J. Bridges, Neil Vachharajani, Yun Zhang, Thomas Jablin, David I. August.
“Revisiting the Sequential Programming Model for Multi-Core”.
Proceedings of the 40th IEEE/ACM International Symposium on Microarchitecture (MICRO), December, 2007.
http://liberty.princeton.edu/Publications/index.php
?abs=1&setselect=micro40_scale

http://liberty.princeton.edu/Publications/index.php
?abs=1&setselect=ieeemicro08_scale

(easy to read version)

[Ja]

えっ?このマルチコア時代に対応するために、逐次プログラムの並列化をまだ手作業でやっているって? で、お決まりのデッドロックやレース競合に苦しんでいる?…
ナンセンス!いまや逐次プログラムでも並列化はコンパイラが自動でやってくれる時代だよ?

という印象を受けた論文.

この論文では、逐次プログラムから、並列に実行可能な部分を解析して抜き出して複数スレッド化するのをコンパイラで自動にやる方法を提案しています。
(ただし、自動並列化をしやすくするために少しアノテーションを加えたりする作業がいります)

たとえば、以下のようなコードを考えてみます.


while (done) {
    line = load();
    result = exec(line);
    store(result);
}

このような逐次コードは、たとえば load(), exec(), store() がそれぞれの処理に依存していなければ、下図のように load(), exec(), store() の処理をそれぞれスレッド化させて 3 スレッドで同時実行し、パフォーマンスの向上を図ることができます.

text2451.png

自動最適化の程度ですが、結果を見るかぎり概ねよい感じです。

とくに gzip 処理を行う 164.gzip ベンチマークでは、すこし並列化しやすくするためにコードを修正した上でこの自動並列化手法を適用していますが、ほぼスレッド数に比例したパフォーマンス向上を達成しています.
もちろん, gzip 処理は本質的に上のような load, exec, store スタイルのプログラムなのでしょうから(予測なのは最後のおまけの部分参照)並列化しやすかったし並列化の恩恵が受けやかったというのもあると思います.

汎用的なプログラムに適用するには難しいかもしれませんが、MUDA のような DSL 的なプログラムにならこの自動並列化処理の導入も容易な気がしています。
データフロー解析が必要なので、自前でやるにはちょっと実装が大変そうですが。
(MLton みたいなコンパイラフレームワークみたいなのの Haskell 版があれば簡単にできるかなぁ…)
MUDA は Erlang みたいにメッセージングベースの並列化を取り入れようかと考えていましたが、
これ(逐次プログラムを自動並列化)ができるなら、こっちのほうがいいとおもいます。

この研究がやっていることのより詳細である、
自動スレッド抽出を行うために使っている
DSWP(Decoupled Software Pipelining)
という技法についてはまたいずれ取り上げたいと思います.

Abstract 日本語訳

シングルスレッドプログラミングはすでに複雑な作業であると理解されている.
マルチスレッドプログラミングへの移行は、
既存コードの書き直し、プログラマのトレーニング、
プログラムのデバッグ作業の増加、レース条件、
デッドロック、その他の並列プログラミングに固有の問題、、、
を回避するための努力に関連する複雑度とコストが上がるにすぎない.

このコストを減らすために自動スレッド抽出などのアプローチが研究されてきた.
しかしながら、自動で抽出される並列度の量は複数のコアをビジーにするには不十分であった.

本論文では、この並列度の不足が逐次プログラミングモデルの本質的な制約からくるものではなく、次の2つの理由から発生するものであることについて論じる.

一つは、核となる既存の最新コンパイラとハードウェア技法を伴う自動スレッド抽出のフレームワークがないことである.
本論文ではそのようなフレームワークがあればいくつかの SPEC CINT2000 のベンチマークプログラムに対してスケーラブルな並列化が可能であることを示す.

もう一つは、既存の逐次プログラミング言語はプログラマにひとつの正しいプログラム結果を強制させており、複数の正しい結果は認めていないことである.
本論文では逐次プログラミングモデルの自然な拡張が、(上記の一つ目の理由の解決方法では解決できなかった)残りの SPEC CINT2000 ベンチマークスイートの並列化を可能にすることを示す.

実験結果では、ソースコードを 60 行変更するだけで, SPEC CINT2000 スイートの C ベンチマークすべてが自動スレッド抽出により並列可能になった. この手法では 454% の高速化を実現し、制約となるのはコンパイラの最適化の制限だけである.

—-

おまけ

しかし SPEC CPU(CINT2000) のベンチマークプログラムってどんなものかなって見ようとしたら、お金払って買わないとダメとは!なんだそりゃ.
ベンチマークプログラムなのにいったい金を取るとはどういう理由なのだろうか.
(テクニカルサポートが云々というのがありますが、個人コンパイラ野郎にはそんなの必要ないのだけれど…)

Advertisements