Halide とその世界の広がり

Halide は、最新のプロセッサに最適化された高速な画像処理コードを簡単に生成するための、ドメイン特化型言語(Domain Specific Language: DSL) です。MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) で開発されており、言語仕様スケジューリングの設計について述べた論文には、AdobeやStanford のメンバーも共著者リストに加わっています。

そのAdobe は、PROJECT HELIUM と呼ばれる旧来の画像処理コードを最新のハードウェアアーキテクチャー向けに蘇らせるという野心的なプロジェクトでこのHalide を使用しています。また、オープンソースのコンピュータビジョン向けライブラリであるOpenCV では、Deep Learning 用モジュールに対して、Halide をバックエンドで利用することで処理効率を上げることができます。さらに最近では、Google がリリースしたスマートフォン”Pixel 2″ に、標準でHalide をサポートする画像処理専用SoC が搭載されていることが話題となっています。

 

アルゴリズムとスケジューリングの分離

画像処理のコードは、並列化やローカルキャッシュの効率化など、対象となるプロセッサ・アーキテクチャを理解した上でのチューニングを行うと、アルゴリズムを素直に実装した教科書的なコードと比べて、処理速度に10倍以上の差が出ることがあります。しかしながら、そのようなハードウェアを意識したチューニングを施したコードは複雑で、可読性も大きく下がります。例えば、簡単な3×3 のぼかし(Blur) 処理を行う場合でも、x86 アーキテクチャに最適化されたコードは

void box_filter_3x3(const Image &in, Image &blury) {
    __m128i one_third = _mm_set1_epi16(21846);

    #pragma omp parallel for
    for (int yTile = 0; yTile < in.height(); yTile += 32) {
        __m128i a, b, c, sum, avg;
        __m128i blurx[(256/8)*(32+2)]; // allocate tile blurx array

        for (int xTile = 0; xTile < in.width(); xTile += 256) {
            __m128i *blurxPtr = blurx;
            for (int y = -1; y < 32+1; y++) {
                const uint16_t *inPtr = &(in[yTile+y][xTile]);
                for (int x = 0; x < 256; x += 8) {
                    a = _mm_loadu_si128((__m128i*)(inPtr-1));
                    b = _mm_loadu_si128((__m128i*)(inPtr+1));
                    c = _mm_load_si128((__m128i*)(inPtr));
                    sum = _mm_add_epi16(_mm_add_epi16(a, b), c);
                    avg = _mm_mulhi_epi16(sum, one_third);
                    _mm_store_si128(blurxPtr++, avg);
                    inPtr += 8;
                }
            }
            blurxPtr = blurx;
            for (int y = 0; y < 32; y++) {
                __m128i *outPtr = (__m128i *)(&(blury[yTile+y][xTile]));
                for (int x = 0; x < 256; x += 8) {
                    a = _mm_load_si128(blurxPtr+(2*256)/8);
                    b = _mm_load_si128(blurxPtr+256/8);
                    c = _mm_load_si128(blurxPtr++);
                    sum = _mm_add_epi16(_mm_add_epi16(a, b), c);
                    avg = _mm_mulhi_epi16(sum, one_third);
                    _mm_store_si128(outPtr++, avg);
                }
            }
        }
    }
}

となります。このコードは教科書的な素直な実装と比べて、Intel Quad Core CPUでは11倍高速に動作しますが、非常に複雑です。さらに実際には、データへの最適なアクセスパターンや計算粒度は、アルゴリズムと対象ハードウェアによって様々なので、コード上に細かい変更を加えながらトライアンドエラーを繰り返して最適なパラメータを見つける作業が必要になります。

Halide は、アルゴリズムそのものの記述と、並列化やローカルキャッシュの使い方を指定するスケジューリングの記述を分離しています。また、用意されているスケジューリングの記述も直感的でわかりやすく、ハードウェアのintrinsic コードがそのまま出てくることはありません。これにより、コードの可読性と処理の高速化を見事に両立させています。参考までに、先程の3×3 のぼかし処理をHalide で実装したものは以下のようになります。

Func box_filter_3x3(Func in) {
    Func blurx, blury;
    Var x, y, xi, yi;
    
    // The algorithm > no storage, order
    blurx(x, y) = (in(x-1, y) + in(x, y) + in(x+1, y))/3;
    blury(x, y) = (blurx(x, y-1) + blurx(x, y) + blurx(x, y+1))/3;
    
    // The schedule > defines order, locality; implies storage
    blury.tile(x, y, xi, yi, 256, 32)
         .vectorize(xi, 8).parallel(y);
    blurx.compute_at(blury, x).store_at(blury, x).vectorize(x, 8);

    return blury;
}

 

スケジューリングの記述部(上記10-12行目) は、自動で導かれるものではないので、依然としてトライアンドエラーを繰り返して、最適なスケジューリングをプログラマが見つける必要があります。しかし、そうだとしても、この簡潔なコードでトライアルを繰り返せるのはHalide の強みと言えます。

 

ポータビリティと”Genesis” コンパイラ

また、Halide は、独自のインクルードファイルを埋め込み、独自のライブラリをリンクします。コード自体は標準的なC++コードとしてGNU g++ などのC++コンパイラでビルドされ、x86(with SSE), ARM (with NEON)のバイナリを生成できる他、CUDA やOpenCL のコードを生成可能なため、nvcc などのコンパイラを介してGPUでの動作も可能です。このようなソースコードのポータビリティは、Halide のもう一つの魅力です。

フィックスターズでは、Halide からFPGAの高位合成(High Level Synthesis: HLS) のための特殊なプラグマを持ったC++ ソースコードへのソースto ソースコンパイラ(Genesis コンパイラ) を開発し、Halide からFPGA IP を生成できるようにしました。これにより、Halide コードは、x86 CPU, ARM, GPU, FPGA の幅広いハードウェア上で実行可能となります。