Successful deployment of autonomous systems in a wide range of societal applications depends on error-free operation of the underlying signal processing and control functions. Real-time error detection in nonlinear systems has mostly relied on redundancy at the component or algorithmic level causing expensive area and power overheads. This paper describes a real-time error detection methodology for nonlinear control systems for detecting sensor and actuator degradations as well as malfunctions due to soft errors in the execution of the control algorithm on a digital processor. Our approach is based on creation of a redundant check state in such a way that its value can be computed from the current states of the system as well as from a history of prior observable state values and inputs (via machine learning algorithms). By checking for consistency between the two, errors are detected with low latency. The method is demonstrated on two test case simulations - an inverted pendulum balancing problem and a sliding mode controller driven brake-by-wire (BBW) system. In addition, hardware results from error injection experiments in an ARM core representation on an FPGA and artificial sensor degradations on a self-balancing robot prove the practical feasibility of implementation.

Precisely controlled power delivery is critical for high performance systems-on-chip. This work describes functional test sequences to induce large dynamic and static supply voltage droops impacting the minimum operating voltage (VMIN) of the processor. An algorithm is provided to generate high and low power sequences that are functions targeting a wide range of power delivery network (PDN) frequencies. The voltage-droop tests induce large dynamic voltage droops by aligning hardware threads using a method that generates relatively prime sequence lengths across threads in a multi-threaded processor system. Functional tests also create symmetric and asymmetric high and low power sequences, introducing delay in processor pipeline stages. Additionally, tests consisting of a loop of sustained high-power sequences are also generated causing static droops. Simulation and silicon results of voltage-droop tests applied on a multi-threaded Qualcomm®Hexagon™processor show that the techniques increase the VMINof the processor system by up to 120 mV. Evaluation of the relatively prime method against the previously published NOP insertion method shows that the sequences generated using the relatively prime method can induce a higher rate of change of maximum dynamic voltage droop in $\sim 72.5$% of functional test sequences.

Resilience to errors in the underlying hardware is a key design objective for a large class of computing systems, from embedded systems all the way to the cloud. Sources of hardware errors include radiation, circuit aging, variability induced by manufacturing and operating conditions, manufacturing test escapes, and early-life failures. Many publications have suggested that cross-layer resilience, where multiple error resilience techniques from different layers of the system stack cooperate to achieve cost-effective resilience, is essential for designing cost-effective resilient digital systems. This paper presents a comprehensive overview of cross-layer resilience by addressing fundamental cross-layer resilience questions, by summarizing insights derived from recent advances in cross-layer resilience research, and by discussing future cross-layer resilience challenges.

Emerging intelligent systems have stringent constraints including cost and power consumption. When they are used in critical applications, resiliency becomes another key requirement. Much research into techniques for fault tolerance and dependability has been successfully applied to highly critical systems, such as those used in space, where cost is not an overriding constraint. Further, most resiliency techniques were focused on dealing with failures in the hardware and bugs in the software. The next generation of systems used in critical applications will also have to be tolerant to test escapes after manufacturing, soft errors and transients in the electronics, hardware bugs, hardware and software Trojans and viruses, as well as intrusions and other security attacks during operation. This paper will assess the impact of these threats on the results produced by a critical system, and proposed solutions to each of them. It is argued that run-time checks at the application-level are necessary to deal with errors in the results.

Ensuring run time Control Flow Integrity (CFI) has proven to be a good way to detect and prevent intrusions which result from exploitation of unknown vulnerabilities in the software. Attackers need to change the control flow and/or the code text of the victim application to achieve their malicious intent. However, existing techniques for monitoring run time CFI have been impractical due to their large software and hardware costs. In this paper, we describe a practical hardware based approach at a fine granularity to ensure integrity of code and the control flow of an executing application. We utilize the low power benefits and randomness of a stream cipher based hash, combined with the efficient hardware based monitoring, to provide a practical and functional defense against intrusion attacks.

The last decade has seen tremendous advances in the transformation of ubiquitous control, computing and communication platforms that are anytime, anywhere. These platforms allow humans to interact with machines through sensing, control and actuation functions in ways not imaginable a few decades ago. While robust control techniques aim to maintain autonomous system performance in the presence of bounded modeling errors, they are not designed to manage large multi- parameter variations and internal component failures that are inevitable during lengthy periods of field deployment. To address the trustworthiness of autonomous systems in the field, we propose a cross-layer error resilience approach in which errors are detected and corrected at appropriate levels of the design (hardware-through software) with the objective of minimizing the latency of error recovery while maintaining high failure coverage. At the control processor level, soft errors in the digital control processor are considered. At the system level, sensor and actuator failures are analyzed. These impairments define the health of the system. A methodology for adapting the control procedure of the autonomous system to compensate for degraded system health is proposed. It is shown how this methodology can be applied to simple linear and nonlinear control systems to maintain system performance in the presence of internal component failures. Experimental results demonstrate the feasibility of the proposed methodology.

Computer use in high dependability applications is rapidly increasing. These applications require the computer to be able to detect, locate, isolate and recover from software, hardware or security attacks errors. To evaluate the dependability of a computer system design, it is critical to be able to assess its ability to detect, locate, recover from errors, and to estimate coverage and latencies. Fault-injection tools play critical role in the evaluation and validation of dependable systems. They generate statistics on error coverage and latencies. This helps to identify good fault tolerance technique that detects and prevent system failures. In this paper, we present an Efficient Fault Injection System for Transient Fault (ESIFT). ESIFT is based on Python extended GDB which makes ESIFT portable across a wide variety of systems. ESFIT operates at near native speed enabling the dependability evaluation of large system. Unlike traditional techniques which evaluate only the faulty system behavior, ESIFT evaluates, concurrently, both the faulty and the fault-free system behavior. This allows faster error detection and latency evaluation.

We present cross-layer exploration for architecting resilience, a first of its kind framework which overcomes a major challenge in the design of digital systems that are resilient to reliability failures: achieve desired resilience targets at minimal costs (energy, power, execution time, and area) by combining resilience techniques across various layers of the system stack (circuit, logic, architecture, software, and algorithm). This is also referred to as cross-layer resilience. In this paper, we focus on radiation-induced soft errors in processor cores. We address both single-event upsets and single-event multiple upsets in terrestrial environments. Our framework automatically and systematically explores the large space of comprehensive resilience techniques and their combinations across various layers of the system stack (586 cross-layer combinations in this paper), derives cost-effective solutions that achieve resilience targets at minimal costs, and provides guidelines for the design of new resilience techniques. Our results demonstrate that a carefully optimized combination of circuit-level hardening, logic-level parity checking, and micro-architectural recovery provides a highly cost-effective soft error resilience solution for general-purpose processor cores. For example, a $50 {\times }$ improvement in silent data corruption (SDC) rate is achieved at only 2.1% energy cost for an out-of-order core (6.1% for an in-order core) with no speed impact. However, (application-aware) selective circuit-level hardening alone, guided by a thorough analysis of the effects of soft errors on application benchmarks, provides a cost-effective soft error resilience solution as well (with ~1% additional energy cost for a $50{\times }$ improvement in SDC rate).

CLEAR (Cross-Layer Exploration for Architecting Resilience) is a first of its kind framework which overcomes a major challenge in the design of digital systems that are resilient to hardware errors: achieve desired resilience targets at low cost (energy, power, execution time, area) by combining resilience techniques across various layers of the system stack (circuit, logic, architecture, software, algorithm). CLEAR automatically and systematically explores the large space of resilience techniques and their combinations, derives cost-effective solutions, provides guidelines for designing new techniques, and offers insights into how to design cost-effective digital systems resilient to hardware errors: 1. circuit-level techniques are crucial; 2. application-level guidance is essential; 3. existing architecture and software techniques are generally expensive or provide too little resilience; 4. some previously published techniques suffer from inaccurate analysis, leading to incorrect conclusions; 5. cost-effective protection from multiple error sources is achieved by combining techniques targeting each specific error source.

The proliferation of cyber physical systems in society, from the smart grid to sensor networks and robots has raised the importance of error resilience in signal processing and control systems to unprecedented levels. Resilience to errors in sensing and control algorithm execution in processors all the way down to circuits for sensing and actuation is of critical importance in safety-critical applications where undetected errors can have disastrous consequences. In this presentation, we describe how ideas in the domain of algorithm-based fault tolerance developed in the mid-80s for signal processing and matrix computations can be applied to a vast domain of circuits and systems in electrical engineering; from digital and analog filters to complex nonlinear autonomous control systems. The key insight is that electrical systems can be fundamentally represented by linear and nonlinear differential equations with equivalent matrix representations. These representations can be encoded with extra check states that bear a known relationship with all the observable states of the system independent of the system driving inputs. By checking for the validity of this relationship, errors can be detected and mitigated in real-time with near-zero latency with minimal hardware overhead. The broad vision of the proposed methodology is illustrated with examples from different electrical engineering domains.

In this paper, we propose a generic weighted checksum code based quality aware error detection scheme for 2-D separable linear transformation. These key components are widely used in multimedia compression systems, e.g., video and image codecs. The technique encodes the input array at the 2-D linear transformation level, and algorithms are designed to operate on encoded data and produce encoded output data. The proposed error detection technique is a system-level method therefore can be used in existing hardware or software 2-D linear transformation architectures with low overhead. More importantly, the proposed weighted checksum code based error detection can enable quality metric aware error detection which only flags an error when the quality of the result is lower than expectation. The error tolerance detection technique can fit perfectly in multimedia compression systems.

We present a first of its kind framework which overcomes a major challenge in the design of digital systems that are resilient to reliability failures: achieve desired resilience targets at minimal costs (energy, power, execution time, area) by combining resilience techniques across various layers of the system stack (circuit, logic, architecture, software, algorithm). This is also referred to as cross-layer resilience. In this paper, we focus on radiation-induced soft errors in processor cores. We address both single-event upsets (SEUs) and single-event multiple upsets (SEMUs) in terrestrial environments. Our framework automatically and systematically explores the large space of comprehensive resilience techniques and their combinations across various layers of the system stack (798 cross-layer combinations in this paper), derives cost-effective solutions that achieve resilience targets at minimal costs, and provides guidelines for the design of new resilience techniques. We demonstrate the practicality and effectiveness of our framework using two diverse designs: a simple, in-order processor core and a complex, out-of-order processor core. Our results demonstrate that a carefully optimized combination of circuit-level hardening, logic-level parity checking, and micro-architectural recovery provides a highly cost-effective soft error resilience solution for general-purpose processor cores. For example, a 50× improvement in silent data corruption rate is achieved at only 2.1% energy cost for an out-of-order core (6.1% for an in-order core) with no speed impact. However, selective circuit-level hardening alone, guided by a thorough analysis of the effects of soft errors on application benchmarks, provides a cost-effective soft error resilience solution as well (with ~1% additional energy cost for a 50× improvement in silent data corruption rate).

The rapid proliferation of sensor networks and robots in a wide range of societal applications has focused renewed attention on error-free operation of their underlying signal processing and control functions for reasons of safety and reliability. While real-time error detection in linear systems has been investigated in the past, error detection in nonlinear control functions has largely relied on implementing redundancy in components, units, or subsystems resulting in excessive area/performance overheads. In this paper, we introduce a realtime error detection methodology for nonlinear control state space systems that uses mapped predictive check states for detecting sensor and actuator malfunctions and transient errors in the execution of the control algorithm on the underlying processor. In our approach, the check state at time t bears a known relationship with the corresponding states of the nonlinear system. This check state can also be predicted from knowledge of the prior system states and inputs using nonlinear mappings. Consistency between the prior known relationship and its predicted value above, is used to check for errors in system function. We demonstrate the proposed approach on two test cases - a classical nonlinear inverted pendulum balancing problem using a moving cart and a nonlinear sliding mode controller driven electromagnetic brake-by-wire (BBW) system. Simulation results show the effectiveness of the proposed approach for detecting degradation of the sensor and actuator functions and soft errors in the execution of the control algorithms.

When we analyze the scaling factors of the recent technology nodes, we come to the conclusion that the geometrical scaling scenario has been replaced by the electrical scaling and hence the electrical characterization of these really challenging technologies becomes an absolute must. However, the extremely small process windows, and the 3-dimensional nature of the FinFET devices and the complicated interconnect schemes, make this characterization very difficult. Systematic failure modes and their dependence on the layout patterns are extremely complex and almost impossible to detect in-line. Moreover, soft failures become much more prevalent due to process marginalities and present not only yield but also reliability hazards. Hence, the new fault models must be created that take into account layout patterns and layout-process interactions to allow for more efficient testing and reliability risk screening. This talk will present novel approaches to electrical characterization of the dominant failure modes, its impact on the test generation and execution, and the need for tracking this information all the way from the front end process to the test and assembly stages of IC manufacturing.

A duty-cycle correction technique using a novel pulsewidth modification cell is demonstrated across a frequency range of 100 MHz-3.5 GHz. The technique works at frequencies where most digital techniques implemented in the same technology node fail. An alternative method of making time domain measurements such as duty cycle and rise/fall times from the frequency domain data is introduced. The data are obtained from the equipment that has significantly lower bandwidth than required for measurements in the time domain. An algorithm for the same has been developed and experimentally verified. The correction circuit is implemented in a 0.13-μm CMOS technology and occupies an area of 0.011 mm2. It corrects to a residual error of less than 1%. The extent of correction is limited by the technology at higher frequencies.

Bounded Model Checking (BMC), as a formal method of verifying VLSI circuits, shows violation of a given circuit property by finding a counter-example to the property along bounded state paths of the circuit. In this paper, we present an emulation framework for Automatic Test Pattern Generation (ATPG)-BMC model capable of checking properties on gate-level design. In our approach, counterpart to a property is mapped into a structural monitor with one output. A target fault is then injected at the monitor output, and a modified ATPG-based state justification algorithm is used to find a test for this fault which corresponds to formally establishing the property. In this paper, emulating the process of ATPG-based BMC on reconfigurable hardware is presented. The ATPG-BMC emulator achieves a speed-up over software based methods, due to the fine-grain massive parallelism inherent to hardware. As circuit sizes approach limits of even ATPG-based method feasibility, further solutions are required. In this presentation, we propose an ATPG-based algorithm for formal verification implementation on reconfigurable hardware (FPGA). This implementation is shown to have a linear relationship between the size of the circuit being verified and FPGA resource utilization. This implies a reasonable bound on the size of the implementation, as opposed to an exponential utilization explosion as circuit size increases.

We describe a methodology to model the low power and voltage behavior of multi-voltage custom memories in processors. These models facilitate early power-aware verification by abstracting the transistor-level representation of the memory to its power-aware behavioral RTL model. To the best of our knowledge, this is the first attempt at addressing the power-aware RTL model generation problem for custom memories. In our method, we identify voltage crossing points in transistors across channel connected components and use these crossing points to transform the RTL for power-awareness closely matching its circuit implementation. Without the proposed abstraction technique to generate power-aware RTL, low-power verification of such memories will need to be done using transistor-level simulations that are prohibitively time-intensive and hence impractical. We check for correctness of these generated power-aware memory models through formal equivalence, symbolic simulations, assertion and simulation based verification. These models are also validated using static power-domain checks. By applying this methodology in a power-aware design and verification framework on a commercial processor, we identified and corrected low power circuit and RTL bugs prior to tape-out.

Fault tolerant (or dependable) computing has always been an exciting research area in the intersection of computer science and engineering and electrical and electronics engineering. During the last two decades the applicability of the methods and tools that the fault tolerance research community produces has expanded to virtually all application domains. The type of fault tolerance methods employed in a computing system depend on: (a) the faults expected to affect the system, (b) the importance of errors in the system operation, (c) the design, cost and power budgets that can allocated to fault tolerance and reliable operation. New solutions and tools in fault tolerant computing are emerging to deal with the very broad spectrum of values that all (a), (b) and (c) can take in today's computing landscape.

Statistical fault injection is widely used for analyzing hardware in the presence of soft errors. Although this method can give accurate results for averaged erroneous outcomes with a fairly small sample size, it will not be accurate for vulnerability analysis of each sequential element in the design with small sample sizes. This paper describes a novel and highly efficient technique which is suitable for detailed vulnerability analysis of a processor. The technique involves specific sets of assembly language routines, and is shown to be much more efficient and comprehensive compared with traditional statistical error injection on a predetermined set of benchmarks. We have shown the effectiveness of the method using error injection in an ARM Amber25 processor model. Our analysis is based on more than 330,000 simulation runs with single bit-flips on the sequential elements of this processor running our synthetic benchmarks and 40,000 FPGA-based error injections for 4 conventional benchmarks.

Soft errors, caused by radiation, have become a major challenge in today's computer systems and networking equipment, making it imperative that systems be designed to be resilient to errors. Error injection is a powerful approach to evaluate system resilience, and current practice is to inject errors in architectural registers of processors, program variables of applications, or storage elements in the hardware model. This paper, using answers to frequently asked questions, discusses the need for rethinking conventional approaches to error injection, showing data from recent research and our simulation results. Approaches to improving current error injections are also suggested.

The advent of sensor networks, robots, autonomous vehicles and the smart grid have made the dependability of circuits and systems that control them critical to society and national defense. While significant advances in the design of linear and nonlinear control systems have been made to allow modes of operation not possible in the past, the problem of resilience to errors induced by hostile operating environments remains largely unexplored even though the probability of such errors occurring during real-time operation has increased. In this talk we propose mechanisms for detecting transient errors in control systems and circuitry as well as diagnosing and correcting for their effects on overall system operation. It is shown how real-number checksum encodings of circuit function can be used to detect and correct errors in the plant and feedback subsystems of linear control systems. Applications to signal processing and control algorithms are described. It is shown how errors in motor control electronics can be detected and corrected using the proposed methodology. Finally, extensions to nonlinear control systems are presented.

This paper presents a novel low power 11-bit hybrid ADC using flash and delay line architectures, where a 4-bit flash ADC is followed by a 7-bit delay-line ADC. This hybrid ADC inherits accuracy and power efficiency from flash ADCs and delay-line ADCs, respectively. Also, in order to reduce the power of the first stage flash ADC, a power-saving technique is adopted by biasing the DC tail current of the preamplifiers at 5μA instead of the operational current, 47μA in stand-by mode. The hybrid ADC was designed and simulated in a commercial 65nm process. With 1.1 V supply and 100 MS/s, the ADC achieves an SNDR of 60 dB and consumes 1.6 mW, which results in a figure of merit (FOM) of 19.4 fJ/conversion-step without any calibration technique. Also, Monte Carlo simulations are performed with a 3σ device mismatch for the SNDR estimation, and the SNDR is observed to be better than 58.5 dB.

The rapid shrinking of device geometries in the nanometer regime requires new technology-aware design methodologies. These must be able to evaluate the resilience of the circuit throughout all System on Chip (SoC) abstraction levels. To successfully guide design decisions at the system level, reliability models, which abstract technology information, are required to identify those parts of the system where additional protection in the form of hardware or software coun-termeasures is most effective. Interfaces such as the presented Resilience Articulation Point (RAP) or the Reliability Interchange Information Format (RIIF) are required to enable EDA-assisted analysis and propagation of reliability information. The models are discussed from different perspectives, such as design and test.

This paper proposes novel DIF and DIT, FFT algorithms that utilizes data sparsity information to acheive sub-optimal computational complexity over traditional radix-2 FFT. Using the sparsity information, a map of the relavant nodes that would contribute to the FFT sum is first derived. Then the second part of the algorithm traverses this map and performs computation. This paper also provides the analysis of the computational complexity and how it can be tied in to existing frame work of OFDMA baseband. This algorithm is well suited for hardware efficient in-place FFT computations and especially for large size FFTs. The best application would be to use this algorithm in OFDMA basebands where the sparsity information can be known in advance.

Evaluating the fault coverage of manufacturing tests has become a time-consuming process due to today's large and complex digital designs. The computation cost is even more pronounced in software-based self test, on-line test, and logic BIST schemes, which require fault simulation of sequential circuits. In this paper, we build a regression model for estimating stuck-at fault coverage. This model is built based on partial fault simulation along with a statistical metric, which is calculated by a single pass of fault-free simulation. Our results on ISCAS'85, ISCAS'89, and the OR1200 processor show that by only fault simulating 7.6% of the test vectors, on average, over 94% of the fault coverage bounds are estimated correctly.

In-field testing of SoC devices is increasingly important to face the dependability requirements of several application domains. Different solutions can be devised and adopted. We summarize the main solutions currently adopted by industry, identify the most critical open issues, and discuss important future trends.

Evaluating the coverage of tests for large circuits is computationally very intensive, particularly for logic BIST, software-based self test and on-line test schemes. This has led to research into techniques for rapidly evaluating the coverage of proposed test. We introduce a new metric which is highly correlated with fault coverage measured by gate-level simulators. Based on this metric, we estimate the time when the fault coverage saturates. This is done with only one pass of simulation and it provides a measure of the effectiveness of the test sequence when applied to the circuit-under-test; additionally, the fault coverage can be estimated with a relatively small number of test vectors. Experimental results on the ISCAS'85 and ISCAS'89 benchmarks, and a RISC processor (OR1200), show an average error of 2.85% in the estimated fault coverage compared with the fault coverage from full fault simulation, with an average speedup over 8× for large circuits.

Delay line ADCs become more and more attractive with technology scaling to smaller dimensions with lower voltages. However, linearity, which has always been an issue, becomes a problem with longer delay lines. Resolutions of reported delay line ADCs are hardly more than 4 bits with sampling rates of hundreds of MHz. In this paper, we present a technique which extends harmonic distortion correction techniques to digital calibration of a delay-line ADC. In our simulation results, digital calibration improves SNDR and SFDR to 42.5 dB and 45.4 dB, respectively, compared with the original SNDR of 25.6 dB and the original SFDR of 25.7 dB. This strongly supports the scalability of delay line ADCs and their improved performance in further scaled fabrication processes.

Choosing the correct error injection technique is of primary importance in simulation-based design and evaluation of robust systems that are resilient to soft errors. Many low-level (e.g., flip-flop-level) error injection techniques are generally used for small systems due to long execution times and significant memory requirements. High-level error injections at the architecture or memory levels are generally fast but can be inaccurate. Unfortunately, there exists very little research literature on quantitative analysis of the inaccuracies associated with high-level error injection techniques. In this paper, we use simulation and emulation results to understand the accuracy trade-offs associated with a variety of high-level error injection techniques. A detailed analysis of error propagation explains the causes of high degrees of inaccuracies associated with error injection techniques at higher levels of abstraction.

In the past few years, many techniques have been introduced which try to utilize excessive timing margins of a processor. However, these techniques have limitations due to one of the following reasons: first, they are not suitable for high-performance processor designs due to the power and design overhead they impose; second, they are not accurate enough to effectively exploit the timing margins, requiring substantial safety margin to guarantee correct operation of the processor. In this paper, we introduce an alternative, more effective technique that is suitable for high-performance processor designs, in which a processor predicts timing errors in the critical paths and undertakes preventive steps in order to avoid the errors in the event that the timing margins fall below a critical level. This technique allows a processor to exploit timing margins, while only requiring the minimum safety margin. Our simulation results show that proposed idea results in 12% and 6% improvement in energy and Energy-Delay Product (EDP), respectively, over a Razor-based speculative method.

In the recent past, there has been a proliferation of complex control problems in sensor network design, multi-agent systems such as autonomous vehicles and robotics, to name a few. While prior research has focused on the design of optimal controllers for real-time systems, in the future it will become increasingly difficult to perform periodic maintenance of such systems due to their mobile and autonomous nature. Moreover, in safety-critical real-time applications it will become increasingly necessary to perform real-time monitoring of the plant as well as its controller functions for reasons of reliability and safety. In this paper, we develop, for the first time, a theory for implementing low-overhead and high coverage detection of transient errors and permanent faults in linear control systems consisting of the plant and its controller using analog checksums. The approach is demonstrated on a servo-motor control problem. It is shown that small parametric perturbations as well as transient errors are detected in real-time using the proposed checking methodology.

Running at-speed functional tests has shown to be a very effective method to detect faulty chips. In our previous paper we presented a methodology for generating functional tests aimed at hard to detect gate level faults in the control logic of a processor. In that methodology gate level tests were mapped to the register transfer level (RTL) and a faulty RTL model was built. The propagation constraints of the fault through the design were captured as linear temporal logic (LTL) properties. These constraints reduced the search space. Further, the constraints also allowed us to do structural reductions like cone of influence reduction and removal of irrelevant duplicated signals. Overall the constraints provided improved scaling. Not all the design behaviours are required to generate a test for a fault. In this paper we use this insight to scale our previous methodology further. Under-approximations are design abstractions that only capture a subset of the orignial design behaviors. The use of RTL for test generation affords us two types of under-approximations: bit-width reduction and operator approximation. Our experiments show that the use of these two under-approximations can achive 2× to 3× reduction in test generation time without compromising the fault coverage.

Transient errors during execution of a process running on a processor can lead to serious system failures or security lapses. It is necessary to detect, and if possible, correct these errors before any damage is caused to the system. Of the many approaches, monitoring the control flow of an application during runtime is one of the techniques used for transient error detection during an application execution. Although promising, the cost of implementing the control flow checks in software has been prohibitively high and hence is not widely used in practice. In this paper we describe a hardware based control flow monitoring technique which has the capability to detect errors in control flow and the instruction stream being executed on a processor. Our technique achieves a high coverage of control flow error detection (99.98 %) and has the capability to quickly recover from the error, making it resilient to transient control flow errors. It poses an extremely low performance overhead (~ 1 %) and reasonable area cost (<; 6 %) to the host processor. The framework for runtime monitoring of control flow described in this paper can be extended to efficiently monitor and detect any transient errors in the execution of instructions on a processor.

As the complexity of integrated circuit design increases and production schedules become shorter, the dependency on post-silicon validation for capturing design errors that escape from pre-silicon verification also increases. A major challenge in post-silicon validation is the limited observability of internal states caused by the limited storage capacity available for post-silicon validation. Recent research has shown that observability can be enhanced if trace and scan signals are combined together, compared with the debugging scenario where only trace signals are monitored. This paper proposes an enhanced and systematic algorithm for the efficient combination of trace and scan signals to maximize the observability of internal circuit states. Experimental results on benchmark circuits show that the proposed technique provides a higher number of restored states compared to the existing techniques.

At the 1999 ITC, Pat Gelsinger from Intel delivered an important keynote address where he outlined the need for a low-pin count tester with lower performance pin electronics to meet the stringent test cost requirements of a billion transistor machine. At the 2009 ITC, engineers from AMD came forward with an I/O test solution that is believed to meet the Intel challenge using a cash-resident self-testing strategy combined with an external low-pin count tester. How can we drive major challenges to post-silicon validation and in huge variance era? Technology scaling enables us to trade off amplitude resolution for time resolution. Accordingly, both internal and external tests, some of which use low-pin count testers, are also shifting from voltage centric tests to timing centric tests. How can time resolution be used to push the timing centric tests beyond current limitations? How can spatial resolution be realized to enhance yields in terms of both die-to-die variations and within-die variations? What is necessary to provide robust on-chip solutions subject to huge variations, which may be combined with an external low-pin count tester?

Circuit timing is becoming more and more uncertain under greater process variation as technology scales. Given the fault probability of each timing path and their statistical correlation from a statistical timing framework, the path selection problem for delay faults has a nature similar to the problem of designing a portfolio of stocks or assets or determining the size of bets in gambling to minimize risk. This observation allows us to develop a very different path selection approach from the conventional ones. If selection of k paths is required in a set of paths, we partition the set into two path sets and determine how many paths should be selected in each path set out of the k paths based on the probabilities of each path set containing faulty paths. We recursively continue this process, which results in the paths to be targeted during tests. The partitioning is easily performed because the paths are already grouped into the depth-first search tree based on their suffix or prefix. Experimental results show that the proposed algorithm can effectively use the correlation to generate high-quality path sets. In addition, we study the issues that occur after automatic test pattern generation on the selected paths, and discuss possible solutions to them.

This paper presents a built-in self repair analyzer with the optimal repair rate for memory arrays with redundancy. The proposed method requires only a single test, even in the worst case. By performing the must-repair analysis on the fly during the test, it selectively stores fault addresses, and the final analysis to find a solution is performed on the stored fault addresses. To enumerate all possible solutions, existing techniques use depth first search using a stack and a finite-state machine. Instead, we propose a new algorithm and its combinational circuit implementation. Since our formulation for the circuit allows us to use the parallel prefix algorithm, it can be configured in various ways to meet area and test time requirements. The total area of our infrastructure is dominated by the number of content addressable memory entries to store the fault addresses, and it only grows quadratically with respect to the number of repair elements. The infrastructure is also extended to support various types of word-oriented memories.

This paper presents an on-chip test circuit with a high resolution for testing source synchronous interface timing. Instead of a traditional strobe-scanning method, an on-chip delay measurement technique which detects the timing mismatches between data and clock paths is developed. Using a programmable pulse generator, the timing mismatches are detected and converted to pulse widths. To obtain digital test results compatible with low-cost ATE, an Analog-to-Digital Converter (ADC) is used. We propose a novel calibration method for the input range for the ADC using a binary search algorithm. This enables test results to be measured with high resolution using only a 4-bit flash ADC (which keeps the area overhead low). The method achieves a resolution of 21.88 ps in 0.18μ technology. We also present simulation results of the interface timing characterization, including timing margins and timing pass/fail decisions.

This paper presents a new method for random jitter measurement on systems-on-a-chip (SoCs) by exploiting shmoo plotting in automatic test equipment (ATE). After finding the maximum operating frequency of a microprocessor using functional test patterns that can sensitize its critical paths, the proposed method constructs a cumulative distribution function (CDF) whose standard deviation represents the root mean square (RMS) value of the random jitter of the clock signals used in the microprocessor. By leveraging tester period resolution with a frequency multiplying phase-locked loop (PLL) in the SoC, the shmoo plot with a fine period step size can detect the jitter component in the clock signal, which reflects the actual jitter that most critical paths undergo. The proposed idea was verified with circuit-level simulations, and was validated by silicon measurements using one of the latest SoC products.

At-speed functional testing has proven to be very effective at uncovering defective chips. However for processor testing, generating instruction level tests for covering all faults is a challenge given the issue of scalability. Data-path faults are relatively easier to control and observe compared to control-path faults. In this paper we present a novel method to generate instruction level tests for hard to detect control-path faults in a processor. We initially map the gate level stuck-at fault to the Register Transfer Level (RTL) and build an equivalent faulty RTL model. The fault activation and propagation constraints are captured using Control and Data Flow Graph of RTL as an Liner Temporal Logic (LTL) property. This LTL property is then negated and given to a Bounded Model Checker based on a Bit-Vector Satisfiability Module Theories (SMT) solver. From the counter-example to the property we can extract a sequence of instructions that activates the gate level fault and propagates the fault effect to one of the observable points in the design. Our approach is completely automatic and does not require any external information or manual intervention. Experimental results show that our method is robust and scalable for generating functional tests for hard to detect faults.

Hardware based execution monitoring of applications holds the promise for an effective and tamper-proof solution for intrusion detection on processor. This paper presents a practical hardware based intrusion detection framework which uses stream cipher based hashing techniques for runtime control flow and instruction integrity monitoring. This framework enables accurate monitoring of the control flow of a process with an instruction level granularity. Additional hardware required for implementation of our framework has very low power and area overheads which makes it possible to practically implement execution monitoring even on embedded processors. Our technique achieves an order of magnitude lower power overhead compared to other similar techniques. Furthermore, our implementation of the developed framework has a low intrusion detection latency, which enables us to verify the control flow integrity of the executing code before the violating control flow instructions are retired from the processor pipeline.

FALCON (FAst fauLt COverage estimatioN) is a scalable method for fault grading which uses local fault simulations to estimate the fault coverage of a large system. The generality of this method makes it applicable for any modular design. Our analysis shows that the run time of our algorithm is related to the number of gates and the number of IOs in a module, while fault simulation run time is related to the total number of gates in the system. We have measured fault coverage for OR1200 and IVM processors and compared the results with fault simulation performed by a commercial tool. We have also compared our results with fault sampling. Our results show that for large designs FALCON is an order of magnitude faster compared with fault simulation. It also has a smaller error rate compared with fault sampling when the size of design under test grows.

Conventional test for high speed serial links requires expensive test equipment to meet the standard < 10−12bit error rate (BER) requirement. Although timing margining loop-back tests are cost effective, phase interpolator (PI) circuitry needs to be tested for test completeness. Our method provides an efficient linearity test capability for the PI circuitry. In the proposed scheme, a sliding window search algorithm is used to extract differential nonlinearity (DNL) and integral nonlinearity (INL), based on a jitter distribution obtained from undersampling. Various simulations were performed to evaluate the accuracy and robustness of the method. They indicate that the proposed algorithm provides an accurate estimation of linearities of the PI. We also implemented our algorithm in a conventional low cost high volume manufacturing (HVM) tester platform to show feasibility and validity of the proposed technique.

Technology scaling introduces many sources of variability and uncertainty that are difficult to model and predict [3]. The result of these uncertainties is a degradation in our ability to predict the performance of fabricated chips, i.e., a lack of model-to-hardware matching. The prediction of circuit performance is the result of a complex hierarchy of models starting at the basic MOSFET device model and rising to full-chip models of important performance metrics like power, frequency of operation, etc. The assessment of the quality of such models is an important activity, but it is becoming harder and more complex with rising levels of variability, as well as with the increase in the number of systematic effects observed in modern CMOS processes. The purpose of this paper is to introduce a special-purpose test structure that specifically focuses on ensuring the accuracy of gate timing models. The certification of digital design correctness (the so-called signoff) is based largely on the results of performing a Static Timing Analysis (STA) [15], [18], which, in turn, is based entirely on the gate timing models. Our test structure compares favorably to alternative approaches; it is far easier to obtain the desired results than direct delay measurement, and it is much more general than simple ring oscillator structures. Further, the structure is specified at a high level, allowing it to be synthesized using a standard ASIC place-and-route flow, thus capturing the systematic local layout effects which can sometimes be lost by simpler (e.g., ring oscillator) structures. Experimental results show the structure can play an important role in identifying mismatches between timing models and observed hardware.

This paper presents a Built-In Self-Test (BIST) scheme to measure high speed double data rate (DDR) memory output timing using low cost testers. This technique uses an on-chip pattern generator to generate a time delay between data and data-strobe or clock. The time delay is controlled precisely using a phase interpolator based cycle-by-cycle control method. A novel method for testing the resolution of phase interpolator, which does not need any extra hardware, is also presented. Using the test resolution, a timing pass/fail flag is set and the timing margin is quantified as a multiple of the test clock cycle. Since these test results have high observability, output per-pin timing performance can be diagnosed easily, which is especially good for testing parallel memory interfaces. Moreover, these features make our scheme compatible with low-cost testers and decreases the time-to-market for the chip. The BIST circuit has been implemented using the 0.18-μm CMOS process, and chip measurement results are presented. We obtained a test resolution of 10 ps for testing output timing. Using the fabricated test chip, this paper shows the effects of switching noise, per-pin skews and slew-rate change on output timing variations.

As process technology continues to shrink, Negative Bias Temperature Instability (NBTI) has become a major reliability issue in CMOS circuits. NBTI degrades the threshold voltage of the PMOS transistor and, over time, causes the operating speed of the circuit to become slower (also known as the aging effect). In this paper, we introduce a new aging-aware Flip-Flop (FF) that is based on accurate, run-time Failure Prediction. In order to maintain prediction accuracy despite aging, we use two schemes: (a) the master latch in the main FF is duplicated and used as an aging monitor so that it can have the same aging effect as that of the main FF; (b) the delay element that is used for the guardband is inserted into the clock network to utilize the recovery effect of NBTI. These schemes keep the guardband virtually constant, which reduces the likelihood of both overestimating the aging effect and failing to detect it. The SPICE simulation results reveal that our FF architecture maintains its prediction accuracy for up to 10 years as a result of keeping its guardband almost completely constant.

Reconvergent paths in circuits have been a nuisance in various computer-aided design (CAD) algorithms, but no elegant solution to deal with them has been found yet. In statistical static timing analysis (SSTA), they cause difficulty in capturing topological correlation. This paper presents a technique that in arbitrary block-based SSTA reduces the error caused by ignoring topological correlation. We interpret a timing graph as an algebraic expression made up of addition and maximum operators. We define the division operation on the expression and propose algorithms that modify factors in the expression without expansion. As a result, the algorithms produce an expression to derive the latest arrival time with better accuracy in SSTA. Existing techniques handling reconvergent fanouts usually use dependency lists, requiring quadratic space complexity. Instead, the proposed technique has linear space complexity by using a new directed acyclic graph search algorithm. Our results show that it outperforms an existing technique in speed and memory usage with comparable accuracy. More important, the proposed technique is not limited to SSTA and is potentially applicable to various issues due to reconvergent paths in timing-related CAD algorithms.

The maximum operator in statistical static timing analysis (SSTA) is a decent approximation for timing sign-off, but often causes significant error in SSTA applications. This paper presents a timing criticality computation method based on non-maximum analytic operators in a parameterized SSTA. After an SSTA run, the proposed method computes the criticality for all edges and nodes in a single graph traversal. Although we do not employ the max operator in the computation process, the error in the maximum operator still degrades the accuracy of the computed criticality because the criticality is a joint probability of expressions, including arrival times, which are computed by the maximum operator during SSTA. To address this issue, we employ the refactoring technique, which was recently proposed to reduce common path pessimism in combinational circuits. This paper shows that refactoring is also very useful in reducing the maximum-induced error in arrival times, and how existing graph-based algorithms can be geared toward refactoring. Our experimental results show that the proposed method reduces the error of the criticality significantly compared to the conventional cutset-based method.

This paper presents a method to compute criticality probabilities of paths in parameterized statistical static timing analysis. We partition the set of all the paths into several groups and formulate the path criticality into a joint probability of inequalities. Before evaluating the joint probability directly, we simplify the inequalities through algebraic elimination, handling topological correlation. Our proposed method uses conditional probabilities to obtain the joint probability, and statistics of random variables representing process parameters are changed to take into account the conditions. To calculate the conditional statistics of the random variables, we derive analytic formulas by extending Clark's work. This allows us to obtain the conditional probability density function of a path delay, given the path is critical, as well as to compute criticality probabilities of paths. Our experimental results show that the proposed method provides 4.2X better accuracy on average in comparison to the state-of-art method.

In the face of large-scale process variations, statistical timing methodology has advanced significantly over the last few years, and statistical path selection takes advantage of it in at-speed testing. In deterministic path selection, the separation of path selection and test generation is known to require time consuming iteration between the two processes. This paper shows that in statistical path selection, this is not only the case, but also the quality of results can be severely degraded even after the iteration. To deal with this issue, we consider testability in the first place by integrating a satisfiability (SAT) solver, and this necessitates a new statistical path selection method. We integrate the SAT solver in a novel way that leverages the conflict analysis of modern SAT solvers, which provides more than 4X speedup without special optimizations of the SAT solver for this particular application. Our proposed method is based on a generalized path criticality metric whose properties allow efficient pruning. Our experimental results show that the proposed method achieves 47% better quality of results on average, and up to 361X speedup compared to statistical path selection followed by test generation.

This paper presents a method to compute criticality probabilities of paths in parameterized statistical static timing analysis (SSTA). We partition the set of all the paths into several groups and formulate the path criticality into a joint probability of inequalities. Before evaluating the joint probability directly, we simplify the inequalities through algebraic elimination, handling topological correlation. Our proposed method uses conditional probabilities to obtain the joint probability, and statistics of random variables representing process parameters are changed due to given conditions. To calculate the conditional statistics of the random variables, we derive analytic formulas by extending Clark's work. This allows us to obtain the conditional probability density function of a path delay, given the path is critical, as well as to compute criticality probabilities of paths. Our experimental results show that the proposed method provides 4.2X better accuracy on average in comparison to the state-of-art method.

It is known that power-up values of embedded SRAM memory are unique for each individual chip. The uniqueness enables the power-up values to be considered as SRAM fingerprints used to verify device identities, which is a fundamental task in security applications. However, as the SRAM fingerprints are sensitive to environmental changes, there always exists a chance of error during the authentication process. Hence, the accuracy of a device authentication system with the SRAM fingerprints should be carefully estimated and verified in order to be implemented in practice. Consequently, a proper system evaluation method for the SRAM-based device authentication system should be provided. In this paper, we introduce tractable and computationally efficient system evaluation methods, which include novel parametric models for the distributions of matching distances among genuine and imposter devices. In addition, novel algorithms to calculate the confidence intervals of the estimates, which are crucial in system evaluation, are presented. Also, empirical results follow to validate the models and methods.

The wakeup sequence for power gating techniques has become an important issue as the rush current typically causes a high voltage drop. This paper proposes a new wakeup scheme utilizing an on-chip detector which continuously monitors the power supply noise in real time. Therefore, this scheme is able to dynamically throttle the wakeup sequence according to ambient voltage level. As a result, even the adjacent active circuit blocks induce an unexpectedly high voltage drop, the possibility of the occurrence of excessive voltage drop is reduced significantly.

In the nanometer era, the mismatch between the pre-silicon model and the post-silicon timing behavior is becoming severer. Therefore, it is necessary to validate timing with post-silicon data. We propose a method that estimates all the segment delays in the observed paths of a design from post-silicon path delay measurements. Our method is based on equality-constrained least squares methods, which enable us to find a unique and optimized solution of segment delays from underdetermined systems. Experimental results show that segment delays obtained using our method achieved correlation ranged from 0.848 to 0.992 to the sampled segment delays for different ISCAS-85 benchmark circuits.

Memory interface speed has been rapidly increasing to overcome the performance gaps between microprocessor and memory. Testing the I/O timing parameters at-speed has become a challenge because of the limitations on the test clock frequencies provided by low-cost testers. This paper presents a technique to generate a dual-capture signal with a programmable delay for both rising and falling transitions, which effectively tests double-data rate memory interface timing. The relative delay difference between data and clock paths is measured for the I/O timing test instead of using complicated test vectors. The test clock frequency is programmed in a wide operating range with 20 ps resolution. The proposed on-chip programmable double-capture generator can be also easily integrated with the current scan-based delay test methods. The scheme has low area overhead, low design effort, and is also compatible with low-cost testers.

In the face of large-scale process variations, statistical timing methodology has advanced significantly over the last few years, and statistical path selection takes advantage of it in at-speed testing. In deterministic path selection, the separation of path selection and test generation is known to require time consuming iteration between the two processes. This paper shows that in statistical path selection, this is not only the case, but also the quality of results can be severely degraded even after the iteration. To deal with this issue, we consider testability in the first place by integrating a SAT solver, and this necessitates a new statistical path selection method. Our proposed method is based on a generalized path criticality metric which properties allow efficient pruning. Our experimental results show that the proposed method achieves 47% better quality of results on average, and up to 361x speedup compared to statistical path selection followed by test generation.

Timing analysis is a key sign-off step in the design of today's chips, but as technology advances, it becomes ever more challenging to create timing models that accurately reflect real timing-related behavior. Complex dependencies on second order phenomena, such as pattern density and stress/strain make it very difficult to develop device models and simulation tools that accurately predict the timing behavior that will be seen in actual product silicon. As a result, it is necessary to validate timing models in silicon. Traditional ways to validate timing models use ring oscillators or perform delay testing but both approaches have significant drawbacks. Ring oscillators lack diversity in circuit structure and present layout configurations that are not typical of real products. Delay test can be expensive to apply and provides directly only path delay information not individual gate delays. To address these limitations, we explore the potential of a new test structure-based method of timing model validation. The proposed approach combines benefits of a ring oscillator and path delay testing while addressing their limitations. Specifically, the test structure is composed of circuits that are physically synthesized and therefore product-representative, but configures the devices under test into oscillating paths so that measurement is easy and inexpensive. Path delay test ATPG is used to generate test patterns whose oscillation frequencies provide measures of path delays. Gate delays are deduced from those path delays using a matrix that codes the delay elements comprising each path in a careful way that overcomes overdetermination problems in the matrix algebra. Results show that RMS errors can be maintained under 5% for all gate types using a chosen circuit.

This paper presents an efficient software technique, control-flow error detection through assertions (CEDA), for online detection of control-flow errors. Extra instructions are automatically embedded into the program at compile time to continuously update runtime signatures and to compare them against preassigned values. The novel method of computing runtime signatures results in a huge reduction in the performance overhead, as well as the ability to deal with complex programs and the capability to detect subtle control-flow errors. The widely used C compiler, GCC, has been modified to implement CEDA, and the SPEC benchmark programs were used as the target to compare with earlier techniques. Fault injection experiments were used to demonstrate the effect of control-flow errors on software and to evaluate the fault detection capabilities of CEDA. Based on a new comparison metric, method efficiency, which takes into account both error coverage and performance overhead, CEDA is found to be much better than previously proposed methods.

Timing problems in high-speed serial communications are mitigated with phase-interpolator (PI) circuitry. Linearity testing of PI has been challenging, even though PI is widely used in modern high speed I/O architectures. Previous research has focused on implementing additional built-in circuits to measure PI linearity. In this paper, we present a cost effective PI linearity measurement technique which requires no significant modification of existing I/O circuits. Our method uses jitter distributions obtained from random jitter injected into the data channel. Two distributions are separately obtained using undersampling and sampling using PI. The proposed algorithm calculates the differential nonlinearity (DNL) from the difference of these distributions. Simulation results show that the average prediction RMS error for the DNL calculation is 0.31 LSB.

A built-in self-test (BIST) for testing high speed source-synchronous memory interfaces has been designed using 0.18-μm TSMC process. To overcome limitations of the resolution and the accuracy in low-cost automated test equipment (ATE), a cycle-by-cycle controllable embedded pattern generator in the proposed BIST scheme is presented to specify performance-related I/O parameters. Using this method, the I/O parameters affected by the internal and the external mismatches are investigated by measuring the relative timing differences between the data lines and the strobe signal. The measurement results are monitored with low frequency output by using dividers and the embedded pattern generator. The advantage of this low cost approach is that it does not require ATE to access high frequency signals for testing. Monte Carlo simulations are performed to verify the circuit operations, and the experimental results show the measurement of I/O parameters for a 1.6Gbps memory system.

This paper presents an efficient test framework to extend a use of low-cost ATE (Automatic Test Equipment) to at-speed test of high-speed DUT (Device Under Test). To bridge the speed gap between the ATE and the DUT, an off-chip test interface circuit, called Built-off Test Interface (BOTI), has been developed. Unlike the previous methods which use on-chip or off-chip self-test circuits, in our method, the ATE plays main role in testing high-speed DUTs by actively controlling the BOTI operation, and monitoring the overall test procedure. This makes the presented method flexible to be applied to various test applications without compromising the test coverage. Also, since the BOTI is implemented off-chip, it does not require hardware modifications of the ATE or the DUT except the DUT load board to accommodate the BOTI module. To maintain reliable off-chip signal communication between the BOTI and the DUT, the BOTI measures off-chip channel skew and compensates the measured skew when communicating signals with the DUT. Currently, the BOTI is configured to do the at-speed test of high-speed memory. The measurement results are presented to validate the functionality of the BOTI, and the effectiveness of the presented test framework.

Semiconductor testing, aimed at detecting manufacturing defects and marginalities, should be able to screen out fabrication artifacts that affect immediate as well as future mission-mode device performance. While a large amount of resources are dedicated towards catastrophic fault detection, parametric fault detection is an increasingly important research area. Parametric faults marginally affect device performance and may affect functionality in prolonged field use. In this work, Circuit-under-test (CUT) static bias current is monitored in order to identify catastrophic as well as parametric defects. Any active circuit requires a deterministic amount of DC bias current which may vary outside the specifications when faults exist within the circuit. We propose a process-voltage-temperature (PVT) compensated current measurement built-in-self-test (BIST) scheme, which can be used for sub-system level/circuit-level bias current measurements. The BIST scheme provides better accessibility to internal blocks and enables isolated parametric testing. Process independence due to calibration makes it feasible for commercial implementation in Systems on a Chip (SoCs). Our BIST scheme is compatible with very-low-cost automatic test equipment (VLC-ATE), and can be used for detailed parametric testing in the production environment.

This paper presents a Built-In Self-Test (BIST) circuit for high speed I/O, based on an embedded pattern generator to remove external factors which could affect the I/O parameters. The rising and falling edge positions of the generated patterns can be controlled independently during every cycle. In the basic operation mode, ATE provides the codes for controlling the edge positions, while in extended mode, an embedded counter generates the control codes. The control of both rising and falling edges makes this scheme especially good for systems with Double-Data Rate (DDR) interfaces. Moreover, the cycle-by-cycle control allows us to analyze efficiently the influence of mismatch trees and per-pin skew on I/O performance. The proposed BIST circuit has been simulated using a 0.18-μm process.

This paper describes a delay measurement method using a shrinking clock signal. The shrinking clock is generated from an AND operation on two clock signals having slightly different periods, which are provided by an external tester. Instead of measuring the number of clocks before it vanishes, another AND operation is utilized to reduce the size of the counter. A differential approach is used to minimize the effect from any non-ideal behavior of circuits used for the measurement as well as to substitute for calibration. In the proposed method, the dynamic range, the measurement resolution and accuracy do not depend on the measurement circuit itself, but on the external clocks from the tester. Circuit-level simulations show good linearity and measurement accuracy regardless of process, voltage, and temperature (PVT) variations when the edge placement accuracy of the external tester amounts to 100ps.

Due to process variation, power-up values of embedded SRAM memory are unique for individual devices. They are used as SRAM fingerprints to identify integrated-circuits which is fundamental for security applications. The fingerprints, however, are sensitive to environmental changes. Consequently, during the identification process, errors may occur. To overcome this inherent nondeterminism, we provide a systematic approach to designing reliable SRAM-based identification system. We also discuss how to evaluate its system performance. We present a generic score-fusion-based matching recipe to identify devices with high confidence across a wide range of environmental conditions.

Effective and meaningful visualization techniques are quite important for multidimensional DNA microarray gene expression data analysis. Elucidating the cluster properties of these multidimensional data are often complex. Patterns, hypotheses on the relationships, and ultimately of the function of the gene can be analyzed and visualized by non-linear reduction of the multidimensional data to a lower dimension. In this paper, an improved SOM visualization technique named Improved Side Intensity Modulated (ISIM) Self-Organizing Map (SOM) has been proposed and compared with other SOM based visualization techniques. On different datasets, ISIM-SOM is found to offer better cluster boundary, simplicity and clarity.

This paper presents a built-in self repair analyzer with the optimal repair rate for embedded memory arrays. The proposed method requires only a single test, even in the worst case. By performing the must-repair analysis on the fly during the test, it selectively stores fault addresses, and the final analysis to find a solution is performed on the stored fault addresses. To enumerate all possible solutions, existing techniques use depth first search using a stack and a FSM. Instead, we propose a new algorithm and its combinational circuit implementation. Since our formulation for the circuit allows us to use the parallel prefix algorithm, it can be configured in various ways to meet area and test time requirements. The total area of our infrastructure is dominated by the number of CAM entries to store the fault addresses, and it only grows quadratically with respect to the number of repair elements.

This paper presents a new method for testing radio frequency (RF) receivers that utilizes a multitone digital signal generation scheme and relies on the analysis of the receiver baseband output to compute the RF performance parameters. The proposed method takes out the cost of expensive RF instrumentation on the input side of receiver testing and only requires the less expensive baseband digitization at the receiver output. The complexity of the RF signal generation inherent to standard methods is traded off with extensive signal processing on the baseband side, with the tedious analysis necessary for tackling the problem being addressed and presented herein. While the proposed test scheme was implemented and experimentally verified on a load board for testing UHF receivers, generalized use in BIST applications in need of multi-GHz RF stimuli is also discussed in the paper. RF performance parameters like Gain, Noise Figure (NF), and IIP3 were measured using both standard methods and the proposed method and, the results are shown to be accurate.

This paper describes a RMS value measurement technique for random jitter. A jittery clock signal is combined with a reference clock signal using an OR operation and an AND operation in sequence, and the pulse width outputs modulated by the amount of the random jitter are used to charge or discharge a capacitor. The voltage at the capacitor, in turn, modulates the frequency of VCO having a current-starved inverter, and whose frequency difference from the OR operation and the AND operation is used in calculating the RMS value of the random jitter. Circuit-level simulations show the validity of the proposed technique for up to 20% peak-to-peak jitter in the clock even with process variations. The proposed technique can be applied to BIST solutions for random jitter measurement on a transmitted clock signal.

This paper presents an efficient pseudorandom (PR) test method to characterize the performance of nonlinear analog and mixed-signal (AMS) circuits including those embedded in SoC devices. Previous applications of the PR test method to BIST have been limited to digital and linear analog circuits. In this paper, we extend the application of PR test to nonlinear AMS circuits. In doing so, we reduce the cost of testing nonlinear circuits, and increase the test coverage of embedded AMS circuits without incurring a large area overhead to accommodate a test stimulus generator. Our method maintains good test accuracy by using a Volterra series model to describe the behavior of the device under test (DUT). A PR sequence generated from a simple LFSR is used to excite the DUTs over a wide range of frequencies and estimate the parameters of the Volterra series, which are then used to predict the performance of DUTs. We present a method to reduce the test time by using a compressed cross-correlation method which reduces the complexity of the presented algorithm. The mathematical background and hardware measurement results are presented to validate our method.

Skew calibration and compensation are critical ATE features for reliable functional test, particularly for applications such as memory chips. This paper presents a new Time-to-Digital Converter (TDC) design for off-chip skew calibration from Time Domain Reflectometry (TDR)measurements. It consists of coarse and fine parts which enable the circuit to detect a large skew range with high resolution. Circuit complexity is reduced through use of the proposed automatic edge detection methods which control coarse/fine operations. We also present skew compensation circuits which can de-skew off-chip signals based on the skew calibration. The TDC occupies a small area, making it suitable for implementation in a Built-Off Test (BOT) chip.The circuits were implemented using a 130nm technology in a Built-Off Test Interface (BOTI) developed for 800Mbps DDR2 memory functional test.

Identifying the set of real critical paths of a circuit is an important step in delay testing. Since path delays are vector dependent, the set of critical paths selected depends on the vectors assumed when estimating the path delays. To find the real critical paths, it is important to consider the effect of dynamic (vector dependent) delay effects such as coupling noise, supply noise etc. during path selection. In this work a methodology to incorporate the effect of coupling noise during path selection is described. For any given path, both logic and timing constraints are extracted and a constrained optimization problem is formulated to estimate the maximum path delay in the presence of coupling noise.

This paper shows that a timing graph has a hierarchy of specially defined subgraphs, based on which we present a technique that captures topological correlation in arbitrary block-based statistical static timing analysis (SSTA). We interpret a timing graph as an algebraic expression made up of addition and maximum operators. We define the division operation on the expression and propose algorithms that modify factors in the expression without expansion. As a result, they produce an expression to derive the latest arrival time with better accuracy in SSTA. Existing techniques handling reconvergent fanouts usually use dependency lists, requiring quadratic space complexity. Instead, the proposed technique has linear space complexity by using a new directed acyclic graph search algorithm. Our results show that it outperforms an existing technique in speed and memory usage with comparable accuracy.

A novel technique for implementing very high speed FFTs based on unrolled CORDIC structures is proposed in this paper. There has been a lot of research in the area of FFT algorithm implementation; most of the research is focused on reduction of the computational complexity by selection and efficient decomposition of the FFT algorithm. However there has not been much research on using the CORDIC structures for FFT implementations, especially for large, high speed and high throughput FFT transforms, due to the recursive nature of the CORDIC algorithms. The key ideas in this paper are replacing the sine and cosine twiddle factors in the conventional FFT architecture by non-iterative CORDIC micro-rotations which allow substantial (~ 50%) reduction in read-only memory (ROM) table size, and total removal of complex multipliers. A new method to derive the optimal unrolling/unfolding factor for a desired FFT application based on the MSE (mean square error) is also proposed in this paper. Implemented on a Virtex-4 FPGA, the CORDIC based FFT runs 3.9 times faster and occupies 37% less area than an equivalent complex multiplier-based FFT implementation.

There has been ongoing debate regarding the use of voltage overscaling along with error resilience techniques for ultra low power operation of scaled CMOS logic. The issue is whether to build enough design margin into future electronic systems so that errors do not impact the Quality of Service of the end application or to allow errors to occur and correct them using error tolerance mechanisms. Specific signal processing algorithms have been shown to be inherently tolerant to errors. However, large general purpose processors experience virtually zero errors under supply voltage scaling up to a certain scaling level and then exhibit “massive errors” or “complete breakdown”. The problem is made worse by the fact that low power design methodologies force devices to be sized in such a way as to make a large number of circuit paths “critical”. Under all of the above constraints, what is the best way to build low power systems of the future using deeply scaled CMOS technologies? Is the use of voltage overscaling along with error resilience techniques realistic? Can we allow errors to occur and compensate for them with high confidence? Under what conditions will design guardbanding be absolutely necessary? If we do let errors occur periodically, will customers buy the associated products and is there a marketplace for such error-resilient ICs?

Discrete Wavelet transform is a powerful mathematics technique which is being adopted in different applications including physics, image processing, biomedical signal processing, and communication. Due to its pipelined structure and multirate processing requirements, a single numerical error in one stage can easily affect multiple outputs in final result. In this paper, we propose a weighted checksum code based fault tolerance technique for 2-D discrete wavelet transform. The technique encodes the input array at the 2-D discrete wavelet transform algorithm level, and algorithms are designed to operate on encoded data and produce encoded output data. The proposed encoding technique can perfectly fit into the lifting structure and existing general purpose 2-D discrete wavelet lifting VLSI architectures, without significant modification and overhead. We present the mathematics proof of this coding technique and show this technique can detect the errors in 2-D wavelet transforms. The hardware overhead using this technique is significantly lower than existing methods.

The cost of testing mixed signal circuitry with conventional analog-stimulus is significantly higher than digital circuitry due to higher cost automatic test equipment (ATE) required for generation of analog stimulus. Multiple variants of low cost testers have been developed for digital testing which rely on relaxed timing, power or tester channel requirements to lower hardware cost. Systems containing mixed-signal/RF components can thus not be tested on such ATE due to the cost and limitations of analog/RF stimulus and measurement modules. This paper proposes a hybrid BIST scheme for analog to digital converters (ADCs) to enable full production-quality testing with low cost ATE. The two major challenges addressed are generating the input stimulus, and a fully functional at-speed test to maintain the test quality of a pure analog ATE solution.

As the supply voltage shrinks with technology scaling, the slightest drop in the voltage level has a significant impact on chip functionality. It is, therefore, important to accurately measure supply voltage noise to evaluate the actual IR drop on-chip and to feed the results to a power management unit, which can scale the voltage and perform on-chip compensation based on the IR drop. In this paper, we propose a detection scheme based on a ring oscillator, which can detect and evaluate static IR drop on-chip with minimal additional area and design complexity.

This paper presents a new path selection algorithm for delay fault testing in a statistical timing framework. Existing algorithms which consider correlation between paths use an iterative process for each path or defect and require a Monte Carlo simulation for each iteration to calculate the conditional fault probability. The proposed algorithm does not require the iteration process and selects a requested number of paths simultaneously once it performs a statistical timing analysis at the beginning. If selection of k paths is required in a set of paths, it partitions the set into two path sets and determines how many paths should be selected in each path set out of the k paths. It recursively continues this process and ends up with k paths. The partitioning is easily performed during the recursive traversal of a circuit, which produces an imaginary path tree, where paths are already grouped based on their prefix. Experimental results show the proposed algorithm can effectively use structural correlation and spatial correlation to generate high quality path sets.

This paper develops a technique, using a built-in detector, for measuring the specifications of RF subsystems and fine-tuning them with a feedback control algorithm. At the same time, optimum power consumption points can be chosen from different biasing schemes. The detector has small area overhead with low frequency output. The sampled output waveform is analyzed using an FFT. The low frequency measurements are directly used to calculate the circuit specifications, without requiring learning steps. The technique was used to measure the performance parameters of a 940 MHz to 40 MHz down conversion mixer in a RF receiver front-end test chip, fabricated in a commercial 0.18 mum CMOS process. The tuning algorithm was implemented in the Labview environment, and tuning knobs on board were used for biasing and control optimization. Results show that the approach can provide accurate calibration of specifications and power for real RF chips.

The timing models used in current Static Timing Analysis tools use gate delays only for single input switching events. It is well known that the temporal proximity of signals arriving at different inputs causes significant variation in the gate delay. This variation in delay affects the accuracy of our timing estimates. In this paper, we derive simple analytical models for incorporating the effect of simultaneous multiple input switching events on gate delay. The model presented requires minimum additional characterization effort, and can be employed in a statistical timing engine. The dynamic delay variability of a path caused by MIS noise can be accurately estimated using the proposed model.

CMOS has been the dominant integrated circuit (IC) technology for nearly four decades, following the trends predicted by Moore's Law, and fueling the information and communication revolution. As chip geometries decrease and transistor densities increase, new types of faults - from manufacturing defects and operational transients to long- term wearout - need to be addressed. These faults and the resulting logic errors have been dealt with at both the low and high levels of the design. This talk deals with approaches for improving dependability at the system level.

The paper presents a panel discussion on the issues and challenges in dependable embedded system from both the academic and industrial perspectives. The panelists are Jacob Abraham from the University of Texas at Austin-USA, Stefan Poledna from TTTech-Austria, Avi Mendelson from Intel-Israel, and Subhasish Mitra from Stanford University-USA.

This paper presents a concurrent error detection technique targeted towards control logic in a processor with emphasis on low area overhead. Rather than detect all modeled transient faults, the technique selects faults which have a high probability of causing damage to the architectural state of the processor and protects the circuit against these faults. Fault detection is achieved through a series of assertions. Each assertion is an implication from inputs to the outputs of a combinational circuit. Fault simulation experiments performed on control logic modules of an industrial processor suggest that high reduction in damage causing faults can be achieved with a low overhead.

Jitter impairs the bit-error rate in high-speed communication systems. Jitter decomposition is important for accurately deriving the total jitter in a system and for aiding in identifying the root causes of jitter. We extend a previous approach for jitter decomposition in clock signals is to enable separation of correlated and uncorrelated jitter in both data and clock signals. We use time lag correlation functions with special test patterns to estimate the characteristic parameters of different jitter components such as peak-to-peak value of DDJ and RMS value of RJ. Our approach can be implemented using only one-shot capture instead of multiple captures to average out the uncorrelated jitter from the correlated jitter. Hardware measurements are presented to validate the proposed technique.

Identifying the set of real critical paths of a circuit is an important step in delay testing. Since path delays are vector dependent, the set of critical paths selected depends on the vectors assumed when estimating the path delays. To find the real critical paths, it is important to consider the effect of dynamic (vector dependent) delay effects such as coupling noise, supply noise etc. during path selection. In this work a methodology to incorporate the effect of coupling noise during path selection is described. For any given path, both logic and timing constraints are extracted and a constrained optimization problem is formulated to estimate the maximum path delay in the presence of coupling noise.

We present a technique that deals with the problem of efficiently generating instruction sequences to test for delay defects in a processor. These instruction sequences are loaded into the cache of a processor and the processor is run in its normal functional (native) mode to test itself. The methodology that we present avoids the significant increase in search space of a previous method while generating tests. We also present a technique which increases the probability of detecting multiple delay faults with a single instruction sequence. This technique can help immensely in reducing the cost of test. We demonstrate the effectiveness of our technique on an off-the shelf processor.

SRAMs typically represent half of the area and more than half of the transistors on a chip today. Variability increases as feature size decreases, and the impact of variability is especially pronounced on SRAMs since they make extensive use of minimum sized devices. Variability leads to a large amount of guard banding in the design phase in order to meet frequency and yield targets. We develop an SRAM architecture that eliminates guard banding. Specifically, our SRAM uses multiple supply voltages that are assigned post-manufacturing. We compensate for variation by powering up manufactured devices that are slower than designed. Specifically, we assign supply voltages to 6T cells on a per-column basis; this gives us sufficiently fine-grained control over devices without excessive area overhead. We show that post-manufacturing voltage assignment results in a 28% reduction in bitline energy compared to a fixed voltage design for the same yield using data from a real-world 45 nm process.

The problem of detection of control flow errors in software has been studied extensively in literature and many detection techniques have been proposed. These techniques typically have high memory and performance overheads and hence are unusable for real-time embedded systems which have tight memory and performance budgets. This paper presents two algorithms by which the overheads associated with any detection technique can be lowered by trading off fault coverage. These algorithms are generic and can be applied to any detection technique. They can be applied either individually or cumulatively. The algorithms are validated on a previously proposed detection technique using SPEC benchmark programs. Fault injection experiments suggest that massive savings in overheads can be achieved using the algorithms with just a minor drop off in fault coverage.

The increasing gap between modern chip frequencies and test clock frequencies provided by external test equipment, makes at-speed delay testing a challenge. We present a novel technique to generate a capture signal on-chip, with programmable delay, which enables faster than at-speed test. The test clock frequency can be programmed as a part of the test vector itself. Since test clock frequency can be controlled, it is no longer required to depend only on the long paths for detecting small delay defects, which provides flexibility in selecting test paths. The technique has minimal overhead in terms of area and design effort and can be easily incorporated into the current scan based delay test methods.

Time interleaved A/D converters (TIADCs) provide an attractive solution to the realization of analog front ends in high speed communication systems. However, gain mismatch, offset mismatch, and sampling time mismatch between time-interleaved channels limit the performance of TIADCs. This paper presents a low-cost test scheme to measure timing mismatch using an undersampling clock. Our method is applicable to an arbitrary number of channels, achieving picosecond resolution with low power consumption. Both simulation and hardware measurements are presented to validate the proposed technique.

Accurate measurement of sub-picosecond aperture jitter when testing state-of-the-art high-speed, high-resolution data converters is a difficult problem, since there is no systematic method of precisely separating aperture jitter from input and clock jitter components as well as additive noise. In addition, it is more difficult to implement Built-in Self-test (BIST) schemes for accurately measuring aperture jitter based on a low cost approach, since jitter-induced noise present in the Device Under Test (DUT) degrades the performance of the Design for Test (DfT) circuitry as well as the DUT. These problems result in low test accuracy and serious yield loss. This paper presents a novel methodology for accurate prediction of aperture jitter using a cost-effective loopback methodology. Aperture jitter is precisely separated from input and clock jitter as well as additive noise present in the DUT, by using an efficient loopback scheme along with spectral characteristic equations. Hardware measurement results show that this approach can be effectively used to predict the aperture jitter of a DUT, with a significant reduction in the prediction error compared with previous approaches.

Parallel testing of mixed-signal circuits has been considered a difficult task due to the limited resources in generating and analyzing multiple analog signals. A number of methods have been proposed to perform parallel testing of mixed-signal circuits using built-in test circuitry; however, these techniques are vulnerable to fault masking issues which may degrade the test accuracy. This paper presents an efficient parallel test algorithm for mixed-signal circuits based on a loopback test method. Multiple DUTs (devices under test) are loopbacked externally on a loadboard which is loaded with a simple analog adder and an RMS detector. The performance parameters of each DUT are calculated separately from the composite responses, while removing the effect of fault masking. Parallelism is increased by sharing common test equipment and a DUT loadboard among the multiple DUTs. The mathematical theory and simulation results are presented to validate our algorithm.

This paper describes the theory and chip measurements of a built-in test technique for RF receivers which uses simple RF amplitude detectors. The method has been used to measure the performance parameters of a 940 MHz RF receiver front-end with a mixer and LNA. The detector has small area overhead with low frequency output. The sampled output waveform is analyzed using an FFT, and the low frequency measurements are used to deduce the conversion gain and Third Order Intercept point (TOI, IIP3) of the receiver. A test chip was fabricated in a commercial 0.18 mum CMOS process. By using two detectors, both the system performance and specifications of discrete components have been accurately measured. Measurement results show accurate prediction of system and component specifications.

We present a technique for generating instruction sequences to test a processor functionally. We target delay defects with this technique using an ATPG engine to generate delay tests locally, a verification engine to map the tests globally, and a feedback mechanism that makes the entire procedure faster. We demonstrate nearly 96% coverage of delay faults with the instruction sequences generated. These instruction sequences can be loaded into the cache to test the processor functionally.

Design complexity is increasing with every technology generation, causing verification tools to require large amounts of resources. In this paper, we develop a technique to reduce the complexity of verifying digital designs described in a Hardware Description Language (HDL). For a given property to be verified, we derive an HDL executable design slice that is behaviorally equivalent to the original design. The slice is less complex than the original design and requires fewer resources for analysis by a verification tool. The slicer is implemented as a pre-processor to SMV, a SAT-based verification tool, and Formal, an ATPG-based verification tool. Experimental results on the USB2.0 IP core show that RTL slicing reduces both CPU and memory overhead for both SMV and Formal. This reduction allows the verification tools to effectively deal with complex designs.

Accurately estimating critical path delays is extremely important for yield optimization and for path selection in delay testing. It is well known that dynamic effects such ascoupling noise can significantly affect critical path delays. In traditional static timing analysis, the coupling effect isincorporated by estimating the switching window overlaps between aggressor and victim and then assuming a constant (worst case) coupling factor if any overlap is present. However in path based statistical timing analysis, using a constant coupling factor can overestimate the mean delay while under estimating the delay variance. In this paper, we propose a technique to estimate the dynamic variation in pathdelay caused by coupling noise. We treat the effective coupling capacitance as a random variable that varies as a function of the relative signal arrival times between victim andaggressor nodes. A modeling technique to estimate the capacitance variation is shown and a framework that gives therelative signal arrival time distribution at the victim nodesis developed.

Detection of control-flow errors at the software level has been studied extensively in the literature. However, there has not been any published work that attempts to correct these errors. Low-cost correction of CFEs is important for real-time systems where checkpointing is too expensive or impossible. This paper presents automatic correction of control-flow errors (ACCE), an efficient error correction algorithm involving addition of redundant code to the program. ACCE has been implemented by modifying GCC, a widely used C compiler, and performance measurements show that the overhead is very low. Fault injection experiments on SPEC and MiBench benchmark programs compiled with ACCE show that the correct output is produced with high probability and that CFEs are corrected with a latency of a few hundred instructions.

Loopback tests for a differential mixed-signal device under test (DUT) have rarely been attempted, since any imbalance introduced by a design for test (DfT) circuitry on differential signaling delivers an imperfect sinusoidal wave to the DUT input, thereby degrading the DUT performance. In addition, this methodology inherently suffers from fault masking. These problems result in low test accuracy and serious yield loss. This paper presents a novel methodology for efficient prediction of individual DUT dynamic performance parameters with a radio-frequency (RF) transformer in loopback mode to overcome the imbalance problem of DfT circuitry. Cascaded RF transformer in loopback mode produces differently weighted loopback responses, which are used to characterize the DUT dynamic performance. Hardware measurement results show that this approach can be effectively used to predict the specifications of a DUT.

This paper presents a novel technique for proving the correctness of arithmetic circuit designs described at the register transfer level (RTL). The technique begins with the automatic translation of circuits from a Verilog RTL description into a term rewriting system (TRS). We prove the correctness of the designs via an equivalence proof between TRSs for the implementation circuit design and a much simpler specification circuit design. We present this notion of equivalence between the TRSs and a stepwise refinement method for its decomposition, which we leverage in our tool Verifire. We demonstrate the effectiveness of our technique by using the tool for the verification of several multiplier designs that have hitherto been impossible to verify with existing approaches and tools.

It is important to separate random jitter from deterministic jitter to quantify their contributions to the total jitter. This paper identifies the limitations of the existing methodologies for jitter decomposition, and develops a new and efficient approach using time lag correlation functions to decompose different jitter components. The theory of the approach is developed and it is applied to a ring oscillator simulated in a 0.6-mum AMI CMOS process. Results show good agreement between the theory and Hspice simulation

This paper presents a new built-in self test (BIST) method based on efficient digital equalization and spectral prediction techniques. The method enables accurate built-in characterization of the static performance parameters of data converters, and thus test and calibration costs can be significantly alleviated. Based on recent work on dynamic performance parameter characterization using a loopback test, the transfer function of a DAC in loopback mode is estimated with a spectral prediction technique and Chebyshev polynomials. A digital equalizer is designed to compensate for the non-linearity of the DAC in the pre-conversion stage, hence the ADC can be tested with the digitally calibrated analog signals. The digital equalizer overcomes accuracy limitations encountered in a traditional compensation technique, and thus a standard histogram test which may suffer from INL masking problems can be successfully applied. Simulation results are presented to validate the technique

We propose instruction-driven slicing, a technique for annotating microprocessor descriptions at the register transfer level (RTL) in order to achieve lower power dissipation. Our technique automatically annotates existing RTL code to optimize the circuit for lowering power dissipated by switching activity. Our technique can be applied at the architectural level as well, achieving similar power gains. We demonstrate our technique on architectural and RTL models of a 32-bit OpenRISC processor (OR1200), showing power gains for the SPEC2000 benchmarks

Accurate generation of circuit specifications from test signatures is a difficult problem, since analytical expressions cannot precisely describe the nonlinear relationships between signatures and specification. In addition, it is difficult to precisely control physical factors in Built-in Self-test (BIST) circuitry, which can cause errors in the signatures. This paper presents a novel methodology for efficient prediction of circuit specifications with optimized signatures. The proposed Optimized Signature Based Alternate Test (OSBAT) methodology accurately predicts the specifications of a DUT using a strong correlation mapping function. Hardware measurement results show that this approach can be effectively used to predict the specifications of a DUT, with a significant reduction in the prediction error compared with previous approaches.

This paper presents an efficient software technique, control flow error detection through assertions (CEDA), for online detection of control flow errors. Extra instructions are automatically embedded into the program at compile time to continuously update run-time signatures and to compare them against pre-assigned values. The novel method of computing run-time signatures results in a huge reduction in the performance overhead, as well as the ability to deal with complex programs and the capability to detect subtle control flow errors. The widely used C compiler, GCC, has been modified to implement CEDA, and the SPEC benchmark programs were used as the target to compare with earlier techniques. Fault injection experiments were used to evaluate the fault detection capabilities. Based on a new comparison metric, method efficiency, which takes into account both error coverage and performance overhead, CEDA is found to be much better than previously proposed methods

Testing a processor in native mode by executing instructions from cache has been shown to be very effective in discovering defective chips. In previous work, we showed an efficient technique for generating instruction sequences targeting specific faults. We generated tests using traditional techniques at the module level and then mapped them to instruction sequences using novel methods. However, in that technique, the propagation of module test responses to primary outputs was not automated. In this paper, we present the algorithm and experimental results for a technique which automates the functional propagation of module level test responses. This technique models the propagation requirement as a Boolean difference problem and uses a bounded model checking engine to perform the instruction mapping. We use a register transfer level (RT-Level) abstraction which makes it possible to express Boolean difference as a succinct linear time logic (LTL) formula that can be passed to a bounded model checking engine. This technique fully automates the process of mapping module level test sequences to instruction sequences

The size of the hardware description model for a complex modern digital system is increasing rapidly. CAD tools used to analyze these models are challenged by this increase in model complexity. This paper presents a technique that extracts for a given set of variables, a smaller HDL executable design slice that includes all the behavioral elements that affect those variables directly or indirectly. The design slice when compiled produces a behavior for the set of variables equivalent to the one computed by the original unsliced design. ATPG and verification tools analyzing this design could use the sliced model to reduce computation overhead. This technique was implemented in a computer program and evaluated its impact on the bounded model checker, SMV. Results show a reduction for both CPU time and memory needed by SMV to verify a publicly available model of the USB 2.0 IP core

This paper presents a new low-cost fault diagnosis technique based on built-in self test (BIST). The method enables rapid and accurate identification of weak spots in a design and potential problems in the manufacturing process, thereby leading to a significant reduction in time-to-market. Fault diagnosis is accelerated with available on-chip BIST which can generate low-cost signatures (performance parameters). Imperfect signatures due to limited on-chip resources and accuracy are compensated in two ways. Supplemental signatures are obtained from a re-configured device under test (DUT) by parameter tuning, leading to improvements in diagnosability. Secondly, diagnosis accuracy is significantly improved by using an ensemble method which has been widely used in data mining. The technique can be used to identify single as well as multiple faults, and can also be used to facilitate a self-repair mechanism by accurately identifying the source of errors. Simulation results are presented to validate the technique

Sequential equivalence checking between system level descriptions of designs and their register transfer level (RTL) implementations is a very challenging and important problem in the context of systems on a chip (SoCs). We propose a technique to alleviate the complexity of the equivalence checking problem, by efficiently decomposing it using compare points. Traditionally, equivalence checking techniques use nominal or functional mapping of latches as compare points. Since we operate at a level where design descriptions are in system level languages or hardware description languages, we leverage the information available to us at this level in deducing sequential compare points. Sequential compare points encapsulate the sequential behavior of designs and are obtained by statically analyzing the design descriptions. We decompose the design using sequential compare points and represent the design behavior at these compare points by symbolic expressions. We use a SAT solver to check the equivalence of the symbolic expressions. In order to demonstrate our technique, we present results on a non-trivial case study. We show an equivalence check between a SystemC description and two different Verilog RTL implementations of a Viterbi decoder, that is a component of the DRM SoC.

We present a novel technique for performing post-silicon timing characterization, i.e., delay fault test and debug, using on-chip delay measurement of critical paths in Integrated Circuits. In Deep Submicron technologies, timing related failures have become a major source of defective silicon, making it imperative to carry out efficient delay fault testing on such chips. In addition to test, there is also a need for an efficient and systematic silicon debug methodology for timing related failures. Existing timing characterization strategies are not effective in Deep Submicron technologies due to limitations on controllability and observability. The proposed technique uses a novel scheme to perform on-chip delay measurement and thus facilitate quick and efficient testing and debugging of delay faults in chips. The scheme has minimal hardware overhead and is robust in face of process variations.

Loopback testing of mixed-signal SOCs provides a low-cost test solution, but suffers from fault masking, resulting in serious yield loss and low test accuracy. This paper presents an efficient loopback test methodology which enables individual characterization of dynamic performance of devices under test (DUTs) in loopback mode. DUTs are loop-backed externally on a loadboard (DUT board), and a simple filter and an analog adder on the loadboard produce a composite loopback response. Characteristic parameters are extracted from these loopback responses, and a non-linear regression technique based on spectral predictors is used to predict various performance parameters such as Gain, SNR, THD and SINAD. The spectral predictor provides more accurate and reliable prediction compared to a time-domain approach. Both simulation and hardware measurements are presented to validate the proposed technique.

Bounded model checking based on sequential ATPG (automatic test pattern generation) is virtually the sequential ATPG state-justification phase. The state-justification phase is a very complicated and expensive process in term of CPU time. Previous work to speed the search concentrated on developing heuristics to achieve speed-up. In this paper we develop a novel architecture to emulate the state-justification on reconfigurable hardware. The feature of fine-grain massive parallelism of reconfigurable hardware is exploited to achieve speed-up.

This paper presents the ATPG performances of verifying USB2.0 IP core. Using the USB protocol and typical properties, the ATPG-based bounded model checking mechanism is revealed. Heuristics to accelerate the ATPG search are presented and their impacts are analyzed. We feel that results from this case study are applicable to serial communication circuits of the same family and can be scaled to industrial-sized circuits.

We propose novel design for test and debug techniques to apply two patterns for delay fault test and debug in dynamic circuits. Dynamic circuits, which have traditionally been difficult to test, pose new challenges for AC tests due to the presence of a reset phase between applications of any two patterns, which impedes delay fault testing of such circuits. We present two sets of design for test and debug techniques. The first set facilitates application of two patterns to dynamic circuits in general, overcoming the issue of reset phase, and reduces the problem of test generation for dynamic circuits to test generation for pull down paths of static CMOS circuits. The second set enables application of two patterns to scan based dynamic circuits. The proposed techniques reduce the problem of delay test generation for scan based dynamic circuits to that of delay test generation for static CMOS circuits with complete accessibility to all primary inputs. The techniques have minimal area overhead and also provide significant reduction in power during scan operation

Executing instructions from the cache has been shown to improve the defect coverage of real chips. However, although the faults detected by such tests can be determined, there has been no technique to target test generation for an undetected fault. This paper presents a novel technique to map pre-computed test sequences at the module level of a processor, to sequences of instructions. The module level pre-computed test sequence is translated into a temporal logic property and the negation of the property is passed to a bounded model checker. The model checker produces a counter-example for the temporal logic property. This counter-example trace contains the instruction sequence that can be applied at the primary inputs to produce the pre-computed test sequence at the module inputs. This technique has no restrictions on the type of test sequences, so it can be used to map test sequences for any kind of fault to processor instructions. It can also be used in the design phase to produce validation tests.

This paper describes a novel technique to reuse the existing scanpaths in a chip for delay fault testing and silicon debug. Efficient test and debug techniques for VLSI chips are indispensable in Deep Submicron technologies. A systematic debug scheme is also necessary in order to reduce time-to-market. Due to stringent timing requirements of modern chips, test and debug schemes have to be tailored for detection and debug of functional defects as well as delay faults quickly and efficiently. The proposed technique facilitates an efficient scheme for detecting and debugging delay faults and has minimal area and power overhead.

Our method extracts the linearity of on-chip high speed data converters with minimum area overhead. With a loop-back setup in the presence of noise, differential nonlinearities (DNLs) and integral nonlinearities (INLs) of analog-to-digital converters (ADCs) and digital-to-analog converters (DACs) can be extracted by the proposed method. Our approach exploits the fact that the loop-back output distribution due to noise is distorted by nonlinearities of the ADC, but not by those of the DAC. We first fully characterize the ADC in the loop-back system, exclusive of the DAC. Then, the DAC is characterized using the extracted nonlinearities of the ADC. Numerical simulation shows a maximum error of less than ±0.1 LSB for the ADC and the DAC.

Efficient test and debug techniques are indispensable for performance characterization of large complex integrated circuits in deep-submicron and nanometer technologies. Performance characterization of such chips requires on-chip hardware and efficient debug schemes in order to reduce time to market and ensure shipping of chips with lower defect levels. In this paper we present an on-chip scheme for delay fault detection and performance characterization. The proposed technique allows for accurate measurement of delays of speed paths for speed binning and facilitates a systematic and efficient test and debug scheme for delay faults. The area overhead associated with the proposed technique is very low.

This paper presents a new analog BIST scheme using a slope detection technique. In test mode, a circuit under test (CUT) is stimulated with a periodic rectangular pulse generated from a Linear Feed-Back Shift Register (LFSR) and a periodic invariant response is generated. The width of the pulse is a BIST parameter to allow a trade-off between test time and fault coverage. In order to maximize fault coverage and minimize the hardware overhead, we propose a slope detection technique which analyzes the response of CUT using a counter and a simple digital gate. Simulation results are presented to show the feasibility of this scheme.

We propose a novel design for testability technique to apply two pattern tests for path delay fault testing. Due to stringent timing requirements of deep-submicron VLSI chips, design-for-test schemes have to be tailored for detecting stuck-at as well as delay faults quickly and efficiently. Existing techniques such as enhanced scan add substantial hardware overhead, whereas techniques such as scan-shifting or functional justification make the test generation process complex and produce lower coverage for scan based designs as compared to non-scan designs. We exploit the characteristics of CMOS circuitry to enable the application of two-pattern tests. The proposed technique reduces the problem of path delay fault testing for scan based designs to that of path delay fault testing with complete accessibility to the combinational logic, and has minimal area overhead. The scheme also provides significant reduction in power during scan operation.

Oscillation based test (OBT) techniques in the past have focussed on detecting the existence of catastrophic and parametric faults. Recent work on predictive oscillation based test (POBT) has used OBT techniques to predict the performance parameters of the circuit under test (CUT). However, this technique cannot be used to predict the performance parameters of the CUT for process parameter variations that cause a loss of oscillation in test mode. This work presents a novel predictive quasi-oscillation based technique (PQOBT) to extend the usability of POBT over a wide range of process parameter variations with minimal test generation overhead.

Formal verification of systems-on-chips (SoCs) is an immense challenge to current industrial practice. Most existent formal verification techniques are extremely computation intensive and produce good results only when used on individual sub-components of SoCs. Without major modifications they are of little effectiveness in the SoC world. We attack the problem of SoC verification using an elegant abstraction mechanism, called computation slicing, and show that it enables effective temporal property verification on large designs. The technique targets a set of execution sequences, that is exhaustive with respect to an intended subset of system level properties, and automatically finds counter-example execution sequences in case of errors in the design. We have obtained exponential gains in reducing the global state space using a polynomial-time algorithm, and also applied a polynomial-time algorithm for checking global liveness and safety properties. We have successfully applied the technique to verify properties on two high level transaction based designs - the MSI cache coherence protocol and an admittedly academic SoC having a bus arbiter and a parameterizable number of devices connected to a PCI bus backbone.

Signatures used in low-cost schemes for testing analog and mixed-signal circuits do not directly represent or characterize the behavior of the device-under-test (DUT), since the lossy compression or complicated mathematical relations used can result in the loss of physical performance information. We develop a novel scheme where the signature is generated by built-in circuits based on a ternary signal representation (TSR), which represents the behavior of a signal with three levels, positive, zero, and negative. The signatures can be used directly to characterize DUTs or can be manipulated to obtain widely accepted dynamic performance parameters, such as SNR, THD, etc. Simulation results on a /spl Delta//spl Sigma/ DAC and a /spl Delta//spl Sigma/ ADC using TSR signatures through built-in circuits are presented to show the feasibility of the proposed method.

The use of functional vectors has been an industry standard for speed binning purposes of high performance ICs. This practice can be prohibitively expensive as the ICs become faster and more complex. In comparison, structural patterns can target performance related faults in a more systematic manner. To make structural testing an effective alternative to functional testing for speed binning, structural patterns need to correlate with functional test frequencies closely. We investigate the correlation between functional test frequency and that of various types of structural patterns on MPC7455, a Motorola processor executing to the PowerPC/spl trade/ instruction set architecture.

Oscillation based test (OBT) is a low-cost and vectorless test technique for analog and mixed-signal integrated circuits. Previous research with OBT has focused primarily on structural issues with an emphasis on fault detection rather than determining the conformance of the circuit under test (CUT) with its specifications, or evaluation of CUT performance. This paper presents a novel methodology for efficient interpretation of OBT results. The proposed predictive oscillation based test (POBT) methodology uses adaptive regression models to predict the performance parameters of the CUT from the oscillation measurements. Simulation results indicate that, under parametric variations, this methodology can determine CUT performance parameters, resulting in enhanced test effectiveness.

This paper presents an efficient approach to testing on-chip analog to digital converters (ADCs) and digital to analog converters (DACs) in loop-back mode. On-chip digital signal processing units can be used to generate stimuli. With this methodology, go/no-go tests as well as characterization of the individual ADCs and DACs are possible. The proposed approach is simple and overcomes the low parametric fault coverage of conventional loop-back tests. Simulations on a Matlab model of loop-backed converters are presented to validate the feasibility of the method.

The design and modeling of a high performance successive approximation analog-to-digital converter (ADC) using non-binary capacitor array are presented in this paper. A non-binary capacitor array with 20 capacitors is used to design a 16-bit, 1.5 mega samples per second (MSPS) successive approximation ADC. A perceptron learning rule, originally developed for Artificial Intelligence applications, is used as the capacitor calibration algorithm. The system architecture and the circuit design for the capacitor array, the sampling network and the high performance comparator are discussed. The capacitor weights are adaptively calibrated to match the physical capacitors with better than 22-bit accuracy. Capacitor matching is not a limiting factor to the accuracy. Various sources of noise, interference and distortion are modeled to evaluate their effects and to ensure the robustness of the calibration algorithm. This architecture is especially suitable for mixed-signal VLSI in the Nanometer Era because it relaxes the matching requirement on analog circuitry.

Fault tolerance requires the inclusion of redundant information. In this paper an on-line error detecting adder is presented in which the redundant information serves a dual purpose. It provides fault tolerance during the arithmetic operations while also providing a method by which addition is constrained to become a constant delay operation regardless of the word size of the operands.

We propose a DSP-based statistical self test approach for testing on-chip data converters. Analog to digital converters (ADCs) and digital to analog converters (DACs) can be tested in a loop-back mode, providing a go/no-go result; however such tests focus on catastrophic fault coverage. We develop a technique for testing converters in loop-back mode which is simple, but has good parametric as well as catastrophic fault coverage. We use the on-chip digital signal processing unit to generate test stimuli. The analysis of the results is done through the use of software on the DSP unit which is capable of monitoring primary inputs, outputs and/or internal nodes. Characterization of actual /spl Delta//spl Sigma/ converters was performed to show the feasibility of the proposed method.

A low-cost and comprehensive built-in self-test (BIST) methodology for analog and mixed-signal circuits is described. We implement a time-division multiplexing (TDM) comparator to analyze the response of a circuit under test with minimum hardware overhead. The TDM comparator scheme is an effective signature analyzer for on-chip analog response compaction and pass/fail decision. We apply this scheme to an oscillation-test environment and implement a low-cost and comprehensive vectorless BIST methodology for high fault and yield coverage. Our scheme allows a tolerance in the output response, a feature necessary for analog circuits. Both oscillation frequency and oscillation amplitude are measured indirectly to increase the fault coverage. We provide a theoretical analysis of the oscillation that explains why the amplitude measurement is essential. Simulation results demonstrate that the proposed scheme can significantly reduce test time of the oscillation-test while achieving higher fault coverage.

Systems-on-a-chip (SOCs) with many complex intellectual property cores require a large volume of data for manufacturing test. The computing power of the embedded processor in a SOC can be used to test the cores within the chip boundary, reducing the test time and memory requirements. This paper discusses techniques that use the computing power of the embedded processor in a more sophisticated way. The processor can generate and reuse random numbers to construct test patterns and selectively apply only those patterns that contribute to the fault coverage, significantly reducing the pattern generation time, the total number of test applications and, hence, the test time. It can also apply deterministic test patterns that have been compressed using the characteristics of the random patterns as well as those of the deterministic patterns themselves, which leads to high compression of test data. We compare three fast run-length coding schemes which are easily implemented and effective for test-data compression. We also demonstrate the effectiveness of the proposed approach by applying it to some benchmark circuits and by comparing it with other available techniques.

A well-known problem in timing verification of VLSI circuits using static timing analysis tools is the generation of false timing paths. This leads to a pessimistic estimation of the processor speed and wasted engineering effort spent optimizing unsensitizable paths. Earlier results have shown how ATPG techniques can be used to identify false paths efficiently [6],[9], as well as how to bridge the gap between the physical design on which the static timing analysis is based and the test view on which ATPG technique is applied to identify false paths [9]. In this paper, we will demonstrate efficient techniques to identify more false timing paths by utilizing information from an ordered list of timing paths according to the delay information. More than 10% of additional false timing paths out of the total timing paths analyzed are identified compared to earlier results on the MPC7455, a Motorola processor executing to the PowerPC™.

This paper develops an improved approach for hierarchical functional test generation for complex chips. In order to deal with the increasing, complexity of functional test generation, hierarchical approaches have been suggested wherein functional constraints are extracted for each module under test (MUT) within a design. These constraints describe a simplified ATPG view for the MUT and thereby speed up the test generation process. This paper develops an improved approach which applies this technique at deeper levels of hierarchy, so that effective tests can he developed for large designs with complex submodules. A tool called FACTOR (FunctionAl ConsTraint extractOR), which implements this methodology is described in this work. Results on the ARM design prove the effectiveness of FACTOR-ising large designs for test generation and testability analysis.

Many systems-on-a-chip (SOCs) include processors as central units to implement diverse algorithms and control peripheral units such as embedded cores. The computing power of the embedded processor can be used to self-test its own functions as well as to test the other cores within the chip boundary. In BIST methodology, pseudo-random pattern testing can reduce the memory requirements. In addition to general pseudo-random pattern testing, this paper proposes and evaluates a novel selective-random pattern test technique. This technique increases the fault coverage while significantly reducing test application time. This also greatly decreases the memory requirements compared to traditional BIST schemes. The cost for extra hardware is low and the technique is easily integrated with parallel scan and boundary scan designs.

This paper develops new techniques for detecting both stuck-open faults and resistive open faults, which result in increased delays along some paths. The improved detection of CMOS open defects is made possible by a new delay fault model which combines the advantages of the gate delay fault model and the path delay fault model. We develop a test generation methodology for this fault model which enables generation of test vectors that test a percentage of the longest sensitizable paths in the design and also test each net for spot defects through their longest sensitizable paths. Real delay values are used to determine the true critical paths in the circuit. The high degree of effectiveness of this fault model under realistic assumptions for process characteristics is first enumerated, and experimental results demonstrate the improved coverage possible with the proposed approach.

This paper develops a novel approach for formally verifying both safety and liveness properties of designs using sequential ATPG tools. The properties are automatically mapped into a monitor circuit with a target fault so that finding a test for the fault corresponds to formally establishing the property. The mapping of the properties to the monitor circuit is described in detail and the process is shown to be sound and complete. Experimental results show that the ATPG-based approach performs better than existing verification techniques, especially for large designs.

Systems-on-a-chip (SOCs) with many complex intellectual property (IP) cores require a large number of test patterns and a large volume of data. The computing power of the embedded processor in an SOC can be used to test the cores within the chip boundary, reducing the test time and memory requirements. This paper discusses techniques that use the computing power of the embedded processor in a more sophisticated way to significantly reduce memory requirements and the number of test applications, and hence the testing time. The processor can generate random patterns and selectively apply those patterns that contribute to the fault coverage. It can also apply deterministic test patterns that have been compressed using the characteristics of the random patterns as well as the deterministic patterns themselves. Fast run-length coding schemes which are easily implemented and effective for test data compression are described.

Equivalence checking between Register Transfer Level (RTL) descriptions and transistor level descriptions of custom memories is an important step in the design flow of high performance microprocessors. Equivalence checking can be done with or without the knowledge of state mapping between the two descriptions. We present evidence that because of state mapping, our verification technique exercises system behavior that exposes hard-to-detect bugs that might otherwise go undetected. This paper defines Crossover Bugs (CB's) that can be present in scan-based custom designs and that are inherently hard-to-detect without state mapping. We demonstrate that such bugs can be missed by equivalence checking techniques that do not have state mappings between the two descriptions. By identifying the state correspondences between the RTL and the transistor implementation of custom memories, a more rigorous equivalence check can be performed compared to traditional equivalence checking methods such as product machine constructions. We also compare the time and memory complexities of crossover bug detection capability of the two equivalence checking approaches. We conclude with experimental results of CB detection on some of the custom designed embedded memories of Motorola's MPC 7455 microprocessor (compliant with IBM's PowerPC instruction set architecture).

Sequential Automatic Test Pattern Generation (ATPG) is extremely computation intensive and produces good results only on relatively small designs. This paper develops an elegant theoretical basis, based on program slicing, for hierarchical ATPG which targets one module at a time and abstracts the rest of the design. The technique for obtaining a "constraint slice" for each embedded Module Under Test (MUT) within a design is described in detail. The technique has been incorporated in an automated tool for designs described in Verilog, and results on large benchmark circuits show the significant benefits of the approach.

Static timing anaylsis sets the industry standard in the design methodology of high speed/performance microprocessors to determine whether timing requirements have been met. Unfortunately, not all the paths identified using such analysis can be sensitized. This leads to a pessimistic estimation of the processor speed. Also, no amount of engineering effort spent on optimizing such paths can improve the timing performance of the chip. In the past we demonstrated initial results of how ATPG techniques can be used to identify false paths efficiently. Due to the gap between the physical design on which the static timing analysis of the chip is bused and the test view on which the ATPG techniques are applied to identify false paths, in many cases only sections of some of the paths in the full-chip were analyzed in our initial results. In this paper, we will fully analyze all the timing paths using the ATPG techniques, thus overcoming the gap between the testing and timing analysis techniques. This enables us to do false path identification at the full-chip level of the circuit. Results of applying our technique to the second generation G4 PowerPC/sup TM/ will be presented.

Article Causality based generation of directed test cases Share on Authors: Nina Saxena Comp. Eng. Res. Ctr., University Of Texas At Austin, Austin, TX Comp. Eng. Res. Ctr., University Of Texas At Austin, Austin, TXView Profile , Jacob Abraham Comp. Eng. Res. Ctr., University Of Texas At Austin, Austin, TX Comp. Eng. Res. Ctr., University Of Texas At Austin, Austin, TXView Profile , Avijit Saha IBM, Austin, 11400 Burnet Rd., Austin, TX IBM, Austin, 11400 Burnet Rd., Austin, TXView Profile Authors Info & Claims ASP-DAC '00: Proceedings of the 2000 Asia and South Pacific Design Automation ConferenceJanuary 2000 Pages 503–508https://doi.org/10.1145/368434.368771Online:28 January 2000Publication History 3citation183DownloadsMetricsTotal Citations3Total Downloads183Last 12 Months3Last 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

A new verification technique for /spl Delta//spl Sigma/ analog-to-digital converters (ADC) is proposed. The ADC is partitioned into functional blocks, and adaptive regression models for each partition are constructed using transistor-level simulation data. Non-idealities in circuit behavior are captured by the adaptive regression technique from the collected data. The algorithms have been implemented in a simulation program ARSIM (Adaptive Regression Simulator), which performs data sampling, model building, and simulation. Experimental results using ARSIM are shown on a second-order /spl Delta//spl Sigma/ modulator, and they demonstrate the effectiveness of our technique as a fast and accurate approach for verifying /spl Delta//spl Sigma/ converters.

This paper develops a novel technique which uses charge sharing as a method to perform addition in memory arrays. DRAM cells are conventionally used as storage elements and their data read through charge sharing. In our approach, DRAM cells are used as arithmetic units, thus saving area and power consumption in system-on-silicon applications. An adder in DRAM is designed, and its HSPICE simulation results are presented to show the viability of the proposed scheme.

This paper describes the use of Symbolic Trajectory Evaluation (STE), a modified form of symbolic simulation, to verify the equivalence between RTL and transistor-level representations of on-chip custom memories for the latest PowerPC microprocessor. The validation of embedded memories and their associated control logic poses a special problem for traditional formal equivalence checking tools due to the inherently sequential and self-timed nature of the internal control logic and the large number of state-holding elements. The use of the VERSYS STE engine to validate these custom memories is illustrated. We present our array verification methodology, discuss some of the results of our approach, and outline plans for future development.

We propose a comprehensive built-in self-test (BIST) methodology for analog and mixed-signal circuits. A time-division multiplexing (TDM) comparator scheme was proposed as an effective signature analyzer for on-chip analog response compaction and pass/fail decision with minimum hardware overhead. By applying this scheme to the oscillation-based test, the oscillation frequency can be measured indirectly as well as the oscillation amplitude to increase the fault coverage. The experimental results demonstrate that the proposed scheme can significantly reduce test time of the oscillation-based test with higher fault coverage.

We present a new algorithm for detecting both combinationally and sequentially false timing paths, one in which the constraints on a timing path are captured by justifying symbolic functions across latch boundaries.We have implemented the algorithm and we present, here, the results of using it to detect false timing paths on a recent PowerPC microprocessor design.We believe these are the first published results showing the extent of the false path problem in industry.Our results suggest that the reporting of false paths may be compromising the effectiveness of static timing analysis.

The Advanced VLIW architecture of the Equator MAP1000 processor has many features that present signif-icant verification challenges. We describe a functional ver-ification methodology to address this complexity. In par-ticular, we present an efficient method to generate directed assembly tests and a novel technique using the processor it-self to control self-tests and check the results at speed using native instructions only. We also describe the use of emula-tion in both pre-silicon and post-silicon verification stages. 1

As the sizes of general and special purpose processors increase rapidly, generating high quality manufacturing tests which can be run at native speeds is becoming a serious problem. One solution is a novel method for functional test generation in which a transformed module is built manually, and which embodies functional constraints described using virtual logic. Test generation is then performed on the transformed module using commercial tools and the transformed module patterns are translated back to the processor level. However, the technique is useful only if the virtual logic can be generated automatically. This paper describes an automatic functional constraint extraction algorithm and a procedure to build the transformed module. We describe the tool, FALCON, used to extract the functional constraints of a given embedded module fromaVerilog RTL model. The constraint extraction for embedded modules of benchmark processors using FALCON takes only a few seconds. We show that this method can generate functional patterns in a time several orders of magnitude less than one using a conventional, at view of the circuit. 1

We have developed a filter-based framework where several fundamentally different techniques can be combined to provide fully automated and efficient heuristic solutions to verification and possibly other NP-complete problems. Such an integrated methodology is far more robust and efficient than any single existing technique on a wide variety of circuits. Our methodology has been applied to verify the ISCAS 85 benchmark circuits and efficient verification results have been presented on a large set of industrial circuits which could not be verified using several published techniques and commercial verification tools available to us.

This paper introduces a novel framework to synthesize static CMOS circuits at the transistor level. A new class of binary decision diagrams (BDDs) which represent inverting Boolean functions, called transistor mapped BDDs (TM-BDDs), is used in the synthesis process. There is a one-to-one correspondence between a transistor netlist and its TM-BDD. Nodes in a TM-BDD represent gate inputs and the edges represent the transistors in the netlist. TM-BDDs can be optimized using BDD operations, and the data structure can retain device aspect ratios and geometries for performance optimization. The synthesis process involves a transformation from logic functions to transistor netlists using TM-BDDs. We show how a transistor netlist can be automatically generated during a depth-first traversal on a TM-BDD. The synthesis process is not only independent of any library, but also capable of generating a cell library for a particular circuit. Experimental results demonstrating the reduction of transistor counts are presented.

Only very small designs can be verified currently using property checking due to state-space explosion. Abstractions have been developed to simplify the design in an attempt to address this problem. However, the properties themselves may involve large state spaces, and practical property checking is generally confined to the control behavior. This paper describes an elegant technique for verifying properties of complex designs where the abstraction is applied to both the property and the design, thereby allowing us to verify properties which may deal with the data space. We demonstrate the technique on a processor by checking properties which are intractable using existing model checking techniques.

We present a method for constructing concrete executions or witnesses to abstract behaviour specifications. The key concept is the use of an ordering on states which preserves containment of behaviours seen from the states. We present a modified depth-first search algorithm which uses the ordering to prune the requisite search paths and the memory needed for the history of the search. We apply the search to a model of a superscalar pipeline.

It is argued that test and verification (validation) have a lot in common. The test problem is a (small) subset I of the verification problem. The concept of justification is useful for both problems. Practical formal Bbolean equivalence checking tools draw heavily on algorithms from the test field. ATPG techniqu~s are beginning to be applied to other verification problems. A VLSI design course should, therefore, emphasize both manufacturing test and design verification as necessary to produce a quality ptoduct, and these topics should comprise a significant part of the content of the course.

Dynamic circuit families are commonly used to achieve high operating speeds in recent microprocessor designs. Because of their noise sensitivity, it is necessary to design dynamic circuits accurately to achieve performance goals and avoid problems with noise. Although individual cells can be analyzed effectively, timing verification of the entire design is not easy because of the increased complexity. In this paper, we develop a new approach to find critical paths and generate test vectors for delay test of large dynamic circuits, given information on the path delays of the unit cells. We introduce the concept of "path gates" to represent the discharge paths in a dynamic circuit, and have developed an extraction tool (PEAR) to construct the path gates. The critical path analyzer (CRITIC) is used to identify the critical paths and generate delay tests for the integrated units. The technique has been successfully applied to industry circuits.

A new technique is proposed to analyze and compress the output responses from analog circuits. We first describe the subband filtering scheme to decompose responses from the analog circuit under test (CUT). A subband filter or wavelet takes the response, then generates the decomposed signals for each frequency band. The decomposed signal for each frequency band is fed into its respective integrator. Two kinds of wavelets are used to decompose the test response and effectively detect the faults in the circuit. Implementation issues including hardware overhead are also discussed.

This paper develops a new abstraction technique for processor microarchitecture validation. An abstract finite-state machine model is derived directly from the processor HDL description. This model, along with information about the instruction set, is used for validation coverage analysis. We also present automatic test generation algorithms for generating sequences for traversing state transition paths and covering snapshot and temporal events.

Combinational verification is a co-NP complete problem. However, in reality, several techniques exist which perform reasonably well on many practical circuits. Also, it is often found that while one technique efficiently verifies a given circuit it fails badly on another circuit, whereas a certain other technique is efficient on the latter circuit but cannot handle the former circuit. Therefore, clearly, a robust verification methodology cannot depend on any single technique. Our goal in this research is to build a verification methodology whose performance is more immune to circuit variations. We have developed a methodology where several fundamentally different techniques can be combined to provide efficient heuristic solutions to combinational verification, and possibly other intractable problems as well. Such an integrated methodology is far more robust and efficient on a majority of combinational verification problems than any single existing technique. In this paper, we discuss the methodology in detail and present verification results using a fully automated prototype of the proposed methodology. Using this methodology, we can verify many circuits which could not be efficiently verified using any published techniques available to us, and even by some popular commercial combinational verification programs.

This paper evaluates the concurrent error detection capabilities of system-level checks, using fault and error injection. The checks comprise application and system level mechanisms to detect control flow errors. We propose Enhanced Control-Flow Checking Using Assertions (ECCA). In ECCA, branch-free intervals (BFI) in a given high or intermediate level program are identified and the entry and exit points of the intervals are determined. BFls are then grouped into blocks, the size of which is determined through a performance/overhead analysis. The blocks are then fortified with preinserted assertions. For the high level ECCA, we describe an implementation of ECCA through a preprocessor that will automatically insert the necessary assertions into the program. Then, we describe the intermediate implementation possible through modifications made on gee to make it ECCA capable. The fault detection capabilities of the checks are evaluated both analytically and experimentally. Fault injection experiments are conducted using FERRARI to determine the fault coverage of the proposed techniques.

No abstract available.

In the past, hardware design validation has relied primarily on simulation. New techniques such as model checking have been introduced but no objective study investigating the advantages such techniques provide over simulation has been made. Simulation is model checking over a trace elicited by executing a test vector; model checking can be viewed as exhaustive simulation. Each has its own set of advantages and limitations. A platform, "Sherlock", was available wherein one could use properties or specifications expressed as CTL-like formulae interchangeably for checking simulation runs or for model checking. In this paper we describe and present results from an experimental study undertaken on a real implementation to better understand the efficacies of the two methods. We also present improved methods for accommodating liveness, fairness (of arbitration) and existence conditions in simulation and outline some techniques for writing implementation-independent properties for model checking.

We present methods for improving the effectiveness of random simulation using guides measured during the execution of a program. The key idea is to select inputs based on the measurement of the current state and judge input sequence effectiveness by analyzing the measured direction it induces. The process allows a set of test programs to be derived from a single guide by varying a random seed. We present some experimental results for an initial implementation.

New methodologies based on functional testing and built-in self-test can narrow the gap between necessary solutions and existing techniques for processor validation and testing. We present a versatile automatic functional test generation methodology for microprocessors. The generated assembly instruction sequences can be applied to both design validation and manufacturing test, especially in high speed "native" mode. All the functional capabilities of complex processors can be exercised, leading to high quality validation sequences and manufacturing tests with high fault coverage. The tests can also be applied in a built-in self-test fashion. Experimental results on two microprocessors show that this method is very effective in generating high quality manufacturing tests as well as in functional design validation.

As clock speeds of current deep submicron design technologies increase over 1 GHz and metal line spacings narrow, unexpected crosstalk effects start to degrade the circuit performance significantly. It is important for the designer to test the effects before taping out the designs. Unfortunately, conventional tests for stuck-at or delay faults are not guaranteed to expose potential crosstalk effects. This paper presents an efficient methodology for generating test vectors to detect crosstalk glitch effects in digital circuits. The ATEG (Automatic Test Extractor for Glitch) algorithm uses the multiple backrace technique, and uses a "forward-evaluation" technique in its backtacking phase which searches for the "right" entry to select by propagating "suggested values" to minimize the number of backtracks. In the glitch propagation phase, we employ a criterion function which gives a metric for determining the propagation of a transitional signal at a given gate. Our experiments show that ATEG efficiently generates test vectors to create glitches at candidate nodes.

Despite great advances in Formal Verification (FV) simulation is still the primary means for design validation. The definition of pragmatic measures for the coverage achieved and the problem of automatic test generation (ATG) are of great importance. In this paper we introduce a new set of metrics, the Event Sequence Coverage Metrics (ESCMs). Our approach is based on an automatic method to extract the control flow of a circuit which can be explored for coverage analysis and ATG. We combine FV and traditional ATPG techniques to automatically generate sequences which traverse uncovered parts of the control graph or exercise uninstantiated control event sequences.

The enormous state spaces which must be searched when verifying the correctness of, or generating tests for, complex circuits precludes the use of traditional approaches. Hard-to-find abstractions are often required to simplify the circuits and make the problems tractable. This paper presents a simple and automatic method to extract the control flow of a circuit so that the resulting state space can be explored for validation coverage analysis and automatic test generation. This control flow, capturing the essential "behavior" of the circuit, is represented as a finite state machine called the ECFM (Extracted Control Flow Machine). Simulation is currently the primary means of verifying large circuits, but the definition of a coverage measure for simulation vectors is an open problem. We define functional coverage as the amount of control behavior covered by the test suite. We then combine formal verification techniques, using BDDs as the underlying representation, with traditional ATPG techniques to automatically generate additional sequences which traverse uncovered parts of the control state graph. We also demonstrate how the same abstraction techniques can complement ATPG techniques when attacking hard-to-detect faults in the control part of the design for which conventional ATPG alone proves to be inadequate or inefficient at best. Results on large designs show significant improvement over conventional algorithms.

While the design of signature analyzers for digital circuits has been well researched in the past, signature analyzers for analog signals are relatively unknown. The primary difficulty in analyzing signatures for analog signals is that the latter are imprecise in nature. Therefore, deterministic signature analysis schemes, such as those based on finite-field arithmetic using linear feedback shift registers, are unsuitable for analog circuits. In this paper, a novel signature analysis scheme for analog and mixed signal circuits is proposed. The signatures possess the interesting property that if the input analog signal is imprecise within certain bounds (an inherent property of analog signals), then the generated signature is also imprecise within certain bounds. A failure is indicated by the generated signature being different from the expected signature by a margin greater than a predetermined threshold; the larger the effects of the failure, the larger the difference between the generated signature and the expected signature. The probabilities of aliasing and false rejection are also derived. Results for an example filter circuit are presented.

As the sizes of general and special purpose processors increase rapidly, generating high quality manufacturing tests for them is becoming a serious problem in industry. This paper describes a novel method for hierarchical functional test generation for processors which targets one embedded module at a time and uses commercial ATPG tools to derive tests for faults within the module. Applying the technique to benchmark processor designs, we were able to obtain test efficiencies for the embedded modules of the processors which were extremely close to what the commercial ATPG could do with complete access to the module. The hierarchical approach used produced this result, using the same commercial tool, but required a CPU time several orders of magnitude less than when using a conventional, flat view of the circuit.

Existing timing verification tools can provide methodologies for identifying and optimizing critical true paths in a embedded combinational module; however the problem of justifying these paths to the chip level is a very difficult one. This paper addresses the problem of timing verification at the entire chip level. We use a critical path tool, CRITIC, to obtain critical paths in an embedded combinational module. In order to reduce the complexity of checking whether the module-level critical path is indeed critical at the chip level, we use techniques from formal verification to extract the control behavior of the circuit, and check whether there is any control sequence which will justify the path to the chip level. The results of the experiments on several processor designs show that our approach is very effective in large sequential circuits such as microprocessors, where conventional ATPG techniques require inordinate amounts of CPU time. The experiments also show that the execution time remains reasonable as the circuit size increases, since we deal with a reduced control space rather than the entire state space of the circuit.

A new Boolean function representation scheme, the Indexed Binary Decision Diagram (IBDD), is proposed to provide a compact representation for functions whose Ordered Binary Decision Diagram (OBDD) representation is intractably large. We explain properties of IBDDs and present algorithms for constructing IBDDs from a given circuit. Practical and effective algorithms for satisfiability testing and equivalence checking of IBDDs, as well as their implementation results, are also presented. The results show that many functions, such as multipliers and the hidden-weighted-bit function, whose analysis is intractable using OBDDs, can be efficiently accomplished using IBDDs. We report efficient verification of Booth multipliers, as well as a practical strategy for polynomial time verification of some classes of unsigned array multipliers.

This paper addresses the problem of verifying the correctness of gate-level implementations of large synchronous sequential circuits with respect to their higher level specifications in a hardware description language (HDL). The verification strategy is to verify containment of the finite state machine (FSM) represented by the HDL description in the gate-level FSM by computing pairs of compatible states. This formulation of the verification problem dissociates the verification process from the specification of initial states, whose encoding may be unknown or obscured during optimization and also enables verification of reset circuitry. To make verification of large circuits with merged data path and control tractable, the concept of strong containment is introduced. This is a conservative approach which exploits correspondence between data path-registers in the two descriptions without requiring any correspondence between the control units. We also present an important result and associated proof that computation of pairs of equivalent or compatible states can be achieved by considering subsets of the circuit outputs. Consequently, verification of circuits with large and diverse input-output sets, which was previously intractable due to lack of a single effective variable order for the binary decision diagrams (BDD's), is now feasible. Experimental results are presented for the verification of several industry level circuits.

This paper presents a new mechanism for power analysis and reduction that exploits the hierarchical nature of circuits. A number of mechanisms have been proposed for power reduction, but they do not offer solutions in all cases. An activity-based reduction technique is presented where the clock is turned off for entire modules or sub-modules hierarchically when that portion of the circuit is not in use. Behavioral constraints are used to determine when a portion of the circuit is in use. The method shown is a top-down approach independent of the technology used during fabrication of the chip. Experimental results indicate that this method will result in a considerable reduction in power.

Logic and fault simulation are crucial steps in the design process for verifying the correctness of a circuit and generating high quality manufacturing tests. Traditionally, Intel has been relying on dedicated hardware accelerators to meet its fault grading needs. The unprecedented size and complexity of the Pentium/sup (R/)Pro microprocessor were foreseen to severely stretch the existing compute resources at Intel. Exploiting the design hierarchy and using the processing power of distributed computers were identified to be key areas which could alleviate the simulation problem. This paper describes a distributed mixed level logic and fault simulator that has been developed using an RTL simulation engine at the core, in conjunction with a gate level logic/fault simulator. The techniques and algorithm developed have been successfully applied on the Pentium/sup (R/)Pro microprocessor.

New approaches to address the difficult problems in test are necessary if its current status as a major bottleneck in the production of quality integrated circuits is to be changed. The authors propose a new direction for solving the test problem using powerful methods already employed for the formal verification of large circuits. More specifically, they discuss how abstraction techniques can assist conventional ATPG tools when attacking hard to detect faults. The same abstractions can also be used in design verification to increase the level of confidence in a design following simulation, by providing a meaningful measure of the coverage achieved by the verification vectors. In this sense, the authors' approach is geared toward providing a unified fled framework for design validation and manufacturing test.

In this paper we propose to use an output signal waveform analysis method called signal waveform integration for detection of stuck-at failures in combinational circuits. Non-robust tests are applied at-speed or faster to achieve high fault coverage, low test application time and detectability of redundant faults using directed random test generation techniques.

While analog test generation tools are still in their infancy, the corresponding tools in the digital domain have reached a fair degree of maturity and acceptance. Recognizing this fact, we propose a novel test generation method for linear analog circuits that employs well established digital test software to generate time-domain tests for analog parametric faults. We transform the analog circuit to an equivalent digital circuit, and target only those stuck-at faults in the digital circuit that could possibly capture parametric failures in the original analog circuit. Hence, the sequence of digital test vectors obtained from any test generator represents a test waveform for the analog parametric faults. The technique is illustrated using examples that show this to be a simple, yet attractive alternative to costlier simulation-based analog test generation approaches.

This paper presents a model which can be used to characterize the diagnosability of Algorithm-Based Fault Tolerant (ABFT) systems. In the model, the relationship between processors computing useful data, the output data, and the check processors is defined in terms of matrix entries. Necessary and sufficient conditions for detecting and locating faults in the processors are derived, and based on them, efficient algorithms to evaluate the fault detection and location capabilities of the system are developed.

This paper discusses a new approach for generating test vectors, using test cultivation, for both combinational and sequential VLSI circuits described hierarchically at the transistor, gate, and higher levels. The approach is based on continuous mutation of a given input sequence and on analyzing the mutated vectors for selecting the test set. The hierarchical technique used in the analysis drastically reduces the memory requirements, allowing test generation for large circuits. The test cultivation algorithms are simulation-based and a test set can be cultivated for any circuit that can be simulated logically. In particular, general MOS digital designs can be handled, and both stuck-at and transistor faults can be accurately modeled. Using the approach, tests were generated with very high fault coverage for gate-level circuits as well as for transistor level circuits.

This paper presents a new verification methodology to prove that a high level HDL description of a synchronous sequential circuit satisfies certain desired behavior or that it is free of certain malicious behavior. The correctness specifications are modeled as state machines with some transitions having unspecified inputs. We show that this suffices for specification of a large class of properties, including both safety and liveness properties. The properties are described as VHDL programs to enable the designer to simulate them for sample inputs and gain some measure of confidence in their correctness. Experimental results are presented for the Viper microprocessor.

Simulation is still the primary, although inadequate, resource for verifying the conformity of a design to its functional specification. Fortunately, most errors in the early stages of design involve only the control flow in the circuit. We define the functional coverage of a given sequence of verification vectors as the amount of control behavior exercised by them. We present a novel technique for automatically extracting the control flow of a design on the basis of the underlying mathematical model. Significantly, this extraction is independent of the circuit description style. The Extracted Control Flow Machine (ECFM) is then used for estimation of functional coverage and to provide information that will help the designer improve the quality of his or her tests.

With the introduction of complex analog designs the need to verify the circuit behavior completely and efficiently cannot be overemphasized. Recognizing the limitation of circuit simulation to achieve this goal, we present a novel approach based on formal techniques developed for digital circuits. Given a transfer function (specification) and its implementation using operational amplifier macro circuits, we verify the correctness of the transient behavior of the implementation over all possible input waveforms. Transforming the specification and the extracted state equations of the implementation from the s-domain to the Z-domain facilitates a digital representation in terms of adders, multipliers and delay elements. These two digitized circuits are then compared using techniques for checking compatibility of states in finite state machines. An example that illustrates the technique is presented.

A major step toward the development of fault-tolerant computer systems is the validation of the dependability properties of these systems. Fault/error injection has been recognized as a powerful approach to validate the fault tolerance mechanisms of a system and to obtain statistics on parameters such as coverages and latencies. This paper describes the methodology and guidelines for the design of flexible software based fault and error injection and presents a tool, FERRARI, that incorporates the techniques. The techniques used to emulate transient errors and permanent faults in software are described in detail. Experimental results are presented for several error detection techniques, and they demonstrate the effectiveness of the software-based error injection tool in evaluating the dependability properties of complex systems.>

No abstract available.

Automatic verification of implementations against their specifications in the design hierarchy is largely based on state machine comparison. This paper presents a simple technique that exploits information about correspondence between registers in the data path to enable abstraction of data path registers and make automatic verification of circuits with large date paths tractable. Correspondence between registers which encode the control states is not required. This generality enables efficient verification of large circuits with data paths structured differently, as well as verification against specifications devoid of structural information. Results are presented for the verification of realistic circuits at different levels in the design hierarchy.>

Introduces some new methods for estimating the "importance" of a variable in a Boolean function, and uses them to compute variable orders for OBDD construction. These measures are based on information theoretic criteria, and require the computation of the entropy of a variable in a given function. These entropy measures prove quite effective in distinguishing the importance of variables. Experimental results show this to be a very encouraging approach to help in the solution of this well known problem.>

This paper presents a technique for asynchronous logic design using ECDL (Enable/Disable CMOS Differential Logic). A pipelined serial-parallel multiplier clocked at 55.6 MHz has been designed to show the implementation of this technique. The serial-parallel multiplier architecture has been designed in ECDL using MAGIC, and circuit simulations have been done in HSPICE using a 2 /spl mu/m model from MOSIS. An evaluation of the area using ECDL is presented and compared against techniques used in the past to show that a significant reduction in area overhead is possible.>

While the design of signature analyzers for digital circuits has been well researched in the past, signature analyzers for analog signals are relatively unknown. In this paper, a novel signature analysis scheme for analog and mixed-signal circuits is proposed. The signatures possess the interesting properly that if the input analog signal is imprecise within certain bounds (an inherent property of analog signals), then the generated signature is also imprecise within certain bounds. A failure is indicated by the generated signature being different from the expected signature by a margin greater than a predetermined threshold.>

We consider the problem of validating a functional (architectural) timing model coded to predict instructions-per-cycle (IPC) performance for an advanced superscalar processor family. We present a methodology based on loop test cases for validating such models. For the purpose of this paper, we focus on two key strategies within our overall validation methodology: transient mode testing; and steady-state parametric testing. We state a few key lemmas characterizing the underlying theory and present a set of experimental results to illustrate the use of these validation strategies.>

Behavioral specification of a VLSI design can be used to suggest behavioral modifications that improve testability of the design. Past work has been targeted at identifying the techniques that will enable such modifications. However, the impact of such behavioral modifications on the testability of a design has not been analyzed with regards to fault coverage and area overhead which is the focus of this paper. Results obtained show that the area overhead is low and the fault coverage is higher when the behavior is modified for testability. These results are compared with the results obtained when partial scan is used to improve the testability of a design.>

With the anticipated growth of BiCMOS technology for high-performance ASIC design, the issue of testing takes on great significance. This paper addresses the testing of BiCMOS logic circuits. Since many different implementations of BiCMOS gates have been proposed, four representative ones are studied. The adequacy of stuck-at, quiescent current, and delay testing are examined based on circuit level faults. It is demonstrated that a large portion of the defects cannot be detected by common stuck-at or quiescent current tests since they manifest themselves as delay faults. By using the results presented, the test methodologies and the logic families can be ranked based on fault coverage. This ranking can then be used to help decide which BiCMOS solution is proper for a given application.>

Article Free Access Share on VIPER: an efficient vigorously sensitizable path extractor Authors: Hoon Chang View Profile , Jacob A. Abraham View Profile Authors Info & Claims DAC '93: Proceedings of the 30th international Design Automation ConferenceJuly 1993 Pages 112–117https://doi.org/10.1145/157485.158845Online:01 July 1993Publication History 38citation241DownloadsMetricsTotal Citations38Total Downloads241Last 12 Months3Last 6 weeks2 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 SiteeReaderPDF

This paper presents a novel test generation technique, called Selective Pseudo Scan (SPS), which incurs very low overhead. SPS uses a commercial combinational ATPG tool to generate tests with high fault coverage by reconfiguring sequential circuits to appear combinational without inserting scan. Results of applying SPS to several complex control blocks of a full custom RISC Microprocessor, demonstrate its superiority compared to traditional full scan or partial scan in a full custom design environment.

The areas of analog circuit fault simulation and test generation have not achieved the same degree of success as their digital counterparts owing to the difficulty in modeling the more complex analog behavior.We present a novel approach to this problem by mapping the circuit and circuit-level faults to the dis- crete domain.An efficient fault simulation is then performed on this discretized circuit for the given input test waveform.

Recognizing that specification testing of analog circuits involves a high cost and lacks any quantitative measure of the testing process, we adopt a fault-based technique. With the help of hierarchical fault models for parametric and catastrophic faults, and a very efficient fault simulator, our simulation-assisted technique automatically determines the test frequencies to detect AC faults in linear analog circuits. By a suitable choice of parameters in the test generator, we can either determine the best test (maximize the error between the good and the faulty responses) for every fault (resulting in a large test set), or generate the smallest test set for all the faults. Finally, fault coverage values provide a quantitative evaluation of the final test set.

This paper presents an efficient unified approach to mixed-signal fault simulation. A common fault simulation platform is developed for continuous valued analog circuits, discrete time switched-capacitor circuits and binary valued digital circuits, by discretizing the analog circuit, using discrete models of switched-capacitor circuits and complementing the stuck-at digital fault models with comprehensive behavioral analog fault models.>

The paper discusses techniques that help a designer to consider testability features early in the design cycle. The behavioral specification of a design is used to perform high level testability analysis, based on which behavioral modifications for testability are suggested to the designer. Results show that the overhead for incorporating these modifications is minimal.>

Error detection and error isolation are becoming stringent requirements for many computational problems requiring high reliability in addition to high performance. This paper presents CAPACETI, a technique for utilizing capabilities at the application level in order to achieve dependable operations. The proposed technique is further augmented with executable assertions and other software error detection techniques. The effectiveness of the techniques to detect errors, their contribution to the overall coverage, and their performance overhead were experimentally obtained using fault/error injection. Results obtained from these experiments show that high coverage with a low performance overhead can be achieved by selectively combining different error detection techniques.

An approach to modular and hierarchical sequential circuit test generation, which exploits a top-down design methodology, uses high level test knowledge and constraint driven module test generation to target faults at the structural level, is introduced in this paper. Results obtained for several designs are provided to demonstrate the effectiveness of our approach and the need for high level knowledge along with global constraints while deriving sequential circuit tests.>

Develops a synthesis-for-testability procedure wherein behavioral modeling techniques are used to generate testable designs. Knowledge about the accessibility of embedded modules is extracted from the behavioral design, analyzed, and any modification required subsequently incorporated in the behavioral design. Results show that when the resulting testable circuit is synthesized from this modified design using a high level synthesis tool, the overhead for testability is quite small, especially for large circuits.>

The authors define a general framework for the parallel simulation of digital systems and develop and evaluate tools for logic and fault simulation that have a good cost-performance ratio. They first review previous work and identify central issues. Then a high-level process model of parallel simulation is presented to clarify essential design choices. Algorithms for parallel logic and fault simulation of synchronous gate-level designs are introduced. The algorithms are based on a partitioning approach that reduces the number of necessary synchronizations between processors. A simple performance model characterizes the dependence on some crucial parameters. Experimental results for some large benchmarks are given, using prototype implementations for both message-passing and shared-memory machines.>

Given the increased availability of general purpose parallel computers two issues arise: One needs to compare the performance of the different available platforms using realistic examples, and it is necessary to write application software that can be ported easily in order to take advantage of different platforms. The authors address these issues from an applications point of view. They are interested in the use of general purpose parallel computers for simulation tasks needed during the design of very large scale integrated (VLSI) circuits. They characterize the simulation task as a useful benchmark and introduce a high level process view of parallel simulation that is helpful for deriving portable parallel programs. Details of the partitioning strategy and the simulation algorithm used in the application are given. They discuss their implementation on different parallel machines and give statistics of various experiments.>

A hierarchial testing approach for linear state variable digital systems based on matrix manipulation and constrained low-level test generation is reported. FEAST (functional extractor and sequential test generator) operates at the high level, where the circuit is described as an interconnection of arithmetic modules. CREST (constrained sequential test generator) operates at the low level description of the individual modules, and generates test sets satisfying constraints imposed by the high-level modules and their interconnection structure. The approach was found to perform better than automatic test generation at the gate level using existing algorithms for several large circuits.>

An approach to cultivating a test for combinational and sequential VLSI circuits described hierarchically at the transistor, gate, and higher levels is discussed. The approach is based on continuous mutation of a given input sequence and on analyzing the mutated vectors for selecting the test set. The approach uses a hierarchical simulation technique in the analysis to drastically reduce the memory requirement, thus allowing the test generation for large VLSI circuits. The algorithms are at the switch level so that general MOS digital designs can be handled, and both stuck-at and transistor faults are handled accurately. The approach was implemented in a hierarchical test generation system, CRIS, that runs under UNIX on SPARC workstations. CRIS was used successfully to generate tests with high fault coverage for large combinational and sequential circuits.>

Switch level simulation has been mapped to a distributed platform using a network of workstations. Model parallelism is used with preprocessing to partition the circuit to be simulated among the processors. A high-level pipelining scheme with multiple buffers is proposed to overcome the effects of a low-bandwidth network. Speedups of up to 4.1 with five processors have been obtained for medium sized ISCAS benchmark circuits. The speedups achieved using distributed simulation are very close to those obtained with the same switch-level simulator implemented on a shared-memory parallel machine.>

Presents a comprehensive approach, based on functional error characterization, for modeling faults in analog and mixed-signal circuits. A case study based on a CMOS and an nMOS operational amplifier is discussed, and a full listing of derived behavioral fault models is presented. These fault models are then mapped to the faulty behavior at the macro-circuit level.>

The analysis of fault-tolerant multiprocessor systems that use concurrent error detection (CED) schemes is much more difficult than the analysis of conventional fault-tolerant architectures. Various analytical techniques have been proposed to evaluate CED schemes deterministically. However, these approaches are based on worst-case assumptions related to the failure of system components. Often, the evaluation results do not reflect the actual fault tolerance capabilities of the system. A probabilistic approach to evaluate the fault detecting and locating capabilities of online checks. in a system is developed. The various probabilities associated with the checking schemes are identified and used in the framework of the matrix-based model. Based on these probabilistic matrices, estimates for the fault tolerance capabilities of various systems are derived analytically.>

The authors describe a number of heuristic algorithms to compact a set of test sequences generated by a sequential circuit automatic test pattern generator (ATPG). A model has been developed and analyzed which shows that finding the optimal solution has an exponential worst-case complexity. To achieve an acceptable run time, some heuristics have been developed that yield good suboptimal solutions in a very short time. Three heuristic algorithms were developed. These algorithms were implemented in C and lex and applied to several of the ISCAS-89 benchmark sequential circuits. They reduce the test length by 17%-63% with a very small time overhead, while having little effect on the original fault overage.>

Summary form only given. The author discusses fault tolerance techniques for computer systems, including a new technique, which he calls algorithm-based fault tolerance, for error detection and correction when computations are performed using multiple processor systems. The technique uses knowledge about the algorithm to reduce the amount of overhead necessary for fault tolerance. This is done by appropriately encoding the data and tailoring the algorithms to operate on the encoded data and produce encoded output data. Examples are given of applications including matrix operations, fast Fourier transforms, and computation of eigenvalues.>

The authors present a novel method for verifying the equivalence of two Boolean functions. Each function is hashed to an integer code by assigning random integer values to the input variables and evaluating its integer-valued representation. The equivalence of two functions can be verified with a very low probability of error. The probability of error can be exponentially decreased by making multiple runs. Results indicate significant time and space advantages for this method over deterministic techniques. Some functions known to require space (and time) exponential in the number of input variables for deterministic verification require only polynomial resources using the proposed technique.>

Event controlled pipelines (micropipelines) have several advantages over clocked pipelines as they offer modularity and speed independence. The concept of micropipelines can be easily applied to any linear pipeline. In practice, most pipelines include feedback loops and, therefore, are not as easy to control as linear pipelines. A novel interlocking scheme to solve the control flow problem is proposed. As an application, the design of a self-timed rebound sorter is considered where interlocking schemes are required to ensure proper operation of the pipeline. Similar interlocking schemes can be used for other pipelines with feedback.>

This paper presents an approach to developing high quality tests for switch-level circuits using both current. and logic test generation algorithms. Clear definitions for analyzing the effectiveness of the joint !,est generation approach are derived. Results on a set of switch-level circuits show very high coverage of stuickat, st,uck-on, and stuck-open faults when both current and logic tests are used.

A low cost deterministic fault simulation technique for practical ultra large scale integrated WSI) circuits, in a hardware accelerator environment is presented. A dynamic test directed partitioning scheme is implemented to select the faults which should be deterministically simulated for a given pattern. Experimental data show a speedup greater than an order of magnitude over conventionad fault simulation.

The authors present a novel approach to the test generation problem for a more general class of two-dimensional iterative logic arrays (ILAs) than considered by previous researchers. For certain ILAs it is possible to find a test set whose size remains fixed irrespective of the size of the ILA, while for others it varies with array size. Given an arbitrary ILA cell truth table and a cell interconnection structure, the goal is to determine if a fixed-size test can be found. If not, then a test set whose size grows as slowly as possible with the size of the array should be found. The authors propose a new model, called the n-cube of cell states model, for representing the cell truth table and interconnection structure. The test generation problem is shown to be related to certain properties of cycles in a set of graphs obtained from this model. By careful analysis of these cycles, efficient testing schedules can be obtained. The proposed technique can be applied to unilateral as well as regular bilateral ILAs in which the bilateral direction of signal flow are restricted to lie along the horizontal axis.>

We propose a general methodology to speed up the test generation process for circuits with high-level primitives. Our search procedure is a variation of depth first search that tries to fully exploit the capabilities of a computer to execute complex arithmetic and logical operations. We present techniques for signal value justification, and fault propagation, which are used by our algorithm. We have implemented a dependency-directed backtracking method to speed up our algorithm. This methodology has been applied to six circuits and the results are found to be very encouraging.

A novel switch-level simulator, called SNEL, is presented. The SNEL simulator preprocesses the circuit description to abstract its functionality prior to simulation. Functional abstraction is concisely defined in terms of the functional domain and the functional application of circuit constructs. SNEL uses four algorithms that operate on levels ranging from single circuit elements to multiple DC-connected components. Since the functional abstraction preserves the complete functionality of the circuit, the accuracy of the simulation is maintained. However, SNEL models the circuit at a higher and more abstract level, which increases its simulation speed. The presented algorithms were implemented and tested on commercial designs. Without functional abstraction, the simulation speed of SNEL is competitive with current simulators. When functional abstraction was used, the simulation speed increased by more than an order of magnitude.>

A powerful automatic test generation system which uses a novel nine-valued relaxation algorithm is presented. This algorithm, which brings together the relaxation technique from circuit simulation and a nine-valued algebra from sequential circuit test generation, is applied to the strongly connected DC coupling components so that for every possible choice of node values a stable state could be achieved through relaxation. Circuits which use bidirectional transistors and depend on the transistor strengths for correct operation are properly handled by this algorithm. A method called DC path sensitization is used to detect the stuck-at, stuck-on, stuck-open and bridging faults for CMOS transistors. The algorithm has been implemented in C++ and preliminary results are very promising. The algorithm can easily be extended to different circuit models and other technologies, or be incorporated into a higher level test generation system.>

In switch-level simulation, nodes carry a charge on their parasitic capacitance from one evaluation to the next, which gives them a memory quality. A node is classified as temporary if its memory aspect is lost and cannot affect the circuit operation, whereas a node is classified as a memory node if the memory of the node is maintained and can affect the circuit operation. Accurate classification of nodes into temporary and memory nodes increases the performance of compiled simulators and high-level model generators. An approach for reliable automatic classification of nodes in a switch-level description is introduced. Both an exhaustive, exponential-time algorithm and a polynomial-time heuristic are presented. The heuristic was implemented and tested for several large circuits, including a commercial microprocessor. For this processor, the proposed heuristics identified an average of 92% of all nodes as temporary nodes. The heuristic was applied in a high-level model generator and significantly increased its performance.>

The adequacy of the stuck-at fault model for BiCMOS logic is investigated. Realistic failures in basic logic blocks are examined, and their coverage by the stuck-at model is explored. It is shown that the static stuck-at model cannot cover the complete range of possible failures, and more importantly, tests for stuck-at faults will not detect realistic features in BiCMOS technology. This is because most open faults manifest themselves as delay failures. Through the use of transient analysis it is shown that the only way to insure proper functioning of BiCMOS circuits is to test for delay faults.>

Cost-effective and accurate fault simulation of very large digital designs on engineering workstations is proposed. The hierarchical approach reduces memory requirements drastically by storing the structure of common repeated subcircuits only once. The approach allows flexible multilevel simulation. The simulation algorithms are at the switch-level so that general MOS digital designs with bidirectional signal flow can be handled, and both stuck-at and transistor faults are treated accurately. The fault simulation algorithms have been implemented as a prototype that was used to determine the fault grade of a model of the Motorola 68000 microprocessor on SUN Microsystems workstations.>

The authors describe a novel matric method of analyzing faulty signatures from both single-input and multiple-input signature registers (MISRs). In particular, the information contained in the faulty signature of an MISR is investigated. The results indicate that the proposed method can be used to locate the faulty cycle or channel(s) of the failing net. The formulation has the advantage of simplicity over the polynomial representation and can be used to determine the relation between an error and its syndrome. The results provide new insights into the application of MISRs to built-in self-test.>

The problem of mapping a computation-intensive task of irregular structure onto a parallel framework is examined. The application considered is the switch-level logic simulation of digital circuits, a technique that is in wide use for the verification of VLSI designs. The authors focus on medium-grain multiprocessors and only consider model parallel computation, where the model of the design to be simulated is partitioned among processors. They address the issues of portability and scalability and look at specific features of the application that can be exploited. Different ways of mapping the simulation problem onto a parallel framework are presented. A prototype implementation of the algorithms is described.>

The design of fault-tolerant hypercube multiprocessor architecture is discussed. The authors propose the detection and location of faulty processors concurrently with the actual execution of parallel applications on the hypercube using a novel scheme of algorithm-based error detection. System-level error detection mechanisms have been implemented for three parallel applications on a 16-processor Intel iPSC hypercube multiprocessor: matrix multiplication, Gaussian elimination, and fast Fourier transform. Schemes for other applications are under development. Extensive studies have been done of error coverage of the system-level error detection schemes in the presence of finite-precision arithmetic, which affects the system-level encodings. Two reconfiguration schemes are proposed that allow the authors to isolate and replace faulty processors with spare processors.>

The testability of a class of circuits called generalized counters is investigated under a more powerful fault model than examined in earlier work. It is assumed that any number of full adders in a generalized counter can assume an incorrect function under fault, as long as the function remains combinational. The testability of the overall class of generalized counters is examined and it is shown that under a restricted fault model it is possible to detect all multiple faults with a test set that grows linearly with the number of counter inputs. It is then shown that for a subset of the class of generalized counters it is possible to detect multiple faults with a larger number of tests, linear to the number of counter inputs, when the restrictions on the fault model are relaxed.>

A generalization of existing real numer codes is proposed. It is proven that linearity is a necessary and sufficient condition for codes used for fault-tolerant matrix operations such as matrix addition, multiplication, transposition, and LU decomposition. It is also proven that for every linear code defined over a finite field, there exists a corresponding linear real-number code with similar error detecting capabilities. Encoding schemes are given for some of the example codes which fall under the general set of real-number codes. With the help of experiments, a rule is derived for the selection of a particular code for a given application. The performance overhead of fault tolerance schemes using the generalized encoding schemes is shown to be very low, and this is substantiated through simulation experiments.>

This paper discusses the automatic generation of high-level software models from switch-level circuit descriptions. The proposed algorithms operate directly on the hierarchical description, and incorporate information about the design such as the structure, regularity, functionality, and control signals in the generation process. New algorithms are proposed and have been implemented for combinational modules and bus structures. A significant speedup has been obtained for these modules of a commercially available chip.

In this paper we show that it is necessary to utilize different partitioning coefficients in interconnection length analyses which are based on Rent's rule, depending on whether one- or two-dimensional placement strategies are used. β, the partitioning coefficient in the power-law relationship αΒβ, provides a measure of the number of interconnections which cross a boundary enclosing Β blocks. The partitioning coefficients are β=p/2 and β=p for two- and one-dimensional arrays, respectively, where p is the experimental coefficient of the Rent relationship T=αΒp. Based on these separate partitioning coefficients, an average interconnection length prediction is presented for rectangular arrays that outperforms existing predictions. Examples are given to support this theory.

Timing verification is a critical part of VLSI circuit design. A new approach to timing verification using Register Transfer Level (RTL) descriptions is presented, which eliminates false paths that occur due to (i) redundancy, (ii) reconvergent fanout or (iii) control signal constraints, and generates a test for the critical paths. High level instructions of the circuit are used to test for any timing violations. An algorithm to identify a minimal set of instructions that tests the circuit for all timing errors in valid paths is proposed. Results are presented based on an implementation of the algorithm in LISP programming language on a TI Explorer machine.

Consideration is given to the use of general-purpose multiprocessors for various simulation tasks. The aims of the work are to define a general framework for the parallel simulation of digital systems and to develop and evaluate tools for logic and fault simulation that have a good cost-performance ratio. Specifically, a novel partitioning approach is introduced and used as the basis for the parallel logic and fault simulation of synchronous gate-level designs. Performance experiments with prototype implementations on a message passing and a shared memory machine give promising results, in particular for fault simulation.>

The synthesis of combinational logic which is robust delay fault testable is developed. In a circuit, any reconvergent fanout may result in the presence of blocked paths and/or paths which can be sensitized only if some other path is also sensitized. Implicit don't care terms are used to detect these problems and a local transformation at the reconvergence point is used to upgrade the delay fault testability of the circuit. The sharing of terms in a multilevel circuit is preserved to the greatest extent possible. Good results have been obtained based on an implementation of the algorithm in the LISP programming language on a TI Explorer machine.>

The authors present a model that allows the designer to calculate the cost of scan-path design for testability (DFT) for standard cell-based chips. The model is used to estimate the profitability of designs that use DFT techniques over the product life cycle and those that do not. It is shown that, under dynamic market conditions, it is sometimes better to choose a more expensive solution if the product can be delivered faster. Thus, scan-path techniques can more than make up for their extra area if they reduce test generation time and therefore product lead times.>

The authors consider the problem of estimating the testability of a digital circuit at the functional level. Using an information-theoretic approach, they have developed a functional testability measure for both controllability and observability. They introduce two techniques that can efficiently and accurately estimate the measure. In addition, some applications of the testability measure for automated design for testability, such as automatic circuit partitioning and test point insertion, are described.>

NCUBE applies all possible input patterns to each array cell while ensuring that the effects of incorrect transitions are observable at the array outputs. If the array is testable with a constant number of test vectors irrespective of its size (C-testable), then NCUBE generates the constant-size test set for the array. If the array cannot be tested with a constant number of test vectors, then the test size is proportional either to the number of rows or columns of the array or to the number of cells. In that case, NCUBE generates a minimal or near-minimal test set that depends on the size of the array.>

Currently available automatic test pattern generators (ATPGs) generate test sets that are nonoptimal in length. The authors describe novel heuristic techniques to reduce the length of the test set for a sequential circuit by compaction of the automatically generated patterns. Based on these techniques, a program has been written in C that achieved a 56%-73% reduction in the test length of a highly sequential circuit obtained from industry.>

The design and implementation of a hierarchical switch-level simulator for complex digital circuits is discussed. The hierarchy is exploited to reduce the memory requirements of the simulation, thus allowing the simulation of circuits that are too large to simulate at the flat level. The algorithm used in the simulator operates directly on the hierarchical circuit description. Speedup is obtained through the use of high-level models. The simulator has been implemented on a SUN workstation and used to simulate a switch-level description of the Motorola 68000 microprocessor.>

An algorithm is proposed for automatic test input generation for nonlinear analog circuits and digital circuits with analog behavior under fault. The algorithm uses high-level reasoning with simple iteration to find inputs which will detect resistive shorts and opens that cause DC errors. A simple version of the algorithm, for the time-domain case, has been implemented. Current work includes incorporating the heuristics into the path-generating algorithm, creating tests for larger circuits, extending the fault model to a parameter change in branches other than resistors (e.g. a beta change in a transistor), creating sensitivity metrics for the frequency domain and developing a transient error solution.>

Two concurrent error detection (CED) schemes are proposed for N-point fast Fourier transform (FFT) networks that consists of log/sub 2/N stages with N/2 two-point butterfly modules for each stage. The method assumes that failures are confined to a single complex multiplier or adder or to one input or output set of lines. Such a fault model covers a broad class of faults. It is shown that only a small overhead ratio, O(2/log/sub 2/N) of hardware, is required for the networks to obtain fault-secure results in the first scheme. A novel data retry technique is used to locate the faulty modules. Large roundoff errors can be detected and treated in the same manner as functional errors. The retry technique can also distinguish between the roundoff errors and functional errors that are caused by some physical failures. In the second scheme, a time-redundancy method is used to achieve both error detection and location. It is sown that only negligible hardware overhead is required. However, the throughput is reduced to half that of the original system, without both error detection and location, because of the nature of time-redundancy methods.>

This paper investigates the testability of a class of circuits, called counters, that perform the addition of sets of input bits of equal arithmetic weight. These circuits consist of full and half adders interconnected in an iterative manner defined by the counting process. The general class of counter circuits contain reconvergent fanouts and are not as structurally regular as one- or two-dimensional iterative logic arrays. A model for analyzing the structure of counter circuits is proposed. Several schemes for generating test sets that exploit the iterative structure of counter circuits are presented. The testability of such circuits is enhanced by imposing certain design constraints on them. Some methods for generating easily testable counter circuits are proposed. It is shown that counter circuits can always be designed to be testable with either eight or ten tests, irrespective of the input size.

This paper presents the technique of concurrent hierarchical fault simulation, a performance model, and two hierarchical optimization techniques to enhance fault simulator performance. The mechanisms for these enhancements are demonstrated with a performance model and are validated experimentally via CHIEFS, the Concurrent Hierarchical and Extensible Fault Simulator, and WRAP, an offline hierarchy compressor. Hieararchy-based fault partitioning and circuit reconfiguration are shown to improve simulator performance to O(n log n) under appropriate conditions. A decoupled fault modeling technique permits further performance improvements via a bottom-up hierarchy compression technique where macros of primitives are converted to single primitives. When combined, these techniques have produced a factor of 180 speedup on a mantissa multiplier. The performance model indicates that the speedup should increase with circuit size.

This paper examines the problem of comparing large replicated files in a context in which communication dominates the cost of comparison. A low-cost checking matrix is proposed for comparison of these replicated files. The checking matrix is composed of check symbols generated by a divide-and-conquer encoding algorithm. The matrix allows for detection and diagnosis of disagreeing pages with very little communication overhead. In contrast to a previous O(N) proposal, the storage requirement for the checking matrix is O(log N), where N is the number of pages in the file. The matrix can be stored in main memory without the need for extra accesses to disk during normal updates of pages.

A new methodology is proposed for generating tests at the transistor level for realistic failures including bridging faults, and transistor gate-to-source short and gate-to-drain short faults in CMOS combinational circuits. A new tree model for a fault-free CMOS complex gate is used to propagate errors due to faults with much less computation time. The technique adapts the tree structure representation for MOS gates to the D-Algorithm.

This paper describes a variety of fault and error models which are used as the basis for designing fault-tolerant Very Large Scale Integrated (VLSI) systems. The fault models describe physical defects and failures and the input patterns which will expose them, and are suitable for testing, while error models describe the effects on the functional outputs of defects and are useful for on-line error detection. The models are described at various levels of abstraction. The differences between fault and error models for identical functional modules are also illustrated.

Hardware for executing matrix arithmetic and signal processing algorithms at high speeds is in great demand in many real-time and scientific applications. With the advent of VLSI technology, large numbers of processing elements which cooperate with each other at high speed have become economically feasible. Since any functional error in a high-performance system may seriously jeopardize the operation of the system and its data integrity, some level of fault tolerance must be incorporated in order to ensure that the results of long computations are valid. Since the major computational requirements for many important real-time signal processing tasks can be reduced to a common set of basic matrix operations, the development of a unified fault-tolerant scheme for matrix operations can solve the problems of both reliable signal processing and reliable matrix operations. Earlier work proposed a low-cost checksum scheme for fault-tolerant matrix operations on multiple processor systems. However, this scheme can only correct errors in matrix multiplication; it can detect, but not correct, errors in matrix-vector multiplication, LU decomposition, matrix inversion, etc. In order to solve these problems with the checksum scheme, a very general matrix encoding scheme is proposed in this paper to achieve fault-tolerant matrix arithmetic and signal processing with linear arrays, which are believed to hold the most promise in VLSI computing structures for their flexibility, low cost, and applicability to most of the interesting algorithms. This proposed technique is, therefore, a very cost-effective encoding technique to achieve fault-tolerant matrix arithmetic and signal processing on highly concurrent VLSI computing structures.

An important consideration in the design of high- performance multiple processor systems should be in ensuring the correctness of results computed by such complex systems which are extremely prone to transient and intermittent failures. The detection and location of faults and errors concurrently with normal system operation can be achieved through the application of appropriate on-line checks on the results of the computations. This is the domain of algorithm-based fault tolerance, which deals with low-cost system-level fault-tolerance techniques to produce reliable computations in multiple processor systems, by tailoring the fault-tolerance techniques toward specific algorithms. This paper presents a graph-theoretic model for determining upper and lower bounds on the number of checks needed for achieving concurrent fault detection and location. The objective is to estimate ate the overhead in time and the number of processors required for such a scheme. Faults in processors, errors in the data, and checks on the data to detect and locate errors are represented as a tripartite graph. Bounds on the time and processor overhead are obtained by considering a series of subproblems. First, using some crude concepts for t-fault detection and t-fault location, bounds on the maximum size of the error patterns that can arise from such fault patterns are obtained. Using these results, bounds are derived on the number of checks required for error detection and location. Some numerical results are derived from a linear programming formulation.

In order to be able to take full advantage of a distributed computing facility it is important not only to distribute the hardware but also to distribute the control of these resources. However, distributed control is very different from centralized control since at any time, several processes or several controllers may observe different and inconsistent views of the global system state. The task of scheduling jobs in a distributed system must also be done Without full knowledge of the system state. In this correspondence we define a totally new distributed scheduling algorithm LP (linear predictive). scheduling, which not only implements distributed control of task scheduling but is also able to adapt itself to workload fluctuations. Using a general-purpose distributed system simulator we have shown the performance rnitince advantages of this new algorithm.

This paper describes FAUST, an MOS fault simulator with timing information. FAUST simulates the effects of realistic physical failures on MOS circuits and uses a static concurrent fault-simulation technique to evaluate the fault-free circuit and all the faulty circuits in one pass. FAUST produces voltage waveforms as well as logic tables with delay information for the fault-free circuit and for each of the faulty circuits.

article TIDBITS: speedup via time-delay bit-slicing in ALU design for VLSI technology Share on Authors: Peter Y. T. Hsu Computer Systems Group, Coordinated Science Laboratory, University of Illinois at Urbana-Champalgn Computer Systems Group, Coordinated Science Laboratory, University of Illinois at Urbana-ChampalgnView Profile , Joseph T. Rahmeh Computer Systems Group, Coordinated Science Laboratory, University of Illinois at Urbana-Champalgn Computer Systems Group, Coordinated Science Laboratory, University of Illinois at Urbana-ChampalgnView Profile , Edward S. Davidson Computer Systems Group, Coordinated Science Laboratory, University of Illinois at Urbana-Champalgn Computer Systems Group, Coordinated Science Laboratory, University of Illinois at Urbana-ChampalgnView Profile , Jacob A. Abraham Computer Systems Group, Coordinated Science Laboratory, University of Illinois at Urbana-Champalgn Computer Systems Group, Coordinated Science Laboratory, University of Illinois at Urbana-ChampalgnView Profile Authors Info & Claims ACM SIGARCH Computer Architecture NewsVolume 13Issue 3June 1985 pp 29–35https://doi.org/10.1145/327070.327121Online:01 June 1985Publication History 5citation474DownloadsMetricsTotal Citations5Total Downloads474Last 12 Months6Last 6 weeks3 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

This paper proposes a new logical model for nMOS and CMOS circuits. Existing gate-level and switch-level models are limited in their ability to simulate MOS circuit behavior accurately when modeling physical failures. The model proposed in this paper is in the form of a multivalued algebra defined on a set of node states. The state of a node is represented as a pairwhere "a" specifies the condition of a node and "b" specifies the logic level: There are five conditions and five logic levels. The assignment of node states is done dynamically during the process of logic simulation. The rules of the algebra are used to derive state tables that model the behavior of transistors. Our general model of a transistor allows for strong interactions between all three terminals of a transistor. This enables us to model the effects of physical failures such as a short between the gate and drain of a transistor. A simulation algorithm based on the algebra is discussed, and techniques for simulating physical failures in MOS circuits using the algebra are indicated.

The sequential behavior of CMOS logic circuits in the presence of stuck-open faults requires that an initialization input followed by a test input be applied to detect such a fault. However, a test set based on the assumption that delays through all gates and interconnections are zero, can be invalidated in the presence of arbitrary delays in the circuit. In this paper, we will present a necessary and sufficient condition for the existence of a test set, which cannot be invalidated under arbitrary delays, for an AND-OR or OR-AND CMOS realization for any given function. We will also introduce a Hybrid CMOS realization which, for any given function, is guaranteed to have a valid test set under arbitrary delays.

This paper presents a new and systematic method to generate tests for microprocessors. A functional level model for the microprocessor is used and it is represented by a reduced graph. A new and comprehensive model of the instruction execution process is developed. Various types of faults are analyzed and it is shown that with the use of appropriate codewords all faults can be classified into three types. This gives rise to a systematic procedure to generate tests which is independent of the microprocessor implementation details. Tests are given to detect faults in any microprocessor, first for the READ register instructions, and then for the remaining instructions. These tests can be executed by the microprocessor in a self-test mode, thus dispensing with the need for an external tester.

The rapid progress in VLSI technology has reduced the cost of hardware, allowing multiple copies of low-cost processors to provide a large amount of computational capability for a small cost. In addition to achieving high performance, high reliability is also important to ensure that the results of long computations are valid. This paper proposes a novel system-level method of achieving high reliability, called algorithm-based fault tolerance. The technique encodes data at a high level, and algorithms are designed to operate on encoded data and produce encoded output data. The computation tasks within an algorithm are appropriately distributed among multiple computation units for fault tolerance. The technique is applied to matrix compomations which form the heart of many computation-intensive tasks. Algorithm-based fault tolerance schemes are proposed to detect and correct errors when matrix operations such as addition, multiplication, scalar product, LU-decomposition, and transposition are performed using multiple processor systems. The method proposed can detect and correct any failure within a single processor in a multiple processor system. The number of processors needed to just detect errors in matrix multiplication is also studied.

Comprehensive VLSI fault models are proposed for three broad classes of interconnection networks between multiple processors and multiple memory modules. System-level algorithms are given for concurrent detection of errors produced by these faults during the normal use of the networks. The proposed algorithms are shown to be applicable to the three classes of interconnection networks with minimal changes in their classical design. The algorithms are appropriate for the broad classes of permanent and transient faults predominant in dense VLSI and wafer-scale integration with a minimal amount of network redundancy required for implementation.

In this paper we concentrate on the effect of instruction set architecture on the performance potential of a computer system. These issues are key in considerations of what instruction set is most appropriate for the support of high level languages on general purpose machines. Two possible approaches are so called complex instruction sets, such as those of the VAX and IAPX 432, and the “reduced” instruction set of the RISC I [2] microcomputer, which is expected to have performance similar to that of a VAX 11-780.

In order to implement a distributed system with fail-soft capabilities it is necessary to specify algorithms which redistribute the work load of a failed processor to the remaining good processors. This paper develops a general model to analyze the behavior of these algorithms in a distributed system. Such algorithms should be used with caution as they have the capability of making the entire system Unstable. By unstable we mean that if a processor fails, and its workload is redistributed, then the increased workload directed towards the rest of the system could drive one or more of the processors into overload resulting in a serious degradation of system performance. Using the general model we have studied a class of load redistribution algorithms which use various techniques to redistribute workload. These techniques include: buffering jobs arriving to the failed processor, transmitting only the jobs in the queue of the failed processor, and rerouting all jobs around the failed processor. For this class of algorithms we have derived closed form expressions for the performance of the system as a function of job arrival rate, job service rate, processor failure rate, and processor service rate. In addition, we have defined a criterion which, if adhered to, will guarantee system stability in the event of failure.

The problem of fault detection and test generation for programmable logic arrays (PLAs) is investigated. The effect of actual physical failures is viewed in terms of the logical changes of the product terms (growth, shrinkage, appearance and disappearance) constituting the PLA. Methods to generate a minimal single fault detection test set (Ts) from the product term specification of the PLAs, are presented. It is shown that such a test set can be derived using a set of simple, easily implementable algorithms. Methods to augment Ts in order to obtain a multiple fault detection test set (TM) are also presented.

In a distributed computing system made up of different types of processors each processor in the system may have different performance and reliability characteristics. In order to take advantage of this diversity of processing power, a modular distributed program should have its modules assigned in such a way that the applicable system performance index, such as execution time or cost, is optimized. This paper describes an algorithm for making an optimal module to processor assignment for a given performance criteria. We first propose a computational model to characterize distributed programs, consisting of tasks and an operational precedence relationship. This model alows us to describe probabilistic branching as well as concurrent execution in a distributed program. The computational model along with a set of seven program descriptors completely specifies a model for dynamic execution of a program on a distributed system. The optimal task to processor assignment is found by an algorithm based on results in Markov decision theory. The algorithm given in this paper is completely general and applicable to N-processor systems.

A methodology is given for generating combinational structures from high-level descriptions (using assignment statements, "if" statements, and single-nested loops) of register-transfer (RT) level operators. The generated structures are cellular, and are interconnected in a tree structure. A general algorithm is given to test cellular tree structures with a test length which grows only linearly with the size of the tree. It is proved that this test length is optimal to within a constant factor. Ways of making the structures self-checking are also indicated.

The goal of this paper is to develop test generation procedures for testing microprocessors in a user environment. Classical fault detection methods based on the gate and flip-flop level or on the state diagram level description of microprocessors are not suitable for test generation. The problem is further compounded by the availability of a large variety of microprocessors which differ widely in their organization, instruction repertoire, addressing modes, data storage, and manipulation facilities, etc. In this paper, a general graph-theoretic model is developed at the register transfer level. Any microprocessor can be easily modeled using information only about its instruction set and the functions performed. This information is readily available in the user's manual. A fault model is developed on a functional level quite independent of the implementation details. The effects of faults in the fault model are investigated at the level of the graph-theoretic model. Test generation procedures are proposed which take the microprocessor organization and the instruction set as parameters and generate tests to detect all the faults in the fault model. The complexity of the test sequences measured in terms of the number of instructions is given. Our effort in generating tests for a real microprocessor and evaluating their fault coverage is described.

A fault model which views faults in semiconductor random-access memories at a functional level instead of at a basic gate level is presented. An efficient 0(n) algorithm to detect all faults in the fault model is described. The fault model is then extended to incorporate more complex faults. An 0(n · log2 n) algorithm is presented for one such extended fault model.

A combinatorial procedure is given to calculate the reliability of an interwoven redundant logic network to any desired degree of accuracy. The procedure consists of enumerating combinations of gate failure which are tolerated by the redundant network, and is explained with reference to a quadded logic network. Since the exact reliability calculation might be too time consuming for large networks, a formula is given for a lower bound which can be used in conjunction with the exact method to give a very accurate reliability figure with a comparatively small computation time.

There are several instances where the classical method of triple-modular redundancy (TMR) reliability modeling may provide predictions which are inadequate. It is shown that for even simple networks such as those exhibiting fan-in and fan-out, classical methods may predict a reliability that is higher than or lower than the actual reliability. Furthermore, the classical method gives no hint as to whether the predicted number is high or low. As a solution to this problem, a method of partitioning an arbitrary network into cells such that faults in a cell are independent of faults in other cells is proposed. An algorithm is then given to calculate the reliability of any such cell, by considering only the structure of the interconnections within the cells. The value of the reliability found is exact if TMR is assumed to be a coherent system. An approximation to the algorithm is also described; this can be used to find a lower bound to the reliability without extensive calculation.