Halide事始め
MIT Halide(http://halide-lang.org/)というC++の高速画像処理ライブラリが去年リリースされた。C++内のDSLを使っていて、画像処理を、
- 計算のアルゴリズム
- アルゴリズム自体は副作用がなく、純粋関数的に定義される。
- 実装の詳細(「スケジュール」)
- スケジュールは、計算の並列化と、複数の計算ステップの融合を最適化する方法を指定する。
を分離した形で簡潔に書ける。
凄いのは、抽象的に書いたアルゴリズムからライブラリによって低レベルコードを出力させたほうが、手書きでチューニングしたコードよりも速いことすらあること(という作者の主張)。たとえば最近開発されたlocal Laplacian filterというの複雑なアルゴリズム(http://people.csail.mit.edu/sparis/publi/2011/siggraph/、pixelwise operationやstencil operationだけでなく、任意の画素にアクセスするような計算も含む。)が、OpenMPとIntel IPPで並列化した手書きのC++よりも2.1倍速く、コードが3.7倍短い(http://people.csail.mit.edu/jrk/halide12/)とか。
このHalide、かなり有望な感じがするのだけど、なんせ資料が少ない。公式サイトにもサンプルコードがあるのみで、ドキュメントらしいドキュメントはない(追記:http://halide-lang.org/Halide/index.html にAPIレファレンスがあった)。しかしこの技術、DSL、画像処理、並列計算、純粋関数型の計算による抽象化、と僕の興味に見事にマッチしている。そこで以下に覚書を兼ねてライブラリの概要を記す。
論文
http://people.csail.mit.edu/jrk/halide12/halide12.pdf
- この論文に使い方(アルゴリズムの書き方とスケジュールの指定方法)が説明されている。
http://people.csail.mit.edu/jrk/halide-pldi13.pdf
- この論文は続編で、遺伝的アルゴリズムを使ったスケジュールの自動最適化を行なったりしている。
使い方
Githubのレポhttps://github.com/halide/Halideをクローンしてmakeでビルドする。llvm (>= 3.2)とllvm-configが使えるようにしておく必要がある。(私はここで微妙にハマった...。)
ごく簡単なチュートリアルがtutorialsフォルダの中にあるが、情報量は少ないので、むしろtestとappsの2つのフォルダ内のコードが参考になりそう。
- 実行時にJITコンパイルする方法
- C++を実行時にDSLを展開した別のC++を生成する方法
の2種類があるが、使える機能は同じようだ。単に試す分には簡単に使えるJITコンパイルで良い。
Halide::FuncとHalide::Varの2つのクラスを使って、例えば以下のように画像を表現できる。ソースを読んでいないので仕組みはよくわからないがこれはなんかマジックっぽい感じがする。
Halide::Func output; Halide::Var x, y; output(x, y) = x + y; output.realize(800,600);
tutorialsフォルダにあるサンプルコードをコンパイルするには、以下の様な感じで良い。
$ clang++ -lHalide `libpng-config --cflags --ldflags` lesson_02.cpp
Funcクラスのインスタンスとして定義した関数に対してrealize()を呼ぶことで計算を実行する。 並列化などの「スケジュール」を指定する場合は、realize()の前にそれを指定する。
testフォルダ内にたくさん小さなコードがあるが、簡単な例は以下のようなものがある。
- two_vector_args.cpp
- vector_extern.cpp
- vector_bounds_inference.cpp
- lambda.cpp
- ラムダ式が使えるので、その例。
これまでの例はpixelwiseの操作だが、線形フィルタなど、近傍のピクセルを使った計算(stencil computation)もできる。
実際に使ってみる
以下の様なコードをサンプルコードからコピペ+適当に変更して書いた。画像の明るさを調整するプログラム。 https://gist.github.com/nebuta/6149137
コンパイルして実行してみる。
$ clang++ -I ../include -L ../bin -lHalide `libpng-config --cflags --ldflags` brighter.cpp $ ./a.out Input: 1536 x 2560 x 3 Start measurement. Vectorized vs scalar (average over 1000 times): 2.20 ms 23.02 ms. Speedup = 10.482 Success!
約4メガピクセルの画像が2msで処理できている。良い感じだ。スケジュールをたった1行指定するだけで10倍に加速した。ちなみにスケジュールの指定を適切にしないと速くならないし、何もしないよりも遅くなることすらあった。
追記:画像の入出力、pointwise operation(コントラスト調整・2値化など), stencil operation(ガウスフィルタなど)といった基本操作をサンプルコードからコピペ+適当に変更してまとめてみた。https://gist.github.com/nebuta/6152664 コンパイルにlibpngが必要。 実行結果は
$ clang++ -lHalide `libpng-config --cflags --ldflags` halide-examples.cpp $ ./a.out 1.337 ms (1000 times average): pointwise 0.104 ms (1000 times average): pointwise,parallel 12.9x speedup. 8.153 ms (10 times average): image_rgb_to_gray 4.168 ms (10 times average): image_rgb_to_gray, par 2.0x speedup. 56.128 ms (10 times average): blur 9.090 ms (10 times average): blur,par 6.2x speedup.
良い感じだ。
まとめ
MIT Halideを使うメリットは、
- 画像処理のアルゴリズムが純粋関数的に抽象的・簡潔に書くことが可能で、実装の詳細(「スケジュール」)は、アルゴリズムから分離して後から最適化できる。
- スケジュールによって、単一ステップの並列化と複数ステップの融合を同時に行うことができる。
- 簡単なスケジュールの指定で、劇的に速度が向上する。
現状不足している点は、
- スケジュールを人間が考えて手書きしないとならず、それだけちょっと難しい気がする。
- ドキュメントがほとんどなく、サンプルコードを読んでライブラリの機能を推測する必要がある。
- 特に、スケジュールの書き方に関する指針がほとんど示されていない。
Halideのようなアプローチが一般化すれば、OpenCVのような既存の大きなフレームワークに頼ることなく、自分の必要な機能を柔軟かつ簡潔にボトムアップで構築することも十分可能になると思われる。
2報目の論文ではスケジュールの自動最適化も行なっているので、そのうちユーザー向けにも実装されることが期待できる。複雑なアルゴリズムの場合、スケジュールの組み合わせを単純にランダムに探索すると組み合わせ爆発してしまうそうで、遺伝的アルゴリズムで効率的な探索をしている。