Efficient test case generation for validation of UML activity diagrams

Unified Modeling Language (UML) is widely used as a system level specification language in embedded system design. Due to the increasing complexity of embedded systems, the analysis and validation of UML specifications is becoming a challenge. UML activity diagram is promising to modeling the overall system behavior. However, lack of techniques for automated test case generation is one major bottleneck in the UML activity diagram validation. This article presents a methodology for automatically generating test cases based on various model checking techniques. It makes three primary contributions: First, we propose coverage-driven mapping rules that can automatically translate activity diagram to formal models. Next, we present a procedure for automatic property generation according to error models. Finally, we apply various model checking based test case generation techniques to enable efficient test case generation. Our experimental results demonstrate that our approach can reduce the validation effort drastically by reducing both test case generation time and required number of test cases to achieve a functional coverage goal.     

Logic Design Validation via Simulation and Automatic Test Pattern Generation

We investigate an automated design validation scheme for gate-level combinational and sequential circuits that borrows methods from simulation and test generation for physical faults, and verifies a circuit with respect to a modeled set of design errors. The error models used in prior research are examined and reduced to five types: gate substitution errors (GSEs), gate count errors (GCEs), input count errors (ICEs), wrong input errors (WIEs), and latch count errors (LCEs). Conditions are derived for a gate to be testable for GSEs, which lead to small, complete test sets for GSEs; near-minimal test sets are also derived for GCEs. We analyze undetectability in design errors and relate it to single stuck-line (SSL) redundancy. We show how to map all the foregoing error types into SSL faults, and describe an extensive set of experiments to evaluate the proposed method. These experiments demonstrate that high coverage of the modeled errors can be achieved with small test sets obtained with standard test generation and simulation tools for physical faults.     

Robust Coupling Delay Test Sets

One of the most challenging problems in high-level testing is to reduce the size of a high-level test set while ensuring an adequate fault coverage for various implementations of a function under test. A small and high-coverage test set called a robust coupling delay test set (RCDTS) is derived from the coupling delay test set proposed previously. A partial ordering relationship among delay tests in certain implementations called ??restricted?? gate networks is used to reduce the size of test sets. The RCDTS still detects all robust path delay faults. This result is extended further to the more general balanced inversion parity networks. A test generation program RTGEN for RCDTSs is then developed, and experiments with it show that significant test set reduction can be achieved.     

Test Generation Based on High-Level Assertion Specification for PowerPCTM Microprocessor Embedded Arrays

Test and validation of embedded array blocks remains a major challenge in today's microprocessor design environment. The difficulty comes from twofold, the sizes of the arrays and the complexity of their timing and control. This paper describes a novel test generation methodology for test and validation of microprocessor embedded arrays. Unlike traditional ATPG methods, our test generation method is based upon the high-level assertion specification which is originally used for the purpose of formal verification. The superiority of these assertion tests over the traditional ATPG tests will be discussed and shown through various experiments on recent PowerPC microprocessor designs.     

Design of a transport triggered vector processor for turbo decoding

In order to meet the requirement of high data rates for next generation wireless systems, efficient implementations of receiver algorithms are essential. On the other hand, faster time-to-market motivates the investigation of programmable implementations. This paper presents a novel design of a programmable turbo decoder as an application-specific instruction-set processor (ASIP) using transport triggered architecture (TTA). The processor architecture is designed in such a manner that it can be programmed with high level language to support different suboptimal maximum a posteriori (MAP) algorithms in a single TTA processor. The design enables the designer to change the algorithms according to the frame error rate performance requirement. A quadratic polynomial permutation interleaver is used for contention-free memory access and to make the processor 3GPP LTE compliant. Several optimization techniques to enable real time processing on programmable platforms are introduced. The essential parts of the turbo decoding algorithm are designed with vector function units. Unlike most other turbo decoder ASIPs, high level language is used to program the processor to meet the time-to-market requirements. With a single iteration, 68.35 Mbps decoding speed is achieved for the max-log-MAP algorithm at a clock frequency of 210 MHz on 90 nm technology.     

Switch-level soft error emulation for SET-induced pulses of variable strengths

Due to the increased complexity of modern digital circuits, the use of simulation-based soft error detection methods has become cumbersome and very time-consuming. FPGA-based emulation provides an attractive alternative, as it can not only provide faster speed, but also handle highly complex circuits. In this work, a novel FPGA-based soft error detection technique is proposed, which enables detection of soft errors resulting from voltage pulses of different magnitudes induced by single-event transients (SETs). The paper analyzes the effect of transient injection location on soft error rate (SER) and applies the idea of transient equivalence to minimize resource overhead as well as speed-up emulation process. Switch-level implementations of ISCAS’85 benchmarks are designed using gate-level structures and experimental results are reported. The results show that an application of transient equivalence results in an emulation speed-up of 2.875 and reduces the memory utilization by 65%. An average soft error rate (SER) of 0.7-0.8 was achieved using the proposed strength-based detection with drain as transient injection location, showing that voltage pulses of magnitude smaller than logic threshold can eventually result in soft errors. Furthermore, the presented emulation-based soft error detection technique achieved significant speed-up of the order of 10⁶ compared to a customized simulation-based method.     

Analytical Techniques for Soft Error Rate Modeling and Mitigation of FPGA-Based Designs

Radiation-induced soft errors are the major reliability threat for digital VLSI systems. In particular, field-programmable gate-array (FPGA)-based designs are more susceptible to soft errors compared to application-specific integrated circuit implementations, since soft errors in configuration bits of FPGAs result in permanent errors in the mapped design. In this paper, we present an analytical approach to estimate the soft error rate of designs mapped into FPGAs. Experimental results show that this technique is orders of magnitude faster than the fault injection method while more than 96% accurate. We also present a highly reliable and low-cost soft error mitigation technique which can significantly improve the availability of FPGA-mapped designs. Experimental results show that, using this technique, the availability of an FPGA mapped design can be increased to more than 99.99%.     

High‐speed flow‐based classification on FPGA

Analyzing the composition of Internet traffic has many applications nowadays, like tracking bandwidth‐consuming applications, QoS‐based traffic engineering and lawful interception of illegal traffic. Even though many flow‐based classification methods, such as support vector machines (SVM), have demonstrated their accuracy, few practical implementations of lightweight classifiers exist. We consider in this paper the design of a real‐time SVM traffic classifier at hundreds of Gb/s to allow online detection of categories of applications. We also implement a high‐speed flow reconstruction algorithm able to handle one million concurrent flows. The solution is based on the massive parallelism and low‐level network interface access of FPGA boards. We find maximum supported bit rates up to 408 Gb/s for classification and up to 20 GB/s for flow reconstruction for the most challenging trace. Results are confirmed using a commercial Combov2 board with a Virtex 5 FPGA. Copyright © 2014 John Wiley & Sons, Ltd.     

Testability of artificial neural networks: A behavioral approach

Testability analysis of neural architectures can be performed at a very high abstraction level on the computational paradigm. In this paper, we consider the case of feed-forward multi-layered neural networks. We introduce a behavioral error model which allows good mapping of the physical faults in widely different implementations. Conditions for error controllability, observability and global testability are analytically derived; their purpose is that of verifying whether it is possible to excite all modeled errors and to propagate the error's effects to the primary outputs (actual test vectors being then technological-dependent). Mapping of physical faults onto behavioral errors is performed for some representative, architectures.     

Partial scan design of register-transfer level circuits

Register-transfer level designs that are derived from high-level synthesis systems generally consist of functional blocks and registers that are interconnected by multiplexers and buses to maximize resource sharing These multiplexer and bus structures have the unique ability to behave asswitches, i.e., to logically partition the circuit when their control inputs are manipulated in different ways. The presence of switches, the selection of scan registers can be influenced. This leads to an efficient partial scan methodology presented in this paper. Second, switches help set up data transfer paths calledI-paths. By employingI-paths to transport test data, the functional logic in the circuit can be separated from the switching logic for the purpose of test generation. This can lead to a reduction in test generation costs for a partial scan design. Thus the techniques presented in this paper help to minimize both testability overhead and test generation cost in bus-based circuits. This methodology is implemented in the SIESTA system for serial scan design.     

Portable video-on-demand in wireless communication

Our present ability to work with video has been confined to a wired environment, requiring both the video encoder and decoder to be physically connected to a power supply and a wired communication link. This paper describes an integrated approach to the design of a portable video-on-demand system capable of delivering high-quality image and video data in a wireless communication environment. The discussion will focus on both the algorithm and circuit design techniques developed for implementing a low-power video compression/decompression system at power levels that are two orders of magnitude below existing solutions. This low-power video compression system not only provides a compression efficiency similar to industry standards, but also maintains a high degree of error tolerance to guard against transmission errors often encountered in wireless communication. The required power reduction can best be attained through reformulating compression algorithms for energy conservation. We developed an intra-frame compression algorithm that requires minimal computation energy in its hardware implementations     

Built-in testable error detection and correction

A method for design of built-in testable (BIT) error detection and correction (EDAC) circuits is presented that uses up to 65% less test hardware than customary BIT implementations. A 1-μm CMOS, 16-bit EDAC designed and fabricated with this technique exhibits >99% fault coverage in 10 μs at 25 MHz. Built-in test impacts the speed performance by only one gate delay regardless of the size of the EDAC. Various faults are injected into the chip to verify the effectiveness of built-in test     

A method for automatic design error location and correction in combinational logic circuits

We present a new diagnostic algorithm, based on backward-propagation, for localising design errors in combinational logic circuits. Three hypotheses are considered, that cover all single gate replacement and insertion errors. Diagnosis-oriented test patterns are generated in order to rapidly reduce the suspected area where the error lies. The originality of our method is the use of patterns which do not detect the error, in addition to detecting patterns. A theorem shows that, in favourable cases, only two patterns suffice to get a correction. We have implemented the test generation and diagnosis algorithms. Results obtained on benchmarks show that the error is always found, after the application of a small number of test patterns, with an execution time proportional to the circuit size. This work is partially supported by EUREKA “JESSI-AC3” project and the ESPRIT Basic Research Action CHARME Working Group #6018.     

A Biased Random Instruction Generation Environment for Architectural Verification of Pipelined Processors

Architectural verification is a critical aspect of the microprocessor design cycle. In this paper, we present a design verification environment centered around a biased random instruction generator for simulation-based architectural verification of pipelined microprocessors. The instruction generator uses biases specified by the user to generate instruction sequences for simulation. These biases are not hard-coded and can thus be changed depending on the specific areas in the design and type of design errors being targeted. Correctness checking is achieved using assertion checking and end-of-state comparison with a high-level architectural model. Several architectural-level errors are introduced into a behavioral model of the DLX processor to investigate the processor's response in the presence of design errors. Simulation experiments conducted using the behavioral model show that biased random instruction sequences provide higher coverage of RTL conditional branches and design errors than random instruction sequences or manually-generated test programs. Furthermore, instruction sequences containing a high percentage of read-after-write (RAW) and control dependencies are the most useful.     

Experience in Validation of PowerPCTM Microprocessor Embedded Arrays

Design validation for embedded arrays remains as a challenging problem in today's microprocessor design environment. Although several methods for validating embedded arrays have been proposed, not much has been done to characterize the strengths and weaknesses of these methods. This paper provides a comprehensive study of various design validation approaches adopted at the Somerset PowerPC Design Center in the past, including methods from both formal verification and test generation. Effectiveness of these approaches will be measured based on automatic design error injection and simulation at both gate and transistor levels. Experience of using different validation approaches on recent PowerPC microprocessor arrays will be analyzed and discussed.     

Fast software implementation of error detection codes

Software implementations of error detection codes are considered to be slow compared to other parts of the communication system. This is especially true for powerful error detection codes such as CRC. However, we have found that powerful error detection codes can run surprisingly fast in software. We discuss techniques for, and measure the performance of, fast software implementation of the cyclic redundancy check (CRC), weighted sum codes (WSC), one's-complement checksum, Fletcher (1982) checksum, CXOR checksum, and block parity code. Instruction count alone does not determine the fastest error detection code. Our results show the computer memory hierarchy also affects performance. Although our experiments were performed on a Sun SPARCstation LX, many of the techniques and conclusions will apply to other processors and error detection codes. Given the performance of various error detection codes, a protocol designer can choose a code with the desired speed and error detection power that is appropriate for his network and application     

MMV: A Metamodeling Based Microprocessor Validation Environment

With increasing levels of integration of multiple processing cores and new features to support software functionality, recent generations of microprocessors face difficult validation challenges. The systematic validation approach starts with defining the correct behaviors of the hardware and software components and their interactions. This requires new modeling paradigms that support multiple levels of abstraction. Mutual consistency of models at adjacent levels of abstraction is crucial for manual refinement of models from the full chip level to production register transfer level, which is likely to remain the dominant design methodology of complex microprocessors in the near future. In this paper, we present microprocessor modeling and validation environment (MMV), a validation environment based on metamodeling, that can be used to create models at various abstraction levels and to generate most of the important validation collaterals, viz., simulators, checkers, coverage, and test generation tools. We illustrate the functionalities in MMV by modeling a 32-bit reduced instruction set computer processor at the system, instruction set architecture, and microarchitecture levels. We show by examples how consistency across levels is enforced during modeling and also how to generate constraints for automatic test generation.