下载掌阅APP，畅读海量书库
立即打开
高级程序设计语言作为程序员与计算机之间信息交互的界面，隐藏了底层软件和硬件的细节，为程序员在计算机上实现特定的计算任务提供了便捷的编程接口。高级程序设计语言在向程序员提供友好的编程体验的同时，也将应用程序在目标计算机上优化和部署的任务转移到了编译器上。程序员在利用程序设计语言实现算法时所采用的基本结构包括顺序结构、分支结构和循环结构。其中，顺序结构表示程序中各个操作按照它们在程序中描述的依赖顺序执行，程序员也总是期望计算机能够按照预先设定的依赖顺序执行各个操作，优化编译器不会改变顺序结构中操作之间的依赖，但是可以改变无依赖的操作之间的执行顺序。分支结构和循环结构则是通过条件判定选择或反复执行一段代码来完成算法设计的步骤，优化编译器可以在确保证依赖关系不被破坏的前提下，通过改变这些控制结构中操作的执行顺序来优化性能。
现代优化编译器在将程序员编写的应用程序转换为可执行的机器代码或者其他编程语言的代码时，不仅要充分利用目标计算机体系结构的存储层次结构，还要考虑多核/众核等并行硬件的特征，这种优化过程需要改变原始程序中操作之间的顺序。确保转换后的程序与原始程序的等价性，是编译器在实现自动优化时面临的一个重要挑战。传统的底层或细粒度编译优化技术往往集中在寄存器分配、指令调度和冗余消除等优化目标上，这些经典的编译优化技术已经被系统开发工程师熟练掌握。随着领域专用加速芯片的日益普及，现代优化编译器的优化重心已经逐渐从过去的底层或细粒度优化转向以循环嵌套为核心的上层或高级优化。
根据Flynn分类法 [31] ，计算机体系结构可以分为单指令流单数据流（SISD）、单指令流多数据流（SIMD）、多指令流单数据流（MISD）和多指令流多数据流（MIMD）四种类型。其中，SISD为串行计算机体系结构，MISD类型的并行计算机比较少见。现代计算机体系结构大多采用SIMD和MIMD的多数据流并行的方式来达到并行加速的目的。因此，要实现并行计算机体系结构上的自动优化，一个优化编译器必须能够寻找到有效的数据分解策略，以充分利用并行计算机体系结构上多数据流并行的特性。循环内的数组下标表达式通常是循环索引变量的函数，因此，优化编译器必须具备正确判断不同数组下标表达式是否相等的能力，并基于此判定循环的不同迭代之间是否能够进行数据分解。当循环的不同迭代引用相同的地址单元时，称这些迭代之间存在依赖。在优化编译器的静态分析阶段，判定不同循环迭代之间不存在依赖，是实现多数据流并行优化的基本前提。
本章的目的是详尽阐述数据依赖关系的定义和性质，以及如何判定数据依赖关系的方法。本章还将介绍依赖关系的几种分类方式，以及它们在优化编译器实现面向并行性和局部性的自动变换时发挥的作用，这些基本概念和分析方法为优化编译器的循环变换奠定了坚实的基础。最后，本章还将介绍数据流分析方法，以及数据流分析在循环嵌套优化过程中产生的影响和发挥的作用。