本文节选自书籍《多面体编译理论与深度学习实践》，作者赵捷、李宝亮，经授权后发布。
在过去的数十年里，摩尔定律一直支配着半导体行业的发展路线，随着晶体管尺寸的不断变小单个芯片上集成的晶体管数量越来越多。
最新的 NVIDIA A100 GPU 单个芯片集成了 540 亿个晶体管，而嵌入式系统级芯片（System on Chip，SoC）中的晶体管数量，例如华为麒麟 990 集成了 103 亿个晶体管。晶体管数量的增加允许芯片设计厂商可以在单个芯片上实现更多的功能和更高的计算能力。也正是日益丰富的功能和日渐增强的处理能力，使得软件开发人员可以不断地开发新的应用，从而驱动着整个信息技术产业不断向前发展。
在现代计算机系统中，编译器已经成为一个必不可少的基础软件工具。程序员通过高级语言对底层硬件进行编程，而编译器则负责将高级语言描述转换为底层硬件可以执行的机器指令。编译器在将应用程序翻译到机器指令的过程中，还需要对程序进行等价变换，从而让程序能够更加高效地在硬件上执行。
在特定硬件平台和编程语言的双重约束条件下，应用程序的性能主要依赖于程序员编写并行代码的能力和编译器的优化能力。编译器还需要充分弥合上层编程模型与底层硬件的巨大鸿沟，尽可能地降低程序员的编程难度。也正因如此，编译技术的发展始终紧随着硬件架构的演化，并且扮演着越来越重要的角色。
1
面向经典体系结构的性能优化
从经典体系结构的角度，提升硬件性能主要有三类方法：第一类方法是将更多的精力用于发掘各种并行性；第二类方法是引入新的存储层次来缓解访存速度和存储容量之间的矛盾；第三类方法则是通过定制化的方法来提升硬件处理领域相关应用的性能。
1.1 并行性发掘
并行性的发掘主要有三种方式，即指令级并行、数据级并行和线程级并行。根据 Flynn 分类法 ，按照指令流和数据流的不同组合方式将计算机分为以下四类：
1. 单指令流单数据流（Single Instruction, Single Data, SISD），对应串行计算机体系结构，仅能挖掘指令级并行性。
2. 单指令流多数据流（Single Instruction, Multiple Data, SIMD)，可用于数据并行计算，可以挖掘指令级并行性和数据级并行性。
3. 多指令流单数据流（Multiple Instruction, Single Data, MISD），这类硬件的应用范围非常有限，具体实例包括密码破译或对单一信息流进行多频率滤波。
4. 多指令流多数据流（Multiple Instruction, Multiple Data, MIMD），这是应用较为广泛的一种并行计算机体系结构，可以同时挖掘指令级并行性、数据级并行性和线程级并行性。
1.1.1 指令级并行
一个处理器核心通常是指能够独立地从至少一个指令流获取和执行指令的处理单元，通常包含取指单元、译码单元、执行单元、访存单元和程序计数器和寄存器文件等逻辑单元。
指令级并行是指在单个处理器核心中，通过同时执行多条指令的方式来提高处理速度。通过巧妙地设计流水线结构，可以大幅度地提升单个处理器核心的指令级并行度。然而，受限于硬件复杂度，处理器中正在执行指令总数与流水线的深度和个数成正比。处理器中正在运行的指令总数决定了处理器的复杂度。
指令级并行是传统系统结构领域中较为成熟的一种并行方式，代表性的技术包括流水线（Pipeline）、多发射（Multiple Issue）、同时多线程（Simultaneous Multithreading）和超长指令字（Very Long Instruction Word）等。
其中，流水线并行是将每个功能单元通过分时复用的方式在不同的指令之间共享，是一种时间上的并行；而多发射则是在每个时钟周期发射多条指令到多个流水线中并行执行，是一种空间上的并行；将时间和空间维度的并行组合起来就形成了同时多线程技术和超长指令字技术。
1.1.2 数据级并行
数据级并行是一种空间维度上的并行处理模式，典型的实现方式是在硬件中集成向量运算部件，用单条向量指令同时处理多个数据，例如 Intel 的 SSE/AVX，ARM 的 NEON/SVE 等。数据级并行不仅可以充分挖掘程序中潜在的并行性，还可以精简指令序列。向量化不需要对硬件结构特别是流水线结构做大量的修改，通常只需要修改数据通路的位宽。
对于图 1.1 所示的代码，如果运行在普通的标量处理器上，编译器需要生成一个循环，通过 16 次迭代来完成整个计算任务，一次迭代完成一个元素的自增运算。如果运行在向量宽度为 4 的向量向量器上，编译器只需要生成 4 条向量加法指令即可完成计算，不需要插入任何分支跳转指令。
1.1.3 线程级并行
线程级并行既可以在单处理器核心内实现，也可以在多个处理器核心内实现。在支持硬件多线程技术的单处理器中，可以通过硬件多线程或者同时多线程等技术来提高资源利用率和计算效率。
但是，在设计复杂度和功耗墙问题的共同约束下，提升单个处理器的性能已经非常困难。一个自然的想法就是在单个芯片上集成多个处理器核心，通过挖掘多个处理器核心之间的线程级并行能力来提升总体的计算能力。
在线程级并行模式中，不同执行单元的指令流相互独立，可以以同步或者异步执行的方式处理各自的数据。
主要的实现方式有：对称多处理器结构（Symmetric Multi-Processing, SMP）、分布式共享存储结构（Distributed Shared Memory, DSM）、大规模并行处理器结构（Massively Paralllel Processing,MPP）、集群（Cluster）。与线程级并行紧密相关的是被 GPU 架构普遍采用的单指令多线程技术，即多个线程以锁步的形式执行相同的指令，但是每个线程处理不同的数据。
1.1.2 存储层次结构
随着体系结构技术的飞速发展，处理器执行指令的速度远远超过了主存的访问速度。这种日益拉大的速度差异对计算机体系结构的发展产生了巨大的影响。
为了弥合这种巨大的鸿沟，处理器中必须要设置由不同容量和不同访问速度的存储器构成的存储层次。存储层次可以提高程序性能的原因是保证了 CPU 大部分数据的访问时延都比较低。随着处理器计算速度和访存速度的差距越来越大，存储层次结构的设计显得越来越重要。
在典型的现代处理器中，每个 CPU 核有私有的 L1 Cache，一组 CPU 核有一个共享的 L2 Cache，而 L3 Cache 通常会被所有的处理器核共享。高速缓存的访问速度往往与容量成反比。容量越大，访问速度越低。由于程序中的时间局部性和空间局部性，高速缓存可以作为一个有效的硬件结构将最有用的数据保持在离处理器较近的位置。
为此，高速缓存需要尽可能多地保留最近使用的数据，在容量有限的前提下尽可能地替换出最近很少使用的数据。现代体系结构中的高速缓存通常是由硬件自动管理的，但是为了极致优化性能，程序员和编译器仍需要知道存储层次的相关信息。除了硬件自动管理的高速缓存以外，现代体系结构往往还有软件自主管理的便签存储器（Scratchpad Memory）。
1.1.3 领域定制架构
领域定制架构（Domain-Specifific Architecture）专用性强，反而可以使得逻辑设计更加趋于简单，在设计思路上也更加开放，不用受到传统指令集和生态因素的制约，已经在大数据处理、数字信号处理、密码学、高性能计算、图形学、图像处理和人工智能等领域获得了广泛的应用。
领域定制处理器一般会根据应用的具体特点，定制运算单元，简化控制逻辑，设计与领域计算特征相适应的存储结构和数据通路，虽然牺牲了通用性和灵活性，却获得了较高的性能和能效比。
特别是在第三次人工智能浪潮中，涌现出大量的面向人工智能应用的领域专用处理器，这些人工智能处理器在功耗、性能和集成度等方面较传统的 CPU、GPU 和 FPGA 都有很大的优势。
领域定制架构体现出领域的专注性。以引爆第三次人工智能浪潮的深度学习算法为例，其主要特点是计算量和输入、输出（Input and Output, IO）数据量都比较大，而且并行度较高。这要求面向人工智能应用的领域定制处理器（简称人工智能处理器）在存储结构、带宽和算力配置以及互连结构上做大量的定制化设计。
为了满足海量数据在计算单元和存储单元之间的高速传输需求，人工智能处理器不仅要具备与计算模式匹配的存储结构，还要在计算单元和存储单元之间具有高速的通信链路。
为了满足深度学习的算力需求和计算模式需求，人工智能处理器不仅要集成大规模的并行计算单元，还要能够高效地处理深度学习算法中常见的卷积、全连接和池化等操作。为了适应深度学习算法的典型计算模式，人工智能处理器在结构设计时还要考虑将不同的计算单元和存储模块有机地结合在一起，尽量降低相关操作之间的数据共享开销。
可以说，深度学习算法既是计算密集的，又是访存密集的。其中计算密集的代表是卷积运算，而访存密集的代表则是全连接运算。卷积神经网络（Convolutional Neural Network, CNN）的主要计算量也都来自卷积层。
以 GoogleNet为例，卷积计算量会占到总计算量的 90% 左右。因此，加速卷积运算是提升深度学习应用性能的核心任务。卷积层的输入是神经元和权值，经过图 1.2 所示的 N 重循环处理后，得到输出神经元。
一个卷积层包含 CO 个 C I × KH × KW 的卷积核，共计 CO × C I × KH × KW 个权值，每个卷积核对应输出神经元的一个通道。每个输出神经元涉及 C I × KH × KW 次乘累加运算，每个卷积层总的乘累加运算次数为 HO × WO × CO × C I × KH × KW。
卷积运算是一种典型的 Stencil 运算，Stencil 运算的特点是输入输出数据组织成一个多维网格，一个输出数据点的值只与临近点的输入点有关，虽然每个输出点都可以独立计算，但是运算密度较低，依赖关系复杂。Stencil 计算模式在流体力学、元胞自动机、天气预报、粒子模拟仿真、电磁学等领域的数值计算中都有广泛的应用。为了在领域专用处理架构上优化这类程序的性能，需要合理地组织计算次序和数据布局，充分发掘数据局部性和计算并行性。
作为访存密集型的代表运算，全连接运算本质上是矩阵向量运算，可以用图 1.3 所示的两层嵌套循环来表示。全连接运算的特点是，R 和 C 比较大，因而权值的 IO 数据量比较大；二维权值中的每个元素都只参与一次乘累加运算，权值局部性比较差，整个算法的计算密度较低。
2
编译器面临的挑战
前面从经典体系结构的角度介绍提升硬件性能的三类主要方法，即发掘并行性、优化存储层次和领域定制架构。但是，体系结构设计仅仅是确定了软件的执行平台，而在确定的执行平台上如何优化程序，则是程序员和编译器的职责。
为了充分利用硬件的处理能力，软件开发人员和编译器都需要充分了解底层体系结构的特点。对于程序员来说，编写正确而且高效的串行程序是非常困难的，编写正确而且高效的并行程序则更加困难，其难度会随着并行粒度的降低而增长。为了解放程序员，编译器需要担起性能优化的重担。
程序优化的目的是尽可能地发掘程序的并行性和硬件的计算能力，使得代码在具体硬件上的执行速度达到最高。优化是编译器为了改进应用程序的某项技术指标，在不改变程序语义的前提下，修改其内部数据结构或所生成代码的过程。
优化可以是架构无关的，也可以是架构相关的。为了把程序员使用高级语言编写的与架构无关的程序转换为可以在具体硬件上高效执行的机器指令，编译器需要在程序分析、代码优化和代码生成这三个核心步骤持续引入各种新的技术和方法。常规的标量优化技术包括循环不变量外提、常量传播、公共表达式删除、运算强度削弱、循环展开、软件流水、指令调度等。
并行性、局部性和领域相关设计对编译器带来了巨大的挑战。而这三个问题都与循环有着紧密的联系，因为大多数的计算机程序几乎将所有运行时间都花费在循环内，因此为循环优化付出的努力往往能得到最高的回报。但是，对应用程序的优化往往需要程序员和编译器的共同努力。例如，程序员需要对循环嵌套结构进行拆分和重写等操作，来帮助编译器更好地识别和优化循环。
1.2 并行性发掘
并行性的发掘可以通过软件静态完成，也可以通过硬件动态地进行。完全依赖硬件管理其并行性的机器称为超标量处理器，而完全依赖编译器来管理其并发性的机器称为超长指令字。
在一些成本或者功耗敏感的嵌入式应用场景（例如，物联网）中，通常依赖编译器来发掘并行性，而在桌面计算、服务器和云计算场景中，虽然硬件实现了强大的调度机制，也需要在编译器的配合下才能充分发挥硬件的指令级并行性能力。
编译器开发指令级并行性的基本思路是结合硬件的结构特点，通过指令调度的方法来提高硬件资源的利用率，常用的提高指令级并行性的方法如表 1.1 所示。
流水线的结构冲突、数据依赖和控制依赖会在处理器流水线中引入空泡。为了避免因流水线空泡导致的性能损失，通常需要编译器对指令序列进行静态调度。
例如，静态分析预测可以结合硬件的推测执行功能减少因控制流引入的流水线空泡，延迟槽调度则是用一些与控制流无关的指令来填充分支跳转指令的延迟槽，常规的静态指令调度则是将一些没有数据依赖的指令安排在一起，以避免因数据依赖引入的流水线空泡。
编译器支持指令级并行的基本方法是在基本块内实现简单的指令调度。然而，在一个基本块级别开发并行性的收益并不大。为了进一步发掘并行性，必须着力于开发循环级并行。循环级优化技术尝试从多个循环迭代中寻找并行性，通过重复执行多个循环体中的代码来提高程序的并行性。循环级并行优化可以显著提升程序的整体性能，因为程序中运行时间较长的代码片段通常是具有很多次迭代的循环。
循环优化首要目标是充分发挥硬件提供的计算能力，以减少延迟（尽可能快地完成计算任务）或者提高吞吐率（在相同的时间内完成更多的任务）。循环优化的基础方法包括循环展开、软流水、并行化和向量化。
其中，循环展开是通过复制循环指令的方式来避免循环的控制开销；软流水主要是对原始循环进行重新组合，将无依赖的访存和计算指令组合在一次循环迭代中；向量化和自动并行化的目的是要对处理大量数据或者可划分后能并行执行的程序改善性能。
循环向量化是编译器将循环中的标量运算转换为向量运算的过程，最终生成的向量运算指令会在同一个硬件单元上执行。
并行化则是把循环拆分成多个可以并行执行的子任务，在不同的硬件单元上并行执行每个子任务。循环并行化需要将循环进行划分，并让多个处理器分别执行其中的一部分。但是为了保证性能，还必须把处理器之间的通信量减少到最小。通信量实际上与数据局部性紧密相关，对于处理器经常访问的数据，在任务或数据划分时应当让它离处理器更近，否则会引入大量的通信和同步操作。
然而，循环向量化和循环并行化通常是两个互相冲突的优化目标，因为循环并行化通常是在外层循环进行，而循环向量化则必须在内层循环进行。自动并行化和自动向量化是现代编译器面临的主要困难，原因是编译器很难有效地收集和分析向量化或者并行所需要的数据相关性和控制相关性等信息。
由于编译器在自动向量化和自动并行化方面遇到了困难，软件开发人员不得不自己发掘应用的并行性，并且处理共享资源的访问冲突，这就要求编译器和编译语言能供提供一种易于描述并行性的编程模型。
1.2 局部性发掘
存储器的容量越大，访问速度越慢。幸好，程序访问的数据通常具有空间局部性和时间局部性。时间局部性通常是指某个数据被访问后，常常会在较近的时间再次被访问；空间局部性则是指某个数据被访问以后，常常会在较近的时间再访问与其相邻的数据。可以在内存之上设置多个存储层级来利用数据的局部性改进程序性能。性能调优一个非常重要的前提就是理解计算机系统的存储层次，并且结合硬件的存储层次和计算特征，进行特定的访存优化从而平衡访存和计算。
图 1.2所示的卷积过程可以通过循环变换转换成不同的实现方式和数据、时间和空间局部性特征，而不同的实现在不同的硬件上性能差异也非常大。我们以图 1.3所示的矩阵—向量乘法运算b = 
为例，当 M ≪ N（M 远远小于 N）时，每计算一个值 b[col]，会导致列向量 x 和矩阵 A 被不断地换入和换出，严重影响性能。
经过分析可以发现，在整个计算过程中，矩阵 A 中的每个元素只会被使用一次。因此，最理想的情况下，A 的数据元素只需要被加载到 Cache 一次，而列向量 x 则会被反复使用 M 次。Cache 优化的最终目标就是确保矩阵 A 的数据元素只被加载到 Cache 一次，x 的元素只被加载一次。因此，可以将图 1.3所示的源代码转换为图 1.4 所示的形式。
访存局部性优化比较成熟的手段是循环分块（loop tiling）和循环融合（loop fusion）。循环分块的基本思想是通过将大块的循环迭代拆解成若干个较小的循环迭代块，减少一个内存单元的数据重用周期，这种重用周期既可以是时间上的也可以是空间上的。循环融合则是将多个具有“生产-消费”关系的循环合并在一起，从而缩短了每个中间数据的重用周期，避免中间结果被换出高速缓存。
循环分块和循环融合都可以确保某个内存地址单元被加载到 Cache 以后，该内存地址单元会尽量保留在 Cache 中，这样就可以达到减少片外访存开销的目的。然而，循环分块和循环融合也是两个相互冲突的优化目标，因为循环融合会导致循环分块的约束增加，灵活性变差。
1.3 平台通用性
编程模型是体系结构和程序之间的接口和桥梁。编程模型的设计需要考虑具体的硬件机器模型，在可编程性和程序性能之间找到平衡点。编程模型使得体系结构与硬件无关，应用也独立于体系结构。如何向程序员展示领域相关的硬件特性，如何暴露并行性和局部性，如何实现跨平台的兼容性，如何简化领域相关的编程，是编程模型需要重点解决的问题。
传统系统结构的并行性通常包括超节点之间的并行性、超节点内多个处理器之间的并行性、处理器内多个处理器核心之间的并行性、处理器核内多个并行功能单元之间的并行化。超节点、多核处理器、处理器核、功能单元构成现在计算系统的层次化组织结构。
在不同的层次，往往对应不同的开发并行性的方法和编程模型。例如，在多个超节点之间可以利用消息传递的并行编程模型（例如 Message Passing Interface, MPI）来发掘超节点之间的并行性，在超节点内的多个处理器之间往往通常共享内存的多进程编程方式发掘并行性，在单个处理器核内则是通过共享内存编程模型（例如OpenMP）实现多线程之间的并行性，在单个处理器核心内则可以利用 SIMD/SIMT 编程模型来发掘多个并行功能单元之间的并行性。
领域相关设计通常是在传统体系结构的基础上，增加领域相关的硬件特性，在复用现有软硬件生态的基础上实现对特定应用的高效处理。而编译器则需要与硬件密切配合，向程序员暴露易于使用的编程模型。
在编程模型设计时，需要平衡通用性和领域专用性之间的关系，通用性可以方便程序的功能和性能的*迁移，而专用性则可以确保特定应用在特定硬件上的性能。通常情况下，编程模型的抽象层次越高，平台的通用性也就越好，但是对特定领域的性能通常不易保证。
不同的编程模型对应不同的并行化机制。并行编程模型提供的并行化机制可以分为两类：隐式并行和显式并行。显式并行是指由程序员利用语言特性、编译器命令或者库函数对并行性进行显式描述，而隐式并行则是通过编译器和运行时系统实现自动并行化。但是，受限于编译器的并行优化能力，自动并行化很难达到较高的性能。
为了利用显式并行编程模型开发并行硬件的计算能力，必须采用向量化和并行化的思维方式来编写软件代码。串行程序也需要重新编写以适配并行硬件。显式并行编程模型的编程难度更大，而且平台适应性较差。自动并行化是对上层应用最友好的方式，它可以充分复用现有的软件生态。然而，自动并行化是编译器当前面临的主要困难。
3
循环优化的数学抽象
科学计算和深度学习领域中大多数的应用程序的核心部分都是 N (N ≥ 1) 重嵌套循环，循环体内基本都会涉及对数组的规则访问，对标量的访问也可以看成是对长度为 1 的数组的访问。
循环作为程序中耗时最多的程序段，始终是编译优化的核心研究对象。在过去数十年的研究和实践过程中，学术界对循环优化的研究取得了巨大的成功，并逐渐形成了依赖判断、循环变换、任务划分、任务映射、并行性和局部性优化和代码生成等几个基础的研究方向。
这些研究方向之间存在着紧密的联系。例如，依赖判断是循环变换的基础，只有无依赖的循环迭代之间可以改变执行顺序；循环变换的目的是在不破坏并行性和局部性的基础上实现任务划分和任务映射；循环变换决定了任务划分和任务映射的粒度以及程序性能；任务划分和任务映射又会反过来影响程序的并行性和局部性，进而限制了循环变换的顺序和种类；代码生成是循环优化的最后一个步骤，可以实现源到源翻译，也可生成低级语言的等价表示。
在研究中人们发现，N (N ≥ 1) 重循环嵌套的上界和下界表达式通常是仿射表达式（从 N 维实数域
到 M 维实数域 RM 的映射 x → Ax + b 称为仿射变换，如果 A 是一个 M × N 的矩阵，x 是一个 N 维向量，b 是一个 M 维向量。仿射变换可以看成是在线性变换 Ax 的基础上增加了一个常数项 b。），而且在循环体内的多维数组下标也通常是循环变量的仿射表达式。
在循环约束以及数组下标均为仿射表达式的前提下，依赖判断退化为线性表达式之间的判等问题，最终可以用线性规划理论解决；而循环变换以及基于循环变换进行的任务划分、任务映射、并行性和局部性优化，也可以用仿射表达式进行描述。
也就是说，在假设循环约束以及数组下标均为仿射表达式的前提下，依赖判断、循环变换、任务划分、任务映射、并行性和局部性优化这些研究方向可以统一使用仿射关系来描述，形成了一个完备和自恰的理论体系，也就是多面体理论。
多面体理论是一种在线性代数、线性规划、集合论、数理逻辑和最优化理论的基础上逐步形成和发展起来的抽象数学模型，它用迭代空间、语句实例、访问关系、依赖关系和调度来描述一个程序，并基于调度变换实现一系列并行性和局部性相关的优化。
多面体理论已经在学术界和工业界成熟的编译器系统中得到获得了巨大的成功，GCC 的 Graphite 框架、和 LLVM 的 Polly 框架都是基于多面体理论实现的，不仅如此，Open64和 IBM XL等编译器也提供了基于多面体理论的循环优化功能。
多面体理论对于这类循环约束和数组下标均为仿射表达式的循环优化问题做了如下抽象：
(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)所示的矩阵表示还可以用整数多面体和 Presburger 表示。我们将在第2章给出整数集和 Presburger 表示的准确定义。图1.3中的二重循环对应的迭代空间可以用Presburger 表示：
来描述。
采用 Presburger 表示有利于实现自动推导，还可以在描述线性约束时使用整数取余 (rem)、向下取整除法（flfloordiv）、向上取整除法（ceildiv）、整数取最大值 (max)、整数取最小值 (min) 等特殊运算符。在仿射约束的基础上增加 rem、flfloordiv、ceildiv、max 和 min 等特殊运算符后得到的表达式称为近似仿射表达式。多面体模型要求循环索引变量的上界和下界表达式必须是由符号常量或者外层循环索引变量构成的近似仿射表达式。
接下来介绍数据空间对应的访问函数。多面体模型要求对数据空间的访问函数必须是由符号常量或外层循环索引变量构成的近似仿射表达式。在多面体模型中，动态语句实例 S(i) 中对数组 A 的读访问和写访问可以分别用
和
来表示，其中 i 表示多面体中的一个迭代向量。对于一个语句中有多次对 A 的访问的情况，可以拆成多个基本访问操作。图 1.3 中的语句 S2 对 Out 数组的访问函数为
在假定所有的循环迭代都遵循同样的仿射表达式约束的前提下，可以将 N 维迭代向量对 M 维数据空间的的仿射访问函数表示为矩阵形式
在(1–4)中，i 是满足迭代空间约束的 N 维循环迭代向量；F 是 M × N 维整数矩阵，用于表示仿射访问函数中每个循环索引变量的系数；f 为 M 维整数向量，用于表示 M 维数据空间的索引表达式中的常量部分。
访问数据空间的每一个操作都对应唯一的 F 和 f，不同的数据访问操作的 F 和 f 可以不同。仿射访问函数提供了从迭代空间到数据空间的一个映射关系，基于仿射访问函数可以确定某些迭代是否会访问同一个数据、或者相邻的数据、或者数据的局部性特征等。对于更加一般的情况，即不同的循环迭代遵循不同的访问规则的时候，可以使用多个仿射访问关系的并集来描述完整的访问函数。
接下来考虑调度抽象。(1–1)所示的迭代空间并没有规定每个迭代向量之间的遍历顺序，实际的遍历顺序（即动态语句实例的执行顺序）是由调度抽象来描述。每一种可行的执行顺序都可以称为一种调度，而初始调度即是原始程序对应的串行执行顺序，就是按照从外到内的方式排列循环下标变量取值的顺序。
在确定了一个合法的调度之后，就相当于确定了循环迭代的执行顺序，即按照迭代向量的字典顺序执行每一个循环迭代。一个向量
按照词典排序小于另一个向量
，记为 i < i′，当且仅当存在一个 m < min(n, n′) 使得
，并且
。
对循环并行性和局部性的优化是通过对调度进行一系列的变换来实现的。任意不破坏原有程序语义中的数据依赖的调度变换都是合法的，但是不同的执行顺序的性能是不同的，特别是考虑到现代体系结构中复杂的存储层次关系的前提下。如何从所有可行的执行顺序中选择一个最优的顺序，是循环优化算法需要考虑和解决的问题。
为了简化处理，初始阶段可以忽略处理器空间，即假设处理器空间的维度与迭代空间相同，而且处理器空间的每个维度都有无限多个处理器。不存在依赖关系的循环迭代可以在虚拟处理器空间中实现完全并行。这样可以实现循环划分和循环调度之间的解耦。在完成依赖分析和循环调度之后，再通过一个简单的处理器分配算法将虚拟处理器映射到物理处理器，同时赋予原来在虚拟处理器空间中完全并行的的循环迭代一个确定的执行顺序即可。
基于上述抽象数学模型，可以将循环变换问题转换为一个最优化问题。即选择一个合适的映射关系，把一个迭代空间中的每个语句映射到特定的执行时间或者处理单元上，使整个程序在维持原始循环串行语义的前提下尽可能高效地执行。为了实现最优的任务映射，多面体理念还必须解决依赖分析、并行性优化、局部性优化、任务映射等一系列的基础问题。
1.3.1 依赖分析
原始串行程序的执行语义定义了不同循环迭代之间的依赖关系，在循环优化中必须保持的依赖关系包括读后写依赖、写后写依赖和写后读依赖。对于不存在这三类依赖关系的循环迭代，可以以任意的顺序执行；而存在上述三种依赖关系的循环迭代既不能并行也不能改变执行顺序。
确定两个地址访问是否存在依赖属于别名分析的范筹。准确有效的相关性测试对并行编译器的性能能否很好地发挥十分重要，计算机程序中所有数据相关性的这一过程就称为依赖分析。在过去数十年中，对数据依赖和控制依赖关系已经进行了深入的研究。
相关性测试是用来确定循环嵌套中对同一个数组的两个或多个下标引用之间是否存在相关性的一种方法。为了便于解释，除循环本身以外，我们将任何控制流都忽略掉。假定想要测试下述用 n个整数 
表示的 N 层循环嵌套中从语句S1到S2 是不是存在相关性。
对于任意形式的访问函数，准确判断两个循环迭代是否访问相同的地址是非常困难的。好在科学计算和深度学习领域的大多数应用程序对数组的访问都是有规律的，数组下标一般可以表示为仿射函数。在限定访问函数为仿射函数的前提下，就可以利用整数线性规划（特别是整数规划）的相关方法来确定两个迭代是否存在依赖关系。
设 α 和 β 是在 n 层循环上界和下界范围内的 n 维索引向量，当且仅当存在 α 和 β，并且 α 按照字典顺序小于或等于 β 以及满足
时，S1和S2存在依赖。
在多面体的理论框架中，数据依赖判断问题可以转换为一个整数线性规划问题，即在满足约束条件(1–1)的情况下，上面的是否有整数解的问题。
对于任意两个循环迭代，只要在满足迭代空间约束的前提下，不存在读后写、写后读和写后写依赖，就可以以任意的顺序执行。而且编译器还可以通过对循环迭代进行重排序来大幅提高数据局部性，也可以将无依赖的语句映射到不同的处理单元并行执行。或者通过合理安排不同循环迭代的执行顺序，来实现并行性和数据局部性的折中，从而在特定的处理器上高效的执行程序（在编译领域，通常将没有依赖的嵌套循环称为 doall 循环，而将有依赖的循环称为 doacross 循环。 ）。
(1–4)表示一个 N 维迭代空间中的索引向量 i 与一个 M 维数据空间中数据位置之间的映射关系。对于任意两个仿射访问关系
，而且在已知至少有一个是写操作时，在分析这两个仿射访问是否存在数据复用和数据依赖时，需要区分以下几种情况：
(1) 
：同一个迭代向量对应同一个访存操作时一定存在依赖。
(2) 
：一轮循环迭代中不同的访存操作之间存在依赖的必要条件是：
(3)
：同一轮循环迭代中不同的访存操作之间，在这种情况下一定不存在依赖。
(4)
：如果循环迭代向量
存在数据依赖，那么一定有
。因此，可以得出不同迭代向量和同一个访问操作之间存在数据依赖的必要条件是：
需要注意的是，(1–6)中的 N 维向量
和
都必须是满足迭代空间约束的循环变量。根据线性代数的基本理论可知，对于 M × N 维的系数矩阵 F，如果 F 的秩为 N，那么说明 M ≥ N而且只有 N 维零向量 x 满足 F x = 0。因此一定不存在数据复用，也就是说迭代空间中所有循环迭代向量都访问不同的数据位置。
(5)
：不同迭代向量和不同的访问操作之间存在依赖的必要条件是：
(6)
：，不同迭代向量和不同的访问操作之间存在依赖的必要条件是：
(7)
，不同迭代向量和不同的访问操作之间存在依赖的必要条件是：
所有读操作之间都是没有依赖的，由于只有涉及到写操作的访问之间才有可能存在依赖关系。两个操作之间存在数据依赖的充要条件是两个操作访问同一个存储位置而且至少有一个是写操作。因此，为了确保数据依赖不被破坏，对数据的所有写操作都必须维护原始的顺序，但是对同一个位置的两次写操作之间的读操作是可以以任意顺序执行的。
需要注意的是，只有当(1–5)、(1–6)、(1–7)、(1–8)和(1–9)在满足迭代空间约束的前提下有整数解时，两个操作才存在数据依赖。在满足迭代空间约束的前提下，寻找上述几个等式整数解的问题是一个典型的整数规划问题。而整数规划问题是一个已知的非多项式 NP（non-polynomial）完全问题。由于精确的依赖分析代价非常大，因而编译器只好去寻求一些能够有效实现的保守分析办法。
传统编译器通常依靠两种依赖测试方法来检查数组引用之间的相关性，即 Banerjee测试（Banerjee 测试是以 Utpal Banerjee 博士的名字命名的。Utpal Banerjee 于 1979 年获得伊利诺伊大学香槟分校博士学位，曾任职于英特尔公司，是 ACM 和 IEEE 会士和加州大学欧文分校的客座教授。他为程序并行化领域做出了巨大的贡献，除了提出 Banerjee 测试以外，还提出了基于幺模变换的程序自动并行化理论。）和 GCD 测试。
1.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 fifission): 它把不同语句的同一个循环下标映射到不同的循环下标。
(7) 循环偏移 (loop shifting): 把一个动态语句实例偏移固定多个循环迭代。
在上述七种变换中，前三种都是幺模变换。一个幺模变换可以用一个幺模系数矩阵来表示。幺模矩阵是一个方阵，其行列式为 ±1。用于循环变换的幺模矩阵还有一个额外的特性就是它的所有元素均为整数。幺模矩阵的另一个重要性质是，幺模矩阵的乘积和逆矩阵仍然是幺模矩阵。幺模转换的重要性在于它把一个 N 维迭代空间映射到另一个 N 维的多面体，并且两个空间的迭代之间具有一一对应关系。
以幺模变换为基础实施循环的工作在 21 世纪初就有比较成熟的研究，这个理论把循环的互换、反转和倾斜都使用变换矩阵来表示，其目的是使循环嵌套中并行化的程度或者数据局部性的程度达到最高，这些变换对并行机器上的存储层次结构也能有效的支持。
幺模变换可以描述任何基于循环交换、循环倾斜和循环反转构成的复杂转换。最终的变换矩阵可以将各种基本的循环变换矩阵相乘即可。而基于幺模变换矩阵的循环优化，本质上是在给定一组调度约束的条件下，求出最大的目标函数。
可以用一个 N × N 的方阵来表示将一个原始 N 层循环
转换为
的循环交换，方阵的每个行向量代表一个循环，对于第 i 层循环来说，只有第 i 个元素为 1，其余元素均为 0。
因此，原始循环对应 N × N 的单位矩阵，而变换后的循环对应变换矩阵。一个合法的循环交换必须维持原始循环的依赖关系。要实现第 i 层循环和第 j 层循环的循环交换，只需要交换原始矩阵的第 i 行和第 j 行即可。图 1.6 所示为 N = 2 时的循环交换示例，在这个循环中，每个循环迭代之间都不存在依赖关系，所有循环迭代都可以并行执行。
对于图 1.6 所示的循环交换示例，循环迭代之间并不存在依赖关系，图中箭头仅用于表示不同迭代之间的执行顺序。图中每个坐标轴表示一层循环，每个圆点都代表一次循环迭代，对应的各层循环的循环变量的坐标构成的迭代向量。
与循环交换类似，可以用一个 N×N 的方阵来表示循环反转。将一个原始 N 层循环
的第 i 层循环做循环反转，只需要将原始循环对应的 N × N 单位矩阵的第 i 行的对角元素取相反数即可。同样，一个合法的循环反转必须维持原始循环的依赖有关系。在完成循环反转之后，动态语句实例中对循环变量的引用也需要同步更新。图 1.7 所示为 N = 2 时的循环反转示例。
对于第 j 层循环相对于第 i (j > i) 层循环的循环倾斜变换，实际上是在对迭代空间进行坐标变换。为了得到基础循环倾斜变换的变换矩阵，只需要将 N × N 的单位矩阵的第 j 行的第 i 列置成1 即可，最终得到的变换矩阵实际上是一个下三角矩阵。对于倾斜因子为 f 的通用循环循环倾斜变换，只需要将 N × N 的单位矩阵的第 j 行的第 i 列置成 f 即可。通用的循环倾斜变换也可以看成是循环延展变换和基础循环倾斜变换的组合。图 1.8 所示为 N = 2 时的循环倾斜示例。
幺模变换只能用于完美嵌套循环，而且只能对循环嵌套中的所有语句和所有循环迭代做同样的变换，因此无法实现诸如循环延展、循环合并、循环分布以及循环偏移等重要的基础仿射变换，也无法实现诸如循环分块、循环分段 (loop strip-minging) 和循环展开压紧等近似仿射变换。这种局限性主要源自其基于矩阵的变换表示。
与之相比，基于多面体模型的循环变换更加一般化。它基于更加一般化的关系运算（矩阵运算只是各种关系运算中的一种），可以表示各种各样的变换形式，使用约束也更少。它不仅可以用于描述任意的循环嵌套，而且每个语句都可以有自己独立的映射关系，因而可以作的转换更加丰富。
表1.2给出了上述七种基础仿射变换对应的多面体调度表示。其中，循环分布和循环合并变换中的常数0 和 1 是为了维持原始循环的语义顺序而引入的常量维度。我们将在第4详细介绍多面体模型中如何实现这些基础循环变换。
1.3.3 并行性优化
多面体中的调度是近似仿射调度，它是由循环迭代向量与全局符号的近似仿射表达式构成的映射关系。而调度生成的过程就是任务映射、任务划分、数据局部性和任务并行性优化的时机。调度的生成，本质上可以看成是对原始迭代空间和数据空间进行坐标变换。
并行性粒度与具体的应用程序和硬件紧密相关。一般情况下，在超标量硬件上可以开发指令级并行性，在向量处理器上可以开发指令级并行性和数级并行性，而在多核处理器上则可以同时开发指令级并行性、数据级并行性和线程级并行性。实现循环并行化的目的是使可以并行化的循环迭代数量达到最大化。对于相当性可以用相关距离来表示的深度为 N 的循环来说，不论是细粒度或粗粒度计算，可以开发的并行度至少为 N − 1。
为了优化循环的并行性，多面体模型可以把无依赖的循环交换到内层循环以便于实现循环向量化和循环并行化是两个互相冲突的优化目标。将便于实现向量化的循环交换到内层循环，可以保证程序中对数组元素的连续访问能够命中高速缓存；而将便于实现并行化的循环交换到外层循环，可以降低映射到不同处理器上的并行任务之间的同步和通信开销。
确定仿射调度，使得数据局部性、并行度等指标中的一个或多个达到最优, 这也是多面体模型需要重点解决的问题。我们将在第5章介绍循环并行化的主要方法。
1.3.4 任务映射
任务映射反映了循环和处理器空间之间的映射关系，在多面体的世界中也可以使用映射关系来表示。计算划分
是一个将语句 S 的动态实例映射到一个整数向量的仿射函数，这个整数向量表示虚拟处理器编号。 必须满足循环约束和数据依赖关系。类似地，数据映射
将每个数组元素映射到一个虚拟处理器编号。而计算 和 的过程实际上是一个优化问题。类似地，还可以定义一个仿射时间变换
表示语句 S 到执行时间的映射。
线性规划方法主要用于求解线性函数在线性等式或不等式约束下最大值或最小值。具体到循环优化问题，整个算法的输出是一系列仿射函数，这些仿射函数定义了每个处理器在哪个时刻执行哪个循环迭代。算法利用仿射函数来描述原始迭代空间中的循环迭代实例与处理器迭代空间之间的映射关系，还利用仿射函数来描述原始迭代空间中不同迭代的执行顺序。
任务映射还需要考虑数据局部性和同步开销，我们将在第5章介绍基于多面体模型的任务映射方法。
1.3.5 局部性优化
可以结合(1–1)和(1–4)进行访存依赖分析和数据局部性优化。数据依赖和数据局部性具有紧密的关联，但又不完全相同。考虑两个读取同一位置的循环迭代，二者存在数据局部性，但是并不存在数据依赖。
迭代空间相当于仿射访问函数的定义域，对依赖的分析相当于是在定义域中找出所有的访问同一个位置的循环迭代。如果两个访问同一位置的循环迭代，其中至少有一个是写操作，那么这两个循环迭代之间就是有数据依赖的。最终可以实现对于没有依赖的循环迭代和数据访问调整访问顺序，对于存在数据局部性的情况调整访问顺序从而达到利用数据局部性的目的。
循环分块可以降低同步开销并改进循环的数据局部性, 它将一个深度为 N 的循环嵌套映射到深度为 2N 的循环嵌套，其中 N 个内层循环只有少量的固定迭代。循环分段和循环分块类似，它只把一个循环嵌套结构中的一部分循环分解开，每个循环分解成两个循环，这么做的好处是一个多维数组被分段访问，从而获得较好的缓存利用率。
1.3.6 代码生成
通过对多面体进行变换可以实现并行性和局部性的挖掘，而在确定了调度策略之后，就可以按照调度确定的顺序生成代码了。代码生成通常涉及从一种描述到另一种称之为中间形式描述的转换。
转换的另一种情况是源到源变换（有时称为预编译器），实现程序从一种高级语言转换为另一种高级语言的转换，在这之后再利用目标机器的第二语言编译器进行编译。
根据变换后的迭代空间和调度生成代码，只需要在确定了循环的嵌套层次关系后，从最内层循环开始，不断利用 Fourier-Motzkin 消去法得到每个循环维度的上界和下界。Fourier-Motzkin 消去法是一种求解线性规划问题的常用方法，每运用一次 Fourier-Motzkin 消去法，多面体就会减少一个维度。而循环体代码而可以利用仿射函数变换矩阵确定下标表达式。
我们还要常常对控制流命令连接的基本程序块进行优化以获得较高的并行性。不同类型计算硬件的并行代码生成也是很不一样的。
作者简介
赵捷，2009年于清华大学获得工学学士学位，2018年于法国巴黎高等师范学校获得工学博士学位，现就职于数学工程与先进计算国家重点实验室。赵捷博士长期从事编译器高级优化和代码生成方面的研究，目前主要从事深度学习编译器的研究。
李宝亮，2009年于清华大学获工学学士学位，2014年赴加拿大麦吉尔大学交流访问，2015年于国防科学技术大学获工学博士学位。李宝亮博士长期从事体系结构性能分析优化方面的研究，目前主要从事深度学习专用加速芯片的研制和相关系统软件和编程语言的开发。
其他人都在看
欢迎Star、试用OneFlow最新版本：https://github.com/Oneflow-Inc/oneflow/
