Polyhderal Model

本文的内容主要来自于对Presburger Formulas and Polyhedral Compilation文档的翻译和学习

1. 主要概念

对于代码的优化分析，有很多种方法，Polyhedral Model就是其中之一。Polyhedral Model的变种有很多，但他们核心的概念都是相似的，纵使他们各自的术语千差万别。
在所有的概念中，有三点最为重要：

Instance Set: 一段代码中语句的执行实例集和。
Dependence Relation: 是Instance Set中元素的二元关系集和，表示了一个语句实例对另一个语句实例的依赖，依赖有不同的类型（如读、写依赖）。
Schedule: 一个Schedule是一个偏序的定义，建立在Instance Set上，表示了执行中语句实例的顺序。

Polyhedral Model可以被用来分析程序，也可以用来改变程序，改变程序时就是对Schedule进行更改。但是更改不是随意的，需要满足一定的规则：

定义1.1 （可行Schedule）
记$D$为一个Dependence Relation，其元素$a\rightarrow b$表示语句实例$a$必须先于语句实例$b$执行。有一个Schedule $S$定义了一个偏序$<{S}$，那么$S$是一个在$D$上可行的Schedule当且仅当$D \subset (<{S})$。

2. Instance Set

定义2.1 （Instance Set）一个Instance Set是所有语句运行实例的集和。

这里的语句运行实例，其粒度与实际分析时的源程序有关，比如分析C代码，则语句运行实例对应了一个C语句，如果输入是编译中间表示形式，那语句实例可以对应一个基本块。

例2.1 对于二维卷积例子：

for (int i = 0; i < M; ++i)
for (int j = 0; j < N; ++j)
{
T1:    B[i][j] = 0.0;
       for (int p = 0; p < 3; ++p)
       for (int q = 0; q < 3; ++q)
       {
T2:        B[i][j] += Img[i + p][j + q] * Filt[p][q];
       }
}

其Instance Set可以写成{T1[i][j] : 0 <= i < M and 0 <= j < N; T2[i][j][p][q] : 0 <= i < M and 0 <= j < N and 0 <= p < 3 and 0 <= q < 3}。

3. Dependence Relation

在考虑Dependence Relation时，首先介绍访存关系。
定义3.1 （读关系）读关系是Instance Set和数据元素集合间的二元关系，反映了语句实例读取数据。
定义3.2 （写关系）写关系是Instance Set和数据元素集和间的二元关系，反映了语句实例写入数据。

需要指出的是读写关系并不总是能很有把握地给出，因为访存不一定是按照线性规则地，如A[i * i]这种访存就不能通过Polyhedral Model准确地给出访存位置。在这种情况下往往会采用保守估计。

Dependence Relation产生的原因很大程度上都是因为不同的语句实例会访问同一个数据元素，在某些情况下，这种访问顺序不能更改（如先读后写），因此产生了依赖关系。
定义3.3 （Dependence Relation）定义四种Dependence Relation: 1. 读后写， 2. 写后读， 3. 写后写， 4. 数据流依赖。其中数据流依赖是写后读依赖的子集，要求在写入的值被读走之前不能有其它对其的写入被执行。

例3.1 对于二维卷积的例子，其Dependence Relation如下：
读后写：${T2[i][j][p][q] \rightarrow T2[i][j][p^\prime][q^\prime] : p < p^\prime \land q < q^\prime }$
写后读：${ T1[i][j] \rightarrow T2[i][j][p][q]; T2[i][j][p][q] \rightarrow T2[i][j][p^\prime][q^\prime] : p < p^\prime \land q < q^\prime }$
写后写：${ T1[i][j] \rightarrow T2[i][j][p][q]; T2[i][j][p][q] \rightarrow T2[i][j][p^\prime][q^\prime] : p < p^\prime \land q < q^\prime }$
数据流：${ T1[i][j] \rightarrow T2[i][j][p][q]; T2[i][j][p][q] \rightarrow T2[i][j][p^\prime][q^\prime] : p < p^\prime \land q < q^\prime }$
所有的依赖都要满足，那么最终的Dependence Relation就是${ T1[i][j] \rightarrow T2[i][j][p][q]; T2[i][j][p][q] \rightarrow T2[i][j][p^\prime][q^\prime] : p < p^\prime \land q < q^\prime }$

4. Schedule

定义4.1 （Schedule）一个Schedule就是Instance Set上一个严格偏序$<_{S}$。

一个Schedule的表示方式也有很多种，比如表示成树。
例4.1 二维卷积的一种可行偏序是
${ T1[i][j] \rightarrow T2[i][j][p][q]; T2[i][j][p][q] \rightarrow T2[i][j][p^\prime][q^\prime] :p < p^\prime \land q < q^\prime }$，其对应的Schedule可以写为${ T1[i][j] \rightarrow [i, j]; T2[i][j][p][q] \rightarrow [i, j, p, q] }$这是一个可行Schedule，因为它包含了所有的Dependence Relation。

5. 总结

介绍到这里只是将Polyhedral Model中的三个基本概念讲述一下，或者说是介绍了如何用Polyhedral Model描述程序。这里遗留下的一个重要内容是如何算出满足需求的Schedule，这部分常常用线性规划结合Cost Model来完成，留作后续介绍吧。
另外近年来出现了几个工作用Polyhedral Model来做深度学习编译器，但从上面的简单介绍可以看到naive的Polyhedral Model有一些问题，比如在Dependence Relation里会将累加顺序限制住，这是因为Polyhedral Model并不知道加法有结合律和交换律。而深度学习中几乎所有的加和乘都可以假设有结合律与交换律，这也算是一种Domain Knowledge。因此必须要对Polyhedral Model进行恰当的修改才能很好地放入深度学习场景下。

Polyhedral Model