命题逻辑提升到一阶逻辑上的子句消去方法

在基于命题逻辑的可满足性问题（SAT）求解器和基于一阶逻辑的定理证明器上，子句集简化一直是必不可少的步骤，而其中子句消去方法在这些子句集简化方法中是非常重要的组成部分。将命题逻辑中的子句消去方法归结隐藏恒真消去方法（RHTE）和归结隐藏包含消去方法（RHSE）提升到一阶逻辑上，并且利用蕴含模归结原则（IMR）证明了这种提升方式在一阶逻辑上具有可靠性（Soundness），即依据这两种子句消去方法删除一阶逻辑公式集中的子句，并不会改变公式集的可满足性或者不可满足性。此外，将这两个方法与一阶逻辑子句消去方法锁子句消去方法（BCE）和归结包含消去方法（RSE）进行组合推广，发展得到一阶逻辑上新型子句消去方法（BC+RHS）E、（RS+RHT）E和（RHS+RHT）E，并且证明了这3种子句消去方法在一阶逻辑上的可靠性。最后，分析比较了这些子句消去方法的有效性，并且证明了这3种新型子句消去方法比组成它们的原始子句消去方法均具有更高的有效性。     

Performance of the most common non‐cryptographic hash functions

Non‐cryptographic hash functions (NCHFs) have an immense number of applications, ranging from compilers and databases to videogames and computer networks. Some of the most important NCHF have been used by major corporations in commercial products. This practical success demonstrates the ability of hashing systems to provide extremely efficient searches over unsorted sets. However, very little research has been devoted to the experimental evaluation of these functions. Therefore, we evaluated the most widely used NCHF using four criteria as follows: collision resistance, distribution of outputs, avalanche effect, and speed. We identified their strengths and weaknesses and found significant flaws in some cases. We also discuss our conclusions regarding general hashing considerations such as selection of the compression map. Our results should assist practitioners and engineers in making more informed choices regarding which function to use for a particular problem. Copyright © 2013 John Wiley & Sons, Ltd.     

基于Radix-4 Booth编码的模2n+1乘法器设计

模2n+1乘法(n=8、16)在分组密码算法中比较常见,如IDEA算法,但由于其实现逻辑复杂,往往被视为密码算法性能的瓶颈。提出了一种适用于分组密码算法运算特点的基于Radix-4 Booth编码的模2n+1乘法器实现方法,其输入/输出均无需额外的转换电路,并通过简化部分积生成、采用重新定义的3-2和4-2压缩器等措施以减少路径时延和硬件复杂度。比较其他同类设计,该方法具有较小的面积、时延,可有效提高分组密码算法的加解密性能。     

Generating effective test cases based on satisfiability modulo theory solvers for service‐oriented workflow applications

Web Service Business Process Execution Language (WS‐BPEL) is one of the most popular service‐oriented workflow applications. The unique features (e.g. dead path elimination semantics and correlation mechanism) of WS‐BPEL applications have raised enormous problems to its test case generation, especially in unit testing. Existing studies mainly assume that each path in the control flow graphs that correspond to WS‐BPEL applications is feasible, which always yields imprecise test cases or complicates testing results. The current study tackles this problem based on satisfiability modulo theory solvers. First, a new coverage criterion is proposed to measure the quality of test sets for testing WS‐BPEL applications. Second, decomposition algorithms are presented to obtain test paths that meet the proposed coverage criterion. Finally, this paper symbolically encodes each test path with several constraints by capturing the unique features of WS‐BPEL. These constraints are solved and the test cases (test paths and test data) are obtained with the help of satisfiability modulo theory solvers to test WS‐BPEL applications effectively. Experiments are conducted using our approach and other typical approaches (e.g. message‐sequence generation‐based approach and concurrent path analysis approach) with 10 WS‐BPEL applications. Experimental results demonstrate that the test cases generated by our approach can avoid instantiating idle instance and expose more faults. Copyright © 2015 John Wiley & Sons, Ltd.     

模2~n±1乘法的可重构设计与实现

论文提出了一种可同时实现模2~n±1乘法的算法及其VLSI结构。通过对常规并行前缀加法器和乘法器的改造,在实现普通加法和乘法的基础上增加少量逻辑,实现了模2~n±1乘法(n=8、16、32)。较之同类设计,该设计实现了对常规加法器和乘法器资源的高度重用,而且性能较高。     

On the design of multiple key hashing files for concurrent orthogonal range retrieval between two disks

This paper concerns the following problem: given a set of multi-attribute records, a fixed number of buckets and a two-disk system, arrange the records into the buckets and then store the buckets between the disks in such a way that, over all possible orthogonal range queries (ORQs), the disk access concurrency is maximized. We shall adopt the multiple key hashing (MKH) method for arranging records into buckets and use the disk modulo (DM) allocation method for storing buckets onto disks. Since the DM allocation method has been shown to be superior to any other allocation methods for allocating an MKH file onto a two-disk system for answering ORQs, the real issue is knowing how to determine an optimal way for organizing the records into buckets based upon the MKH concept.

A performance formula that can be used to evaluate the average response time, over all possible ORQs, of an MKH file in a two-disk system using the DM allocation method is first presented. Based upon this formula, it is shown that our design problem is related to a notoriously difficult problem, namely the Prime Number Problem. Then a performance lower bound and an efficient algorithm for designing optimal MKH files in certain cases are presented. It is pointed out that in some cases the optimal MKH file for ORQs in a two-disk system using the DM allocation method is identical to the optimal MKH file for ORQs in a single-disk system and the optimal average response time in a two-disk system is slightly greater than one half of that in a single-disk system.     

Parallelization of WHILE loops on pipelined architectures

Modulo scheduling theory can be applied successfully to overlap Fortran DO loops on pipelined computers issuing multiple operations per cycle both with and without special loop architectural support. This paper shows that a broader class of loops—REPEAT-UNTIL, WHILE, and loops with more than one exit, in which the trip count is not known beforehand—can also be overlapped efficiently on multiple-issue pipelined machines. The approach is described with respect to a specific machine model, but it can be extended to other models. Special features in the architecture, as well as compiler representations for accelerating these loop constructs, are discussed. Performance results are presented for a few select examples.An earlier version of this paper was presented at Supercomputing '90.     

基于Craig插值的线性混成系统符号化模型检测

最强后件的计算是模型检测算法的核心.本文使用一阶逻辑可满足性模线性算术理论给出线性混成自动机的有界模型检测表示公式,利用一阶逻辑公式不可满足情况下的插值存在性定理,对线性混成自动机的有界模型检测公式进行指定的划分,使用支持线性算术插值计算的可满足性模理论后端证明引擎的线性时间复杂度的消解反证技术获得这两部分公式间的插值公式,按一阶逻辑Craig插值的性质,所得到的插值公式就是模型检测过程中最强后件公式的上近似表示.有效地避免了使用逻辑编码方案实现线性混成自动机模型检测过程中需要双指数时间复杂度的量词消去操作求取最强后件公式,也不需像有界模型检测按步长展开变迁公式进行可满足性判定.最后本文在此最强后件计算的基础上,以有界模型检测技术作为反例确认方法,实现了一种无假反例的混成系统近似可达集计算算法.实验证明该算法与目前已经得到广泛工业应用的有界模型检测算法相比具有更优的性能.     

TMS320C6X的SPLOOP技术

软件流水是一种实现循环迭代中指令级并行的指令调度技术。它可以克服多周期指令延迟对CPU处理性能的影响,保证循环核的运行效率最优。从C64X+开始,TMS320C6X系列DSP引入SPLOOP技术,软件上增加SPLOOP(D/W)、SPKERNEL等相关指令,硬件上增加软件流水缓存等专用模块,通过模调度软件流水模式,有效缩小了软件代码量,提升了执行代码效率。一般情况下,采用SPLOOP技术后机器编译输出的循环代码质量很高,编程人员无需再对代码进行进一步的手工优化。     

Fast dynamic casting

We describe a scheme for implementing dynamic casts suitable for systems where the performance and predictability of performance is essential. A dynamic cast from a base class to a derived class in an object‐oriented language can be performed quickly by having the linker assign an integer type ID to each class. A simple integer arithmetic operation verifies whether the cast is legal at run time. The type ID scheme presented uses the modulo function to check that one class derives from another. A 64‐bit type ID is sufficient to handle class hierarchies of large size at least nine levels of derivation deep. We also discuss the pointer adjustments required for a C++ dynamic_cast. All examples will be drawn from the C++ language. Copyright © 2005 John Wiley & Sons, Ltd.