1 缩写 & 引用

2 abstract & introduction

stencil代码是一类迭代内核，它们根据stencil的固定模式更新数组元素。常见于计算机模拟代码中，如流体动力学、求解偏微分方程、雅可比内核、高斯-塞德尔方法、图像处理和元胞自动机。
本篇论文主要贡献

面向stencil pipeline的系统模型：locality、parallelism、redundant recomputation之间的tradeoff
scheduling representation
一个编译器，可以把Halide的算法和调度描述结合起来
对于数据并行流水线的loop synthesizer
code generator：产生高质量向量代码
autotuner：通过启发式搜索实现优化

3 Halide DSL & scheduling image processing pipelines

别的语言里是可变数组，在这里是从整数坐标到值的映射函数
调度需要解决的问题：

每个函数中每个坐标的值什么时候在哪里算出来
这些值要存在哪里
这些值要cache多久，不同的消费者之间如何通信

3.1 motivation: scheduling a two-stage pipeline

这里举了一个3x3卷积的例子，3x3卷积会被拆成3x1卷积和1x3卷积
第一个方法叫breath-first，先用3x1卷积算一遍，再用1x3卷积算一遍，缺点是中间数据要存储的多，locaity很少；这种方法被称为breadth-first
第二个方法叫total fusion，不要存中间数据，直接算最终的结果，需要行卷积的结果就现算，这可以充分的并行，locality也很好，问题是有冗余计算
第三个方法叫sliding window，每次行卷积算三行存起来，有点像line buffer，然后算列卷积，这个没有荣誉的计算，数据局部性也挺好，缺点是不能充分的并行
第四个方法叫overlap tiling，通过tiling将整个图像切成块，块与块之间可以并行，块以内可以利用局部性citaei
文献阅读（32）
第五个方法最快，叫siding windows within tiles，结合了第三个和第四个方法，并行度比第三个快，就是把好几行分成一条，每一条有8行，每一条内部按第三个方法计算

3.2 model for the scheduling choice space

**Domain Order：**包括tiling、向量化、unrolling、展开成内外两套循环
分割递归地打开了更多的选择，并在与其他转换结合时支持许多常见的模式，如tiling。矢量化和展开的建模方法是先用矢量宽度或展开因子分割一个维度，然后将新的内部维度安排为矢量化或展开。
由于Halide的函数模型是通过构造实现的数据并行，所以维度可以以任何顺序交错，并且任何维度都可以被安排为串行、并行或向量化。
对于reduction 函数，只有在reduction更新是关联的情况下，才可以重新排序或并行化reduction域的维。与纯函数一样，自由可变维可以按任何顺序调度。

这里的模型首先需要明确边界，所以边界分析很重要，剩下的会把他看作axis-aligned bounding region，这比多面体模型要简单一点

call schedule
domain order定义的循环转换与call schedule选择的阶段间交错粒度交互，因为call schedule是通过指定存储或计算的循环级别来定义的。
a 可以存储或计算在任何循环中，从直接调用函数的最内层维度，到其自身计划计算的周围维度，等等。
分割维度允许在比调用函数的内在维度上更细粒度地指定call schedule，例如，扫描线块interleaving而不是单个扫描线，或者像素块而不是单个像素。
由于计算的每个值都需要一个可以存储其结果的逻辑位置，因此存储粒度必须等于或大于计算粒度。

4 compiling scheduled pipeline

编译器这部分就不做启发式的决策，比如说如何循环转换，这部分交给schedule来做
文献阅读（32）

4.1 lowering and loop synthesis

从后往前找循环、最后把所有的函数都变成一系列的循环，只不过循环上下标是用变量表示的

lowering从pipeline递归的进行，从caller到callee(这里是从out到blurx)。
callee(除了inline调度)被调度为在某个caller函数的某个维度的粒度上计算。这与目前生成的代码中的现有循环相对应。
这个site和对callee进行评估的代码被注入到循环体的开始。这个代码采用循环嵌套的形式，使用callee的domain order构造。callee的allocation类似地注入到调度指定的某个containing循环级别。
在图5中，中间的blurx是在tile(out.x)级别上分配的，而它是根据tile内每个scanline的需要计算的

4.2 bounds inference

也是从output往前找，确定循环的上下界，是用interval analysis的方法
interval analysis是多面体模型分析的简化版本，针对直线的、笔直的情况

4.3 sliding window optimization and storage folding

这是类似line buffer
在边界推断之后，编译器遍历循环巢，寻找滑动窗口优化的机会。
如果一个函数的实现被存储在比它的计算更高的循环级别上，并且中间有一个串行循环，那么该循环的迭代可以重用前一个迭代生成的值。使用与边界推断相同的区间分析机制，我们通过排除前面所有迭代计算的区域来缩小每次迭代计算的区间。
正是这个转换使我们能够在并行性(因为中间的循环必须是串行的)和重用(因为我们避免了重新计算先前迭代已经计算的值)之间进行权衡。

4.4 flattening

这个跟其他语言一样，就是把多维数组转化一维数组，得到数组的存储地址，这里总是标准的正常的存储方式

4.5 vectorization and unrolling

4.6 back-end code generation

LLVM可以进行constant-folding、dead-code消除，LLVM主要有两个问题：

是关于loop的代码，这里把循环的迭代当作一个线程，放到线程池里
LLVM不太容易产生向量化指令，这里要用peephole优化

文献阅读（32）

文章目录