2018年3月15日 星期四

Halide - 實務心得 1

近日著手開始以 Halide 撰寫 AOT 程式 發現有一些特別的東西沒有寫在教學文件上

 

 1. buffer pointer of Halide::Runtime::Buffer

宣告一個 Buffer object 並不困難像是:
Halide::Runtime::Buffer buf(640, 480);
而在教學文件中很常看到 Buffer 的使用 
但是範例上常常是直接載入 jpg/png 圖檔, 
或是透過下列的方式來讀取或寫入 (x, y) 位置的數值: (見 Lesson 10 part 2)
buf(x, y) = val

而對於 C/C++ 而言是可以取得 buffer pointer 的
取得方式也很簡單, 透過 Buffer::data() 這個成員函式的呼叫
以上述例子就是:
unsigned char* buf_ptr = (unsigned char*)(buf.data());
使用由 data() 取得的 pointer 就必須注意 layout, 預設的是 Planar
若需要使用 interleaving data 則要透過 set_stride  來設定 (見 Lesson 16)

2. Buffer allocation

儘管一般開發 Halide 程式使用的裝置離不開 CPU/GPU
但是 Halide 俱備介面, 只要實作 code generation 與 runtime interface 就可以接上
以 Qualcomm HVX 來說, DSP backend 的 Buffer 使用與 CPU 有相當不同
透過的是 Buffer::device_malloc() 來配置特定計算裝置的記憶體
並以此避免 memcpy 的呼叫, 來達到 zero-copy 的目的
而 device_malloc 需要帶入 Device API 的 interface
像是在 Qualcomm 官方 Halide 文件中提到 Qualcomm Hexagon DSP buffer 配置的呼叫為:
buf.device_malloc(halide_hexagon_device_interface());
如此即可配置針對 Hexagon DSP 所使用的記憶體空間, 並且無需 data copy

3. Prefetch schedule directive

計算單元與記憶體間資料的傳輸方式一直是改善效能的重點
個人經驗是撰寫 SIMD code 透過 prefetch 能改善不少效能
其他像是 GPU 俱備 local/shared memory,
有些 DSP 也有著自己的 scratchpad memory
透過重疊(overlapping) 執行時間與傳輸時間
這部分都牽涉到 2D 的 Prefetch 或 DMA 的呼叫使用

在 2015 年剛接觸 Halide 時, 與當時熟悉 Halide 同事討論
當時給的答覆是並無法對應 prefetch 這樣的行為
而日前第一時間在 Qualcomm Halide SDK 中的範例看到 prefetch 排程指令時:
(像是 Halide SDK 中  HALIDE_Tools/2.0/Halide/hexagon_benchmarks/gaussian5x5_generator.cpp )
output.hexagon().prefetch(input, y, 2) ... ;
個人一度以為這只是 Qualcomm 為了 Hexagon DSP 而客製的 API
然而近日發現 Halide 中的 Prefetch.h說明文件
又挖了 History 後才發現在 2016 年中 Halide 已加入了對於 prefetch 行為的支援
這也讓 Halide 能夠更彈性的支援不同處理器的運作特性
而類似於 data 在 Boundary 的處理 Prefetch 也有 PrefetchBoundStrategy

4. AOT target

在 Lesson 15 並沒有提及 Generator Enhancements
在後續 Halide 對於 Generator 分為 generate() 與 schedule()
顧名思義, generate() 是用來定義 pipeline 的, 而 schedule() 是處理排程的
若希望有效地支援不同平台, 就需要知道 code generation target 的特性
這裡主要透過二個 API 與二個 public member
* Halide::GeneratorContext::get_target() - 這可以得到 Halide::Target 的物件, 透過這物件可以獲得相關資訊, 最直接的就是 Target::to_string() 可以得到指令傳入的 target 字串
* Halide::Target::has_feature() - 可以確認是否支援某些特性像是 SSE/AVX, ARMv7s or HVX
* Halide::Target.arch - X86, ARM, Hexagon ...
* Halide::Target.os - Linux, Windows ...
如此可以透過條件判別來針對平台特性呼叫在 schedule() 中呼叫對應的排程指令


簡短列出這些日子看到的有趣東西, 一方面也做個紀錄


2018年3月5日 星期一

"人生剩利組"觀後感

 

的確, 很多時候你想要有什麼樣的結果, 最好就先做準備, 也就是 "想要xxxx, 那就先 oooo", 的確這是最直接的, 也就是"現況是選擇造成的", 若這句話放眼在未來, 那麼的確就是要怎麼收穫先那麼哉. 但這不是拍給人生剛起步看的勵志電影, 電影原名"Brad's Status" 其實潛在說明了一些事情, 其實個人看法是電影想談很重要的一點: "每個人並不是總是清楚知道(甚至可能最後也沒能知道), 人生中到底想要的是什麼, 但是事後的在意卻是難以避免."
 
這電影其實有更多可以談的地方, 首先是主角的妻子, 戲份不多但是卻是影響主角很重要的角色, 必須要瞭解他們生活了至少近 20 年. 主角的成就感, 價值觀, 生活滿意度, 工作態度都受到彼此影響, 這些在主角省思時也都提到, 或許妻子讓他不那麼充滿幹勁, 而又變得容易滿足.
個人認為在機場一幕中反覆被提起, 但相較之下又派不上用場, 但最後還是沒法拋棄的航空公司會員銀卡, 其實是人生累積的一種類比與具像. 事先買了廉價機票, 但後來覺得難得的旅程想要一搏, 卻發現自身有的籌碼沒有高人一等, 看到別人的待遇與無法對家人交代, 敬愛的老師過世然而卻沒被通知與參與告別, 這些都不是單純的目標與達成, 而是多少是許多社會運作下的壓抑, 難免的焦慮, 挫折與自我懷疑. 而再對比兒子大學精彩人生剛起步, 而自己能幫得不多, 也或許是希望在過程中能逞一些威風. 另外兒子儘管優秀, 也碰到了一些必定的人生不如預期的事(重要關鍵搞砸, 認為指導老師跟預期落差大.. 等等).
 
主角因為大學同窗的後續種種, 一方面自卑一方面又腦補了一些事情, 然而其實終究也發現, 那些之後自己認為都飛黃騰達的同窗(特別注意, 觀眾對於當年同窗的瞭解, 事實上都是透過主角的幻想畫面), 實則並非如他一直以來想像的那麼夢幻美好. 除了成就上與交誼上的挫折與失落, 另一方面主角兒子的成長也給予主角省思. 儘管因為兒子因素而求於多位以往的朋友, 從而多少得知近況, 然而最後主角也無法自己地吐露真心話而離開了飯局. 而這些都還是無法改變他與以往同窗間客觀的差距.
 
最有趣的是, 主角與兒子的一位愛好社會運動的社團學姐的互動, 儘管因為主角同窗談及的風花雪月讓他有些許遐想(?), 其實儘管電影沒有描述, 但一個人可以談一整晚自己的工作生涯, 多少都是真心喜愛所做的事情, 儘管言語上的自我貶抑, 主角多少是因為有人能夠瞭解與願意花時間談他在乎的專業生涯, 該位學姐在想法上其實與他的妻子有所重疊, 甚至那句 "你很幸運", 其實與一開始他妻子與他在睡前的互動也有著呼應的味道.
 
"人生剩利組" 談的是職業籃球場上, 當已打到第三節過一半, 你亦敵亦友的隊友與對方精英球員都打得比你好, 當下你知道你不會是 MVP, 也不是該場吸睛的鋒頭角色, 但你喜歡長久以來維持的步調與佔的位置, 那麼該用什麼想法與態度看待過去的上半場, 當下進行的第三節, 以及最後的第四節?
 
這些態度與價值是否有標準答案? 因人而異或是完全沒有, 如同最後的結局那般, 只能不斷地以自己的理解, 透過思考修正, 再提醒自己, ...

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

這是最後四節的中譯部分
官方 Tutorial 的翻譯也到此告一段落
若有不恰當, 錯譯或是更好的表示方式還請不吝指教
以下為前7個部分的聯結

Halide Tutorial 非官方中譯 - Part 1
Halide Tutorial 非官方中譯 - Part 2
Halide Tutorial 非官方中譯 - Part 3
Halide Tutorial 非官方中譯 - Part 4
Halide Tutorial 非官方中譯 - Part 5
Halide Tutorial 非官方中譯 - Part 6
Halide Tutorial 非官方中譯 - Part 7

後續希望能針對應用這些技巧提供心得與 case study
==

Lesson 19: 包裝函式 (Wrapper Funcs)

// 這節示範如何使用 Func::in 與 ImageParam::in 對一個函式在不同地方以不同方式排程
// 並且階段地自 Func 或 ImageParam 載入

#include "Halide.h"
#include  <stdio.h>

using namespace Halide;

int main(int argc, char **argv) {
    // 宣告後續會使用到的變數
    Var x("x"), y("y"), xo("xo"), yo("yo"), xi("xi"), yi("yi"); 
    // 這節將使用 Func::in 與 ImageParam::in 指令來包裝一個 Func 或是 ImageParam
    {
        // 考量一個簡單二階 pipeline
        Func f("f_local"), g("g_local");
        f(x, y) = x + y;
        g(x, y) = 2 * f(x, y) + 3;

        f.compute_root();

        // 這將產生下列巢狀 loop:
        // for y:
        //   for x:
        //     f(x, y) = x + y
        // for y:
        //   for x:
        //     g(x, y) = 2 * f(x, y) + 3

        // 使用 Func::in 能夠在介於 f 與 g 之間插入一個單獨排程的函式
        Func f_in_g = f.in(g);
        f_in_g.compute_root(); 
        // 同樣地, 能夠如下地串聯起來:
        // f.in(g).compute_root();
        // 這將產生下列巢狀 loop:
        // for y:
        //   for x:
        //     f(x, y) = x + y
        // for y:
        //   for x:
        //     f_in_g(x, y) = f(x, y)
        // for y:
        //   for x:
        //     g(x, y) = 2 * f_in_g(x, y) + 3

        g.realize(5, 5); 
        // 下圖為視覺化結果
 
        // 排程指令 f.in(g) 會以包裝後的函式取代在 'g' 中 'f' 的呼叫.
        // 實際上它以下列方式改寫了上面原本的 pipeline
        {
            Func f_in_g("f_in_g"), f("f"), g("g");
            f(x, y) = x + y;
            f_in_g(x, y) = f(x, y);
            g(x, y) = 2 * f_in_g(x, y) + 3;

            f.compute_root();
            f_in_g.compute_root();
            g.compute_root();
        }
        // 在隔離方式上, 像轉換的計算似乎沒多大意義, 但這能被應用在多樣的排程技巧上
    }

    { 
        // 在上面的排程, 僅有 'g' 所產生的 'f' 呼叫被取代
        // 其他對 f 產生的呼叫依然直接地使用 'f'
        // 若希望廣域地以一個包裝函式取代所有 'f' 的呼叫, 那麼就使用 f.in()
        // 考慮下列有兩個 stage 使用 f 的三階 pipeline:
        Func f("f_global"), g("g_global"), h("h_global");
        f(x, y) = x + y;
        g(x, y) = 2 * f(x, y);
        h(x, y) = 3 + g(x, y) - f(x, y);
        f.compute_root();
        g.compute_root();
        h.compute_root(); 
        // 將所有在 'g' 與 'h' 中的 'f' 呼叫以一個包裝函式取代:
        f.in().compute_root();

        // 等義的巢狀 loop:
        // for y:
        //   for x:
        //     f(x, y) = x + y
        // for y:
        //   for x:
        //     f_in(x, y) = f(x, y)
        // for y:
        //   for x:
        //     g(x, y) = 2 * f_in(x, y)
        // for y:
        //   for x:
        //     h(x, y) = 3 + g(x, y) - f_in(x, y)

        h.realize(5, 5); 
        // 下圖為視覺化結果
 
    }

    { 
        // 亦能夠給予 g 與 h 屬於各自的 f 包裝函式
        // 這次在各自巢狀 loop 內部排程, 這是無法以單一包裝函式所達到的

        Func f("f_unique"), g("g_unique"), h("h_unique");
        f(x, y) = x + y;
        g(x, y) = 2 * f(x, y);
        h(x, y) = 3 + g(x, y) - f(x, y);

        f.compute_root();
        g.compute_root();
        h.compute_root();

        f.in(g).compute_at(g, y);
        f.in(h).compute_at(h, y);

        // 這產生了下列巢狀 loop:
        // for y:
        //   for x:
        //     f(x, y) = x + y
        // for y:
        //   for x:
        //     f_in_g(x, y) = f(x, y)
        //   for x:
        //     g(x, y) = 2 * f_in_g(x, y)
        // for y:
        //   for x:
        //     f_in_h(x, y) = f(x, y)
        //   for x:
        //     h(x, y) = 3 + g(x, y) - f_in_h(x, y)

        h.realize(5, 5);
        // 下圖為視覺化結果

     }

    {
        // 至今這可能像是許多無意義的記憶體複製
        // 而 Func::in 能與其他排程指令合併來達到不同的用途
        // 首先確認對於不同的函式建立了個別的實現並且以不同方式排程
 
        // 以幾乎相同的 pipeline 開始
        Func f("f_sched"), g("g_sched"), h("h_sched");
        f(x, y) = x + y;
        g(x, y) = 2 * f(x, y);
        // h 使用 f 的一個較遠區域
        h(x, y) = 3 + g(x, y) - f(x + 93, y - 87);

        // 這次以 inline 方式使用 f
        // f.compute_root();
        g.compute_root();
        h.compute_root();

        f.in(g).compute_at(g, y);
        f.in(h).compute_at(h, y);

        // g 與 h 現在透過個別的包裝函式來呼叫 f. The wrappers are
        // 排程是透過包裝函式, 若無則 f 是以 inline 方式置於兩個包裝函式中.
        // 這兩者將獨立計算呼叫其所需的 f 區域.
        // 當以 compute_root 排程 f 函式, 將會計算 g 與 h 所需範圍的區域方塊,
        // 而當中可能多數都是不被需要的資料.
 
        // 因此亦能夠各自不同地排程
        // 為了排程, 包裝函式自原始函式繼承了純變數, 
        // 因此能夠使用在定義 f 時使用一樣的 x 與 y:
        f.in(g).vectorize(x, 4);
        f.in(h).split(x, xo, xi, 2).reorder(xo, xi);

        // 請注意乎要 f.in(g) 在第二次呼叫時回傳的是在第一次呼叫已被建構的包裝函式,
        // 並不會建構一個新的.

        h.realize(8, 8);
        // 下圖為視覺化結果


        // 請注意由於 f 是以 inline 方式被兩個包裝函式使用,
        // 因此是包裝函式執行 f 的計算工作, 而非只是從已經計算好的資料載入
    }

    {
        // Func::in 對於透過 Func 階段載入可能在堆疊或GPU 共享記憶體的中介 buffer 相當有用
 
        // 考量一個轉置部份 compute_root 計算後結果的 pipeline:

        Func f("f_transpose"), g("g_transpose");
        f(x, y) = sin(((x + y) * sqrt(y)) / 10);
        f.compute_root();

        g(x, y) = f(y, x);

        // 執行策略上要載入一個 f 的 4x4 tile 到暫存器中, 於暫存器中轉置並寫到 g 的 4x4 tile.
        // 這裡使用 Func::in 來表示:
 
        Func f_tile = f.in(g);

        // 如此有了一個三階 pipeline:
        // f -> f_tile -> g 
        // f_tile 會載入多個 f 向量, 寫入暫存器中並轉置, g 將這些資料寫回主記憶體.
        g.tile(x, y, xo, yo, xi, yi, 4, 4)
            .vectorize(xi)
            .unroll(yi);
 
        // 這裡將在 g 的 tile 計算 f_transpose,
        // 並且使用 Func::reorder_storage 來說明 f_transpose 應以 column-major 方式存放
        // 因此對於 g 的載入這些資料能以向量載入的形式達成
       f_tile.compute_at(g, xo)
            .reorder_storage(y, x)
            .vectorize(x)
            .unroll(y); 
        // 必須要小心確認 f_transpose 只以常數索引方式存取
        // 全部於各自 compute_at 層次存在的 loop 的 unrolling/vectorization
        // 有著這樣的特性. 僅被常數索引存取的記憶體配置將會被提升到暫存器中.
 
        g.realize(16, 16);
        // 下圖為視覺化結果

    }

    {
        // ImageParam::in 如同 Func::in 的行為, 能夠以類似的方式做階段載入
        // 不再以轉置為例, 而用 ImageParam::in 來階段載入輸入影像至 GPU 共享記憶體,
        // 如同明確管理的 cache 一般有效地使用 shared/local memory.
        ImageParam img(Int(32), 2);

        // 計算些微模糊化的輸入影像
        Func blur("blur");
        blur(x, y) = (img(x - 1, y - 1) + img(x, y - 1) + img(x + 1, y - 1) +
                      img(x - 1, y    ) + img(x, y    ) + img(x + 1, y    ) +
                      img(x - 1, y + 1) + img(x, y + 1) + img(x + 1, y + 1));

        blur.compute_root().gpu_tile(x, y, xo, yo, xi, yi, 8, 8); 
        // 以 ImageParam::in 建構的包裝函式 有著以 _0, _1 .. 等等所命名的純變數
        // 對 blur 每個 tile 的變數排程, 並且將 _0 與 _1 對應到 gpu 執行緒
        img.in(blur).compute_at(blur, xo).gpu_threads(_0, _1);
         // Without Func::in, computing an 8x8 tile of blur would do
        // 8*8*9 loads to global memory. With Func::in, the wrapper
        // does 10*10 loads to global memory up front, and then blur
        // does 8*8*9 loads to shared/local memory.
 
        // 在不使用 Func::in 情況下, blur 計算 8x8 tile 需要 8*8*9 次 global memory 載入
        // 而使用 With Func::in, 包裝函式於開始會作 10*10 次 global memory 載入
        // 接著 blur 函式會自 shared/local memory 作 8*8*9 次載入

        // 如同 Lesson 12 , 選擇適當的 GPU API
        Target target = get_host_target();
        if (target.os == Target::OSX) {
            target.set_feature(Target::Metal);
        } else {
            target.set_feature(Target::OpenCL);
        }

        // 建立一個有趣的輸入影響
        Buffer input(258, 258);
        input.set_min(-1, -1);
        for (int y = input.top(); y <= input.bottom(); y++) {
            for (int x = input.left(); x <= input.right(); x++) {
                input(x, y) = x * 17 + y % 4;
            }
        }

        img.set(input);
        blur.compile_jit(target);
        Buffer<int> out = blur.realize(256, 256);

        // 確認結果一致
        for (int y = out.top(); y <= out.bottom(); y++) {
            for (int x = out.left(); x <= out.right(); x++) {
                int val = out(x, y);
                int expected = (input(x - 1, y - 1) + input(x, y - 1) + input(x + 1, y - 1) +
                                input(x - 1, y    ) + input(x, y    ) + input(x + 1, y    ) +
                                input(x - 1, y + 1) + input(x, y + 1) + input(x + 1, y + 1));
                if (val != expected) {
                    printf("out(%d, %d) = %d instead of %d\n",
                           x, y, val, expected);
                    return -1;
                }
            }
        }
    }

    {
        // Func::in 也能夠用來以相同巢狀 loop 將多階合併為單一函式
        // 考量下列計算每個 pixel 數值的並由左至右翻轉每個 scanline 的 pipeline
        Func f("f_group"), g("g_group"), h("h_group");

        // 初始化 f
        f(x, y) = sin(x - y);
        RDom r(1, 7);

        // 由左至右翻轉
        f(r, y) = (f(r, y) + f(r - 1, y)) / 2;

        // 由右至左翻轉
        f(7 - r, y) = (f(7 - r, y) + f(8 - r, y)) / 2;
        // 接著嘗試複雜的存取模式: 一個循環的 45 度旋轉
        g(x, y) = f((x + y) % 8, (x - y) % 8);

        // 由於以複雜的方式存取, 因此 f 應以 compute_root 排程
        // 但這也表示 f 所有的階層將在巢狀 loop 中計算:

        // for y:
        //   for x:
        //     f(x, y) = sin(x - y)
        // for y:
        //   for r:
        //     f(r, y) = (f(r, y) + f(r - 1, y)) / 2
        // for y:
        //   for r:
        //     f(7 - r, y) = (f(7 - r, y) + f(8 - r, y)) / 2
        // for y:
        //   for x:
        //     g(x, y) = f((x + y) % 8, (x - y) % 8);
        // 若以共同的 loop y 來對 f 作排程能夠得到更佳的區域特性(locality)
        // 能夠以包裝函式計算 f 的 scanline  來達成:
        f.in(g).compute_root();
        f.compute_at(f.in(g), y);
        // 對於一個函式有更新階 (update stage)時, 
        // f 有著預設在 consumer 最內層 loop 計算的排程, 這裡也就是 f.in(g)
        // 因此產生如下有較佳區域性的巢狀 loop:
 
        // for y:
        //   for x:
        //     f(x, y) = sin(x - y)
        //   for r:
        //     f(r, y) = (f(r, y) + f(r - 1, y)) / 2
        //   for r:
        //     f(7 - r, y) = (f(7 - r, y) + f(8 - r, y)) / 2
        //   for x:
        //     f_in_g(x, y) = f(x, y)
        // for y:
        //   for x:
        //     g(x, y) = f_in_g((x + y) % 8, (x - y) % 8);
        // 能額外對 f 的初始作向量化, 並且將 pixel 數值自 f 帶給其包裝函式:
        f.vectorize(x, 4);
        f.in(g).vectorize(x, 4);

        g.realize(8, 8);
        // 下圖為視覺化結果

    }

    printf("Success!\n");

    return 0;
}

==

Lesson 20: 複製函式(Cloning Funcs)


// 這節示範如何使用 Func::clone_in 來建構一個函式的複製

#include "Halide.h"
#include <stdio.h>

using namespace Halide;

int main(int argc, char **argv) {
    // 首先宣告後續會用到的變數
    Var x("x"), y("y"), xo("xo"), yo("yo"), xi("xi"), yi("yi");

    // 這結是關於使用 Func::clone_in 指令來複製一個 Func 函式
    {
        // 考量一個簡單二階的 pipeline:
        Func f("f_single"), g("g_single"), h("h_single");
        f(x, y) = x + y;
        g(x, y) = 2 * f(x, y) + 3;
        h(x, y) = f(x, y) + g(x, y) + 10;

        f.compute_root();
        g.compute_root();
        h.compute_root();

        // 這產生下列巢狀 loop:
        // for y:
        //   for x:
        //     f(x, y) = x + y
        // for y:
        //   for x:
        //     g(x, y) = 2 * f(x, y) + 3
        // for y:
        //   for x:
        //     h(x, y) = f(x, y) + g(x, y) + 10

        // 使用 Func::clone_in, 能夠以獨立排程的 'f' 複製 取代 'g' 中的 'f' 呼叫:
        Func f_clone_in_g = f.clone_in(g);
        f_clone_in_g.compute_root();

        // 同樣地, 能夠以串聯方式來排程:
        // f.clone_in(g).compute_root();

        // 這產生下列巢狀 loop:
        // for y:
        //   for x:
        //     f(x, y) = x + y
        // for y:
        //   for x:
        //     f_clone_in_g(x, y) = x + y
        // for y:
        //   for x:
        //     g(x, y) = 2 * f_clone_in_g(x, y) + 3
        // for y:
        //   for x:
        //     h(x, y) = f(x, y) + g(x, y) + 10

        h.realize(5, 5);

        // 排程指令 f.clone_in(g) 以一個 'f' 的複製取代 'g' 中所有 'f' 的呼叫, 並回傳此複製
        // 本質上來說, 它以下列方式改寫上方原有的 pipeline:
        {
            Func f_clone_in_g("f_clone_in_g"), f("f"), g("g"), h("h");
            f(x, y) = x + y;
            f_clone_in_g(x, y) = x + y;
            g(x, y) = 2 * f_clone_in_g(x, y) + 3;
            h(x, y) = f(x, y) + g(x, y) + 10;

            f.compute_root();
            f_clone_in_g.compute_root();
            g.compute_root();
            h.compute_root();
        }
    }

    {
        // 在上面的排程只有 g 所產生的 'f' 的呼叫被取代
        // 其他對於 'f' 的呼叫依然直接呼叫 'f' 函式. (這裡也就是. 'h' 依然呼叫 'f' 而非複製)
        // 若期望以一個複製取代 'g' 與 'h' 對於 'f' 的呼叫, 只要呼叫 f.clone_in({g, h}).

        // 考量一個三階 pipeline, 其中兩階參考使用到 f:
        Func f("f_group"), g("g_group"), h("h_group"), out("out_group");
        f(x, y) = x + y;
        g(x, y) = 2 * f(x, y);
        h(x, y) = f(x, y) + 10;
        out(x, y) = f(x, y) + g(x, y) + h(x, y);

        f.compute_root();
        g.compute_root();
        h.compute_root();
        out.compute_root();

        // 以一個複製來取代 'g' 與 'h' 中所有對 'f' 的呼叫:
        f.clone_in({g, h}).compute_root();

        // 等義的巢狀 loop:
        // for y:
        //   for x:
        //     f(x, y) = x + y
        // for y:
        //   for x:
        //     f_clone(x, y) = x + y
        // for y:
        //   for x:
        //     g(x, y) = 2 * f_clone(x, y)
        // for y:
        //   for x:
        //     h(x, y) = f_clone(x, y) + 10
        // for y:
        //   for x:
        //     out(x, y) = f(x, y) + g(x, y) + h(x, y)

        out.realize(5, 5);
    }

    {
        // 一個應用 Func::clone_in() 的情況是當兩個 consumers 使用相當的 producer
        // 然而所需的範圍有非常的區隔. 考慮以下情況的範例:
        Func f("f"), g("g"), h("h");
        f(x) = x;
        g(x) = 2 * f(0);
        h(x) = f(99) + 10;

        // 將 'f' 以 compute_root 方式排程.
        f.compute_root();
        // 由於 'g' 與 'f' 都參考使用了 'f',  需要的 'f' 在 x 維度的範圍是 [0, 99]
        // 等義的巢狀 loop 為:
        // for x = 0 to 99
        //   f(x) = x
        // for x:
        //   g(x) = 2 * f(0)
        // for x:
        //   h(x) = f(99) + 10

        // 若 'f' 的計算成本相當昂貴, 那麼 'g' 與 'h' 最好能有著自己的一份 'f',
        // 來避免不必要的 'f' 計算.
        // 透過下列來對 'g' 與 'h' 建構區隔的 'f' 複製:
        f.clone_in(g).compute_root(); 
        // 等義的巢狀 loop 為:
        // f(0) = x
        // f_clone(99) = x
        // for x:
        //   g(x) = 2 * f_clone(0)
        // for x:
        //   h(x) = f(99) + 10
    }

    printf("Success!\n");

    return 0;
}
 
==

Lesson 21: 自動排程器(Auto-Scheduler) (Part 1, Part 2)


// 至今都是手工撰寫 Halide 排程, 但是有可能要求 Halide 建議一個合理的排程.
// 這稱為自動排程.
// 這節示範如何使用自動排程器來產生一個可剪貼套用並能後續改善的 CPU 排程
#include "Halide.h"
#include <stdio.h>

using namespace Halide;

// 定義一個自動排成器
class AutoScheduled : public Halide::Generator {
public:
    Input<Buffer<float>>  input{"input", 3};
    Input<float>          factor{"factor"};

    Output<Buffer<float>> output1{"output1", 2};
    Output<Buffer<float>> output2{"output2", 2};

    Expr sum3x3(Func f, Var x, Var y) {
        return f(x-1, y-1) + f(x-1, y) + f(x-1, y+1) +
               f(x, y-1)   + f(x, y)   + f(x, y+1) +
               f(x+1, y-1) + f(x+1, y) + f(x+1, y+1);
    }

    void generate() {
        // 這裡使用 Harris corner detection 作為演算
        Func in_b = BoundaryConditions::repeat_edge(input);

        gray(x, y) = 0.299f * in_b(x, y, 0) + 0.587f * in_b(x, y, 1) + 0.114f * in_b(x, y, 2);

        Iy(x, y) = gray(x-1, y-1)*(-1.0f/12) + gray(x-1, y+1)*(1.0f/12) +
                   gray(x, y-1)*(-2.0f/12) + gray(x, y+1)*(2.0f/12) +
                   gray(x+1, y-1)*(-1.0f/12) + gray(x+1, y+1)*(1.0f/12);

        Ix(x, y) = gray(x-1, y-1)*(-1.0f/12) + gray(x+1, y-1)*(1.0f/12) +
                   gray(x-1, y)*(-2.0f/12) + gray(x+1, y)*(2.0f/12) +
                   gray(x-1, y+1)*(-1.0f/12) + gray(x+1, y+1)*(1.0f/12);

        Ixx(x, y) = Ix(x, y) * Ix(x, y);
        Iyy(x, y) = Iy(x, y) * Iy(x, y);
        Ixy(x, y) = Ix(x, y) * Iy(x, y);
        Sxx(x, y) = sum3x3(Ixx, x, y);
        Syy(x, y) = sum3x3(Iyy, x, y);
        Sxy(x, y) = sum3x3(Ixy, x, y);
        det(x, y) = Sxx(x, y) * Syy(x, y) - Sxy(x, y) * Sxy(x, y);
        trace(x, y) = Sxx(x, y) + Syy(x, y);
        harris(x, y) = det(x, y) - 0.04f * trace(x, y) * trace(x, y);
        output1(x, y) = harris(x + 2, y + 2);
        output2(x, y) = factor * harris(x + 2, y + 2);
    }

    void schedule() {
        if (auto_schedule) {
            // 自動排程器需要依序評估所有 input/output 大小以及參數數值,
            // 來比較不同的選擇方案來決定一個好的排程.

            // 使用 set_bounds_estimate() 來提供輸入影像的每個維度評估 (最小以及延伸數值),
            // set_bounds_estimate() 帶入對應維度的 (最小, 延伸數值) 作為參數
            input.dim(0).set_bounds_estimate(0, 1024);
            input.dim(1).set_bounds_estimate(0, 1024);
            input.dim(2).set_bounds_estimate(0, 3);

            // 使用 set_estimate 來評估參數數值(parameter values).
            factor.set_estimate(2.0f);

            // 使用 estimate() 來評估 pipeline 輸出的每個維度(最小與延伸數值)
            // estimate() 帶入 (dim_name, 最小, 延伸數值) 作為參數
            output1.estimate(x, 0, 1024)
                   .estimate(y, 0, 1024);

            output2.estimate(x, 0, 1024)
                   .estimate(y, 0, 1024);

            // 技術上來說, 評估數值可以是任意值, 但愈接近應用數值形式, 產生的排程愈好.

            // 為了自動排程 pipeline, 不需要做其他事情:
            // 每個 Generator 潛在地有著一個名為 "auto_schedule" 的 GeneratorParam ;
            // 若將其設為 true, Halide 將對 pipeline 所有的輸出自動地呼叫 auto_schedule().

            // 每個 Generator 潛在地有著一個名為 "machine_params" 的 GeneratorParams ;
            // 這能允許指定計算架構的特對於自動排成器,  通常在 Makefile 中指定
            // 若沒有指定, 自動排成器將使用通用 CPU 的預設架構參數

            // (這段屬於架構專有解釋, 略譯).
            // Let's see some arbitrary but plausible values for the machine parameters.
            //
            //      const int kParallelism = 32;
            //      const int kLastLevelCacheSize = 16 * 1024 * 1024;
            //      const int kBalance = 40;
            //      MachineParams machine_params(kParallelism, kLastLevelCacheSize, kBalance);
            //
            // The arguments to MachineParams are the maximum level of parallelism
            // available, the size of the last-level cache (in KB), and the ratio
            // between the cost of a miss at the last level cache and the cost
            // of arithmetic on the target architecture, in that order.

            // 請注意當使用自動排程器時,  不能對 pipeline 套用任何排程, 否則將換產生錯誤
            // 目前自動排程器無法處理局部排程的 pipeline.

            // 當 HL_DEBUG_CODEGEN 設為 3 或更大數值, 排程將會透過 stdout 印出
            // 一個更好的方式是加入 "schedule" 到給 Generator 的 -e 旗標
            // (在 CMake 與 Bazel 這是透過使用 "extra_outputs" 旗標.)

            // 產生的排程為能夠直接剪貼小幅修改而使用的 Halide C++ 原始碼檔案
            // 這能作為起始的排程, 並再反覆地改善.
            // 請注意目前的自動排程器僅能夠產生 CPU 排程,
            // 且搭配 tiling, 簡單的向量化與平行化
            // 並不會處理 line buffer, 儲存次序調整或是歸納處理

            // 這個範例對於上述宣告的評估與架構參數, 自動排程器傳回下列排程:
            //
            // Var x_i("x_i");
            // Var x_i_vi("x_i_vi");
            // Var x_i_vo("x_i_vo");
            // Var x_o("x_o");
            // Var x_vi("x_vi");
            // Var x_vo("x_vo");
            // Var y_i("y_i");
            // Var y_o("y_o");
            //
            // Func f0 = pipeline.get_func(3);
            // Func f1 = pipeline.get_func(7);
            // Func f11 = pipeline.get_func(14);
            // Func f2 = pipeline.get_func(4);
            // Func output1 = pipeline.get_func(15);
            // Func output2 = pipeline.get_func(16);
            //
            // {
            //     Var x = f0.args()[0];
            //     f0
            //         .compute_at(f11, x_o)
            //         .split(x, x_vo, x_vi, 8)
            //         .vectorize(x_vi);
            // }
            // {
            //     Var x = f1.args()[0];
            //     f1
            //         .compute_at(f11, x_o)
            //         .split(x, x_vo, x_vi, 8)
            //         .vectorize(x_vi);
            // }
            // {
            //     Var x = f11.args()[0];
            //     Var y = f11.args()[1];
            //     f11
            //         .compute_root()
            //         .split(x, x_o, x_i, 256)
            //         .split(y, y_o, y_i, 128)
            //         .reorder(x_i, y_i, x_o, y_o)
            //         .split(x_i, x_i_vo, x_i_vi, 8)
            //         .vectorize(x_i_vi)
            //         .parallel(y_o)
            //         .parallel(x_o);
            // }
            // {
            //     Var x = f2.args()[0];
            //     f2
            //         .compute_at(f11, x_o)
            //         .split(x, x_vo, x_vi, 8)
            //         .vectorize(x_vi);
            // }
            // {
            //     Var x = output1.args()[0];
            //     Var y = output1.args()[1];
            //     output1
            //         .compute_root()
            //         .split(x, x_vo, x_vi, 8)
            //         .vectorize(x_vi)
            //         .parallel(y);
            // }
            // {
            //     Var x = output2.args()[0];
            //     Var y = output2.args()[1];
            //     output2
            //         .compute_root()
            //         .split(x, x_vo, x_vi, 8)
            //         .vectorize(x_vi)
            //         .parallel(y);
            // }
        } else {
            // 這裡能夠宣告先前手寫排程或是剪貼自動排程器所產生的排程.
            // 為了比較自動排程與基本的排程差異, 這裡使用了很陽春的排程
            gray.compute_root();
            Iy.compute_root();
            Ix.compute_root();
        }
    }
private:
    Var x{"x"}, y{"y"}, c{"c"};
    Func gray, Iy, Ix, Ixx, Iyy, Ixy, Sxx, Syy, Sxy, det, trace, harris;
};

// 如同在 lesson 15, 註冊 generator 後搭配 tools/GenGen.cpp 來一同編譯
HALIDE_REGISTER_GENERATOR(AutoScheduled, auto_schedule_gen)

// 編譯之後來看如何使用

// 這份 code 實際使用編譯出的 pipeline, 因此不會使用到 libHalide,
// 因此無需引入 Halide.h.
//
// 相對地, 這使用了上面的程式所產生的 header files
#include "auto_schedule_false.h"
#include "auto_schedule_true.h"

// 使用 Halide::Runtime::Buffer 類別來傳遞 pipeline 的資料輸入輸出
#include "HalideBuffer.h"
#include "halide_benchmark.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

int main(int argc, char **argv) {
    // 宣告與初始輸入影像
    Halide::Runtime::Buffer<float> input(1024, 1024, 3);

    for (int c = 0; c < input.channels(); ++c) {
        for (int y = 0; y < input.height(); ++y) {
            for (int x = 0; x < input.width(); ++x) {
                input(x, y, c) = rand();
            }
        }
    }

    Halide::Runtime::Buffer<float> output1(1024, 1024);
    Halide::Runtime::Buffer<float> output2(1024, 1024);
    // 為了評測而對每個版本 (沒有自動排程版本以及自動排程版本)執行數次
    double auto_schedule_off = Halide::Tools::benchmark(2, 5, [&]() {
        auto_schedule_false(input, 2.0f, output1, output2);
    });
    printf("Manual schedule: %gms\n", auto_schedule_off * 1e3);

    double auto_schedule_on = Halide::Tools::benchmark(2, 5, [&]() {
        auto_schedule_true(input, 2.0f, output1, output2);
    });
    printf("Auto schedule: %gms\n", auto_schedule_on * 1e3);

    // auto_schedule_on 應該會比較快, 因為 auto_schedule_off 版本的排程很簡陋,
    assert(auto_schedule_on < auto_schedule_off);

    return 0;
}

在 ARM 平台上使用 Function Multi-Versioning (FMV) - 以使用 Android NDK 為例

Function Multi-Versioning (FMV) 過往的 CPU 發展歷程中, x86 平台由於因應各種應用需求的提出, 而陸陸續續加入了不同的指令集, 此外也可能因為針對市場做等級區隔, 支援的數量與種類也不等. 在 Linux 平台上這些 CPU 資訊可以透過...