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

• US 20090248387A1
• Filed: 03/28/2008
• Published: 10/01/2009
• Est. Priority Date: 03/28/2008
• Status: Active Grant

• Current Assignee: Carnegie Mellon University
• Original Assignee: Carnegie Mellon University
• Inventors: Rutenbar, Rob, Singhee, Amith
• Granted Patent: US 8,155,938 B2
• Time in Patent Office: Days
• US Class Current: 703/16
• 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 use with respect to a manufacturing process, the manufacturing process susceptible to simulation of quality, the quality simulation being computationally costly, the method comprising the steps of:

performing a random sampling of possible events with respect to the manufacturing process;

applying a classifier to the random sampling of possible events, the classifier yielding rareness value for each of the possible events;

comparing the rareness values with a predefined rareness threshold, identifying events among the random sampling of possible events that are rarer than the predefined threshold;

carrying out simulations of quality with respect to the identified events, yielding results thereof; and

providing to a human user the results of the simulations;

whereby the computational cost of performing applying, comparing, and simulating steps is less than the computational cost of carrying out simulations of quality with respect to the random sampling of possible events.

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

3. The method of claim 1, wherein the computational cost of the performing, applying, comparing, and simulating steps is less than one-tenth of the computational cost of carrying out simulations of quality with respect to the random sampling of possible events.

4. The method of claim 1, wherein the computational cost of the performing, applying, comparing, and simulating steps is less than one-hundredth of the computational cost of carrying out simulations of quality with respect to the random sampling of possible events.

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

6. The method of claim 1, wherein the simulations of quality are performed using SPICE simulations.

7. The method of claim 1, wherein the simulation of quality comprises a simulation of reliability.

8. A method for use with respect to a manufacturing process, the manufacturing process susceptible to simulation of quality, the quality simulation being computationally costly, the method comprising the steps of:

performing a first random sampling of possible events with respect to the manufacturing process;

building a first classifier with respect to the first sampling, defining a first classification threshold indicating whether an event of the first sampling is in a tail or not;

performing a second random sampling of possible events with respect to the manufacturing process;

applying the first classifier to the second random sampling, yielding a subset of the second sampling;

building a second classifier with respect to the subset of the second sampling, defining a second classification threshold indicating whether an event of the subset of the second sampling is in a tail or not;

performing a last random sampling of possible events with respect to the manufacturing process;

applying the last classifier to the last sampling, yielding a subset of the last sampling;

carrying out simulations of quality with respect to the events in the subset of the last sampling, yielding results thereof; and

providing to a human user the results of the simulations;

whereby the computational cost of the performing, building, applying, and simulating steps is less than the computational cost of carrying out simulations of quality with respect to the random sampling of possible events.

9. The method of claim 8, further comprising the steps, carried out after the step of building a second classifier, and before the step of carrying out simulations, of:

performing a third random sampling of possible events with respect to the manufacturing process, and applying the second classifier to the third sampling, yielding a subset of the third sampling;

building a third classifier with respect to the subset of the third sampling, defining a third classification threshold indicating whether an event of the subset of the third sampling is in a tail or not.

10. The method of claim 9, further comprising the steps, carried out after the step of building a third classifier, and before the step of carrying out simulations, of:

performing a fourth random sampling of possible events with respect to the manufacturing process, and applying the third classifier to the fourth sampling, yielding a subset of the fourth sampling;

building a fourth classifier with respect to the subset of the fourth sampling, defining a fourth classification threshold indicating whether an event of the subset of the fourth sampling is in a tail or not.

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

12. The method of claim 8, wherein the computational cost of the performing, applying, comparing, and simulating steps is less than one-tenth of the computational cost of carrying out simulations of quality with respect to the random sampling of possible events.

13. The method of claim 8, wherein the computational cost of the performing, applying, comparing, and simulating steps is less than one-hundredth of the computational cost of carrying out simulations of quality with respect to the random sampling of possible events.

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

15. The method of claim 8, wherein the simulations of quality are performed using SPICE simulations.

16. The method of claim 8, wherein the simulation of quality comprises a simulation of reliability.

17. A method for use with respect to a manufacturing process, the manufacturing process susceptible to simulation of quality, the quality simulation being computationally costly, the method comprising the steps of:

performing a first random sampling of possible events with respect to the manufacturing process;

applying a plurality of classifiers to the random sampling of possible events, each classifier yielding respective rareness values for each of the possible events;

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;

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

carrying out simulations of quality with respect to the events for which the logical expression yields a predetermined value, yielding results thereof; and

providing to a human user the results of the simulations;

whereby the computational cost of the performing, applying, comparing, evaluating, and simulating steps is less than the computational cost of carrying out simulations of quality with respect to the random sampling of possible events.

18. The method of claim 17, 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 of reliability 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.

19. The method of claim 17, 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 of reliability 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.

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

21. The method of claim 17, wherein the computational cost of the performing, applying, comparing, and simulating steps is less than one-tenth of the computational cost of carrying out simulations of quality with respect to the random sampling of possible events.

22. The method of claim 17, wherein the computational cost of the performing, applying, comparing, and simulating steps is less than one-hundredth of the computational cost of carrying out simulations of quality with respect to the random sampling of possible events.

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

27. The method of claim 17, wherein the simulations of quality are performed using SPICE simulations.

28. The method of claim 17, wherein the simulation of quality comprises a simulation of reliability.