遗传算法和关键事件禁忌搜索相融合的ARM/Thumb处理器指令选择

Instruction Selection for ARM/Thumb Processors Based on a Genetic Algorithm Coupled with Critical Event Tabu Search

面向嵌入式系统的编译器,往往需要同时考虑目标代码的性能、大小和功耗等相互冲突的目标.ARM双指令集处理器,在具备通常的32位ARM指令集基础上,还支持一个缩减的16位Thumb指令集,因而为代码优化提供了多个目标之间折衷的机会.由于同一个程序的Thumb代码比相应的ARM代码执行更多的指令,因此虽然前者常比后者占用更少的存储空间,但消耗更多的运行时间.针对这种现象,文中建议一个混合演化算法,通过把程序的不同部分有选择地编译成ARM或Thumb指令集代码,使得可灵活地权衡目标代码大小和运行时间.文中的方法基于遗传算法和关键事件禁忌搜索相融合,后者用来局部搜索.指令选择以函数为单位,从对程序动态行为的profiling分析求得程序运行时间.实验结果表明,文中的技术可有效地、灵活地权衡目标代码大小和性能,并且适用于其它的双指令集处理器.

In the embedded domain, not only performance, but also memory and energy are important concerns. A dual instruction set ARM processor, which supports a reduced Thumb instruction set with a smaller instruction length in addition to a full instruction set, provides an opportunity for a flexible tradeoff between these requirements. For a given program, typically the Thumb code is smaller than the ARM code, but slower than the latter, because a program compiled into the Thumb instruction set executes a larger number of instructions than the same program compiled into the ARM instruction set. Motivated by this observation, this paper proposes a hybrid evolutionary algorithm that can be used to enable a flexible tradeoff between the code size and execution time of a program by using the two instruction sets selectively for different parts of a program. The proposed approach is based on a genetic algorithm coupled with critical event Tabu Search as the local search. The instruction set is determined to be used for each function, and the execution time is got based on the profiling analyses of the dynamic behavior of a program. The experimental results show that the proposed technique can be effectively used to make the tradeoff between a program＇s code size and execution time and can provide much flexibility in code generation for dual instruction set processors in general.