The design and implementation of genesis

Although code optimizations are necessary to parallelize code, few guidelines exist for determining when and where to apply optimizations to produce the most efficient code. The order of applying optimizations can also have an impact on the efficiency of the final target code. However, determining the appropriate optimizations is difficult due to the complex interactions among the optimizations, scheduler and architecture. To aid in selecting appropriate optimizations, an optimizer generator (Genesis) is presented that produces an optimizer from specifications of optimizations. This paper describes the design and implementation of Genesis and demonstrates how such a generator could be used by optimizer designers. Some experiences with the generator are also described.     

脚本引擎的简单实现

脚本是使用一种特定的描述性语言,依据一定的格式编写的可执行文件,又称作宏或批处理文件.脚本引擎对脚本进行编译和执行.一个脚本引擎通常包括的组件有:符号表、词法分析器、语法分析器、语义检查器、中间代码生成器、代码优化器、代码生成器、虚拟机.通过对一个简单脚本引擎实现过程的分析,可以深入理解各组件的实现方法.将以上组件合起来,就可以执行脚本语言.脚本语言可以通过调用软件的COM来扩展功能,实现软件的定制,也可以实现软件的自动化.     

Tools for code optimization and system evaluation of the image processing system PAPRICA-3

This paper presents the complex environment that was built to ease the prototyping of real-time applications on the PAPRICA-3 massively parallel system. Applications are developed in C++ using high level data types and the corresponding Assembly code is automatically created by a code generator. A stochastic code optimizer takes the assembly code and improves it according to a genetic approach; due to the high computational power required by this approach, the stochastic code optimizer was implemented with MPI and runs in parallel on a cluster of workstations. The availability of this complex environment allowed to test the performance of the system and to tune it according to some target applications before the actual development of the hardware. For this purpose a system-level simulator was also built to determine the number of clock cycles required to run a specific segment of code. The whole environment has been used to validate possible solutions for the hardware system and to develop, test, and tune several real-time image processing applications. The hardware system is now completely defined.     

Metamorphic code generation from LLVM bytecode

Metamorphic software changes its internal structure across generations with its functionality remaining unchanged. Metamorphism has been employed by malware writers as a means of evading signature detection and other advanced detection strategies. However, code morphing also has potential security benefits, since it can serve to increase the “genetic diversity” of software. We have created a metamorphic code generator within the LLVM compiler framework. LLVM is a three-phase compiler that supports multiple source languages and target architectures. It uses a common intermediate representation (IR) bytecode in its optimizer. Consequently, any supported high-level programming language is transformed to this IR bytecode as part of the LLVM compilation process. Our metamorphic generator functions at the IR bytecode level, which provides many advantages over morphing at the assembly or source code level. The morphing techniques that we employ include dead code insertion and transposition, where the dead code is actually executed within the morphed code, making its detection and removal more challenging. We have verified the effectiveness of our code morphing using hidden Markov model analysis.     

AlphaQO: Robust Learned Query Optimizer

Recently, learned query optimizers typically driven by deep learning models have attracted wide attention as they can offer similar or even better performance than state-of-the-art commercial optimizers. A successful learning optimizer often relies on enough high-quality load queries as training data, and poor-quality training will lead to the query failure of learned query optimizers. In this paper, we propose a novel training framework AlphaQO for robust learned query optimizers based on Reinforcement Learning (RL), and the robustness of the optimizers can be improved by finding the bad queries in advance. AlphaQO is a loop system consisting of two main components, namely the query generator and the learned optimizer. A query generator aims at generating ``difficult'' queries (i.e., queries that the learned optimizer provides poor estimates). The learned optimizer will be trained using these generated queries, as well as providing feedback (in terms of numerical rewards) to the query generator for updates. If the generated queries are good, the query generator will get a high reward; otherwise, the query generator will get a low reward. The above process is performed iteratively, with the main goal that within a small budget, the learned optimizer can be trained and generalized well to a wide range of unseen queries. Extensive experiments show that AlphaQO can generate a relatively small number of queries and train a learned optimizer to outperform commercial optimizers. Moreover, learned optimizers require much fewer queries from AlphaQO than randomly generated queries for the quality training of the learned optimizer.     

AlphaQO:鲁棒的学习型查询优化器

由深度学习驱动的学习型查询优化器正在越来越广泛地受到研究者的关注,这些优化器往往能够取得近似甚至超过传统商业优化器的性能.与传统优化器不同的是,一个成功的学习型优化器往往依赖于足够多的高质量的负载查询作为训练数据.低质量的训练查询会导致学习型优化器在未来的查询上失效.提出了基于强化学习的鲁棒的学习型查询优化器训练框架A...     

Using profile information to assist classic code optimizations

This paper describes the design and implementation of an optimizing compiler that automatically generates profile information to assist classic code optimizations. This compiler contains two new components, an execution profiler and a profile-based code optimizer, which are not commonly found in traditional optimizing compilers. The execution profiler inserts probes into the input program, executes the input program for several inputs, accumulates profile information and supplies this information to the optimizer. The profile-based code optimizer uses the profile information to expose new optimization opportunities that are not visible to traditional global optimization methods. Experimental results show that the profile-based code optimizer significantly improves the performance of production C programs that have already been optimized by a high-quality global code optimizer.     

Optimization of structured programs

The class of programs which do not contain goto statements has a structure which lends itself to optimization by an optimizer that is fast, efficient and relatively easy to program. The design of such an optimizer is described, along with some of the results obtained using this optimizer—one such result being that very little code optimization is achieved. The conjecture is made that this is true because gotoless programming languages lend themselves to more compact and concise object code at the source language level.     

OPTIMA—A portable PCODE optimizer

This paper describes the design and implementation of OPTIMA, a Portable optimizer for the PASCAL-P4 compiler. The PASCAL-P4 compiler generates code, called PCODE, for a hypothetical stack computer. The stack computer is easy to simulate or to emulate on a wide range of computer architectures. However, the code produced for it by PASCAL-P4 is unoptimized and inefficient when emulated on conventional computers. OPTIMA improves the code which is produced by the compiler. It has three levels of optimization: PCODE transformations, TUPLE transformations and Code generation. Programs processed by the optimizer are substantially smaller and faster than before optimization. OPTIMA was implemented for the Weizmann Institute of Science GOLEM-B computer.     

Construction of a peephole optimizer

The design and construction of a peephole optimizer is described. The optimizer consists of a database of patterns, a translator that translates the patterns into an implementation language, and a pattern-matcher skeleton into which the generated pattern code is inserted. it is argued that this three-part split is a good way to approach the construction of certain kinds of programs.     

A 99 line topology optimization code written in Matlab

The paper presents a compact Matlab implementation of a topology optimization code for compliance minimization of statically loaded structures. The total number of Matlab input lines is 99 including optimizer and Finite Element subroutine. The 99 lines are divided into 36 lines for the main program, 12 lines for the Optimality Criteria based optimizer, 16 lines for a mesh-independency filter and 35 lines for the finite element code. In fact, excluding comment lines and lines associated with output and finite element analysis, it is shown that only 49 Matlab input lines are required for solving a well-posed topology optimization problem. By adding three additional lines, the program can solve problems with multiple load cases. The code is intended for educational purposes. The complete Matlab code is given in the Appendix and can be down-loaded from the web-site http://www.topopt.dtu.dk. Received October 22, 1999     

A binary grey wolf optimizer for the multidimensional knapsack problem

Grey Wolf Optimizer (GWO) is a new meta-heuristic that mimics the leadership hierarchy and group hunting mechanism of grey wolves in nature. A binary version is developed to tackle the multidimensional knapsack problem which has an extensive engineering background. The proposed binary grey wolf optimizer integrates some important features including an initial elite population generator, a pseudo-utility-based quick repair operator, a new evolutionary mechanism with a differentiated position updating strategy. The proposed algorithm takes full advantage of the knowledge of the problem to be solved and highlights the distinctive feature of the optimizer in the family of evolutionary algorithm. Experimental results statistically show the effectiveness of the new optimizer and the superiority of the proposed algorithm in solving the multidimensional knapsack problem, especially the large-scale problem.     

基于Pspice的低通滤波器优化设计与仿真分析

高性能滤波器是现代信号处理的一种基本电路,传统的设计思想和方法运算量大,存在优化复杂的缺点。本文采用Pspice的仿真优化工具对二阶低通滤波器基于通带宽度的目标进行了优化和仿真,结果表明优化目标和仿真结果一致。     

Optimization of hierarchical directed graphs

A machine- and language-independent representation for programs suitable for use within a compiler is presented. This representation is the hierarchical directed graph. Powerful code optimization techniques are presented in the context of this representation. An experimental optimizer has been built to validate the ideas discussed. The power of the representation is evident in the compactness of the code implementing the optimizations.     

多语种自然语言生成系统中的预映射句子规划器

自然语言生成是研究如何用计算机来生成自然语言文本的研究领域 ,经典结构是宏观规划、微观规划和表层生成的流水线结构 .分析了多语种自然语言生成系统 ACNL G中的微观规划器 ,提出了“基于语言资源预映射的句子优化器”,它不仅对句子进行优化 ,而且负责将语种无关的文章内容映射到具体语种的表达方式中 .其核心思想就是将处理过程同具体语种的语言资源相分离 ,但同时又以语言资源为导向 ,既继承了现有方法的优点 ,同时也解决了多语种条件下各语种之间细微差别的处理问题 ,使句子优化能够针对目标语种的特点进行优化操作 ,从而使优化效果有实质的提高 ,进一步发展了多语种文本生成的理论     

Register allocation and exhaustive peephole optimization

Emerging peephole optimizers can relieve code generators of much case analysis, but delaying code generation decisions requires register allocation algorithms that accept object code instead of the more usual intermediate code. This paper describes two programs that implement such algorithms for a retargetable optimizing compiler. In a machine-independent fashion, they allocate and assign registers, eliminate common subexpressions (including often-missed machine-specific ones), identify dead variables, and define windows for the companion peephole optimizer. Their techniques for handling machine-specific data should generalize to other optimizations as well.     

代码生成技术在MDA中的实现

针对如何将具体的业务模型转换为应用程序代码的问题,提出了一个采用XSLT技术的代码生成器设计方案,用来实现MDA中的自动代码生成。从介绍代码生成器的输入文件入手,讨论了代码生成器的处理原理,最后举了一个采用XSLT技术的代码生成器生成代码的例子。     

The design and implementation of a code generation tool

A practical approach to the development of a high-quality, re-usable code generator is described in this paper. This code generator produces code for the Prime 64V mode architecture, but the methodology used is generally applicable to the construction of compilers for most architectures. The code generator accepts a tree-structured intermediate form, linearized and represented as a file of integers. This intermediate form uses high-level operators, minimizing work by compiler front-ends that use it and providing a number of advantages in the code generation process. The output of the code generator is assembly language. This tool was found to considerably extend the capabilities of students in a graduate compiler class and has been used in the construction of Pascal and C compilers.     

The Glue-Nail deductive database system: Design,implementation, and evaluation

We describe the design and implementation of the Glue-Nail deductive database system. Nail is a purely declarative query language; Glue is a procedural language used for non-query activities. The two languages combined are sufficient to write a complete application. Nail and Glue code are both compiled into the target language IGlue. The Nail compiler uses variants of the magic sets algorithm and supports well-founded models. The Glue compiler's static optimizer uses peephole techniques and data flow analysis to improve code. The IGlue interpreter features a run-time adaptive optimizer that reoptimizes queries and automatically selects indexes. We also describe the Glue-Nail benchmark suite, a set of applications developed to evaluate the Glue-Nail language and to measure the performance of the system.Part of this article was presented at the ACM SIGMOD International Conference on Management of Data, Washington, DC, 1993.Much of this research was done while the authors were at Stanford University, Stanford, California, USA.