Browse Prior Art Database

Simulation Algorithm

IP.com Disclosure Number: IPCOM000046034D
Original Publication Date: 1983-May-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Butler, RW: AUTHOR [+4]

Abstract

This simulator evaluates test coverage and provides diagnostic data for VLSI (very large-scale integration) structures. It provides significant performance improvement over previous techniques for structures in the range of 200 to 4000 gates. It is capable of providing full stuck-fault simulation on structures on the order of 30,000 gates. CPU time reductions on the order of 20 to 1 have been experienced on very large structures (200 hours reduced to 10 hours).

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 2

Simulation Algorithm

This simulator evaluates test coverage and provides diagnostic data for VLSI (very large-scale integration) structures. It provides significant performance improvement over previous techniques for structures in the range of 200 to 4000 gates. It is capable of providing full stuck-fault simulation on structures on the order of 30,000 gates. CPU time reductions on the order of 20 to 1 have been experienced on very large structures (200 hours reduced to 10 hours).

The simulator is a single-pass parallel fault simulator incorporating deductive look-ahead techniques.

The primary innovation in this simulator is the development of single-pass parallel fault simulation. This was made possible by exploiting ideas derived from three separate areas: Deductive Simulation, Logic Partitioning and Parallel Fault Simulation.

One of the first efforts directed at improvement of the speed of fault simulation was the deductive simulation algorithm (see IBM Tech -nical Disclosure Bulletin 13, 3433 (April 1971) and IEEE Transactionson Computers C- 21, 464 (May 1972)).

A parallel fault simulator uses the bits in the computer word to store, in parallel, the states for faulty copies of the network being simulated; the deductive technique uses a fault list to contain the information on the faulty copies. Advanced development work on a purely deductive simulator revealed two problems that severely limited the applicability of this technique.

1. The size of the fault lists necessitated

complicated sharing and list structures.

2. The deductive algorithms require calculation of

the Union and Intersection of these fault lists. These

calculations involved looping through the fault lists

in a way that further complicated the code and impacted

performance.

Earlier work in large logic structure partitioning resulted in the compressed bit string format for storing fault lists. (The technique of logic structures partitioning is fully described in Proc14th D...