基于计算博弈论的空间优化研究

在嵌入式系统特别是SoC系统中，存储器的大小对芯片的成本影响非常大，因此对程序的空间优化的需要远远强于对时间（效率）优化的需求。目前国内外在编译优化技术中对空间优化方面的研究开展不多，一般只是针对某一种芯片研究与平台相关的空间优化技术。本课题针对嵌入式系统对空间优化的需求，拟利用计算博弈论的理论基础与研究成果，在通用的空间优化方面展开研究，研究内容主要包括两个方面：1）数据空间的优化技术，研究基于博弈论的寄存器分配与内存分配技术，提高数据空间的使用效率；2）控制流指令冗余的优化技术，针对嵌入式系统中常见的一些体系结构，将控制流指令冗余的优化问题抽象为博弈问题，设计算法消除程序中的冗余代码。本课题的研究成果将在课题组已搭建的编译器环境与大量的实际嵌入式系统的实例上进行实验，使得研究成果不仅具有理论意义，而且具有明显的应用价值。

本课题针对嵌入式系统对空间优化的需求，利用计算博弈论的方法，在空间优化方面展开研究。.本课题的研究成果主要包含以下几个方面：1）面向空间优化的标准测试集：根据实际的嵌入式系统提取出基于图的测试程序集；2)数据空间覆盖算法：在无递归的程序（嵌入式软件中的常见约束条件）上研究过程局部数据的覆盖方法，减少内存的使用；3)基于计算博弈论的寄存器分配算法，针对嵌入式系统中的较少寄存器数目的CPU提出基于博弈的分配算法，降低目标代码的指令数。4）针对分区内存体系结构的冗余指令消除算法，降低代码生成中的冗余指令。包括启发式算法与博弈算法。