基于扩展逻辑变换系统μTS证明循环优化正确性

循环优化对于提高Cache性能、发掘程序的并行性以及减少执行循环的开销都有着重要的作用,证明带循环优化功能的现代编译器的正确性已成为可信编译的一个挑战性的问题.形式化证明一个羽翼丰满的优化编译器本质上是不可行的,可以使用替代的方法,即不是证明优化编译器本身,而是形式化证明每一次循环变换前后编译对象的正确性.提出一种新颖的基于扩展逻辑变换系统μTS来证明循环优化正确性的方法.系统μTS在逻辑变换系统TS的基础上扩展了若干条派生规则,经谓词抽象将源程序与目标程序转换为形式化Radl语言后,使用μTS的派生规则能证明常见循环变换的正确性,如循环融合、循环分配、循环交换、循环反转、循环分裂、循环脱皮、循环调整、循环展开、循环铺盖、循环判断外提、循环不变代码外提等.循环优化可以看作一系列循环变换的组合,从而系统μTS能证明循环优化的正确性.为了支持自动化证明循环优化的正确性并出示证据,进一步提出了一个辅助证明算法.最后通过一个典型实例对这一方法进行了详细的阐述,实际效果表明了该方法的有效性.该方法对设计高可信优化编译器具有重要的指导意义.     

基于时序逻辑的编译优化测试用例生成方法*

提出一种基于时序逻辑公式的关键节点控制图生成方法,生成的测试用例针对性强,容易扩展;并以该方法改进了一种编译优化自动化测试工具,在很大程度上消除了其测试冗余,提高了测试效率.     

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

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

时序逻辑控制系统的形式变换

目前在智能控制的研究中存在着一系列重要问题。其中有:(1)如何将人工智能与控制理论结合起来?(2)怎样对智能控制系统进行分析、综合?针对这些问题,本文提出了以数举模型形式表达基于浅层知识的系统的思想,并采用了时序逻辑描述了控制系统和系统理论中的一些基本定义,给出了这类系统的形式变换方式,这些工作对上述问题的研究具有一定的意义.     

基于时序Petri网的联锁逻辑形式建模与验证

时序Petri网结合Petri和时序逻辑的优点,清晰简洁地描述并发系统事件间的时序和因果关系,包括系统的最终性和公平性。文章给出安全苛求系统——车站信号联锁逻辑系统的时序Petri网描述,并使用时序逻辑描述系统状态的时序和因果关系,最后通过分析和验证模型的性质得出系统是正确的。     

基于线性表出的非奇异循环变换局部性优化方法

开发程序的局部性是当今并行编译优化研究的重点之一，而程序变换是开发程序时间局部性和空间局部性的重要手段之一．该文提出了一种新的利用非奇异循环变换来优化程序局部性的局部性优化方法，即基于线性表出的循环变换．该方法利用一组最少的线性无关向量组来线性表出数组访问的下标表达式，并据此构造非奇异变换矩阵来优化数组访问的时间局部性和空间局部性．该方法能充分开发数组访问的时间局部性，能简便地确定是否能对数组访问进行时间局部性或空间局部性优化，并能对给定的嵌套循环同时进行时间局部性和空间局部性优化．实验结果表明了该文所提出的基于线性表出的非奇异循环变换局部性优化方法是有效的．     

基于CTL的循环优化变换描述方法

TRANS是基于CTL的优化变换描述语言,对TRANS语言作了宏扩展,给出了循环嵌套、循环归纳变量、循环依赖及方向向量的时序逻辑描述.从依赖分析的角度对重排序循环优化变换加以考查,并以循环逆转和循环交换为例阐述了其形式化描述方法.     

面向X10的数据流程序编译优化算法

数据流编程作为一种编程模式已被广泛应用到各个领域.然而,多核体系结构的不同使得数据流程序在不同平台上移植困难.X10作为一种新型并行编程语言,为不同的多核体系结构提供了统一的并行计算环境.如何利用X10语言的特性来提高数据流程序的效率已成为目前研究工作的一大难点.本文设计并实现了一个面向X10的编译优化系统,该系统确立了三种优化算法:针对X10语言的代码生成优化减少了生成的X10代码量;针对同步数据流图的任务划分优化在负载均衡的基础上,避免了死锁的产生,同时减少了通信开销;针对底层硬件资源的通信优化在机器间通信、机器内部线程间通信、线程内部通信方面进行了区分和优化,减少了通信开销.实验结果表明,设计的三种编译优化算法都获得了较大的性能提升.     

基于时序逻辑的时序数据库中知识发现方法

知识发现是一个众多学科诸如人工智能、机器学习、模式识别、统计学、数据库和知识库、数据可视化等相互交叉、融合所形成的一个新兴的且具有广阔应用前景的领域。目前国际上对知识发现的研究与开发进展很快。众多现实世界(如天气预报、电信、金融)的数据库中数据都是随时间变化的,即数据具有时序性。目前,时序数据库中的知识发现问题正逐渐引起KDD研究者的兴趣。本文首先给出时     

时态逻辑与程序验证

近年来,时态逻辑大量应用于程序验证,采取的途径随使用的时态逻辑的形式和方法的不同而异。本文用自动机理论研究几种时态逻辑(LTL,BTL,POTL)的模型和模型生成子,并讨论用时态逻辑进行程序验证的的重要途径。     

基于时序逻辑的加密协议分析

形式化方法由于其精炼，简洁和无二义性，逐步成为分析加密协议的一条可靠和准确的途径，但是加密协议的形式化分析研究目前还不够深入，至今仍没有统一的加密协议验证体系，针对这一现状，该文从加密协议可能面临的最强大的攻击着手，提出了一种基于时序逻辑的加密协议描述方法，在该模型下，对协议行为，入侵者行为，安全需求等特性的描述均用时序逻辑公式表达，从而利用现有的统一的时空逻辑框架分析密码协议的性质，特别地，作者描述和检测了一个系统入侵者不能用任何代数和逻辑的办法获得消息的实例，通过对比，作者认为该方法具有形式化程度较高的特点。     

基于时序逻辑的面向实现的协议规范语言

在多种形式化描述语言和时序逻辑原理的研究之上；针对通讯协议的特点提出一个协议模型思想，并设计了实现此模型协议描述语言．本方法的特点是：基于时序逻辑；引入了面向对象的概念，对事件有强的描述能力，让描述更接近于现实；扩展了对事件的描述．能描述事件的随机发生，我们已将之成功地应用于对超文本协议的描述．     

基于时序描述逻辑的UML顺序图形式化方法

根据统一建模语言(UML)顺霤图的时霤特征,提出一种基于时霤描述逻辑ALCQIUS的UML顺霤图需式化方法。研究ALCQIUS时霤扩展部分的语法和语义、ALCQIUS断言公式集一致霆定理,给出ALCQIUS断言公式集一致霆推理算法,并证明该推理算法的可判定霆。以公安报警系统为例,说明基于ALCQIUS的UML顺霤图需式化规约和需式化验证具备可霂霆,并且ALCQIUS为UML顺霤图需式化提供了合理的逻辑基础。     

An Experiment in Program Composition and Proof

This paper explores a compositional approach to program specification, development and proof. We apply a theory of composition to a problem in distributed computing with the goal of understanding the strengths and weaknesses of this compositional approach. First, we describe the theory briefly. Then we give a specification of a desired system. Next, we propose a design of the desired system as a composition of components and prove its correctness. Finally, we show how the proof can be reused for a slightly different compositional structure by using the concept of observation.     

基于Hoare逻辑的密码软件形式化验证系统

在Hoare逻辑理论和ACSL语法规范的基础上,设计一种针对密码软件的形式化验证系统,由程序规范、验证推理规则、可靠性策略、验证推理等模块组成。以OpenSSL中RC4算法的软件实现为例,对其功能正确性、保险性和信息流安全性进行验证,结果表明,该系统具有较高的自动化水平,可在一定程度上降低形式化验证方法的复杂度。     

基于直觉模糊集的不确定时序逻辑模型

针对现有时序逻辑在描述复杂不确定时间信息方面的局限性,提出了一种基于直觉模糊集的不确定时序逻辑模型。该模型分别定义了离散论域和连续论域下的不确定点时序逻辑、点-时段时序逻辑以及时段时序逻辑的判定公式;引入直觉模糊集的犹豫度参数,使得推理结果更加精确。最后通过实例对两类不确定时间信息进行描述,并对其时序逻辑关系的可能性进行度量。通过分析表明该模型是比较优越的。     

Using Program Transformations to Provide Safety Properties for Real-Time Systems

The process of showing that a program satisfies some particular properties with respect to its specification is called program verification. Axiomatic semantics is a verification method that makes assertions describing properties about the states of a program. There exists a transformation from the assertions of a program's verification proof to executable assertions. The latter may be embedded in the program to make it fault tolerant. An axiomatic proof system for concurrent programs is applied to generate executable assertions in a real time distributed environment. A train set example is used as modelproblem.