Halide視覺神經網絡優化
概述
Halide是用C++作為宿主語言的一個圖像處理相關的DSL(Domain Specified Language)語言，全稱領域專用語言。主要的作用為在軟硬層面上(與算法本身的設計無關)實現對算法的底層加速，有必要對其有一定的了解。因為不論是傳統的圖像處理方法亦或是深度學習應用都使用到了halide的思想。
其中，在OpenCV(傳統圖像處理庫)中部分算法使用了Halide后端，而TVM(神經網絡編譯器)也是用了Halide的思想去優化神經網絡算子。

Halide到底是什么？看上面那張圖，同樣的一個算法處理(局部拉普拉斯變換)，使用直接的C++語言寫出來算法速度很慢，Adobe公司使用3個月對這個算法進行了優化(手工優化)使這個算法的速度快了10倍，但是如果使用了Halide，只需要幾行代碼，就可以使這個算法比之前普通直接的算法快上20倍。
一句話來說，Halide大大節省了手動優化底層算法的時間，只需要關心算法的設計。
Halide為什么可以優化算法
Halide的特點是其圖像算法的計算的實現（Function和Expression）和這些計算在計算硬件單元上的調度（Schedule）是分離的，其調度以Function為單位。最終將整個圖像算法轉換為高效率的多層for循環，for循環的分部數據范圍劃分和數據加載都是由Halide來完成的，而且可以實現數據的加載和算法計算的Overlay，掩蓋數據加載導致的延遲。Halide的Schedule可以由程序員來指定一些策略，指定硬件的buffer大小，緩沖線的相關設置，可以根據不同的計算硬件的特性，實現高效率的計算單元的調度，而圖像算法的計算實現卻不需要修改。
決定算法在某個硬件平臺上執行時性能的“三角力量”如下。

其中，算法本身的設計是一方面，一個好的算法往往效率會高很多。而另外一個方面就是算法中計算順序的組織，而Halide可以改變的就是算法在某個硬件平臺上的計算順序：

其中Halide可以在硬件平臺上為算法實現并行和良好的緩存一致性：
示例
Halide中的經典模糊化(blurred)圖像的例子，演示一下(以下代碼也可以在自己的電腦上測試觀察結果)，這里用OpenCV來對圖像進行操作進行演示：
首先設計一個可以對圖像進行模糊的操作函數：
// in為輸入原始圖像 blury為輸出模糊后的圖像
void box_filter_3x3(const Mat &in, Mat &blury) { Mat blurx(in.size(), in.type()); for(int x = 1; x < in.cols-1; x ++) for(int y = 0 ; y < in.rows; y ++) blurx.at<uint8_t >(y, x) = static_cast<uint8_t>( (in.at<uint8_t >(y, x-1) + in.at<uint8_t >(y, x) + in.at<uint8_t >(y, x+1)) / 3); for(int x = 0; x < in.cols; x ++) for(int y = 1 ; y < in.rows-1; y ++) blury.at<uint8_t >(y, x) = static_cast<uint8_t>( (blurx.at<uint8_t >(y-1, x) + blurx.at<uint8_t >(y, x) + blurx.at<uint8_t >(y+1, x)) / 3); }
對圖像模糊操作很簡單，首先在x軸上對每個像素點，以及周圍的兩個點進行求和平均，然后再到y軸上進行同樣的操作，這樣相當于一個3×3平均卷積核，對整個圖像進行操作，這里就不進行詳細描述了。
準備一張(1920,1080)的圖像，對其進行100次上述操作，并記錄時間，發現Time used:4521.72 ms。
然后，簡單改變一下執行次序，將上述循環嵌套中的x和y的順序改變一下：
Mat blurx(in.size(), in.type()); // 這里進行了嵌套的變換 for(int y = 0 ; y < in.rows; y ++) for(int x = 1; x < in.cols-1; x ++) blurx.at<uint8_t >(y, x) = static_cast<uint8_t>( (in.at<uint8_t >(y, x-1) + in.at<uint8_t >(y, x) + in.at<uint8_t >(y, x+1)) / 3); // 這里進行了嵌套的變換 for(int y = 1 ; y < in.rows-1; y ++) for(int x = 0; x < in.cols; x ++) blury.at<uint8_t >(y, x) = static_cast<uint8_t>( (blurx.at<uint8_t >(y-1, x) + blurx.at<uint8_t >(y, x) + blurx.at<uint8_t >(y+1, x)) / 3); }
同樣，執行100次并記錄時間：發現Time used:3992.35 ms，可以發現，下面的模糊操作執行的速度比上面的快一些。當然，這只是一副示例圖像，如果這張圖像的長寬差距比較大(例如1:10)、亦或是要某一個時刻處理幾萬次這樣的操作，一旦量級起來，那么這兩者的差距就不是一點半點了。
硬件原理
這差別和算法本身沒什么關系，而與硬件的設計是有巨大關系，例如并行性和局部性。
下面是Adobe工程師對上述的算法在硬件層面上極致優化結果，比之前的算法快了10倍，其中用到了SIMD(單指令多數據流)、以及平鋪（Tiling）、展開（Unrolling）和向量化（Vectorization）等常用技術。充分利用了硬件的性能，不改變算法本身設計的前提下，最大化提升程序執行的速度。

官方示例
Halide作為一個DSL，很容易就可以使用它，這里將其源碼下下來并進行編譯。完成之后，就可以使用它了(這里省略編譯步驟，可自行在官網查閱)：
首先引用Halide頭文件，以及其它的文件。
#include “Halide.h”
#include <stdio.h> #include using namespace Halide;
初次使用Halide之前，首先需要知道halide中的一些語法：

然后，利用Halide定義兩個變量，這兩個變量單獨使用時，沒有任何意義，同時用字符串x和y為兩個變量起了名字：
Var x(“x”), y(“y”);
然后利用Func 定義一個待執行的function，并起名為gradient。
Func gradient(“gradient”);
這時定義function中每個點的執行邏輯，對于(x,y)這個點執行的邏輯為x + y。
其中x和y都是Var，而x + y這個操作在賦予給gradient的時候會自動轉化為Expr類型，這里可以理解為將x + y這個代數表達式的邏輯，賦予了gradient，最后，通過realize函數來執行整個邏輯：
gradient(x, y) = x + y; // realize 即為實現這個操作 到了這一步才會對上述的操作進行編譯并執行 Buffer output = gradient.realize(4, 4);
這個邏輯用C++來表示即為：
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); } }
而上述實現的Halide偽代碼為:
produce gradient:
for y:
for x:
gradient(…) = …
Halide默認的計算順序是行優先的，也就是x代表每一行的元素位置，y代表每一列的元素位置：

如果將其中y和x的計算順序換一下：
// 將y的順序提到x之前
gradient.reorder(y, x);
最終的計算過程就為列優先：

相應的偽代碼為：
produce gradient_col_major:
for x:
for y:
gradient_col_major(…) = …
拆分 Split
可以對每個維度進行拆分，假如依然是行優先計算，但是對x軸進行拆分，將其拆成，一個外循環，一個里循環，y軸不進行變動：
Var x_outer, x_inner;
gradient.split(x, x_outer, x_inner, 2);
這時對應的C++代碼實現為:
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); } } }
融合 fuse
或者不進行拆分，對x和y兩個軸進行融合：
Var fused;
gradient.fuse(x, y, fused);
此時對應的C++實現代碼為:
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); }
但是要知道，上述拆分和融合操作，只是對Halide所能進行的操作進行一下演示，而是，這種操作方式并沒有實際用處，也就是說實際中的計算順序并沒有改變。
平鋪 tile
這一步中就要進入Halide中比較重要的部分了，這一步中將x和y軸以4為因子間隔進行劃分，并且重新對計算的路徑進行重排序：
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);
對應的C++計算代碼為：
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); } } } }
可視化一下就是這個樣子(注意這里的示例大小為(8,8))：

這種平鋪的好處是可以充分利用相鄰的像素，例如在模糊中，會使用重疊的輸入數據(也就是存在一個元素使用兩次的情況)，如果采用這種計算方式，可以大大加快計算性能。
向量化 vector
向量化即使用cpu中的SIMD技術，一次性計算多個數據，充分利用硬件的特點，例如在x86中，可以利用SSE技術來實現這個功能。
在Halide中，首先將x軸的循環嵌套按照，內側循環因子4的方式，拆分為兩個(也就是內側循環x執行四次，外側根據總數進行計算，下例是2*4=8)，然后將內側的x循環轉化為向量的形式：
Var x_outer, x_inner;
gradient.split(x, x_outer, x_inner, 4); gradient.vectorize(x_inner);
用C++來表示即為:
for (int y = 0; y < 4; y++) { for (int x_outer = 0; x_outer < 2; x_outer++) { // The loop over x_inner has gone away, and has been // replaced by a vectorized version of the // expression. On x86 processors, Halide generates SSE // for all of this. 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]); } }
可視化后就比較明顯了，外部x每一行執行兩次，內側x變為向量的形式，一個指令集就可以執行完成：

展開 unrolling
如果在圖像中，多個像素同時共享有重疊的數據，這個時候就可以將循環展開，從而使那些可以共享使用的數據，只計算一次亦或是只加載一次。
在下面中將x軸拆分為內側和外側，因為每次內側的數值增長都是從0到1，如果將內測循環的x軸展開，就不需要每次循環到這里再讀取內測循環的x的值了：
Var x_outer, x_inner;
gradient.split(x, x_outer, x_inner, 2); gradient.unroll(x_inner);
相應的C++代碼為：
printf(“Equivalent C:\n”); for (int y = 0; y < 4; y++) { for (int x_outer = 0; x_outer < 2; x_outer++) { // Instead of a for loop over x_inner, we get two // copies of the innermost statement. { 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); } } }
融合、平鋪、并行 Fusing, tiling, and parallelizing
這一步中，將融合、平鋪和并行操作都融合到一起，來對一個8×8的圖像進行操作。首先，將x軸和y軸都按照4因子進行平鋪操作。隨后將外側的y和外側的x軸循環，進行融合(2+2=4)，再將這個融合后的操作進行并行操作，也就是同時執行這四個(2+2=4)操作：
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);
相應的C++代碼為：
// This outermost loop should be a parallel for loop, but that’s hard in 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); } } }
可視化后的結果，可以看到8×8中左上、左下、右上、右下四個區域是幾乎同時進行的(tile_index)，而每個區域和之前tile那一節的計算方式是一樣的，只不過這次換成了并行計算：

整合
這次來點大點的圖像，輸入的圖像大小為350 x 250，對其進行最優化的操作：
首先將其按照64 x 64的因子進行平鋪，其次融合y軸和x軸外側的循環操作數，最后對其進行并行操作
（這里注意下，可以看到350或者250并不能被64整除，這個不用擔心，Halide會自動處理多余或者不夠的部分）。
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); // 可以這樣連續使用.寫，因為對象函數返回的是對象本身的引用
這樣還不夠，上面已經將整個圖像平鋪為6*4個部分，而這一步中對每個平鋪后的部分再進行一次平鋪操作，這次將每個小塊按照4×2的形式平鋪為，其中y_inner_outer分成兩個(每個為y_pairs)，x_inner_outer分成四個(每個為x_vectors)，然后將每個x_vectors并行化，將y_pairs展開。
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);
以下可視化的結果為：

對應的c++展示代碼為：
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++) { // We’re vectorized across x int x = std::min(x_outer * 64, 350-64) + x_inner_outer4; int x_vec[4] = {x + 0, x + 1, x + 2, x + 3}; // And we unrolled across y int y_base = std::min(y_outer * 64, 250-64) + y_inner_outer2; { // 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; } } } } } }
到這里Halide中的基本操作就介紹完畢了。
其它
如果用Halide來寫文章一開頭，描述的模糊(blur)算法的話，會是這個樣子：
Func blur_3x3(Func input) {
Func blur_x, blur_y; Var x, y, xi, yi; // The algorithm - no storage or order blur_x(x, y) = (input(x-1, y) + input(x, y) + input(x+1, y))/3; blur_y(x, y) = (blur_x(x, y-1) + blur_x(x, y) + blur_x(x, y+1))/3; // The schedule - defines order, locality; implies storage blur_y.tile(x, y, xi, yi, 256, 32) .vectorize(xi, 8).parallel(y); blur_x.compute_at(blur_y, x).vectorize(x, 8); return blur_y; }
這段著名的代碼同時就在官方的主頁上掛著，算是一個比較好的示例。
Halide的特點
Halide這個底層優化庫有幾個比較亮眼的特點：
Explicit programmer control
The compiler does exactly what you say.
Schedules cannot influence correctness.
Exploration is fast and easy.
明確的程序控制，也就是說，如何按照這個計算的順序(與算法本身無關)是確定的，一旦已經設定好就不會再改變。
Stochastic search (autotuning)
Pick your favorite high-dimensional search.
而自動搜索，則是每個具有搜索空間的優化器都可以使用的，因為每次進行優化操作的時候，優化的因子都是不確定的，對于不同的硬件來說，不同的配置可能導致的執行速度也不一樣。因此自動隨機搜索空間因子是有必要的。
元編程
Halide的思想與元編程有著密切的關系，不僅是其設計思路或者是其執行思路，都遵循了元編程的思想，也就是代碼在編譯之前并沒有明確的執行邏輯，只有編譯過后，才會形成執行邏輯。

其它相關
halide既然作為與算法無關的底層優化器，與深度學習的結合應用肯定也是非常多的。OpenCV庫就使用了halide去優化底層的神經網絡算子，相應的benchmark結論，發現使用了halide的神經網絡運行，速度竟然不如普通的C++實現版。首先，表明這個原因與halide本身的設計無關，但是，與halide優化和神經網絡算子的兼容性有關，如果想要利用halide真正的實現加速，還是需要等待一段時間了。

后記
本文只是簡單介紹了Halide的基本知識，對于想要深入理解Halide的童鞋可以看官方的教程或者閱讀源碼，不論是設計算法的算法工程師亦或是在相關硬件平臺上實現移植功能的底層工程師，Halide的思想都是值得去借鑒和回味的。
另外提一下，Halide的運行有兩種方式，一種是JIT的模式，另一種是AOT的模式。JIT模式使用起來比較方便，可以直接將算法和Halide的代碼生成generator封裝成一個類，在程序的其他部分調用這個類即可。在嵌入式環境和交叉編譯環境下一般使用AOT模式，此時需要調用compiler函數，將算法代碼和Halide的代碼生成generator編譯位目標機器的代碼，生成一個.o目標文件和.h頭文件。然后在獨立的目標機器的應用的工程的源代碼中，通過頭文件調用算法實現的計算函數，并在build的時候鏈接上.o文件，這樣就得到一個可以在目標機器上運行的用Halide實現算法的程序了。一般DSP上都是這種方式來做的。
Halide的利用范圍很廣，之所以想要深入了解Halide是因為使用了TVM庫，TVM借助了Halide的思想，去實現神經網絡算子的優化，并且取得了不錯的效果。

總結

以上是生活随笔為你收集整理的Halide视觉神经网络优化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。