Halide代码优化思想简述

1.Halide介绍

Halide是一种编程语言，主要在图片处理和矩阵计算时具有方便快捷高性能的特点。它不是一种独立语言，而是基于C++的DSL(Domain Specified Language)，主要应用在算法的底层加速，并且此优化与算法本身设计无关。Halide思想在传统的图像处理(OpenvCV)和深度学习(TVM)优化加速方面具有较强的借鉴意义。支持的目标如下：

• CPU 架构: X86, ARM, MIPS, Hexagon, PowerPC, RISC-V

• OS: Linux, Windows, macOS, Android, iOS, Qualcomm QuRT

• GPU APIs: CUDA, OpenCL, OpenGL Compute Shaders, Apple Metal, Microsoft Direct X 12

作为一种嵌入在C++上的语言，用户可以使用C++API创建Halide的内存中间表示，共两种编译方式JIT(just-in-time)和AOT(ahead-of-time)，JIT方式在代码运行阶段被映射为Halide内存对象，AOT方式可以生成编译文件，在使用时进行链接，主要应用于嵌入式和交叉编译环境。

下面代码是使用Halide定义的3*3的图片过滤函数示例：

Func blur_3x3(Func input) {Func blur_x, blur_y;Var x, y, xi, yi;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;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;
}

２．高性能代码的特征

高性能代码需要开发者在并行、局部性、额外开销(如下图)三个方面进行平衡。通过多核并行或SIMD同时对多路数据计算可以缩短计算时间，但是此过程中会存在多进程或线程开销。为了获取程序内存的局部性，可能需要对内存进行合并、划分、拷贝等操作，从而产生额外工作。因此获取高性能代码的过程需要对并行、局部性、额外开销三个方面进行平衡。　

2.1 并行性(parallelizing)

实现并行的方式主要为mutlticore和SIMD,其中multicore的方式比较容易理解，使用多个物理核进行计算，这样就可以比单核计算的速度快。SIMD即Single Instruction Multiple Data，一条指令操作多个数据。是CPU基本指令集的扩展，主要用于小碎数据的并行操作。在图像处理过程中，一个像素点的一个分量总是用小于等于８bit的数据表示的。如果使用传统的处理器做计算，虽然处理器的寄存器是32位或是64位的，处理这些数据却只能用于他们的低８位，如果把64位寄存器拆成８个８位寄存器就能同时完成８个操作，计算效率提升了８倍。

2.2 局部性(loclaity)

在CPU访问存储设备时，无论是存取数据抑或存取指令，都趋于聚集在一片连续的区域中，这就被称为局部性原理。时间局部性（Temporal Locality）,如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。比如循环、递归、方法的反复调用等。空间局部性（Spatial Locality）,如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。比如顺序执行的代码、连续创建的两个对象、数组等。下面是Halide中的经典模糊化(blurred)图像的例子,首先在x轴上对每个像素点以及周围的两个点进行求和平均，然后再到y轴上进行同样的操作，这样相当于一个3×3平均卷积核对整个图像进行操作。

void box_filter_3x3(const Mat ∈, 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(y, x) = static_cast((in.at(y, x-1) + in.at(y, x) + in.at(y, x+1)) / 3);for(int x = 0; x < in.cols; x ++)for(int y = 1 ; y < in.rows-1; y ++)blury.at(y, x) = static_cast((blurx.at(y-1, x) + blurx.at(y, x) + blurx.at(y+1, x)) / 3);
}

在循环嵌套中的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(y, x) = static_cast((in.at(y, x-1) + in.at(y, x) + in.at(y, x+1)) / 3);for(int y = 1 ; y < in.rows-1; y ++)for(int x = 0; x < in.cols; x ++)blury.at(y, x) = static_cast((blurx.at(y-1, x) + blurx.at(y, x) + blurx.at(y+1, x)) / 3);}

同样执行100次并记录时间,第一种方法用时4521.72 ms,第二种方法用时3992.35 ms，可以发现第二种方法的模糊操作执行的速度比上面的快一些。由于此程序中图片的存储是行优先存储，沿着行的方向运算时，其相邻元素在缓存中的概率更大，因此在循环体中沿着x轴操作时，可以节省数据加载时间。

2.3 调度(Schedule)

Halide的特点是其图像算法的计算实现（Function和Expression）和在硬件单元上的调度是分离的，其调度以Function为单位。最终将整个图像算法转换为高效率的多层for循环，for循环的分部数据范围划分和数据加载都是由Halide来完成的，而且可以实现数据的加载和算法计算的Overlay，掩盖数据加载导致的延迟。Halide的Schedule可以由程序员来指定一些策略，指定硬件的buffer大小，缓冲线的相关设置，这根据不同的计算硬件特性来实现高效率的计算单元调度，而算法的计算实现却不需修改。同时为了加速用户的开发效率，提供了Auto-Scheduler，在用户给定输入输出时，在Hailde的调度策略空间内进行优化搜索，快速的找到效果最好的调度策略，节省了开发者的调优时间。

3 Halide优化方法

主要使用方法有Reorder(交换)、Split(拆分)、Fuse(融合)、Tile(平铺)、Vector(向量化)、展开(Unrolling)、并行(Parallelizing)，结合这些方法可以实现缓存一致性强、并行度高、额外开销少的图像处理程序。

3.1 交换 Reorder

Halide在对矩阵或图片进行两层循环时默认列号在最外层循环，因此Reorder后行号在最外层循环。

gradient.reorder(y, x);
对应C代码解释为：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);}}

3.2 拆分 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);}}
}

3.3 融合 Fuse

融合的目的是减少循环层数，下述融合操作只是对Halide操作进行一下演示，并没有实际用处，也就是说实际中的计算顺序并没有改变。对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);
}

3.4 平铺 Tile

Tile是Split、Reorder的语法糖，是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);}}}
}

3.5 向量化 vector

向量化即我们使用cpu中的SIMD技术，一次性计算多个数据，充分利用硬件的特点，例如在x86中我们可以利用SSE、AVX等单指令多数据来实现这个功能。

在Halide中，我们首先将x轴的循环嵌套按照，内侧循环因子4的方式，拆分为两个(也就是内侧循环x执行四次，外侧根据总数进行计算，下例是2*4=8)，然后将内侧的x循环转化为向量的形式，内侧x变为向量形式，一个SIMD指令就可以执行完成。

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]);}
}

3.6 循环展开 unrolling

如果在图像中多个像素同时共享有重叠数据，这时候就可以将循环展开，从而使那些可共享使用的数据只计算一次亦或是只加载一次。

在下面将x轴拆分为内侧和外侧，因为每次内侧的数值增长都是从0到1，如果我们将内测循环的x轴展开：

Var x_outer, x_inner;
gradient.split(x, x_outer, x_inner, 2);
gradient.unroll(x_inner);
对应的Ｃ代码解释为：
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);}}
}

3.7 整合

使用多种操作对大小为350 x 250的图像进行最优化操作。首先我们将其按照64 x 64的因子进行平铺，其次融合y轴和x轴外侧的循环操作数，最后对其进行并行操作。

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);

3.8 自动搜索Auto-Scheduler

前面都是手工编写了Halide调度策略，通过自动搜索策略针对不同硬件及其配置产生不同的优化代码，从而使用户节省大量的优化时间。原始算法描述：

 void generate() {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);...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(){input.set_estimates({{0, 1024}, {0, 1024}, {0, 3}});factor.set_estimate(2.0f);output1.set_estimates({{0, 1024}, {0, 1024}});output2.set_estimates({{0, 1024}, {0, 1024}});const int kParallelism = 32;const int kLastLevelCacheSize = 16 * 1024 * 1024;const int kBalance = 40;MachineParams machine_params(kParallelism, kLastLevelCacheSize, kBalance);
}

自动搜索产生的代码：

            Var x_i("x_i");Var x_i_vi("x_i_vi");Var x_i_vo("x_i_vo");...          {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);}

４．效果

从下图可以看出同样的一个算法处理(局部拉普拉斯变换)，使用直接的C++语言写出来算法速度很慢，Adobe公司使用3个月对这个算法进行了优化(手工优化)使这个算法的速度快了10倍，但是如果使用Halide，只需要几行代码，并且比普通直接的算法快上20倍，因此Halide在图像处理方面的代码优化的效果及效率是显然可见的。因此Halide的代码优化思路对于研究深度学习推理加速优化领域是值得借鉴的。

Halide既然作为与算法无关的底层优化器，也应该可以在深度学习领域进行应用。OpenCV库就使用了Halide去优化底层的神经网络操作，在benchmark中如下图可以看出基于Halide的神经网络运行速度竟然不如普通的C++实现。其实这个原因与Halide本身的设计无关，但是与Halide优化和神经网络操作的兼容性有关，如果想要利用Halide进行深度学习算法的加速优化，则需要对Halide与神经网络算子的兼容性进行研究开发。

5. 参考

• https://oldpan.me/archives/learn-a-little-halide

• https://halide-lang.org/

• https://www.codercto.com/a/67796.html

• https://www.zhihu.com/question/294625837/answer/496218375

• https://github.com/opencv/opencv/wiki/DNN-Efficiency

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！