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

发布时间：2018-06-03 15:26

本文选题：嵌入式系统 + 寄存器分配　；参考：《西安电子科技大学》2012年硕士论文

【摘要】：在信息和网络技术高速发展的后PC时代,嵌入式系统已经渗透到科学研究、工程设计等各个领域中。由于嵌入式系统更看重于应用,所以要求在嵌入式系统中经过编译后能得到高质量的代码。在嵌入式系统编译优化的过程中,最重要的部分是对嵌入式系统寄存器分配的优化,让尽可能多的中间变量保存在寄存器中有助于我们获得高质量的代码。本文在对嵌入式系统寄存器分配算法进行充分的研究的基础上,提出了基于最大团的嵌入式系统寄存器分配算法、基于分割图的嵌入式系统寄存器分配算法和基于Memetic算法的嵌入式系统寄存器分配方法。 (1)提出了基于最大团的嵌入式系统寄存器分配算法。该算法引入补图思想,将中间变量相互干扰图取补图后,巧妙的使用寻找最大团操作,得到了一种很好的启发式算法,实验部分通过与经典的启发式算法进行对比,证实了基于最大团的嵌入式系统寄存器分配算法确实能得到更好的寄存器分配方案。 (2)提出了基于分割图的嵌入式系统寄存器分配算法。在前一个创新点的基础上,引入分割图概念,细化寻找最大团的过程,充分的利用节点的溢出代价,并且引入局部搜索算子对寄存器分配的初步结果进行优化。实验部分通过与经典启发式算法以及两种进化算法对比,证实了基于分割图的嵌入式系统寄存器分配算法能够在较短的时间内得到非常好的寄存器分配方案,性能接近进化算法。 (3)基于Memetic算法的嵌入式系统寄存器分配。通过对原有混合进化算法的交叉算子和评价函数的改进,得到了基于Memetic算法的嵌入式系统寄存器分配方法。在交叉算子中充分考虑了中间变量溢出代价的作用及影响,引入了一个新的适应度评价函数来判断种群个体的优劣,加强种群进化方向。实验部分通过与原进化算法对比,证实了确实对进化算法有明显改进。
[Abstract]:In the post - PC era of high - speed development of information and network technology , the embedded system has been infiltrated into various fields such as scientific research and engineering design . In the process of compilation and optimization of embedded system , it is required to obtain high - quality code in embedded system . In the process of compilation and optimization of embedded system , the most important part is to optimize the register allocation of embedded system .

( 1 ) An embedded system register allocation algorithm based on the maximum clique is proposed . The algorithm introduces the complementary graph idea . After the intermediate variables are disturbed with each other , a good heuristic algorithm is obtained . The experimental part is compared with the classical heuristic algorithm , which proves that the embedded system register allocation algorithm based on the maximum cluster can get a better register allocation scheme .

( 2 ) An embedded system register allocation algorithm based on partition diagram is proposed . On the basis of the previous innovation point , we introduce the concept of segmentation map , refine the process of finding the largest cluster , fully utilize the overflow cost of the node , and introduce the local search operator to optimize the initial results of register allocation .

( 3 ) An embedded system register allocation method based on the Memetic algorithm is proposed . Based on the improvement of the crossover operator and the evaluation function of the original hybrid evolutionary algorithm , an embedded system register allocation method based on the Memetic algorithm is obtained . In the crossover operator , the function and influence of the overflow cost of the intermediate variable are fully taken into account , and a new fitness evaluation function is introduced to judge the population individual ' s advantages and disadvantages and to strengthen the population evolution direction .
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP368.1

【共引文献】