text: [翻译] Polyhedron Model, 2011, Encyclopedia of Parallel Computing
  同义词：polytope model多面体模型是循环程序的一种“计算图式”（computation graph）的抽象表示，基于这种表示，我们可以判断程序的等价性、（更好的）并行执行是否可能。计算图中的每个点对应某个语句的一次迭代，以整数向量标识，这些点属于其语句所围绕在的循环嵌套的界所对应的多面体。作为回报，借助线性规划工具，这些多面体可以被分析/变换，这使能了对等价程序的自动探索：我们可以定义某个目标函数，使工具算出它认为的最/较优等价程序。多面体模型有其应用场景限制，大多关注操作数组的循环嵌套中（并且需要cond/loop bounds/array access表达式都是仿射的），但学界对拓展其应用场景的研究火热。在自动并行化之外，多面体模型可以在许多程序变换场景中使用，比如在内存/性能的优化中。由于编译不同阶段的不同需求，程序有许多表示，这些表示的基本单位都是“语句/指令”（statement），但这种粒度不适合自动并行化（循环变换）的分析，因为此时我们关心的是“语句实例”（instance），也即分析/变换的基本单元，我们需要一种表示将语句实例显式化的表示。一个循环程序必须被表示为一个集合的实例，迭代域（iteration domain，D），在其中每一个实例有其自己的索引（distinct name），配合其所属的语句，以被单一地识别。这个集合对于终止程序是有限的，反之则为无限的。仅如此还不够，还需要确定实例的执行序，也即定义一个在迭代域上的序（D，&lt;）使我们能比较任意两个实例的的先后。这个序是非自反的，因为同一个实例和自己不会有先后关系。显然，常见的控制结构，seq，循环，条件语句，跳转，只是另一种较紧凑地定义该序的方式。同时，对于顺序程序，&lt;是全序，因为任意两个实例一定在语义上被决定了先后；对于并行程序，&lt;是偏序，因部分实例间没有强制的序，neither A &lt; B or B &lt; A。于是，循环变换/自动并行化所做的，就是找到一个新的序，在与旧的序所对应的“语义”等价的前提下，使某些指标更好；但迭代域其实不被改变。那么这种语义等价的条件是什么？这涉及到概念“依赖”（dependences）。假设对于实例u，我们可以刻画它读写的内存单元（可以over approximate），R(u)和W(u)，那么对于两个实例u/v，只要Ru/Wv, Wu/Rv, Wu/Wv的某个交集不空，u/v便（可能）有依赖（暂记为u&amp;v，&amp;即关系“可能有依赖”）。人们可以证明，只要可能有依赖的程序都以相同顺序被执行，那么两个程序是等价的。依赖即必要的序，即&amp;。至于如何命名实例，如何确定程序的迭代域和执行序，如何计算依赖，有很多选择。它们一般需要求解undecidable problems。在多面体模型中，集合一般表示为Z^n下的多面体，即一个集合的affine inequalities（{x|Ax&lt;b, A is a matrix, x/b is a vector}）的解集，在这里多面体模型和线性规划产生了连系。每一个语句对应一个多面体，多个语句则是它们的并集。注意到，程序一般会设计symbolic constant，即那些没有在循环嵌套中被“写入”的变量，这些变量会作为free variable出现在affine约束中，它们的具体的值不影响多面体的维数、基本形状。对于实例的执行序（即“调度，schedule”），所以以多维度的时间戳用以决定执行序是直观的，序即为词法序。我们为每个实例映射到其时间戳。对于依赖分析，我们假设了读写集R/W of u只决定于u的名字。不同变量没有alias，subscript在界内，否则通过计算R/W交集得不到依赖的全集。R/W一般以subscript function（配合数组名；单维度变量算作特殊的数组）表达，它总是仿射函数，对R/W构建计算“交集是否是空集”的线性约束集，判断其是否为空。若一定为空则能保证等价。总结说，可以被多面体模型操作的程序（static control program）要求，它的控制结构只是仿射界的循环，他的数据结构是标量的或者是关于循环变量（和Context）的仿射下标的数组访问。这种要求是语义上的，比如可以用while作为循环结构。这种标准程序主要出现在科学计算，线性代数，信号处理中。无界的迭代域其实是常见的。多面体模型用以优化“片段”，kernal，它们是不少见的。【什么是变换；琐碎，略】【搜索变换；略】【调度；略】【Placement，指如何将实例映射到虚拟处理器】【代码生成；略；对性能是重要的，不好的生成，尤其是含有大量cond test，会显著影响性能，过度的同步/communication也会】while，常常对应一个无限集。【暂略】条件语句。基本模型只支持赋值语句。迭代域分裂（index set/iteration set/domain splitting）。主要是能分裂单语句的R/W依赖，贡献更好调度的可能。如下。分块，增加并行化的粒度，同时对缓存良好。tiling主要是针对domain的，只是相应地要改schedule。【略】表达式。基本模型中表达式时原子的，在某种拓展中，表达式的求值可以并行，lazy，自定义，reuse。【暂略】仿射性（affinity）的放松。比如支持quasi-affine。【暂略】数组拓展（array expansion）。用一个新的array，可以去除依赖。【暂略】数组缩减（array shrinking）。在一些情况下，复写数组有收益。【暂略】通信生成（communication generation）。分布式内存架构下的代码生成。【暂略】局部性强化。【略】动态优化。类似动态分析，根据profiling的反馈自动化寻找高质量目标程序。配合机器学习启发式找新的schedule。【暂略】数学工具支持：pip，omega，.... 代码生成：cloog，...LooPo, Pluto, polly, graphite, ... 【暂略】