Testing Conditions for Communicating Stream X-machine Systems

X-machines were proposed by Holcombe as a possible specification language and since then a number of further investigations have demonstrated that the model is intuitive and easy to use. In particular, stream X-machines (SXM), a particular class of X-machines, have been found to be extremely useful in practice. Furthermore, a method of testing systems specified as SXMs exists and is proved to detect all faults of the implementation provided that the system meets certain “design for test conditions”. Recently, a system of communicating SXMs was introduced as a means of modelling parallel processing. This paper proves that each communicating machine component can be transformed in a straightforward manner so that the entire system will behave like a single stream X-machine - the equivalent SXM of the system. The paper goes on to investigate the applicability of the SXM testing method to a system of communicating SXMs and identifies a class of communicating SXMs for which the equivalent SXM of the system meets the “design for test conditions”. Received November 1999 / Accepted in revised form June 2001     

Generalised Stream X-Machines with Output Delimited Type

Some conditions relating to the automata involved in the W-testing method are discussed. It is also shown how to use the method for reduced automata instead of minimal automata. New design test conditions (weak output distinguishable, strong test-complete and output delimited type) are considered for the generalised stream X-machines (stream X-machines with basic functions replaced by relations and having as output strings of symbols rather than single symbols). It is proved that testing methods similar to those already developed for ordinary deterministic stream X-machines may be applied for generalised stream X-machines with output delimited types. A particular case of generalised stream X-machine with output delimited type is the X-machine with output delimiter, which produces outputs having a distinct right end character. Received October 2000 / Accepted in revised form January 2001     

Checking experiments for stream X-machines

Stream X-machines are a state based formalism that has associated with it a particular development process in which a system is built from trusted components. Testing thus essentially checks that these components have been combined in a correct manner and that the orders in which they can occur are consistent with the specification. Importantly, there are test generation methods that return a checking experiment: a test that is guaranteed to determine correctness as long as the implementation under test (IUT) is functionally equivalent to an unknown element of a given fault domain Ψ. Previous work has show how three methods for generating checking experiments from a finite state machine (FSM) can be adapted to testing from a stream X-machine. However, there are many other methods for generating checking experiments from an FSM and these have a variety of benefits that correspond to different testing scenarios. This paper shows how any method for generating a checking experiment from an FSM can be adapted to generate a checking experiment for testing an implementation against a stream X-machine. This is the case whether we are testing to check that the IUT is functionally equivalent to a specification or we are testing to check that every trace (input/output sequence) of the IUT is also a trace of a nondeterministic specification. Interestingly, this holds even if the fault domain Ψ used is not that traditionally associated with testing from a stream X-machine. The results also apply for both deterministic and nondeterministic implementations.     

A unified integration and component testing approach from deterministic stream X-machine specifications

One of the great benefits of using a stream X-machine to specify a system is its associated testing method. Under certain design for test conditions, this method produces a test suite that can determine the correctness of the implementation under test (IUT), provided that the basic components of the stream X-machine model have been correctly implemented. However, such an approach implies that each component can be tested in isolation from the rest of the system. This is a limitation that, in practice, can be resolved by developing stubs and drivers. However, this adds complexity to the testing process and, furthermore, these new pieces of software can introduce faults that can invalidate the theoretical results of the aforementioned testing method. This paper extends the approach by allowing component testing to be performed in parallel with integration testing, while still guaranteeing the IUT correctness under the given design for test conditions. It also shows how the integration test suite, produced in previous publications, can be reduced.     

一种适用于POP工艺GNC模块的测试系统设计

高可靠性POP工艺的GNC模块,创新采用了无框架结构,以三维互连为层规划准则,集成了信息处理组件和多种传感器,通过三维堆叠实现了立体互连,形成具有多种外设接口的正交立体集成结构的导航制导通信模块;由于其高集成度和小型化的特点而大大增加了测试难度;采用主从协同系统设计方法,构建了一种针对小型化航天电子产品的新型测试系统,测试系统硬件部分采用通用化、标准化设计,实现对产品在特殊环境条件下的测试;软件架构采用分层构件化设计,将单元测试和专项测试相结合,对产品各项功能和性能实行独立测试;经实际应用满足了对GNC产品的测试需求,该测试系统功能齐全,操作简单,利于总体维护及系统级调试,是对GNC模块可测性、可算性的巨大提升。     

Accurate Depth of Field Simulation in Real Time

We present a new post processing method of simulating depth of field based on accurate calculations of circles of confusion. Compared to previous work, our method derives actual scene depth information directly from the existing depth buffer, requires no specialized rendering passes, and allows easy integration into existing rendering applications. Our implementation uses an adaptive, two‐pass filter, producing a high quality depth of field effect that can be executed entirely on the GPU, taking advantage of the parallelism of modern graphics cards and permitting real time performance when applied to large numbers of pixels.     

Testing Conformance to a Quasi-Non-Deterministic Stream X-Machine

Stream X-machines have been used in order to specify a range of systems. One of the strengths of this approach is that, under certain well-defined conditions, it is possible to produce a finite test that is guaranteed to determine the correctness of the implementation under test (IUT). Initially only deterministic stream X-machines were considered in the literature. This is largely because the standard test algorithm relies on the stream X-machine being deterministic. More recently the problem of testing to determine whether the IUT is equivalent to a non-deterministic stream X-machine specification has been tackled. Since non-determinism can be important for specifications, this is an extremely useful extension. In many cases, however, we wish to test for a weaker notion of correctness called conformance. This paper considers a particular form of non-determinism, within stream X-machines, that will be called quasi-non-determinism. It then investigates the generation of tests that are guaranteed to determine whether the IUT conforms to a quasi-non-deterministic stream X-machine specification. The test generation algorithm given is a generalisation of that used for testing from a deterministic stream X-machine. Received November 1999 / Accepted in revised form December 2000     

Dynamic Frame Dropping for Bandwidth Control in MPEG Streaming System

In a network environment where the available bandwidth changes dynamically, it is desirable for a streaming system to control the media quality in an adaptive way according to the dynamics of underlying network resource. This paper presents the implementation of a real-time MPEG filtering system which uses the concept of dynamic frame-drop. The filtering system drops video frames in a controlled way and reconstructs a valid MPEG system stream in real-time. The system consists of a sequence of filtering modules and each module is carefully designed to maintain the synchronization characteristics of real-time streaming. A special effort is given to the correct implementation of video and audio synchronization after frame-drop. The experiments show that the implemented system produces a valid MPEG system stream after filtering as well as the media bandwidth of a filtered stream is dynamically controlled by a given frame-drop policy.     

面向Dataflow的异构集群混合式资源调度框架研究

Dataflow模型的使用,使得大数据计算的批处理和流处理融合为一体.但是,现有的针对大数据计算的集群资源调度框架,要么面向流处理,要么面向批处理,不适合批处理与流处理作业共享集群资源的需求.另外,GPU用于大数据分析计算时,由于缺乏有效的CPU-GPU资源解耦方式,降低了资源使用效率.在分析现有的集群资源调度框架的基础上,设计并实现了一种可以感知批处理/流处理应用的混合式资源调度框架HRM.它以共享状态架构为基础,采用乐观封锁协议和悲观封锁协议相结合的方式,确保流处理作业和批处理作业的不同资源要求.在计算节点上,提供CPU-GPU资源的灵活绑定,采用队列堆叠技术,不但满足流处理作业的实时性需求,也减少了反馈延迟并实现了GPU资源的共享.通过模拟大规模作业的调度,结果显示,HRM的调度延迟只有集中式调度框架的75%左右;使用实际负载测试,批处理与流处理共享集群时,使用HRM调度框架,CPU资源利用率提高25%以上;而使用细粒度作业调度方法,不但GPU利用率提高2倍以上,作业的完成时间也能够减少50%     

rCOS: a formal model-driven engineering method for component-based software

Model-driven architecture (MDA) has become a main stream technology for software-intensive system design. The main engineering principle behind it is that the inherent complexity of software development can only be mastered by building, analyzing and manipulating system models. MDA also deals with system complexity by providing component-based design techniques, allowing independent component design, implementation and deployment, and then system integration and reconfiguration based on component interfaces. The model of a system in any stage is an integration of models of different viewpoints. Therefore, for a model-driven method to be applied effectively, it must provide a body of techniques and an integrated suite of tools for model construction, validation, and transformation. This requires a number of modeling notations for the specification of different concerns and viewpoints of the system. These notations should have formally defined syntaxes and a unified theory of semantics. The underlying theory of the method is needed to underpin the development of tools and correct use of tools in software development, as well as to formally verify and reason about properties of systems in mission-critical applications. The modeling notations, techniques, and tools must be designed so that they can be used seamlessly in supporting development activities and documentation of artifacts in software design processes. This article presents such a method, called the rCOS, focusing on the models of a system at different stages in a software development process, their semantic integration, and how they are constructed, analyzed, transformed, validated, and verified.     

一个面向分布式程序的测试系统框架

提出了一个面向分布式程序的测试系统框架TFDS(test system framework for distributed software system),并介绍了它在异构网络中的一个实现原型PSET*(distributed progra m structure and event trace, revised version).框架的主要功能是对分布式程序进行单 元测试和集成测试.包括面向规约设计和源码分析的静态部分和面向程序执行和事件序列分 析的动态部分.在构件的基础上,PSET*的功能可以较容易     

Generating Test Sets from Non-Deterministic Stream X-Machines

X-machines were proposed by Holcombe as a possible specification language and since then a number of further investigations have demonstrated that the model is intuitive and easy to use as well as general enough to cater for a wide range of applications. In particular (generalised) stream X-machines have been found to be extremely useful as a specification method and most of the theory developed so far has concentrated on this particular class of X-machines. Furthermore, a method for testing systems specified by stream X-machines exists and is proved to detect all faults of the implementation provided that the system meets certain initial requirements. However, this method can only be used to generate test sequences from deterministic X-machine specifications. In this paper we present the theoretical basis for a method for generating test sets from non-deterministic generalised stream X-machines. Received November 1999 / Accepted in revised form September 2000     

UCov: a user‐defined coverage criterion for test case intent verification

The goal of regression testing is to ensure that the behaviour of existing code, believed correct by previous testing, is not altered by new program changes. This paper argues that the primary focus of regression testing should be on code associated with (1) earlier bug fixes and (2) particular application scenarios considered to be important by the developer or tester. Existing coverage criteria do not enable such focus, for example, 100% branch coverage does not guarantee that a given bug fix is exercised or a given application scenario is tested. Therefore, there is a need for a new and complementary coverage criterion in which the user can definea test requirement characterizing a given behaviour to be covered as opposed to choosing from a pool of pre‐defined and generic program elements. This paper proposes this new methodology and calls it UCov, a user‐defined coverage criterion wherein a test requirement is an execution pattern of program elements, and possibly predicates, that a test case must satisfy. The proposed criterion is not meant to replace existing criteria, but to complement them as it focuses the testing on important code patterns that could go untested otherwise. UCov supports test case intent verification. For example, following a bug fix, the testing team may augment the regression suite with the test case that revealed the bug. However, this test case might become obsolete due to code modifications not related to the bug. But if a test requirement characterizing the bug was defined by the user, UCov would determine that test case intent verification failed. The UCov methodology was implemented for the Java platform, was successfully applied onto 10 real‐life case studies and was shown to have advantages over JUnit. The implementation comprises the following tools: (1) TRSpec: allows the user to easily specify complex test requirements; (2) TRCheck: checks whether user‐defined test requirements were satisfied, that is, supports test case intent verification; and (3) TRMigrate: migrates user‐defined test requirements to subsequent versions of a given program. Copyright © 2016 John Wiley & Sons, Ltd.     

Polynomial multiplication on systolic arrays

In this article, we show how the multiplication of polynomials can be performed in a pipelined fashion on a systolic array in linear time steps. The computational model consists of two linear systolic arrays with 2(n+1) processing elements used and (m+2n+2) running time steps needed, where m, n are the degrees of the two given polynomials, respectively. Since the same types of processing elements execute the same program, it is suitable for VLSI implementation. This algorithm is also proved to be correct.     

基于FPGA的传感数据加速处理*

随着传感器网络技术的快速发展,实时处理海量的高速的传感数据为现有数据处理技术提出许多挑战。利用非对称性多核系统加速特殊操作是当前计算机体系结构发展的一种趋势,是解决物联网应用实时响应的有效途径。本文提出一种基于FPGA加速处理传感数据中位数计算的方法,包括计算模型、符合FPGA设计限制的实现过程,把FPGA连接到系统的其他部分的适当的融合策略,实验表明与通用CPU相比,本文提出的基于FPGAs的加速数据处理策略在功耗和并行传感数据流评价方面具有明显的优势,可以广泛地应用于物联网中前端轻量级数据预处理节点的设计与实现。     

数字化保护装置自动测试系统

为了进一步提高数字化保护装置的自动化测试程度,在对现有测试软件研究的基础之上,从装置研发测试实际需求和原理出发,设计出一套能同时支持多台数字化装置的自动测试系统。该软件最大限度的继承现有自动测试软件优点,采用分布式体系结构和模块化设计思想,充分运用现有计算机软件及网络技术,实现多台装置闭环自动测试。实践证明,该软件在继电保护装置研发测试中的应用,能大大提高测试效率和测试的充分性,进一步保证装置的可靠性。     

Bug localization by constructing reduced traces

A method, based on the existing UniTESK test, which finds a bug in a system under test, is proposed to construct the minimal test that finds the same bug. This test can be used to localize this bug in the source code of the system. Two strategies for constructing such a test are considered, a comparative analysis of their advantages and disadvantages is performed, and the optimal strategy is proposed. A mathematical justification of the proposed method is given. An algorithm implementing this method is described, and its correctness is proved. An implementation of the proposed method for the CTESK testing tool is described.     

AFC系统异常连接测试工具的设计与实现

北京地铁车站设备和系统对异常数据的处理是否符合北京轨道交通AFC系统设计及实施规范要求,是地铁新线接入测试的必须环节。针对当前测试方法自动化程度不高,测试人员需要对AFC系统有详细了解才能很好地完成异常数据处理测试的问题,通过分析测试工作的内容,归纳测试数据与测试流程的种类,设计实现了具有自动生成测试数据、自动执行测试用例功能的异常连接测试工具;通过实际测试验证了设计工具功能的有效性。     

一种针对交互式软件的测试用例生成模型研究与实现

测试用例的自动生成是软件测试的一个重要方面，测试用例生成的复杂度与质量直接影响测试的效率和覆盖面，已有的针对软件功能测试的自动测试理论和方法在针对CAD和图像处理这类人机交互复杂、系统状态繁多的系统时，因复杂度大或者测试效率较低而难以在实际中应用．本文提出的一种针对复杂人机交互软件的测试模型一基于功能对象的测试用例生成模型，将用户使用被测试系统的操作流程看成是若干个处理过程的组合，采用面向对象的思想将用户的操作流程进行分解和封装，构建出用以生成测试流程的功能对象，并依照一定约束条件对功能对象的实例进行重组，派生出测试用例．本文提出的测试用例生成模型，已在三维数字化设计系统的专用测试平台CADTesting中成功实现，实践证明，该模型与现有的一些模型相比，实现复杂度低且测试用例的质量较高．     

GPGPU computation and visualization of three-dimensional cellular automata

This paper presents a general-purpose simulation approach integrating a set of technological developments and algorithmic methods in cellular automata (CA) domain. The approach provides a general-purpose computing on graphics processor units (GPGPU) implementation for computing and multiple rendering of any direct-neighbor three-dimensional (3D) CA. The major contributions of this paper are: the CA processing and the visualization of large 3D matrices computed in real time; the proposal of an original method to encode and transmit large CA functions to the graphics processor units in real time; and clarification of the notion of top-down and bottom-up approaches to CA that non-CA experts often confuse. Additionally a practical technique to simplify the finding of CA functions is implemented using a 3D symmetric configuration on an interactive user interface with simultaneous inside and surface visualizations. The interactive user interface allows for testing the system with different project ideas and serves as a test bed for performance evaluation. To illustrate the flexibility of the proposed method, visual outputs from diverse areas are demonstrated. Computational performance data are also provided to demonstrate the method’s efficiency. Results indicate that when large matrices are processed, computations using GPU are two to three hundred times faster than the identical algorithms using CPU.