PLuTo 编译器和它的调度算法（二）

fwalker

在第一篇文章中，笔者对 PLuTo 编译器的整体架构和核心概念进行了梳理。这一篇文章尝试讲清楚其调度阶段，尤其是它的核心调度算法（下图第一阶段）的思路。



图1 PLuTo 编译器的核心调度阶段

• （一）PLuTo 编译器 通览
  
• （二）PLuTo 编译器的调度算法【本文】
  
• （三）PLuTo 编译器的代码生成
  

The PLuTo scheduling algorithm

我们暂称第一阶段使用的算法为 the PLuTo scheduling algorithm，该工作独立地发表在[CC'08]上，名为 Automatic Transformations for Communication-Minimized Parallelization and Locality Optimization in the Polyhedral Model. 若为了了解该算法本身，建议以读该文章为主、而非PLDI'08那篇PLuTo编译器的文章。
该调度算法要做的事是，为多面体模型在“依赖的约束下”寻找到一个“还不错的新调度”。PLuTo 调度算法的思路是，去找到一个具有 粗粒度并行性 和 局部性 的新调度。
注意到，如第一篇文章所讲，该算法为迭代算法，它自外至内求解整数线性规划问题（ILP），不断计算新的维度。我们核心要关注的是，它怎么求解出“一个维度”，它怎么把“并行性”和“局部性”的考虑建模为ILP。
计算一个维度的变换

我们来看一看在计算某个维度（p维度）时，要做的事。

• 输入：到维度p 仍然没有被满足的依赖
  
• 输出：一个还不错的单维度变换（也就是那一堆c，符号在第一篇文章有给出）
  
• 搜索范围：合法性（legality），不违背依赖
  
  
  • 注意，我们不需要让计算的维度满足“更多的依赖”，只需要它不违背即可！因为还可以有更多的内层循环。
    
  
  
• 优化目标：并行性与局部性
  
  
  • 我们需要给数学对象以物理含义，才能进一步对优化性质建模，在这里我们也就是要对“维度”给出物理含义。在 PLuTo 工作中，它说某一个维度可以对应“时间”与“空间”
    
    
    • 时间：这一维度将按照时间顺序执行，也就是顺序执行，它对应的优化目标就是缓存的局部性
      
    • 空间：这一维度将被安排到不同的执行单元上，也即并行执行，它对应的优化目标是并行直接间的交互同步数量
      
    
    
  
  

具体地，合法性要求求解出的维度，与每一个依赖不呈现“负向”，也即“点积”大于等于零。在下图的场景中，0度到90度的范围均是可以的。



图2 求解出的维度需要满足合法性

具体的，算法要求“任何一对（尚未被满足的）实例间依赖”在该维度上，被依赖实例可以被映射到比依赖实例更早或者相同的迭代上。
For all dependent pair of instance (t, s) of Si, Sj, the following should hold. t/s is instantiated iteration vector.


对该不等式组做一些等价变换后，被线性化，作为ILP的约束。这部分数学细节我们不多讨论，主要涉及Farkas定理等。
现在，我们考虑将优化目标建模加入目标函数。

• 对于并行含义的维度，我们希望优化线程间的通讯容量（communication volume），这意味着并行执行的更少的同步代价。在下图中，对应于减少绿色的箭头。
  
• 对于顺序执行来说，我们希望优化复用距离（reuse distance），这意味着对相同内存地址的使用更集中，减少缓存被evict的概率。在下图中，对应将1/3块放在一起，2/4块放在一起。（后注：这里优化的，主要是时间局部性，空间局部性一般借助分块优化）
  

图3 对优化性质的建模

实际上，所谓的communication volume与reuse distance，都体现在依赖之中。最直观地，RAW（写后读）就是信息的生产与消费，也就是对应通信。RAR/RAW/WAR/WAW 都是对相同地址的访问，也就体现了局部性信息。
在 PLuTo 调度算法中，它尝试直接地优化求解的维度中依赖距离的界，下述公式意味着依赖距离：


算法定义了一个关于程序变量向量 \vec{n} 的仿射函数 v(\vec{n})=u\cdot\vec{n}+w ，作为依赖距离的界，u/w均未知，算法会求解出。注意，程序变量的具体的值意味着“计算的规模”。
同时，算法为ILP问题，增加 每一对实例间依赖的界的约束（也会被线性化，忽略），


求解目标为具有最小字典序的下述向量。注意到，u/w被放在最前面，c对应于具体的变换。前者是重要的，我们尤其关注u/w都为零的情景，因为这意味着不同次迭代间完全没有依赖。c随便怎么排布都可以。


这个目标函数其实在尝试求解一个满足 让更少约束被满足 的单维度变换。鉴于我们自外至内的迭代求解过程，外层循环更容易达成这一点，这意味着算法尝试让外层循环是可并行的。那么，依赖的满足便被推到内层循环。这和我们的目标，“粗粒度的并行性”与“局部性”对应。
下图为 PLuTo 调度算法的伪代码，读者可以发现，第一篇文章和本文已覆盖了它的思路。我们已经对这个算法有了较深入的理解。
回顾地说，PLuTo调度算法：

• 迭代地求解
  
• 每一次迭代求解一个ILP问题，计算一个维度
  
  
  • 每一次迭代具有相同的目标函数
    
    
    • 目标函数尝试最小化“依赖距离的界”
      
    
    
  • 迭代间具有变动的约束
    
    
    • 每次迭代结束会增加正交的约束
      
    • 并减去已满足的依赖的约束
      
    • 具体的约束为本文介绍的合法性约束和依赖距离的界约束
      
    
    
  
  
• 直到不再需要新的维度为止
  

第13行-15行的操作是一个额外拓展，我们暂时忽略掉它。它后续的影像也不大。这一步主要对fusion进行支持。



图4 PLuTo 调度算法的伪代码

但注意到图4的第12行也进行了掩盖，这处却至关重要，前面我们没有提及。这一步使能了后续的“分块”。
PLuTo 核心算法对“可交换 维度”的支持

掩盖的词汇实际是“iteratively”，也即，算法的每一次迭代，并非只求解一个维度，它在“相同的约束下”尝试求解连续多个维度。注意，原本每求一个维度，会减弱依赖约束，把因为这个新维度满足了的依赖约束去掉，现在我们不这样做（但仍然增加正交约束）。假设这一次迭代开始对应的维度是p，那么每一次迭代会尝试求解连续若干个维度（加入是m），这些维度不违背所有直到p还未满足的依赖，这意味着这些维度每一个都可以做“第p维”。值得注意的是，依赖约束一定会从外到内越来越弱。这进一步意味着，这m个维度可以随意交换，因为它们都满足这m个维度更严格的依赖约束：第p维需要满足的约束。



图5 PLuTo 算法为了支持permutable band所作改动

这么设计的原因是，PLuTo 最开始就考虑做分块（tiling），因为是提升局部性非常重要的变换。
形式化上，原本的 单维度的合法性 自然升级成 连续多个维度的可交换 性质。


连续可交换维度的一个重要的性质是，它们与 p维未满足依赖 都没有“负”相关，是“正向”。这一点对后续的分块（以及块级别并行）的第二阶段调度的理解很有帮助。
好了，现在我们清楚了 PLuTo 调度算法做了什么。

• 它为每个语句求解出了一个矩阵，表示语句的调度函数
  
  
  • 调度算法尝试对不断求解“连续可重排的多个维度”
    
  • 调度算法了解每一个维度的依赖距离的界（u/w），暂时我们只关注u/w=0，这意味着并行性
    
  
  

permutable band 信息和 并行性信息，也会被传入后续阶段。其中前者，使能了后续的分块。
PLuTo 算法进行分块与进一步并行化

我们先看看分块做了什么。从多面体的角度看，它增加了调度的维度，但是维度的“方向”是和某个维度相同的，只是遍历的粒度更大。


分块不是一个循环的事，它必然涉及多重循环，而且是连续的。
for i in 1, M
  for j in 1, N
与
for i in 1, M
  for j in 1, T, N
    for jj in j, j+T
没有改变对实例迭代的顺序。【1维的 strip mining】
分块可以看作：strip mining + interchange现在我们说：Permutable band 是可以进行分块的，即permutable便是tileable。
直观地说：permutable band 对于所有依赖都在相同方向（都是正的分量）。那么我们沿着这些维度画矩形块（在旧的调度看是平行四边形），不可能在块间引入环，因为这意味着有某个依赖“没有沿着正向”，也即“不是向右上的”，这意味着这个依赖和某个维度具有负的分量。
所以，对于permutable band分块是免费的。

注：这里笔者所说的“免费”意指permutable是分块变换正确的充分条件；但分块是否一定带来性能提升是不一定的，可参见评论中赵老师的补充。

图6 分块前迭代顺序



图7 分块后迭代顺序

至于分块的大小（每个维度分块的长度），在PLuTo算法中是作为输入的。算法并没有自动地计算更优的分块大小。当然，这个算法还是在多面体模型上做的分块操作，增加的“supernodes”对应粗粒度的迭代维度，增加的constraints用于连系粗粒度维度和旧的细粒度维度的关系。在多面体模型上做分块，和在AST上做思路是类似的，从后者入手更容易理解，我们不再深入。



图8 PLuTo 的分块算法

有趣的事，permutable band不止意味着“可分块”，它还免费地暴露了并行性。回忆我们说，所有依赖在每个维度的正向，那这意味着，若“非正向”，便没有依赖。这意味着我们在分块之后，还可以做一次挖掘并行性的调度。如下图，依赖是朝着右上的，那么这意味着相对位置是左上和右下的块之间不具有依赖，于是可以并行。

注：这里的并行，也前述分块一样，也并不一定带来性能的优化，详见赵老师在评论中的补充。笔者称“免费”指这个变换是直接就正确的，不需要额外的性质。

图9 对块再做并行化调度

具体地，PLuTo 编译器在“块”的粒度做变换（注意到，分块前的permutable band对应的块级的维度也是permutable的，因为方向是一致的）。该算法让最外层的循环，负责满足接下来m个维度需要满足的所有依赖，那么接下来m个维度都不再需要满足依赖了、它们都变成可并行的了。



图10 PLuTo 中对分块调度再做并行化的算法

到这里，我们就讲述了PLuTo编译器的调度阶段。包括它的核心调度算法、和ILP相关的部分，以及进一步的分块、并行化。
总结：PLuTo编译器的调度阶段

PLuTo编译器的调度阶段结束，我们得到了一个调度，相对于原有的循环，它的外层循环更可能具有并行性、内层循环具有局部性（满足依赖），同时它进行了分块。额外地，我们直到这个调度的一些维度是可并行的，这信息的来源一部分是u/w的求解，一部分是对分块代码并行化自然得到的。
第三篇文章，我们看看PLuTo算法如何做代码生成。那部分就简单多啦。
<hr/>

也请大家关注赵老师在评论里的补充，因为个人阅读范围有限，会在后续学习过程逐渐对文章疏漏进行调整

RedZero9

1、通讯交互：我觉得这个地方应该是指代需要通信的数据量的大小；
2、reuse distance：这个地方解释应该是正确的，不过我觉得可以进一步告诉作者这个其实只是时间局部性，调度是没办法直接搞定传统的空间局部性，所以也是为什么tiling在后面去搞的原因；
3、可重排：可能解释成交换更容易理解，我理解重排实际上是比交换的范畴更大；解释成可交换更容易理解是因为tiling=strip mining + interchange，显然，strip mining（只涉及一层循环）总是合法的，而interchange却不总是，所以tiling的关键在于确定是否可以interchange，即交换；
4、permutable band分块是无代价的：这句话，我想可能是Uday当时写论文的时候，为了凸显贡献强化的语句，但是这句话显然是值得商榷的，目前来看，permutable band上绝大部分的分块都是有代价的（parallelogram损失外层并行、split引入同步开销、overlapped产生冗余计算，而diamond和hybrid可以看做是split的一种特殊情况），只有rectangular可以看做cost free，但这种在实际程序中太少见了，而且即便有也很难成为程序的关键部分；
5、permutable band免费地暴露了并行性：这句话也是，parallelogram是可以实现wavefront并行，但显然，如果没有这种在permutable band上实现分块，原本的程序可能是doall并行的，所以免费我觉得也是言过的（Uday的锅，哈哈）。

（我的理解仅供参考，不一定对）最后，还是手动点赞！

Ylisar

嗯嗯！赵老师这个补充很重要（尤其第4/5点），我之前也在以为 分块和并行化 一定会为目标代码带来性能的提升，现在了解了。我自己还不太了解对“分块”本身的研究，看起来这的确是比较重要的部分。[可怜]

Ylisar

（文章里我提及“免费”，主要想说这个“变换”是直接就正确的：可交换性直接充分地保证了分块和在块上做并行化这两个变换的正确性，这可能是自己是从形式化验证角度切入的，hhh）

Zephus

没关系，加油。欢迎随时交流，我也很想将性能优化和形式化方向结合，有机会一起合作[赞][赞][赞][赞]

redhat9i

好的！在有问题或新的进展时，会多和老师交流～