基于机器学习的编译优化适应性研究

论文摘要

编译器的开发者所面对的各种编译优化常常都是非常复杂的，甚至是NP问题。所以编译器开发者会从复杂问题中抽取出多个属性来构建模型去描述目标优化，以期得到近优解。但是在实际开发中，所构建的模型可能没有全面准确描述目标优化，或者构建的模型对需要编译的目标程序描述不够合理而无法得到期望的性能，这需要我们有针对性地修改目标优化。另一方面，编译器所面向的硬件结构是非常复杂的，并且发展迅速。当硬件结构发生改变，编译优化也需要进行相应调整。这些都对编译优化的调优提出了多方面要求，编译优化适应性研究的出发点是如何让优化的调试过程自动进行，在有限的时间内寻找到更为合适的优化配置，包括优化选项的组合，优化模型的参数调整等。迭代编译和机器学习是常用的两种方法，本文中的研究都是基于机器学习展开，主要贡献如下： 1．提出基于静态分析的快速机器学习，这是一种基于遗传算法的机器学习。机器学习通常都是非常耗时的过程，如果采用程序的运行时间作为遗传算法中的适应值，对于CPU2000这样的大型程序来说，机器学习将花费好几天的时间。而基于静态分析的快速机器学习的主要思想是：在编译过程中收集优化生成的静态信息来作为机器学习的适应值；然后通过限定静态分析的热点区域，进一步减少静态分析的时间和空间开销，同时保证一定的精确度。最后，可以进一步添加部分动态时的信息，以增加机器学习的能力。 2．根据基于静态分析的快速机器学习思想，本文就寄存器分配提出了两种快速机器学习方法：溢出代码敏感的机器学习和溢出代码与热函数敏感的机器学习。溢出代码敏感的机器学习是将寄存器分配中产生的溢出代码作为活跃区间的权值函数的适应值，能大大降低时间开销，同时采用热文件来限定机器学习的范围，使其能较好地突出目标优化的作用。而溢出代码与热函数敏感的机器学习，其适应值为溢出代码加上profiling信息，这能更为准确描述溢出代码在程序中的分布和溢出代码对程序的影响。溢出代码与热函数敏感的机器学习仍然仅需要较少的时间开销，同时此机器学习被限定在热函数中，不但进一步缩小学习范围而且使学习热点更突出。 3．介绍如何基于ORC编译器构建溢出代码敏感的机器学习和溢出代码与热函数敏感的机器学习平台。并就这两种方法针对CPU2000这样的大型程序对ORC编译器中的寄存器分配进行了学习，其实验数据分析表明了这两种学习方法的有效性。 4．为了衡量不同基于静态分析的机器学习，我们提出了机器学习衡量模型effect。主要考虑两方面因素：适应值的变化和相应性能的变化。并就CPU2000的机器学习结果进行了衡量和分析。 5．为进一步弄清参与机器学习的各个优化因素在编译优化中的重要性和相互之间的关系，本文提出了基于粗糙集理论的机器学习信息挖掘。研究的目标为机器学习中生成的中间文件，其包含作为遗传基因的表达式及其相应的适应值。借助粗糙集理论中的

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 编译器与计算机体系结构
• 1.2 ORC编译器
• 1.3 龙芯编译器
• 1.4 编译优化适应性研究简述
• 1.4.1 迭代编译
• 1.4.2 机器学习
• 1.5 论文概述
• 1.6 论文组织结构
• 第二章 编译优化适应性研究背景
• 2.1 迭代编译
• 2.2 面向迭代编译的快速优化衡量方法
• 2.2.1 简介
• 2.2.2 动态稳定区域
• 2.2.3 编译插桩
• 2.2.4 衡量优化
• 2.2.5 实验结果
• 2.3 机器学习
• 2.4 Meta Optimization
• 2.4.1 权值函数
• 2.4.2 可变长的遗传基因
• 2.4.3 构建初始基因
• 2.4.4 计算适应值
• 2.4.5 学习流程
• 2.4.6 性能分析
• 2.5 本章小节
• 第三章 基于静态分析的快速机器学习
• 3.1 本章简介
• 3.2 优化衡量标准分析
• 3.2.1 运行时间作为衡量标准
• 3.2.2 基于静态分析的衡量标准
• 3.3 基于静态分析的快速机器学习框架
• 3.3.1 静态分析替代动态执行
• 3.3.2 选取热点区域
• 3.3.3 结合profiling的静态分析
• 3.4 面向寄存器分配的快速机器学习
• 3.4.1 溢出代码
• 3.4.2 溢出代码的权值函数
• 3.4.3 溢出代码敏感的机器学习
• 3.4.4 溢出代码与热函数敏感的机器学习
• 3.5 本章小节
• 第四章 面向ORC的快速机器学习平台实现和性能分析
• 4.1 Meta Optimization结构
• 4.2 驱动ORC进行机器学习
• 4.2.1 初始化和完成函数
• 4.2.2 替代权值函数
• 4.2.3 库函数关联
• 4.2.4 运行环境
• 4.2.5 机器学习主程序与编译器通讯协议
• 4.2.6 构建训练集合
• 4.2.7 表达式语法
• 4.3 热点函数和热点文件的输入格式
• 4.4 溢出代码敏感的机器学习实现
• 4.4.1 判断热点文件
• 4.4.2 构建适应值
• 4.5 溢出代码与热点函数敏感的机器学习
• 4.5.1 判断热点函数
• 4.5.2 构建适应值
• 4.6 基于静态分析的机器学习性能分析
• 4.6.1 机器学习配置与试验平台
• 4.6.2 CPU2000CINT热点函数与热点文件
• 4.6.3 学习时间分析
• 4.6.4 溢出代码敏感的机器学习适应值变化分析
• 4.6.5 溢出代码与热函数敏感的机器学习适应值分析
• 4.6.6 CPU2000CINT性能分析
• 4.7 本章小节
• 第五章 机器学习衡量模型
• 5.1 构建机器学习衡量模型的动机
• 5.2 基于静态分析的机器学习衡量模型
• 5.3 CPU2000CINT机器学习衡量分析
• 5.4 基于机器学习衡量模型的分析
• 5.5 本章小节
• 第六章 基于粗糙集的机器学习信息挖掘
• 6.1 粗糙集基本概念和理论
• 6.1.1 简介
• 6.1.2 粗糙集基本概念
• 6.1.3 约简与核
• 6.1.4 知识依赖性
• 6.1.5 属性重要性
• 6.1.6 决策表
• 6.2 数据预处理基本概念
• 6.2.1 连续值属性离散化
• 6.3 机器学习信息挖掘的动机和意义
• 6.4 整体框架
• 6.5 数据预处理
• 6.5.1 数据采样
• 6.5.2 属性选择及构建决策表
• 6.5.3 离散化
• 6.6 属性相对约简与求核
• 6.7 属性重要性
• 6.8 信息挖掘结果的应用展望
• 6.9 本章小节
• 第七章 结束语
• 7.1 本文主要贡献
• 7.2 下一步工作
• 参考文献
• 致谢
• 作者简历