schedule与计算逻辑分离是自动代码生成技术的核心概念，由MIT CASIL组的Jonathan Ragan-Kelley在2012年发表在SIGGRAPH上的文章率先提出，然后在2013年发表在PLDI上的文章给出了schedule的精确定义：
- 1.When and where should be the value at each coordinate in each function be computed?
- 2.Where should they be stored?
- 3.How long are values cached and communicated across multiple consumers, and when are they independently recomputed by each?
第一条是描述了数据计算顺序对性能的影响，第二条是数据的存储位置对性能影响，最后一条是多线程处理过程中，不同线程数据应该如何进行交互。
事实上，schedule就是一系列优化选择的集合。这些选择不会影响计算的结果，但是由于其包含着对architecture的理解，因此对性能是至关重要的。往往一个选择或者多个选择的组合，都会被称为schedule。
常用的Schedule有：
存储层次的相关Schedule
- 1 cache_read(tensor, scope, readers)
将数据存储到片上缓存，减少访问数据时间。
cache_read将tensor读入指定存储层次scope的cache，这个设计的意义在于显式利用现有计算设备的on-chip memory hierarchy。这个例子中（
AA = s.cache_read(A, "shared", [B])），会先将A的数据load到shared memory中，然后计算B。在这里，我们需要引入一个stage的概念，一个op对应一个stage，也就是通过cache_read会新增一个stage。
- 2 cache_write(tensor, scope)
将结果写入片上缓存，然后再写入片外缓存。当然这里的片上和片外并不是绝对的概念，也可以理解为不同层次的存储结构。
cache_write和cache_read对应，是先在shared memory中存放计算结果，最后将结果写回到global memory。当然在真实的场景中，我们往往是会将结果先放着register中，最后写回。
- 3 set_scope
为数据指定存储位置，相比于cache_read和cache_write提供了更灵活的指定数据存储方式。本质上是相同的。
set_scope指定stage计算结果所在的存储层次，为tensor选择最优的存储位置，适用于设置线程间的共享内存。事实上，set_scope是cache_read的子操作。
- 4 storage_align
在我看的文章中，storage_align是针对GPU shared memory的一个优化，目的是为了减少同一个bank的访问冲突。在GPU中shared memory被分割成多个bank，这些bank可以被独立线程同时访问。Storage_align就是为了将数据和bank大小匹配，减少bank conflict的发生。AI芯片中也有类似的问题，只有尽量减少bank冲突的发生，才能最大化并行计算。
storage_align把stage对应的存储空间以factor为单位、以offset为偏置重新对齐，以避免GPU共享访问时的bank conflict，关于bank conflict可以参考2。
- 5 compute_at
不懂CUDA，所以对文章中的代码不是很理解，但是从其解释看，对于多次循环的计算（或者多维计算），可以通过并行计算来降维。
compute_at将当前的stage附着到目标stage的指定iter方向上，同时与目标stage采用相同的并行方式，在其内部完成当前stage的计算。往往compute_at会与cache_read和cache_write一起使用。
- 6 compute_inline
将独立操作转化为内联函数，有点类似FPGA上的流水线计算。转化成内联函数从上层层面减少了stage。在FPGA中也有类似问题，可以将具有相同迭代的多条指令放在一起执行。
compute_inline把独立的计算操作转化成内联函数形式，在使用到原计算结果时再调用内联函数完成运算，通过compute_inline来减少一个stage。
- 7 compute_root
Compute_at的反操作。
compute_root是compute_at的反操作。因为不做任何schedule的话，每一个stage默认就是compute_root的，这个schedule相当于注释了对之前对一个stage的compute操作。
常见循环优化
- 8 fuse
将多个循环iter融合为一个iter。
fuse用于融合两个iter，将两层循环合并到一层，其返回值为iter类型，可以多次合并。
- 9 split
Fuse的反操作，将一次循环迭代拆分为多次。
split是fuse的反操作，把iter以factor为间隔分离成outer与inner两层迭代，增加循环层数，用于将循环操作分割为更小的子任务。事实上，以CUDA为例，gridDim和blockDim都可以最多是三维，所以通过split可以产生新的维度用于绑定到grid和block上3。
- 10 reorder
调整循环计算迭代顺序。
reorder用于重置循环iter的内外顺序，根据局部性原理，最大化利用cache中的现有数据，减少反复载入载出的情况。注意，这里到底怎样的顺序是最优化的是一个很有趣的问题。以矩阵乘法为例，M, N, K三维，往往是将K放在最外层可以最大程度利用局部性。
- 11 tile
Tile也是将循环迭代进行拆分，拆分多次计算。是split+reorder。
tile将stage的两个维度按照各自的factor拆分，并以固定顺序依次返回两个outer和两个inner的iter，从而增加循环层数，形成更小的计算任务。事实上，tile是可以由split和reorder来实现的，tile是矩阵乘法和卷积计算的重要schedule。
- 12 unroll
将循环展开，增加并发执行。
unroll是一种常见的循环优化方法，减分支预测失败减少，如果循环体内语句没有数据相关，增加了并发执行的机会，也有利于指令流水线的调度4。
多线程并行优化
- 13 vectorize
将循环迭代替换成ramp，可以通过SIMD指令实现数据批量计算，也就是单指令多数据计算。这在AI加速中会很常用，每条指令都是多数据计算的。
vectorize把iter方向上的循环迭代替换成ramp，从而通过SIMD指令实现数据的批量计算，并且只有在数据size为常数、且分割的iter为2的幂（即满足SIMD的计算数量）时才会发生替换，否则vectorize没有效果，是SIMD计算设备的常用schedule。
- 14 bind
CUDA中使用的优化方法，将iter绑定到不同线程，实现并发计算。
bind将iter绑定到block或thread的index上，从而把循环的任务分配到线程，实现并行化计算，这是针对CUDA后端最核心的部分。
- 15 parallel
实现多设备并行.
parallel将指定iter的for循环替换为parallel操作，从而在GPU以外的CPU等设备上实现并行。
其他schedule
- 16 pragma
可以在代码中人为添加编译注释，人为干预编译优化。HLS中就是通过这样的方式来实现c的硬件编程的。
pragma用于添加编译注释，使编译器遵循pragma的要求，实现unroll, vectorize等调度功能。事实上一个新的优化规则，都可以看做是一种gragma，也被称作directive5。
- 17 prefetch
将数据计算和load后者store数据重叠起来，在FPGA中是很常见优化方法。
prefetch利用数据的空间局部性，用于使得前一个iter的计算与后一个iter的访存overlap起来，以提高访存和计算的并行度，减少耗时。本质上是软件流水线的概念，不是硬件prefetch。
- 18 tensorize
将tensor作为一个整体匹配硬件的计算核心，比如一个卷积运算就可以实现在FPGA上的一个匹配。
tensorize将计算作为整体，编译为一个tensor_intrin函数中。这是因为很多计算属于常用计算，针对这些计算已经有了很好的built-in的schedule，通过tensorize可以直接调用这些内置的intrinsic，其实这也就是intrinsic在计算机科学中的本意6。
- 19 rfactor(tensor, axis, factor_axis=0)
rfactor对原tensor在axis方向以factor_axis为间隔做reduction操作。
- 20 set_store_predicate
set_store_predicate设置了store的条件，适用于在多线程调度中预防写操作之间的冲突。
- 21 create_group(outputs, inputs, include_inputs=False)
create_group对从inputs到outputs的所有stage创建group，group本质上是一个虚拟stage，可以通过操作这个虚拟stage来一起操作这个group里的所有stage。本例中，通过compute_at使这个group中的D和E，一起附着到指定操作中。
相关示例代码参考https://github.com/StrongSpoon/tvm.schedule
参考：
tvm schedule详细举例