嵌入式处理器寄存器分配的一种混合演化算法  

A Hyrid Evolutionary Algorithm for Register Allocation of Embedded Processors

作　　者：吴圣宁[1] 李思昆[1] 

机构地区：[1]国防科技大学计算机学院,长沙410073

出　　处：《计算机科学》2007年第8期278-280,共3页Computer Science

基　　金：国家自然科学基金(9027019);国家863计划(2002AA1Z1480)的资助

摘　　要：通用处理器的寄存器分配一般采用图着色的方法。除非考虑特例,优化的图着色是NP完全性问题。因此,传统寄存器分配常利用图着色的启发式算法,并能对规则的RISC处理器生成质量较高的代码。但由于嵌入式处理器不规则的体系结构特征,这种传统寄存器分配方法生成的代码质量不能满足嵌入式领域的要求。本文提出了一种新的遗传算法和局部搜索相混合的元启发式方法,能较好地克服传统寄存器分配的不足。实验结果表明,这种新的算法比传统图着色寄存器分配算法减少约30%spill代码。A popular approach to the register allocation problem is based on a graph model. Unless considering only special cases, optimal coloring is an NP-complete problem, so that traditional register allocators have to resort to heuristics and can give rather good code for RISC processors, but the quality of code generated by them cannot meet the requirements of embedded domain, due to irregular architectural features. This paper brings forth a recta-heuristic algorithm composed of a new genetic algorithm and local search, which can overcome the shortcomings of traditional register allocators. Experimental results show that this algorithm can reduce about 30% spill code, compared to traditional graph-coloring register allocators.

关 键 词：寄存器分配 演化算法 嵌入式处理器 

分 类 号：TP332[自动化与计算机技术—计算机系统结构]