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

论文摘要

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

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.2 嵌入式系统寄存器分配算法的研究现状
• 1.2.1 启发式算法
• 1.2.2 进化算法
• 1.3 论文的主要工作和安排
• 第二章 嵌入式系统寄存器分配的相关知识
• 2.1 问题模型
• 2.1.1 图着色问题
• 2.1.2 嵌入式系统寄存器分配模型
• 2.2 寄存器分配相关图论知识
• 2.2.1 补图
• 2.2.2 完全图
• 2.2.3 分割图
• 2.3 本章小结
• 第三章 基于最大团的嵌入式系统寄存器分配算法
• 3.1 基于最大团的嵌入式系统寄存器分配算法基本思想
• 3.2 算法实现
• 3.2.1 算法流程图
• 3.2.2 算法步骤
• 3.3 具体实例
• 3.4 实验结果
• 3.5 基于最大团的嵌入式系统寄存器分配算法缺陷分析
• 3.6 本章小结
• 第四章 基于分割图的嵌入式系统寄存器分配算法
• 4.1 基于分割图的嵌入式系统寄存器分配算法基本思想
• 4.2 算法实现
• 4.2.1 算法流程图
• 4.2.2 算法实现步骤
• 4.2.3 寻找最大团算法
• 4.2.4 冲突最小原则
• 4.2.5 局部搜索算法
• 4.2.6 适应度函数
• 4.3 具体实例
• 4.4 实验结果
• 4.4.1 随机图实验
• 4.4.2 benchmark实验
• 4.5 本章小结
• 第五章 基于Memetic算法的嵌入式系统寄存器分配
• 5.1 基于Memetic算法的嵌入式系统寄存器分配的基本思想
• 5.2 混合进化算法的实现步骤
• 5.2.1 混合进化算法的初始化
• 5.2.2 混合进化算法的免冲突交叉算子
• 5.3 Memetic算法的方法
• 5.3.1 Memetic算法的交叉算子
• 5.3.2 Memetic算法的适应度函数
• 5.4 实验结果
• 5.4.1 随机图实验
• 5.4.2 benchmark实验
• 5.5 本章小结
• 第六章 总结与展望
• 致谢
• 参考文献
• 作者在读期间的科研成果