电子学报 ›› 2009, Vol. 37 ›› Issue (2): 372-376.

• 论文 • 上一篇    下一篇

基于差分进化和贪心策略的自定义指令选择算法研究

周学海, 纪金松, 张 敏   

  1. 中国科学技术大学计算机系,安徽合肥 230027
  • 收稿日期:2008-01-21 修回日期:2008-05-19 出版日期:2009-02-25 发布日期:2009-02-25

Study on Differential Evolution and Greedy Strategy Based Custom Instruction Selection Algorithms

ZHOU Xue-hai, JI Jin-song, ZHANG Min   

  1. Department of Computer Science,University of Science and Technology of China,Hefei,Anhui 230027,China
  • Received:2008-01-21 Revised:2008-05-19 Online:2009-02-25 Published:2009-02-25

摘要: 本文针对常见启发式算法中忽略指令与指令实例区别的问题,改进了一个已有启发式算法GreedyHeur:根据指令实例的启发式函数值得出相应指令的权值,并根据指令的优先级关系以贪心策略进行指令实例选择.针对启发式算法无法找到最优解的问题,本文引入基于群体搜索的差分进化算法,并结合贪心策略,提出了ISDE(Instruction Selection Based on Differential Evolution)算法.ISDE算法通过简单的编码和高效的适应度评价机制,快速地迭代搜索最优指令组合.实验结果表明,GreedyHeur和ISDE算法能快速有效地找到比已有启发式算法更优的候选指令组合.

关键词: 差分进化算法, 贪心策略, 指令集扩展, 指令选择

Abstract: As heuristic algorithms usually omit the difference between instruction and instruction instance,we improved one existing heuristic algorithm to GreedyHeur algorithm.It calculates custom instructions’ weights from their instruction instances,then select custom instruction instances with greedy strategy according to their instructions’ weights.To find better custom instruction than heuristic algorithms,we introduced an algorithm(ISDE)integrating greedy strategy with differential evolution algorithm.Simple encoding and efficient fitness evaluation help ISDE find the best combination of custom instructions quickly.Experiments show that our algorithms can find better custom instruction candidates more quickly and efficiently than heuristic algorithm.

Key words: differential evolution algorithm, greedy strategy, instruction set extension, instruction selection

中图分类号: