嵌入式系统寄存器分配:启发式与进化算法

摘要

在信息和网络技术高速发展的后PC时代，嵌入式系统已经渗透到科学研究、工程设计等各个领域中。由于嵌入式系统更看重于应用，所以要求在嵌入式系统中经过编译后能得到高质量的代码。在嵌入式系统编译优化的过程中，最重要的部分是对嵌入式系统寄存器分配的优化，让尽可能多的中间变量保存在寄存器中有助于我们获得高质量的代码。本文在对嵌入式系统寄存器分配算法进行充分的研究的基础上，提出了基于最大团的嵌入式系统寄存器分配算法、基于分割图的嵌入式系统寄存器分配算法和基于Memetic算法的嵌入式系统寄存器分配方法。
　　 (1)提出了基于最大团的嵌入式系统寄存器分配算法。该算法引入补图思想，将中间变量相互干扰图取补图后，巧妙的使用寻找最大团操作，得到了一种很好的启发式算法，实验部分通过与经典的启发式算法进行对比，证实了基于最大团的嵌入式系统寄存器分配算法确实能得到更好的寄存器分配方案。
　　 (2)提出了基于分割图的嵌入式系统寄存器分配算法。在前一个创新点的基础上，引入分割图概念，细化寻找最大团的过程，充分的利用节点的溢出代价，并且引入局部搜索算子对寄存器分配的初步结果进行优化。实验部分通过与经典启发式算法以及两种进化算法对比，证实了基于分割图的嵌入式系统寄存器分配算法能够在较短的时间内得到非常好的寄存器分配方案，性能接近进化算法。
　　 (3)基于Memetic算法的嵌入式系统寄存器分配。通过对原有混合进化算法的交叉算子和评价函数的改进，得到了基于Memetic算法的嵌入式系统寄存器分配方法。在交叉算子中充分考虑了中间变量溢出代价的作用及影响，引入了一个新的适应度评价函数来判断种群个体的优劣，加强种群进化方向。实验部分通过与原进化算法对比，证实了确实对进化算法有明显改进。