Statistical Design with Importance Sampling Reuse

• US 20120046929A1
• Filed: 08/20/2010
• Published: 02/23/2012
• Est. Priority Date: 08/20/2010
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Joshi, Rajiv V., Kanj, Rouwaida N., Nassif, Sani R., Radens, Carl J.
• Application Number:
  US12/859,871
• Publication Number:
  US 20120046929A1
• Time in Patent Office: Days
• US Class Current: 703/13
• CPC Class Codes: G06F 11/008 Reliability or availability analysis
• CPC Class Codes: G06F 11/076 by exceeding a count or rate limit, e.g. word- or bit count limit
• CPC Class Codes: G06F 11/079 Root cause analysis, i.e. error or fault diagnosis in a hardware test environment G06F11/22; in a software test environment G06F11/36
• CPC Class Codes: G06F 2111/08 Probabilistic or stochastic CAD
• CPC Class Codes: G06F 30/20 Design optimisation, verification or simulation optimisation, verification or simulation of circuit designs G06F30/30
• CPC Class Codes: G06F 30/33 Design verification, e.g. functional simulation or model checking
• CPC Class Codes: G06F 30/3308 using simulation

Abstract

A mechanism is provided for reusing importance sampling for efficient cell failure rate estimation of process variations and other design considerations. First, the mechanism performs a search across circuit parameters to determine failures with respect to a set of performance variables. For a single failure region, the initial search may be a uniform sampling of the parameter space. Mixture importance sampling (MIS) efficiently may estimate the single failure region. The mechanism then finds a center of gravity for each metric and finds importance samples. Then, for each new origin corresponding to a process variation or other design consideration, the mechanism finds a suitable projection and recomputes new importance sampling (IS) ratios.

Claims

1. A method, in a data processing system, for determining failure rate of a device using importance sampling reuse, the method comprising:

performing, by the data processing system, a uniform sampling over a random sample space for a metric for the device with respect to an origin to form a set of samples, wherein the set of samples comprises one or more failing samples;

determining, by the data processing system, a center of gravity of the one or more failing samples with respect to the origin;

determining, by the data processing system, importance samples based on the center of gravity of the one or more failing samples;

selecting a new origin;

recomputing, by the data processing system, new importance sampling weight ratios for the new origin; and

determining, by the data processing system, a failure rate for the device based on the new importance sampling weight ratios for the new origin.

2. The method of claim 1, wherein recomputing new importance sampling weight ratios for the new origin comprises:

finding a projected origin; and

recomputing new importance sampling weight ratios with respect to the projected origin.

3. The method of claim 2, wherein finding the projected origin comprises:

determining a line passing through the origin and the center of gravity of the one or more failing samples; and

projecting the new origin onto the line passing through the origin and the center of gravity of the one or more failing samples.

4. The method of claim 1, wherein recomputing new importance sampling weight ratios for the new origin comprises:

finding a set of projected samples with respect to the new origin; and

recomputing new importance sampling ratios based on the projected samples.

5. The method of claim 4, wherein finding the set of projected samples comprises:

determining a line passing through the origin and the center of gravity of the one or more failing samples; and

move the set of samples in a direction orthogonal to the line passing through the origin and the center of gravity of the one or more failing samples.

6. The method of claim 1, wherein recomputing new importance sampling weight ratios for the new origin comprises computing a weight function, wherein the weight function is as follows:

7. The method of claim 1, further comprising:

repeating selecting a new origin, recomputing new importance sampling weight ratios for the new origin, and determining a failure rate for the device based on the new importance sampling weight ratios for the new origin for a set of process variations.

8. The method of claim 1, wherein recomputing new importance sampling weight ratios for the new origin comprises:

determining importance samples based on the center of gravity of the one or more failing samples and the new origin.

9. A computer program product comprising a computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a computing device, causes the computing device to:

perform a uniform sampling over a random sample space for a metric for the device with respect to an origin to form a set of samples, wherein the set of samples comprises one or more failing samples;

determine a center of gravity of the one or more failing samples with respect to the origin;

determine importance samples based on the center of gravity of the one or more failing samples;

recompute new importance sampling weight ratios for a selected new origin; and

determine a failure rate for the device based on the new importance sampling weight ratios for the new origin.

10. The computer program product of claim 9, wherein recomputing new importance sampling weight ratios for the new origin comprises:

finding a projected origin; and

recomputing new importance sampling weight ratios with respect to the projected origin.

11. The computer program product of claim 10, wherein finding the projected origin comprises:

determining a line passing through the origin and the center of gravity of the one or more failing samples; and

projecting the new origin onto the line passing though the origin and the center of gravity of the one or more failing samples.

12. The computer program product of claim 9, wherein recomputing new importance sampling weight ratios for the new origin comprises:

finding a set of projected samples with respect to the new origin; and

recomputing new importance sampling ratios based on the projected samples.

13. The computer program product of claim 12, wherein finding the set of projected samples comprises:

determining a line passing through the origin and the center of gravity of the one or more failing samples; and

move the set of samples in a direction orthogonal to the line passing through the origin and the center of gravity of the one or more failing samples.

14. The computer program product of claim 9, wherein recomputing new importance sampling weight ratios for the new origin comprises computing a weight function, wherein the weight function is as follows:

15. The computer program product of claim 9, wherein the computer readable program further causes the computing device to:

repeat selecting a new origin, recomputing new importance sampling weight ratios for the new origin, and determining a failure rate for the device based on the new importance sampling weight ratios for the new origin for a set of process variations.

16. The computer program product of claim 9, wherein recomputing new importance sampling weight ratios for the new origin comprises:

determining importance samples based on the center of gravity of the one or more failing samples and the new origin.

17. The computer program product of claim 9, wherein the computer readable program is stored in a computer readable storage medium in a data processing system and wherein the computer readable program was downloaded over a network from a remote data processing system.

18. The computer program product of claim 9, wherein the computer readable program is stored in a computer readable storage medium in a server data processing system and wherein the computer readable program is downloaded over a network to a remote data processing system for use in a computer readable storage medium with the remote system.

19. An apparatus, comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to;

perform a uniform sampling over a random sample space for a metric for the device with respect to an origin to form a set of samples, wherein the set of samples comprises one or more failing samples;

determine a center of gravity of the one or more failing samples with respect to the origin;

determine importance samples based on the center of gravity of the one or more failing samples;

recompute new importance sampling weight ratios for a selected new origin; and

determine a failure rate for the device based on the new importance sampling weight ratios for the new origin.

20. The apparatus of claim 19, wherein recomputing new importance sampling weight ratios for the new origin comprises:

finding a projected origin; and

recomputing new importance sampling weight ratios with respect to the projected origin.

21. The apparatus of claim 20, wherein finding the projected origin comprises:

determining a line passing through the origin and the center of gravity of the one or more failing samples; and

projecting the new origin onto the line passing through the origin and the center of gravity of the one or more failing samples.

22. The apparatus of claim 19, wherein recomputing new importance sampling weight ratios for the new origin comprises:

finding a set of projected samples with respect to the new origin; and

recomputing new importance sampling ratios based on the projected samples.

23. The apparatus of claim 22, wherein finding the set of projected samples comprises:

determining a line passing through the origin and the center of gravity of the one or more failing samples; and

move the set of samples in a direction orthogonal to the line passing through the origin and the center of gravity of the one or more failing samples.

24. The apparatus of claim 19, wherein recomputing new importance sampling weight ratios for the new origin comprises computing a weight function, wherein the weight function is as follows:

25. The apparatus of claim 19, wherein the instructions further cause the processor to:

repeat selecting a new origin, recomputing new importance sampling weight ratios for the new origin, and determining a failure rate for the device based on the new importance sampling weight ratios for the new origin for a set of process variations.