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.

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.

In this paper, we discuss a new type of NEMS switches that can be configured to implement any 2-input logic gates (AND, OR, NAND, NOR, XOR, XNOR, NOT) in a single device structure. These devices can be used to implement FPGA where a four-input CLB requires only nine NEMS switches and at most two mechanical delays per computation. In contrast, CMOS CLBs require 150 traditional switches. By reducing the number of devices, our approach improves yield, reproducibility, speed, power and simplifies implementation.

Energy efficiency and idle power consumption are becoming important parameters in the design of embedded systems that are realized with nanometer-scale CMOS devices. In nanometer-scale CMOS, Excessive quiescent power dissipation can lead to excessive heat generation and reliability issues. To address energy efficiency and idle power consumption, we present a novel Complementary Nano-Electro-Mechanical (CNEM) switch that we manufactured which operates with virtually zero leakage current, has 1 to 2 Volts operation voltage, >; 1 GHZ fundamental resonant frequency, and nanometer-scale footprint. These CNEM switches can be “dropped” in and hybridized with CMOS at the metallization or device levels to manage leakage current and power. In this paper, we present a hybrid CMOS/CNEMS FPGA. The hybrid FPGA is based on using the CNEM switching device as a replacement of CMOS devices in the switch and connection block components found in FPGA architectures. We analyzed the impact of the CNEM substitution on power and delay using VPR and the MCNC benchmark circuits. We present experimental results showing an average 98%, 85%, 71%, and 99.99% reduction in critical path delay, routing energy, total energy, leakage power when comparisons are made between FPGA design using pure CMOS (180nm technology and hybrid CNEMS and CMOS (180nm) technology.

Idle power consumption is becoming an important parameter in portable embedded system design where excessive quiescent power dissipation can lead to excessive heat generation and reliability issues in nanometer-scale CMOS. To address some of these limitations, we have implemented a novel nano-electro-mechanical (NEM) switch with virtually zero leakage current, 1 Volt operation voltage, >1 GHZ fundamental resonant frequency, and nanometer-scale footprint. These NEM switches can be "dropped" in and hybridized with CMOS at the metallization or device levels to manage leakage current and power. Additionally, we introduce positive and negative channel switches in the form of complementary NEMS (CNEMS), similar to CMOS. CNEMS are compatible with CMOS in their functionality, structure and fabrication. Moreover, design methods, circuits, architectures and design automation techniques from CMOS can be readily used to realize CNEMS logic gates and processors. In this paper, we motivate the development of our NEM switch. We present NEMS characterizations, the construction of FET-like NEMs (CNEMS) switches and basic logic gates. We present simulation results showing CNEMS power dissipation improvement over nanometer-scale CMOS.

Exact path delay fault (PDF) coverage calculation of large circuits with an exponential number of detectable PDFs requires exponential memory space. This often yields memory overflow in computations. One common approach to avoid memory overflow is to partition or virtually cut circuits into several subcircuits and to perform coverage calculation at the partition-level circuit. Partitioning reduces the number of PDFs to be stored in memory exponentially at the expense of losing considerable coverage. This paper describes an algorithm to improve the reported coverage value by recovering the lost PDFs up to a user-controlled degree (Delta), which is a function of the length of cut net sequences. The reported coverage monotonically increases as Delta increases: the exact coverage value is guaranteed when Delta is equal to the number of consecutive partitions on the longest path. Experimental results are provided for the ISCAS85 circuits that illustrate the trade-off between the computation time, the number of partitions, the values of Delta, and the reported coverage. The results indicate that as Delta and the number of partitions increase, the runtime does not increase after some point since the cost of set operations reduces as more partitions are created.

In recent years, several alternative devices have been proposed to deal with inherent limitation of conventional CMOS devices in terms of scalability at nanometer scale geometry. The fabrication and integration cost of these devices, however, have been prohibitive and/or the devices do not allow smooth transition from the conventional design paradigm. To address some of these limitations, we have developed a new family of devices called "complementary nano electro-mechanical switches" (CNEMS) using carbon nanotubes as active switching/latching elements. The basic structure of these devices consists of three coplanar carbon nanotubes arranged so that the central nanotube can touch the two side carbon nanotubes upon application of a voltage pulse between them. Owing to the unique properties of carbon nanotubes, these devices have very low leakage current, low operation voltages, and have built-in energy storage to reduce computation power, resulting in very low overall power dissipation. CNEMS have stable on-off state and latching mechanism for non-volatile memory-mode operation. Besides, the devices can be readily integrated in the same substrate as CMOS transistors with high integration densities - thus, allowing easy manufacturability and hybridization with conventional CMOS devices. In this paper, we present the properties of these devices and based on our analysis, we propose a reconfigurable computation framework using these devices. For the first time, we demonstrate that these devices are promising in dynamically reconfigurable instant-on system development with about 25times lower power dissipation.

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.

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

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.

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.

In this paper, a new approach for generating test vectors that detects faults in combinational circuits is introduced. The approach is based on automatically designing a circuit which implements the D-algorithm, an automatic test pattern generation (ATPG) algorithm, specialized for the combinational circuit. Our approach exploits fine-grain parallelism by performing the following in three clock cycles: direct backward/forward implications, conflict checking, selecting next gate to propagate fault or to justify a line, decisions on gate inputs, and loading the state of the circuit after backup. In this paper, we show the feasibility of this approach in terms of hardware cost and speed and how it compares with software-based techniques.

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

In this paper, we introduce a new approach for locating and diagnosing faults in combinational circuits.The approach is based on automatically designing a circuit which implements a closest-match fault location algorithm specialized for the combinational circuit under diagnosis (CUD).This approach eliminates the need for large storage required by a software based fault diagnosis.In this paper, we show the approach's feasibility in terms of hardware resources, speed, and how it compares with software based techniques.

In this paper, a new approach for generating test vectors that detects faults in combinational circuits is introduced. The approach is based on automatically designing a circuit which implements the D-algorithm, an automatic test pattern generation (ATPG) algorithm, specialized for the combinational circuit. Our approach exploits fine-grain parallelism by performing the following in three clock cycles: direct backward/forward implications, conflict checking, selecting next gate to propagate fault or to justify a line, decisions on gate inputs, loading the state of the circuit after backup. In this paper, we show the feasibility of this approach in terms of speed, and how it compares with software based techniques.

To reduce total chip production costs, circuits must be more testable. Several design for testability schemes which tradeoff various design parameters have been proposed toward that end. The recently proposed partial reset (PR) method is incorporated. Rather than allowing all memory elements in a sequential circuit to be reset by a primary input, only a subset of them is given the capability to reset. PR has less hardware overhead and typically smaller test application times than scan design, PR, furthermore, allows unrestricted at-speed testing. The tradeoff is in slightly lower testability. A dynamic PR flip flop selection method is described utilizing a fast sequential test generator. The automated system developed in this research works closely with the test generator to insert PR, observability enhancements and partial scan into a given circuit. The result is higher fault coverage than is possible with PR alone and faster test application times than scan design. Results are shown on all ISCAS'89 circuits, up to s9234. Even though multiple runs of test generation is performed, CPU times are comparable to a single run of conventional deterministic automatic test pattern generations.

In this paper, we introduce a new approach for locating and diagnosing faults in sequential circuits. The approach is based on automatically designing a circuit which implements a closest match fault location algorithm specialized for the sequential circuit under diagnosis. Our result shows an order of magnitude improvements in term of speeds over software based fault location.

A general method for determining whether a certain design is initializable, and for generating its initialization sequence, is presented in this paper. This method is based on structural decomposition of the circuit, and can handle both logical (using X-value simulation) and functional initializability. The routines developed are then used for ATPG of sequential circuits.

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.

A system which adds DFT and generates test vectors for the enhanced circuit is described. Partial reset, observability enhancement and partial scan are employed. A dynamic partial reset flip-flop selection method is described utilizing a fast genetic algorithm based sequential test generator. This system trades off various parameters to obtain high fault coverage, low test application times, low hardware overhead and low CPU time.

Switch-level simulation provides a good level of abstraction for simulating digital MOS circuits. For handling large circuits, it is often necessary to represent parts of the circuit by high-level software models, in order to speed up the simulation process. This paper, considers hierarchical switch-level circuits, and investigates the use of extracted functional models at different levels in the hierarchy to increase the efficiency of simulation. A comparative study, on some sample circuits, is used to determine the ideal size of a module that should be simulated using its functional model.>

A general method for determining whether a certain design is initializable, and for generating its initialization sequence, is presented. This method is based on structural decomposition of the circuit, and can handle both logical (using X-value simulation) and functional initializabilities. Results for some benchmark circuits are also presented.

In this paper, a behavioral synthesis for testability system is presented. In this system, a testability modifier is connected to an existing behavioral level synthesis program, which accepts a circuit's behavioral description in C or VHDL as input. The outline of the system is as follows: (1) a testability analyzer is first applied to identify the hard-to-test areas in the circuit from the behavioral description; (2) a selection process is then applied to select test points or partial scan flip-flops. Selection is based on behavioral information rather than low-level structural description. This allows test point insertion or partial scan usage on circuits described as an interconnection of high level modules; (3) test statement insertion (TSI), an alternative to test point insertion and partial scan, is used to modify the circuit based on the selected test points. The major advantage of using TSI is a low pin count and test application time as compared to test point insertion and partial scan. In addition, TSI can be applied at the early design phase. This approach was implemented in a computer program, and applied to several sample circuits generated by a synthesis tool. The results are also presented.>

The paper presents a methodology for the simulation of massive number of device-level transient faults. Fault injection locations and the gate around those locations are extracted and evaluated with SPICE. The extracted sub-circuits are exercised exhaustively while fault-injections are performed. Faulty behavior at the outputs of each sub-circuit is recorded in a dictionary, along with the associated input vector, fault-injection time, and location. The recorded logical errors are injected concurrent transient simulator is developed to allow simultaneous evaluation of a massive number of fault-injections, in a single simulation pass. The methodology is illustrated by a case study of MC68000 microprocessor.

Diminishing the cost of testing digital VLSI circuits is the goal of design for testability (DFT) techniques. Recently, a new approach called partial reset has been added to the suite of DFT techniques. Only a subset of the flip-flops are capable of resetting. This approach obtained reasonably high coverage. We show that controllability is further enhanced by using multiple reset lines. The configuration of these multiple reset lines is described. This technique has been evaluated on the 1989 ISCAS sequential benchmark circuits, and the results are discussed.

Redundant Arrays of Distributed Disks (RADD) can be used in a distributed computing system or database system to provide recovery in the presence of disk crashes and temporary and permanent failures of single sites. In this paper, we look at the problem of partitioning the sites of a distributed storage system into redundant arrays in such a way that the communication costs for maintaining the parity information are minimized. We show that the partitioning problem is NP-hard. We then propose and evaluate several heuristic algorithms for finding approximate solutions. Simulation results show that significant reduction in remote parity update costs can be achieved by optimizing the site partitioning scheme.

We study the performance of two redun dant disk array organizations in a transaction processing environment and compare it to that of mirrored disk organi zations and organizations using no striping and no redun dancy. Redundant disk arrays and mirrored disks are used for providing rapid recovery from mediafailures in systems requiring high availability. The disk array organizations examined are: data striping with rotated parity (RAIDS) and Parity Striping. RAIDS provides high data transfer rates by striping the data over multiple disks. It also pro vides better load balancing over the disks in the array. At the same time, data striping increases disk arm use which can lead to longer queuing delays. In transaction process ing environments, because of the nature of I/O requests, namely a large number of small size requests, disk arms are a more valuable resource than data transfer bandwidth. Hence, parity striping was proposed as an alternative to RAIDS. It provides rapid recovery from failure at the same low storage cost without interleaving the data over multiple disks. In this study, we use data from a large scale commer cial transaction processing site to evaluate and compare the performance of the above organizations. We consider both non-cached systems as well as systems using a non-volatile cache in the controller.

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.>

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.>

In this paper a new approach, called BETA, for computing testability is presented. The approach is based on analyzing the circuit's behavioral description: the control flow graph (CFG). Based on path analysis, testability measures are derived. Unlike a traditional testability measure which computes testability, our approach also derives the exact sequence for justifying and propagating the contents of each variable when possible. Variable classification is used to diagnose every register's controllability and observability and to classify them into several groups. Based upon this classification, guidance is provided to the test generator for each group. Variable classification is also useful in pointing out hard-to-control and hard-to-observe areas of a circuit. For fully controllable and observable variables, the best path sequence to justify and propagate these registers is generated. This approach has been implemented in a computer program and applied to several examples. All these results are verified by a CFG-based test generator and proven to be successful.>

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.>

A method for switch-level timing simulation of bipolar emitter-coupled-logic (ECL) circuits is presented. The approach is based on the development of a switch level model of the transistor and on the representation of the circuit by a switch-graph. The circuit is partitioned into subcircuits, and the symbolic logic expressions, which represent the logic states of the nodes in terms of subcircuit inputs and initial conditions, are then generated. Timing information is computed using a new physical delay model based on device equations, transistor interconnection, input slew rate, and loading conditions. The delay model was derived on the basis of average branch current analysis and incorporates more than 15 delay-sensitive circuit and SPICE BJT model parameters. The use of a novel parametric correction scheme permits greater freedom to handle complex effects such as high-level injection, parasitic resistances, and interconnection delay. In addition, the dynamic fanout effects due to base leakage current are incorporated by a fanout collapsing technique.>

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 new parallel-concurrent fault simulation algorithm based on the partitioning of faults into groups, with the group size equal to the number of bits in the host computer word, is presented. The fault effects of a particular group are evaluated using parallel fault simulation techniques and propagated using concurrent fault simulation techniques. The speed of the algorithm depends on the circuit and on the fault-grouping criterion. An automatic grouping criterion is devised to group faults that are "close" or nearly equivalent. Comparisons to the concurrent, to the deductive, and to the PROOFS fault simulation techniques are performed on a SPARC SLC with 16 MB of memory running UNIX. ISCAS89 benchmark circuits are used for this comparison.>

A synthesis for testability approach is presented. In this approach test points or flip-flops to be used in test point insertion or partial scan to enhance circuit testability are selected. The selection is based on circuit behavioral information rather than low level structural description. This allows test point insertion or partial scan usage on circuits described as interconnections of high level modules. Test statement insertion is also proposed as an alternative to test point insertion and to partial scan. The major advantage of using test statement insertion is a lower pin count and lower test application time overhead than test point insertion and partial scan. The tool has been implemented in a computer program.>

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.>

A method for extracting functional models from the switch- (or gate-) level description of a circuit is presented. Model extraction is done incrementally while the hierarchical structure of the circuit is maintained. Extracted models are represented by Boolean functions that are compiled and linked to the simulator. A prototype simulator was implemented within the CHAMP framework. Simulations using extracted models executed 2.5 to 3 times faster than ordinary switch-level simulations without any loss of accuracy.>

The authors propose a method for using redundant disk arrays to support rapid recovery from system crashes and transaction aborts in addition to their role in providing media failure recovery. A twin-page scheme is used to store the parity information in the array, making it possible to keep the old version of the parity along with the new version. The old version of the parity is used to undo updates performed by aborted transactions or by transactions interrupted by a system failure. Using an analytical model, it is shown that the proposed method achieves a significant increase in the throughput of database systems using redundant disk arrays by reducing the number of recovery operations needed to maintain the consistency of the database.>

Metal oxide semiconductor (MOS) technology is highly popular currently due to the many advantages that it provides. It has been shown that conventional methods of testing are not applicable to MOS circuits. A switch-level model is used to generate a sequence of test vectors for a variety of MOS circuits, including those containing pass transistor logic.>

An approach, Beta, for computing testability is presented. This approach is based on analyzing the circuit's behavior description data flow graph (DFG). First, each path in the DFG is analyzed to find the set of paths to justify and propagate each data register. Then, register classification follows to diagnose every register's controllability and observability and classify them into several groups. For the most controllable and observable registers, Beta, unlike other testability methods which compute only testability, also tries to derive the exact sequence for justifying and propagating each register. Register classification is also useful in pointing out hard-to-control and hard-to-observe areas of the circuit. This approach has been implemented in a computer program and applied to several examples. These results are verified by a DFG-based test generator and proven to be successful.>

Increasing the accessibility of an internal circuit node is one way to achieve design for testability. An algorithm for accessibility analysis based on a data flow graph (DFG) is presented. Based on this analysis, an approach is proposed for improving total accessibility. This is accomplished by selecting the minimum set of circuit nodes that need to be made accessible to ensure that all other nodes are accessible. A simple modification to the DFG that increases accessibility is presented.>

The problems of synchronizing communication and clock distribution to various circuit parts has led to interest in self-timed circuits, particularly in ASIC signal processing designs. Self-timed circuits employ computational components which generate completion signals to indicate that their data are available for use by other circuit components. Therefore, other circuit components wait for completion signals rather than clock signals. One of the drawbacks of self-timed circuits is that they are difficult to test because they are asynchronous. This paper is concerned with a class of self-timed systems because each logic components generate its completion signals automatically. This paper studies the behaviour of DCVSL logic in the presence of physical faults. Based on this behaviour, the authors present a switch-level test generation algorithm for DCVSL circuits. Finally, they present a scan approach suitable for self-timed systems.>

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.>

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 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.>

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.

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.>

A fault simulation algorithm based on the partitioning of faults into groups, with the group size equal to the number of bits in the host computer word, is presented. The fault effects of a particular group are evaluated using parallel fault simulation techniques and propagated using concurrent fault simulation techniques. The speed of the algorithm depends on the circuit and on the fault-grouping criterion. Three static grouping criteria are examined and compared in terms of speed and memory requirements. A dynamic regrouping technique is developed and is shown to improve the performance of static grouping.>

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.>

This paper describes a new approach for logic simulation of bipolar digital circuits. The approach is based on the development of a switch-level model of the transistor and on representing the circuit by a switch-graph. The method automatically partitions the circuit into subcircuits, and symbolic logic expressions are then generated which represent the logic states of the nodes in terms of subcircuit inputs and initial conditions. The method thus extracts a gate-level functional description of the circuit from transistor netlist or layout. Logic and fault simulation can then be performed using either extracted logic expressions or the switch-graph model. The approach has been implemented in a computer program for logic simulation of common-mode logic (CML) bipolar circuit designs.