多面体编译(Polyhedral Compilation)

Abstract

对《Presburger Formulas and Polyhedral Compilation》做一个总结。

这是一本由isl和PPCG的作者Sven Verdoolaege写的关于多面体编译的入门小册子。主要介绍了多面体编译相关的基础知识（数学基础-凸优化/编译基础-依赖分析）。在实践层面则使用PPCG这种isl-based的编译器——尽管isl不能和多面体编译划等号，但已成为多面体编译事实上的标准库。

Polyhedral Compilation通过一系列的program analysis/compilation techniques对程序中的语句实例dynamic-execution instances进行分析。

例子

语句实例dynamic-execution instance，简称实例。指的是在运行时执行的一组指令或操作operations。比如对于循环程序，语句实例个数就是迭代iterations个数。因为迭代个数有可能是很大甚至无限的，故我们采用数学方法来表示实例——polyhedral and Presburger formulas。下面举个例子：

for(i = 0; i < 3; i ++)
	B[i] = f(A[i]);    // S

for(i = 0; i < 3; i ++) 
	C[i] = g(B[2-i]);  // T

• 语句实例：两个循环，每个循环有一个语句。故该例中的语句实例就是两个语句的迭代执行实例——两个语句分别用S和T表示，则每一次迭代产生的语句实例可以表示成为S[i]/T[i]，其中i表示第几次迭代。

• 执行顺序：语句实例的执行顺序是多面体编译的一个很重要的话题——调度。在代码层面用调度树来表示，这里给出两种方式，都表示S[0]->S[1]->S[2]->T[0]->T[1]->T[2]的执行顺序。其中左边直接列出顺序，而右边的则用S[i]->[i]表示语句实例根据i的增加顺序来执行，其中i表示外层循环的迭代次数。

• 访存关系：上图中的箭头表示语句实例与B数组的访问关系。注意这里S是写内存访问，而T是读内存访问。

• 依赖关系：语句实例之间因为对内存的读写关系因此有了依赖，上图表示S[i]和T[i]语句实例之间的依赖关系。

多面体编译就是在不改变语句实例依赖关系（语义）的基础上，对程序进行变换来挖掘程序的并行性与局部性，针对不同特征的程序会有不一样的变换和约束。

上面的例子中，将开始需要串行执行6次的程序，分割成为{S[i]->[i]; T[i]->[2-i]}这样的并行块——c=0,1,2三次迭代之间没有依赖关系可以并行执行。原图更完整。

工具