一种经验库制导的浮点程序优化加速策略  

An Experience-Guided Acceleration Strategy for Floating-Point Optimization

作　　者：肖安祥 张硕骁 汤恩义[1,2] 陈鑫[1] 王林章[1] XIAO An-Xiang;ZHANG Shuo-Xiao;TANG En-Yi;CHEN Xin;WANG Lin-Zhang(State Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210023;Software Institute,Nanjing University,Nanjing 210093)

机构地区：[1]南京大学计算机软件新技术国家重点实验室,南京210023 [2]南京大学软件学院,南京210093

出　　处：《计算机学报》2022年第9期2014-2028,共15页Chinese Journal of Computers

基　　金：国家自然科学基金(62172210,61772260)资助.

摘　　要：为了保障数值程序的准确与高效,浮点程序自动优化成为了近年来学术界关注的一项新兴技术.该技术的核心思想是将经典的数值分析理论总结成程序转换规则,并利用规则将浮点程序以计算过程更为稳定的算法进行自动重写,从而使数值程序稳定高效且易于维护.然而,现有浮点程序自动优化方法的优化效率是其主要瓶颈.随着越来越多的数值程序转换规则被发现与总结,自动优化框架的规则库会越来越大,传统优化方法在规则库中遍历所有优化规则的过程也变得越来越困难.本文提出了一种经验库制导的浮点程序优化加速策略,该策略基于浮点误差成因的相似性原理,将已成功优化浮点程序对应的符号与结构特征抽取出来,并以散列的方式将优化该程序涉及到的规则序列保存在一个优化经验库中.当新的浮点数值程序需要进行自动优化时,本文算法首先计算其符号结构特征与经验库中各记录的相似度.符号结构相似度较高的记录所对应的规则序列会被优先用于浮点程序重写,从而得到优化程序.随着优化程序的增多,经验库的规模会逐渐增大,经验库的散列化分区存储设计保证了其检索与匹配效率.在浮点程序优化基准用例集FPBench和开源物理引擎OpenRelativity上的实验表明,在优化后浮点程序精度与传统方法类似的前提下,本文的加速策略能使平均优化速度相对于传统浮点程序优化方法提升6.04倍,显著提高了浮点数值程序自动优化技术的可用性.To ensure the correctness and efficiency of floating-point programs,automatic optimizing techniques for floating-point programs have been attached attention from academia in recent years.The core idea is to summarize transformation rules from classical numerical analysis theory and rewrite floating-point programs automatically with more stable algorithms,which produces more stable,efficient and maintainable programs.However,efficiency becomes the bottleneck of these techniques.As more and more transformation rules are discovered and summarized,the rule base used by the optimizing framework becomes larger and larger.It is more difficult to scan the whole rule base as usual.In this paper,we propose an experience-guided acceleration strategy for floating-point optimization.Based on the principle of similar causes of floating-point errors,the strategy extracts the corresponding symbolic and structural features of successfully optimized floating-point programs,and saves the rule sequences involved in the optimization of the programs into a hash-based optimization experience database.When optimizing a floating-point program,the optimizer first calculates the similarity between symbolic and structural features of the program and that of records in the experience base.Rule sequences associated with records having higher similarity are preferred to be used in rewriting and optimizing the program.With more and more programs to be optimized,the experience base increases gradually and a hashed-partition design ensures the efficiency of record-searching.The above approach has been evaluated on the FPBench benchmark and the open source engine OpenRelativity.The results show that compared to the traditional optimizing approach,it can achieve a 6.04x speedup in average.In addition,it improves accuracy for floating-point programs effectively as well as the traditional optimizing approach does.Therefore,our approach improves the usability of automatic optimizing techniques significantly.

关 键 词：加速策略 程序优化 浮点数值程序 经验库 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]