2019基于频繁模式挖掘的GCC编译时能耗演化优化算法-倪友聪 , 吴瑞 , 杜欣 , 叶鹏 , 李汪彪 , 肖如良.pdf

上善若水

330

19页

0次

2022-05-23

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2019,30(5):1269−1287 [doi: 10.13328/j.cnki.jos.005734] http://www.jos.org.cn

基于频繁模式挖掘的 GCC 编译时能耗演化优化算法

∗

倪友聪

1,4

吴

瑞

杜

欣

1,4

叶

鹏

李汪彪

肖如良

(福建师范大学数学与信息学院,福建福州 350117)

(武汉纺织大学数学与计算机学院,湖北武汉 430200)

(福建师范大学光电与信息工程学院,福建福州 350117)

(福建省公共服务大数据挖掘与应用工程技术研究中心(福建师范大学),福建福州 350117)

通讯作者: 杜欣, E-mail: xindu79@126.com; 叶鹏, E-mail: whuyp@126.com

摘要: 演化算法通过搜寻 GCC 编译器最优编译选项集,对可执行代码的能耗进行改进,以达到编译时优化嵌入

式软件能耗的目的.但这类算法未考虑多个编译选项之间可能存在相互影响,导致了其解质量不高且收敛速度慢的

问题.针对这一不足,设计了一种基于频繁模式挖掘的遗传算法 GA-FP.该算法在演化过程中利用频繁模式挖掘得到

出现频度高且能耗改进大的一组编译选项,并以此作为启发式信息,设计了“增添”和“删减”两种变异算子,帮助提高

解质量和加快收敛速度.与 Tree-EDA 算法在 5 个不同领域的 8 个典型案例下进行对比实验,结果表明,该 GA-FP 算

法不仅能够更有效地降低软件能耗(平均降低 2.5%,最高降低 21.1%),而且还能在获得不劣于 Tree-EDA 能耗优化效

果的前提下更快地收敛(平均加快 34.5%,最高加快 83.3%),最优解中编译选项的相关性分析进一步验证了所设计变

异算子的有效性.

关键词: 软件能耗;编译优化;嵌入式软件;演化算法

中图法分类号: TP314

中文引用格式: 倪友聪,吴瑞,杜欣,叶鹏,李汪彪,肖如良.基于频繁模式挖掘的 GCC 编译时能耗演化优化算法.软件学报,2019,

30(5):1269−1287. http://www.jos.org.cn/1000-9825/5734.htm

英文引用格式: Ni YC, Wu R, Du X, Ye P, Li WB, Xiao RL. Evolutionary algorithm for optimization of energy consumption at

GCC compile time based on frequent pattern mining. Ruan Jian Xue Bao/Journal of Software, 2019,30(5):1269−1287 (in

Chinese). http://www.jos.org.cn/1000-9825/5734.htm

Evolutionary Algorithm for Optimization of Energy Consumption at GCC Compile Time

Based on Freque nt Pa tter n Mi ni ng

NI You-Cong

1,4

, WU Rui

, DU Xin

1,4

, YE Peng

, LI Wang-Biao

, XIAO Ru-Liang

(College of Mathematics and Informatics, Fujian Normal University, Fuzhou 350117, China)

(College of Mathematics and Computer Science, Wuhan Textile University, Wuhan 430200, China)

(College of Photonic and Electronic Engineering, Fujian Normal University, Fuzhou 350117, China)

(Fujian Provincial Engineering Technology Research Center for Public Service Big Data Mining and Application (Fujian Normal

University), Fuzhou 350117, China)

∗ 基金项目: 福建省新世纪优秀人才项目; 福建省自然科学基金(2015J01235, 2017J01498); 福建省教育厅 JK 类项目(JK20150

06); 湖北省自然科学基金(2018CFB689)

Foundation item: New Century Talent Supporting Program of Fujian Province; Natural Science Foundatiuon of Fujian Province

(2015J01235, 2017J01498); JK Fund of Education Bureau, Fujian Province (JK2015006); Natural Science Foundatiuon of Hubei Province

(2018CFB689)

本文由智能化软件新技术专刊特约编辑申富饶教授和李戈副教授推荐.

收稿时间: 2018-09-01; 修改时间: 2018-10-31; 采用时间: 2018-12-13

1270

Journal of Software 软件学报 Vol.30, No.5, May 2019

Abstra ct : The evolutionary algorithms have been used to improve the energy consumption of executable code of embedded software by

searching the optimal compilation options of GCC compiler. However, such algorithms do not consider the possible interaction between

multiple compilation options so that the quality of their solutions is not high, and their convergence speed is slow. To solve this problem,

this study designs an evolutionary algorithm based on frequent pattern mining, called GA-FP. In the process of evolution, GA-FP uses

frequent pattern mining to obtain a set of compilation options which are of high-frequency and contribute to significant improvement on

energy consumption. The derived options are used as the heuristic information and two mutation operators of ADD and DELETE are

designed to increase the quality of solution and accelerate the convergence speed. The comparative experiments are done on 8 typical

cases in 5 different fields between Tree-EDA and GA-FP. The experimental results indicate that the GA-FP can not only reduce the energy

consumption of software more effectively (the average and maximal reduction ratios are 2.5% and 21.1% respectively), but also converge

faster (the average of 34.5% faster and up to 83.3% faster) when the energy optimization effect obtained by GA-FP is no less than that of

Tree-EDA. The correlation analysis of compilation options in the optimal solution further validates the effectiveness of the designed

mutation operators.

Key words: software energy; compilation optimization; embedded software; evolutionary algorithm

能耗是嵌入式软件的关键质量属性,特别是在电量受限的执行环境中,降低嵌入式软件的能耗具有更为重

要的价值和意义

[1]

.与嵌入式软件源代码级的能耗优化相比,编译时能耗优化具有无需改动源代码,并且可保证

功能语义一致性的优点.作为一款开源编译器,GCC

[2]

已广泛应用于嵌入式软件源代码的编译.GCC 提供常用的

几种优化等级,利用每种优化等级所预设的一组编译选项对软件源代码进行编译,能实现可执行代码的质量优

化.然而,对于特定的软件源代码、特定的执行平台和特定的优化目标,GCC 的优化等级往往难以获得最佳的优

化效果.此外,GCC 编译选项数目众多,选择空间十分庞大.例如 GCC4.9.2 提供了 188 个编译选项,其选择空间高

达 2

188

.依靠程序员人工选择编译选项不仅十分困难,而且也难以保证优化质量.更为重要的是,GCC 提供的优化

等级多集中于执行时间和目标代码大小的优化,而未针对能耗优化的场景.Pallister 的研究成果

[3]

已表明,使用

GCC 的某些优化等级对嵌入式软件进行编译时,甚至出现能耗增加的情况.近年来,用于能耗优化的 GCC 编译

选项的选择问题已经成为了一个研究热点

[4]

.基于 Hoste 等人

[5]

提出的 58 个常用于能耗优化的编译选项,已涌现

出基于统计的方法、机器学习方法和演化算法这 3 类主要的优化方法

[6]

基于统计的方法

[7]

运用 Mann-Whitney 测试为特定的领域嵌入式软件确定一组有改进效果的编译选项.具

体地,首先,将一组预设的编译选项应用于多个同类型嵌入式软件,考察在这组选项中去掉某一编译选项后的能

耗变化情况;再根据 Mann-Whitney 测试的结果判断去掉该编译选项前后是否存在显著的差异,从而确定该编译

选项是否对能耗有显著影响;最后,经过多组统计实验,可找出一组对某一类型嵌入式软件有能耗改进效果的编

译选项.由于 GCC 编译选项众多且它们之间还存在复杂的影响关系,而基于统计的方法一次仅考查 1 个选项的

模式难以最终获取对能耗改进效果最佳的编译选项集合.

机器学习方法

[8−10]

先通过对训练样本集使用机器学习算法训练得到模型,再利用模型预测与训练样本集

同属一类的嵌入式软件的最优编译选项集合.训练样本集中的每个样本以某一嵌入式软件作为输入,并使用迭

代编译的方法找到的最优编译选项集合作为输出.同类型的多个嵌入式软件及它们的最优编译选项集合组成

了机器学习方法的训练样本集.然而,一些研究工作

[10,11]

已经实证了迭代编译方法不能在庞大的空间中找到最

优编译选项集合.受制于训练样本自身的质量,使得机器学习方法得到的模型难以准确预测出真正的最优编译

选项集合.

基于演化算法的方法

[5,11−14]

将编译时能耗优化问题抽象成一个编译选项选择优化问题,并针对特定的嵌入

式软件和特定的执行平台搜索更大的编译选项选择空间,为进一步降低能耗提供了有力支持.Hoste 等人运用传

统遗传算法(genetic algorithm,简称 GA)

[5,11]

获取了比迭代编译和编译器预设的最高优化等级更好的编译选项

集合.为了进一步提高解的质量和加快算法的收敛速度,Lin,Nagiub 和 Garciarena 又提出了一些新的演化算法.

Lin 等人

[12]

设计了一种基因加权的遗传算法,通过对上一代种群中适应度值高的个体所选择的编译选项加权,

以影响变异概率,从而加快了收敛速度.Nagiub 等人

[13]

通过设计新的 pass-over 算子,将上一代种群中适应度优

的个体直接加入到下一代种群,利用保留优势解的策略进一步加快了算法的收敛速度.但 Lin 等人和 Nagiub 等

of 19

免费下载

软件学报计算机技术

关注

评论