BWDSP104X多条件谓词编译优化

目前BWDSP104X编译器对程序中条件分支的处理是采用传统的谓词优化方法,及每条指令和一个谓词相关,只有当谓词为真时指令才被执行,但它存在的局限性是当涉及到多条件谓词时,并不能消除跳转分支,且多条件谓词之间可能存在控制依赖关系,不利于指令并行和指令流水. 因此在现有编译器框架下,针对传统谓词优化方法的不足之处,本文提出一种基于BWDSP104X体系结构下多条件谓词编译优化方法. 实验结果表明,与传统谓词优化方法相比,该优化算法在BWDSP104X编译器上能够取得平均5.62的加速比.     

指令级并行中谓词分析技术的研究

谓词支持是IA 6 4体系结构的新特征 ,它为发掘指令级并行提供了更多的机会 ,同时给编译器的设计者增加了难度 .谓词是条件执行的依据 ,是提高指令级并行的新途径 .该文介绍在ORC(IA 6 4OpenResearchCompiler)中首次设计实现的基于谓词划分图的谓词分析技术及其在指令调度中的应用 .利用谓词分析技术建立了谓词关系数据库、指令调度查询谓词关系数据库提高指令级并行 .文章着重论述了谓词关系数据库的核心———谓词划分图的建立 ,在谓词划分图的基础上实现了谓词关系的计算和查询 ,实际结果表明谓词分析技术有显著优化效果 .     

基于程序行为特征比较的谓词切换排序

谓词切换（Predicate Switching）通过动态改变程序中的谓词判断语句状态观察程序运行结果的变化,分析可能与错误相关的关键谓词判断语句,从而实现辅助错误定位．谓词判断语句排序算法决定了谓词切换定位关键谓词判断语句的效率．已有的排序算法如LEFS算法定位效率较低;PRIOR算法虽然提高了定位效率,但必须首先做程序动态切片找寻与错误相关的谓词判断语句集合,而后建立程序依赖图以定义谓词判断语句的优先级,这个过程需要花费大量的时间,且算法复杂度较高．在这两种算法基础上提出一种新的改进排序算法,首先通过对比成功和失败的测试用例在运行中所展现出来不同程序行为特征,以此定义谓词判断语句的优先级,然后对不同优先级别的谓词根据执行先后顺序进行反向排序．基于基准测试集SiemensSuite的程序进行了实验,结果表明本文的排序算法与LEFS算法相比定位效率更高,与PRIOR算法相比减少定义谓词优先级的耗费,且算法更易于实现．     

分片式处理器上的谓词执行技术优化

谓词执行能使分片式处理器充分利用众多的执行单元,开发指令级并行性.但因此形成的超块也使得分支误预测代价增大,所以提高分支预测器的性能至关重要.本文提出一种基于剖析信息决策的谓词执行技术,该技术利用剖析信息对谓词执行前后的执行周期进行估算,从而对分支的谓词执行进行决策.该技术使分支预测器的命中率提高了0.68%～3.50%,使系统性能提高了1.67%～8.33%.同时,利用select指令表示谓词化指令也消除了重命名阶段寄存器多定义问题.     

编译型PROLOG系统中内部谓词的实现策略

实用PROLOG语言为用戶提供了大量的內部谓词,实现这些內部谓词是一较为困难的问难,尤其是在编译型PROLOG系统中更是如此。本文介绍在我们所设计的主辅机结构的编译型顺序PROLOG系统KD—PP中,內部谓词的实现方法:借用指令法、专用指令法、子目标序列定义和接口指令法。根据內部谓词的不同特点,不同內部谓词的实现方法的也不一样。我们认为:文中提出的实现策略在主辅机结构的编译系统中是简单可行的,而且实现效率也是较高的。     

一阶谓词公式关联矩阵的构造方法

一阶谓词逻辑可以借助关联矩阵进行有效推理。为了提高关联矩阵的构造效率,从而提高一阶谓词逻辑推理的效率,提出一种由一阶谓词公式构造对应关联矩阵的递归方法。该方法利用二叉树的递归性质,对任意一个一阶谓词公式,在化去量词后直接构造关联矩阵。该方法为借助关联矩阵实现一阶谓词逻辑的自动化推理提供了可能。     

魂芯分簇VLIW DSP上指令调度的优化

魂芯DSP处理器是一款32 bit静态超标量、分簇结构的、支持SIMD的VLIW处理器。魂芯DSP芯片有4个执行簇和3个内存块,但簇间数据传输和寻址会占用总线带宽。魂芯DSP上每个簇中有大量的计算部件,但是现有的编译器框架中指令调度算法是针对非分簇结构的,无法充分利用魂芯DSP的分簇结构特点,产生出高效的指令级并行代码。根据魂芯处理器架构分簇的特点,提出了在魂芯DSP上进行指令分簇和指令调度的启发式算法,并且在开源Open64编译器框架上进行了实现。实验结果表明,该算法在魂芯DSP编译器上的实现可以显著提高一些在DSP上有着计算密集型程序的性能。     

基于约束的多维Apriori改进算法

针对经典多维关联规则挖掘算法执行效率不高、存在冗余规则的不足,提出基于约束的多维Apriori改进算法,在多维Apriori算法的基础上,将用户约束引入挖掘过程,根据关于谓词的约束产生用户感兴趣的频繁谓词集,并以此为依据删减事务集。该算法一方面通过用户约束大大缩减了候选谓词集的产生,另一方面经过删减的事务集也降低了扫描数据库的开销,最终实现了挖掘效率的提高以及冗余规则的减少。应用该算法在FPGA代码缺陷事务集上进行对比实验,实验结果证明了该算法相比多维Apriori算法,在搜索效率以及挖掘结果的准确性方面均得到了改善,有效提高了FPGA代码缺陷分析的准确性。     

实现家庭服务机器人中文指令解析问题研究

为了实现家庭服务机器人在无人干预的情况下自主地执行中文指令中蕴涵的服务任务,提出一种基于回答集的中文指令任务规划方法,将组块标注和回答集编程(answer set programming,ASP)应用于家庭服务机器人任务规划。首先通过组块标注对中文指令进行预处理,然后根据转换规则将关键信息转换为谓词集,并将它转写成ASP规则。此外,给出中文服务指令处理的各个环节的实验结果,并结合实例展示从谓词集到机器人可以执行的动作序列的映射过程。最后,通过合并部分原子动作的方式对回答集进行改进,提高了求解效率,并在任务规划时加入了成本规划,确认求得最优动作序列,该方法对促进自然人-机器人交互技术的发展有重要的意义。     

基于BDD的谓词分析与优化

为对带谓词的数据流进行准确而有效的分析,首先介绍了John W.Sias等人提出的一种基于二进制决策图(BDD)的谓词分析系统(PAS);然后在其基础上,提出了结合芯片自身体系结构特点的谓词优化算法。将PAS及优化算法在学院研制的FT_D4芯片的编译器上实现,实验结果表明,这种基于BDD的谓词分析与优化方法简化了程序控制结构,减少了对谓词寄存器的使用,缩短了代码执行时间,性能获得了较大的提高。     

基于概率和条件逻辑的PKI信任模型推理

提出一种基于概率和条件谓词逻辑来表示和推导PKI信任模型的方法．该方法用3个二元条件谓词表示不同个体之间的关系,并给出了实体认证规则、信任规则和信任扩展规则，对信任度定义了一个概率模型，该模型能反映约束条件如何影响信任度．概率模型加条件谓词逻辑能够对一个PKI信任模型进行更精确的描述．     

基于神经网络的中文谓语动词识别研究

识别谓语动词是理解句子的关键。由于中文谓语动词结构复杂、使用灵活、形式多变,识别谓语动词在中文自然语言处理中是一项具有挑战的任务。本文从信息抽取角度,介绍了与中文谓语动词识别相关的概念,提出了一种针对中文谓语动词标注方法。在此基础上,研究了一种基于Attentional-BiLSTM-CRF神经网络的中文谓语动词识别方法。该方法通过双向递归神经网络获取句子内部的依赖关系,然后用注意力机制建模句子的焦点角色。最后通过条件随机场（Conditional random field, CRF)层返回一条最大化的标注路径。此外,为解决谓语动词输出唯一性的问题,提出了一种基于卷积神经网络的谓语动词唯一性识别模型。通过实验,该算法超出传统的序列标注模型CRF,在本文标注的中文谓语动词数据上到达76.75%的F值。     

开放环境特性感知技术

提出了一个开放环境特性描述框架.该框架支持便捷地、形式化地描述异步环境的各种特性,包括那些既有技术不能处理的时序特性.该框架还引入了谓词检测技术,支持高效的环境特性感知机制的实现.开发了一个开放环境特性感知中间件平台,并通过详细的案例分析展示了如何基于所提出的环境特性描述框架与中间件平台,高效地感知环境特性,支持可信软件系统的构建.     

An Efficient Multiple Predicate Learner

In this paper,we examine the issue of learning multiple predicates from given training examples.A proposed MPL-CORE algorithm efficiently induces Horm clauses from examples and background knowledge by employing a single predicate learning module CORE.A fast failure mechanism is also proposed which contributes learning efficiency and learnability to the algorithm.MPL-CORE employs background knowledge that can be represented in intensional(Horn clauses)or extensional (ground atoms)orms during its learning process.With the fast failure mechanism,MPL-CORE outperforms precious multiple predicate learning systems in both the computational complexity and learnability.     

基于谓词检测方法的上下文感知案例研究

当前,开发灵活的适应环境变化的上下文感知应用较为复杂。在上下文感知应用开发过程中,很多未知情况无法事先被充分考虑到,实际的开发又需要处理很多意外情形,因此有效地表示和处理上下文尤为重要。谓词检测作为实现上下文感知的重要方法之一,能够有效对上下文信息进行建模,但在实际应用中对于真实物理设备的支持如何在很大程度上仍然是未知的。为了应对以上问题,通过构建一个简单的物理场景,将谓词检测方法应用于真实的机器小车上,支持其在一个既定轨道上完成运行任务。在该场景下对原始的上下文环境进行建模,将环境特性逐步规约成特定的快照谓词和序列谓词,并在案例研究中,对规约化的谓词进行检测,将谓词检测应用于真实的机器小车实验上。实验分析的结果表明,谓词检测的方法能有效检测小车的上下文特性并成功支撑小车完成既定的行走目标。     

基于谓词切片的字符串测试数据自动生成

字符串谓词使用相当普遍，如何实现字符串测试数据的自动生成是一个有待解决的问题，针对字符串谓词，讨论了路径Path上给定谓词的谓词切片的动态生成算法，以及基于谓词切片的字符串测试数据自动生成方法，并给出了字符串间距离的定义，利用程序DUC（Definithon-Use-Control)表达式，构造谓词的谓词切片，对任意的输入，通过执行谓词切片，获取谓词中变量的当前值，进而对谓词中变量的每一字符进行分支函数极小化，动态生成给定字符串谓词边界的ON－OFF测试点，实验表明，该方法是行之有效的。     

Techniques and applications of computation slicing

Writing correct distributed programs is hard. In spite of extensive testing and debugging, software faults persist even in commercial grade software. Many distributed systems should be able to operate properly even in the presence of software faults. Monitoring the execution of a distributed system, and, on detecting a fault, initiating the appropriate corrective action is an important way to tolerate such faults. This gives rise to the predicate detection problem which requires finding whether there exists a consistent cut of a given computation that satisfies a given global predicate.Detecting a predicate in a computation is, however, an NP-complete problem in general. In order to ameliorate the associated combinatorial explosion problem, we introduce the notion of computation slice. Formally, the slice of a computation with respect to a predicate is a (sub)computation with the least number of consistent cuts that contains all consistent cuts of the computation satisfying the predicate. Intuitively, slice is a concise representation of those consistent cuts of a computation that satisfy a certain condition. To detect a predicate, rather than searching the state-space of the computation, it is much more efficient to search the state-space of the slice.We prove that the slice of a computation is uniquely defined for all predicates. We also present efficient algorithms for computing the slice for several useful classes of predicates. For an arbitrary predicate, we establish that the problem of computing the slice is NP-complete in general. Nonetheless, for such a predicate, we develop an efficient heuristic algorithm for computing an approximate slice. Our experimental results demonstrate that slicing can lead to an exponential improvement over existing techniques for predicate detection in terms of time and space.Received: 19 November 2003, Revised: 29 July 2004, Published online: 7 February 2005Vijay K. Garg: Supported in part by the NSF Grants ECS-9907213, CCR-9988225, Texas Education Board Grant ARP-320, an Engineering Foundation Fellowship, and an IBM grant.Parts of this paper have appeared earlier in conference proceedings [GM01,MG01a,MG03a].