Today's leading chip and system companies are faced with ever increasing design verification challenges; industry studies reveal that as much as 50% of the total schedule is being spent in verification. Large companies, with almost infinite resources, have shown that throwing CPU cycles and people at the simulation problem still doesn't guarantee a level of coverage desired by the design team.

Procedures for Boolean satisfiability most commonly work with Conjunctive Normal Form. Powerful SAT techniques based on implications and conflicts can be retained when the usual CNF clauses are replaced with BDDs. BDDs provide more powerful implication analysis, which can reduce the computational effort required to determine satisfiability.

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.

Symbolic simulation is a formal verification technique which combines the flexibility of conventional simulation with powerful symbolic methods. Some constructs, however, which are easy to handle in conventional simulation need special consideration in symbolic simulation. This paper discusses some special constructs that require unique treatment in symbolic simulation such as the symbolic representation of arrays, an efficient This paper discusses some special constructs that are unique to symbolic simulation such as the symbolic representation of arrays, an efficient symbolic method for storing arrayed instances and the handling of symbolic data-dependent delays. We present results which demonstrate the effectiveness of our symbolic array model in the simulation of highly regular structures like FPGAs, memories or cellular automata.

Symbolic simulation is a promising formal verification technique combining the flexibility of conventional simulation with powerful symbolic methods. Unfortunately, existing symbolic simulators are restricted to gate level simulation or handle just a synthesizable subset of an HDL. Simulation of systems composed of design, testbench and correctness checkers, however, requires the complete set of HDL constructs. We present an approach that enables symbolic simulation of the complete set of RT-level Verilog constructs with full delay support. Additionally, we propose a flexible scheme for introducing symbolic variables and demonstrate how error traces can be simulated with this new scheme. Finally, we present some experimental results on an 8051 micro-controller design which prove the effectiveness of our approach.

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.

We present Ketchum, a tool that was developed to improve the productivity of simulation-based functional verification by providing two capabilities: (1) automatic test generation and (2) unreachability analysis. Given a set of "interesting" signals in the design under test (DUT), automatic test generation creates input stimuli that drive the DUT through as many different combinations (called coverage states) of these signals as possible to thoroughly exercise the DUT. Unreachability analysis identifies as many unreachable coverage states as possible.

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.

The paper describes some of the synthesis controls in the BooleDozer synthesis system which are unique in concept and implementation. Rather than attempting to achieve the maximum amount of optimization in the minimum amount of run time, the designer specifies the restructuring level which allows him to specify to what extent the original structure should be preserved. We also describe controls which affect the mapping process. Finally we describe the incremental synthesis feature. The run time can be accurately controlled by a run-time budgeting mechanism.>

This paper presents the timing verification and optimization tools used for the 601, 603, 604 and 620 PowerPC processor designs. The timing verification is done by static timing analysis at the chip level, while the timing optimization is done by synthesis at the macro level. A method for automatically deriving timing constraints for timing optimization is described.>

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

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

A combinatorial logic optimization is described. The optimization is (in some sense) a dual of earlier global flow optimizations. The optimization leaves the function carried by each signal in the circuit unchanged and thus avoids expensive recomputation of don't care information. The results of experiments performed to evaluate this optimization are also described.>

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