We propose a hybrid approach for automatic generation of System Verilog assertions from natural-language specifications by combining machine-learning and formal analysis of the input text. The formal analysis focuses on parsing the input text, while the machine learning engine focuses on translating the input text to formal logic and/or assertions. Such a hybrid reduces the burden of a purely machine-learning based translation and increases accuracy in the generated assertions, especially for those complex assertions. In addition, the proposed hybrid approach offers a novel method to validate the assertions generated, in which the results of different machine-learning models are used to determine the confidence of the hybrid approach.

Automatic creation of formal models from natural language specifications can help reduce design time and manual errors. However, the accuracy of the translation may not be high due to the ambiguous, incomplete, and inconsistent nature of natural language. Specifications written in a controlled natural language (CNL) can overcome the problems associated with natural language translation and deliver similar benefits in automation. However, a user has to learn to write in a CNL. We propose a suggestions framework that provides automatic feedback to assist users in writing specifications in CNL. Our feedback generates different ways of writing CNL acceptable sentences when the input sentence is not understood. We developed a ranking scheme to ensure the semantics of generated suggestions are closer to the input specification’s intent. We evaluated the framework on 132 erroneous specifications taken from AMBA and memory controller architectures documents. Our system generated suggestions for all the specs. On manual inspection, we found that 87% of these suggestions were semantically closer to the intent of the input specification.

We propose a framework for extracting natural language assertions from hardware design specification documents. The entire parse tree of each input sentence in a design spec is viewed as a network of words connected to facilitate the creation of semantic frames. We employ a lexicalized grammar that associates words with both semantic and syntactic relations that assist in filling the slots in the semantic frames. At the same time, the accuracy of the extracted semantics is ensured by the incremental understanding algorithm that is guided by both syntactic and semantic rules of the hardware verification domain. We evaluated the framework by writing assertions taken from specification documents of the Memory controller, UART, and the AMBA ACE protocol. System Verilog Assertions (SVA) were automatically generated from logical expressions. Since accuracy is of paramount importance, whenever a complex sentence cannot be understood. we identify and report to the user.

We explore contemporary natural language processing (NLP) techniques for converting NL specifications found in design documents directly to an temporal logic-like intermediate representation (IR). Generally, attempts to use NLP for assertion generation have relied on restrictive sentence formats and grammars as well as being difficult to handle new sentence formats. We tackle these issues by first implementing a system that uses commonsense mappings to process input sentences into a normalized form. Then we use frame semantics to convert the normalized sentences into an IR based on the information and context contained in the Frames. Through this we are able to handle a large number of sentences from real datasheets allowing for complex formats using temporal conditions, property statements, and compound statements; all order agnostic. Our system can also be easy extended by modifying an external, rather than internal, commonsense knowledge-base to handle new sentence formats without requiring code changes or intimate knowledge of the algorithms used.

Mutations in the RTL design can help test generation to uncover bugs. However, since the mutant space is infinite, identifying the right mutants is critical. In this paper, we present two filtering approaches to identify the key mutants without loss in the branch coverage. The final set of test vectors generated is able to achieve both high branch coverage and mutation coverage. Experimental results show that we were able to reduce the overall test generation time up to 85% for all ITC99 benchmarks. In addition, we also found that the test suite length also decreased up to 78% for most of the ITC99 circuits.

In this paper, we explore the relationship between fault coverage for sequential circuits and the observed entropy during test application. We find that the entropy measured at a subset of the primary and pseudo-primary outputs is highly and significantly correlated to the regions of the design that are exercised by the test vectors. Consequently, they can be used for estimating the coverages for the newly generated test sets. As computing the entropy requires only logic simulation, it can greatly speed up the fault grading process. In our experiments on the ISCAS'89 benchmarks, we are able to achieve an average root mean squared error of 2.1% in fault coverage estimation for test sets of varying lengths, together with an order of magnitude speedup over fault simulation.

The test patterns computed for detecting the manufacturing defects in the electronic circuits are generally insufficient for diagnosis. The test set compaction and failure log truncation lead to loss of critical failure observations that diagnosis might depend on. In this context, it is beneficial to know the diagnostic usefulness of failures so that we can log the more useful failures instead of logging the initial failures. In this paper, we evaluate three metrics to gauge such diagnostic usefulness in real-time by observing the circuit responses on the tester. We implement a pattern selection framework for failure logging and compare the results with those achieved by logging the initial failures. Using one of our proposed metrics, we were able to improve the diagnosis quality for a significant number of faulty instances of ISCAS'89 and IWLS'05 benchmarks having 1-7 inserted stuck-at and transition faults.

In this paper, we propose a functional test generation method for Register Transfer Level (RTL) designs by systematically performing highly efficient radial searches starting from heuristically selected system states. During test generation, we track the executed path with a lightweight instrumentation and classify tests that have enabled different or unique executions. Our approach heuristically targets least explored paths, unlike methods that simply try to maximize branches reached. We obtain an overall high branch coverage upon directing the testing effort along the exploration around such paths. The unique paths executed are represented in the form of a Search Tree. A path-oriented selection metric which distinguishes tests that cover least explored paths selects the best next starting state from the Search Tree. Our work is engineered with the goal of being able to produce tests for hard-to-reach states using a lean search-based approach, rather than expensive formal or semi-formal constraint-based methods. Experimental results over benchmarks from ITC '99 and IWLS-2005 show that our method rapidly generates short tests that achieve high coverages.

In this paper, we present CORT, a factored concolic execution based methodology for high-level functional test generation. Our test generation effort is visualized as the systematic unraveling of the control-flow response of the design over multiple explorations. We begin by transforming the Register Transfer Level (RTL) source for the design into a high-performance C++ compiled functional simulator which is instrumented for branch coverage. An exploration begins by simulating the design with concrete stimuli. Then, we perform an interleaved cycle-by-cycle symbolic evaluation over the concrete execution trace extracted from the Control Flow Graph (CFG) of the design. The purpose of this task is to dynamically discover means to divert the control flow of the system, by mutating primary-input stimulated control statements in this trace. We record the control-flow response as a Test Decision Tree (TDT), a novel representation for the test generation effort. Successive explorations begin at system states heuristically selected from a global TDT, onto which each new decision tree resultant from an exploration is stitched. CORT succeeds at constructing functional tests for ITC99 and IWLS-2005 benchmarks that achieve high branch coverage using the fewest number of input vectors, faster than existing methods. Furthermore, we achieve orders of magnitude speedup compared to previous hybrid concrete and symbolic simulation based techniques.

We present a framework for high quality functional test generation at the RTL. The method utilizes static learning to derive cross cycle relationships which helps the search algorithm make inferences about the potential execution path in the next cycle. Additionally, dynamic taint analysis is adapted to model behavioral propagation. Finally, an ant colony optimization swarm intelligence algorithm is combined with an operator level behavioral coverage metric. We show that the method can be used to generate high quality functional test patterns at the RTL. By leveraging RTL code for test generation, we can generate test vectors with comparable levels of coverage up to 100× times faster than gate level ATPG and more than 10× faster than mixed level generation techniques. Additionally, without gate level information, we are able to approach the highest levels of coverage seen by previous techniques and in the case of circuits with deep narrow states, we are able to greatly exceed gate level ATPG performance including generating patterns for b12word and FABSCALAR, which prior ATPG techniques are unable to sufficiently handle.

In this paper, we propose a functional test generation method for Register Transfer Level circuits. A popular metric for measuring the effectiveness of an RTL test suite is branch coverage. The challenge in exercising a hard-to-reach branch is in the understanding of the semantics of the design. Without a good guidance, hard branches might require unnecessarily long test sequences or missed altogether. In our method, we extract such semantics from the circuit using a lightweight static analysis of the code in order to guide the search. Experimental results show that a high level of coverage can be obtained for several benchmark circuits, while reducing the test vector lengths by up to two orders of magnitude in some circuits.

We present SI-SMART, a hybrid Swarm Intelligence and Satisfiability Modulo theory based Automatic Register Transfer level test generator. Traditional Bounded Model Checking (BMC) or symbolic execution based methods depend upon multi-cycle circuit unrolling/analysis for stimuli generation. The presence of loops in the design under test (DUT) typically limits such methods, resulting in lower design coverage. SI-SMART tackles this problem by eliminating explicit unrolling of the control flow graph (CFG). This is achieved by abstracting loops present in the design under test (DUT) and attempting to learn the recurrence relations among the variables that directly or indirectly affect the target branch condition. An SMT solver is used to find correlations between the inputs and the target branches. This learned knowledge is later fed back to a combination of Binary Particle Swarm Optimization (BPSO) and Hooke Jeeves method to attempt to reach the uncovered branches. SI-SMART is evaluated on several difficult variants of ITC99 benchmark circuits. 100% branch coverage is achieved in almost all circuits with significant improvement in branch coverage, test sequence lengths and execution times over existing methods.

Diagnosis of each failed part requires the failed data captured on the test equipment. However, due to memory limitations on the tester, one often cannot store all the failed data for every chip tested. Consequently, truncated failure logs are used instead of complete logs for each part. Such truncation of the failure logs can result in very long turn-around times for diagnosis because important failure points may be removed from the log. Subsequently, the accuracy and resolution of final diagnosis may suffer even after multiple iterations of diagnosis. In addition, the existing test response compaction techniques though good for testing, either adversely affect diagnosis or are highly sensitive to deviation from the chosen fault model. In this context, the industry needs dynamic selection of better failure logs that enhances diagnosis. In this paper, we propose a number of metrics based on information theory that may help in selecting failure logs dynamically for improving the accuracy and resolution of final diagnosis. We also report on the efficacy of these metrics through the results of our experiments.

Functional test generation and design validation frequently use stochastic methods for vector generation. However, for circuits with narrow paths or random-resistant corner cases, purely random techniques can fail to produce adequate results. Deterministic techniques can aid this process; however, they add significant computational complexity. This paper presents a Register Transfer Level (RTL) abstraction technique to derive relationships between inputs and path activations. The abstractions are built off of various program slices. Using such a variety of abstracted RTL models, we attempt to find patterns in the reduced state and input with their resulting branch activations. These relationships are then applied to guide stimuli generation in the concrete model. Experimental results show that this method allows for fast convergence on hard-to-reach states and achieves a performance increase of up to 9× together with a reduction of test lengths compared to previous hybrid search techniques.

Automatic test pattern generation for non-scan sequential circuits is an extremely challenging task. If successful, it can offer many benefits to the EDA community, ranging from manufacturing and functional test to post-silicon validation. High-level test generators often miss the low-level details, thus missing the detection of some gate-level faults. On the other hand, gate-level test generators miss the high-level path traversal knowledge to more effectively traverse the state space. In this work, we present a fine-grain mixed-level test generator that utilizes co-simulation of register-transfer and gate levels to generate high quality vectors. The algorithm, based on an ant colony optimization, targets branch coverage at the RTL and simultaneously attempts to associate rare fault excitations with a sequence of branch activations. By weighting these sequences within the fitness function across the two levels, the algorithm is able to achieve high fault coverage in the presence of deep hard-to-reach states without scan. The result is that the test sequences obtained offer both high branch coverage as well high stuck-at coverage with low computational costs. In particular, for hard-to-test circuits such as the ITC'99 circuit b12, >98% branch coverage and >90% stuck-at coverage are achieved, vastly improving over other state of the art non-scan tools.

Achieving timing-closure has become one of the hardest tasks in logic synthesis due to the required stringent timing constraints in very large circuit designs. In this paper, we propose a novel synthesis paradigm to achieve timing-closure called Timing-Aware CUt Enumeration (TACUE). In TACUE, optimization is conducted through three aspects: (1) a new divide-and-conquer strategy is proposed that generates multiple sub-cuts on the critical parts of the circuit; (2) two cut enumeration strategies are proposed; (3) an efficient parallel synthesis framework is offered to reduce computation time. Experiments on large and difficult industrial benchmarks show the promise of the proposed method.

A GPU-based timing-aware ATPG is proposed to generate a compact high-quality test set. The test generation algorithm backtraces and propagates along multiple long paths so that many test patterns are generated at the same time. Generated test patterns are then fault simulated and selected. Compared with an 8-core CPU-based timing-aware commercial ATPG, the proposed GPU-based technique achieved 36% test length reductions on large benchmark circuits while the SDQL quality remains almost the same.

We propose a new property-checking-based LBIST architecture which uses hardware monitors to check certain properties in the output responses. If any property is violated, the failing property number is stored for diagnosis. The proposed architecture improves diagnosability considerably with minimal hardware overhead. Experimental results show that the diagnostic resolution achieved by our architecture is comparable to that achieved in a non-BIST setup for many circuits.

LBIST is a popular technique for on-chip at-speed testing of digital circuits. In LBIST, output compression techniques are used to reduce hardware overhead of storing test responses but such compression makes diagnosis extremely challenging as the failing vector and the output to which the fault effect propagated are unknown. We propose a new property checking based LBIST architecture which monitors certain properties in the output responses. If any property is violated, the failing vector and property number are stored for diagnosis. The proposed architecture improves diagnosability considerably with minimal hardware overhead. Experimental results show that the diagnostic resolution achieved by our architecture is comparable to the diagnostic resolution achieved in a non-BIST setup for many circuits.

Security of a computer system has been traditionally related to the security of the software or the information being processed. The underlying hardware used for information processing has been considered trusted. The emergence of hardware Trojan attacks violates this root of trust. These attacks, in the form of malicious modifications of electronic hardware at different stages of its life cycle, pose major security concerns in the electronics industry. An adversary can mount such an attack with an objective to cause operational failure or to leak secret information from inside a chip-e.g., the key in a cryptographic chip, during field operation. Global economic trend that encourages increased reliance on untrusted entities in the hardware design and fabrication process is rapidly enhancing the vulnerability to such attacks. In this paper, we analyze the threat of hardware Trojan attacks; present attack models, types, and scenarios; discuss different forms of protection approaches, both proactive and reactive; and describe emerging attack modes, defenses, and future research pathways.

Although stochastic search techniques have shown promise in test generation and design validation, they often fail when there is a specific, random-resistant sequence of vectors required to exercise a target. In order to combat this, deterministic techniques are added, resulting in a hybrid solution to maintain high speed of execution while improving metric performance. This paper presents a formal hybridization that combines a Register Transfer Level (RTL) stochastic swarm intelligence based test vector generation with the Verilator Verilog-to-C++ source-to-source compiler. Verilator generates a fast cycle accurate C++ simulation unit for Verilog descriptions and provides instrumentation for branch and toggle coverage metrics. This RTL model can also be used to generate a bounded model checking (BMC) instance. During the stochastic search, the bounded model checker is launched to expand the unexplored search frontier and aid in the navigation of narrow paths. Additionally, an inductive reach ability test is applied in order to eliminate unreachable branches from our search space. These additions have significantly improved branch coverage, reaching 100% in several ITC99 benchmarks. Additionally, compared to previous functional test generation methods, we achieve substantial speedup achieved with purely stochastic methods.

We propose a new method to derive a small number of LFSR seeds for Logic BIST to cover all detectable faults as a first-order satisfiability problem involving extended theories. We use an SMT (Satisfiability Modulo Theories) formulation to efficiently combine the tasks of test-generation and seed-computation. We make use of this formulation in an iterative seed-reduction flow which enables the “chaining” of hard-to-test faults using very few seeds. Experimental results demonstrate that up to 79% reduction in the number of seeds can be achieved.

Currently, BDD packages such as CUDD depend on chained hash tables. Although they are efficient in terms of memory usage, they exhibit poor cache performance due to dynamic allocation and indirections of data. Moreover, they are less appealing for concurrent environments as they need thread-safe garbage collectors. Furthermore, to take advantage of the benefits from multi-core platforms, it is best to re-engineer the underlying algorithms, such as whether traditional depth-first search (DFS) construction, breadth-first search (BFS) construction, or a hybrid BFS with DFS would be best. In this paper, we introduce a novel BDD package friendly to multicore platforms that builds on a number of heuristics. Firstly, we re-structure the Unique Table (UT) using a concurrency-friendly Hopscotch hashing to improve caching performance. Secondly, we re-engineer the BFS Queues with hopscotch hashing. Thirdly, we propose a novel technique to utilize BFS Queues to simultaneously work as a Computed Table (CT). Finally, we propose a novel incremental Mark-Sweep Garbage Collector (GC). We report results for both BFS and hybrid BFS-DFS construction methods. With these techniques, even with a single-threaded BDD, we were able to achieve a speedup of up to 8× compared to a conventional single-threaded CUDD package. When two-threads are launched, another 1.5× speedup is obtained.

One of the important challenges in testing modern SOCs is the presence of small embedded memories. These memories are too small to employ memory BIST. Also, making these embedded memories scan-able or employing MBIST would increase the area overhead and/or test application time.

The effectiveness of Satisfiability (SAT)-based Bounded Model Checking (BMC) critically relies on the deductive power of the BMC instance. Although implication relationships have been used to help SAT solver to make more deductions, too many such implications would result in a large number of clauses and potentially degrade the underlying SAT solver performance. In this paper, we have formulated clause selection as a set-cover problem. Secondly, we have proposed a novel greedy strategy for optimal selection of static logic clauses. This technique maximizes the number of literals that can be deduced by the SAT solver during the Boolean Constraint Propagation (BCP) operation. Our strategy improves BMC by 1.74x against the case where all extended implications were added to the BMC instance. Compared with the original BMC without any implications, up to 55.32x speedup can be achieved.

Previously used ICs, which are resold as new, result in undue lost revenue, cause lower performance, reduced life span, and even catastrophic failure of platforms and systems. Non-invasive and inexpensive techniques are needed to establish the authenticity of such ICs that do not have special in-built structures for counterfeit detection. Although delay of circuit increases with its age, it cannot directly reveal the age of the chip, as it is also greatly influenced by process variation. In this work, we show that the relationship between two or more paths within the chip is a great indicator of its age. Using the proposed statistical and circuit-level technique, we observe over 97% correct detection of an aged IC from a new IC.

The effectiveness of SAT-based Bounded Model Checking (BMC) critically relies on the deductive power of the BMC instance. Although implication relationships have been used to help SAT solver to make more deductions, frequently an excessive number of implications has been used. Too many such implications can result in a large number of clauses that could potentially degrade the underlying SAT solver performance. In this paper, we first propose a framework for a parallel deduction engine to reduce implication learning time. Secondly, we propose a novel set-cover technique for optimal selection of constraint clauses. This technique depends on maximizing the number of literals that can be deduced by the SAT solver during the BCP (Boolean Constraint Propagation) operation. Our parallel deduction engine can achieve a 5.7× speedup on a 36-core machine. In addition, by selecting only those critical implications, our strategy improves BMC by another 1.74× against the case where all extended implications were added to the BMC instance. Compared with the original BMC without any implication clauses, up to 55.32× speedup can be achieved.

In this paper, we propose an implication graph based sequential logic simulator for debugging scan pattern failures encountered during First Silicon. A novel Debug Implication Graph (DIG) is constructed during logic simulation of the failing scan pattern. An efficient node traversal mechanism across time frames, in the DIG, is used to perform the root-cause analysis for the failing scan-cells. We have developed an Interactive Pattern Debug environment (IDE), viz. scan pattern debugger, around the logic simulator to systematically analyze and root-cause the failures. We integrated the proposed technique into the scan ATPG flow for industrial microprocessor designs. We were able to resolve the First Silicon logical pattern failures within hours, which would have otherwise taken a few days of manual effort.

In this paper, we present RAG, an efficient Reliability Analysis tool based on Graphics processing units (GPU). RAG is a fault injection based parallel stochastic simulator implemented on a state-of-the-art GPU. A two-stage simulation framework is proposed to exploit the high computation efficiency of GPUs. Experimental results demonstrate the accuracy and performance of RAG. An average speedup of 412× and 198× is achieved compared to two state-of-the-art CPU-based approaches for reliability analysis.

In this paper, we present BEACON, a Branch-oriented Evolutionary Ant Colony OptimizatioN method which is a bio-inspired meta-heuristic for design validation and functional test generation. BEACON combines an evolutionary search technique with Ant Colony Optimization (ACO) for improved search capability. BEACON first cross-compiles the Verilog circuit source to a C++ base for fast simulation. Then, it profiles the code, keeping track of each branch and the number of times it has been visited in a database. Branch coverage provides a very useful metric for exploring the design, especially visiting the most critical states, including corner states, in the design. At 100% branch coverage, we can conclude that every control state described in the RTL has been visited. Thus, during execution, BEACON trims highly visited branches from the search and focuses the search on rarely occurring branches and paths. This approach gives a significant performance boost while maintaining a high level of coverage. Experimental results show that BEACON is able to achieve very high branch coverages with a fraction of computational cost. In addition, previous hard-to-reach corner states in the ITC99 benchmarks have now been reached by BEACON. New states can also be discovered from the RTL descriptions. For many circuits, one to two orders of magnitude speedups over existing methods have been achieved.

A diagnostic test pattern generator using a Satisfiability Modulo Theory (SMT) solver is proposed. Rather than targeting a single fault pair at a time, the proposed SMT approach can distinguish multiple fault pairs in a single instance. Several heuristics are proposed to constrain the SMT formula to further reduce the search space, including fault selection, excitation constraint, reduced primary output vector, and cone-of-influence reduction. Experimental results for the ISCAS85 and full-scan versions of ISCAS89 benchmark circuits show that fewer diagnostic vectors are generated compared with conventional diagnostic test generation methods. Up to 73% reduction in the number of vectors generated can be achieved in large circuits.

This article presents a hybrid Automatic Test Pattern Generation (ATPG) technique using the staggered Launch-On-Shift (LOS) scheme followed by the one-hot launch-on-shift scheme for testing delay faults in a scan design containing asynchronous clock domains. Typically, the staggered scheme produces small test sets but needs long ATPG runtime, whereas the one-hot scheme takes short ATPG runtime but yields large test sets. The proposed hybrid technique is intended to reduce test pattern count with acceptable ATPG runtime for multimillion-gate scan designs. In case the scan design contains multiple synchronous clock domains, and each group of synchronous clock domains is treated as a clock group and tested using a launch-aligned or a capture-aligned LOS scheme. By combining these schemes together, we found the pattern counts for two large industrial designs were reduced by approximately 1.6X to 1.8X, while the ATPG runtime was increased by 40% to 50%, when compared to the one-hot clocking scheme alone.

We present a new 2-phase symbolic execution driven strategy that achieves high branch coverage in software quickly. Phase 1 follows a greedy approach that quickly covers as many branches as possible by exploring each branch through its corresponding shortest path prefix. Phase 2 covers the remaining branches that are left uncovered if the shortest path to the branch was infeasible. In Phase 1, a basic conflict-driven learning is used to skip all the paths that may have any of the earlier encountered conflicting conditions, while in Phase 2, a more intelligent conflict-driven learning is used to skip regions that do not have a feasible path to any unexplored branch. This results in considerable reduction in unnecessary SMT solver calls. Experimental results show that significant speedup can be achieved, effectively reducing the time to detect a bug and providing higher branch coverage for a fixed time-out period than previous techniques.

While scan-based testing achieves a high fault coverage, it requires long test application times and substantial tester memory, in addition to the overhead in chip area and high test power. Functional testing, on the other hand, suffers from low coverage but can be applied at-speed. In this paper, we propose a novel three-step design-for-test (DFT) methodology which enhances the performance of functional testing to a great extent. In the first step we expand the state space of the circuit beyond functionally reachable space without scan or reset. These new states create conditions to activate/propagate fault effects that are otherwise hard-to-detect. Since structural correlation between D flip-flops (DFFs) of a circuit restricts its state space variation, the second step consists of partitioning the DFFs into different groups that helps to break such correlations. In the third step, we make internal hard-to-observe points in the circuit more observable by directly XORing them with selected primary outputs. This method can be applied at-speed (since no scan shifting is involved) saving significant amount of test application time, with comparable area overhead as scan-based DFT. Our experiments on large ISCAS'89 and ITC'99 benchmarks show that we are able to achieve very high non-scan fault coverages while simultaneously reducing the test application time (114×) as compared to scan based techniques.

In this paper, we present an efficient diagnostic fault simulator based on a state-of-the-art graphics processing unit (GPU). Diagnostic fault simulation plays an important role to identify and locate the causes of circuit failures. However, today's complex VLSI circuits pose ever higher computational demand for such simulators. Our GPU based diagnostic fault simulator (GDSim) is based on a novel two-stage simulation framework which exploits high computation efficiency on the GPU. The fault pair based simulation is proposed to overcome the limited capacity of GPU memory as well as achieve a substantial fine-grained parallelism. Multi-fault-signature and dynamic load balancing techniques are introduced for the best usage of computing resources on-board. Experimental results demonstrate a speedup of up to 121× (with average speedup of 38.43×) compared to a state-of-the-art CPU-based diagnostic fault simulator.

Fingerprints continue to serve as a reliable trait for human identification. Feature-based matching techniques, such as those used by Automated Fingerprint Identification Systems (AFIS), have demonstrated remarkable success in minutiae-based matching from good quality prints with relatively large extent. As the image quality degrades and acquired fingerprint area decreases, however, the number of reliable minutiae that can be automatically detected decreases, causing match performance to suffer. This paper presents a novel approach to improving the precision of features that can be extracted from fingerprint images. This is accomplished through improved minutia localization and quality assessment routines that are inspired in part by human visual perception. Initial results have shown an improvement in minutia accuracy for 88.2% of fingerprint minutia sets after applying the proposed localization method. An increase in average quality of true minutiae was found for 98.6% of the fingerprint images when using the proposed quality assessment. The results were obtained using a database of 516 fingerprints with ground truth minutiae.

General purpose computing on graphical processing units (GPGPU) is a paradigm shift in computing that promises a dramatic increase in performance. GPGPU also brings an unprecedented level of complexity in algorithmic design and software development. In this paper, we present an efficient parallel fault simulator, FSimGP2, that exploits the high degree of parallelism supported by a state-of-the-art graphic processing unit (GPU) with the NVIDIA compute unified device architecture. A novel 3-D parallel fault simulation technique is proposed to achieve extremely high computation efficiency on the GPU. Global communication is minimized by concentrating as much work as possible on the local device's memory. We present results on a GPU platform from NVIDIA (a GeForce GTX 285 graphics card) that demonstrate a speedup of up to 63× and 4× compared to two other GPU-based fault simulators and up to 95× over a state-of-the-art algorithm on conventional processor architectures.

This paper presents a hybrid automatic test pattern generation (ATPG) technique using the staggered launch-on capture (LOC) scheme followed by the one-hot LOC scheme for testing delay faults in a scan design containing asynchronous clock domains. Typically, the staggered scheme produces small test sets but needs long ATPG runtime, whereas the one-hot scheme takes short ATPG runtime but yields large test sets. The proposed hybrid technique is intended to reduce test pattern count with acceptable ATPG runtime for multi-million-gate scan designs. In case the scan design contains multiple synchronous clock domains, each group of synchronous clock domains is treated as a clock group and tested using a launch aligned or a capture aligned LOC scheme. By combining these schemes together, we found the pattern counts for two large industrial designs were reduced by approximately 1.1X to 2.1X, while the ATPG runtime was increased by 10% to 50%, when compared to the one-hot clocking scheme alone.

We propose a novel technique to mine powerful and generalized boolean relations among flip-flops in a sequential circuit for sequential equivalence checking. In contrast to traditional learning methods, our mining algorithm can detect inductive invariants as well as illegal state cubes. These invariants can be arbitrary boolean expressions and can thus prune a large don’t care space during equivalence checking. Experimental results demonstrate that these general invariants can be very effective for sequential equivalence checking of circuits with no or very few equivalent signals between them, with low computational costs.

Symbolic techniques have been shown to be very effective in path-based test generation, however, they fail to scale to large programs due to the exponential number of paths to be explored. In this paper, we focus on tackling this path explosion problem and propose search strategies to achieve quick branch coverage under symbolic execution, while exploring only a fraction of paths in the program. We present a reach ability-guided strategy that makes use of the reach ability graph of the program to explore unvisited portions of the program and a conflict-driven backtracking strategy that utilizes conflict analysis to perform nonchronological backtracking. We present experimental evidence that these strategies can significantly reduce the search space and improve the speed of test generation for programs.

General Purpose computing on Graphical Processing Units (GPGPU) is a paradigm shift in computing that promises a dramatic increase in performance. But GPGPU also brings an unprecedented level of complexity in algorithmic design and software development. In this paper, we present an efficient parallel fault simulator, FSimGP2, that exploits the high degree of parallelism supported by a state-of-the-art graphic processing unit (GPU) with the NVIDIA Compute Unified Device Architecture (CUDA). A novel three-dimensional parallel fault simulation technique is proposed to achieve extremely high computation efficiency on the GPU. The experimental results demonstrate a speedup of up to 42× compared to another GPU-based fault simulator and up to 53× over a state-of-the-art algorithm on conventional processor architectures.

While conventional test point insertions commonly used in design for testability can improve fault coverage, the test points selected may not necessarily be the best candidates to aid silicon diagnosis. In this paper, test point insertions are conducted with the aim to detect more faults and also synergistically distinguish currently indistinguishable fault-pairs. We achieve this by identifying those points in the circuit, which are not only hard-to-test but also lie on distinguishable frontiers, as Testability-Diagnosability (TD) points. To this end, we propose a novel low-cost metric to identify such TD points. Further, we propose a new DFT + DFD architecture, which adds just one pin (to identify test/functional mode) and small additional combinational logic to the circuit under test. Our experiments indicate that the proposed architecture can distinguish 4× more previously indistinguishable fault-pairs than existing DFT architectures while maintaining similar fault coverages. Further, experiments illustrate that quality results can be achieved with an area overhead of around 5%.

We propose a novel synthesis technique for reversible logic based on ant colony optimization (ACO). In our ACO-based approach, reversible logic synthesis is formulated as a best-path search problem, where artificial ants, starting from their nest (reversible function output), attempt to find the best path to the food source (reversible function input). The experimental results have demonstrated superior performance in terms of both synthesis quality and computation time. They also show that the proposed method is scalable in handling large reversible functions.

Scan-based DFT is the de-facto industrial practice for testing integrated circuits (ICs). Variations in the scan architecture to improve test metrics have been the primary focus in recent years. In this paper, we propose a new nonscan DFT in which a subset of the circuit flip-flops are made directly loadable from the primary inputs and another subset of flip-flops are made observable at the output via a state compactor. In this architecture, multiple flip-flops may share the same primary input in the loading mode. A load-enable pin is added to distinguish the direct-loading mode from the functional mode. With a modest area overhead, this architecture offers several attractive features, including (1) at-speed testing, which eliminates the need for scan-shifting and would thus capture delay-related defects, (2) low test data volume and test application time, as we no longer need to store all the scan and response data, (3) high coverages, since the low-testability flipflops are made to be loadable and/or observable, and (4) low test power. Experimental results on large ISCAS'89 circuits validate the aforementioned metrics with 10× to 100× reduction in test application time with respect to Illinois Scan.

An effective silicon debug technique uses a trace buffer to monitor and capture a portion of the circuit response during its functional, post-silicon operation. Due to the limited space of the available trace buffer, selection of the critical trace signals plays an important role in both minimizing the number of signals traced and maximizing the observability/restorability of other untraced signals during post-silicon validation. This paper presents a new method for trace buffer signal selection for the purpose of post-silicon debug. The selection is performed by favoring those signals with the most number of implications that are not implied by other signals. Then, based on the values of the traced signals during silicon debug, we introduce an algorithm which uses a SAT-based multi-node implication engine to restore the values of untraced signals across multiple time-frames. Experimental results for sequential benchmark circuits showed that the proposed approach selects the trace signals effectively, giving a high restoration percentage compared with other techniques.

Bit-precise verification with variables modeled as bitvectors has recently drawn much interest. However, a huge search space usually results after bit-blasting. To accelerate the verification of bit-vector formulae, we propose an efficient algorithm to discover non-uniform encoding widths. Weof variables in the verification model, which may be smaller than their original modeling widths but sufficient to find a counterexample. Different from existing approaches, our algorithm is path-oriented, in that it takes advantage of the controllability and observability values in the structure of the model to guide the computation of the paths, their encoding widths and the effective adjustment of these widths in subsequent steps. For path selection, a subset of single-bit path-controlling variables is set to constant values. This can restrict the search from those paths deemed less favorable or have been checked in previous steps, thus simplifying the problem. Experiments show that our algorithm can significantly speed up the search by focusing first on those promising, easy paths for verifying those path-intensive models, with reduced, non-uniform bitwidth encoding.

High test data volume and long test application time are two major concerns for testing scan based circuits. The Illinois Scan (ILS) architecture has been shown to be effective in addressing both these issues. The ILS achieves a high degree of data compression thereby reducing both test data volume and test application time. However, the fault coverage achieved in the Broadcast Mode of the ILS architecture depends on the actual configuration of individual scan chains, i.e., the number of chains and the mapping of the individual flip-flops of the circuit to the respective scan chain positions. Current methods for constructing scan chains in the ILS are either ad-hoc or rely on test pattern information from an apriori ATPG run. In this paper, we present a novel low cost technique to construct ILS scan configuration for a given design. It efficiently utilizes the circuit topology and tries to optimize the flip-flop assignment to a scan chain location without compromising the fault coverage in the Broadcast Mode. Thus, it eliminates the need of an apriori ATPG run or any test set information. Experimental results on the ISCAS'89 benchmark circuits show that the proposed ILS configuration method can achieve on an average 5% more fault coverage in the Broadcast Mode and an average 15% more reduction in total test data volume and test application time than the existing methods.

In this paper, a novel heuristic for abstraction-guided state justification is proposed based on ant colony optimization (ACO). A probabilistic state transition model is developed to help formulate the state justification problem as a searching scheme of artificial ants. The amount of pheromone left by the ants is directly proportional to the quality of the search so that it can serve as an effective guidance for the search. In addition, the intelligence based on the collective behavior is capable of avoiding critical dead-end states as well as fast convergence to the target state. Experimental results demonstrated that our approach is superior in reaching hard-to-reach states in sequential circuit compared to other methods.

More than a dozen Wireless @ Virginia Tech faculty are working to address the broad research agenda of cognitive radio and cognitive networks. Our core research team spans the protocol stack from radio and reconfigurable hardware to communications theory to the networking layer. Our work includes new analysis methods and the development of new software architectures and applications, in addition to work on the core concepts and architectures underlying cognitive radios and cognitive networks. This paper describes these contributions and points towards critical future work that remains to fulfill the promise of cognitive radio. We briefly describe the history of work on cognitive radios and networks at Virginia Tech and then discuss our contributions to the core cognitive processing underlying these systems, focusing on our cognitive engine. We also describe developments that support the cognitive engine and advances in radio technology that provide the flexibility desired in a cognitive radio node. We consider securing and verifying cognitive systems and examine the challenges of expanding the cognitive paradigm up the protocol stack to optimize end-to-end network performance. Lastly, we consider the analysis of cognitive systems using game theory and the application of cognitive techniques to problems in dynamic spectrum sharing and control of multiple-input multiple-output radios.

With the advance of SAT solvers, transforming a software program to a prepositional formula has generated much interest for bounded model checking of software in recent years. However, reasoning at the Boolean level often may not be able to identify some key relations among the original high-level program variables. In this paper, we propose a novel framework that uses simulation-directed data mining in the original program to extract a set of high-level potential property invariants according to the dynamic execution data of the software. When these learned invariants are added as constraints to the bounded model checking instances of the software, they help to significantly reduce the search space. The simulation-directed invariant mining framework exhibits more flexibility compared to the conventional static program analysis approaches, and the experimental results showed that our approach can lead to up to an order of magnitude of speedup in software verification via bounded model checking.

In this paper, we propose a novel approximation algorithm (RelaxSAT) for MIN-ONE SAT. RelaxSAT generates a set of constraints from the objective function to guide the search. The constraints are gradually relaxed to eliminate the conflicts with the original Boolean SAT formula until a solution is found. The experiments demonstrate that RelaxSAT is able to handle very large instances which cannot be solved by existing MIN-ONE algorithms; furthermore, very tight bounds on the solution were obtained with one to two orders of magnitude speedup.

We introduce a new semiformal design validation framework to justify hard-to-reach corner-case states. We propose a cultural learning technique to identify the swarming of domain knowledge during the search. In addition, our guidance strategy abstracts sets of partitioned state variables, from which pre-images are computed to capture the expanded portions of the state spaces related to a target state. Experimental results show that our approach is very effective to reach hard- to-reach states than existing methods.

Testing the genuineness of a manufactured chip is an important step in an IC product life cycle. This becomes more prominent with the outsourcing of the manufacturing process, since the manufacturer may tamper the internal circuit behavior using Trojan circuits in the original design. Traditional testing methods cannot detect these stealthy Trojans because the triggering scenario, which activates it, is unknown. Recently, approaches based on side-channel analysis have shown promising results in detecting Trojans. In this paper, we propose a novel test generation technique that aims at magnifying the disparity between side-channel signal waveforms of tampered and genuine circuits to indicate the possibility of internal tampering. Experimental results indicate that our approach could magnify the likelihood of Trojans 4 to 20 times more than existing side-channel analysis based approaches.

Novel nano-scale devices have shown promising potential to overcome physical barriers faced by complementary metal-oxide semiconductor (CMOS) technology in future circuit design. However, many nanotechnologies are intrinsically suitable for implementing threshold logic rather than Boolean logic which has dominated CMOS technology in the past. To fully take advantage of such emerging nanotechnologies, efficient design automation tools for threshold logic therefore become essential. In this work, we propose novel techniques of formulating a given threshold logic in conjunctive normal form (CNF) that facilitates efficient SAT-based equivalence checking. Three different strategies of CNF generation from threshold logic representations are implemented. Experimental results based on MCNC benchmarks are presented as a complete comparison. Our hybrid algorithm, which takes into account input symmetry as well as input weight order of threshold gates, can efficiently generate CNF formulas in terms of both SAT solving time and CNF generating time.

The increasing complexity and size of software designs has made scalability a major bottleneck in software verification. Program abstraction has shown potential in alleviating this problem through selective search space reduction. In this paper, we propose an Ant Colony Optimization (ACO)-directed program structure construction to formulate a novel under-approximation based program abstraction (UAPA). By taking advantage of the resulting abstraction, a new software bounded model checking framework is built with the aim of improving the performance of property checking, especially for property falsification. Experimental results on various programs showed that the proposed ACO-directed program abstraction can dramatically improve the performance of software bounded model checking with significant speedups.

Adaptive micro-architectures aim to achieve greater energy efficiency by dynamically allocating computing resources to match the workload performance. The decisions of when to adapt (temporal dimension) and what to adapt (spatial dimension) are taken by a control algorithm based on an analysis of the power/performance tradeoffs in both dimensions. We perform a rigorous analysis to quantify the energy efficiency limits of fine-grained temporal and coordinated spatial adaptation of multiple architectural resources by casting the control algorithm as a constrained optimization problem. Our study indicates that coordinated adaptation can potentially improve energy efficiency by up to 60% as compared to static architectures and by up to 33% over algorithms that adapt resources in isolation. We also analyze synergistic application of coarse and fine grained adaptation and find modest improvements of up to 18% over optimized dynamic voltage/frequency scaling. Finally, we analyze several previous control algorithms to understand the underlying reasons for their inefficiency.

We present a new approach to intelligently mine three types of invariants from a sequential circuit to significantly improve SAT-based state justification. We adaptively generate mining databases targeting on the hard-to-reach corner-case states, from which global invariants, target state related invariants, and observability-don't-care extended invariants are mined. Each mined invariant involves two or more signals that span across multiple time-frames, which capture the knowledge of the state spaces related to a target state. These invariants are then checked for their validity, and they can significantly increase the deductive power of the instance by pruning a larger portion of the search space. Experimental results show that more than an order of magnitude performance improvement can be obtained when justifying hard-to-justify states.

We present a novel technique on mining relationships in a sequential circuit to discover global constraints. We utilize domain knowledge to prune the search space for our mining process, via which the mined relations may often span several time frames, thus improving the deductibility of the problem instance. Experimental results demonstrate that the application of these global constraints to satisfiability (SAT)-based bounded sequential equivalence checking can achieve a one to two orders-of-magnitude speedup.

No abstract available.

Using DFT methods such as scan can improve testability and increase fault coverage. However, scan tests may scan in illegal or unreachable states during test application, which may result in incidental detection of functional untestable delay faults during the scan test. This paper presents novel mining techniques for fast top-down functional constraint extraction. The extracted functional constraints capture illegal states through internal signal relations. Imposing these relations as functional constraints to a commercial ATPG tool allows for the generation of effective pseudo-functional tests. We analyze its impact on minimizing the over-testing problem of the scan- based circuits. The experimental results on transition faults and path delay faults reveal that the proposed method produces a small fraction, yet extremely powerful functional constraints effective for constraining the state space.

We present a new verification approach that applies aggressive program slicing and a proof-based abstraction-refinement strategy to enhance the scalability of bounded model checking of embedded software. While many software model-checking tools use program slicing as a separate or optional step, our program slicing is integrated in the model construction and reduction process. And it is combined with the compilation optimization techniques so to compute a more accurate slice. We also explore a proof-based abstraction-refinement strategy using the under/overapproximation on our proposed software model, and propose a heuristic method of deciding new encoding size to refine the under-approximation. Experiments on C programs from wireless cognitive radio systems show this approach can greatly reduce the model size and shorten the solving time by the SAT-solver.

In today's deep sub-micron designs, large amounts of switching activity may cause a substantial voltage drop on the power rails, also called power droop. Faults that may result from a power droop include delay faults caused by the increased propagation delays from the reduced supply voltage. In order to assess the performance of a manufactured chip, its worst-case droop condition should be tested by applying a specific input pattern which can cause maximum switching activity. On the contrary, during delay fault diagnosis, it would be beneficial for the diagnostic patterns to induce less switching activity in order to filter the embedded noise. In this paper, we propose a new SAT formulation that incorporates depth-limited search to compute the test patterns for these power droop faults. Experimental results demonstrate the efficiency of the proposed approach for generating test patterns for both transition and path-delay faults that also produce maximal (or minimal) power. Up to three orders of magnitude speed-up can be achieved using our approach.

This work introduces a new guidance strategy to justify hard-to-reach target states in sequential circuits, which also applies to reaching corner-case states in design validation. We propose data-mining methods to extract several partition sets of state variables directly from the gate-level netlist of the design, such that they enable the search to reach the target state. The partition sets are used to compute Partitioned Navigation Tracks (PNTs). PNTs capture the behavior of expanded portions of the state space as they relate to a target state of interest, thus providing a more accurate distance metric than traditional abstract guideposts. Moreover, the computation and storage costs of the PNTs are small, making our approach scalable to large circuits. With the proposed PNTs, we also need not refine the abstract models. Experiments showed that we are able to reach many more hard-to-reach states compared to state-of-the-art methods.

In this paper, we identify two main bottlenecks in the functional diagnosis flow and propose new ways to overcome these. Our approach completely eliminates the "primary input (PI) pattern generation and simulation" step and instead employs scan-dump values extracted from the tester. We utilize backward and forward logic implications of the scan-dump values to reconstruct more logic values for the circuit signals. Furthermore, we employ the reset state for the non-scan latches of the design to increase the number of specified signals in the overall circuit. Experimental results on stuck-at faults on industrial designs show that, in most cases, these reconstructed values are sufficient to correctly diagnose a fault, thereby avoiding hours of conventional functional diagnosis runtimes.

We present a novel scan architecture for simultaneously reducing test application time and test power (both average and peak power). Unlike previous works where the scan chain is partitioned only based on the excitation properties of the flip-flops (FFs), our work considers both the excitation and propagation properties of the scan FFs. In the proposed scan architecture, the scan chain is partitioned to maximize the overlapping between the excitation and propagation on different fault sets. The scan architecture also allows the entire set of detectable faults in the circuit under test (CUT) to be detected with only a portion of the scan elements active at a time, and thereby completely eliminates the need for the "serial full-scan" mode which is inefficient for both the test time and test power. Experimental results show that by introducing minimal hardware overhead, and without sacrificing fault coverage, an average peak power reduction of 22.8%, average power reduction of 41.6%, and an average reduction of 18.5% on the test application time can be achieved, compared with the ordinary full-scan architecture

In this paper, we propose a novel framework to quickly extract illegal states of a sequential circuit and then use them as constraints during the SAT-based induction runs. First, we employ a low-cost combinational ATPG to identify unreachable partial-states among groups of related flip-flops. Second, we propose the concept of necessary-assignment looping to identify additional unachievable partial-states. Third, we extend the above unachievability theory to capture new non-trivial sequential logic dependencies among the circuit signals. Finally, we use a unified framework that utilizes all the above information and aims at maximizing the learning. All the learned illegal states are converted into constraint clauses and are replicated at all the unrolled transition relations to prune the searchspace. Experimental results show that, due to the added constraints, many safety properties can be proved at earlier depths and the induction run-times can be significantly reduced.

In this paper, we propose a novel technique on mining relationships in a sequential circuit to discover global constraints. In contrast to the traditional learning methods, our mining algorithm can find important relationships among several nodes efficiently. The nodes involved may often span several time-frames, thus improving the deductibility of the problem instance. Experimental results demonstrate that the application of these global constraints to SAT-based bounded sequential equivalence checking can achieve one to two orders of magnitude speedup. In addition, because it is orthogonal to the underlying SAT solver, it can help to enhance the efficacy of typical SAT based verification flows.

In this paper, we introduce a novel preimage computation technique that directly computes the circuit cofactors without an explicit search for any satisfiable solution. We use an implicit search on the primary inputs of a sequential circuit to compute all the circuit cofactors for the target preimage. In order to alleviate the computational cost, aggressive learning techniques are introduced that reason on the search-states by analyzing the relations among circuit cofactors. Such analysis generates search-state induced clauses that directly help to prune the cofactor space during preimage computation and to perform non-chronological backtracking. Experimental results show that a significant improvement can be achieved in both performance and capacity as compared to the existing techniques.

This paper introduces a new cooperative traversal on the partitioned finite-state-machine (FSM) space to generate test stimuli for both sequential test generation and design validation. The new features for this logic-simulation-based automatic test pattern generation (ATPG) include: (1) cooperative search that exploits orthogonality is performed on two global state partition sets; (2) feedback information is dynamically extracted from characteristic states (each characteristic state examines a subset of corner cases of the design) to prune away redundant search spaces; (3) different from dynamic partitioning, interactions between two global partition sets are emphasized in the proposed approach. The proposed cooperative search is similar to a cooperative two-player game, where each partition set presents the state space for a player. Experimental results show that test vectors generated by such a cooperative search can yield both higher coverage and up to 5 times reduction on test generation time

This paper presents a study of the implication based functional constraint extraction techniques to generate pseudo functional scan tests. Novel algorithms to extract pair-wise and multi-node constraints as Boolean expressions on arbitrary gates in the design are presented. Its impact on reducing the overkill in testing was analyzed, and report the trade-offs in coverage and scan-loads for a number of fault models. In the case of path-delay fault model, it was shown that the longest paths contribute most to the over-testing problem, raising the question about scan testing of the longest paths. Finally, the evaluation of the functional constraints on large industrial circuits show that the proposed constraint generation algorithm generate a powerful set of constraints most of which are not captured in the constraints extracted by designers for design-verification purposes

Fault collapsing of a fault-set helps in obtaining smaller test-sets as well as in reducing fault-simulation times. In this paper, we propose two new theorems by making use of the generalized dominance relations exhibited by a pair of faults. In order to learn several unique requirements for the faults in a low-cost manner, we employ a fault-independent analysis and propose heuristics to reduce the number of fault-pair comparisons required. Experimental results on ISCAS85, 89 & 93 benchmarks show that significantly more faults can be collapsed as compared to the existing methods, with smaller run-times in many cases. For most circuits, collapsing to less than 30% of the total number of faults is achieved

We present a new BIST (built-in-self-test) architecture for system-on-a-chip (SOC), which can test a cluster of embedded sequential cores simultaneously. The compressed spectrum for a cluster of cores under test is computed by performing spectral analysis individually on all cores. Because there is no need to combine the cores to extract the spectrum for the entire cluster, the computation complexity is greatly reduced. For each individual core, we propose an interleaved state relaxation on the compacted test sequence for its characteristic fault set, leading to a partially specified, interleaved sequence which can be merged in a much easier way. A delay network and a switching network are added selectively to allow for more aggressive merging of spectra. Experimental results show that the same level of fault coverage can be achieved for each individual core with negligible hardware overhead, while the test application time for testing the entire cluster can be reduced by up to four times and the test data storage requirement is reduced by up to 42 percent.

We present a new logic-simulation-based algorithm on verifying safety properties of large sequential hardware designs. This algorithm explores the search space defined by partitioned internal circuit nodes. Two powerful features are proposed to increase the effectiveness during search space exploration and counterexample generation for verifying safety properties. These include 1) new search space constituted by internal nodes instead of state variables and 2) static learning on multiple nodes to further enlarge the target. These two features are integrated with the following techniques during our simulation: incorporation of a BCP (Boolean constraint propagation) engine for multiple nodes implication and multiple-time-frame GA (genetic algorithm) search. Because only logic simulation is needed in our algorithm, the computational effort is low. Experimental results on large benchmark circuits have shown that this logic-simulation-based verifier achieves significantly better results compared with existing formal verification tools and simulation-based methods

This paper presents two low-cost fault-independent techniques that can be used to identify significantly more untestable faults than could be identified by earlier fault-independent techniques. A new theorem and an efficient implementation of the theorem for the purpose of identifying sequentially untestable faults are presented first. Unlike the single-fault theorem where the stuck-at fault is injected exclusively in the last time frame of the k-frame unrolled circuit, this theorem enables a fault injection in any time frame within the unrolled sequential circuit. To efficiently apply the authors' concept to untestable fault identification, sequential implications are used to extend the unobservability propagation of gates to multiple time frames during single-line conflict analysis. Then, a new technique called "maximizing local impossibilities" is proposed. This technique efficiently identifies multiple-node conflicting assignments by analyzing logical relationships local to Boolean gates in the circuit. Using this new concept in conjunction with a powerful implication engine enables identification of many more untestable faults that were missed by the single-line conflict-based approach. Since this approach concentrates on identifying conflicting combinations locally around each Boolean gate in the circuit, its complexity is linear in the size of the circuit. The application of these two proposed techniques to the International Symposium on Circuits and Systems (ISCAS) 1985 and ISCAS 1989 Sequential Benchmark Circuits showed a significant increase in the number of faults identified as untestable, at practically no overhead in both the memory and the execution time

This paper presents a new algorithm to extract characteristic flip-flops, which form a characteristic state set, using state-correlation information. The extracted characteristic state set allows us to focus on a significantly smaller set of flip-flops while ignoring other flip-flops, thereby simplifying the target problem and reducing state explosion in very large sequential circuits. Next, partitioning is applied only on the characteristic state variables, and partial state transition graphs (STGs) are built. During test generation, no specific fault or design error is targeted; instead, test vectors are generated using a twofold criteria: 1) whether the vector will expand the overall STGs and 2) whether this vector will break the relationship among flip-flops within the correlated sets. While generating vectors, state and transition exploration histories for each state group are maintained by dynamically constructing partial STGs for all state groups. By limiting a maximum size any state group can be, maintaining the complete state and transition exploration histories for each state group is feasible even for very large sequential circuits. Experiments showed that our extraction algorithm can reduce the original complete state set by up to 97%. In addition, with the reduced state variables, it achieves not only equal or better coverages for both stuck-at faults and design errors, the execution time is also significantly reduced due to the much fewer flip-flops that this paper needs to consider. For some large sequential circuits, highest coverages have been obtained

This paper presents a framework for high-level design validation using an efficient register-transfer level (RTL) automatic test pattern generator (ATPG). The RTL ATPG algorithm first generates a test environment for each validation objective, which includes variable assignments, conditional statements, and arithmetic expressions in the hardware description language (HDL) description. The test environment for a given validation objective is a set of symbolic conditions that allow for full controllability and observability of that objective. After the RTL ATPG terminates, a back-end translator intelligently translates the test environments into validation vectors by filling in the necessary values. Since the observability of error effect is naturally handled by the RTL ATPG algorithm, this approach is superior to most existing validation methods, which only focus on the excitation of HDL constructs. A set of heuristics is proposed to utilize high-level circuit information to enhance the RTL ATPG algorithm and to maximize the validation efficiency. The RTL ATPG algorithm is also coupled with an improved RTL validation-coverage metric, which can help users to gain a higher degree of confidence on the quality of generated validation vectors. The usage of the coverage metric also results in the generation of compact vector sets. Experimental results on academic and industrial benchmark circuits demonstrate that our method is able to obtain very high design-error coverage in short execution times.

The need for high-performance pipelined architectures has resulted in the adoption of latch based designs with multiple, interacting clocks. For such designs, time sharing across latches results in signals which propagate across multiple clock cycles along paths with multiple latches. These paths need to be tested for delay failures to ensure reliability of performance. However, many of these multi-cycle paths can be untestable and significant computational effort is wasted in targeting such paths during test generation and fault grading. To save this computational effort, a-priori identification of untestable multicycle paths is desired. We address this issue in our paper through a novel and unique framework: unlike traditional techniques, which focus only on single-cycle path delay faults (for flip-flop based designs with single clock), our framework efficiently identifies untestable multi-cycle path delay faults (Mpdfs) in latch-based designs with multiple clocks. We use a novel graphical representation and sequential implications to identify non-robustly untestable M-pdfs through a three-step methodology. Results for industrial designs demonstrate the effectiveness and scalability of our framework.

We propose a new dynamic method of abstraction, which can be applied during successive steps of the model checking algorithm to further reduce the model produced by traditional static abstraction methods. This is facilitated by information gathered from an analysis of the proof of unsatisfiability of SAT-based bounded model checking problems formulated on the original design. The dynamic abstraction effectively allows the model checker to work with smaller abstract models. Experiments on several industrial benchmarks demonstrate that dynamic abstraction can significantly improve both the performance and the capacity of typical abstraction refinement flows.

In recent years, several electronic design automation (EDA) problems in testing and verification have been formulated as Boolean satisfiability (SAT) instances due to the development of efficient general-purpose SAT solvers. Problem-specific learning techniques and heuristics can be integrated into the SAT solver to further speed-up the search for a satisfying assignment. In this paper, we target the problem of generating a complete test-suite for the path delay fault (PDF) model. We provide an incremental satisfiability framework that learns from (1) static logic implications, (2) segment-specific clauses, and (3) unsatisfiability cores of each untestable partial PDF. These learning techniques improvise the test generation for path delay faults that have common testable and/or untestable segments. The experimental results show that a significant portion of PDFs can be excluded dynamically in the proposed incremental SAT formulation for large benchmark circuits, thus potentially achieving speed-ups for PDF test generation.

We present a novel, quality-driven, architectural-level approach that trades-off the output quality to enable power-aware processing of multimedia streams. The error tolerance of multimedia data is exploited to selectively eliminate computation while maintaining a specified output quality. We construct relaxed, synthesized power macro-models for power-hungry units to predict the cycle-accurate power consumption of the input stream on the fly. The macro-models, together with an effective quality model, are integrated into a programmable architecture that allows both power savings and quality to be dynamically tuned with the available battery-life. In a case study, power monitors are integrated with functional units of the IDCT module of a MPEG-2 decoder. Experiments indicate that, for a moderate power monitor energy overhead of 5%, power savings of 72% in the functional units can be achieved resulting in an increase in battery life by 1.95 x.

Image computation is a fundamental step in formal verification of sequential systems, including sequential equivalence checking and symbolic model checking. Since conventional Reduced Ordered Binary Decision Diagram (ROBDD) based methods can potentially suffer from memory explosion, there has been a growing interest in using Automatic Test Pattern Generation (ATPG) / Boolean Satisfiability (SAT) based techniques in recent years. While ATPG has been successful for computing pre-image, image computation presents a very different set of problems. In this paper, we present a novel backtracing-based ATPG technique for forward image computation. We carefully alter the ATPG engine to compute the image cubes and store them incrementally in a Zero-Suppressed Binary Decision Diagram (ZBDD). In order to improve the efficiency of image computation, we propose three heuristics: (i) gate-observability based decision selection heuristics to accelerate ATPG, (ii) search-state based learning techniques supported with a proof for correctness, and (iii) on-the-fly state-set minimization techniques to reduce the size of computed image set. Experimental results on ISCAS '89 and ITC '99 benchmark circuits show that we can achieve orders of magnitude improvement over OBDD-based and SAT-based techniques.

An effective and efficient ATPG-based combinational equivalence checker.

In this paper, we propose novel low-cost methods that combine static logic implications and binary resolution to significantly increase the number of non-trivial signal relations learned from the circuit. The proposed method first applies resolution techniques to learn new static single-node implications and then uses them to learn powerful multi-node implications. All the newly learned relations help in extracting more necessary assignments for a given fault, potentially increasing the chance for a conflict to occur among the necessary assignments. Experimental results on ISCAS89 and ITC99 benchmarks show that our method can identify significantly more untestable faults compared to existing non branch-and-bound based techniques.

In recent years, Boolean satisfiability (SAT) has been shown to hold potential for unbounded model checking (UMC). The success of SAT-based UMC largely relies on (i) the SAT solver efficiency, (it) solution cube enlargement, and (Hi) state-set management. In this paper, we propose a simple, yet efficient, clause conversion technique to account for the state set obtained by SAT-based UMC. Our state set is stored in a zero-suppressed binary decision diagram (ZBDD), and the shared structures in the ZBDD are exploited to aggressively avoid repeated manipulation of common subsets in the state-set. The resulting number of clauses, generated for the state set, now depends on the number of nodes in the ZBDD, rather than the number of solutions found. We integrated the proposed techniques in an unbounded model checking framework that uses a pure SAT solver. The experimental results show that we can attain orders of magnitude improvement in both performance and capacity as compared to the existing techniques.

In this paper, we make two major contributions: First, to enhance Boolean learning, we propose a new class of logic implications called extended forward implications. Using a novel concept called implication-frontier, extended forward implications efficiently capture those nontrivial relationships which previous techniques failed to identify. Secondly, we introduce the concept of dual recurrence relations in sequential circuits, and propose a new theorem which uses this concept to quickly identify sequentially untestable faults. Our tool based on the proposed extended forward implications and the new theorem was applied to identify untestable faults in benchmark circuits. Significantly more untestable faults than reported by earlier techniques, low memory overhead and low computational complexity are the noteworthy features of our tool.

Recent advances in dynamic power management (DPM) techniques have resulted in designs that support a rich set of power management options, both at the hardware and software levels. This has resulted in an explosion of the design space when analyzing the system-level tradeoffs of candidate DPM strategy designs. This paper proposes a design space exploration methodology based on a high-level, multi-layered modeling framework that facilitates rapid estimation of system-wide energy by providing the designer with a global view of the system. The framework is based on the extended finite state machine formalism and abstracts the component power modes, the operating environment and the DPM architecture into interacting, concurrent layers within a single, unified model. The modeling framework is coupled with a symbolic simulation engine to allow for rapid traversal of the large design space. We first illustrate how the proposed model can be constructed by making reasonable assumptions on the system and workload parameters, and then we show how analysis of various candidate strategies can be performed using this model. Our aim is to provide a high-level model that can be used to quickly assess the impact of various power management decisions on the system-wide energy. The framework can also be a formal basis for design of energy efficient power management systems.

Motivated by data value locality and quality tolerance present in multimedia applications, we propose a new micro-architecture, Region-level Approximate Computation Buffer (RACB), to reduce power consumption in such applications. The proposed RACB relaxes the exact matching into partial and approximate tag matching and applies it to regions of code in a program, thereby allowing for aggressive computation/execution reduction, in addition to reductions in memory accesses and pipeline activities. Our experiments demonstrate that a 64-entry RACB can yield up to 70% of region-level execution reduction without noticeable quality degradation in MPEG-2 video decoding, corresponding to 55.9% of system power savings with respect to the regions

Scan-based transition tests are added to improve the detection of speed failures in sequential circuits. Empirical data suggests that both data volume and application time will increase dramatically for such transition testing. Techniques to address the above problem for a class of transition tests, called enhanced transition tests, are proposed in this article.The first technique, which combines the proposed transition test chains with the ATE repeat capability, reduces test data volume by 46.5% when compared with transition tests computed by a commercial transition test ATPG tool. However, the test application time may sometimes increase. To address the test time issue, a new DFT technique, Exchange Scan, is proposed. Exchange scan reduces both data volume and application time by 46.5%. These techniques rely on the use of hold-scan cells and highlight the effectiveness of hold-scan design to address test time and test data volume issues. In addition, we address the problem of yield loss due to incidental overtesting of functionally-untestable transition faults, and we formulate an efficient adjustment to the algorithm to keep the overtest ratio low. Our experimental results show that up to 14.5% reduction in overtest ratio can be achieved, with an average overtest reduction of 4.68%.

In this paper, we present a novel all-solutions preimage SAT solver, SOLALL, with the following features: (1) a new success-driven learning algorithm employing smaller cut sets; (2) a marked CNF database non-trivially combining success/conflict-driven learning; (3) quantified-jump-back dynamically quantifying primary input variables from the preimage; (4) improved free BDD built on the fly, saving memory and avoiding inclusion of PI variables; finally, (5) a practical method of storing all solutions into a canonical OBDD format. Experimental results demonstrated the efficiency of the proposed approach for very large sequential circuits.

Bounded model checking (BMC) based on Boolean satisfiability (SAT) methods has recently gained popularity as a viable alternative to BDD-based techniques for verifying large designs. This work proposes a number of conceptually simple, but extremely effective, optimizations for enhancing the performance of SAT-based BMC flows. The key ideas include: (1) a novel idea to combine SAT-based inductive reasoning and BMC; (2) clever orchestration of variable ordering and learned information in an incremental framework for BMC; and (3) BMC-specific ordering strategies for the SAT solver. Our experiments, conducted on a wide range of industrial designs, show that the proposed optimizations consistently provide between 1-2 orders of magnitude speedup and can be extremely useful in enhancing the efficacy of typical SAT-BMC tools.

'All-solutions ATPG' based methods have found applications in model checking sequential circuits, and they can also improve the defect coverage of a test-suite, by generating distinct multiple-detect patterns. Conventional decision selection heuristics and learning techniques for an ATPG engine were originally developed to 'quickly' find any available (single) solution. Such decision selection heuristics may not be the best for an 'all-solutions ATPG' engine, where all the solutions need to be found. In this paper, we explore new techniques to guide an 'all-solutions ATPG engine'. We first present a new decision selection heuristic that makes use of the 'connectivity of gates' in the circuit in order to obtain a compact solution-set. Next, we analyze the 'symmetry in search-states' that was exploited in 'success-driven learning' and extend it to prune conflict sub-spaces as well. Finally, we propose a new metric that determines the use of learnt information a priori. This information is stored and used efficiently during 'success driven learning'. Experimental results show that we can compute the complete solution-set with our new heuristics for large ISCAS'89 and ITC'99 circuits, where conventional guidance heuristics fail.

The work presents a new transition fault model called as late as possible transition fault (ALAPTF) model. The model aims at detecting smaller delays, which be missed by both the traditional transition fault model and the path delay model. The model makes sure that each transition is launched as late as possible at the fault site, accumulating the small delay defects along its way. Because some transition faults may require multiple paths to be launched, the simple path-delay model miss such faults. Results on ISCAS'85 and ISCAS'89 benchmark circuits shows that for all the cases, the new model is capable of detecting smaller gate delays and produces better results in case of process variations. For all circuits, on an average, 30% of the time the transition reaches later than traditional models. The algorithm proposed also detects robust and non-robust paths along with the transition faults and the execution time is linear to the circuit size.

This work presents a novel technique to identify functionally untestable transition faults in latch based designs with multiple clock domains, bringing to light unaddressed issues related to untestable fault identification in such design environments. We also introduce and provide a solution to a new variant of un-testability analysis wherein "architectural constraints'' are absorbed during the analysis. We give our tool the capability of handling transition faults resulting from defects of varying sizes, and evaluate our tool for various industrial circuits. The proposed algorithm is compared with a state-of-the-art sequential ATPG tool, and our method has shown much better performance both in the context of scan ATPG and functional test development. Results indicate that the proposed technique identifies considerably more untestable transition faults than those that can be deduced from the knowledge of untestable stuck-at faults. Additional insights from our results point to a greater need to eliminate untestable transition faults as compared to stuck-at faults, for more efficient test pattern generation and accurate coverage computation.

We present a new algorithm to extract characteristic flip-flops, which form a characteristic state set, using state correlation information. The extracted characteristic state set allows us to focus on a significantly smaller set of flip-flops while ignoring other flip-flops, thereby simplifying the target problem and reducing state explosion in very large sequential circuits. Next, partitioning is applied only on the characteristic state variables, and partial state transition graphs (STGs) are built. During test generation, test vectors are generated using a two-fold criteria: (1) whether the vector expand the overall STGs, and (2) whether this vector break the relationship among flip-flops within the correlated sets. Experiments showed that our extraction algorithm can reduce the original complete state set by up to 97%. In addition, with the reduced state variables, we achieve not only equal or better coverages for both stuck-at faults and design errors, the execution time is also significantly reduced due to the much smaller set of flip-flops. For some large sequential circuits, highest coverages have been obtained.

Sleep deprivation attacks are a form of denial of service attack whereby an attacker renders a pervasive computing device inoperable by draining the battery more quickly than it would be drained under normal usage. We describe three main methods for an attacker to drain the battery: (1) service request power attacks, where repeated requests are made to the victim for services, typically over a network - even if the service is not provided the victim must expend energy deciding whether or not to honor the request; (2) benign power attacks, where the victim is made to execute a valid but energy-hungry task repeatedly, and (3) malignant power attacks, where the attacker modifies or creates an executable to make the system consume more energy than it would otherwise. Our initial results demonstrate the increased power consumption due to these attacks, which we believe are the first real examples of these attacks to appear in the literature. We also propose a power-secure architecture to thwart these power attacks by employing multi-level authentication and energy signatures.

This paper introduces a new concept of state partitioning and state/transition exploration histories to generate test stimulus for the purpose of design validation. With our new state partitioning, during vector generation, state and transition exploration histories for each state group are maintained by dynamically constructing partial state transition graphs (STGs) for all state groups. By limiting a maximum size any state group can be, maintaining the complete state and transition exploration histories for each state group is feasible even for very large sequential circuits. While such histories are being collected, test vectors are generated using extracted spectral information from existing tests and genetic algorithm (GA) is used to explore new scenarios that are not in the histories. Experiments showed that much higher design error coverages together with smaller test sets are achieved with very short execution times.

We present a framework for high-level design validation using an efficient register-transfer level (RTL) automatic test pattern generator (ATPG). The RTL ATPG generates the test environments for validation targets, which include variable assignments, conditional statements, and arithmetic expressions in the HDL description. A test environment is a set of conditions that allow for full controllability and observability of the validation target. Each test environment is then translated to validation vectors by filling in the unspecified values in the environment. Since the observability of error effect is naturally handled by our ATPG, our approach is superior to methods that only focus on the excitation of HDL descriptions. The experimental results on ITC99 benchmark circuits and an industrial circuit demonstrate that very high design error coverage can be obtained in a small CPU times.

Abstract: The paper presents a novel technique for generating effective vectors for delay defects. The test set achieves high path delay fault coverage to capture smalldistributed delay defects and high transition fault coverage to capture gross delay defects. Furthermore, non-robust paths for ATPG are filtered (selected) carefully so that there is a minimum overlap with the already tested robust paths. A relationship between path delay fault model and transition fault model has been observed which helps us reduce the number of non-robust paths considered for test generation. To generate tests for robust and non-robust paths, a deterministic ATPG engine is developed. Clustering of paths has been done in order to improve the test set quality. Implications were used to identify the untestable paths. Finally an incremental propagation based ATPG is used for transition faults. Results for ISCAS’85 and full-scan ISCAS’89 benchmark circuits show that the filtered nonrobust path set can be reduced to 40 % smaller than the conventional path set without losing delay defect coverage. Clustering reduces vector size in average by about 40%. 1.

We present a new automatic test pattern generation algorithm for sequential circuits by traversing the partitioned state spaces. The new features include: (1) nondisjoint state groups are obtained such that two different state groups may have common flip-flops, (2) partial state transition graphs (STGs) are constructed at run time for each state group, (3) spectral information for state variables are extracted and the spectral information of the state variables helps to identify the behavior of the flip-flops in the frequency domain. This information will help us to intelligently partition the state space. We focus only on the STGs for the flip-flops that are grouped together instead of building the STG for the entire circuit, and the ATPG tries to traverse all states and transitions within each partial STG. By exercising states visited and arcs traversed, the vectors generated often lead to the detection of hard faults. Since we limit a maximum size any state group can be, construction of partitioned STGs is feasible even for very large sequential circuits. Only logic simulation is needed in our ATPG; as a result, the execution time is greatly reduced while achieving high fault coverages compared with other test generators. For some large sequential circuits, highest fault coverages have been achieved.

We present an efficient register-transfer level automatic test pattern generation (ATPG) algorithm. First, our ATPG generates a series of sequential justification and propagation paths for each RTL primitive via a deterministic branch-and-bound search process, called a test environment. Then the precomputed test vectors for the RTL primitives are plugged into the generated test environments to form gate-level test vectors. We augment a 9-valued algebra to efficiently represent the justification and propagation objectives at the RT Level. Our ATPG automatically extracts any finite state machine (FSM) from the circuit, constructs the state transition graph (STG), and uses high-level information to guide the search process. We propose new static methods to identify embedded counter structures, and we use implication-based techniques and static learning to find the FSM traversal sequences sufficient to control the counters. Finally, a simulation-based RTL extension is added to augment the deterministic test set in a few cases when there is additional room for the improvement in fault coverage. Experimental results show that our new deterministic RTL techniques achieve several orders of magnitude reduction of test generation time without compromising fault coverage when compared to gatelevel ATPG tools. Our ATPG also outperforms a recently reported simulation-based high-level ATPG tool in terms of both fault coverage and CPU time. 1.

We present a new low-power BIST (built-in-self-test) for sequential circuits. State correlation analysis is first performed on the flip-flop values in the relaxed, compacted sequence for the undetected faults to extract spatial correlations among the flip-flops. The extracted spatial correlation matrix not only provides additional metrics through which the scan order may be altered, but also allows us to omit some flip-flops in the scan chain. By leaving flip-flops that need less control out of the scan chain, we can reduce transitions on those flip-flops, thereby reducing the overall power and energy. The omission of flip-flops are done in a way that the fault coverage is unaffected. Furthermore, reordering of the flip-flops in the scan chain allows the generated patterns to be more compatible with the state sequence necessary for exciting the random-pattern-resistant faults. Our experiments show that the same or higher fault coverage can be achieved with less energy (and average power) - average power of 48.5% is reduced, with the maximum reduction of 73%.

This paper presents a novel, low cost technique based on implications to identify untestable bridging faults in sequential circuits. Sequential symbolic simulation is first performed, as a preprocessing step, to identify nets which are uncontrollable to a specific logic value. Then, an implication-based analysis is carried out for each fault to determine if a particular fault is testable or not. We also use information about the untestable stuck-at faults to filter out some bridges early in the analysis process. The application of our technique to ISCAS '89 sequential benchmark circuits and a few industrial circuits showed that a large number of untestable bridges could be identified at a low cost, both in terms of memory and execution time.

In this paper, we present a successful application of a simulation-based sequential Automatic Test Pattern Generation (ATPG) for safety property verification, with the target on verifying safety property of large, industrial strength, hardware designs for which current formal methods fail. Several techniques are developed to increase the effectiveness and efficiency during state exploration and justification of the test generator for verification, including (1) incorporation of a small combinational ATPG engine, (2) reset signal masking, (3) threshold-value simulation, and (4) weighted Hamming distance. Experimental results on both ISCAS89 benchmark circuits and real industry circuits have shown that this simulation-based verifier achieves better or comparable results to current state-of-the-art formal verification tools BINGO and CHAFF.

This paper presents a new fault-independent method for maximizing local conflicting value assignments for the purpose of untestable faults identification. The technique first computes a large number of logic implications across multiple time-frames and stores them in an implication graph. Then, by maximizing conflicting scenarios in the circuit, the algorithm identifies a large number of untestable faults that require such impossibilities. The proposed approach identifies impossible combinations locally around each Boolean gate in the circuit, and its complexity is thus linear in the number of nodes, resulting in short execution times. Experimental results for both combinational and sequential benchmark circuits showed that many more untestable faults can be identified with this approach efficiently.

We present a new method of built-in-self-test (BIST) for sequential circuits and system-on-a-chip (SOC) using characteristic faults and circuitspecific spectral information in the form of one or more Hadamard coefficients. The Hadamard coefficients are extracted from the test sequences for a small set of characteristic faults of the circuit. By extracting a few characteristic faults from the circuit, we show that detection of these characteristic faults is sufficient in detecting a vast majority of the remaining faults in the circuit. The small number of characteristic faults allows us to reduce the coefficients necessary for BIST. State relaxation is performed on the compacted test sequences to reduce the spectral noise further. Since we are targeting only a very small number of characteristic faults, the execution times for computing the spectra are greatly reduced. Our experimental results show that our new method can achieve high BIST coverage with both lower computational efforts and storage, with very few characteristic faults.

Scan based transition tests are added to improve the detection of IC speed failures using scan tests. Empirical data suggests that both data volume and application time for transition test will increase dramatically. Techniques to address this problem, for a class of transition tests called "enhanced transition tests", are proposed. The first technique, which combines the ATE repeat capability and the notion of transition test chains, reduces test data volume by 46.5%, when compared with transition tests computed by a commercial transition test ATPG tool. The test application time could increase or decrease. To address the test time issue, exchange scan, a new DFT technique, is proposed. Exchange scan reduces both data volume and application time by 46.5%. These techniques rely on the use of hold scan cells and highlight the effectiveness of hold-scan design to address test time and test data volume issues.

Low-power issues become critical when the networked computing devices depend mainly on non-AC power sources such as batteries or self-generated power. In the application of using short-range wireless networks to convey low-speed but important information, low power consumption becomes a top design consideration in wireless design. Traditionally, signal strength level is fixed during the entire time of communication to maintain a certain acceptable error rate. A new approach is proposed in this paper to explore the potential and practicality of decreasing the signal strength, thus reducing the total energy consumption. Although the error rate of one frame at the DLL layer increases, it is compensated by retransmission. And it is shown in this paper both theoretically and experimentally that the power consumed could be lowered, without incurring a higher frame loss rate. An adaptive power-adjusting algorithm is proposed to allow power and energy reduction during signal transmission. Experiments are conducted using GloMoSim, up to 71.3% reduction in power can be achieved.

Presents a spectral built-in-self-test (BIST) for a system-on-a-chip (SOC) environment. Test vectors are generated using the spectral properties of the embedded cores. Because some embedded cores may not have direct connections to the embedded TPG, it would be necessary to test them via other cores. As a result, testing such (cascaded) cores requires considerations on the spectral characteristics of the predecessor and successor cores. Matching spectral characteristics between the outputs of the predecessor core and dominant inputs of the successor core allows the successor core to be more testable. Experimental results for the spectral BIST showed that significantly more faults can be detected using spectral patterns than by conventional weighted random BIST technique.

We present a new test generation procedure for sequential circuits using spectral techniques. Iterative processes of filtering via compaction and spectral analysis of the filtered test set are performed for each primary input, extracting inherent spectral information embedded within the test sequence. This information, when viewed in the frequency domain, reveals the characteristics of the input spectrum. The filtered and analyzed set of vectors is then used to predict and generate future vectors. We also developed a fault-dropping technique to speed up the process. We show that very high fault coverages and small vector sets are consistently obtained in short execution times for sequential benchmark circuits.

Article Compiler-directed dynamic voltage/frequency scheduling for energy reduction in microprocessors Share on Authors: Chung-Hsing Hsu CS Dept., Rutgers University, New Jersey CS Dept., Rutgers University, New JerseyView Profile , Ulrich Kremer CS Dept., Rutgers University, New Jersey CS Dept., Rutgers University, New JerseyView Profile , Michael Hsiao ECE Dept., Rutgers University, New Jersey ECE Dept., Rutgers University, New JerseyView Profile Authors Info & Claims ISLPED '01: Proceedings of the 2001 international symposium on Low power electronics and designAugust 2001 Pages 275–278https://doi.org/10.1145/383082.383165Online:06 August 2001Publication History 39citation533DownloadsMetricsTotal Citations39Total Downloads533Last 12 Months9Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Article Share on Fast, flexible, cycle-accurate energy estimation Authors: Phillip Stanley-Marbell Department of Electrical and Computer Engineering, Rutgers University, Piscataway, NJ Department of Electrical and Computer Engineering, Rutgers University, Piscataway, NJView Profile , Michael Hsiao Department of Electrical and Computer Engineering, Rutgers University, Piscataway, NJ Department of Electrical and Computer Engineering, Rutgers University, Piscataway, NJView Profile Authors Info & Claims ISLPED '01: Proceedings of the 2001 international symposium on Low power electronics and designAugust 2001 Pages 141–146https://doi.org/10.1145/383082.383120Published:06 August 2001Publication History 27citation375DownloadsMetricsTotal Citations27Total Downloads375Last 12 Months10Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The rising trend in large scale integration and design complexity has greatly increased the need for efficient design error diagnosis. We present techniques for fast and efficient error diagnosis of digital circuits by eliminating to a large extent the set of false candidates identified by the diagnosis. The elimination of false candidate regions is conducted via distinguishing X's, flipping of values at the output of candidate regions, and combination of these techniques. The algorithms help to improve both the speed and resolution of error diagnosis. Experimental results on combinational benchmark circuits showed that up to 92% improvement in diagnostic resolution and 74% speedup over the original region-based diagnosis can be achieved with our approaches.

This new method of built-in self-test (BIST) for sequential cores on a system-on-a-chip (SOC) generates test patterns using a real-time program that runs on an embedded processor. Alternatively, the same program can be run on an external low-cost tester. This program generates patterns using circuit-specific spectral information in the form of one or more Hadamard coefficients. The coefficients are extracted from high fault-coverage compacted pattern sets. When an embedded processor is available on SOC, the overhead is negligible. Also, sequential cores are tested in the functional mode, avoiding activation of nonfunctional timing paths. We present experimental results to show that for hard to test circuits, with any given test time, spectral patterns provide significantly higher fault coverage than weighted-random patterns.

Presents a new test generation procedure for sequential circuits using newly-traversed state information and newly-detected fault information obtained between successive iterations of vector compaction. Two types of technique are considered. One is based on which new states a sequential circuit is driven into, and the other is based on the new faults that are detected in the circuit between consecutive iterations of vector compaction. These data modify an otherwise random selection of vectors to bias vector sequences that cause the circuit to reach new states and cause previously undetected faults to be detected. The biased vectors, when used to extend the compacted test set, provide an intelligent selection of vectors. The extended test set is then compacted. Repeated applications of state and fault analysis, vector generation and compaction produce significantly high fault coverage using relatively small computing resources. We obtained improvements in terms of higher fault coverage, fewer vectors for the same coverage, or smaller numbers of iterations and time required, consistently for several benchmark circuits.

Testing of embedded cores is very difficult in SOC (system-on-a-chip), since the core user may not know the gate level implementation of the core, and the controllability and observability of the core are limited by other cores and the user defined logic surrounding the core. One simple but expensive method to solve this problem is to add a wrapper around each core in the SOC, and shift in/out every bit at the core input, output, and possibly its internal state. An approach to remove part of these wrappers using controllability and observability evaluation via random inputs is proposed at the high level (i.e. no gate-level information needed). To achieve better results than the random input vectors, a genetic algorithm is used in this paper to justify the test patterns provided by the core designer. Several high level benchmarks are experimented and results show that with the test patterns generated by the genetic algorithm, both the wrapper size and the test application time are further reduced, while the fault coverage of each core is improved.

This paper presents a method for redundancy identification (RID) using multi-node logic implications. The algorithm discovers a large number of direct and indirect implications by extending single node implications to multiple nodes. The large number of implications found by multi-node implication method introduces a new redundancy identification technique. Our approach uses an effective node-pair selection method which is O(n) in the number of nodes to reduce execution time, and it can be used as an efficient preprocessing phase for test generation. Application of these multi-node static logic implications uncovered more redundancies in ISCAS85 combinational circuits than previous single-node methods without excessive computational effort.

Improvement of the accuracy of error and fault diagnosis as well as ATPG for IP-based designs are important problems in industry. In this paper we address these problems when portions of the design may be unspecified. Two approaches to solve these problems have been presented: (1) solving Boolean satisfiability under unknown constraints, and (2) a network modification-based solution. Experimental results on constrained equivalence checking, enhancement of error diagnosis resolution for combinational circuits, and ATPG for IP-based designs have been presented on the ISCAS 85 benchmark and industrial circuits.

A new method for state justification is proposed for sequential circuit test generation. The linear list of states dynamically obtained during the derivation of test vectors is used to guide the search during state justification. State-transfer sequences that drive the circuit from the current state to the target state may already be known. Otherwise, genetic engineering of existing state-transfer sequences is required. In both cases, genetic-algorithm-based techniques are used to generate valid state justification sequences for the circuit in the presence of the target fault. This approach achieves extremely high fault coverages, and thus outperforms previous deterministic and simulation-based techniques.

New measures of peak power are proposed in the context of sequential circuits, and an efficient automatic procedure is presented to obtain very good lower bounds on these measures, as well as providing the actual input vectors that attain such bounds. Automatic generation of a functional vector loop for near-worst case power consumption is also attained. Experiments show that vector sequences generated give much more accurate estimates of peak power dissipation and are generated in significantly shorter execution times than estimates made from randomly generated sequences for four delay models.

Estimating peak power involves optimization of the circuit's switching function. We propose genetic spot expansion and optimization in this paper to estimate tight peak power bounds for large sequential circuits. The optimization spot shifts and expands dynamically based on the maximum power potential (MPP) of the nodes under optimization. Four genetic spot optimization heuristics are studied for sequential circuits. Experimental results showed an average of 70.7% tighter peak power bounds for large sequential benchmark circuits was achieved in short execution times.

This research applies formal dataflow analysis and techniques to high-level DFT. Our proposed approach improves testability of the behavioral-level circuit description (such as in VHDL) based on propagation of the value ranges of variables through the circuit's Control-Data Flow Graph (CDFG). The resulting testable circuit is accomplished via controllability and observability computations from these value ranges and insertion of appropriate testability enhancements, while keeping the design area-performance overhead to a minimum.

Efficient methods to evaluate the quality of a test set in terms of its coverage of arbitrary defects in a circuit are presented. Our techniques rapidly estimate arbitrary defect coverage because they are independent of specific, physical, fault models. We overcome the potentially explosive computational requirements associated with considering all possible defects by implicitly evaluating multiple faults (of all types) simultaneously and by exploiting the local nature of defects. Our experiments show that a strong correlation exists between stuck-at fault coverage and defects whose behavior is independent of the input vectors. Our techniques are capable of identifying regions in the circuit where defects may escape the test set. We also demonstrate how the chances of detection of an arbitrary defect by a test set vary when a single stuck-at-fault within the vicinity of that defect is detected multiple times by the test set.

Sequential test generators fail to yield tests for some stuck-at-faults because they are unable to reach certain states necessary for exciting/propagating these target faults. Adding scan to the circuit increases reachability of these hard-to-reach and/or previously unreachable states. In this paper, we postulated that fewer scan flip-flops are needed to make these states reachable. The states necessary for detecting the hard-to-detect faults, when reached, will facilitate reaching other hard-to-reach states in one or more hops by the sequential test generator, resulting in significantly higher fault coverage. We collect information on the hard-to-reach, aborted, and easy states in our analysis. Results from our approach have indicated that higher fault coverage can be achieved with significantly fewer scan flip-flops for some circuits.

Two fast algorithms for static test sequence compaction are proposed for sequential circuits. The algorithms are based on the observation that test sequences traverse through a small set of states and some states are frequently revisited throughout the application of a test set. Subsequences that start and end on the same states may be removed if necessary and if sufficient conditions are met for them. Contrary to the previously proposed methods, where multitudes of fault simulations are required, the techniques described in this paper require only two fault simulation passes and are applied to test sequences generated by various test generators, resulting in significant compactions very quickly for circuits that have many revisited states.

We propose a new static test set compaction method based on a careful examination of attributes of fault coverage curves. Our method is based on two key ideas: (1) fault-list and test-set partitioning, and (2) vector re-ordering. Typically, the first few vectors of a test set detect a large number of faults. The remaining vectors usually constitute a large fraction of the test set, but these vectors ore included to detect relatively few hard faults. We show that significant compaction can be achieved by partitioning faults into hard and easy faults. This significantly reduces the computational cost for static test set compaction without affecting quality of compaction. The second technique re-orders vectors in a test yet by moving sequences that detect hard faults to the beginning of the test set. Fault simulation of the newly concatenated re-ordered test set results in the omission of several vectors so that the compact test set is smaller than the original test set. Experiments on several ISCAS 89 sequential benchmark circuits and large production circuits show that our compaction procedure yields significant test set reductions in low execution times.

We extend the subsequence removal technique to provide significantly higher static compaction for sequential circuits. We show that state relaxation techniques can be used to identify more or larger cycles in a test set. State relaxation creates more opportunities for subsequence removal and hence, results in better compaction. Relaxation of a state is possible since not all memory elements in a finite state machine have to be specified for a state transition. The proposed technique has several advantages: (1) test sets that could not be compacted by existing subsequence removal techniques can now be compacted, (2) the size of cycles in a test set can be significantly increased by state relaxation and removal of the larger sized cycles leads to better compaction, (3) only two fault simulation passes are required as compared to trial and re-trial methods that require multiple fault simulation passes, and (4) significantly higher compaction is achieved in short execution times as compared to known subsequence removal methods, Experiments on ISCAS89 sequential benchmark circuits and several synthesized circuits show that the proposed technique consistently results in significantly higher compaction in short execution times.

We present a fast, dynamic fault coverage estimation technique for sequential circuits that achieves high degrees of accuracy by significantly reducing the number of injected faults and faulty-event evaluations.Specficdy, we dynamically reduce injection of two types of faults: (1) hyperactive faults that never get detected, and (2) faults whose effects never propagate to a flip-flop or primary output.The cost of fault simulation is greatly reduced as injection of most of these two types of faults is prevented.Experiments show that our technique gives very accurate estimates with frequently greater speedups than the sarnpfing techniques for most circuits.Most significantly, the proposed technique can be combined with the sampling approach to obtain speedups equivalent of smd sample sizes and retain estimation accuracy of large fault samples.

New methods for fault-effect propagation and state justification that use finite-state-machine sequences are proposed for sequential circuit test generation. Distinguishing sequences are used to propagate the fault effects from the flip-flops to the primary outputs by distinguishing the faulty machine state from the fault-free machine state. Set, clear, and pseudoregister justification sequences are used for state justification via a combination of partial state justification solutions. Reengineering of existing finite-state machine sequences may be needed for specific target faults. Moreover, conflicts imposed by the use of multiple sequences may need to be resolved. Genetic-algorithm-based techniques are used to perform these tasks. Very high fault coverages have been obtained as a result of this technique.

Previous work has shown that maximum switching density at a given node is extremely sensitive to a slight change in the delay at that node. However, when estimating the peak power for the entire circuit, the powers estimated must not be as sensitive to a slight variation or inaccuracy in the assumed gate delays because computing the exact gate delays for every gate in the circuit during simulation is expensive. Thus, we would like to use the simplest delay model possible to reduce the execution time for estimating power, while making sure that it provides an accurate estimate, i.e., that the peak powers estimated will not vary due to a variation in the gate delays. Results for four delay models are reported for the ISCAS85 combinational benchmark circuits, ISCAS89 sequential benchmark circuits, and several synthesized circuits.

New measures of peak power in the context of sequential circuits are proposed.This paper presents an automatic procedure to obtain very good lower bounds on these measures as well as the actual input vectors that attain such bounds.The initial state of the circuit is an important factor in determining the amount of switching activity in sequential circuits and is taken into account.A peak power estimator tool K2 was developed using genetic techniques.Experiments show that vector sequences generated by K.2 give much more accurate estimates for peak power dissipation than the estimates made from randomly generated sequences.

Two fast algorithms for static test sequence compaction are proposed for sequential circuits. The algorithms are based on the observation that test sequences traverse through a small set of states, and some states are frequently re-visited throughout the application of a test set. Subsequences that start and end on the same states may be removed if necessary and sufficient conditions are met for them. The techniques require only two fault simulation passes and are applied to test sequences generated by various test generators, resulting in significant compactions very quickly for circuits that have many revisited states.

A fault-oriented sequential circuit test generator is described in which various types of distinguishing sequences are derived, both statically and dynamically, to aid the test generation process. A two-phase algorithm is used during test generation. The first phase activates the target fault, and the second phase propagates the fault effects (FE's) from the flip-flops with assistance from the distinguishing sequences. This strategy improves the propagation of FE's to the primary outputs, and the overall fault coverage is greatly increased. In our new test generator, DIGATE, genetic algorithms are used to derive both activating and distinguishing sequences during test generation. Our results show very high fault coverages for the ISCAS89 sequential benchmark circuits and several synthesized circuits.

A new technique is proposed to handle fault simulation at the architectural level. The technique bypasses the need for complete gate level structure and efficiently uses the architectural information. Symbolic data representing groups of stuck at faults, known as fault effects, are propagated across the circuit with intelligent propagation prediction. Fault effects may combine and form new groups in the process. Automated behavioral simulation using only three data types is used to propagate fault effects at the architectural level by propagation prediction; no additional high level constraints or precomputation of faulty behavior are needed for simulation. Although not a fully deterministic algorithm, the results of ALFSIM, Architectural Level Fault Simulation, show high accuracy when compared with the gate level fault simulation.