This keynote is a tribute to the late Prof. Mel Breuer, entitled Contributions to CAD and Test. It is organized by Sandeep Gupta. A panel of three prominent speakers gives this keynote. The three speakers are Miron Abramovici, Magdy Abadir and Sridhar Narayanan.

Post-silicon validation is a necessary step in a design's verification process. Pre-silicon techniques such as simulation and emulation are limited in scope and volume as compared to what can be achieved on the silicon itself. Some parts of the verification, such as full-system functional verification, cannot be practically covered with current pre-silicon technologies. This panel brings together experts from industry, academia, and EDA to review the differences and similarities between pre- and post-silicon, discuss how the fundamental aspects of verification are affected by these differences, and explore how the gaps between the two worlds can be bridged.

Most adaptive computing systems use reconfigurable hardware in the form of field programmable gate arrays (FPGAs). For these systems to be fielded in harsh environments where high reliability and availability are a must, the applications running on the FPGAs must tolerate hardware faults that may occur during the lifetime of the system. In this paper, we present new fault-tolerant techniques for FPGA logic blocks, developed as part of the roving self-test areas (STARs) approach to online testing, diagnosis, and reconfiguration . Our techniques can handle large numbers of faults (we show tolerance of over 100 logic faults via actual implementation on an FPGA consisting of a 20 times 20 array of logic blocks). A key novel feature is the reuse of defective logic blocks to increase the number of effective spares and extend the mission life. To increase fault tolerance, we not only use nonfaulty parts of defective or partially faulty logic blocks, but we also use faulty parts of defective logic blocks in nonfaulty modes. By using and reusing faulty resources, our multilevel approach extends the number of tolerable faults beyond the number of currently available spare logic resources. Unlike many column, row, or tile-based methods, our multilevel approach can tolerate not only faults that are evenly distributed over the logic area, but also clusters of faults in the same local area. Furthermore, system operation is not interrupted for fault diagnosis or for computing fault-bypassing configurations. Our fault tolerance techniques have been implemented using ORCA 2C series FPGAs which feature incremental dynamic runtime reconfiguration

In this paper we present a Design-for-Debug (DFD) reconfigurable infrastructure for SoCs to support at-speed in-system functional debug. A distributed reconfigurable fabric inserted at RTL provides a debug platform that can be configured and operated post-silicon via the JTAG port. The platform can be repeatedly reused to configure many debug structures such as assertions checkers, transaction identifiers, triggers, and event counters.

In this paper, we introduce two design-for-testability (DFT) techniques based on clock partitioning and clock freezing to ease the test generation process for sequential circuits. In the first DFT technique, a circuit is mapped into overlapping pipelines by selectively freezing different sets of registers so that all feedback loops are temporarily cut. An opportunistic algorithm takes advantage of the pipeline structures and detects most faults using combinational techniques. This technique is feasible to circuits with no or only a few self-loops. In the second DFT technique, we use selective clock freezing to temporarily cut only the global feedback loops. The resulting circuit, called a loopy pipe, may have any number of self-loops. We present a new clocking technique that generates clock waves to test the loopy pipe. Another opportunistic algorithm is proposed for test generation for the loopy pipe. Experimental results show that the fault coverage obtained is significantly higher and test generation time is one order of magnitude shorter for many circuits compared to conventional sequential circuit test generators. The DFT techniques do not introduce any delay penalty into the data path, have small area overhead, allow for at-speed application of tests, and have low power consumption.

We present the first online built-in self-test (BIST) and BIST-based diagnosis of programmable logic resources in field-programmable gate arrays (FPGAs). These techniques were implemented and used in a roving self-testing areas (STARs) approach to testing and reconfiguration of FPGAs for fault-tolerant applications. The BIST approach provides complete testing of the programmable logic blocks (PLBs) in the FPGA during normal system operation. The BIST-based diagnosis can identify any group of faulty PLBs, then applies additional diagnostic configurations to identify the faulty look-up table or flip-flop within a faulty PLB. The ability to locate defective modules inside a PLB enables a new form of fault-tolerance that reuses partially defective PLBs in their fault-free modes of operation.

In this paper we show that an embedded FPGA core is an ideal host to implement infrastructure IP for yield improvement in a bus-based SoC. We present methods for testing, diagnosing, and repairing embedded FPGAs, for which complete testability is achieved without any area overhead or performance degradation. We show how an FPGA core can provide embedded testers for other cores in the SoC, so that cores designed to be tested with external vectors can be tested with BIST, and the entire SoC can be tested with a low-cost tester.

We present a new clock-control DFT technique for sequential circuits, based on clock partitioning and selective clock freezing, and we use it to break the global feedback loops and to generate clock waves to test the resulting sequential circuit with self-loops. Clock waves allow us to significantly reduce the complexity of sequential ATPG. Unlike scan, our non-intrusive DFT technique does not introduce any delay penalty; the generated tests may be applied at speed, have shorter application time, and dissipate less power.

We present a Built-In Self-Test (BIST)-based diagnostic approach for the programmable interconnect resources in Field Programmable Gate Arrays (FPGAs) that can be used for either on-line or off-line testing. The technique was originally intended for on-line diagnosis of faulty interconnect to support fault-tolerant applications. However, the technique has been proven to be an excellent approach for off-line testing and diagnosis as well, providing high-resolution diagnostics with the ability to identify the faulty wire segment or programmable switch. We have implemented this BIST-based diagnostic approach on the ORCA series FPGA and present the results of testing and diagnosing known defective FPGAs.

We present a new approach to built-in self-test (BIST) for logic circuits that achieves comparable fault coverages to scan BIST with less hardware overhead and no impact on performance. We combine clock partitioning to create independent clocks with a selective freezing of clock signals to form various pipeline configurations during testing. Since no scan operations are performed, tests can be applied at the operational speed of the circuit. Experimental results are presented for several benchmark circuits to demonstrate the effectiveness of the approach.

We present a built-in self-test (BIST) approach able to detect and accurately diagnose all single and practically all multiple faulty programmable logic blocks (PLBs) in field programmable gate arrays (FPGAs) with maximum diagnostic resolution. Unlike conventional BIST, FPGA BIST does not involve any area overhead or performance degradation. We also identify and solve the problem of testing configuration multiplexers that was either ignored or incorrectly solved in most previous work. We introduce the first diagnosis method for multiple faulty PLBs; for any faulty PLB, we also identify its internal faulty modules or modes of operation. Our accurate diagnosis provides the basis for both failure analysis used for yield improvement and for any repair strategy used for fault-tolerance in reconfigurable systems. We present experimental results showing detection and identification of faulty PLBs in actual defective FPGAs. Our BIST architecture is easily scalable.

In this paper we present an on-line, multi-level fault tolerant (FT) technique for system functions and applications mapped to partially and dynamically reconfigurable FPGAs. Our method is based on the roving self testing areas (STARs) fault detection/location strategy presented in Abramovici et al. (1999). In STARs, the area under test uses partial reconfiguration properties to modify the configuration of the area under test without affecting the configuration of the system function and dynamic reconfiguration properties to allow uninterrupted execution of the system function while reconfiguration takes place. In this paper we take this one step further. Once a fault (or multiple faults) is detected we dynamically reconfigure the working area application around the fault with no additional system function interruption (other than the interruption when a STAR moves to a new location). We also apply the concept of partially usable blocks to increase fault tolerance. Our method has been successfully implemented and demonstrated on the ORCA 2CA series FPGAs from Lucent Technologies.

We present a BIST-based approach able to detect and accurately diagnose any single and most multiple faulty programmable logic blocks (PLBs) in field programmable gate arrays (FPGAs). For any faulty PLB, we also identify its internal faulty modules or modes of operation. This accurate diagnosis provides the basis for both failure analysis used for yield improvement and for any repair strategy used for fault-tolerance. We present experimental results showing detection and identification of faulty PLBs in actual defective FPGAs.

In this paper we present MUST-a multiple-stem analysis algorithm for identifying untestable faults in sequential circuits. In general, processing untestable faults is the most time-consuming part of a sequential ATPG. MUST extends the scope of the single-stem analysis done in the FIRES algorithm by identifying additional untestable faults that cannot be found by single-stem analysis. While its computational requirements are greater than those of FIRES, the run-time of MUST remains significantly lower than that used by sequential ATPG. We show that the faults identified by MUST are difficult targets for conventional ATPG programs, that can benefit by using MUST as a preprocessor and excluding the untestable faults identified by multiple stem analysis from the target faults processed by ATPG. We report experimental results obtained by our prototype implementation of MUST on ISCAS benchmarks and other circuits.

In this paper, we first present an algorithm (FILL) to efficiently identify a large subset of illegal states in synchronous sequential circuits, without assuming a global reset mechanism. A second algorithm, FUNI, finds sequentially untestable faults whose detection requires some of the illegal states computed by FILL. Although based on binary decision diagrams (BDDs), FILL is able to process large circuits by using a new functional partitioning procedure. The incremental building of the set of illegal states guarantees that FILL will always obtain at least a partial solution. FUNI is a direct method that identifies untestable faults without using the exhaustive search involved in automatic test generation (ATG). Experimental results show that FUNI finds a large number of untestable faults up to several orders of magnitude faster than an ATG algorithm that targeted the faults identified by FUNI. Also, many untestable faults identified by FUNI were aborted by the test generator.

Article A massively-parallel easily-scalable satisfiability solver using reconfigurable hardware Share on Authors: Miron Abramovici Bell Labs - Lucent Technologies, Murray Hill, NJ Bell Labs - Lucent Technologies, Murray Hill, NJView Profile , Jose T. de Sousa Bell Labs - Lucent Technologies, Murray Hill, NJ Bell Labs - Lucent Technologies, Murray Hill, NJView Profile , Daniel Saab Case Western Reserve University, Cleveland, Ohio Case Western Reserve University, Cleveland, OhioView Profile Authors Info & Claims DAC '99: Proceedings of the 36th annual ACM/IEEE Design Automation ConferenceJune 1999 Pages 684–690https://doi.org/10.1145/309847.310028Online:01 June 1999Publication History 11citation298DownloadsMetricsTotal Citations11Total Downloads298Last 12 Months0Last 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

Test application time is an important factor in the overall cost of VLSI chip testing. We present a new ATPG approach for generating compact test sequences for sequential circuits. Our approach combines a conventional ATPG algorithm, a technique based on the frozen clock testing strategy, and a dynamic compaction method based on a genetic algorithm. The frozen clock strategy temporarily suspends the sequential behavior of the circuit by stopping its clock and applying several vectors to increase the number of faults detected without changing the circuit state. Results show that test sets generated using the new approach are more compact than those generated by previous approaches for many circuits.

Satisfiability (SAT) is a computationally expensive algorithm central to computer science. In this paper, we present a virtual logic algorithm that allows an FPGA based reconfigurable comparing platform to process SAT solver circuits much larger than its available capacity. Our algorithm is based on decomposition techniques that create independent subproblems (pages) that fit the size of the available reconfigurable hardware. Those pages can take turns reusing the platform, and creating a virtual logic environment.

In this paper we present a novel integrated approach to on-line FPGA testing, diagnosis, and fault-tolerance, to be used in high-reliability and high-availability hardware. The test process takes place in self-testing areas (STARs) of the FPGA, without disturbing the normal system operation. The entire chip is eventually tested by having (STARs) gradually rove across the FPGA. Our approach guarantees complete testing of programmable logic blocks and interconnect, and provides maximum diagnostic resolution. A new fault-tolerant (FT) technique allows using partially defective FPGA resources for normal operation, providing longer mission life-span in the presence of faults. We also introduce the basic concepts of a new dynamic FT method, spare resources needed to bypass a fault are always in the neighborhood of the located fault, thus simplifying fault-bypassing.

We introduce the first BIST approach for testing the programmable routing network in FPGAs. Our method detects opens in, and shorts among, wiring segments, and also faults affecting the programmable switches that configure the FPGA interconnect. As a result, the BIST technique provides complete testing of interconnect faults.

The authors introduce a new approach to fault simulation, using reconfigurable hardware to implement a critical path tracing algorithm. The performance estimate shows that the approach is at least on order of magnitude faster than serial fault emulation used in prior work.

Accurate diagnosis is an essential requirement in many testing environments, since it is the basis for any repair or replacement strategy used for chip or system fault-tolerance. In this paper we present the first approach able to diagnose faulty programmable logic blocks (PLBs) in Field Programmable Gate Arrays (FPGAs) with maximal diagnostic resolution. Our approach is based on a new Built-In Self-Test (BIST) architecture for FPGAs and can accurately locate any single and most multiple faulty PLBs. An adaptive diagnostic strategy provides identification of faulty PLBs with a 7% increase in testing time over the complete detection test, and can also be used for manufacturing yield enhancement. We present results showing identification of faulty PLBs in defective ORCA chips.

personal or class-room use is granted without fee provided that copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication and its date appear, and notice is given that copying is

We present a new approach for FPGA testing that exploits the reprogrammability of FPGAs to create Built-In Self-Test (BIST) logic only during off-line test. As a result, BIST is achieved without area or performance penalties to the system function implemented by the FPGA, since the FPGA is reconfigured for normal system operation. An analysis of Look-Up Table (LUT) based FGPA architectures yields a general expression for the number of test sessions and establishes the bounds on FPGA logic resources required to minimize the number of BIST configurations required to completely test all of the programmable logic blocks of an FPGA.

We present an improved Built-In Self-Test (BIST) approach for the programmable logic blocks (PLBs) of a Field Programmable Gate Array (FPGA), which repeatedly reconfigures the FPGA as a group of C-testable iterative logic arrays. The new architecture is easily scalable with increasing size of FPGAs and ensures routability of the various configurations required to completely test the FPGA in three test sessions. In addition, the BIST approach addresses RAM mode testing as well as testing the adder/subtractor modes in FPGAs.

We provide a new answer to the fundamental question "Why is sequential test generation so difficult?" the presence of darn (Difficult And Really Needed) states. A darn state is both difficult to reach and required to detect some faults. We introduce a method for identifying darn stares, along with a technique to measure their detrimental effect on the fault coverage. Darn states are the result of detrimental correlation between flip-flops (FFs) sharing the same clock. We propose a novel DFT technique in which FFs are partitioned into different groups having independent clocks during resting. The goal of partitioning is to increase the fault coverage by transforming darn states into easy-to-reach states. The proposed DFT has small area overhead and no performance penalty.

We present a new approach for Field Programmable Gate Array (FPGA) testing that exploits the reprogrammability of FPGAs to create Built-In Self-Test (BIST) logic only during off-line test. As a result, BIST is achieved without any area overhead or performance penalties to the system function implemented by the FPGA. Our approach is applicable to all levels of testing, achieves maximal fault coverage, and all tests are applied at-speed. We describe the BIST architecture used to test all the programmable logic blocks in an FPGA and the configurations required to implement our approach using a commercial FPGA. We also discuss implementation problems caused by CAD tool limitations and limited architectural resources, and we describe techniques which overcome these limitations.

FIRE is a novel Fault-Independent algorithm for combinational REdundancy identification. The algorithm is based on a simple concept that a fault which requires a conflict as a necessary condition for its detection is undetectable and hence redundant. FIRE does not use the backtracking-based exhaustive search performed by fault-oriented automatic test generation algorithms, and identifies redundant faults without any search. Our results on benchmark and real circuits indicate that we find a large number of redundancies (about 80% of the combinational redundancies in benchmark circuits), much faster than a test-generation-based approach for redundancy identification. However, FIRE is not guaranteed to identify all redundancies in a circuit.

In this paper, we present a testability-based method to combine three different DFT techniques: partial reset, partial observation, and partial scan. This approach combines the complementary strengths of the DFT techniques taking advantage of their different cost/benefit trade-offs, and results in more testable circuits with reduced design penalty.

In this paper, we first present an algorithm (FILL) which efficiently identifies a large subset of the illegal states in a synchronous sequential circuit, without assuming a global reset mechanism. A second algorithm, FUNI, finds sequentially untestable faults whose detection requires some of the illegal states computed by FlLL. Although based on binary decision diagrams (BDDs), FILL is able to process large circuits by using a new functional partitioning procedure. The incremental building of the set of illegal states guarantees that FILL mill always obtain at least a partial solution. FUNI is a direct method that identifies untestable faults without using the exhaustive search involved in automatic test generation (ATG). Experimental results show that FUNI finds a large number of untestable faults up to several orders of magnitude faster than an ATG algorithm that targeted the faults identified by FUNI, Also, many untestable faults identified by FUNI were aborted by the test generator.

This paper presents a novel fault-independent algorithm for identifying untestable faults in sequential circuits. The algorithm is based on a simple concept that a fault which requires an illegal combination of values as a necessary condition for its detection is untestable. It uses implications to find a subset of such faults whose detection requires conflicts on certain lines in the circuit. No global reset state is assumed and no state transition information is needed. Our fault-independent algorithm identifies untestable faults without any search as opposed to exhaustive search done by fault-oriented test generation algorithms. Results on benchmark and real circuits indicate that we find a large number of untestable faults, much faster (up to 3 orders of magnitude) than a test-generation-based algorithm that targeted the faults identified by our algorithm. Moreover, many faults identified as untestable by our approach were aborted when targeted by a sequential test generator.

In this paper, we present a new method for selecting flip-flops for partial scan. Our method ranks all flip-flops based on a sensitivity analysis that determines the improvement in the testability of the circuit as a result of scanning a flip-flop. Testability is computed with respect to a given set of target faults. Our method can estimate the number of scan flip-flops needed to reach a good fault coverage.

High fault coverage for single stuck faults (SSFs) is a necessary (but not sufficient) condition to achieve high defect coverage. The defect coverage of the manufacturing test is the main factor determining the quality of the products shipped to customers. Since the fault coverage for SSFs is a basic concept in testing, it should have a clear, well-understood, and universally accepted meaning. How can it be otherwise, when a minimum fault coverage is one of the requirements imposed on a design, when vendors make so many claims regarding the fault coverage obtained with their tools, when we apply DFT techniques to improve the fault coverage, and when almost every paper reports some fault coverage figures? In reality, there are several ways of computing the fault coverage, and their results may differ greatly. This position paper provides a critical analysis of the different fault coverage measures used in practice.>

Partial reset is an inexpensive design for test technique in which an additional primary input is connected to the reset or the set inputs of a subset of flip-flops (FFs). In this paper, we present a new method to select the FFs to be initialized and their initial values. The FFs are selected based on their contribution to the testability of the circuit. A sensitivity analysis is done to determine the ranking of FFs. The results obtained by the new method show that our selection of FFs gives consistently better fault coverage than the previously used one.>

In this gaper we show that even when a sequential test generator does a perfect job and achieves 100% detectable fault coverage, a circuit passing the test may still exhibit severe testability problems caused by undetectable faults that prevent initialization (FPIs). Thus 100% fault coverage may be a misleading quality indicator, unless undetectable FPIs are accounted for. We present the first algorithm able to identify undetectable FPIs and we report the results obtained for the sequential benchmark circuits. We also discuss the design for testability techniques that make these faults detectable.

Test generation for combinational circuits, an NP-complete problem, shows its worst-case behavior while trying to generate tests for redundant faults and failing after an exhaustive search. The performance of an automatic test generator can be significantly improved by identifying redundancy via simple techniques which do not involve a search. The authors present a technique to identify redundant faults. This technique works dynamically during test generation, but is not based on a search process. It relies on test-covering relations among faults, which allow identification of addition redundant faults after the test generator fails to generate a test for a target fault. This technique has been implemented in AT&T's Testpilot test generation system and has shown a reduction of up to 32% in the number of backtracks in test generation runs.>

The full-scan and the nonscan versions of a circuit This paper presents a new algorithm for selecting the best flip-flops to scan for achieving maximum fault coverage in a partial-scan circuit. The algorithm, called PASCAL (PArtial Scan AnaLysis), ranks the flip-flops based on their contribution to the fault coverage. The results of PASCAL provide a global view of the entire partial-scan design spectrum (from no scan to full scan), and allow the designer to estimate the fault coverage achievable with any number of scanned flip-flops and to select the minimal subset of flip-flops to scan for obtaining a desired fault coverage. The number of scanned flip-flops can be reduced by taking into account faults detected by functional tests.

The basic critical path tracing method for combinational circuits is outlined, and it is shown how it can produce pessimistic results in certain cases where fault effects propagate along multiple paths. The problem of extending the critical path tracing method to sequential circuits is considered. It is shown that the pessimistic nature of critical path tracing in combinational circuits may lead to optimistic results in sequential circuits, and a modification of the critical path tracing method to make it exact for combinational circuits is proposed. Based on this modification, a critical path tracing algorithm for synchronous sequential circuits is developed which is also exact.>

The authors present a new cost function (GLOBAL) which is used to guide the decision process in test generation algorithms. By analyzing the global fanout structure of the circuit, GLOBAL guides the search for a test toward decisions that are least likely to result in conflict. The results obtained indicate that GLOBAL is a consistently superior guidance heuristic for test generation. Compared with previous cost functions, it provides greater fault coverage in approximately the same number of tests and usually in less CPU time. It appears to be more consistent and hence it can be reliably used on large circuits. GLOBAL identifies both lines whose justification is conflict free and lines whose justification is likely to lead to conflicts. Although its worst-case complexity is exponential in the number of stems, the analysis done by GLOBAL is performed only once, while its results are used at every decision step of an algorithm with a similar worst-case behavior. The results show that the time gained in test generation usually outweighs the time spent in preprocessing.>

The performance of an automatic test generator can be significantly improved by identifying redundancy by simple techniques which do not involve search. The authors present a technique for identifying redundant faults. This technique works dynamically during test generation but is not based on a search process. It exploits dominance and test-covering relations among faults, which allow identification of additional redundant faults after the test generator fails to generate a test for a target fault. This technique has been implemented in AT&T's LTG (LAMP2 test generation) system and has shown up to 32% reduction in the number of backtracks in test generation runs.>

The authors present the experience and strategy guiding the system-level computer-aided design verification (CADV) process used in the AT&T computer division. Specifically, they provide an overview of processes, results, and the strategy used to choose among modeling options, styles for the verification process, methods for test development, timing models, and techniques for analyzing results. CADV is now being used on ten active projects. The use of CADV has reduced the number of circuit board artmaster cycles required to produce a high-quality design for high-volume manufacture from an average of 3.5 to 4 cycles to an average of 2 cycles. >

The authors present the CAD tools used for system-level design verification (DV) in the AT&T computer division. They discuss features of the tools for building and preparing the model of the system, developing tests, simulation, static timing analysis, results analysis, and circuit comparison. While a good simulator is an essential component, many other tools are required. Although some of them provide only relatively minor capabilities, together they form an integrated set of tools that greatly simplify the designers' work and make possible successful completion of system-level DV projects.>

Critical path tracing has been shown to be faster than traditional fault simulation methods, but it produces pessimistic results in some cases involving reconvergent fanout. It is shown that the pessimistic nature of critical path tracing in combinational circuits can lead to incorrect results that are not necessarily pessimistic in sequential circuits. A modification of the method for removing the approximation is proposed, and a critical path tracing algorithm for synchronous sequential circuits is presented.>

Motivated by the advances in fast fault-simulation techniques for large combinational circuits, a panel discussion was organized for the 1988 International Test Conference. A collective account of the position statements is offered by the panelists. The panelists present discussions on the following topics: introduction to fault simulation; parallel pattern fault simulation; intelligent heuristics; graph-theoretic approaches; approximate solutions; hierarchical fault simulation; and hardware solutions.>

Stuck-at faults on primary inputs and fan-out branches are commonly used as target faults in test generation algorithms for combinational circuits. This correspondence shows that these faults may not constitute an adequate set of target faults. A procedure is presented for selecting a set of target faults with the property that the detection of all detectable faults from this set guarantees the detection of all detectable faults in the circuit.

In this correspondence we prepent a practical approach to fault simulation and test generation for bridging faults in combinational circuits. Unlike previous work, we consider Unrestricted bridging faults, including those that introduce feedback. Our approach is based on extending fault simulation and test generation for stuck faults to cover bridging faults as well. We consider combinational testing only, and show that adequate bridging fault coverage can be obtained in most cases without using sequences of vectors.

Special-purpose CAD hardware is increasingly being considered as a means to meet the challenge posed to conventional (software-based) CAD tools by the growing complexity of VLSI circuits. In this paper we describe the architecture of a logic simulation machine employing distributed and parallel processing. Our architecture can accommodate different levels of modeling ranging from simple gates to complex functions, and support timing analysis. We estimate that simulation implemented by the proposed special-purpose hardware will be between 10 and 60 times faster than currently used software algorithms running on general-purpose computers. With the available technology, a throughput of 1 000 000 gate evaluations/sec can be achieved.

Special-purpose CAD hardware is increasingly being considered as a means to meet the challenge posed to conventional (software-based) CAD tools by the growing complexity of VLSI circuits. In this paper we describe the architecture of a logic simulation machine employing distributed and parallel processing. Our architecture can accommodate different levels of modeling ranging from simple gates to complex functions, and support timing analysis. We estimate that simulation implemented by the proposed special-purpose hardware will be between 10 and 60 times faster than currently used software algorithms running on general-purpose computers. With the available technology, a throughput of 1,000,000 gate evaluations/second can be achieved.

Special-purpose CAD hardware is increasingly being considered as a means to meet the challenge posed to conventional (software-based) CAD tools by the growing complexity of VLSI circuits. In this paper we describe the architecture of a logic simulation machine employing distributed and parallel processing. Our architecture can accommodate different levels of modeling ranging from simple gates to complex functions, and support timing analysis. We estimate that simulation implemented by the proposed special-purpose hardware will be between 10 and 60 times faster than currently used software algorithms running on general-purpose computers. With the available technology, a throughput of 1,000,000 gate evaluations/second can be achieved.

We present several extensions of the effect–cause analysis method [1] for fault diagnosis in combinational circuits. First, we extend the analysis to circuits consisting of interconnected modules that are assumed to be internal fault-free. To handle the situation in which the obtained response is incompatible with a fault domain restricted to the I/O pins of modules, we introduce a hierarchical approach that repeats the analysis, every time with a suspected module replaced by its gate model, while the rest of the circuit remains modeled at the module level.

In this paper we present a new approach to fault diagnosis in sequential circuits based on an effect–cause analysis. This represents an extension of our previous work dealing with combinational circuits [1]. The main tool of our approach is the Deduction Algorithm, which deduces internal values in the circuit under test based upon the test results. The deduced values are used for fault diagnosis, which encompasses both fault detection and location.

This paper presents the basic concepts of a new fault diagnosis technique which has the following features: 1) is applicable to both single and multiple faults, 2) does not require fault enumeration, 3) can identify faults which prevent initialization, 4) can indicate the presence of nonstuck faults in the D.U.T., 5) can identify fault-free lines in the D.U.T. Our technique, referred to as effect-cause analysis, does not require a fault dictionary and it is not based on comparing the obtained response of the D.U.T. with the expected response, which is not assumed to be known. Effect-cause analysis directly processes the actual response of the D.U.T. to the applied test (the effect) to determine the possible fault situations (the causes) which can generate that response.

In this paper we present a new approach to multiple fault diagnosis in combinational circuits based on an effect-cause analysis. The main vehicle of our approach is the deduction of internal line values in a circuit under test N*. The knowledge of these values allows us to identify fault situations in N* (causes) which are compatible with the applied test and the obtained response (the effect). A fault situation specifies faulty as well as fault-free lines. Other applications include identifying the existence of nonstuck faults in N* and determination of faults not detected by a given test, including redundant faults. The latter application allows for the generation of tests for multiple faults without performing fault enumeration.

In this correspondence we show that the well-known concepts of redundancy and undetectability of a stuck-at fault, which are equivalent in combinational circuits, are not equivalent in sequential circuits. We also show that some faults in sequential circuits, which are undetectable (by "conventional" methods of testing), are detectable by transition count testing methods.