1 缩写 & 引用

2 abstract & introduction & prior work

先举了一个3x3卷积的例子，一个是未优化C语言版本，一个用x86向量化指令优化过的，一个是Halide语言的，说明现行情况下想要优化算法的执行速度，会导致算法很难理解，那么不如把算法和调度分开写，这样更易懂
其中调度包括这几项：

函数内部的并行、SIMD
一个函数域内的点相对于另一个函数域内的点求值的顺序
存储方式
是否重新计算

本篇论文的贡献：

一个编程语言Halide
Halide编译器，可以将算法优化成x86、ARM、CUDA的机器指令
提供了Halide的操作函数

以前的相关的工作有：

data-paralle language
programmer-controlled scheduling
image processing languages

3 算法和调度的表示

Halide语言比较简单，还提供了一些reduction function

3.1 the schedule

调度包括：

inline：比如说数组A用到了数组B，那么需要用B[0]就现算B[0]，而不是把B[0]的值提前存好，这样可以省存储空间
root：提前算好所有的需要的区域：比如就是提前把数组B的值全算好，这样不用重复计算，但是耗费存储空间和带宽
chunk：一部分提前算好
reuse：比如说root，如果数组A和数组C都用到了数组B，那么提前算好数组B的值就可以服用到两个地方

在函数作用域的内部，需要明确计算是串行的、并行的、向量化的、还是如何展开

调度没有指定每个维度的边界。在编译期间，将推断每个阶段所需的域范围。
最终，这些表达式的大小取决于请求的输出图像的大小。将边界规范留给编译器将使算法和调度更简单、更灵活。
显式边界只在编译器无法分析的索引表达式时才需要。在这些情况下，我们需要算法显式地固定有问题的索引。

分裂维度将其边界扩展为内部维度范围的倍数。向量化或展开维度类似地将其范围舍入为所使用的因子的最接近倍数。
这样的边界扩展总是合法的，因为我们把图像表示为无限域上的函数。

这些选择相当于指定一个完整的循环嵌套，它将遍历输出域的所需区域。
平铺访问模式在最大化局部性和缓存效率方面非常重要，并且是我们计划的一个关键影响。但是，每个区域的存储布局不受计划的控制。
令人惊讶的是，在我们尝试过的所有架构和应用程序中，平铺存储布局的重要性都很低，因此我们不包括它们。
cache line通常比tile宽度小，因此主存中的tile布局对cache行为的影响通常有限。

调度reduction：
reduction的调度必须指定一对嵌套循环:一个用于初始值(在输出域上)，一个用于reduction步骤(在reduction域上)。在后一种情况下，边界由reduction的定义给出，不需要在以后进行推断。由于reduction的含义部分依赖于顺序，因此不能更改维度顺序，这可能会改变他的含义。
但是，虽然我们在语义上定义reduction以遵循reduction域中严格的字典遍历顺序，但许多常见的reduction(如求和、直方图)是关联的，可以并行执行。像cdf这样的扫描很难并行化。我们还没有解决这个问题。

3.2 the fully specified program

这是一个通用的命令式程序表示，但是我们不需要以这种形式分析或转换程序。
最具挑战性的优化已经从内在算法降低到命令式程序。
因为编译器生成所有命令式分配和执行结构，所以它对它们的语义和约束有深入的了解，这对于从任意命令式输入中推断非常具有挑战性。我们降低的命令程序可能仍然包含需要解决的符号界限。
最后的边界推断传递根据程序中不同循环变量的边界之间的依赖关系来推断具体的边界

4 编译器实现

用LLVM compiler infrastructure进行传统标量优化、寄存器分配、机器代码生成
文献阅读（23）

lowering：既然算法和调度是分开写的，那么就先要把他们转换成一体，编译器从后往前依次看函数执行顺序
bound inference：明确作用域的边界
CPU代码生成：用LLVM
CUDA代码生成：

文献阅读（23）

文章目录