Previous results show that both flat and hierarchical methodologies present obstacles to effectively completing combinational equivalence checking. A new approach that combines the benefits while effectively dealing with the pitfalls of both styles of equivalence checking is presented.

This paper presents four new powerful SAT optimization techniques: partial clauses, back-leaps, immediate implications and local decisions. These optimization techniques can be combined with SAT mechanisms used in Chaff, SATO, and GRASP to develop a new solver that significantly outperforms its predecessors on a large set of benchmarks. Performance improvements for standard benchmark groups vary from 1.5x to 60x. Performance improvements measured using VLIW microprocessor benchmarks amount to 3.31x.

This paper presents performance results for a new SAT solver designed specifically for EDA applications. The new solver significantly outperforms most efficient SAT solvers-Chaff, SATO, and GRASP-on a large set of benchmarks. Performance improvements for standard benchmark groups vary from 1.5/spl times/ to 60/spl times/. They were achieved through a new decision-making strategy and more efficient Boolean constraint propagation (BCP).

In this paper, we examine delay models used in very large scale integration (VLSI) circuit testing. Our study is based on electrical-level simulation experiments. We present a comprehensive analysis of phenomena which significantly affect the actual delays but are not taken into account by the existing models used in testing. Because of these phenomena, for a given path in a circuit, tests commonly considered equivalent may result in different pass/fail decisions. Moreover, contrary to a common assumption, robust tests may fail to detect faults detectable by nonrobust tests. This may happen even in circuits in which all paths are robust testable. Our analysis questions the test quality offered by delay test procedures used so far.

We show that a path delay under a non-robust test may be longer than under any robust test. Thus, for a given path, a non-robust test can detect a delay fault undetectable by robust tests. This can happen even in a circuit in which all paths are robust-testable.

In this paper, we study the properties of all major counter-based compaction schemes when the circuit under test is affected by delay or stuck-open faults. We present an error model that accurately describes the behavior of such circuits. The error model inherits from the asymmetric error model. Using this model, we compute exact aliasing probability for any test session length; we also determine the asymptotic aliasing probability. Examples that compare aliasing in counter-based compaction with aliasing in LFSRs indicate that the latter is more "predictable".>

For the original article see ibid., vol. 10, no. 3, p. 390-98 (1991). In the aforementioned paper by S. Sastry and A. Majumdar the testing effectiveness of random pattern techniques is studied and the authors claim to give complete analytical solutions to the problem of estimating such an effectiveness. The commenters point out that the analysis is based on an oversimplified circuit model, and, therefore, the conclusions are invalid. They comment on the analysis and explain its weakness, especially with respect to the built-in self-test (BIST) technique referred to as circular self-test path (CSTP).>

We propose simple modifications to existing BIST schemes. These modifications significantly improve the path delay fault coverage. For example, a modified circular self-test path can detect a significant number of path delay faults within a reasonable test running time.>

Many results regarding the probability of aliasing for multiple-input compactors have been derived under error assumptions that are not very realistic for VLSI circuits. Recently, the value of aliasing probability has been proven to tend to 2/sup -k/, where k is the number of binary memory elements of the linear compactor. This result is based on the assumption that the compactor is characterized by an irreducible polynomial and that the 'no error' vector has a probability different from zero. In these notes, the above result is generalized. More specifically, it is proved that it is valid if any two error vectors, neither of which needs to be the 'no error' vector, have probabilities of occurrence different from zero. To make the error model complete, the situation in which exactly one error vector has a probability different from zero is also considered. For the latter type of error distributions, the test lengths at which aliasing occurs are determined. Simple proofs for the results are provided; they are based on standard linear algebra notions and well-known theorems.>

Aliasing is studied for delay and stuck-open faults. It is shown that, as the test sequence length is increased, the probability of aliasing for such faults tend to 2/sup -k/, where k is the number of binary memory elements in a linear compactor. The result is based on the assumption that the linear compactor has an irreducible characteristic polynomial. Some recent results on combinational faults are special cases of the results presented here.>

We show how to design a self-testable RAM using the Circular Self-Test Path technique. The proposed solution, which implements the idea of random testing, offers much higher test quality than deterministic RAM self-test schemes. A 256-Kbit embedded memory can be efficiently tested within 1 second. Such a memory is tested concurrently with other VLSI chip modules.

Proposes a new easily testable PLA. In the design process the authors use a simple property of relatively prime numbers. The PLA can be efficiently integrated with random pattern techniques used for testing combinational circuits. In the proposed implementation, test pattern generation and test response compaction are performed by circular self-test path (circular BIST). Very high fault coverage can be achieved in a feasible testing time.>

The effectiveness of a random built-in self-test technique for VLSI circuits is studied. This technique, called the circular self-test path (CSTP), is applicable to circuits that consist of combinational blocks and registers. In particular, the effectiveness of test pattern generation, the effectiveness of test response compaction and fault coverage are examined. The test generation effectiveness is evaluated by the fraction of all possible test patterns applied during a testing session to the circuit under test. The compaction effectiveness of the CSTP technique is measured by the probability of aliasing, and fault coverage by the fraction of all permanent faults that are detected. For all these measures, simple formulas are developed, which give very accurate estimations without detailed circuit simulation. To demonstrate their accuracy, the estimates obtained by the formulas are compared to the results obtained by extensive simulation experiments.>

Checkpointing in a distributed database system is analyzed by establishing a correspondence between consistent snapshots in a general distributed system and transaction-consistent checkpoints in a distributed database system. The analysis culminates in a useful condition for transaction-consistent checkpoints. Based on this condition, a general checkpointing scheme, which records a transaction-consistent set of values of all or some selected data items is presented. These rules are implemented in some representative concurrency control protocols, i.e., those based on two-phase locking and timestamping. These implementations cause little interference with other activities in the database system.>

We present a new checkpointing scheme for a distributed database system. Our scheme records the states of some selected data items and can be executed at any time without stopping other activities in the database system. It makes use of “shadows” of data items to make sure that the collected data item values are “transaction-consistent”. Storage overhead is low, since at most one shadow is needed for each data item.

A technique for designing self-test VLSI circuits, referred to as circular self-test path (CSTP), is introduced. The CSTP is a feedback shift register (output of the last flip-flop is supplied to the first flip-flop) with a data communication capability. It serves simultaneously for test pattern generation and test response compaction, thereby minimizing the test schedule complexity; the whole chip is tested in a single test session. A distinguishing attribute of built-in self-test (BIST) chips designed using this technique is a low silicon area overhead, slightly exceeding that of scan path designs, but substantially lower than that of built-in logic block observer (BILBO)-based circuits. Theoretical and simulation studies were performed to demonstrate that the test pattern generation efficiency of the CTSP is comparable to that of a pseudorandom generator, regardless of the functionality of the circuit under test.>

A new technique for designing self-testing VLSI circuits, referred to as Circular Self-Test Path, is presented The Circular Self-Test Path is a feedback shift register (output of the last flip-flop is supplied to the first flip-flop) with a data compaction capability. A distinguishing attribute of self-testing chips designed using this technique is a low silicon area overhead, slightly exceeding that of scan path designs. A theoretical analysis and comprehensive simulation experiments we performed to demonstrate that the effectiveness of test pattern generation for the circular self-test path is comparable to that of an ideal pseudorandom test generator.