Halide小ネタ(Halide::undef編)

初投稿です．Halideを触っていて「なんか使えそうだな～いやそうでもないかぁ」って感じの小ネタや，チュートリアルのってない便利機能を紹介していこうとおもいます．今回はその第1弾(いくつ続けられるか...)

はじめに

Halideは画像処理に特化したドメイン固有言語です．大きな特徴として処理の本質となるアルゴリズム部分と，高速化に関するスケジューリング部分を独立して記述でき，簡潔な記述ですげぇ速いコードが生成できます．詳細な解説はこちらやこちらでされているので，ここでは省略．公式チュートリアルが公開されているので，基本的な使い方はここで学べます．

Pure DefinitionとUpdate Definition

公式チュートリアル09の内容です．既に知っている内容なら飛ばしてください．

HalideのFuncはマルチパスで定義することができます．下のコードがマルチパスFuncの一例で，
f(x, y) = input(x, y);とf(x, 3) = f(x, 0) * f(x, 10);によってFunc fが定義されます．前者の定義がPure Definition，後者の定義がUpdate Definitionと呼ばれ，本記事ではこれらを純粋定義と更新定義と呼びます．

Halide::Var x("x"), y("y");
Halide::Func f("func");
f(x, y) = input(x, y);
f(x, 3) = f(x, 0) * f(x, 10);

純粋定義では画像全体についてどのように処理されるかを記述し，VarからExprへのマッピングでないといけないですが，更新定義では画像の一部分に限った処理が許されます．また，純粋定義はただ1つで必須な定義ですが，更新定義はいくつでも任意に定義できます．また，処理される順番は純粋定義のあと更新定義が定義された順番に処理されます．

undefで初期化スキップ

次のようなHalideコードを見てみましょう．

Halide::Var x("x"), y("y");
Halide::RDom r(1, w - 1);
Halide::Func before("before"), after("after");

before(x, y) = input(x, y);
before(r, y) = 0.8f * before(r, y) + 0.2f * before(r - 1, y);

上のコードでは，Func beforeが純粋定義で入力inputをコピーし，更新定義でReduction Domainを使って1つ前の出力と，現在の入力との加重平均をとっています...が．

...これ純粋定義のいらんくない???
はじめからbefore(r, y) = 0.8f * input(r, y) + 0.2f * before(r - 1, y);ってすりゃええ話なのでは??

ところが，純粋定義の制約上Reduction Domainが使えないし，befoeの初期値が分からんといったことからできないのです．こいういときはHalide::undefの出番です．

Halide::Var x("x"), y("y");
Halide::RDom r(1, w - 1);
Halide::Func after("after");

after(x, y) = Halide::undef(input.type());
after(0, y) = input(0, y); // 初期値がいる
after(r, y) = 0.8f * input(r, y) + 0.2f * after(r - 1, y);

このように，純粋定義をHalide::undefにすることで，純粋定義の処理を省略することができます．

undefの説明

Halide.hによると，Halide::undefの説明は以下の通りです．

/** Return an undef value of the given type. Halide skips stores that
* depend on undef values, so you can use this to mean "do not modify
* this memory location". This is an escape hatch that can be used for
* several things:
*
* You can define a reduction with no pure step, by setting the pure
* step to undef. Do this only if you're confident that the update
* steps are sufficient to correctly fill in the domain.
*
* For a tuple-valued reduction, you can write an update step that
* only updates some tuple elements.
*
* You can define single-stage pipeline that only has update steps,
* and depends on the values already in the output buffer.
*
* Use this feature with great caution, as you can use it to load from
* uninitialized memory.
*/

Halide::undefの値に依存するストアはスキップされるそうですね．

実験結果

環境はIntel Core i7-8550U CPU @ 1.80GHzです．

before : 1.29004ms
after : 1.08038ms

画素タッチ一回分くらい速くなりました.

最後に

今回はHalide::undefを紹介しました．
個人的に結構便利機能だと思うのですがなぜかチュートリアルに載ってないんですよね...そもそも公式チュートリアルが不十分すぎる
こんな感じの小ネタを今後いくつか紹介できたらなと思います.

テスト用コード全体

void test_undef_initialize(Halide::Buffer<float> input) {
    const int w = input.width(), h = input.height();
    Halide::Var x("x"), y("y");
    Halide::RDom r(1, w - 1);
    Halide::Func before("before"), after("after");
    double result;

    before(x, y) = input(x, y);
    before(r, y) = 0.8f * before(r, y) + 0.2f * before(r - 1, y);
    result = Halide::Tools::benchmark(10, 10, [&]()
        {
            before.realize(w, h);
        }
    );
    cout << "before : " << result * 1e3 << "ms\n";

    after(x, y) = Halide::undef(input.type());
    after(0, y) = input(0, y);
    after(r, y) = 0.8f * input(r, y) + 0.2f * after(r - 1, y);
    result = Halide::Tools::benchmark(10, 10, [&]()
        {
            after.realize(w, h);
        }
    );
    cout << "after : " << result * 1e3 << "ms\n";
}