2018年2月13日 星期二

Halide Tutorial 非官方中文翻譯 - Part 2

說是 Part 2 也僅有 Lesson 5, 而看了一下後續, 這系列大概會分成 9 ~ 10 個部份
Lesson 5 是相當重要的一節, 內容也相當多, 主要在於它提供了底層排程上的操作
對於排程與硬體計算架構的了解有助於快速撰寫適合的排程描述
可以說 Halide 在撰寫程式上的重點之一即在於此
==

Lesson 5 - Vectorize, parallelize, unroll 與 tile 的使用

// 本節使用多種不同方式定義與排程 gradient 函數,
// 並藉此觀察 pixel 被計算的次序

Var x("x"), y("y");
// 預設次序
{
Func gradient("gradient");
gradient(x, y) = x + y;
gradient.trace_stores();

// 預設來說它是個 raster-scan 的方式, 也就是逐條水平掃過
// 也就是 x 會快速變動, 而 y 變動較為緩慢
// 這是個 row-major 的掃描方式
printf("Evaluating gradient row-major\n");
Buffer<int> output = gradient.realize(4, 4);
// Click to show output ...

// 下圖為視覺化結果


// 等義的 C 程式碼
printf("Equivalent C:\n");
for (int y = 0; y < 4; y++) {
    for (int x = 0; x < 4; x++) {
        printf("Evaluating at x = %d, y = %d: %d\n", x, y, x + y);
    }
}
printf("\n\n");

// Tracing 是一個有效了解排程如何運作的方式
// 也可以要求 Halide 印出 pseudocode 來顯示 Halide 所產生的迴圈
printf("Pseudo-code for the schedule:\n");
gradient.print_loop_nest();
printf("\n");
// Click to show output ...

// 由於使用預設次序, 輸出會是:
// compute gradient:
//   for y:
//     for x:
//       gradient(...) = ...
}

// reordering: 重新調整變數次序
{
Func gradient("gradient_col_major");
gradient(x, y) = x + y;
gradient.trace_stores();

// 若想要重新調整 x, y 的次序, 即能夠以垂直的方式掃描
// 重新調整次序呼叫使用 Func 的參數, 並且依序設定新的巢狀 for loop 次序
// 參數設定的方式是由最內層 loop 依序向外層設定
// 所以下列呼叫將 y 置於內層 loop
gradient.reorder(y, x);

// 這表示 y 將快速地變動, 而 x 變為變動緩慢
// 是個 column-major 的掃描方式

printf("Evaluating gradient column-major\n");
Buffer output = gradient.realize(4, 4);
// Click to show output ...

// 下圖為視覺化結果


printf("Equivalent C:\n");
for (int x = 0; x < 4; x++) {
    for (int y = 0; y < 4; y++) {
        printf("Evaluating at x = %d, y = %d: %d\n", x, y, x + y);
    }
}
printf("\n");

// 若印出此排程的 pseudocode, 將會看到 y 的 loop 現在置於 x 的 loop 中
printf("Pseudo-code for the schedule:\n");
gradient.print_loop_nest();
printf("\n");
// Click to show output ...
}

// splitting: 將變數一分為二
{
Func gradient("gradient_split");
gradient(x, y) = x + y;
gradient.trace_stores();

// 對於變數而言, 最強大排程操作是能夠將變數分為內部與外部的子變數
Var x_outer, x_inner;
gradient.split(x, x_outer, x_inner, 2);

// 這能夠將 x 的 loop 分為巢狀的兩層 loop:
// 一個外部的 x_outer loop 以及一個內部的 x_inner loop
// split 呼叫所使用到的最後一個參數稱為 split factor.
// 其表示在內層的 loop 將自 0 遞增到 split factor.
// 而外部的 loop 將自 0 遞增到 x (這個例子為 4) 除以 split factor
// 在這個 loop 中舊有參數將被分為 outer*factor + inner 這樣的方式.
// 若舊 loop 是自非 0 值起算, 這個 offset 將會加到這個新 loop 中

printf("Evaluating gradient with x split into x_outer and x_inner \n");
Buffer output = gradient.realize(4, 4);
// Click to show output ...

printf("Equivalent C:\n");
for (int y = 0; y < 4; y++) {
    for (int x_outer = 0; x_outer < 2; x_outer++) {
        for (int x_inner = 0; x_inner < 2; x_inner++) {
            int x = x_outer * 2 + x_inner;
            printf("Evaluating at x = %d, y = %d: %d\n", x, y, x + y);
        }
    }
}
printf("\n");

printf("Pseudo-code for the schedule:\n");
gradient.print_loop_nest();
printf("\n");
// Click to show output ...

// 注意計算 pixel 數值的次序實際上並不會改變
// Splitting 只是打開了排程上探尋的可能性
// 後續會做說說明
}

// fusing: 合併兩個變數為一個
{
Func gradient("gradient_fused");
gradient(x, y) = x + y;

// 相對於 splitting 的操作是 'fusing'
// fusing 兩個變數將會合併兩個 loops 為單一 for loop
// fusing 比起 splitting 較為不重要, 但它還是有其用途
// 如同 splitting, fusing 本身實際上並不會改變計算的次序
Var fused;
gradient.fuse(x, y, fused);

printf("Evaluating gradient with x and y fused\n");
Buffer output = gradient.realize(4, 4);

printf("Equivalent C:\n");
for (int fused = 0; fused < 4*4; fused++) {
    int y = fused / 4;
    int x = fused % 4;
    printf("Evaluating at x = %d, y = %d: %d\n", x, y, x + y);
}
printf("\n");

printf("Pseudo-code for the schedule:\n");
gradient.print_loop_nest();
printf("\n");
// Click to show output ...
}

// 以 tile 方式計算
{
Func gradient("gradient_tiled");
gradient(x, y) = x + y;
gradient.trace_stores();

// 現在能夠同時作 split 與 reorder 如此能夠達到 tile 方式計算
// 將 x, y 各以 factor 4 作 split 操作
// 並且 reorder 變數來表示 tile 的掃描方式
//
// Tile 掃描方式將原有區域劃分為多個較小長方形的 tile
// 而外部的 loop 在於掃過每個 tile, 而內部的 loop 則掃描 tile 中的每個點.
// 若鄰近的 pixel 有著重複的輸入資料像是 blur, 這樣的方式對於效能上有好處
// 我們能夠表示 tile 的掃描方式如下:
Var x_outer, x_inner, y_outer, y_inner;
gradient.split(x, x_outer, x_inner, 4);
gradient.split(y, y_outer, y_inner, 4);
gradient.reorder(x_inner, y_inner, x_outer, y_outer);
// 這樣的模式其一般性足以有簡短表示
// gradient.tile(x, y, x_outer, y_outer, x_inner, y_inner, 4, 4);

printf("Evaluating gradient in 4x4 tiles\n");
Buffer output = gradient.realize(8, 8);
// Click to show output ...

// 以下為視覺化結果


printf("Equivalent C:\n");
for (int y_outer = 0; y_outer < 2; y_outer++) {
    for (int x_outer = 0; x_outer < 2; x_outer++) {
        for (int y_inner = 0; y_inner < 4; y_inner++) {
            for (int x_inner = 0; x_inner < 4; x_inner++) {
                int x = x_outer * 4 + x_inner;
                int y = y_outer * 4 + y_inner;
                printf("Evaluating at x = %d, y = %d: %d\n", x, y, x + y);
            }
        }
    }
}
printf("\n");

printf("Pseudo-code for the schedule:\n");
gradient.print_loop_nest();
printf("\n");
// Click to show output ...
}

// 以 vector 方式做計算
{
Func gradient("gradient_in_vectors");
gradient(x, y) = x + y;
gradient.trace_stores();

// splitting 的好處是其保證內部的變數自 0 遞增到 split factor.
// 多數情況 split-factor 在編譯時期會是常數,
// 因此我們能夠將內部 loop 使用 vector 做計算
// 這次我們以 factor 4 做 split, 因為在 x86 平台上 SSE 能提供 4-wide vector
Var x_outer, x_inner;
gradient.split(x, x_outer, x_inner, 4);
gradient.vectorize(x_inner);

// Splitting 接著於內部 loop 作 Vectorizing , 其一般性足以有簡短表示:
//
// gradient.vectorize(x, 4);
//
// 即等同於:
//
// gradient.split(x, x, x_inner, 4);
// gradient.vectorize(x_inner);
//
// 注意在這個例子中, 我們重複使用了 'x' 作為新的外部 loop 的變數名稱
// 而緊接著的排程使用到 x 將以此作為新的外部 loop 變數

// 這次將以 8x4 方塊的方式來計算,
// 因此每 scanline 將會有超過一個 vector 的工作
printf("Evaluating gradient with x_inner vectorized \n");
Buffer output = gradient.realize(8, 4);
// Click to show output ...

// 下圖為視覺化結果


printf("Equivalent C:\n");
for (int y = 0; y < 4; y++) {
    for (int x_outer = 0; x_outer < 2; x_outer++) {
        // 在此 x_inter loop 被 vectorized 版本取代而消失了
        // 於 x86 處理器上, Halide 對這些產生 SSE 程式碼

        int x_vec[] = {x_outer * 4 + 0,
                       x_outer * 4 + 1,
                       x_outer * 4 + 2,
                       x_outer * 4 + 3};
        int val[] = {x_vec[0] + y,
                     x_vec[1] + y,
                     x_vec[2] + y,
                     x_vec[3] + y};
        printf("Evaluating at <%d, %d, %d, %d>, <%d, %d, %d, %d>:"
               " <%d, %d, %d, %d>\n",
               x_vec[0], x_vec[1], x_vec[2], x_vec[3],
               y, y, y, y,
               val[0], val[1], val[2], val[3]);
    }
}
printf("\n");

printf("Pseudo-code for the schedule:\n");
gradient.print_loop_nest();
printf("\n");
// Click to show output ...
}

// Unrolling: 展開 loop
{
Func gradient("gradient_unroll");
gradient(x, y) = x + y;
gradient.trace_stores();

// 若多個 pixel 分享重複的資料, 對於計算作 unroll loop 就有意義
// 因分享的資料只需計算或載入一次
// 這方式類似於 vectorizing 的方式:
// split 一個維度, 然後 unroll 內部 loop
// 同樣地, Unrolling 並不會改變計算的次序
Var x_outer, x_inner;
gradient.split(x, x_outer, x_inner, 2);
gradient.unroll(x_inner);

// 可簡短表示為:// gradient.unroll(x, 2);

printf("Evaluating gradient unrolled by a factor of two\n");
Buffer result = gradient.realize(4, 4);
// Click to show output ...

printf("Equivalent C:\n");
for (int y = 0; y < 4; y++) {
    for (int x_outer = 0; x_outer < 2; x_outer++) {
        // 對於 x_inner loop 取而代之的是得到兩個類似的 x_inner block
        {
            int x_inner = 0;
            int x = x_outer * 2 + x_inner;
            printf("Evaluating at x = %d, y = %d: %d\n", x, y, x + y);
        }
        {
            int x_inner = 1;
            int x = x_outer * 2 + x_inner;
            printf("Evaluating at x = %d, y = %d: %d\n", x, y, x + y);
        }
    }
}
printf("\n");

printf("Pseudo-code for the schedule:\n");
gradient.print_loop_nest();
printf("\n");
// Click to show output ...
}

// 以無法整除的 split factor 作 splitting
{
Func gradient("gradient_split_7x2");
gradient(x, y) = x + y;
gradient.trace_stores();
// splitting 保證內部 loop 自 0 起算到 split factor, 從先前可知這點對應用很重要
// 然而若要處理的內容無法被 split factor 整除時會如何?
// 這裡以 factor 3 方式作 splitting 一個 7x2 的範圍而非先前的 4x4 方塊
Var x_outer, x_inner;
gradient.split(x, x_outer, x_inner, 3);

printf("Evaluating gradient over a 7x2 box with x split by three \n");
Buffer output = gradient.realize(7, 2);
// Click to show output ...

// 以下為視覺化結果
// 請注意有的 pixel 被計算超過一次


printf("Equivalent C:\n");
for (int y = 0; y < 2; y++) {
    for (int x_outer = 0; x_outer < 3; x_outer++) { // Now runs from 0 to 2
        for (int x_inner = 0; x_inner < 3; x_inner++) {
            int x = x_outer * 3;
            // Before we add x_inner, make sure we don't
            // evaluate points outside of the 7x2 box. We'll
            // clamp x to be at most 4 (7 minus the split
            // factor).
            if (x > 4) x = 4;
            x += x_inner;
            printf("Evaluating at x = %d, y = %d: %d\n", x, y, x + y);
        }
    }
}
printf("\n");

printf("Pseudo-code for the schedule:\n");
gradient.print_loop_nest();
printf("\n");
// Click to show output ...

// 若察看輸出會發現一些座標點被計算超過一次
// 通常是沒問題的, 因為純 Halide 函數並沒有 side-effects,
// 因此單一點被計算多次是安全的
// 若是使用 C function 則必須確認能處理單一點被重複計算多次的情形

// 通則是: 若 x 自 x_min 到 x_min + x_extent , 且需要以 factor 作 splitting 則:
//
// x_outer loop 自 0 增加到 (x_extent + factor - 1)/factor
// x_inner loop 自 0 增加到 factor
// x = min(x_outer * factor, x_extent - factor) + x_inner + x_min
//
// 在範例中 x_min 為 0 , x_extent 為 7 而 factor 為 3

// 然而當使用一個更新定義撰寫 Halide 函數時(lesson 9),
// 單一點的重複計算並不是安全的, 因此不要使用這技巧
// 相對地計算範圍將會調整到下一個 split factor 的倍數
}

// Fusing, Tiling 與 Parallelizing
{
// 在先前得知能夠在一個變數上做平行化
// 這裡將它與 fusing 及 tiling 合併應用產生有用的模式 - 平行處理 tiles

// 這部份是 fusing 好用的地方.
// fusing 讓跨多維度的平行無需使用巢狀平行化.
// Halide 支援巢狀平行化(在平行化的 for loop 之中作 for loop的平行化)
// 相較於 fusing 多個變數來做單一 for loop 平行化, 通常巢狀平行化帶來較差的效能

Func gradient("gradient_fused_tiles");
gradient(x, y) = x + y;
gradient.trace_stores();

// 首先分為多個 tile, 並且合併 tile 索引
// 並且對合併後作平行化
Var x_outer, y_outer, x_inner, y_inner, tile_index;
gradient.tile(x, y, x_outer, y_outer, x_inner, y_inner, 4, 4);
gradient.fuse(x_outer, y_outer, tile_index);
gradient.parallel(tile_index);

// 排程的呼叫會傳回 Func 的 reference,
// 因此能夠將其串連起來成為單一敘述, 能相對簡潔
//
// gradient
//     .tile(x, y, x_outer, y_outer, x_inner, y_inner, 2, 2)
//     .fuse(x_outer, y_outer, tile_index)
//     .parallel(tile_index);


printf("Evaluating gradient tiles in parallel\n");
Buffer output = gradient.realize(8, 8);
// Click to show output ...

// 可以觀察到 Tiles 將被亂序地處理, 在每個 tile 中都是以 row-major 做處理
// 以下為視覺化結果


printf("Equivalent (serial) C:\n");
// 最外層的 loop 應該是個平行化的 for loop, 但難以用 C 表示

for (int tile_index = 0; tile_index < 4; tile_index++) {
    int y_outer = tile_index / 2;
    int x_outer = tile_index % 2;
    for (int y_inner = 0; y_inner < 4; y_inner++) {
        for (int x_inner = 0; x_inner < 4; x_inner++) {
            int y = y_outer * 4 + y_inner;
            int x = x_outer * 4 + x_inner;
            printf("Evaluating at x = %d, y = %d: %d\n", x, y, x + y);
        }
    }
}
printf("\n");

printf("Pseudo-code for the schedule:\n");
gradient.print_loop_nest();
printf("\n");
// Click to show output ...
}

// 綜合應用
{
// 接著使用上面所有的功能特性
Func gradient_fast("gradient_fast");
gradient_fast(x, y) = x + y;

// 將影像分為 64x64 tiles 並作平行化
Var x_outer, y_outer, x_inner, y_inner, tile_index;
gradient_fast
    .tile(x, y, x_outer, y_outer, x_inner, y_inner, 64, 64)
    .fuse(x_outer, y_outer, tile_index)
    .parallel(tile_index);

// 當掃描每個 tile 過程中同時計算兩個 scanline
// 最簡單的表示方式是在 tile 中再次 tiling 到 4x2 的 subtile
// 接著在 x 方向與 y 方向做 vectorize 與 subtile :
Var x_inner_outer, y_inner_outer, x_vectors, y_pairs;
gradient_fast
    .tile(x_inner, y_inner, x_inner_outer, y_inner_outer, x_vectors, y_pairs, 4, 2)
    .vectorize(x_vectors)
    .unroll(y_pairs);

// 注意並沒有明確的 split 或 reorder.
// 這些是最為重要的基本操作, 但通常隱藏在 tiling, vectorizing 或是 unrolling 呼叫之下

// 接著計算非 tile 大小整數的範圍

// 若喜歡可以打開 tracing 功能, 但也將印出大量的訊息
// 相對地能夠在 C 與 Halide 計算並確認是否一致
Buffer result = gradient_fast.realize(350, 250);

//以下為視覺化結果

printf("Checking Halide result against equivalent C...\n");
for (int tile_index = 0; tile_index < 6 * 4; tile_index++) {
    int y_outer = tile_index / 4;
    int x_outer = tile_index % 4;
    for (int y_inner_outer = 0; y_inner_outer < 64/2; y_inner_outer++) {
        for (int x_inner_outer = 0; x_inner_outer < 64/4; x_inner_outer++) {
            // 在 x 方向作 vectorize
            int x = std::min(x_outer * 64, 350-64) + x_inner_outer*4;
            int x_vec[4] = {x + 0,
                            x + 1,
                            x + 2,
                            x + 3};

            // 以及在 y 方向 unrolling
            int y_base = std::min(y_outer * 64, 250-64) + y_inner_outer*2;
            {
                // y_pairs = 0
                int y = y_base + 0;
                int y_vec[4] = {y, y, y, y};
                int val[4] = {x_vec[0] + y_vec[0],
                              x_vec[1] + y_vec[1],
                              x_vec[2] + y_vec[2],
                              x_vec[3] + y_vec[3]};

                // Check the result.
                for (int i = 0; i < 4; i++) {
                    if (result(x_vec[i], y_vec[i]) != val[i]) {
                        printf("There was an error at %d %d!\n",
                               x_vec[i], y_vec[i]);
                        return -1;
                    }
                }
            }
            {
                // y_pairs = 1
                int y = y_base + 1;
                int y_vec[4] = {y, y, y, y};
                int val[4] = {x_vec[0] + y_vec[0],
                              x_vec[1] + y_vec[1],
                              x_vec[2] + y_vec[2],
                              x_vec[3] + y_vec[3]};

                // Check the result.
                for (int i = 0; i < 4; i++) {
                    if (result(x_vec[i], y_vec[i]) != val[i]) {
                        printf("There was an error at %d %d!\n",
                               x_vec[i], y_vec[i]);
                        return -1;
                    }
                }
            }
        }
    }
}
printf("\n");

printf("Pseudo-code for the schedule:\n");
gradient_fast.print_loop_nest();
printf("\n");
// Click to show output ...

// 注意在這 Halide 版本中, 演算只有在最上面作一次的指定,
// 接著再個別做不同的優化, 總共並沒有很多行程式碼
// 而相較之下 C 版本有著較多行的程式碼
// 通常惱人的是分散多處對於演算的陳述造成的凌亂
// 而 C 程式碼並不容易撰寫, 且難以閱讀與除錯, 更難以進一步地優化
// 而這也是為什麼 Halide 產生並存在的原因
}

沒有留言:

Chisel 學習筆記 - Scala 與 Chisel 基礎語法

標題為筆記, 但這篇比較屬於心得 延續 上一篇 的環境建立, 這次計劃藉由 Jserv 最新的 課程安排 來學習 Chisel, 當然個人目標是能夠按照 Jserv 的課程規劃在 期限之內 完成 Lab 3, 由於個人並非 digital designer (現在這年紀也算老貓學...