文章目录

1 缩写 & 引用2 abstract & introduction & prior work3 representing and scheduling program3.1 scheduling for Producer-Consumer Locality3.2 scheduling for input reuse3.3 function bounds analysis 4 算法4.1 函数预处理4.2 函数分组和tiling4.2.1 tiling for input data reuse4.2.2 generating tile size 4.3 函数inlining4.4 最终调度的产生 1 缩写 & 引用2 abstract & introduction2 相关工作3 确定hadlide调度空间3.1 参数化的调度空间3.2 定向搜索算法 4 预测运行时间4.1 调度的特征

题目：Automatically Scheduling Halide Image Processing Pipelines时间：2016会议：SIGGRAPH研究机构：MIT

1 缩写 & 引用

2 abstract & introduction & prior work

本篇在之前Halide基础上，是说编程者要写高性能程序，需要费尽心思的写优化的schedule，这里提出了一个算法，扩展之前的边界分析，自动化产生优化的调度策略，就不需要人为写了 之前的研究方向有：

自动化的tuning：很多是暴力搜索，需要实际跑到硬件上来测时间，费时间限制搜索空间：比如Darkroom，限制一些条件，变成整数线性规划问题多面体模型

3 representing and scheduling program

一个Halide程序可以表示为无环有向图，边表示数据依赖，但即使有数据依赖，也没有规定前后计算的流程

3.1 scheduling for Producer-Consumer Locality

类似上一篇论文，这里还是举了3x3卷积的例子，给出了三种调度方式。第一种需要分配比较大的空间来存放中间结果，数据局部性最差；第二种压根不存放中间结果，这就会有冗余计算，虽然数据局部性最好；第三种用overlapped tiling的方式

3.2 scheduling for input reuse

这个FPGA的数据复用还不一样，是面向CPU的，为了让数据还保留在cache里，这样重新读这个数据的时候就快得多； 对于一个矩阵乘法，如果这个矩阵很大的话，可能就不能都放到cache里，这就需要tiling了

3.3 function bounds analysis

编译器动过interval analysis来确定循环的边界，确定中间数组的大小；这个边界在后面的自动调度算法中也需要 它从output函数开始，根据函数依赖链，在无环有向图中一步一步确定 如果这个边界不好自动判断，那就需要编程者显式声明

4 算法

这节主要讲自动化产生Halide调度的算法，原理是把整个程序分成几组，每一组内部可以独立的利用数据局部性原理进行优化，比如说tiling 要求是算法必须已知各个循环的边界，不能自己判断的话就要显式声明

4.1 函数预处理

估计计算量计算出确切的边界计算不同方向上数据的复用 比如说如果输入每次都是一列一列的话，没法很好的利用数据局部性，因为存储是row-major的；如果调换循环顺序，一行一行的输入的话，能更好的利用数据局部性，可以做到数据的复用

4.2 函数分组和tiling

算法采用聚类的思想，一开始每个函数的分散的

枚举所有可能的merging的可能性对于每一个merging，估计性能的提升然后选择性能提升最大的merging如果性能不在提升的话，终止merging

4.2.1 tiling for input data reuse

其实还是立足于cache，有一个明确的cache的大小，寻找合适的tile大小，保证cache miss次数是最小的

4.2.2 generating tile size

主要就是明确tile的尺寸，对于n维的循环，可以看作一个n维的多面体，在数据可以复用的方向上拉长。 这需要编译器明确分配临时缓冲区的大小 若果中间临时存储大小超过了cache大小，或者tile太大并行度太小，这些都会被舍弃掉

4.3 函数inlining

inline有好处也有坏处，会导致冗余计算，所以要评估出这部分的代价。consumer可能不止一个，所有冗余计算可能不止一处，所有的consumer的代价都要加上

4.4 最终调度的产生

刚刚讲了确定tiling大小和inline，还要做的优化是

reorder输出函数的循环，看如何实现最大的input locality尝试unroll和向量化最里面的循环 之后就可以让编译器产生机器代码了

---

题目：Learning to Optimize Halide with Tree Search and Random Programs时间：2019期刊：ACM Transaction Graph研究机构：ANDREW ADAMS(Facebook)代码： https://autoscheduler2019.halide.io

1 缩写 & 引用

ILP: integer linear program整数线性规划 Loop Transformations Leveraging Hardware Prefetching (2018 International Symposium on Code Generation and Optimization) Schedule Synthesis for Halide Pipelines Through Reuse Analysis (2019 ACM Trans. Archit. Code Optim) Learning to Optimize Tensor Programs（2018 陈天奇 CoRR）

2 abstract & introduction

过去自动化优化代码的局限性有：

只考虑了搜索空间的子集：只是用了一些特定的调度模板或者习语用了特别的搜索算法，有局限性手工设计的cost model不足够准确

本篇论文提出的方法，是自动优化halide程序的算法，第一个大幅超过人工手写代码的性能，主要贡献有：

参数化的搜索空间通用的搜索算法：利用率回溯法和粗粒度改进利用了符号分析和机器学习的cost model一个鲁棒的可以训练cost model的方法：通过大量的随机程序来训练，更通用利用采样和benchmarking（autotuning）来提高性能可以平衡编译时间和程序性能：程序编译时间可任意设置，从最快的贪婪算法到最优算法之间可以插值

2 相关工作

2013年最早的autotuner：遗传搜索，启发式调度模板，利用实际运行时间来measure，耗时久2014年有一个简化的版本，只能做最简单的流水线2016年MIT的autoscheduler，贪婪算法，简单调度模板，简单的cost model，没有benchmark，可以tiling，fusion，固定的启发式选择如并行化，向量化和展开2018年的，回溯，更复杂的cost model2019年的，回溯，相似的cost model，fusion策略polyhedral compilers：整数线性规划TVM：通用的搜索with learning and benchmarking，但是搜索空间要程序呀u按指定

3 确定hadlide调度空间

halide程序分成算法和调度两部分，算法又称pipeline，可以用有向无环图表示；调度则表示成一个确定的loop nest。loop nest主要由两部分决定：

intra-stage order：包括arbitrary dimension order和n维作用域的tiling，而且任意循环都可以并行或者展开做cross-stage granularity：at what granularity each stage should be computed，比如inline，root，sliding window或者line-buffered

3.1 参数化的调度空间

一个loop nest是由这几个决定的：

a nested set of n维tiling计算和存储的粒度循环的每层tiling是展开、用并行的线程还是SIMD

首先要遍历出所有的可行的调度选择，我们是从最后的结果开始，从后往前加计算的一级，每一级会有计算和存储的粒度，以及tiling的策略

3.2 定向搜索算法

每次保留最好的k个结果，同时又减枝策略，排除掉一些不合适的情况

4 预测运行时间

这里基于halide符号分析工具提取的特征，用一个小型的神经网络来预测runtime

4.1 调度的特征

特征可以分成

算法决定的特征调度决定的特征