频繁序列挖掘帮助的LLVM编译时能耗优化方法

Frequent-sequence-mining-assisted Energy Consumption Optimization Method at LLVM Compilation Time

面向最小化能耗的LLVM编译时优化研究工作还较为稀缺,而现有的设计空间搜索优化方法仍缺乏有效捕获和使用选项交互信息的手段,还存在解质量不高和收敛速度不快的问题.针对上述问题,文中提出一种频繁序列挖掘帮助的LLVM编译时能耗优化方法.该方法运用带能耗改进标注的频繁选项序列FOSE表征反复出现在优势解中的选项子序列及其功效,进一步借助不同序列长度的FOSE捕获任意多个选项之间交互并利用前缀树和后缀树进行表示;在此基础上,针对迭代寻优过程设计了一种FOSE挖掘算法,从而形成可为新解生成提供有用、全面、可高效使用和时效好的选项交互信息挖掘方法;最后基于FOSE的前后缀树定义了新解生成机制并给出了新解生成的规则和过程,进而提出一种迭代优化算法FHIA-FSM.与当前最快可获取较好质量解的Georgiou算法以及公认在足够长演化时间后可得到高质量解的GA算法在4个不同领域的7个典型案例下的实验对比显示:在基准停机时间下本文FHIA-FSM较Georgiou和GA的解质量平均相对改进最好可达15.52%和101.81%;在达到基准解质量的收敛速度上,FHIA-FSM较Georgiou和GA平均相对改进最好可达18.00%和25.25%.

At present the researches on minimizing energy consumption at LLVM(widely used open source compiler)compilation time are still scarce.The existing design space search optimization methods still lack of effective means to capture and use options interaction information,and have the problems of low quality of solution and slow convergence rate.To alleviate these problems,a frequent-sequence-mining-assisted energy consumption optimization method at LLVM compilation time is proposed.In this method,the frequent option sequence with energy consumption improvement annotation(denoted as FOS E for convenience)is used to characterize the subsequence of options that repeatedly appear in the dominant solutions and its utility.Further,all the FOS E with different sequence lengths are used to capture the interactions among options,and are represented with prefix tree and suffix tree.To build these trees in the iterative optimization process,a mining algorithm is designed in order to provide useful,comprehensive,efficiently addressable,and time-effective heuristic information for the new solutions generation,then the mining method is formed to effectively capture option interactions on energy consumption.At the same time,a mechanism including the rules and process for new solution generation is also defined based on the prefix and suffix trees of FOS E.On the basis of the proposed mining method and mechanism,an iterative optimization algorithm named FHIA-FSM is designed.Moreover,Georgiou and GA are selected as compared algorithms.The experimental results under 7 typical cases in 4 different fields show that FHIA-FSM was significantly better than the compared methods in terms of solution quality and convergence rate in all compared experiments.Specifically,FHIA-FSM has the best improvement relative to average solution quality by 15.52%against Georgiou and 101.81%against GA under the reference run time respectively.FHIA-FSM can accelerate the convergence rate by 18.00%against Georgiou and 25.25%against GA at best under achieving the reference solution quality respectively.