2020, Vol. 29
2. 福建师范大学 福建省公共服务大数据挖掘与应用工程技术研究中心, 福州 350117;
3. 武汉纺织大学 数学与计算机学院, 武汉 430073
2. Fujian Provincial Engineering Technology Research Center for Public Service Big Data Mining and Application, Fujian Normal University, Fuzhou 350117, China;
3. College of Mathematics and Computer Science, Wuhan Textile University, Wuhan 430073, China
能耗是嵌入式系统的关键质量属性. 据报道[1], 在嵌入式系统中高达80%的能耗直接与软件执行活动密切相关. 因而在电量受限的执行环境中, 降低嵌入式软件的能耗具有更为重要的价值和意义[2]. 通过选择一组最佳编译选项[3]在给定的执行平台下对嵌入式软件源代码进行编译, 可以获取能耗更低的可执行代码. 与源代码重构[4]的能耗优化技术相比, 基于编译选项选择的优化不仅可以考虑硬件平台特性, 而且还能在不修改源代码的情况下保证功能语义一致性. 因此, 编译选项的选择优化为降低嵌入式软件能耗提供了一种可行且有效的解决方案.
开源编译器GCC[5]已广泛用于嵌入式系统的开发. 针对GCC编译器的编译选项选择优化问题可描述为: 对于源代码src和执行平台platform, 搜索选项选择方案X = < x1, x2,···, xi···, xl> (xi∈{0,1}分别表示不选用或选用第i号选项, l为可用的选项数), 使得目标函数
近年来, 在能耗优化这一方面, GCC 编译选项的选择问题已成为一个热门的研究话题[3], 但仍面临两个公开挑战. 一是GCC编译器提供了大量的编译选项, 构成了庞大且离散的选择空间. 例如针对Hoste 等[8]提出58 个常用于能耗优化的编译选项, 其对应的选择空间将高达258(大于1017). 另一挑战是编译选项之间、编译选项与能耗之间存在着潜在的复杂影响, 给提高搜索效率和优化质量带来相当大的困难. 一个编译选项的选用可能触发或使其它编译选项失效, 不同的编译选项对能耗所起的效用也不尽相同. 目前已涌现出统计、机器学习和演化算法等3类基于GCC编译选项选择的嵌入式软件能耗优化方法.
统计方法[2]使用部分析因实验设计技术搜索编译选项的选择空间. 正交数组被用于定义实验组和控制组, 通过曼-惠特尼检验或克鲁斯凯-沃利斯统计检验以观测能耗是否发生显著变化, 进而确定选用或不选用的选项. 统计方法不仅难以识别任意多个编译选项之间的影响, 而且受限于搜索空间也难以找到最优的编译选项组. 机器学习方法[3,9], 通过构建预测模型以帮助GCC编译器或优化算法搜索出最佳编译选项组. 构建预测模型分为收集训练样本和建立预测模型两个阶段. 收集训练样本阶段是一个迭代过程: 在每个迭代步中, 首先选择一个嵌入式软件并计算其特征的值; 接着基于一定策略在选项选择空间中采样获得多个选项组; 再利用一个选项组对所选择的嵌入式软件进行编译, 并通过执行获取能耗值. 基于软件的特征值、选项组和能耗值可构建出一个训练样本. 利用收集的训练样本集, 建模阶段则根据选用的机器学习算法[9]构建相应的预测模型. 为了增加嵌入式软件特征的有用性, 静态[10]、动态[11]和混合[12]等方法被用于确定具体的特征. 然而机器学习方法的训练样本往往针对特定编译器版本和特定执行平台, 所构建的预测模型可移植性差. 另外, 受制于选项的采样空间, 机器学习方法也难以获取高质量的优化结果.
为了搜索更大的编译选项选择空间, 提高能耗优化的质量, 一些演化优化算法也被纷纷提出. 基因加权的遗传算法GWGA[13]将权值关联到每个基因位, 用于刻画相应的编译选项对优化目标的重要性, 并在优化过程中进行更新. 与一元分布评估算法UMDA类似, GWGA仅考虑最优解中每个选项被选用的概率分布. GWGA虽能一定程度地加快收敛速度, 但因没有考虑各个选项之间存在相互影响关系, 容易导致陷入局部最优. Tree-EDA[14]运用概率树模型捕获任意两个编译选项之间的影响, 能得到比遗传算法(GA)、GWGA和UMDA更好的解质量. 为了考虑多个编译选项之间潜在的影响, 我们提出了基于频繁模式挖掘的遗传算法GA-FP[15]. GA-FP在演化过程中将相对于未优化前有改进效果的个体信息(包括选用的选项编号和获得的能耗改进)存入全局事务表, 并在每代种群演化结束后基于全局事务表挖掘频繁选项模式集, 接着利用频繁选项模式集中各个选项的能耗标注作为启发式信息设计了“增添”和“删减”两种单点变异算子, 进而得到了比Tree-EDA更好的解质量和收敛速度.
然而, GA-FP算法还存在一些不足: (1)在演化过程中始终固定以优化前能耗值作为参考点来判断个体是否有改进, 并将有改进效果的个体信息存入全局事务表中, 容易导致事务表规模过大、存储效率不高的问题. (2)基于全局事务表挖掘频繁选项模式, 不仅存在挖掘时间长的问题, 而且挖掘出的频繁选项模式也难以体现较好的时效性. 此外, 挖掘出的频繁选项模式仅给出单个频繁选项的能耗标注, 而多个频繁选项同时选用的次数和能耗标注也未予考虑. (3) “增添”和“删减”变异操作虽能充分利用单个频繁选项的能耗标注所体现的启发式信息进行单点变异, 但仍没有完全利用多个频繁选项同时选用的次数和能耗标注等启发式信息, 潜在地影响到解质量和收敛速度. 针对上述问题, 文中提出一种嵌入式软件编译时能耗演化优化算法GA-MFPM. GA-MFPM借助逐代替换参考点和事务表的机制以降低事务表大小; 在此基础上提出可获取更多启发式信息的繁编译选项挖掘算法, 并采用逐代挖掘的策略有利于保持频繁选项模式的时效性; 进一步设计最大频繁模式匹配算法进行多点变异, 以提高优化质量和收敛速度. 通过与GA-FP在5个不同领域的8个典型案例下实验对比的结果表明: GA-MFPM获取了较GA-FP更低的软件能耗(平均降低2.4%, 最高降低 16.1%)和更快的收敛速度(平均加快57.6%, 最高加快97.5%).
1 GA-MFPM算法总体流程GA-MFPM算法用于求解针对GCC编译器并用于嵌入式软件能耗优化的编译选项选择问题. 其总体流程(算法1)与遗传算法GA[16]类似. 但不同之处在于, GA-MFPM算法在演化过程中需构建和更新带能耗改进标注的事务表TTE (the Transaction Table with Energe annotations of options)、挖掘和更新带能耗改进标注频繁模式集表TPSFOE+(the Table of Pattern Set of Frequent Options with Energy annotations), 并基于TPSFOE+进行多点变异. 下面对它们作一简要介绍.
|
(1) 带能耗改进标注事务表的构建和更新
GA-MFPM算法利用每代种群中优势个体的信息构造事务表, 并逐代更新事务表.
在构造事务表时, 首先按适应度值f(Sftsrc, X)(能耗改进百分比)从小到大对种群中各个体X进行排序; 然后将适应度值等于或高于设定参考点值refVal的个体作为优势个体, 并把这些个体的信息存入事务表. GA-MFPM算法借鉴了多数EDA[17]中优势个体在种群中的占比, 将refVal设定为种群中各个体适应度值的中值. 算法1第4行构建初始事务表. 下面通过一个例子阐述事务表的构建方法.
例中, 初始种群各个体适应度的中值为8%, 即参考点值refVal=8%. 初始种群中有5个个体的适应度值等于或大于refVal, 现以其中的一个个体X, 其适应度的值f(Sftsrc , X)=10%为例说明一条事务的构建. 从图1所示的个体X可知其选用8个选项, 其编号为: {1, 2, 3, 6, 12, 13, 15, 16}. 依据这些选用的选项及其出现次数, 并将个体X的适应度值作为能耗标注附加于每个选用的选项, 可分别构建8个三元组(选用选项, 出现次数, 能耗标注), 如表1中第2行的事务. 类似地, 利用其它4个优势个体可分别构建4条事务, 进而获得表1所示的初始事务表.
|
图 1 个体X |
|
|
表 1 带能耗标注的选项事务表TTE的例子 |
GA-MFPM算法在每代演化中对事务表进行更新, 如算法1中第14行和15行. 与对比算法GA-FP在演化过程中始终固定以优化前能耗值作为参考点不同, GA-MFPM在演化过程中逐代替换参考点和事务表的机制有利于依据优势种群降低事务表大小.
(2)带能耗改进标注频繁模式集表的挖掘和更新
算法1第5行挖掘获取初始频繁选项模式集表TPSFOE+, 而算法1第17行至第18行完成在每代对模式集表TPSFOE+的更新. TPSFOE+的具体挖掘方法将在第2节予以详细阐述. 相比于GA-FP, GA-MFPM在当前代事务表中挖掘出的频繁选项模式可较好地保持频繁选项模式的时效性.
(3)启发式多点变异方法
算法1的第11行给出了基于模式集表TPSFOE+并通过设计的最大匹配算法对个体Xk进行多点变异. 较GA-FP的单点启发式变异, GA-MFPM的多点变异方法有利于提高收敛速度. 最大频繁模式匹配帮助的多点变异将在第3节进行重点阐述.
2 挖掘带能耗标注的频繁选项模式集下面先阐述带能耗改进频繁选项模式树FPE的构建, 然后给出挖掘带能耗改进标注频繁选项模式相关的定义, 最后结合例子描述带能耗标注频繁选项模式的挖掘算法FPE-growth+.
2.1 带能耗改进频繁选项模式树FPE的构建GA-MFPM中FPE树的数据结构及其构建过程与GA-FP类似. 依照表1事务表并在最小支持度计数Cmin=3下, 可构建出图2所示的FPE树. 为了便于理解本节内容, 下面对FPE树的数据结构作一简要介绍.
|
图 2 基于表1例子事务表TTE生成的FPE树 |
FPE树由前缀项树PT和项头表HL所构成. PT树中各结点用选项编号opNm、出现次数count、能耗标注engAno、指向父结点的指针parNode和指向下一个具有相同选项编号结点的指针nextNode五个域进行描述. 在图2椭圆形结点中, 用逗号分隔的是opNm、count和engAno的值, 而各结点的parNode和nextNode的值分别由实线和虚线弧隐含表示. 项头表HL中各表项由频繁选项编号opNm和结点链的头指针hdLnk两个属性表示. hdLnk可将相同选项通过结点链链接起来. 图2中项头表HL最后一行的hdLnk可将所有的2号选项结点链接起来.
基于FPE树, 可挖掘出所有带能耗标注的频繁选项模式. 下一小节将给出相关的定义.
2.2 挖掘带能耗改进标注频繁选项模式相关的定义定义1. 前缀路径. 若node为FPE树中的一个非根结点, 则从root根节点到node结点之间的一条路径称为node的前缀路径. 而node结点称为该前缀路径的后缀结点.
前缀路径可用一个结点序列进行表示. 图2中灰色背景结点为后缀的前缀路径path1可用式(1)的结点序列表示.
| $ \begin{array}{l} pat{h_1} = < \left( {6,4,41\% } \right),\left( {1,4,41\% } \right),\left( {3,3,33\% } \right),\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\left( {13,2,22\% } \right),\left( {16,2,22\% } \right) > \end{array} $ | (1) |
定义2. 条件前缀路径. 设path是后缀结点node的一条前缀路径. 若将path上各结点的支持计数和能耗标注分别修改为node的支持计数和能耗标注, 而获得的路径被称为node的条件前缀路径.
条件前缀路径用于表示前缀路径上各结点对应选项与后缀结点对应选项共同出现的次数及对应的能耗标注. 例如: path1为图2灰色背景结点node的前缀路径, 用node的支持计数1和能耗标注10%分别更新path1上各结点对应值, 可得到式(2)表示的node的条件前缀路径path2. 它表示选项集{6,1,3,13,16}共同出现1次且能耗标注为10%.
| $ \begin{array}{l} pat{h_2} = < \left( {6,{\rm{ }}1,{\rm{ }}10\% } \right),{\rm{ }}\left( {1,{\rm{ }}1,{\rm{ }}10\% } \right),\left( {3,1,10\% } \right),\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\left( {13,{\rm{ }}1,{\rm{ }}10\% } \right),{\rm{ }}\left( {16,{\rm{ }}1,{\rm{ }}10\% } \right) > \end{array} $ | (2) |
定义3. 频繁选项的条件前缀路径集. 若nodes是FPE树中所有i号频繁选项对应的结点集, 以nodes中各结点为后缀所得条件前缀路径的集合, 称为选项i的条件前缀路径集, 记为paths|i.
FPE树中i号频繁选项对应的全部结点可沿结点链的头指针hdLnk遍历获取. 图2中2号选项对应的结点集, 可通过头表HL最后一个表项的头指针hdLnk遍历结点链得到. 图2中2号选项的条件前缀路径集由path2, path3和path4所组成. 式(2)~式(4)分别给出了path2~path4的表示. 它们分别对应结点链中第1~3个结点的条件前缀路径.
| $ pat{h_3} = < \left( {6,1,{\rm{ }}11\% } \right),{\rm{ }}\left( {1,{\rm{ }}1,{\rm{ }}11\% } \right),{\rm{ }}\left( {3,{\rm{ }}1,{\rm{ }}11\% } \right) > $ | (3) |
| $ pat{h_4} = < \left( {3,1,{\rm{ }}10\% } \right),\left( {16,1,{\rm{ }}10\% } \right) > $ | (4) |
定义4. 条件事务表. 以i号频繁选项的条件前缀路径集paths|i中各路径为事务所构建的事务表, 称为i号频繁选项的条件事务表, 记作TTFE|i.
按图2中2号频繁选项的条件前缀路径集{path2, path3, path4}可构建表2所示的条件事务表.
|
|
表 2 图2中2号频繁选项的条件事务表 |
定义5. 条件FPE树. 以i号频繁选项的条件事务表TTE|i作为输入所构建的FPE树被称为频繁选项i的条件FPE树, 记为FPE |i.
按照表2的2号频繁选项条件事务表并在最小支持计数Cmin =3下, 可构建出图3所示的条件FPE树.
|
图 3 FPE-growth+以图2中2选项为后缀构建的条件FPE树 |
定义6. 频繁选项模式.
| $ engAno = \sum\limits_{{\rm{T_E}} \in {\rm{TT_E}} \wedge {S_{{\rm{op}}}} \subseteq \mathop \prod \nolimits^{\left( {\rm{T_E}} \right)} } {{{engImpr}}} \left( {\rm{T_E}} \right) $ | (5) |
对比算法GA-FP的频繁选项模式仅给出单个频繁选项的能耗标注, 而GA-MFPM则定义了多个频繁选项同时选用的次数和能耗标注. 因而, GA-MFPM包括了新的挖掘算法.
2.3 带能耗标注频繁选项模式的挖掘算法FPE-growth+FPE-growth+算法基于FPE树并采用模式项数渐增的递归挖掘方法, 其描述如算法2所示. FPE-growth+算法包括递归出口处理和循环递归处理两部分, 分别如算法2第2行至第8行、第10行至18行.
|
|
FPE-growth+算法的递归出口条件是当FPE树为单分支的树. 当满足出口条件时, 首先依据单分支路径上非根结点的序列, 枚举获得所有非空结点序列的集合SnodeSeq; 然后对SnodeSeq中每个元素nodeSeq重复做以下步骤: 将nodeSeq作为头部连接到后缀结点序列postFixNodes形成新序列newNodeSeq、计算序列newNodeSeq中各结点支持计数和能耗标注的最小值, 并用它们更新newNodeSeq序列中各结点的支持计数和能耗标注的值、基于newNodeSeq序列生成频繁选项模式fopE+并基于项数将fopE+存入模式集表的对应位置.
循环递归部分是依次对FPE树项头表HL的尾行至头行进行递归处理, 如算法2第10行至17行. 递归调用前需要构建新后缀结点序列postFixNodes并输出频繁选项模式、构建条件事务表、构建条件FPE树. FPE-growth+算法在挖掘频繁选项时, 采用与经典FP挖掘算法[18]相同的递归过程挖掘获取频繁选项. 仅在挖掘过程中增加了频繁选项的能耗标注的计算, 如算法2第5行和第13行. 而该步骤时间复杂性为O(1), 故FPE-growth+算法与经典FP算法相同.
图2所示FPE树是一棵多分支的树, 在利用FPE-growth+算法进行挖掘时, 由于不满足递归出口条件, 需要进入循环递归处理过程. 在循环中, 首先要以图2项头表最后一行的2号选项为后缀和空的后缀结点序列进行挖掘. 下面以此场景为例对FPE-growth+算法进行解释.
(1) 递归调用的处理
1) 构建新的后缀结点序列并输出频繁选项模式
沿图2头表最后一行的结点链头指针进行遍历可得2号频繁选项的支持计数和能耗标注分别为3和31%, 进而可构造一个新结点node(2, 3, 31%). 将node连接到当前后缀结点序列postFixNodes时, 由于postFixNodes为空序列, 故连接后得到的postFixNodes=<(2, 3, 31%)>. 根据postFixNodes生成的频繁选项模式fopE+(1)=({2}, 3, 31%), 可将其输出到模式集表TPSFOE+的1频繁选项集中.
2) 构建条件事务表
2号频繁选项为后缀的条件事务表
3) 构建条件FPE树
根据条件事务表TTE|2构建条件频繁模式树FPE|2已在定义5中的例子给出, 如图3所示. 以FPE|2和postFixNodes=<(2, 3, 31%)>递归调用FPE-growth+时, 由于FPE|2树为一单路径树满足递归出口条件, 进行递归出口处理.
(2) 递归出口中的处理
1) 枚举获得所有非空结点序列的集合SnodeSeq
由于图3的FPE|2树中仅含一个非根结点node(3, 3, 31%), 故枚举生成的SnodeSeq={<(3, 3, 31%)>}.
2) 对SnodeSeq中各元素nodeSeq重复执行以下3个步骤:
① nodeSeq与后缀结点序列连接获取新序列newNodeSeq
SnodeSeq中仅包含的一个序列与postFixNodes=<(2, 3, 31%)>连接后生成新序列newNodeSeq={<(3, 3, 31%)>, (2, 3, 31%)}.
② 更新序列newNodeSeq中各结点支持计数和能耗标注
由于newNodeSeq各结点的支持计数和能耗标注相同, 故更前新后的newNodeSeq序列相同.
③ 依据newNodeSeq序列生成频繁选项模式并输出
根据序列newNodeSeq={<(3, 3, 31%)>, (2, 3, 31%)}可生成频繁选项模式fopE+(2)=({3, 2}, 3, 31%), 可将其输出到模式集表TPSFOE+的2频繁选项集中.
以图2的FPE树和空的后缀结点序列为参数, 调用FPE-growth+算法最终输出表3所示的模式集表TPSFOE+.
|
|
表 3 例子带能耗标注的频繁选项模式集表TPSFOE+ |
3 最大频繁选项模式匹配帮助的多点变异
不同于GA-FP中的单点变异, GA-MFPM采用最大频繁选项模式匹配帮助的多点变异. 多点变异的流程如算法3所示. 其主要包括确定变异的位数和位置、最大频繁选项模式匹配、修改变异位值等3个步骤. 下面以图4个体X2={1,1,0,0,0,0,0,0,0,0,0,1,1,0,1,1}和表3的为例, 阐述最大频繁选项模式匹配帮助的多点变异操作流程.
|
|
|
图 4 待变异的个体X2 |
(1)确定变异的位数和位置
确定变异的位数和位置如算法3的第2行至第4行. 为了能基于模式集表TPSFOE+提供的启发式信息进行变异, 规定最多变异的位数不超过TPSFOE+中频繁选项模式的最大项数. 利用产生随机数完成变异的位数和位置的确定. 每个变异位置对应于一个选项编号, 进而得到一个选项编号集S0, 假设例中得到的S0={2, 1, 6}.
(2)最大频繁选项模式匹配
最大频繁选项模式匹配是指将给定的选项编号集S0与TPSFOE+表中各模式的选项编号集进行最大匹配. 通过最大匹配可发现编号集S0中频繁出现在优势个体中最长的编号集.
算法3第5行至第10行描述了最大频繁选项模式匹配的匹配过程:
① 首先基于频繁选项模式所具有的向下闭包性质[18](k频繁选项集的任何子集都应是频繁的), 在TPSFOE+表的1频繁选项模式集SFOPE+(1)中, 将各模式的1个编号与S0中的编号进行匹配, 并将匹配的编号放入S1中, 进而获取S0中频繁的选项编号, 例中获取的S1={2,1,6}.
② 然后调用算法4的最大频繁模式匹配算法MFPM. MFPM算法将输入的选项编号集赋给Stemp后, 从大小为|Stemp|的频繁选项模式集SFOPE+(|Stemp|)开始对Stemp进行最大匹配, 若能匹配上则将匹配结果放入结果频繁选项模式集Sfop中并退出匹配过程, 否则在SFOPE+(Stemp–1)中进行最大匹配; 直至Stemp为空结束匹配. 例中首先在3频繁选项模式集上对Stemp={2, 1, 6}进行第1轮最大匹配, 没有任何匹配的频繁模式. 因而在2频繁选项模式集上对Stemp={2,1,6}进行第2轮最大匹配, 获取了频繁模式集Sfop ={ ({6,1},4, 41%)}.
|
|
(3)修改变异位值
算法3第7行至第11行负责完成个体中变异位值的修改. 首先, 将个体X2赋给X2', 并以S0 (存放随机生成的各变异位置)中各元素值为下标, 将X2'对应位的值设为0. 例中由S0={2, 1, 6}, 可知X2'的第2, 1, 6位上的值均设为0. 然后, 若基于最大匹配得到频繁模式集Sfop不空, 则按Sfop中各元素的平均能耗标注(engAno/count), 依概率选择其中一个频繁模式fopE+, 并以fopE+的选项编号集中各元素值为下标, 将X2'对应位的值设为1.
例中最大匹配获取的Sfop ={({6,1},4, 41%)}不为空, 因Sfop只有一个频繁二项集, 则fopE+={{6,1},4, 41%)}因而再将X2'第1和第6位上的值设定为1. 最终X2'应如图5所示, 本例中编号2和6位上的值发生变异, 即2号选项由选用变为不选用, 而6号选项由不选用变为选用.
|
图 5 变异后的个体X2' |
4 案例研究
本节给出了案例研究. 4.1节简介了实验案例; 4.2节提出了要验证的问题及度量标准; 4.3节说明了实验中使用的统计方法; 4.4节介绍了实验安装; 4.5节展示了实验结果并进行了分析.
4.1 案例简介本文从最新的BEEBS平台[6]中选用了8个案例, 如表4所示, BEEBS是目前最大的用于嵌入式系统执行时间和能耗优化的开源基准平台. 综合考虑以下3个要素, 从BEEBS所包含的84个案例中选取了具有代表性的8个案例.
|
|
表 4 实验案例的应用领域、源代码的结构特性和操作特性 |
(1)源代码的操作特性: 案例涵盖尽可能影响运行时能耗的各种不同操作. 如整型运算强度、浮点运算强度、分支频度和内存访问频度等.
(2)应用领域: 案例覆盖尽可能多的领域. 如汽车、消费、网络、安全和通讯等.
(3)源代码的结构特性: 由于基准测试的编译和大量的编译选项的存在会极大地影响上述案例的编译效率, 所以在基准测试源代码中也会有一系列影响编译过程的特性. 其中包括: 循环、嵌套循环、不同的算术类型(8位、16位和32位整型、浮点型等)、函数调用、字符串操作、位操作和数组访问. 表4给出了选用的8个案例的应用领域、源代码的结构特性和操作特性.
4.2 研究问题及其度量指标问题1. 解质量: 本文GA-MFPM算法较GA-FP算法能否得到更优的编译选项组合, 使得案例的运行能耗更低? GA-FP是目前以能耗为优化目标并可获取较优编译选项组合的一种算法. 通过回答这一问题, 可以验证GA-MFPM算法的有用性.
| $ {I_{eng\% }}(S\!\!f{t_{\rm{src}}}) \!=\! \frac{{f\left( {S\!\!ft_{\rm{src}},X_{\rm{GA - MFPM}}^*} \right) \!-\! f\left( {S\!\!ft_{\rm{src}},X_{\rm{GA - FP}}^*} \right)}}{{f\left( {S\!\!ft_{\rm{src}},X_{\rm{GA - FP}}^*} \right)}} $ | (6) |
问题2. 收敛速度: 与GA-FP算法比, GA-MFPM算法能否加快收敛速度? 通过回答这一问题进一步验证GA-MFPM算法的有效性.
度量指标: 为了公平比较两种算法的收敛速度, 将GA-MFPM相对于GA-FP首达最优时间的减少百分比I△t%作为度量指标. 在案例源代码Sftsrc下, I△t%的定义如式(7)所示, 其值越大越好. 式(7)中MinTGA-FP(Sftsrc,
| $\begin{aligned} &{I_{\Delta {\rm{t\% }}}}(S\!f{t_{\rm{src}}}) =\\ & \frac{{Min{T_{\rm{GA - FP}}}\left( {S\!f{t_{\rm{src}}},{X^*}} \right) - Min{T_{\rm{GA - MFPM}}}\left( {S\!f{t_{\rm{src}}},{X^*}} \right)}}{{Min{T_{\rm{GA - FP}}}\left( {S\!f{t_{\rm{src}}},{X^*}} \right)}} \end{aligned} $ | (7) |
由于演化算法具有随机性, GA-MFPM和GA-FP算法被分别独立运行20次, 并进行统计检验. 为了对实验数据进行统计分析, 本文采用了Wilcoxom秩和检验[19]方法, 并将置信水平α的值设置为 0.05. 为了进一步观测对比数据的差异程度(effect size), 本文还使用Vargha-Delaney[19]的
(1)实验环境
上位机的运行环境: Intel(R) Core(TM)i5-4590, 3.30 GHz处理器, 8 GB内存及Ubuntu-16.04.1操作系统.
能耗评估系统: 基于STM32F4板自主研发.
案例软件优化的运行环境: STM32F103板.
编译器和编译选项: GCC4.9.2, 并选用与GA-FP[15]相同的58个编译选项.
(2)算法参数的设定
为了保持公平, 尽可能让GA-MFPM采用与GA-FP相同的参数设定, 如表5所示. 但两个算法的最小支持计数设定有所不同. 这是因为GA-MFPM采用逐代替换事务表的策略. 在事务表中, 若每个选项按随机方式选用, 则每个选项出现的次数应为种群大小N的一半. 而GA-MFPM期望跟踪各代种群中优势个体选用选项的特点, 故将Cmin设定为0.6×N. 而不是GA-FP中设定的0.1倍全局事务表大小.
|
|
表 5 GA-FP和GA-MFPM的参数设定 |
4.5 实验结果及分析
下面具体给出各问题的实验结果及分析.
(1)问题1(解质量)的实验结果及分析.
表6给出了GA-MFPM在这8个案例下对比GA-FP的能耗改进百分比(I△eng%)的秩和检验结果. 从表6中第2列可知p-value值都远比置信水平0.05要小, 这表明GA-MFPM的I△eng%指标在这8个案例下的统计意义显著比GA-FP的好. 从表6中第3列可看出在这8个案例下, GA-MFPM算法的effect size值以很明显的优势优于GA-FP. 而从图6所示的统计盒图也能直观反映出一致结论. 从表7的统计量结果能知道: 8个案例下的I△eng%指标平均值为2.4%, 最大I△eng%指标值可达16.1%.
|
|
表 6 GA-MFPM较GA-FP在8个案例下能耗改进百分比(I△eng%)的秩和检验结果 |
|
图 6 GA-MFPM较GA-FP在8个案例下能耗改进百分比(I△eng%)的统计盒图 |
|
|
表 7 GA-MFPM较GA-FP在8个案例下能耗改进百分比(I△eng%)的统计量结果 |
GA-MFPM较GA-FP获取更好解质量的原因是: GA-MFPM在逐代挖掘的频繁模式中保存了多个频繁选项, 同时标注选用次数和能耗, 可获取更完整、时效性更好的启发式信息, 有利于帮助提高解质量.
(2)问题2(收敛速度)的实验结果及分析.
表8给出了在8个案例下收敛速度指标I△t% (相对于GA-FP, GA-MFPM首达最优解耗时的相对减少百分比)的秩和检验结果. 表8中第2列p-value值都远比置信水平0.05要小, 表明GA-MFPM的I△t%指标在8个案例下的统计意义显著比GA-FP的好. 表8中GA-MFPM首达最优解较GA-FP在大概率上需要更少的时间. 表9可知: 8个案例下的I△t%指标平均值为57.6%, 最大达到了97.5%. 图7所示的统计盒图也能直观反映出一致结论.
|
|
表 8 在8个案例下收敛速度指标I△t% (GA-MFPM相对于GA-FP首达最优解耗时的减少百分比)秩和检验结果 |
|
|
表 9 在8个案例下收敛速度指标I△t% (GA-MFPM相对于GA-FP首达最优解耗时的减少百分比)的统计量结果 |
|
图 7 在8个案例下收敛速度指标I△t% (GA-MFPM相对于GA-FP首达最优解耗时的减少百分比)的统计盒图 |
GA-MFPM较GA-FP获取更好的收敛速度的原因在于: GA-MFPM逐代替换参考点的机制可有效降低事务表的大小、借助最大频繁模式匹配帮助的多点变异可提高变异效率, 进而有利于帮助提高收敛速度.
5 结语本文将频繁模式挖掘和最大频繁模式匹配帮助的多点变异引入到传统遗传算法, 提出了一种用于GCC编译时能耗演化优化算法GA-MFPM. GA-MFPM采用逐代替换判定是否有能耗改进的参考点、逐代构建事务表和逐代挖掘的策略; 在此基础上提出可获取更多启发式信息的频繁编译选项挖掘算法; 进一步设计了最大频繁模式匹配帮助的多点变异方法. 通过案例研究实证了GA-MFPM的解质量和收敛速度在统计意义上显著优于已有的GA-FP算法. 未来我们将引入代理模型解决GA-MFPM算法中目标值计算耗时长的问题.
| [1] |
Georgiou K, Xavier-de-Souza S, Eder K. The IoT energy challenge: A software perspective. IEEE Embedded Systems Letters, 2018, 10(3): 53-56. DOI:10.1109/LES.2017.2741419 |
| [2] |
Pallister J, Hollis SJ. Bennett J. Identifying compiler options to minimize energy consumption for embedded platforms. The Computer Journal, 2015, 58(1): 95-109. DOI:10.1093/comjnl/bxt129 |
| [3] |
Ashouri AH, Killian W, Cavazos J, et al. A survey on compiler autotuning using machine learning. ACM Computing Surveys, 2019, 51(5): 96. |
| [4] |
Petke J, Haraldsson SO, Harman M, et al. Genetic improvement of software: A comprehensive survey. IEEE Transactions on Evolutionary Computation, 2018, 22(3): 415-432. DOI:10.1109/TEVC.2017.2693219 |
| [5] |
Using the GNU Compiler Collector (GCC). https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html.
|
| [6] |
Pallister J. Exploring the Fundamental Differences between Compiler Optimisations for Energy and for Performance[Ph. D. Thesis]. Bristol: University of Bristol, 2016.
|
| [7] |
Nobre R, Reis L, Cardoso JMP. Compiler phase ordering as an orthogonal approach for reducing energy consumption. Proceedings of the 19th Workshop on Compilers for Parallel Computing. Valladolid, Spain. 2016.
|
| [8] |
Hoste K, Eeckhout L. Cole: Compiler optimization level exploration. Proceedings of the 6th Annual IEEE/ACM International Symposium on Code Generation and Optimization. Boston, MA, USA. 2008. 165–174.
|
| [9] |
Wang Z, O’Boyle M. Machine learning in compiler optimization. Proceedings of the IEEE, 2018, 106(11): 1879-1901. DOI:10.1109/JPROC.2018.2817118 |
| [10] |
Leather H, Bonilla E, O’Boyle M. Automatic feature generation for machine learning based optimizing compilation. Proceedings of 2009 International Symposium on Code Generation and Optimization. Seattle, WA, USA. 2009. 81–91.
|
| [11] |
Ashouri AH, Mariani G, Palermo G, et al. A Bayesian network approach for compiler auto-tuning for embedded processors. Proceedings of 2014 IEEE 12th Symposium on Embedded Systems for Real-time Multimedia. Greater Noida, India. 2014. 90–97.
|
| [12] |
Ashouri AH, Mariani G, Palermo G, et al. COBAYN: Compiler autotuning framework using Bayesian networks. ACM Transactions on Architecture and Code Optimization, 2016, 13(2): 21. |
| [13] |
Lin SC, Chang CK, Lin NW. Automatic selection of GCC optimization options using a gene weighted genetic algorithm. Proceedings of 2008 13th Asia-Pacific Computer Systems Architecture Conference. Hsinchu, China. 2008. 1–8.
|
| [14] |
Garciarena U, Santana R. Evolutionary optimization of compiler flag selection by learning and exploiting flags interactions. Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion. Denver, CO, USA. 2016. 1159–1166.
|
| [15] |
倪友聪, 吴瑞, 杜欣, 等. 基于频繁模式挖掘的GCC编译时能耗演化优化算法. 软件学报, 2019, 30(5): 1269-1287. DOI:10.13328/j.cnki.jos.005734 |
| [16] |
Holland JH. Genetic algorithms. Scientific American, 1992, 267(1): 66-73. DOI:10.1038/scientificamerican0792-66 |
| [17] |
Hauschild M, Pelikan M. An introduction and survey of estimation of distribution algorithms. Swarm and Evolutionary Computation, 2011, 1(3): 111-128. DOI:10.1016/j.swevo.2011.08.003 |
| [18] |
Han JW, Pei J, Yin YW. Mining frequent patterns without candidate generation. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. Dallas, TX, USA. 2000. 1–12.
|
| [19] |
Arcuri A, Briand L. A practical guide for using statistical tests to assess randomized algorithms in software engineering. Proceedings of 2011 33rd International Conference on Software Engineering. Honolulu, HI, USA. 2011. 1–10.
|