监督学习模型指导的函数级编译优化参数选择方法研究

基于机器学习的迭代编译方法可以在对新程序进行迭代编译时,有效预测新程序的最佳优化参数组合。现有方法在模型训练过程中存在优化参数组合搜索效率较低、程序特征表示不恰当、预测精度不高的问题。因此,基于机器学习的迭代编译方法是当前迭代编译领域内的一个研究热点,其研究挑战在于学习算法选择、优化参数搜索以及程序特征表示等问题。基于监督学习技术,提出了一种程序优化参数预测方法。该方法首先通过约束多目标粒子群算法对优化参数空间进行搜索,找到样本函数的最佳优化参数;然后,通过动静结合的程序特征表示技术,对函数特征进行抽取;最后,通过由函数特征和优化参数形成的样本构建监督学习模型,对新程序的优化参数进行预测。分别采用k近邻法和softmax回归建立统计模型,实验结果表明,新方法在NPB测试集和大型科学计算程序上实现了较好的预测性能。     

结合模型和迭代编译优化矩阵相乘程序

高性能计算应用程序获得的持续性能与机器峰值性能的差距日益扩大,很大程度上制约着高性能计算的发展。程序变换通过对程序进行适应机器体系结构特征的优化变换,提高程序实际执行性能,是解决该问题的有效途径之一。很多高级程序变换均具有数值参数,为了获得最优性能,需要仔细选择参数的值。传统的编译器使用简单的模型选择这些参数,难以适应日趋复杂的硬件平台和应用程序。迭代编译通过生成不同的程序版本并在实际硬件评估上运行程序,来评估关键优化参数的值并决定能够产生最优性能的值,显著优于静态方法,但巨大的优化开销限制了其应用范围。本文针对矩阵相乘程序提出一种结合性能模型和迭代编译的优化方法,利用基于对机器体系结构和程序的经验知识构造性能模型约束优化空间,并使用遗传算法加速在优化空间中寻找优秀解的过程。实验结果表明,该方法可以较低的开销获得更优的性能优化效果。     

一种基于增量式实例学习的迭代编译方法

为提高编译器的自适应性,以应对复杂的体系结构,提出一个结合迭代编译和机器学习的编译框架。编译器可将在优化空间中搜索到的最佳编译选项信息保存到知识库中,并能从知识库中学习获得适合当前程序的最佳编译选项。实例学习算法具有增量式的特点,可有效利用编译过程中积累的数据。通过避免冗余实例入库以及从库中剔除噪声实例,保证学习的精度与效率。     

多面体表示技术及在程序性能优化中的应用

多面体表示技术提供一种统一化的方式来表示程序变换和程序变换组合,有利于最优程序变换的搜索。论文首先介绍并评价了几种典型的多面体表示方法,并详细介绍了Cohen提出的多面体表示模型;同时,对多面体表示在程序性能优化尤其是迭代编译中的应用进行了介绍和评价;最后,对多面体表示技术在迭代编译领域今后的发展方向做出了展望。     

迭代编译优化技术综述

首先介绍了迭代编译的基本概念,然后讨论了其起源与发展,对其研究现状进行综述,主要包括优化空间的表述、优化空间的开发与搜索以及对数据输入集的敏感度分析三个方面。然后分析了目前迭代编译技术中所存在的不足。最后指出了迭代编译的未来发展趋势。     

虚拟机中的编译优化技术

传统静态编译技术给虚拟机的性能带来了极大的挑战：首先,可移植的程序表示以及动态语言的特性（例如动态类加载）迫使多数优化都推迟到运行时进行,导致运行时增加了优化开销;第二,模块化设计的程序使得很多针对整个程序的过程间优化技术难以应用;最后,虚拟机在一些运行间服务上（如安全机制和自动内存管理）花费了大量的资源。为了解决这些问题,商品化的虚拟机厂商以及一些研究机构都花费了大量时间和精力在虚拟机上研究开发自适应优化系统。当前的主流虚拟机基本都包含了一些基层实现以便于来实现实时程序分析、动态编译以及基于反馈的动态优化技术。介绍了虚拟机中的编译优化技术的产生发展以及当前虚拟机中流行的动态优化技术。     

利用超级编译技术优化串行程序

现代的超标量和超流水线高速处理器通常都带有二级高速缓冲存储器，以及较多的快速寄存器。利用程序变换来改善程序性能，是当今编译技术研究的热门课题之一。本重点讨论了超级编译技术中的循环分布，交换，合并和ｓｔｒｉｐｍｉｎｉｎｇ对串行程序的优化应用和效果。     

反馈式编译优化在寄存器分配中的应用技术

寄存器分配技术是编译器最为关键的优化技术之一.反馈式编译优化是一种基于程序当前和以前运行时的趋势来改变程序以后执行动作的技术,它能够提供给寄存器分配一些有用的优化信息.在分析Open64编译器反馈式编译优化技术的基础上,基于ALPHA结构实现和扩展了反馈式编译优化在寄存器分配中的应用,获得了较好的优化性能.     

浅谈编译技术在软件开发中的地位

编译技术在计算机软件工程开发中的有不可代替的地位,它不光是一种语言生命的开始,还伴随着该语言功能的逐渐壮大.基于语言的软件设计想要更加完美,离不开编译技术.本文从编译技术的背景及软件工程开发的现状开始介绍,讲解了程序设计语言的基本编译过程,列举了基于编译技术的程序可视化,及编译技术在排版上的应用.     

基于面向对象技术的MiniC编译器的设计与实现

针对传统编译器过于抽象复杂的不足,本文提出MiniC实例语言,采用面向对象技术实现该语言的编译器。MiniC编译器可以演示复杂的程序分析过程,给出编译各阶段的详细分析结果,使编译原理中的抽象内容可视化。实际应用表明,MiniC编译器在促进人们对编译理论的理解和提高系统软件开发能力方面能够发挥重要作用。     

Data Flow Analysis as a General Concept for the Transport of Verifiable Program Annotations

Just-in-Time (JIT) compilation is frequently employed in order to speed-up the execution of platform-independent and dynamically extensible mobile code applications. Since the time required for dynamic compilation directly influences a program's execution time, JIT compilers usually utilize only simple and fast techniques for program analysis and optimization. To improve further the analysis and optimization process of such compilers program annotations can be used.However, mostly all current annotation approaches suffer from the fact that the verification of transmitted program information is time consuming and therefore will not be carried out on the consumer side of a mobile code system. In this paper, we present a verifiable annotation technique that is based on a well known iterative data flow algorithm and which can be used for the transmission of all program information that can be derived through data flow analysis. Preliminary measurements of compilation and verification time indicate that the presented technique seems to be implementable and therefore could be used as an all-purpose transportation technique for safe program annotations.     

Combined Selection of Tile Sizes and Unroll Factors Using Iterative Compilation

Loop tiling and unrolling are two important program transformations to exploit locality and expose instruction level parallelism, respectively. However, these transformations are not independent and each can adversely affect the goal of the other. Furthermore, the best combination will vary dramatically from one processor to the next. In this paper, we therefore address the problem of how to select tile sizes and unroll factors simultaneously. We approach this problem in an architecturally adaptive manner by means of iterative compilation, where we generate many versions of a program and decide upon the best by actually executing them and measuring their execution time. We evaluate several iterative strategies based on genetic algorithms, random sampling and simulated annealing. We compare the levels of optimization obtained by iterative compilation to several well-known static techniques and show that we outperform each of them on a range of benchmarks across a variety of architectures. Finally, we show how to quantitatively trade-off the number of profiles needed and the level of optimization that can be reached. In this way, we can reach high levels of optimization within 50 iterations.     

Milepost GCC: Machine Learning Enabled Self-tuning Compiler

Tuning compiler optimizations for rapidly evolving hardware makes porting and extending an optimizing compiler for each new platform extremely challenging. Iterative optimization is a popular approach to adapting programs to a new architecture automatically using feedback-directed compilation. However, the large number of evaluations required for each program has prevented iterative compilation from widespread take-up in production compilers. Machine learning has been proposed to tune optimizations across programs systematically but is currently limited to a few transformations, long training phases and critically lacks publicly released, stable tools. Our approach is to develop a modular, extensible, self-tuning optimization infrastructure to automatically learn the best optimizations across multiple programs and architectures based on the correlation between program features, run-time behavior and optimizations. In this paper we describe Milepost GCC, the first publicly-available open-source machine learning-based compiler. It consists of an Interactive Compilation Interface (ICI) and plugins to extract program features and exchange optimization data with the cTuning.org open public repository. It automatically adapts the internal optimization heuristic at function-level granularity to improve execution time, code size and compilation time of a new program on a given architecture. Part of the MILEPOST technology together with low-level ICI-inspired plugin framework is now included in the mainline GCC. We developed machine learning plugins based on probabilistic and transductive approaches to predict good combinations of optimizations. Our preliminary experimental results show that it is possible to automatically reduce the execution time of individual MiBench programs, some by more than a factor of 2, while also improving compilation time and code size. On average we are able to reduce the execution time of the MiBench benchmark suite by 11% for the ARC reconfigurable processor. We also present a realistic multi-objective optimization scenario for Berkeley DB library using Milepost GCC and improve execution time by approximately 17%, while reducing compilation time and code size by 12% and 7% respectively on Intel Xeon processor.     

申威众核处理器访存与通信融合编译优化

申威众核片上多级存储层次是缓解众核“访存墙”的重要结构.完全由软件管理的SPM结构和片上RMA通信机制给应用性能提升带来很多机会,但也给应用程序开发优化与移植提出了很大挑战.为充分挖掘片上存储层次特点提升应用程序性能,同时减轻用户编程优化负担,本文提出了一种多级存储层次访存与通信融合的编译优化方法.该方法首先设计了融合编译指示,将程序高层信息传递给编译器.其次构建了编译优化收益模型并设计了启发式循环优化方案迭代求解框架,并由编译器完成循环优化方案的求解和优化代码的变换.通过编译生成的DMA和RMA批量数据传输操作,将较低存储层次空间中高访问延迟的核心数据批量缓冲进低访问延迟的更高存储层次空间中.在三个典型测试用例上进行了优化实验测试与分析,结果表明本文所提出的优化在性能上与手工优化相当,较未优化版程序性能有显著提升.     

一个面向C和Fortran数值程序的静态分析工具

程序的正确性验证一直以来都是计算机科学中的一个挑战性问题,抽象解释理论为程序静态分析提供了一个通用框架,可以在编译时自动地推导程序的动态性质。基于抽象解释的数值程序分析可以自动推导程序中数值变量间的不变式关系,这对于编译优化、程序错误检查至关重要。本文建立并实现了一个面向C和Fortran程序并支持过程间分析的数值程序分析框架和工具,C或Fortran源程序经过预处理后转化为具有统一格式的中间表示形式,然后基于该中间表示抽取与源程序语义等价的语义等式,最后在该语义等式上进行不动点迭代计算从而得到程序不变式。在此基础上,本文还对数组等复杂语法结构进行了建模和抽象。实验结果表明,该工具具有较高的可扩展性、精度,并能够处理大部分因数组的使用而带来的程序分析上的问题。     

跨文件编译模式与基于GCC的实现

有很多编译优化都与编译时的视野有关,较宽的视野能给编译器提供更详细的信息,从而能得到更好的优化效果。采用跨文件编译模式使编译器的视野扩大至整个程序将是未来的方向。本文总结了实现这种模式的一般流程以及所遇到的问题和解决方法,分析了三种已提出的跨文件过程间编译模式,最后给出了一个基于GCC3.4的跨文件编译框架的实现方法。     

基于域的编译框架

传统的基于函数范围的后端编译框架是一种方便的程序划分方法，然而，考虑到编译过程中的资源需求（例如编译时间和内存使用），代码性能以及编译功能，函数的范围大小以及结构并不是最适合进行程序分析和优化的程序划分，在现代编译器为了尽可能地发掘指令级并行机会而寻求更复杂和时空复杂性更高的算法和情况下，这种不适应性变得更加突出，当函数的范围很大时，时空复杂性很高的算法以函数为基本编译单位通常会导致编译时间太长和（或）内存消耗太多，Hank提,出了一种编译框架，使得优化的范围和结构可以得到一定的控制，基于编译时间和优化机会的考虑，本文提出了一种新的基于域的编译框架，同时，允许一些基于域的优化制导属性在不同的优化阶段之间被传递和观察，这个基于域的编译框架已经在目标码为安腾（Itanium)处理器的编译器ORC（Open Research Compiler)中实现，实验结果表明，此框架在控制编译的时空复杂性方面是成功的。