We present a method for using a set of temporal properties (SVA, PSL, OVA, RTL monitors) as environment models for industrial-strength hybrid verification that combines formal methods with constrained random simulation. We demonstrate the effectiveness of the method on real-world designs.

An important step in using combinational equivalence checkers to verify sequential designs is identifying and matching corresponding compare-points in the two sequential designs to be verified. Both non-function and function-based matching methods are usually employed in commercial verification tools. In this paper, we describe a heuristic algorithm using ATPG for matching comparepoints based on the functionality of the combinational blocks in the sequential designs. Results on industrial-sized circuits show our methods are both practical and efficient.

We present RFN, a formal property verification tool based on abstraction refinement. Abstraction refinement is a strategy for property verification. It iteratively refines an abstract model to better approximate the behavior of the original design in the hope that the abstract model alone will provide enough evidence to prove or disprove the property.

Traditional ASIC design flows have treated logic synthesis and physical design as separate steps in the flow. A recent trend in design automation has been to integrate placement and logic synthesis operations for designs that strive for high performance. The motivation for this is ascribed to achieving timing convergence. These efforts attempt a brute-force combination of techniques from the two fields. We present an architecture for combining synthesis transforms with rough placement. There are three main contributions of this paper. First we present a system architecture that permits a clean separation of placement and synthesis issues and combines the two solutions in an elegant manner. Second, we propose a minor modification to the current ASIC design flow to enable timing convergence. Third, we use design rules for correct circuit operation to drive the placement and the synthesis components of the system. We present results for a set of high performance ASIC designs which demonstrate the practicality of our method.

Most sequential ATPG (automatic test pattern generation) programs employ the time-frame expansion technique. Within a time-frame, combinational test generation algorithms that are variations of D-algorithm or PODEM are used. Here, it is shown that some ATPG programs may err in identifying untestable faults. In other words, these test generators may not be able to find the test sequence for a testable fault, even allowed infinite run time, and furthermore may mistakenly claim it as untestable. The main problem of these programs is that the underlying combinational test generation algorithm may overspecify the requirements at the present state lines. The authors present a necessary condition that the underlying combinational test generation algorithm must satisfy to ensure a correct sequential ATPG program. It is shown that the simple D-algorithm satisfies this condition while PODEM and the enhanced D-algorithm do not. The impact of overspecification on the length of the generated test sequence is also studied. Overspecification causes a longer test sequence. Experimental results are presented.>

An outline is presented of a synthesis procedure that, beginning from a state transition graph (STG) description of a sequential machine, produces an optimized easily testable programmable logic array (PLA) based logic implementation. Previous approaches to synthesizing easily testable sequential machines have concentrated on the stuck-at-fault model; for PLAs, an extended fault model called the crosspoint fault model has been used. The authors propose a procedure of constrained state assignment and logic optimization which guarantees testability for all combinationally irredundant crosspoint faults in a PLA-based finite-state machine. No direct access to the flip-flops is required. The test sequences to detect these faults can be obtained using combinational test generation techniques alone. This procedure thus represents an alternative to a scan design methodology. Results are presented which show that the area/performance penalties in return for easy testability are small.>

It is shown that optimal sequential logic synthesis can produce irredundant, fully testable finite-state machines. Synthesizing a sequential circuit from a state transition graph description involves the steps of state minimization, state assignment, and logic optimization. Previous approaches to producing fully and easily testable sequential circuits have involved the use of extra logic and constraints on state assignments and logic optimization. Here it is shown that 100% testability can be ensured without the addition of extra logic and without constraints on the state assignment and logic optimization. Unlike previous synthesis approaches to ensuring fully testable machines, there is no area/performance penalty associated with this approach. This technique can be used in conjunction with previous approaches to ensure that the synthesized machine is easily testable. Given a state-transition-graph specification, a logic-level automaton that is fully testable for all single stuck-at faults in the combinational logic without access to the memory elements is synthesized.>

The authors explore the relationships between redundant logic and don't care conditions in sequential circuits. Stuck-at faults in a sequential circuit may be testable in the combinational sense but may be redundant because they do not alter the terminal behavior of a nonscan sequential machine. These sequential redundancies result in a faulty state transition graph (STG) that is equivalent to the STG of the true machine. The authors present a classification of redundant faults in sequential circuits composed of single or interacting finite-state machines. Don't care sets can be defined for each class of redundancy, and optimally exploiting these don't care conditions results in the implicit elimination of any such redundancies in a given circuit. In cascaded and interconnected sequential circuits, sequential don't cares are required to eliminate redundancies. The authors present preliminary experimental results which indicate that by exploiting these don't cares medium-sized irredundant sequential circuits can be synthesized with no area overhead and within reasonable CPU times.>

The authors outline a synthesis procedure which beginning from a state transition graph (STG) description of a sequential machine produces an optimized fully and easily testable logic implementation. This logic-level implementation is guaranteed to be testable for all single stuck-at faults in the combinational logic and the test sequences for these faults can be obtained using combinational test generation techniques alone. The sequential machine is assumed to have a reset state and be R-reachable. All single stuck-at faults in the combinational logic and the input and output stuck-at faults of the memory elements in the synthesized logic-level automaton can be tested without access to the memory elements using these test sequences. Thus this procedure represents an alternative to a scan design methodology. The area penalty incurred due to the constraints on the optimization are small. The performance of the synthesized design is usually better than that of an unconstrained design optimized for area alone. The authors show that an intimate relationship exists between state assignment and the testability of a sequential machine. They propose a procedure of constrained state assignment and logic optimization which guarantees testability for both Moore and Mealy machines.>

LOgic VERification (LOVER) incorporates a novel approach to combinational logic verification and obtains excellent results when compared to existing techniques. The authors describe a new verification algorithm, LOVER-PODEM, whose enumeration phase is based on PODEM. A variant of LOVER-PODEM, called PLOVER, is presented. Parallel logic verification schemes have been developed for the first time. Issues in efficiently parallelizing both general and specific LOVER-based approaches to logic verification over a large number of processors are addressed. The parallelism inherent in the LOVER framework regardless of what enumeration and simulation algorithms are used is discussed. Since the enumeration phase is the efficiency bottleneck in parallelizing LOVER-based approaches, parallel versions of PODEM-based enumeration algorithms have been developed.>

A synthesis procedure is described that produces an optimized fully and easily testable logic implementation of a sequential machine from a state transition graph description of the machine. This logic-level implementation is guaranteed to be testable for all single stuck-at faults in the combinational logic. No access to the memory elements is required. The test sequences for these faults can be obtained using combinational test generation techniques alone. It is shown that an intimate relationship exists between state assignment and the testability of a sequential machine. A technique is also presented of don't-care minimization and added observability which ensures fully testable machines.>

An incomplete scan design approach to sequential test generation is presented. This approach represents a significant departure from previous methods. First, using an efficient sequential testing algorithm, test sequences are generated for a large number of possible faults in the given sequential circuit. A minimal subset of memory elements is then found, which if made observable and controllable will result in easy detection of the sequentially redundant and irredundant but difficult-to-defect faults. The deterministic test generation algorithm is again used to generate tests for these faults in the modified circuit (the circuit with the identified memory elements made scannable). Detection of all irredundant faults can be guaranteed as in the complete scan design case, but at significantly less area and performance cost.>

The techniques described have been implemented in a multilayer channel router called Chameleon. Chameleon consists of two stages: a partitioner and a detailed router. The partitioner divides the problems into two-layer and three-layer subproblems such that global channel area is minimized. The detailed router then implements the connections using generalizations of the algorithms used in YACR2 (see ibid., vol.CAD-4, no.3, p.208-19, 1985). In particular, a three-dimensional maze router is used for the vertical connections; this methodology is effective even when cycle constraints are present. Chameleon has produced optimal results on a wide range of industrial and academic examples for a variety of layer and pitch combinations, and can handle a variety of technology constraints.>

An algorithm is presented for the verification of the equivalence of two sequential circuit descriptions at the same of differing levels of abstraction, namely, at the register-transfer (RT) level and the logic level. The descriptions represent general finite automata at the differing levels. A finite automaton can be described in ISP-like language and its equivalence to a logic level implementation can be verified using this algorithm. Two logic-level automata can be similarly verified for equivalence. The technique is shown to be computationally efficient for complex circuits. The efficiency of the algorithm lies in the exploitation of don't care information derivable from the RT or logic-level description during the verification process. Using efficient cube enumeration procedures at the logic level, the equivalence of finite automata with a large number of states in small amounts of CPU time was verified. A two-phase enumeration-simulation algorithm for verifying the equivalence of two logic-level finite automata with the same or differing number of latches is also presented.>

The problem of state assignment for synchronous finite-state machines (FSM), targeted towards multilevel combinational logic and feedback register implementations, are addressed. The authors present state-assignment algorithms that heuristically maximize the number of common cubes in the encoded network to maximize the number of literals in the resulting combinational logic network after multilevel logic optimization. Results over a wide range of benchmarks which prove the efficacy of the proposed techniques are presented. Literal counts averaging 20%-40% less than other state-assignment programs have been obtained.>

An approach to test-pattern generation for synchronous sequential circuits is presented. The deterministic sequential test-generation algorithm, based on extensions to the PODEM justification algorithm, is effective for midsized sequential circuits and can be used in conjunction with an incomplete scan design approach to generate tests for very large sequential circuits. Tests for finite-state machines with a large number of states have been successfully generated using reasonable amounts of CPU time and close-to-maximum possible fault coverages have been obtained. For very large sequential circuits, an incomplete scan-design approach to test generation has been developed. The deterministic test generation algorithm is again used to generate test for faults in the modified circuit. All irredundant faults can be detected as in the complete scan design case, but at significantly less area and performance cost. The length of the test sequences for the faults can be bounded by a prescribed value-in general, a tradeoff exists between the number of memory elements required to be made scannable and the maximum allowed length of the test sequence.>

In this paper, an algorithm is presented for the verification of the equivalence of two sequential circuit descriptions at the same or differing levels of abstraction, namely at the register-transfer (RT) level and the logic level. The descriptions represent general finite automata at the differing levels - a finite automaton can be described in a ISP-like language and its equivalence to a logic level implementation can be verified using our algorithm. Two logic level automatons can be similarly verified for equivalence. Previous approaches to sequential circuit verification have been restricted to verifying relatively simple descriptions with small amounts of memory. Unlike these approaches, our technique is shown to be computationally efficient for much more complex circuits. The efficiency of our algorithm lies in the exploitation of don't care information derivable from the RTL or logic level description (e.g. invalid input and output sequences) during the verification process. Using efficient cube enumeration procedures at the logic level we have been able to verify the equivalence of finite automata with a large number of states in small amounts of CPU-time.

LOVER incorporates a novel approach to combinational logic verification and obtains good results when compared to existing techniques. In this paper we describe a new verification algorithm, LOVER-PODEM, whose enumeration phase is based on PODEM. A variant of LOVER-PODEM, called PLOVER, is presented. We have developed, for the first time, parallel logic verification schemes. Issues in efficiently parallelizing both general and specific LOVER-based approaches to logic verification over a large number of processors are addressed. We discuss parallelism inherent in the LOVER framework regardless of what enumeration and simulation algorithms are used. Since the enumeration phase is the efficiency bottleneck in parallelizing LOVER-based approaches, we have developed parallel versions of PODEM-based enumeration algorithms. Experimental results are presented to show that high processor utilization can be achieved when these parallelisms are exploited. Speed-up factors of over 7.8 have been achieved with 8 processor configurations.

New techniques for routing general multi-layer channels are introduced. These techniques can handle a variety of technology constraints. For example, linewidth and line-to-line spacing can be specified independently for each layer, and contact stacking can be allowed or forbidden. These techniques have been implemented in a new multi-layer channel router called Chameleon. Chameleon consists of two stages: a partitioner and a detailed router. The partitioner divides the problem into two and three-layer subproblems such that global channel area is minimized. The detailed router then implements the connections using generalizations of the algorithms used in YACR2. In particular a three-dimensional maze router is used which guarantees that any problem can be routed even when cyclic constraints are present. Chameleon produces optimal results on a wide range of industrial and academic examples for any number of layers and pitch combinations.

A Fault coverage estimation technique for mixed-level circuit is described. Observability formulae for combinational multiple-input multiple-output functional block are derived. Special procedures for estimating CMOS circuit transistor fault detection probability are developed, and the implementation of a FAult Coverage Estimation (FACE) system is described.