說是 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 產生並存在的原因
沒有留言:
張貼留言