|
在第一篇文章中,笔者对 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/>也请大家关注赵老师在评论里的补充,因为个人阅读范围有限,会在后续学习过程逐渐对文章疏漏进行调整 |
本帖子中包含更多资源
您需要 登录 才可以下载或查看,没有账号?立即注册
×
|