深度学习编译器（halide）是怎么优化的？

最近关注了深度学习编译器领域，梳理了一些知识

其中 halide （论文是2013年）算是比较早的编译器，tvm 的设计灵感也是参考了 halide 的

halide 是怎么优化的？

主要有三个点： 并发(parallelism) 、 重复工作 ( Redundant work ) 、 局部性 ( Locality )

并发（parallelism）：

可以拆分成多个向量，并行计算

重复工作（Redundant work）

* Loading a value from memory somtimes slower than re-computing it .

‍

如上图： 每次计算的窗长为4，到最后剩下 2 个「正方形」， 方法1 是使用单个向量指令计算，最后会有2个「正方形」重复计算； 方法2 是将剩下2个「正方形」切换到不同的代码路径执行，需要重新 Loading value， 一般方法2会比较慢

局部性（Locality）

* If you just wrote a value to memory, you should try to use it quickly, while it's still in cache .

CPU 缓存是有限的，也是相对比较小的。如果某个值在 CPU 缓存，尽量将这个值有关的计算都计算好，提高 CPU 缓存的命中率

如上图，虽然step2 依赖于 step1 的值（通过3黄色的得到1个棕色的），但是不用等到 step1 都计算完之后，再计算 step2；类似上图，可以在 step1 计算一部分之后，再计算 step2，再回到 step1 这样交替计算，可以提高内存的命中率

编译器优化的例子

循环重排(loop recorder)

alloc arr[256][1024]for each y in 0..1024:  for each i in 0..256:    do(arr[i][y]) 

编译器会调整顺序, 因为按照「行」读取，内存地址是连续的，可以提高 CPU 缓存的命中率:

alloc arr[1024][1024]// 上下循环交换for each i in 0..256:  for each y in 0..1024:    do(arr[i][y]) 

向量化（vectorize）和 平铺（tiling）