1.2　编译器面临的挑战

前面从体系结构的角度介绍了提升硬件性能的三类主要方法，即发掘并行性、优化存储层次和设计领域专用架构。但是，体系结构设计仅仅是确定了软件的执行平台，而在确定的执行平台上如何优化程序，则是程序员和编译器的职责。为了充分利用硬件的处理能力，软件开发人员和编译器都需要充分了解底层体系结构的特点。对于程序员来说，编写正确而且高效的串行程序是非常困难的，编写正确而且高效的并行程序则更加困难，其难度会随着并行粒度的降低而增长。为了减轻程序员的工作，编译器需要担起性能优化的重担。特别地，随着非金字塔形存储结构在各个领域专用架构（例如，人工智能芯片、网络处理器和数据处理器）的普遍应用，以及各种定制化加速器部件的持续集成，程序员手工编写高性能程序变得越来越困难，而编译器则成为上层应用与体系结构之间一个至关重要的工具。

狭义的程序优化是指尽可能地发掘程序的并行性和硬件的计算能力，使得代码在具体硬件上的执行速度达到最高。而广义上的程序优化是指，编译器为了改进应用程序的某项技术指标（例如，执行时间、代码尺寸和内存占用），在不改变程序语义的前提下，修改其内部数据结构或所生成代码的过程。优化可以是架构无关的，也可以是架构相关的。为了把程序员使用高级语言编写的与架构无关的程序转换为可以在具体硬件上高效执行的机器指令，编译器需要在程序分析、代码优化和代码生成这三个核心步骤持续引入各种新的技术和方法。常规的标量优化技术包括循环不变量外提、常量传播、公共表达式删除、运算强度削弱、循环展开、软件流水、指令调度等。

并行性、局部性和领域专用设计为编译优化带来了巨大的挑战，这些挑战在以深度学习为优化目标的背景下同样适用，并且如何在这些优化目标之间进行权衡取舍的问题也显得日益尖锐。而这三个问题都与循环有着紧密的联系，因为大多数的计算机程序几乎将所有运行时间都花费在循环内，因此为循环优化付出的努力往往能得到最高的回报。但是，对应用程序的优化往往需要程序员和编译器的共同努力。例如，程序员需要对循环嵌套结构进行拆分和重写等操作，来帮助编译器更好地识别和优化循环。

1.2.1　并行性发掘

并行性发掘可以通过软件静态完成，也可以通过硬件动态地进行。完全依赖硬件管理其并行性的机器称为超标量处理器，而完全依赖编译器来管理其并发性的机器称为超长指令字。在一些成本或者功耗敏感的嵌入式应用场景（例如物联网）中，通常依赖编译器来发掘并行性，而在桌面计算、服务器和云计算场景中，虽然硬件实现了强大的调度机制，也需要在编译器的配合下才能充分发挥硬件的指令级并行性能力。

编译器开发指令级并行性的基本思路是结合硬件的结构特点，通过指令调度的方法来提高硬件资源的利用率，常用的提高指令级并行性的方法如表1.1所示。

流水线的结构冲突、数据依赖和控制依赖会在处理器流水线中引入空泡。为了避免因流水线空泡导致的性能损失，通常需要编译器对指令序列进行静态调度。例如，静态分析预测可以结合硬件的推测执行功能减少因控制流引入的流水线空泡，延迟槽调度则是用一些与控制流无关的指令来填充分支跳转指令的延迟槽，常规的静态指令调度则是将一些没有数据依赖的指令安排在一起，以避免因数据依赖引入的流水线空泡。

指令级并行在过去数十年中已经被深度发掘，并成为LLVM、GCC等传统编译器的基础功能。编译器支持指令级并行的基本方法是在基本块内实现简单的指令调度。然而，在一个基本块级别开发并行性的收益并不大。为了进一步发掘并行性，必须着力于开发更高层级的并行。

本书中重点介绍的多面体模型主要用于开发单指令多数据并行性和线程级并行性，而对请求级并行的开发则不在本书的讨论范围。对单指令多数据并行和线程级并行的优化通常是以循环为研究对象的，因此也称为循环级优化。循环级优化技术尝试从多个循环迭代中寻找并行性，通过重复执行多个循环体中的代码来提高程序的并行性。循环级并行优化可以显著提升程序的整体性能，因为程序中运行时间较长的代码片段通常是具有很多次迭代的循环。

循环级优化的首要目标是充分发挥硬件提供的计算能力，以减少延迟（尽可能快地完成计算任务）或者提高吞吐率（在相同的时间内完成更多的任务）。循环级优化的基础方法包括循环展开、软流水、并行化和向量化。其中，循环展开是通过复制循环指令的方式来避免循环的控制开销；软流水主要是对原始循环进行重新组合，将无依赖的访存和计算指令组合在一次循环迭代中；向量化和并行化的目的是要对处理大量数据或者可划分后能并行执行的程序改善性能。

循环向量化是编译器将循环中的标量运算转换为向量运算的过程，最终生成的向量运算指令会在同一个硬件单元上执行。并行化则是把循环拆分成多个可以并行执行的子任务，在不同的硬件单元上并行执行每个子任务。循环并行化需要将循环进行划分，并让多个处理器分别执行其中的一部分。但是为了保证性能，还必须把处理器之间的通信量减少到最小。通信量实际上与数据局部性紧密相关，对于处理器经常访问的数据，在任务或数据划分时应当让它离处理器更近，否则会引入大量的通信和同步操作。

然而，循环向量化和循环并行化通常是两个互相冲突的优化目标，因为循环并行化通常在外层循环进行，而循环向量化则必须在内层循环进行。自动并行化和自动向量化是现代编译器面临的主要困难，原因是编译器很难有效地收集和分析向量化或者并行化所需要的数据相关性和控制相关性等信息。由于编译器在自动向量化和自动并行化方面遇到了困难，软件开发人员不得不自己发掘应用的并行性，并且处理共享资源的访问冲突，这就要求编译器和编译语言能够提供一种易于描述并行性的编程模型。

与此同时，在以大量的矩阵乘法和卷积运算为中心的深度神经网络中，循环嵌套的维度也随着增加，不同运算循环嵌套结构之间可能存在较大差异。在开发外层循环的并行化和内层循环的向量化时，优化编译器的任务不再是简单地识别某一个或多个循环维度上的并行性，而是要在一个循环嵌套内多个循环维度上的不同并行性内寻找到能够最大限度地提升程序性能的并行执行方式，这就需要优化编译器在原有的识别并行性的基础上，还要具备同时组合多种循环变换的能力。

1.2.2　局部性发掘

存储器的容量越大，则访问速度越慢。幸好程序访问的数据通常具有空间局部性和时间局部性。时间局部性通常是指某个数据被访问后，常常会在较近的时间再次被访问；空间局部性则是指某个数据被访问以后，常常会在较近的时间再访问与其相邻的数据。可以在内存之上设置多个存储层级来利用数据的局部性改进程序性能。性能调优一个非常重要的前提就是理解计算机系统的存储层次，并且结合硬件的存储层次和计算特征，进行特定的访存优化从而平衡访存和计算。

图1.2所示的卷积过程可以通过循环变换转换成不同的实现方式和数据、时间和空间局部性特征，而不同的实现在不同的硬件上性能差异也非常大。我们以图1.3所示的矩阵与向量乘法运算为例，当M<<N（M远小于N）时，每计算一个值b[col]，会导致列向量x和矩阵A被不断地换入和换出，严重影响性能。经过分析可以发现，在整个计算过程中，矩阵A中的每个元素只会被使用一次。因此，最理想的情况下，A的数据元素只需要被加载到Cache一次，而列向量x则会被反复使用M次。Cache优化的最终目标就是确保矩阵A的数据元素只被加载到Cache一次，x的元素只被加载一次。因此，可以将图1.3所示的源代码转换为图1.6所示的形式。

访存局部性优化比较成熟的手段是循环分块（loop tiling）和循环融合（loop fusion）。循环分块的基本思想是通过将大块的循环迭代拆解成若干较小的循环迭代块，减少一个内存单元的数据重用周期，这种重用周期既可以是时间上的也可以是空间上的。循环融合则是将多个具有“生产–消费”关系的循环合并在一起，从而缩短了每个中间数据的重用周期，避免中间结果被换出高速缓存。循环分块和循环融合都可以确保某个内存地址单元被加载到Cache以后，该内存地址单元会尽量保留在Cache中，这样就可以达到减少片外访存开销的目的。然而，循环分块和循环融合也是两个相互冲突的优化目标，因为循环融合会导致循环分块的约束增加，灵活性变差。

特别地，循环分块和循环融合在当前的领域专用架构上扮演着至关重要的作用。与传统多核处理器的线程级并行方式不同，基于领域专用架构的加速部件往往以类似协处理器的方式与CPU进行协同工作，这就要求在加速器上完成的计算任务所需的数据在计算任务执行之前都已经在加速器的缓存上准备就绪。而且，为了减少因加速部件和CPU之间的数据传递导致的访存开销，优化编译器应该尽可能地减少启动加速部件上计算任务的频次。除此之外，以Google TPU为代表的领域专用芯片上的存储层次结构打破了金字塔形存储结构的特征，使得这些加速部件上的数据流管理更加复杂，优化编译器在将数据传输到加速部件的缓存上之后，还需要通过综合循环分块和循环融合，更系统地管理特定计算功能部件之间的数据流向。

1.2.3　编程模型和抽象层次

计算机程序的一个重要特征是通过编程模型构建体系结构和应用算法之间的接口和桥梁。编程模型的设计需要考虑具体的硬件机器模型，在可编程性和程序性能之间找到平衡点。编程模型使得体系结构与硬件无关，应用也独立于体系结构。但是，编程模型也隐藏了具体的硬件细节。如何向程序员展示领域相关的硬件特性，如何暴露并行性和局部性，如何实现跨平台的兼容性，如何简化领域相关的编程，是编译器需要重点解决的问题。

传统系统结构的并行性通常包括超结点之间的并行性、超结点内多个处理器之间的并行性、处理器内多个处理器核心之间的并行性、处理器核心内多个并行功能单元之间的并行性。超结点、多核处理器、处理器核心、功能单元构成现在计算系统的层次化组织结构。在不同的层次，往往对应不同的开发并行性的方法和编程模型。例如，在多个超结点之间可以利用消息传递的并行编程模型（例如Message Passing Interface，即MPI）来发掘超结点之间的并行性，在超结点内的多个处理器之间往往通常共享内存的多进程编程方式发掘并行性，在单个处理器核心内则是通过共享内存编程模型（例如OpenMP）实现多线程之间的并行性，在单个处理器核心内则可以利用SIMD/SIMT编程模型来发掘多个并行功能单元之间的并行性。

领域相关设计通常是在传统体系结构的基础上，增加领域相关的硬件特性，在复用现有软硬件生态的基础上实现对特定应用的高效处理。而编译器则需要与硬件密切配合，向程序员暴露更多能够充分利用体系结构的特点进行程序性能优化的机会。在编程模型设计时需要平衡通用性和领域专用性之间的关系，通用性可以方便程序的功能和性能的自由迁移，而专用性则可以确保特定应用在特定硬件上的性能。通常情况下，编程模型的抽象层次越高，对底层体系结构信息的隐藏就会越多，但是对特定领域的性能就越不易保证。

随着编程模型和体系结构抽象层次的鸿沟越来越大，采用一层编译抽象的方式很难充分提升程序的性能。以深度学习的应用为例，一个深度神经网络表示成计算图的形式，计算图结点之间的并行性和局部性需要在一种编译抽象层次上进行优化；在将计算图划分成小的区间或子图后，又需要在另外一种编译抽象层次上进行优化。这种编译阶段的多级抽象[50]也逐渐替代了传统单一编译抽象的方式。在这种多级编译抽象层次上，如何设计和实现通用的编译技术路线也是当前优化编译器面临的重要挑战。