宋广辉(1997-), 男, 硕士生, 主要研究领域为高性能计算, 先进编译技术
郭绍忠(1964-), 女, 教授, CCF高级会员, 主要研究领域为高性能计算, 分布式处理
赵捷(1987-), 男, 讲师, CCF专业会员, 主要研究领域为先进编译技术
陶小涵(1996-), 男, 博士生, 主要研究领域为先进编译技术
李飞(1996-), 男, 硕士生, 主要研究领域为高性能计算
许瑾晨(1987-), 男, 讲师, 主要研究领域为高性能计算
混合精度在深度学习和精度调整与优化方面取得了许多进展, 广泛研究表明, 面向Stencil计算的混合精度优化也是一个很有挑战性的方向. 同时, 多面体模型在自动并行化领域取得的一系列研究成果表明, 该模型为循环嵌套提供很好的数学抽象, 可以在其基础上进行一系列的循环变换. 基于多面体编译技术设计并实现了一个面向Stencil计算的自动混合精度优化器, 通过在中间表示层进行迭代空间划分、数据流分析和调度树转换, 首次实现了源到源的面向Stencil计算的混合精度优化代码自动生成. 实验表明, 经过自动混合精度优化之后的代码, 在减少精度冗余的基础上能够充分发挥其并行潜力, 提升程序性能. 以高精度计算为基准, 在x86平台上最大加速比是1.76, 几何平均加速比是1.15; 在新一代国产申威平台上最大加速比是1.64, 几何平均加速比是1.20.
Mixed precision has made many advances in deep learning and precision tuning and optimization. Extensive research shows that mixed precision optimization for stencil computation is challenging. Moreover, the research achievements secured by the polyhedral model in the field of automatic parallelization indicate that the model provides a good mathematical abstraction for loop nesting, on the basis of which loop transformations can be performed. This study designs and implements an automatic mixed precision optimizer for Stencil computation on the basis of polyhedral compilation technology. By performing iterative domain partitioning, data flow analysis, and scheduling tree transformation on the intermediate representation layers, this study implements the source-to-source automatic generation of mixed precision codes for Stencil computation for the first time. The experiments demonstrate that the code after automatic mixed precision optimization can give full play to its parallelism potential and improve the performance of the program by reducing precision redundancy. With high-precision computing as the benchmark, the maximum speedup is 1.76, and the geometric average speedup is 1.15 on the x86 architecture; on the new-generation Sunway architecture, the maximum speedup is 1.64, and the geometric average speedup is 1.20.
Stencil计算是浮点计算应用中一种常见的循环嵌套运算模式, 也是加州大学伯克利分校并行计算实验室提出的7个计算主题之一[
Stencil计算中使用的浮点数一般遵循IEEE 754标准, 其中最经常使用的浮点类型是32位的单精度(float)和64位的双精度(double)[
现有的混合精度的研究核心都集中在有明显精度差别的变量声明、算子等层次上, 对于程序中的循环嵌套关注度很少, 但是Stencil计算的性能和误差热点一般是循环嵌套中的高精度计算, 其严重拖慢程序执行时间, 而如果是将其直接转换成低精度计算, 又会使误差大幅度提高. 因此, 针对Stencil计算中的循环嵌套, 在满足误差阈值的前提下利用混合精度技术提升程序性能成为一个难题.
为了解决这一难题, 本文基于多面体模型设计并实现了一个面向Stencil计算的自动混合精度优化器(automatic mixed precision optimizer for Stencil computations, AMPO-SC), 该优化器可以将C语言源程序中指定的循环嵌套区的Stencil计算代码自动转换成混合精度优化之后的代码. 本文的主要贡献如下.
(1) 提出了基于仿射约束表达式的迭代空间划分算法, 在多面体模型的指导下能够对任意Stencil计算中的循环嵌套进行划分, 给出了混合精度计算所需的相互分离的迭代空间.
(2) 将(1)与数据流分析和调度树转换结合在一起, 实现了一个面向Stencil计算的自动混合精度优化器, 即首次实现了源到源的面向Stencil计算的混合精度优化代码自动生成.
(3) 选取了Stencil计算10个典型的测试用例进行实验, 其结果表明, 本文所实现的面向Stencil计算的自动混合精度优化器能够自动生成混合精度优化之后的代码, 且可以充分挖掘Stencil计算中潜在的精度冗余和性能增长.
本文第1节介绍混合精度的研究现状. 第2节介绍本文研究的基础知识, 包括多面体模型和调度树. 第3节介绍面向Stencil计算的自动混合精度优化器的框架. 第4节详细介绍面向Stencil计算的自动混合精度优化器的核心算法和实现细节. 第5节分析本文所开展的实验及其结果. 第6节总结全文.
混合精度是一种在存在精度冗余的程序中同时使用高精度计算和低精度计算的程序优化手段. 目前混合精度的研究主要分为两种, 一种是算子级的混合精度, 典型的就是人工智能领域的混合精度训练, 另一种是变量级的混合精度, 典型的就是各种精度调整和分析工具, 根据其特点又可以分为静态分析工具和动态分析工具. 他们的核心都是通过一定的策略利用不同精度的变量和算子来实现混合精度优化, 在一定的误差阈值下尽可能地提升应用性能.
2018年, 百度与NVIDIA联合发表的论文[
人工智能应用的计算过程可以分为建模、训练和推理这3个过程, 其中建模是根据应用的特征建立合适的模型, 如果是语音识别、手写识别和文字识别之类的需要处理和预测时间序列中间隔和延迟非常长的重要事件的应用, 一般需要建立长短期记忆人工神经网络(long short-term memory, LSTM), 而如果是图像识别和人脸识别之类的需要具有表征学习(representation learning)能力并能够按其阶层结构对输入信息进行平移不变分类的应用, 一般需要建立卷积神经网络(convolutional neural network, CNN); 其次, 是用海量的数据信息来训练模型, 通过大量的训练来提升模型捕获输入数据中特征的能力, 具体而言就是在每次训练之后, 获取模拟的结果与真实结果之间的损失(loss), 然后通过一定的手段和策略调整模型中的参数再次训练, 如此循环往复, 直到损失满足实际应用需求为止; 最后, 便于用训练好的模型去求解现实中的特定问题, 以推理得到较好的计算结果, 这一过程与人类的思维过程十分类似, 因此称为推理.
因为人工神经网络的参数和中间结果绝大部分都是采用FP32进行存储和计算的, 当网络变得超级大时, 这部分的计算和访存将会成为程序的性能瓶颈, 大大降低程序的执行速度. 因此在对精度不太敏感的训练过程中降低浮点数精度, 比如使用半精度浮点数, 显然是提高计算速度, 降低存储开销的一个很直接的办法, 这便是混合精度训练的核心思想. 然而副作用也很显然, 如果直接降低浮点数的精度直观上必然导致模型训练精度的损失, 因此为了解决精度损失的问题, 混合精度训练还提出了权重备份和loss缩放等方法来规避这一问题. 同时为了提升混合精度训练在人工智能应用中的广度和深度, 目前主流的人工智能开发框架都实现了对自动混合精度训练(也被称为自动混合精度, automatic mixed precision, AMP)的支持.
浮点研究人员已经开发了很多精度分析和调整工具, 以便来测试、分析和改进他们的代码[
静态分析技术直接从源代码中提取相关信息并通过相关的理论计算来预测误差的最坏情况[
由于静态分析的局限性, 往往得出的精度分配方案比较保守, 不能有效地找到最佳方案, 故动态分析方法是更为常用的技术. 动态分析技术一般是在具有代表性的输入集上运行降低精度的版本和原始的较为精确的版本, 并比较两者的结果进而得到精度和性能较为权衡的精度分配方案. Kum等人提出的Autoscaler For C[
综上所述, 混合精度计算的相关工作都取得了很好的进展, 但是都不能解决具有循环嵌套运算模式的Stencil计算的精度和性能的权衡难题, 一方面是因为循环本身是没有明确的精度类型—循环的精度取决于循环中语句的计算精度和循环的迭代次数, 并且由于编译器可能会对精度进行自动提升, 语句实际的计算精度往往是隐含的. 另一方面, 在一个循环结构中, 往往又会包含另一个完整的循环结构(即循环嵌套), 因此, 循环嵌套中的计算顺序具有一定的复杂性, 外层循环体每执行一次, 内层循环都要整体循环一次. 再加上循环的嵌套方式和层数十分丰富多样, 这些都大大增加了对Stencil计算中的循环嵌套进行混合精度的复杂性. 因此本文拟基于混合精度的基本思想, 对用户程序中的Stencil计算开展自动混合精度优化工作.
本文的工作主要基于多面体模型和调度树, 下面就相关概念和基本知识予以介绍.
多面体模型(polyhedral model)[
多面体编译工具的一般编译流程如
基于多面体模型的一般编译流程
在程序自动并行化领域, 多面体模型不仅取得了很多突破性的成就, 还在Pluto编译工具[
多面体模型中的调度是一种用于表示程序执行顺序的中间表示(intermediate representation, IR)形式, 结合数据结构中“树”的一些特征, 我们不难发现, 多面体模型中使用的调度天然具有树的形式, 因为它特别适合处理循环和复合语句. 前人提出的通用调度表示形式, 例如Kelly等人提出的抽象表示形式[
一般而言, 调度树中可以包含
基于调度树, 可以很方便地对循环嵌套进行各种优化, 一方面是因为调度树这一中间表示形式可以通过一定的手段将其描绘成“树”的形状, 十分直观且易于理解, 程序开发人员可以很方便地对其进行修改和插入操作, 从而实现特定的功能. 另一方面是因为PPCG等多面体编译器中代码生成模块可以根据调度树生成其对应的AST, 进而自动生成面向特定体系结构的并行代码, 程序开发人员只需要确保调度树等信息符合特定的规范即可. 因此本文采用调度树作为多面体模型中调度的中间表示形式, 以实现面向Stencil计算的自动混合精度优化.
为了解决混合精度对Stencil计算的普遍适应性难题, 针对程序中给定的Stencil计算自动生成混合精度程序, 本文设计了如
面向Stencil计算的自动混合精度优化器示意图
面向Stencil计算的自动混合精度优化器的编译优化流程如
(1) 预处理模块将从C语言源程序中识别用户指定的循环嵌套程序段, 将该程序段表示成多面体形式, 通过调用线性整数规划过程计算依赖关系, 然后利用isl (integer set library)调度算法将原始调度转换成另一种新的调度, 并生成调度树中间表示.
(2) 混合精度优化模块将根据混合比例的参数值对循环嵌套的迭代空间进行划分, 然后对划分出来的两个子空间进行数据流分析, 并通过计算得出混合精度计算中需要进行强制类型转换的相关数据, 最后依据这些信息对调度树进行转换, 即利用树中各种结点通过插入和删除等操作将原始调度树转换成混合精度计算的调度树.
(3) 代码生成模块将调度树等数据作为输入, 借助线性整数规划过程生成AST, 然后根据C语言规范将AST转变成最终代码, 即得到经过自动混合精度优化的目标代码.
预处理模块其实是基于多面体模型的一般编译流程中的抽象分析和调度变换两个阶段的组合, 称之为预处理是针对第2部分的混合精度优化而言的; 混合精度优化模块本质上也是在满足依赖关系的前提下, 将一种调度转换成另外一种调度的过程, 即其本质上也是一种调度变换, 与自动并行化领域的调度变换不同的是, 其不是以挖掘程序并行性和数据局部性为目的, 而是以实现混合精度计算优化为目的; 代码生成模块本质上则是对原有编译工具的代码生成阶段进行适当的改造和扩展以使其支持混合精度优化之后的调度树.
从理论上讲, 混合精度优化的目标代码中包含的高精度计算占比越高, 那么误差就会越小, 精度也就越高; 程序运行耗时就会越长, 性能也就越差. 然而, 实际上其精度和性能情况还会受到其他多种因素的影响, 且不同因素之间相互关联, 例如: 不同混合比例下的混合精度计算程序在运行时其Cache命中率、累积误差的大小、强制类型转换引起的舍入误差等都会不同, 且其均会对精度和性能产生一定的影响, 因此目前尚没有一种成熟的方法可以直接量化或者分析出来这种相互关系, 但是这个趋势是普遍成立的, 本文的实验也充分验证了这一趋势. 因此用户可以通过一定的策略生成几个特定混合比例下的混合精度代码, 并根据其误差和性能表现来进一步确定最合适的混合比例或其区间, 比如: 利用二分搜索的思路通过判断误差是否符合应用的精度需求来确定混合比例所在的区间, 再结合区间内的性能表现来确定最合适的混合比例.
本文的面向Stencil计算的自动混合精度优化器是在PPCG[
预处理模块分为抽象分析和调度变换两个阶段, 抽象分析阶段利用pet库从用户输入的C语言源代码中识别用#pragma scop和#pragma endscop编译指示指定的循环嵌套程序段, 然后构建该程序段的多面体模型, 其中包括迭代空间、访存关系以及原始调度, 并以仿射约束的形式储存起来, 以便对该程序段进一步分析和优化.
迭代空间是对应的程序段中所有语句实例的集合, 且语句实例与迭代向量一一对应. 示例一维Jacobi迭代计算的核心代码如
一维Jacobi迭代计算代码
访存映射是语句实例与其访问的数组元素之间映射关系的集合, 其中包括了读访存映射关系与写访存映射关系. 对于一维Jacobi迭代计算的示例, 两者分别可以用公式(2)和公式(3)来表示, 其中“→”表示源点的语句实例读或者重写了汇点元素的数据, 例如
调度主要是为语句实例分配执行顺序, 在多面体模型中一般采用通过映射关系将每一个语句实例与一个无名整数元组一一对应的形式来表示. 示例一维Jacobi迭代计算的原始调度可以由公式(4)来表示, 其中变量
调度变换前后的调度树示意图
依赖关系是相互依赖和关联的语句实例的集合, 同时它也是判断程序是否正确执行的关键, 因为一旦程序的依赖关系发生改变, 那么程序的语义和结果也会随之而改变. 因此, 在抽象分析阶段一般还会以迭代空间和访存映射为输入, 通过调用线性整数规划过程来计算依赖关系[
在程序自动并行化领域, 多面体编译工具在将循环嵌套内的语句表示成空间多面体形式之后, 会进行一系列的以提升程序并行性和数据局部性为目的分析和变换, 即调度变换. 为了使程序具有较好的并行性和局部性, 面向Stencil计算的自动混合精度优化器在抽象分析阶段结束之后, 采用了isl库中改进的isl调度算法[
经过预处理模块完成对程序段的抽象分析以及调度变换后, 优化器将得到一个包含多个
迭代空间划分是指利用迭代空间划分算法将
算法
输入:
输出: band_node_list.
initialize two new
initialize two new iteration domain
initialize a new empty statement in each new iteration domain
get the boundary of two affine constraint expressions,
compute the affine constraint pair:
compute the affine constraint pair: −1 −
add the pair of affine constraint to the corresponding statement respectively
add the pair of affine constraint to both statement
add the two new iteration domain to the corresponding
combine two
示例一维Jacobi迭代计算中
可以发现, 由于调度变换阶段对循环嵌套实现了循环合并优化, 所以优化后的两条语句在同一个循环体中, 即语句
由于程序中一切合法的循环必须要同时有上下界, 以便程序能够在适当的时候跳出循环, 所以一般一层循环会有两个仿射约束表达式, 我们将其称为一对仿射约束表达式. 以语句
那么, 语句
首先从其中提取循环的上下界, 即仿射约束表达式的边界值
算法1在设计时便充分考虑到了如何尽可能帮助用户能够快速准确地找到最合适的混合比例
最外层循环切分示意图
然后依次计算切分后的第1个迭代空间循环边界对应的仿射约束表达式和切分后的第2个迭代空间循环边界对应的仿射约束表达式, 并将这两对仿射约束分别添加到两个迭代空间的语句中. 这两个语句最外层循环的仿射约束对的可以分别用公式(10)和公式(11)来表示:
对于一维Jacobi迭代计算的示例, 其
迭代空间划分之后的调度树
算法1在实现时由于仿射约束对需要自行提前判断, 且还需要考虑到各种非法情况以及对应的异常处理, 所以其具体的代码会比上面描述的过程更加复杂, 本文算法的实现代码可以参考论文开源代码中
需要说明的是, 该迭代空间划分算法等价于循环分段和循环剥离的结合, 并不会破坏程序内原有的依赖关系, 由依赖基本定理可知, 该程序变换可以保证其合法性[
数据流分析在本文中是指通过对程序段中所有数组的引用以及语句实例的访存映射进行分析, 并对其中的数组引用进行分组、计算和分块, 从而得到混合精度计算所需要的强制类型转换的流映射关系和低精度数组的信息, 以便实施混合精度计算的过程. 由于循环嵌套中计算误差的特性, 一般而言混合精度计算都是先用高精度计算, 然后再用低精度计算, 因为只有这样整个过程中累积的误差才会最小, 计算结果才会最精确. 因此, 一般而言本过程计算的结果都只是低精度计算所在的第2个迭代空间中的相关数据, 换言之就是高精度计算所在的迭代空间的计算结果一般为空, 也就是其不需要进行任何的强制类型转换, 这显然与我们的常识相一致.
我们首先将所有需要的调度信息提取出来, 然后依次考虑每个数组, 对程序段中的数组引用进行分组, 检测过程的算法描述如算法2.
算法
输入: arrays, band_node_list;
输出: local_array.
get scheduling and other information of the band_node_list
initialize the groups of array references
combine these two groups into one group
tiling the array reference groups according to the divided iteration domain, and copy array to local_array
combine these two groups into one group
calculate the index offset and other information, perform a series of checks at the same time
update the information of the local_array
首先对代码中数组引用进行初始化分组, 即一个数组的引用及其相关信息初始化为一个组, 但是, 如果两个组中的引用访问了相同的数组元素, 并且如果两个引用中的至少一个是写入(即存在依赖), 那么需要将这两个引用放在一起考虑(合并这两个组), 因为仅考虑其中一个可能会导致数据不一致. 因此还需要通过遍历经过初始化的分组结果来判断是否存在两个分组有交叉访问关系, 然后再判断访问关系中是否包含写入, 如果同时满足这两个条件则需要将这两个引用组合并成一个组. 然后根据划分的迭代空间对合并后的数组引用组进行分块, 得到本地数组副本local_array, 之后针对local_array再次进行数组引用组的遍历、判断和合并, 根据合并结果计算索引偏移量等信息, 同时进行一系列的检查, 最后更新local_array中的信息.
在得到本地数组local_array之后, 虽然其中的计算索引偏移量等信息已经更新, 但是其中的大小、边界等信息还是原始数组的信息副本, 以原始数组的大小为例, 其可能取决于参数, 但是利用提取出来的上下文信息可以获得对这些参数的限制, 进而可以简化这些表达式, 与此同时, 还可以利用数组引用分组的信息计算本地数组被引用部分的大小, 并将其与预处理阶段提取的上下文等信息进行结合进而更新和简化本地数组local_array中的大小和索引偏移量等信息. 标量数据也被当作数组处理, 并将其大小视为1. 如果更新后的某一个数组大小是一个零函数或者NULL, 则表示该数组在这里没有被引用, 由于访问函数实际上无法访问任何内容, 因此将数组大小打印为0并没有什么影响, 同时还可以提高算法的鲁棒性和健壮性.
以一维Jacobi迭代计算为例,
最后, 标记所有数组引用组非空的local_array数组, 并为其生成强制类型转换的流映射关系, 并存储在local_array的数组引用组中, 同时在低精度所在的子树中插入一个包含流映射关系的
对于输入流而言, 其含义是读取
数据流分析之后的调度树
调度树转换过程是指依据划分后的迭代空间和数据流分析的结果, 通过对原始调度树中的结点施以各种合法的操作, 将其自动转换成符合混合精度计算的新的调度树的过程. 其具体的步骤如下.
(1) 通过算法3利用local_array中的信息计算低精度计算时所需的输入和输出流, 再将他们与流映射关系结合, 从而计算出强制类型转换对应的调度
(2) 在
调度转换算法本质上就是通过对树进行一系列操作以达到对其改造的目的, 但是其具体实现时由于要充分考虑各种情况的树形, 因此会设置很多
算法
输入: local_array;
输出: in, out.
init in and out
get all read and write access relationships of the group
delete the access relationships that are only needed to communicate data within current domain
add the results into in and out
对于一维Jacobi迭代计算示例而言, 其低精度计算的输入流可以用公式(13)来表示, 其输出流可以用公式(14)来表示, 其转换之后的调度树如
转换之后的调度树
由于PPCG内嵌了对领域专用语言(domain specified language, DSL) Pencil语言的支持, 使其能够采用“制导+多面体编译优化”的模式对程序进行分析, 因此我们的优化器也天然地支持用户将__pencil_kill()等编译指示添加到通用编程语言中, 为多面体模型进行特定优化提供领域相关信息. 同时, 我们这里的输出流和调度树都是经过编译指示优化之后的结果, 以便尽可能地还原Stencil计算在实际应用场景中的使用情景, 更准确地反映混合精度优化在实际应用场景中所能发挥的作用.
代码生成模块将经过混合精度优化后的调度树作为输入, 利用多面体扫描技术[
由于PPCG的代码生成模块做得十分细致且完善, 因此本文在实现时只是对其进行了一些扩展和改进, 以支持混合精度优化的强制类型转换等特殊代码的生成, 故不再赘述其生成细节.
一维Jacobi迭代计算示例最终生成的代码如后文
一维Jacobi迭代计算示例最终生成的代码
为验证面向Stencil计算的自动混合精度优化器的有效性, 我们利用PAPI (performance application programm-ing interface)性能测试工具[
我们在PPCG原有功能的基础上提供了一个--automatic-mixed-precision选项来选择是否开启自动混合精度优化(默认开启), 一个--automatic-mixed-precision-rate (或-R)选项用于接收用户自定义的混合比例. 本文实验所采用的测试平台的相关信息如
测试平台信息
类型 | x86平台 | 国产申威平台 |
Architecture | x86_64 | Sunway |
CPU | Intel(R) Xeon(R) Gold 6230 CPU 2-socket NUMA | SW26010P CPU |
Clock | 2.10 GHz | 2.10 GHz |
Cores | 20 cores/socket, 2 socket (total: 40 cores) | 41 932 800 cores |
Hyperthreading | enabled | unknown |
Cache sizes | 64 KB L1, 1 024 KB L2, 28 160 KB L3 | unknown |
Compiler | gcc 9.4.0 | SWGCC |
Common flags | -O2 -DPOLYBENCH_USE_C99_PROTO -lm | -O2 -DPOLYBENCH_USE_C99_PROTO -lm |
PAPI test flags | -DPOLYBENCH_PAPI -lpapi | -DPOLYBENCH_PAPI -lpapi |
Error test flags | -DPOLYBENCH_DUMP_ARRAYS | -DPOLYBENCH_DUMP_ARRAYS |
Performance test flags | -DPOLYBENCH_TIME | -DPOLYBENCH_TIME |
PPCG | 0.08.5-33 | 0.08.5-33 |
ppcg flags | --target=c [--no-automatic-mixed-precision/-R $rate] | --target=c [--no-automatic-mixed-precision/-R $rate] |
Tiling options | --tile --tile-size=… | none |
PAPI | 6.0.0.1 | not support |
OS | Ubuntu 20.04.4 LTS (GNU/Linux 5.14.0-1027-oem) | unknown |
runtime state | single core single thread | single MPE single thread |
我们采用了Polybench测试集中Stencil计算的测试用例[
测试集信息
测试用例 | 类型 | 问题规模 | 国产申威平台执行时间 (s) | X86平台执行时间 (s) | |||
double | float | double | float | ||||
3d7pt | 星形 | 1200×128×128×128 | 54.84 | 36.06 | 3.75 | 6.98 | |
3d27pt | 盒型 | 800×128×128×128 | 108.51 | 90.48 | 14.56 | 14.45 | |
fdtd-1d | 星形 | 100000×10240 | 6.63 | 6.62 | 1.62 | 1.59 | |
fdtd-2d | 星形 | 3072×2047×2557 | 471.84 | 313.43 | 79.33 | 51.44 | |
jacobi-1d | 星形 | 819320×20480 | 16.32 | 15.77 | 3.09 | 2.12 | |
jacobi-2d | 星型 | 2048×2048×2048 | 360.68 | 312.04 | 23.53 | 18.60 | |
heat-1d | 星形 | 100000×10240 | 7.86 | 7.86 | 1.32 | 0.82 | |
heat-2d | 星形 | 8000×1024×1024 | 157.46 | 93.06 | 11.67 | 11.19 | |
heat-3d | 星形 | 1000×200×200×200 | 373.19 | 322.43 | 34.31 | 30.53 | |
seidel-2d | 盒型 | 2048×1024×1024 | 85.07 | 69.81 | 23.72 | 22.03 |
在该测试集中, 3d7pt和3d27pt用例代表了大数据规模的Stencil计算, 对这些用例的测试可以验证混合精度优化在大型应用中的有效性; fdtd-1d/2d用例中包含多条语句, 分别用于测试混合精度优化在特殊情况下的适用性; jacobi-1d/2d、seidel-2d用例分别代表一维、二维的Jacobi计算以及Gauss-Seidel计算, 可测试其迭代计算在不同收敛情况下的适用性; heat-1d/2d/3d用例分别代表一维、二维、三维的heat计算, 对这3个用例的分析可以说明混合精度优化在不同维度上的可扩展性.
从第4.3节生成的代码可以看到, 代码里面确实包括两个不同精度计算的循环, 但是在编译时编译器有可能会自动进行精度提升的操作, 因此不能从代码就直接得出已经实现了混合精度计算的结论, 还需要进一步的测试来证明. 于是, 我们通过调用PAPI测试工具[
在对混合精度进行误差测试时, 我们采用绝对误差来刻画不同结果的可靠程度, 并以PPCG的高精度计算的结果为基准, 其低精度计算的结果为对比进行测试, 即
不同比例下的误差表现情况
从
我们在性能测试时, 为了准确地测量混合精度指令级并行的加速效果, 同时测试了PPCG的double精度计算、float精度计算、不同混合比例的混合精度计算代码的执行耗时, 对它们还进行了多种大小的循环分块, 找到各自的最小的执行耗时, 并以double精度计算为基准计算float精度计算的加速比以及混合精度计算的加速比, 从而来量化混合精度指令级并行的加速效果. 加速比的计算方法如公式(15)所示, 其中
此外, 为了避免执行耗时的测量会受到软件和硬件等环境因素的影响, 本文采取了执行程序5次, 并分别去掉一次最长和最短的执行耗时, 然后计算剩余3次执行的平均耗时来表示其执行耗时, 同时还计算了3次执行耗时与平均执行耗时的最大绝对偏差, 来帮助评估执行耗时测量的精确度. 本文中展示的性能测试结果的最大绝对偏差均小于5%.
由于混合比例为100时, 优化器不会对原始的高精度计算程序做混合精度优化; 混合比例为0时, 优化器生成的目标代码虽然只有低精度计算, 但是还会包含精度转换, 一方面从严格意义上来说并不属于混合精度计算, 另一方面实际应用中与用户手工修改原始程序得到的纯低精度版本相比, 性能较差, 无实际应用价值. 故下文中我们测试性能表现选取的混合比例是
在新一代国产申威平台上, 由于其主核(MPE)上的指令更为全面和完善, 因此我们选择了其主核进行测试. 同时受其Cache大小的影响, 我们没有对其进行循环分块来提升数据局部性. 另外, 由于两个平台指令集和架构的不同, 其性能表现也有较为明显的差异, 一方面表现在同一测试用例的加速效果并不相同, 其中最典型的就是3d7pt用例, 在X86平台上受其计算的类型、计算的宽度、数据量、Cache大小、自动向量化和SSE指令架构等特性的影响, 其double计算快于float计算, 而申威平台自动向量化和指令集等较为简单, 导致其并没有出现这样的加速效果; 另一方面还表现在性能最优时混合比例的不同. 不同测试用例在不同平台上性能最优时的混合比例大小如
性能最优时的混合比例
测试用例 | 国产申威平台 | x86平台 | ||
Tile size | ||||
3d7pt | 5 | 0 | 95 | |
3d27pt | 5 | 512 | 5 | |
fdtd-1d | 5 | 8 192 | 5 | |
fdtd-2d | 5 | 0 | 5 | |
jacobi-1d | 95 | 1 024 | 95 | |
jacobi-2d | 5 | 4 096 | 95 | |
heat-1d | 55 | 8 192 | 95 | |
heat-2d | 5 | 0 | 5 | |
heat-3d | 90 | 0 | 90 | |
seidel-2d | 5 | 4 | 5 |
x86平台上所有测试用例的性能表现如
x86平台上不同测试用例的加速比
申威平台上所有测试用例的性能表现如
申威平台上不同测试用例的加速比
由于heat-3d本身的计算和访存特性的影响, 混合精度优化后的运行速度不升反降, 故其加速比略小于1, 但是从整体上看, 混合精度的加速效果还是值得肯定的. 另外, 从
本文除了对自动生成的混合精度程序代码开展性能测试, 还对代码生成过程中的编译时长也进行了测试, 从而达到以量化的方式准确评估优化器性能的目的, 编译时长测试结果如
编译时长测试结果
方法 | 3d7pt | 3d27pt | fdtd-1d | fdtd-2d | jacobi-1d | jacobi-2d | heat-1d | heat-2d | heat-3d | seidel-2d | Average |
PPCG | 505 | 3 188 | 135 | 420 | 148 | 347 | 146 | 250 | 1 250 | 208 | 659.5 |
Our | 642 | 3 748 | 142 | 505 | 163 | 413 | 159 | 321 | 1 549 | 252 | 789.5 |
整个测试中10个测试用例的平均编译时长为789.5 ms, 其中耗时最长的3d27pt用例编译时长为3 748 ms, 与PPCG相比编译时长平均多130 ms, 而手工编写Stencil计算的混合精度程序至少需要以小时为单位的时间, 甚至面对复杂应用时需要以天为单位计算. 相比之下, 利用本文提出的面向Stencil计算的自动混合精度优化器能够大大降低混合程序开发的成本, 从而解决Stencil计算的混合精度程序的编程难的问题.
由于混合精度可以减少计算中不必要的精度冗余, 并且其内存占用更少、计算速度更快, 因此受到了极大的关注, 很多研究人员都对其开展了研究, 目前虽然已经在精度调整和混合精度训练方面取得了相当不错的进展, 但是循环嵌套级的混合精度仍然是一个很具有挑战性的问题. 另一方面, 基于多面体模型的各种编译工具层出不穷, 其将循环嵌套抽象成空间多面体, 并通过多面体上的几何操作来优化程序, 在程序自动并行化领域取得了许多突破. 本文将多面体模型和混合精度结合在了一起, 设计并实现了第1个面向Stencil计算的自动混合精度优化器. 该优化器在基于多面体模型的一般编译流程的中间表示层, 扩展并实现了迭代空间划分、数据流分析和调度树转换, 使得能够在调度树上实施混合精度优化, 从而实现面向Stencil计算的自动混合精度优化. 对Stencil计算用例测试的实验结果证明了所提出方案的有效性和实用性.
必须承认的是, 面向Stencil计算的自动混合精度优化器仍有很多优化的潜力, 一方面我们目前正在支持除Stencil计算外的其他常用的计算模式, 另一方面我们目前也正在尝试在提取多面体模型之后, 进行迭代空间划分之前, 根据循环嵌套内的计算语句及其边界, 对其误差和性能的提升以及损耗进行建模, 并通过对该模型计算直接得到误差阈值下性能最好的混合比例, 而不再需要用户指定比例参数, 并用该模型来指导后续过程, 从而直接自动生成最优化的混合精度优化代码. 另外, 我们还在考虑对面向Stencil计算的混合精度优化器进行优化和扩展, 使其支持更多的循环计算类型, 从而实现循环嵌套级的自动混合精度优化, 并将其扩展到GPU等异构架构上, 以提高其通用性和对主流异构架构的适用性. 不仅如此, 我们还在尝试对其编译后端进行扩展, 使其能够自动生成指定平台下二进制文件, 而不再只是生成目标代码, 并在其进行指令选择和重排序时, 采用一定的策略和算法实现高精度和低精度计算的多流水并行, 最大幅度地挖掘混合精度计算的性能优势.
http://www.jos.org.cn/1000-9825/4589.htm]]>
http://www.jos.org.cn/1000-9825/4589.htm]]>
DeVries PMR, Viégas F, Wattenberg M, Meade BJ. Deep learning of aftershock patterns following large earthquakes. Nature, 2018, 560(7720): 632–634. [doi: 10.1038/s41586-018-0438-y]
Cherubin S, Agosta G. Tools for reduced precision computation: A survey. ACM Computing Surveys, 2021, 53(2): 33. [doi: 10.1145/3381039]
Damouche N, Martel M. Salsa: An automatic tool to improve the numerical accuracy of programs. Automated Formal Methods, 2018, 5: 63–76.
Cherubin S, Cattaneo D, Chiari M, Di Bello A, Agosta G. TAFFO: Tuning assistant for floating to fixed point optimization. IEEE Embedded Systems Letters, 2020, 12(1): 5–8. [doi: 10.1109/LES.2019.2913774]
Kum KI, Kang JY, Sung W. AUTOSCALER for C: An optimizing floating-point to integer C program converter for fixed-point digital signal processors. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 2000, 47(9): 840–848. [doi: 10.1109/82.868453]
Grosser T, Verdoolaege S, Cohen A. Polyhedral AST generation is more than scanning polyhedra. ACM Transactions on Programming Languages and Systems, 2015, 37(4): 12. [doi: 10.1145/2743016]
http://www.jos.org.cn/1000-9825/5563.htm]]>
http://www.jos.org.cn/1000-9825/5563.htm]]>
Verdoolaege S, Carlos Juega J, Cohen A, Gómez JI, Tenllado C, Catthoor F. Polyhedral parallel code generation for CUDA. ACM Transactions on Architecture and Code Optimization, 2013, 9(4): 54. [doi: 10.1145/2400682.2400713]
https://hal.inria.fr/inria-00551516/]]>
Grosser T, Groesslinger A, Lengauer C. Polly—performing polyhedral optimizations on a low-level intermediate representation. Parallel Processing Letters, 2012, 22(4): 1250010. [doi: 10.1142/S0129626412500107]
Girbal S, Vasilache N, Bastoul C, Cohen A, Parello D, Sigler M, Temam O. Semi-Automatic composition of loop transformations for deep parallelism and memory hierarchies. International Journal of Parallel Programming, 2006, 34(3): 261–317. [doi: 10.1007/s10766-006-0012-3]
http://perso.ens-lyon.fr/christophe.alias/impact2011/impact-05-slides.pdf]]>
https://sourceforge.net/projects/polybench/]]>