1.3　循环优化的数学抽象

科学计算和深度学习领域中大多数的应用程序的核心部分都是 N （ N ≥1）重嵌套循环，循环体内基本都会涉及对数组的规则访问，对标量的访问也可以看成对长度为1的数组的访问。循环作为程序中耗时最多的程序段，始终是编译优化的核心研究对象。在过去数十年的研究和实践过程中，学术界对循环优化的研究取得了巨大的成功，并逐渐形成了依赖判断、循环变换、任务划分、任务映射、并行性和局部性优化和代码生成等几个基础的研究方向。

这些研究方向之间存在着紧密的联系。例如，依赖判断是循环变换的基础，只有无依赖的循环迭代之间可以改变执行顺序；循环变换的目的是在不破坏并行性和局部性的基础上实现任务划分和任务映射；循环变换决定了任务划分和任务映射的粒度以及程序性能；任务划分和任务映射又会反过来影响程序的并行性和局部性，进而限制了循环变换的顺序和种类；代码生成是循环优化的最后一个步骤，可以实现源到源翻译，也可生成低级语言的等价表示。

在研究中人们发现， N （ N ≥1）重循环嵌套的上界和下界表达式通常是仿射表达式 ^[1] ，而且在循环体内的多维数组下标也通常是循环变量的仿射表达式。在循环约束及数组下标均为仿射表达式的前提下，依赖判断退化为线性表达式之间的判等问题，最终可以用线性规划理论解决；而循环变换以及基于循环变换进行的任务划分、任务映射、并行性和局部性优化，也可以用仿射表达式进行描述。也就是说，在假设循环约束及数组下标均为仿射表达式的前提下，依赖判断、循环变换、任务划分、任务映射、并行性和局部性优化这些研究方向可以统一使用仿射关系来描述，形成了一个完备和自恰的理论体系，也就是本书将要介绍的多面体理论。

1.3.1　多面体模型的基本概念

多面体理论是一种在线性代数、线性规划、集合论、数理逻辑和最优化理论的基础上逐步形成和发展起来的抽象数学模型，它用迭代空间、语句实例、访问关系、依赖关系和调度来描述一个程序，并基于调度变换实现一系列并行性和局部性相关的优化。多面体理论已经在学术界和工业界成熟的编译器系统中获得了巨大的成功，GCC的Graphite框架 ^[68] 和LLVM的Polly框架 ^[37] 都是基于多面体理论实现的，不仅如此，Open64 ^[27] 和IBM XL ^[18] 等编译器也提供了基于多面体理论的循环优化功能。

多面体理论对于这类循环约束和数组下标均为仿射表达式的循环优化问题做了如下抽象：

（1）迭代空间抽象：将一个 N 重嵌套循环抽象为一个 N 维迭代空间，每层循环的循环上界和循环下界的线性约束构成整个迭代空间的约束集合。这个 N 维迭代空间对应 N 重循环中各个循环索引变量的取值集合，只有满足约束的 N 维向量才是一个合法的迭代向量。

（2）语句实例抽象：将 N 重嵌套循环中的每个静态语句及其对应的循环迭代向量的组合抽象成一个动态语句实例。静态语句 S 的一个动态访问实例可以写成 S （ i ），其中， i 表示一个 N 重嵌套循环的迭代向量。

（3）数据空间抽象：将一个 M 维数组抽象为一个 M 维的数据空间，数据空间的维度可以与迭代空间不同。迭代空间中的任意一个迭代向量可以通过数据访问关系映射到数据空间中的某一个具体的位置。

（4）处理器空间抽象：将一个系统中的可以并行工作的计算单元抽象为 K 维的处理器空间，处理器空间中的每个处理器都有唯一的整数标识。

（5）依赖关系抽象：对数据空间的访问关系可以细分为读访问和写访问，动态语句实例之间的依赖关系就是程序中对数据空间的读写顺序约束。

（6）调度抽象：将任意一个动态语句实例映射到一个多维的执行时间，相当于给每个动态语句实例指定了一个执行顺序，这个执行顺序是由多维时间的字典顺序描述的。

基本上述抽象模型的编译优化方法也称为 多面体优化 （polyhedral optimization）。多面体模型把循环优化问题转换成多维空间和这些空间之间的仿射映射，使得我们可以使用标准的数学技术（特别是线性规划）来解决循环并行性和局部性优化问题。

首先考虑循环迭代空间。由于 N 重循环的迭代空间是一个满足循环约束的 N 维子空间，因此构造循环迭代空间的核心是确定每一重循环的上界和下界。而在这个过程中通常需要对循环做一些等价变换，同时对一些无法在编译时确定的情况保守处理。经过等价变换的循环只有一个循环索引变量，而且循环索引变量的步长为1。对于下界为 l 、步长为 d （ d> 1）的循环索引变量 i ，可以引入一个新的循环索引变量 i ^′ ，将循环中对 i 的引用代数替换为 d×i ^′ + l ，从而实现循环索引变量的代数替换。

对于循环上界无法在编译时确定的情况，可以保守地认为循环上界为+ ∞ ；同理，对于循环下界无法在编译时确定的情况，可以保守地认为循环下界为 −∞ 。但是，需要注意的是，当循环上界或下界是基于某个全局不变的符号的表达式时，是不需要做保守处理的。迭代空间是一个整数集，整数集描述的迭代域并不隐含语句的实际执行顺序，因为实际的执行顺序由调度来表示。

对于经过前述等价变换后的 N 重循环，由循环迭代变量和循环上下界构成的线性不等式组构成整个 N 维迭代空间的约束集合。在多面体优化中，为了方便利用整数线性规划的数学模型实现相应的优化，通常将约束写成以下形式：

其中， 表示 N 维整数空间， B 是一个 N×N 的整数矩阵， d 是一个长度为 N 的整数向量， 0 为 N 维零向量。

根据线性代数的基础知识可知， N 维仿射空间中的一个超平面是一个 N− 1维的仿射子空间，可以用仿射方程组 Mx + c = 0 来表示。 N 维空间的一个超平面将 N 维仿射空间划分为两部分，每一部分称与该超平面一起都被称为一个半空间，半空间可以用 Mx + c ≥ 0 来表示。由多个半空间的交集构成的子空间称为多面体。

式（1-1）定义了 N 维空间中的一个凸多面体（convex polyhedron）。满足上述约束的任意两点的连线一定位于一个多面体内部。凸多面体中任意一个整数点都是一个合法的循环迭代向量。凸多面体在任意维度的投影最终对应该维度的循环上界和下界。

在多面体模型中，式（1-1）中的矩阵表示还可以用整数多面体 ^[55] 和Presburger表示 ^[62] 。我们将在第2章给出整数集和Presburger表示的准确定义。图1.3中的二重循环对应的迭代空间可以用Presburger表示

来描述。

采用Presburger表示有利于实现自动推导，还可以在描述线性约束时使用整数取余（rem）、向下取整除法（floordiv）、向上取整除法（ceildiv）、整数取最大值（max）、整数取最小值（min）等特殊运算符。在仿射约束的基础上增加rem、floordiv、ceildiv、max和min等特殊运算符后得到的表达式称为近似仿射表达式。多面体模型要求循环索引变量的上界和下界表达式必须是由符号常量或者外层循环索引变量构成的近似仿射表达式。

接下来介绍数据空间对应的访问函数。多面体模型要求对数据空间的访问函数必须是由符号常量或外层循环索引变量构成的近似仿射表达式。在多面体模型中，动态语句实例 S （ i ）中对数组 A 的读访问和写访问可以分别用 R _S,A （ i ）和 W _S,A （ i ）来表示，其中， i 表示多面体中的一个迭代向量。对于一个语句中有多次对 A 的访问的情况，可以拆成多个基本访问操作。图1.3中的语句S2对Out数组的访问函数为

在假定所有的循环迭代都遵循同样的仿射表达式约束的前提下，可以将 N 维迭代向量对 M 维数据空间的仿射访问函数表示为矩阵形式

式中， i 是满足迭代空间约束的 N 维循环迭代向量； F 是 M×N 维整数矩阵，用于表示仿射访问函数中每个循环索引变量的系数； f 为 M 维整数向量，用于表示 M 维数据空间的索引表达式中的常量部分。

访问数据空间的每个操作都对应唯一的 F 和 f ，不同的数据访问操作的 F 和 f 可以不同。仿射访问函数提供了从迭代空间到数据空间的一个映射关系，基于仿射访问函数可以确定某些迭代是否会访问同一个数据或相邻的数据，或者访问数据的局部性特征等。对于更加一般的情况，即不同的循环迭代遵循不同的访问规则的时候，可以使用多个仿射访问关系的并集来描述完整的访问函数。

接下来考虑调度抽象。式（1-1）所示的迭代空间并没有规定每个迭代向量之间的遍历顺序，实际的遍历顺序（即动态语句实例的执行顺序）是由调度抽象来描述的。每种可行的执行顺序都可以称为一种调度，而初始调度即是原始程序对应的串行执行顺序，就是按照从外到内的方式排列循环下标变量取值的顺序。

在确定了一个合法的调度之后，就相当于确定了循环迭代的执行顺序，即按照迭代向量的字典顺序执行每个循环迭代。一个向量 i =（ i ₀ ,i ₁ ,…,i _n ）按照词典排序小于另一个向量 ，记为 i < i ^′ ，当且仅当存在一个 m< min（ n,n ^′ ）使得 ，并且 。

对循环并行性和局部性的优化是通过对调度进行一系列的变换来实现的。任意不破坏原有程序语义中的数据依赖的调度变换都是合法的，但是不同的执行顺序的性能是不同的，特别是考虑到现代体系结构中复杂的存储层次关系的前提下。如何从所有可行的执行顺序中选择一个最优的顺序，是循环优化算法需要考虑和解决的问题，我们将在第4章进行深入介绍。

为了简化处理，初始阶段可以忽略处理器空间，即假设处理器空间的维度与迭代空间相同，而且处理器空间的每个维度都有无限多个处理器。不存在依赖关系的循环迭代可以在虚拟处理器空间中实现完全并行。这样可以实现循环划分和循环调度之间的解耦。在完成依赖分析和循环调度之后，再通过一个简单的处理器分配算法将虚拟处理器映射到物理处理器，同时赋予原来在虚拟处理器空间中完全并行的循环迭代一个确定的执行顺序即可。

基于上述抽象数学模型，可以将循环变换问题转换为一个最优化问题。即选择一个合适的映射关系，把一个迭代空间中的每个语句映射到特定的执行时间或者处理单元上，使整个程序在维持原始循环串行语义的前提下尽可能高效地执行。为了实现最优的任务映射，多面体理念还必须解决依赖分析、并行性优化、局部性优化、任务映射等一系列的基础问题。

1.3.2　多面体模型在编译器中的应用

在复杂场景下，为了降低编译优化的难度和工作量，通常需要采用多层抽象的形式，在不同的抽象层次实施不同级别的优化。以深度学习领域的编译优化为例，通常分为计算图级别的优化（例如计算图融合和调度）、算子级别的优化（例如并行性和局部性的开发）以及指令级别的传统优化。

多面体模型的编译抽象层次是高于那些以指令级并行为优化目标的传统编译器的，同时，又是低于以划分计算图为目标的高层编译器的。当然，随着多面体模型的不断发展，更多基于多面体模型的编译优化技术将不断向上和向下渗透到底层和上层的编译抽象层次，为优化编译器的整体设计带来更多新的技术路线。本书将多面体模型的编译抽象层次定位在张量计算的循环优化上，即在充分考虑底层体系结构特征的基础上，实现张量级别的循环变换、任务映射和代码生成。

更具体地，多面体模型的任务是将循环嵌套内的张量计算通过循环变换，转换成适于在底层体系结构上高效执行的代码。这要求多面体模型要充分考虑程序的并行性和局部性等特征。对于程序的并行性，多面体模型要解决的是通过线程级并行、向量化等方式来充分挖掘程序的数据并行，程序的任务并行并不是多面体模型要解决的目标。对于局部性，多面体模型通过循环变换来尽量减少程序在目标体系结构上执行时所需要的数据传输开销。为了实现这个目标，多面体模型还需要自动实现将任务映射到目标体系结构的特定硬件抽象上，同时还要自动实现数据在存储层次结构之间以及特定计算功能部件之间的数据流管理。此外，多面体模型还需要在代码生成阶段，充分考虑与其他基础编译工具的兼容，因此在代码生成阶段，多面体模型还要兼顾能够便于实现指令级并行等其他程序变换的相关优化。

1.3.3　基于多面体模型的编译流程

多面体模型经过三十几年的发展，已经形成了一套完整的理论体系和编译流程。本节简要阐述多面体模型在现代优化编译器中实现的几个步骤，即依赖分析、循环变换、并行性优化、任务映射、局部性优化和代码生成，更具体的内容在本书的后面章节详细介绍。

1．依赖分析

原始串行程序的执行语义定义了不同循环迭代之间的依赖关系，在循环优化中必须保持的依赖关系包括读后写依赖、写后写依赖和写后读依赖。对于不存在这三类依赖关系的循环迭代，可以以任意的顺序执行；而存在上述三种依赖关系的循环迭代既不能并行也不能改变执行顺序。

确定两个地址访问是否存在依赖属于别名分析的范畴。准确有效的相关性测试对并行编译器的性能能否很好发挥十分重要，计算机程序中所有数据相关性的这一过程就称为依赖分析。在过去数十年中，对数据依赖和控制依赖关系已经进行了深入的研究。

相关性测试是用来确定循环嵌套中对同一个数组的两个或多个下标引用之间是否存在相关性的一种方法。为了便于解释，除循环本身以外，我们将任何控制流都忽略掉。假定想要测试如图1.7所示的用 n 个整数 i ₁ ,i ₂ ,…,i _n 表示的 N 层循环嵌套中从语句 S ₁ 到 S ₂ 是不是存在相关性。

对于任意形式的访问函数，准确判断两个循环迭代是否访问相同的地址是非常困难的。好在科学计算和深度学习领域的大多数应用程序对数组的访问都是有规律的，数组下标一般可以表示为 仿射函数 。在限定访问函数为仿射函数的前提下，就可以利用整数线性规划（特别是整数规划）的相关方法来确定两个迭代是否存在依赖关系。

设 α 和 β 是在 n 层循环上界和下界范围内的 n 维索引向量，当且仅当存在 α 和 β ，并且 α 按照字典顺序小于或等于 β 以及满足

f _i （ α ）= g _i （ β ） ,∀i, 1≤ i ≤ m

时， S ₁ 和 S ₂ 存在依赖。

在多面体的理论框架中，数据依赖判断问题可以转换为一个整数线性规划问题，即在满足约束条件式（1-1）的情况下，是否有整数解的问题。

对于任意两个循环迭代，只要在满足迭代空间约束的前提下，不存在读后写、写后读和写后写依赖，就可以以任意的顺序执行。而且编译器还可以通过对循环迭代进行重排序来大幅提高数据局部性，也可以将无依赖的语句映射到不同的处理单元并行执行。或者通过合理安排不同循环迭代的执行顺序，来实现并行性和数据局部性的折中，从而在特定的处理器上高效地执行程序 。

式（1-4）表示一个 N 维迭代空间中的索引向量 i 与一个 M 维数据空间中数据位置之间的映射关系。对于任意两个仿射访问关系 F ₁ i ₁ + f ₁ 和 F ₂ i ₂ + f ₂ ，而且在已知至少有一个是写操作时，在分析这两个仿射访问是否存在数据复用和数据依赖时，需要区分以下几种情况：

（1） i ₁ = i ₂ ， F ₁ = F ₂ 且 f ₁ = f ₂ ：同一个迭代向量对应同一个访存操作时一定存在依赖。

（2） i ₁ = i ₂ ， F ₁ ≠ F ₂ 且 f ₁ = f ₂ ：一轮循环迭代中不同的访存操作之间存在依赖的必要条件是

（ F ₁ − F ₂ ） i ₁ = 0 （1-5）

（3） i ₁ = i ₂ ， F ₁ = F ₂ 且 f ₁ ≠ f ₂ ：同一轮循环迭代中不同的访存操作之间，在这种情况下一定不存在依赖。

（4） i ₁ ≠ i ₂ ， F ₁ = F ₂ 且 f ₁ = f ₂ ：如果循环迭代向量 i ₁ 和 i ₂ 存在数据依赖，那么一定有 F ₁ i ₁ + f ₁ = F ₂ i ₂ + f ₂ 。因此，可以得出不同迭代向量和同一个访问操作之间存在数据依赖的必要条件是

F ₁ （ i ₁ − i ₂ ）= 0 （1-6）

需要注意的是，式（1-6）中的 N 维向量 i ₁ 和 i ₂ 都必须是满足迭代空间约束的循环变量。根据线性代数的基本理论可知，对于 M×N 维的系数矩阵 F ，如果 F 的秩为 N ，那么说明 M ≥ N 而且只有 N 维零向量 x 满足 Fx = 0 。因此一定不存在数据复用，也就是说迭代空间中所有循环迭代向量都访问不同的数据位置。

（5） i ₁ ≠ i ₂ ， F ₁ ≠ F ₂ 且 f ₁ = f ₂ ：不同迭代向量和不同的访问操作之间存在依赖的必要条件是

F ₁ i ₁ = F ₂ i ₂ （1-7）

（6） i ₁ ≠ i ₂ ， F ₁ = F ₂ 且 f ₁ ≠ f ₂ ，不同迭代向量和不同的访问操作之间存在依赖的必要条件是

F ₁ （ i ₁ − i ₂ ）= f ₂ − f ₁ （1-8）

（7） i ₁ ≠ i ₂ ， F ₁ ≠ F ₂ 且 f ₁ ≠ f ₂ ，不同迭代向量和不同的访问操作之间存在依赖的必要条件是

F ₁ i ₁ + f ₁ = F ₂ i ₂ + f ₂ （1-9）

所有读操作之间都是没有依赖的，由于只有涉及写操作的访问之间才有可能存在依赖关系。两个操作之间存在数据依赖的充要条件是两个操作访问同一个存储位置而且至少有一个是写操作。因此，为了确保数据依赖不被破坏，对数据的所有写操作都必须维持原始的顺序，但是对同一个位置的两次写操作之间的读操作是可以以任意顺序执行的。

需要注意的是，只有当式（1-5） ∼ 式（1-9）在满足迭代空间约束的前提下有整数解时，两个操作才存在数据依赖。在满足迭代空间约束的前提下，寻找上述几个等式整数解的问题是一个典型的整数规划问题。而整数规划问题是一个已知的非多项式NP（non-polynomial）完全问题。由于精确的依赖分析代价非常大，因而编译器只好去寻求一些能够有效实现的保守分析办法。传统编译器通常依靠两种依赖测试方法来检查数组引用之间的相关性，即Banerjee测试 和GCD测试。我们将在第3章详细介绍依赖分析的基本方法。

2．循环变换

循环变换是多面体优化的核心，也是实现并行性和局部性发掘的核心手段。如果一个 N 层循环嵌套结构有 K （ K ≤ N ）个可以并行化的循环，即这 K 个循环的所有迭代之间都没有依赖关系，就说这个循环的并行度为 K 。对于并行度为 K 的 N 层嵌套循环，可以在一个计算单元上以任意的顺序遍历这个 K 维的子迭代空间，在 K 维子迭代空间中的每一个循环迭代，都需要执行另外的 N−K 层循环；也可以将 K 维子迭代空间映射到一个处理器阵列上并行处理，而且在处理器之间不需要同步。

在过去数十年中，基于仿射变换的循环优化已经得到了深入的研究。通过将仿射变换分解为一系列基本的变换，可以相对容易地理解仿射变换对源程序的修改。构成整个仿射变换的每一种基本变换，都对应源代码层次上的一个简单的改变。常见的几种基础仿射变换如下：

（1）循环交换（loop permutation）：交换内层循环和外层循环的次序。

（2）循环反转（loop reversal）：按照相反的顺序执行一个循环中的所有迭代。

（3）循环倾斜（loop skewing）：对原始循环的迭代空间进行坐标变换。

（4）循环延展（loop scaling）：将循环索引变量和循环步长做等比例缩放。

（5）循环合并（loop fusion）：把原程序中的多个循环下标映射到同一个循环下标上。

（6）循环分布（loop fission）：把不同语句的同一个循环下标映射到不同的循环下标。

（7）循环偏移（loop shifting）：把一个动态语句实例偏移固定多个循环迭代。

在上述7种变换中，前3种都是幺模变换。一个幺模变换可以用一个幺模系数矩阵来表示。幺模矩阵是一个方阵，其行列式为 ± 1。用于循环变换的幺模矩阵还有一个额外的特性就是它的所有元素均为整数。幺模矩阵的另一个重要性质是，幺模矩阵的乘积和逆矩阵仍然是幺模矩阵。幺模变换的重要性在于它把一个 N 维迭代空间映射到另一个 N 维的多面体，并且两个空间的迭代之间具有一一对应关系。

以幺模变换为基础实施循环的工作在21世纪初就有比较成熟的研究 ^[80] ，这个理论把循环的互换、反转和倾斜都使用变换矩阵来表示，其目的是使循环嵌套中并行化的程度或者数据局部性的程度达到最高，这些变换对并行机器上的存储层次结构也能有效支持。

幺模变换可以描述任何基于循环交换、循环倾斜和循环反转构成的复杂变换。最终的变换矩阵可以将各种基本的循环变换矩阵相乘即可。而基于幺模变换矩阵的循环优化，本质上是在给定一组调度约束的条件下，求出最大的目标函数。

可以用一个 N×N 的方阵来表示将一个原始 N 层循环（ i ₁ ,i ₂ ,…,i _N ）转换为 的循环交换，方阵的每个行向量代表一个循环，对于第 i 层循环来说，只有第 i 个元素为1，其余元素均为0。因此，原始循环对应 N×N 的单位矩阵，而变换后的循环对应变换矩阵。一个合法的循环交换必须维持原始循环的依赖关系。要实现第 i 层循环和第 j 层循环的循环交换，只需要交换原始矩阵的第 i 行和第 j 行即可。图1.8所示为 N =2时的循环交换示例，在这个循环中，每个循环迭代之间都不存在依赖关系，所有循环迭代都可以并行执行。

对于图1.8所示的循环交换示例，循环迭代之间并不存在依赖关系，图中箭头仅用于表示不同迭代之间的执行顺序。图中每个坐标轴表示一层循环，每个圆点都代表一次循环迭代，对应的各层循环的循环变量的坐标构成迭代向量。

与循环交换类似，可以用一个 N×N 的方阵来表示循环反转。将一个原始 N 层循环（ i ₁ ,i ₂ ,…,i _N ）的第 i 层循环做循环反转，只需要将原始循环对应的 N×N 单位矩阵的第 i 行的对角元素取相反数即可。同样，一个合法的循环反转必须维持原始循环的依赖关系。在完成循环反转之后，动态语句实例中对循环变量的引用也需要同步更新。图1.9所示为 N =2时的循环反转示例。

对于第 j 层循环相对于第 i （ j>i ）层循环的循环倾斜变换，实际上是在对迭代空间进行坐标变换。为了得到基础循环倾斜变换的变换矩阵，只需要将 N×N 的单位矩阵的第 j 行的第 i 列置成1即可，最终得到的变换矩阵实际上是一个下三角矩阵。对于倾斜因子为 f 的通用循环倾斜变换，只需要将 N×N 的单位矩阵的第 j 行的第 i 列置成 f 即可。通用的循环倾斜变换也可以看成循环延展变换和基础循环倾斜变换的组合。图1.10所示为 N =2时的循环倾斜示例。

幺模变换只能用于完美嵌套循环，而且只能对循环嵌套中的所有语句和所有循环迭代做同样的变换，因此无法实现诸如循环延展、循环合并、循环分布以及循环偏移等重要的基础仿射变换，也无法实现诸如循环分块、循环分段（loop strip-mining）和循环展开压紧等近似仿射变换。这种局限性主要源自其基于矩阵的变换表示。

与之相比，基于多面体模型的循环变换更加一般化。它基于更加一般化的关系运算（矩阵运算只是各种关系运算中的一种），可以表示各种各样的变换形式，使用约束也更少。它不仅可以用于描述任意的循环嵌套，而且每个语句都可以有自己独立的映射关系，因而可以做的转换更加丰富。表1.2给出了上述7种基础仿射变换对应的多面体调度表示。其中，循环分布和循环合并变换中的常数0和1是为了维持原始循环的语义顺序而引入的常量维度。我们将在第4章详细介绍多面体模型中如何实现这些基础循环变换。

3．并行性优化

多面体中的调度是近似仿射调度，它是由循环迭代向量与全局符号的近似仿射表达式构成的映射关系。而调度生成的过程就是任务映射、任务划分、数据局部性和任务并行性优化的时机。调度的生成本质上可以看成对原始迭代空间和数据空间进行坐标变换。

并行性粒度与具体的应用程序和硬件紧密相关。一般情况下，在超标量硬件上可以开发指令级并行性，在向量处理器上可以开发指令级并行性和数据级并行性，而在多核处理器上则可以同时开发指令级并行性、数据级并行性和线程级并行性。实现循环并行化的目的是使可以并行化的循环迭代数量达到最大。对于相关性可以用相关距离来表示的深度为 N 的循环来说，不论是细粒度或粗粒度计算，可以开发的并行度至少为 N− 1。

为了优化循环的并行性，多面体模型可以把无依赖的循环交换到内层循环以便于实现循环向量化，也可以把无依赖的循环交换到最外层循环以便于实现循环并行化。从这个角度来看，循环向量化和循环并行化是两个互相冲突的优化目标。将便于实现向量化的循环交换到内层循环，可以保证程序中对数组元素的连续访问能够命中高速缓存；而将便于实现并行化的循环交换到外层循环，可以降低映射到不同处理器上的并行任务之间的同步和通信开销。

确定仿射调度，使得数据局部性、并行度等指标中的一个或多个达到最优，这也是多面体模型需要重点解决的问题。我们将在第5章介绍循环并行化的主要方法。

4．任务映射

任务映射反映了循环和处理器空间之间的映射关系，在多面体的世界中也可以使用映射关系来表示。计算划分 π _s 是一个将语句 S 的动态实例映射到一个整数向量的仿射函数，这个整数向量表示虚拟处理器编号。 π _s 必须满足循环约束和数据依赖关系。类似地，数据映射 ϕ _A 将每个数组元素映射到一个虚拟处理器编号。而计算 π _S 和 ϕ _A 的过程实际上是一个优化问题。类似地，还可以定义一个仿射时间变换 θ _S 表示语句 S 到执行时间的映射。

线性规划方法主要用于求解线性函数在线性等式或不等式约束下最大值或最小值。具体到循环优化问题，整个算法的输出是一系列仿射函数，这些仿射函数定义了每个处理器在哪个时刻执行哪个循环迭代。算法利用仿射函数来描述原始迭代空间中的循环迭代实例与处理器迭代空间之间的映射关系，还利用仿射函数来描述原始迭代空间中不同迭代的执行顺序。

任务映射还需要考虑数据局部性和同步开销的影响，我们将在第5章介绍基于多面体模型的任务映射方法。

5．局部性优化

可以结合式（1-1）和式（1-4）进行访存依赖分析和数据局部性优化。数据依赖和数据局部性具有紧密的关联，但又不完全相同。考虑两个读取同一位置的循环迭代，二者存在数据局部性，但是并不存在数据依赖。迭代空间相当于仿射访问函数的定义域，对依赖的分析相当于在定义域中找出所有的访问同一个位置的循环迭代。如果两个访问同一位置的循环迭代，其中至少有一个是写操作，那么这两个循环迭代之间就是有数据依赖的。最终可以实现对于没有依赖的循环迭代和数据访问调整访问顺序，对于存在数据局部性的情况调整访问顺序从而达到利用数据局部性的目的。

循环分块可以降低同步开销并改进循环的数据局部性，它将一个深度为 N 的循环嵌套映射到深度为2 N 的循环嵌套，其中 N 个内层循环只有少量的固定迭代。循环分段和循环分块类似，它只把一个循环嵌套结构中的一部分循环分解开，每个循环分解成两个循环，这么做的好处是一个多维数组被分段访问，从而获得较好的缓存利用率。

如前所述，局部性优化与并行性开发以及任务映射是紧密相关而且互相影响的，我们将在第6章介绍局部性优化的详细内容。

6．代码生成

通过对多面体进行变换可以实现并行性和局部性的挖掘，而在确定了调度策略之后，就可以按照调度确定的顺序生成代码了。代码生成通常涉及从一种描述到另一种称之为中间形式描述的转换。转换的另一种情况是源到源变换（有时称为预编译器），实现程序从一种高级语言转换为另一种高级语言的转换，在这之后再利用目标机器的第二语言编译器进行编译。

根据变换后的迭代空间和调度生成代码，只需要在确定了循环的嵌套层次关系后，从最内层循环开始，不断利用Fourier-Motzkin消去法 ^[65] 得到每个循环维度的上界和下界。Fourier-Motzkin消去法是一种求解线性规划问题的常用方法，我们将在2.3节介绍Fourier-Motzkin消去法的基本原理。每运用一次Fourier-Motzkin消去法，多面体就会减少一个维度。而循环体代码可以利用仿射函数变换矩阵确定下标表达式。

我们还要常常对控制流命令连接的基本程序块进行优化以获得较高的并行性。不同类型计算硬件的并行代码生成策略也存在较大的差异，具体内容可以参考第7章。

---

[1] 从 N 维实数域R ^N 到 M 维实数域R ^M 的映射 x → Ax + b 称为仿射变换，如果 A 是一个 M × N 的矩阵， x 是一个 N 维向量， b 是一个 M 维向量。仿射变换可以看成在线性变换 Ax 的基础上增加了一个常数项 b 。 YLVqx1mQGmZk7jjpjhAdzs2buDqIZuRatWOcsmXPJDWM+k8gJ3VaEoR+MSYagK6G