Method and apparatus for sampling and predicting rare events in complex electronic devices, circuits and systems

• US 8,155,938 B2
• Filed: 03/28/2008
• Issued: 04/10/2012
• Est. Priority Date: 03/28/2008
• Status: Expired due to Fees

• Current Assignee: Carnegie Mellon University
• Original Assignee: Carnegie Mellon University
• Inventors: Singhee, Amith, Rutenbar, Rob
• Primary Examiner(s): Rodriguez, Paul
• Assistant Examiner(s): Kim, Eunhee
• Application Number:
  US12/057,537
• Publication Number:
  US 20090248387A1
• Time in Patent Office: 1,474 Days
• Field of Search: 703/6
• US Class Current: 703/6
• CPC Class Codes: G06F 2111/08 Probabilistic or stochastic CAD
• CPC Class Codes: G06F 30/367 Design verification, e.g. using simulation, simulation program with integrated circuit emphasis [SPICE], direct methods or relaxation methods

Abstract

The invention provides methods for enhancing circuit reliability under statistical process variation. For highly replicated circuits such as SRAMs and flip flops, a rare statistical event for one circuit may induce a not-so-rare system failure. To combat this, the invention discloses the method called “Statistical Blockade,” a Monte Carlo-type technique that allows the efficient filtering—blocking—of unwanted samples insufficiently rare in the tail distributions of interest, with speedups of 10-100×. Additionally, the core Statistical Blockade technique is further extended in a “recursive” or “bootstrap” formulation to create even greater efficiencies under a much wider variety of circuit performance metrics, in particular two-sided metrics such a Data Retention Voltage (DRV) which prior Monte Carlo techniques could not handle.

Claims

1. A method for simulating the effect of events of interest in a manufacturing process, the manufacturing process being susceptible to simulation, the method comprising the steps of:

(a) generating a first randomly chosen sample of possible events;

(b) performing the manufacturing process simulation on each of the events in the first randomly chosen sample;

(c) using the results from step (b) to generate a classifier;

(d) generating a second randomly chosen sample of possible events;

(e) applying the classifier to each of the events in the second randomly chosen sample, the classifier yielding rareness values for each of the events;

(f) comparing the rareness values with a predefined rareness threshold, thereby identifying events among the second randomly chosen sample that are rarer than the predefined threshold;

(g) carrying out manufacturing simulations of the events identified in step (f), yielding results thereof; and

(h) providing to a human user the results of the manufacturing simulations.

2. The method of claim 1, wherein the manufacturing process is a process for manufacture of static random-access memory chips.

3. The method of claim 1, wherein the simulations include SPICE simulations.

4. The method of claim 1, wherein the simulations include simulations of reliability.

5. A method for use with respect to a manufacturing process, the manufacturing process susceptible to simulation, the method comprising the steps of:

(a) generating a first random sample of possible events;

(b) performing the manufacturing simulation on the events in the first random sample;

(c) using results from (b) to build a first classifier;

(d) generating a second random sample of possible events;

(e) applying the first classifier to the second random sample, yielding a subset of the second sample;

(f) performing the manufacturing simulation on the subset of the second random sample;

(g) using results from (f) to build a second classifier;

(h) generating a third random sample of possible events;

(i) applying the second classifier to the third sampling, yielding a subset of the third sampling;

(j) carrying out the manufacturing simulations on events in the subset of the third sampling, yielding results thereof; and

(k) providing to a human user the results of the simulations.

6. The method of claim 5, wherein the manufacturing process is a process for manufacture of static random-access memory chips.

7. The method of claim 5, wherein the manufacturing simulations include SPICE simulations.

8. The method of claim 5, wherein the manufacturing simulations include a simulation of reliability.

9. A method for use with respect to a manufacturing process, the manufacturing process susceptible to simulation, the method comprising the steps of:

(a) obtaining a first random sampling of possible events with respect to the manufacturing process;

(b) applying a plurality of classifiers to the random sampling of possible events, each classifier derived from manufacturing simulations of previous randomly sampled events, each classifier yielding respective rareness values for each of the possible events;

(c) comparing each respective rareness value with a predefined respective rareness threshold, identifying events among the random sampling of possible events that are rarer than the respective predefined threshold;

(d) for each of the random sampling of possible events, evaluating a logical expression which is a function of the classifiers;

(e) carrying out manufacturing simulations with respect to the events for which the logical expression yields a predetermined value, yielding results thereof; and

(f) providing to a human user the results of the simulations.

10. The method of claim 9, wherein:

the number of classifiers is two, thereby defining a first classifier and a second classifier; and

the logical expression is an “

and”

function, whereby the carrying out of a simulation with respect to an event takes place only if the first classifier identifies the event as being rarer than the respective predefined threshold of the first classifier, and if the second classifier identifies the event as being rarer than the respective predefined threshold of the second classifier.

11. The method of claim 9, wherein:

the number of classifiers is two, thereby defining a first classifier and a second classifier; and

the logical expression is an “

or”

function, whereby the carrying out of a simulation with respect to an event takes place only if the first classifier identifies the event as being rarer than the respective predefined threshold of the first classifier, or if the second classifier identifies the event as being rarer than the respective predefined threshold of the second classifier.

12. The method of claim 9, wherein the random sampling of possible events is further characterized as Monte Carlo sampling.

13. The method of claim 9, wherein the manufacturing process is a process for manufacture of static random-access memory chips.

14. The method of claim 9, wherein the manufacturing simulations include SPICE simulations.

15. The method of claim 9, wherein the manufacturing simulations include simulations of reliability.