Translation and Run-Time Validation of Optimized Code

The paper presents approaches to the validation of optimizing compilers. The emphasis is on aggressive and architecture-targeted optimizations which try to obtain the highest performance from modern architectures, in particular EPIC-like micro-processors. Rather than verify the compiler, the approach of translation validation performs a validation check after every run of the compiler, producing a formal proof that the produced target code is a correct implementation of the source code.First we survey the standard approach to validation of optimizations which preserve the loop structure of the code (though they may move code in and out of loops and radically modify individual statements), present a simulation-based general technique for validating such optimizations, and describe a tool, VOC-64, which implements these technique. For more aggressive optimizations which, typically, alter the loop structure of the code, such as loop distribution and fusion, loop tiling, and loop interchanges, we present a set of permutation rules which establish that the transformed code satisfies all the implied data dependencies necessary for the validity of the considered transformation. We describe the necessary extensions to the VOC-64 in order to validate these structure-modifying optimizations.Finally, the paper discusses preliminary work on run-time validation of speculative loop optimizations, that involves using run-time tests to ensure the correctness of loop optimizations which neither the compiler nor compiler-validation techniques can guarantee the correctness of. Unlike compiler validation, run-time validation has not only the task of determining when an optimization has generated incorrect code, but also has the task of recovering from the optimization without aborting the program or producing an incorrect result. This technique has been applied to several loop optimizations, including loop interchange, loop tiling, and software pipelining and appears to be quite promising.     

Translation and Run-Time Validation of Loop Transformations

This paper presents new approaches to the validation of loop optimizations that compilers use to obtain the highest performance from modern architectures. Rather than verify the compiler, the approach of translation validationperforms a validation check after every run of the compiler, producing a formal proof that the produced target code is a correct implementation of the source code. As part of an active and ongoing research project on translation validation, we have previously described approaches for validating optimizations that preserve the loop structure of the code and have presented a simulation-based general technique for validating such optimizations. In this paper, for more aggressive optimizations that alter the loop structure of the code—such as distribution, fusion, tiling, and interchange—we present a set of permutation ruleswhich establish that the transformed code satisfies all the implied data dependencies necessary for the validity of the considered transformation. We describe the extensions to our tool voc-64 which are required to validate these structure-modifying optimizations. This paper also discusses preliminary work on run-time validation of speculative loop optimizations. This involves using run-time tests to ensure the correctness of loop optimizations whose correctness cannot be guaranteed at compile time. Unlike compiler validation, run-time validation must not only determine when an optimization has generated incorrect code, but also recover from the optimization without aborting the program or producing an incorrect result. This technique has been applied to several loop optimizations, including loop interchange and loop tiling, and appears to be quite promising. This research was supported in part by NSF grant CCR-0098299, ONR grant N00014-99-1-0131, and the John von Neumann Minerva Center for Verification of Reactive Systems.     

Correctness of Classical Compiler Optimizations using CTL

In this paper, global compiler optimizations are captured by conditional rewrite rules of the form ( ), where and are program instructions and φ is a condition expressed in a variant of CTL, a formalism well suited to describe properties involving the control flow of a given program. The goal: to formally prove that if the condition φ is satisfied, then the rewrite rule can be applied to the program without changing the semantics of the program. Once a rewrite rule has been proven correct, it can be directly and automatically utilized in an optimizing compiler.The framework is based on joint work with David Lacey, Neil Jones and Eric Van Wyk [6]. The present paper presents a slightly simplified version of the framework, with emphasis on the CTL variants relation to CTL, along with a correctness proof of a transformation eliminating recomputations of available expressions.     

ADO.NET性能的优化

本文主要分析了ADO.NET中两种典型的数据访问模式的性能,以及有肋于提高数据访问性能的存储结构和连接池技术,并进一步研究了ADO.NET中其他优化数据访问性能的方法。     

Run-Time Checking of Dynamic Properties

We consider a first-order property specification language for run-time monitoring of dynamic systems. The language is based on a linear-time temporal logic and offers two kinds of quantifiers to bind free variables in a formula. One kind contains the usual first-order quantifiers that provide for replication of properties for dynamically created and destroyed objects in the system. The other kind, called attribute quantifiers, is used to check dynamically changing values within the same object. We show that expressions in this language can be efficiently checked over an execution trace of a system.     

The Implementation of Run-Time Diagnostics in Pascal

This paper considers the role of run-time diagnostic checking in enforcing the rules of the Pascal programming language. Run-time diagnostic checks must be both complete (covering all language requirements) and efficient. Further, such checks should be implemented so that the cost of enforcing the correct use of a given construct is borne by users of that construct. This paper descxibes simple and efficient mechanisms currently in use with a diagnostic Pascal compiler that monitor the run-time behavior of such sensitive Pascal constructs as pointers, variant records, reference (i.e., var) parameters, and with statements. The use of these mechanisms with related constructs in other languages is considered. Language modifications that simplify run-time checking ate also noted.     

医院信息化建设优化方案

分析了当前医疗信息化系统的发展现状,根据当前医疗信息化系统存在的问题,提出优化医疗信息化系统的方案,着重优化现有医疗信息化系统的网络设备和数据库存储设备,提高了系统性能,增强了安全性以及可扩展性。     

LQ优化的并行化方法

本文提出了两种有效的并行ＬＱ优化算法，分别用于求解多输入及单输入情况下控制参数合成。这两种算法都可以用脉动阵列结构并行实现，通过对数据流时序以及控制器利用率的分析，说明了并行的有效性。     

多维度等级评分模型优化技术

研究了多维度等级评分模型的训练学习优化技术.为了解决不同用户之间的评分标注所存在的不一致性,提出两种简单、有效的模型训练优化技术,包括基于容忍度的样本选择方法和基于排序损失的样本选择方法.另外,为了充分利用不同特征的用户评分标注之间的相关性,提出了一个面向属性的协同过滤技术以改善多维度等级评分模型.在两个公开的英语和汉语真实餐馆评论数据集上进行实验验证,实验结果表明,所提出的方法有效地改善了等级评分的性能.     

Prediction of Run-Time Failures Using Static Product Quality Metrics

A study is presented in which it is determined whether software product metrics gathered statically from designs or source code may be helpful in predicting the number of run-time faults that will be encountered during execution. Metrics examined include intermodule metrics such as fan-in and fan-out, as well as intramodule metrics such as cyclomatic complexity and size. Our study indicates that it may be possible, with certain classes of software products, to predict the run-time behaviour using well-known static intermodule metrics.     

运行时消除指针别名歧义方法的加速比分析

采用软硬件结合的运行时消除指针别名歧义方法SHRTD(software/hardware run-time disambiguation)适用于不可逆代码,同时,它的代码空间受到限制,不存在严重的代码可重入性问题.文章详细分析了SHRTD方法的指令级并行加速比,给出了发生地址冲突后的并行加速比与平均并行加速比以及发生地址冲突的依概率并行加速比.文章引入的三类理论加速比对指令级并行编译技术的研究和评测有重要的实际意义     

Effective and Efficient Compilation of Run-Time Generics in Java

After several years from Sun Microsystems' call-for-proposals for adding generics to the Java Programming Language, JDK 1.5 will be finally shipped with a compile-time support for generics. However, differently e.g. from the current implementation of .NET Common Language Runtime, run-time support to generics — also commonly referred to as reification of type parameters — is not provided, leading to a number of well-known inadequacies which might potentially be critical. In this paper we present the EGO compiler (Exact Generics on Demand). This is the result of a project developed in collaboration with Sun Microsystems as an effort to provide run-time generics in a smooth way, without requiring any change on the JVM or on any other run-time support. The core solution is a sophisticated translation of code based on the type-passing style, where run-time type information is automatically created on a by-need basis, limiting as most as possible run-time overhead while retaining interoperability with legacy Java code.We present the main aspects of this development, from basic design to implementation and deployment issues. Many relevant aspects that typical raise when implementing advanced type systems over a mainstream programming language are discussed, shading light to some effective implementation techniques.     

运行时消除指针别名歧义方法的加速比分析S

采用软硬件结合的运行时消除指针别名歧义方法SHRTD(software/hardware run-time disambiguation)适用于不可逆代码,同时,它的代码空间受到限制,不存在严重的代码可重入性问题.文章详细分析了SHRTD方法的指令级并行加速比,给出了发生地址冲突后的并行加速比与平均并行加速比以及发生地址冲突的依概率并行加速比.文章引入的三类理论加速比对指令级并行编译技术的研究和评测有重要的实际意义.     

一种工作流运行时流程回退方法的研究与实现

为了解决在流程回退操作中产生的死锁和数据不一致问题,本文在全面分析各种回退场景的基础上给出了流程的形式化定义和确保回退正确性的规则集,提出了一个获取可回退目标活动列表的算法。最后,我们设计了一个有效支持工作流运行时回退的应用模型。该模型在开源工作流引擎Shark中得到了实现,并对流程可能出现的回退场景进行了验证。实验的结果和分析的结果一致。     

支持森林场景动态生成的树木生长模拟

为了解决传统L文法中树木建模困难和运行效率低的问题,提出了支持森林场景动态生成的树木生长模拟方法.该方法基于分形元建立树木模型,在此基础上对大规模树木实体实例化的简化算法进行研究,将基于视点的多分辨率简化模型融入树木建模方法之中,并选择典型树种进行生长模拟.实验结果表明,该方法能较真实地模拟树木的生长过程,并实现在虚拟森林场景中的实时漫游.     

多核系统的多应用任务映射方法研究*

在多核处理器系统中,多个计算任务映射到多核处理器内核的方式对于系统吞吐率至关重要。针对此问题提出一种新的多应用任务到多核的映射算法,该算法在应用到来之前预测应用的相关性能,并采用分支限界法提前为未来应用预留合适的内核几何位置。当应用真正到来时,根据预留的区域完成映射。实验结果表明,该算法相比其他传统算法,在多任务通信量的减少和多核系统的吞吐率等方面都收到了良好效果。     

针对子程序结构的线程级推测并行性分析

线程级推测技术为开发更多的线程级并行性,充分利用多核加速传统上难以手工或自动并行化的串行程序提供可行的技术途径.然而,这种技术的性能严重地依赖于线程划分方案.有研究表明,仅推测执行循环所产生的并行性是不够的.但推测执行子程序结构比循环结构要难.本文提出寻找适于推测并行执行的子程序结构的基本判定依据;通过运行由Simplescalar工具集改造得到的动态剖析工具ProRV、ProFun和SPEC CPU2000基准测试程序,我们对子程序结构线程化推测执行的适合性进行详细分析,给出具有指导意义的实验分析方法和实验数据.我们发现:①无返回值的子程序结构占据程序整体执行时间的大约40%;返回稀疏整型的子程序结构占据了程序整体执行时间的大约10%,对其返回值的预测成功率在70%左右.对于其他返回值类型的子程序结构,由于对其返回值的预测成功率过低,我们认为不适合作为线程划分的对象.②简单的last-value的值预测方案对于返回值的预测是简单而且足够有效的.③访存数据依赖普遍存在于子程序与其后继代码之间,显式同步机制对于针对子程序结构的线程级推测是必要的.     

供电整流系统技术优化与改进

根据变电所供电整流系统直流电流由150kA强化至160～170kA的目标,提出设备改进优化的方案,以达到提高供电系统的安全性和增产降耗的目的.