开购物网站需要多少钱,外国域名注册网站,锦州网站建设品牌好,传媒公司网站源码php4.1 适配体系结构特征的关键技术
由于高级语言隐藏了底层硬件体系结构的大量细节#xff0c;如果不经过优化直接将高级程序设计语言编写的程序部署在底层硬件上#xff0c;往往无法充分利用底层硬件体系结构的处理能力。
算子融合不仅可以提…4.1 适配体系结构特征的关键技术
由于高级语言隐藏了底层硬件体系结构的大量细节如果不经过优化直接将高级程序设计语言编写的程序部署在底层硬件上往往无法充分利用底层硬件体系结构的处理能力。
算子融合不仅可以提高计算密度还可以避免相邻算子之间通过GPU设备内存通信引入的数据访问开销。
循环变换和不同循环变换之间的组合是实现面向底层硬件体系结构的重要优化手段。本章将基于多面体模型详细介绍优化编译器实现循环变换及不同循环变换之间组合的方式并介绍各种循环变换的应用场景以及一些循环变换之间的关系。
4.2 预处理
只要维持程序的循环携带依赖那么循环变换总是有效的。在开始分析依赖关系之前优化编译器应该提供一些能够对循环嵌套实现预处理的机制。一方面预处理能够简化依赖测试或精确依赖分析的过程另一方面预处理也能够消除一些复杂的循环携带依赖为实现更多的循环变换创造环境。
4.2.1 循环正规化
循环正规化使得循环嵌套中每个循环下界从0开始运行到某个确定的上界并且循环的步长为1.同时使用新的循环索引变量替换的仿射函数表达式区替换原循环变量在循环内的所有引用。即循环的下界为0上界为(U-L)/r步长为1,。原循环索引变量为i之后为r*i L。注意r应该是一个具体的常数值而不是符号常亮否则难以通过静态分析来判定依赖是否存在。尽管可能通过引入谓词条件的方式将非仿射表达式转换为仿射表达式的形式但这种向上近似的方法往往会导致冗余的循环跌打程序的语义则通过引入的谓词条件来保证。
4.2.2 死代码删除
在实际应用中可能会存在一些不会被其他有用的语句引用结果的语句即程序的死代码。有用的语句是指用于输出程序结果的代码或者那些再被优化的程序中仍然需要执行的代码。
死代码删除可以在计算出程序的数据流信息之后利用向下暴露集与程序迭代空间以及依赖关系之间的基本操作来完成其基本思想是先根据近似数据流分析方法计算出被优化的程序片段的向下暴露集并依此计算出所有向下暴露集中语句实例的流依赖源点的集合将二者集合求并得到一个新的集合向这些变量写入数据的语句实例都不会是死代码重复该过程直到求并之后的集合不再发生变化。由于死代码可以与其他语句产生数据流关系因此将所有死代码语句导致的依赖从数据流关系和各种依赖关系中删除减少编译器对程序实施循环变换的约束。
4.2.3 别名分析
别名分析阻碍优化编译器分析依赖关系最关键的因素之一特别是对以多面体模型为基础的优化编译器而言因为多面体没有办法判定不同内存地址单元之间的别名关系也就无法确定语句实例之间是否有依赖。
大多数基于多面体模型的优化编译器只是简单地认为数组之间不再存在别名关系。
一种常用的方法是在程序设计语言级别引入辅助别名分析或者消除别名的语言特性。例如C语言提供的restrict关键字。另一种方式是优化编译器在实施程序转换时对可能产生别名关系的数组进行标记并依靠运行时技术确定别名关系是否存在。
4.2.4 迭代空间分裂
为了减少二维stencil中空间维度之间的长距离依赖在每个维度上的距离向量分量可以采用一种称为迭代空间分裂的方法。
对原迭代空间中非依赖方向进行切割同一时间维度上的子空间可以通过折叠将原来的依赖转换。迭代空间分裂为子空间的折叠创造了条件但子空间的折叠却需要依靠多面体模型对循环迭代空间进行一维或多维反向的循环偏移或反转变换才能获得有利于循环变换的迭代空间。
4.3 多面体模型中的循环变换
与传统的并行编译器所采用的幺模矩阵相比多面体模型具备以下几个特点 1. 应用范围广。幺模矩阵只能处理完美嵌套循环而多面体模型对输入程序的约束更少不仅处理完美循环嵌套而且对非完美循环也支持。 2. 表示能力强。幺模矩阵只能处理循环变换、切斜和反转等变换。而多面体还能处理循环分块、合并和分布等在内的几乎所有循环变换。 3. 优化空间大。多面体模型能处理更多的循环变换的组合。
除了面向通用体系结构的源到源优化工具Pluto和PPCG外GCC、LLVM、Opn64和IBM XL编译器都集成了多面体优化相关的模块。也在深度神经网络和自动优化和部署受到了广泛的关注MLIR, TensorComprehensionsTiramisu, PlaidML/Stripe和Diesel等深度学习编译器中发挥了不可替代的作用。
4.3.1 循环变换分类
根据循环变换对程序特征的改变分为以下几种 1. 改变程序算法设计是通过对算法的调整来降低时间或空间复杂度的。例如在不考虑稳定性的前提下可以使用快排代替冒泡排序。 2. 改变程序计算顺序往往是为了提升程序的并行性或数据的局部性。例如循环合并就是为了缩短相邻循环嵌套访问数据之间的“生产-消费”距离、提升数据的时间局部性而实现的循环变换。 3. 仅改变循环结构、但不改变程序计算顺序主要是为了生成对目标体系结构友好的代码而设计或实现的。例如循环展开就是一种为了充分利用细粒度指令流水并行而设计的循环变换。 4. 改变程序数据布局和被访问内存地址单元充分利用目标体系结构上的存储层次结构。
编译器很难实现第一种循环变换基于多面体的编译器能够自动实现后三种的循环变换及其组合。后三种循环变换几乎都需要考虑目标体系结构的特征因此如何在多面体模型中实现对目标体系结构的抽象是实现循环变换的关键。
4.3.2 循环变换的复杂性
基于多面体模型的循环变化将循环的迭代空间表示成空间多面体并通过多面体上的几何操作达到分析和优化程序的目的。多面体模型利用迭代空间、访存映射、依赖关系和调度表示程序及其语义。其中调度表示语句实例与其对应的字典序之间的仿射函数多面体模型实现循环变换的方法就是在满足依赖关系的前提下将一种调度转换成另一种调度的过程该过程也被称为调度变换。多面体模型首先将循环嵌套内的语句实例构成的集合表示为空间多面体的形式。从几何角度来看多面体模型上的调度变换实质上就是多维空间几何的变基过程。
// CPU 一段可并行循环
for(t 0; t T; t1)for(i 0; i N; i1)A[t1][i] 0.25 * (A[t][i1] -2*A[t][i] A[t][i-1]);// GPU 二段可并行循环
for(t 0; t T; t1)for(it 0; it (N-2)/4; it1)for(ip max(1, 4*ip); ip min(N-1, 4*ip4); ip1)A[t1][ip] 0.25 * (A[t][ip1] -2*A[t][ip] A[t][ip-1]);
只考虑并行性的前提下循环变换的代码在硬件上的部署似乎看起来没有那么麻烦。然而一个无法忽视的问题是现代体系结构上的存储层次结构。尽管一些底层的编译技术已经充分考虑到如寄存器分配、指令流水线并行等细粒度策略但是面向高速缓存的数据局部性优化却是循环变换不得不考虑的问题。
在基于多面体的编译器中代码生成阶段的输入是表示程序迭代空间的集合和表示程序调度的映射。其中表示程序调度的映射必须是从语句实例集合到字典序之间的仿射函数。
对迭代空间进行粗暴地矩形划分是非法的因为任意两个水平相邻的分块之间存在依赖环而多面体模型的代码生成器限制循环只能延(t,i)坐标轴方向切割。细看之后发现沿i轴获得循环分块是合法的。接下来解决t轴切割。t轴的切割方向与程序中的两个依赖即左上和右上方向的依赖都相交。如果沿着两个依赖的其中一个方向进行切割并构造新的分块形状。不难发现这两种分块形状都不会导致任意方向相邻两个分块之间的依赖环。
要构造上述分块i轴保持不变另外一个坐标轴的指向左上或右上的依赖方向平行需要编译器自动实现对循环分块友好的循环变换及这些循环变换的不同组合这对编译器很重要也很困难。
循环变换的目的有时候是互相冲突的以程序并行性和数据局部性为例上述分块没有实现最大化程序并行性的目的尽管提高了数据局部性。
带有OpenMP编译指示的代码在运行时有同步开销编译指示在循环嵌套的层数越靠近同步的开销就越小。循环分块增大了同步开销因此损失了程序并行性。
4.3.3 Pluto调度算法
Pluto算法以自动实现循环分块为目的在实施循环分块之前试图寻找能够最大化循环分块可能性的循环变化组合。
Pluto调度算法的核心是兼顾程序并行性和数据局部性的前提下利用一种定义良好的代价模型自动确定有利于实现循环分块的顺序关系通过计算原始程序的顺序关系和新的顺序关系之间的映射函数自动实现循环分块友好的循环变换组合。
4.4 仿射循环变换
任何能用多维仿射变换表示的循环变换都成为仿射循环变换。Pluto调度算法先进行仿射变换然后在循环分块。
4.4.1 循环交换interchange
向量化使用向量寄存器并行化无依赖
循环交换将完美嵌套循环的两个循环顺序进行交换通过这种技术既可以将可向量化的循环移动到循环嵌套的最内层以提高程序的向量化效果也可以将可并行化的循环移动到循环嵌套最外层以增加程序的并行粒度减少同步开销。
Pluto调度算法的代价模型是面向多核架构设计的所以Pluto算法在实现循环交换时更倾向于将可并行化的循环移动到循环嵌套的外层以提高并行的粒度并降低同步开销。
4.4.2 循环反转reversal
循环反转是一种将循环嵌套某一层循环的迭代方向进行反转并将循环步长设置为原始值的相反数。
for (int i 1; i M; i)for (int j 1; j N; j)for (int k 0; k K - 1; k)A[i][j][k] A[i][j-1][k1] A[i-1][j][k1];// reverse loop
for (int k K-2; k 0; k--)#pragema omp parallel forfor (int i 1; i M; i)for (int j 1; j N; j)A[i][j][-k] A[i][j-1][-k1] A[i-1][j][-k1];
4.4.3 循环延展scaling
循环延展通过延展循环索引变量的取值范围和循环步长的技术目的在于将程序中不规则的依赖转换成灾迭代空间上全局一致的依赖从而使程序迭代之间的依赖距离向量分量能够用整数表示依此来为其他循环变换创造机会。
for (int i 0; i N; i)f[i] fin[i];
for (int i 0; i N/2; i)g[i] f[2*i1] * f[2*i-1];
for (int i 0; i N; i)h[i] g[i/21] * g[i/2];
将g[i]循环以延展为2展开所有循环迭代之间的依赖在整个迭代空间上全局一致且3个循环还可以合并。
4.4.4 循环倾斜skewing
循环倾斜通过改变完美循环嵌套对应迭代空间形状的循环变换技术但并不会改变迭代之间的执行顺序。例如(t, i) -- (t, 2ti)。
for(t 0; t T; t1)for(i 0; i N; i1)A[t1][i] 0.25 * (A[t][i1] -2*A[t][i] A[t][i-1]);
4.4.5 循环合并fussion
循环合并是一种通过将多个循环嵌套融合在一起形成一个统一的迭代空间从而便于编译器实现其他优化的循环变换技术。循环合并本身是一个非常复杂的过程合并后的循环可能会失去并行性或无法实现循环分块因为可能产生的依赖问题。循环合并通过循环的融合缩短程序数据之间的“生产--使用”距离从而提高数据的局部性。
4.4.6 循环分裂fission
循环分裂是一种将一个循环嵌套在分裂成多个循环嵌套的循环变换技术。循环分裂通过将循环嵌套某层循环上的循环携带依赖转换为循环无关依赖来提升循环的并行性。
4.5 近似仿射变换
在仿射循环变换中用于循环变换的表达式只包含加减法乘法以及这些操作的组合并且表示循环变换的仿射变换中不会涉及存在量词。在一些循环变换中除法、取模以及存在量词是不可避免的所以需要借助近似仿射表达式来表示循环变换。
4.5.1 循环分块blocking
循环分块将循环嵌套空间划分成不同的分块并改变循环迭代执行顺序的循环变换技术。如果在未经循环倾斜的原始迭代空间上能够实现正确的循环分块那么就称为矩形分块。在经过一些仿射循环变换的组合之后才能进行循环分块所得到形状可能是平行四边形后者其他形状。
4.5.2 循环分段strip-mining
循环分段将一个循环的迭代空间分成多个子集并将每个子集作为一个调度单元进行执行的循环变换技术。在多核架构中循环分段的实现往往是隐式地分配单个循环迭代空间的不同子集给不同线程。但是在多级并行硬件抽象的体系结构例如GPU上的线程块和线程循环分段必须显式执行。
由编译器显式实现的循环分段往往会带来额外的循环执行开销因为引入了新的循环边界判断条件。除非能提升程序的并行性否则并不鼓励在优化编译器中显示地实现循环分段。循环分段也可看做循环分块在单层循环上的特殊情况。
4.5.3 循环展开压紧unroll and jam
循环展开压紧将某两层的外层循环展开后再将内层循环进行合并的循环变换技术压紧效果在于减少了向量寄存器取数操作的次数和展开效果在于增加不同计算功能部件之间的指令流水线并行效率。
4.6 代码生成过程的循环变换
代码生成过程中的循环变换包括分块分离、循环展开和循环剥离。
4.6.1 分块分离tile isolation
在迭代空间边界上由于与迭代空间相交而被舍去部分区域的分块被称为半块其他没有被舍去的分块为整块。分块分离式一种将半块和整块分离以消除循环嵌套中的重叠边界条件限定条件min、max。
分开分离通过消除生成代码中循环边界的min和max等限定边界操作使得生成的代码能够对一些领域特定的加速芯片友好。
4.6.2 循环展开unrolling
循环展开是一种通过展开循环迭代来降低循环条件分支开销的循环变换技术提高指令间流水并行并降低用于循环边界判定的控制开销还为向量化创造条件但注意寄存器溢出。
4.6.3 其他循环优化
循环剥离peeling将循环某些迭代从循环主体中剥离出来的循环变换技术。循环中有时只有部分迭代会产生依赖当这些循环迭代是循环的前几个或后几个迭代的时候优化编译器就可以通过循环剥离的方法将原来循环转换为两部分。
循环判断外提unswitching将循环内与循环索引无关的条件谓词外提到循环外的技术降低分支开销减少代码量。
4.7 循环压紧
循环压紧coalescing将多层循环嵌套压缩成单层循环的技术。
