Statistical design with importance sampling reuse

• US 9,348,680 B2
• Filed: 04/01/2014
• Issued: 05/24/2016
• Est. Priority Date: 08/20/2010
• Status: Active Grant

• 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.
• Primary Examiner(s): Saxena, Akash
• Application Number:
  US14/242,418
• Publication Number:
  US 20140215274A1
• Time in Patent Office: 784 Days
• Field of Search: 716/56
• US Class Current: 1/1
• 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 distribution sampling over a random sample space for a performance metric for the device with respect to an origin to form a uniform distribution set of samples, wherein the origin represents nominal values for device parameters for a given design of the device, wherein the metric is an operational performance value of the device, and wherein the uniform distribution 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, an importance sampling weight function based on the center of gravity of the one or more failing samples;

selecting a new origin representing alternative values for device parameters corresponding to a process variation or design consideration;

determining, by the data processing system, a new importance sampling weight function with respect to the new origin;

applying the new importance sampling weight function to the uniform distribution set of samples to form a weighted set of samples; and

determining, by the data processing system, a failure rate for the device using the weighted set of samples for the alternative values for the device parameters.

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

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

projecting the new origin onto the line passing through the origin and the center of gravity of the one or more failing samples to determine a projected origin; and

determining the new importance sampling weight function with respect to the projected origin.

3. The method of claim 1, wherein determining the new importance sampling weight function for the new origin comprises:

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

moving the uniform distribution 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 to determine a set of projected samples with respect to the new origin; and

determining the new importance sampling ratio weight function based on the set of projected samples.

4. The method of claim 1, further comprising:

repeating selecting a new origin, determining the new importance sampling weight function for the new origin, applying the new importance sampling weight function to the uniform distribution set of samples to form a weighted set of samples, and determining a failure rate for the device based on the weighted set of samples for the new origin for a set of process variations.

5. The method of claim 1, wherein determining the new importance sampling weight function for the new origin comprises:

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

6. The method of claim 1, wherein the importance sampling weight function is as follows:

7. The method of claim 1, wherein performing the uniform distribution sampling comprises performing the uniform distribution sampling over the random sample space for the performance metric for the device with respect to the origin until a predetermined number of failing samples are encountered.

8. The method of claim 1, wherein the importance sampling weight function is as follows:

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 distribution sampling over a random sample space for a performance metric for a device with respect to an origin to form a uniform distribution set of samples, wherein the origin represents nominal values for device parameters for a given design of the device, wherein the metric, is an operational performance value of the device, and wherein the uniform distribution 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 an importance sampling weight function based on the center of gravity of the one or more failing samples;

determine a new importance sampling weight function with respect to a selected new origin, wherein the new origin represents alternative values for device parameters corresponding to a process variation or design consideration;

apply the new importance sampling weight function to the uniform distribution set of samples to form a weighted set of samples; and

determine a failure rate for the device using the weighted set of samples for the alternative values for the device parameters.

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

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

projecting the new origin onto the line passing through the origin and the center of gravity of the one or more failing samples to determine a projected origin; and

determining the new importance sampling weight function with respect to the projected origin.

11. The computer program product of claim 9, wherein determining the new importance sampling weight function for the new origin comprises:

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

moving the uniform distribution 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 to determine a set of projected samples with respect to the new origin; and

determining the new importance sampling weight function based on the set of projected samples.

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

repeat selecting a new origin, determining the new importance sampling weight function for the new origin, applying the new importance sampling weight function to the uniform distribution set of samples to form a weighted set of samples and determining a failure rate for the device based on the weighted set of samples for the new origin for a set of process variations.

13. The computer program product of claim 9, wherein determining the new importance sampling weight function for the new origin comprises:

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

14. The computer program product of claim 9, wherein the new importance sampling weight function is as follows:

15. 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 distribution sampling over a random sample space for a performance metric for a device with respect to an origin to form a uniform distribution set of samples, wherein the origin represents nominal values for device parameters for a given design of the device, wherein the metric is an operational performance value of the device, and wherein the uniform distribution 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 sampling weight function based on the center of gravity of the one or more failing samples;

determine a new importance sampling weight function with respect to a selected new origin, wherein the new origin represents alternative values for device parameters corresponding to a process variation or design consideration;

apply the new importance sampling weight function to the uniform distribution set of samples to form a weighted set of samples; and

determine a failure rate for the device using the weighted set of samples for the alternative values for the device parameters.

16. The apparatus of claim 15, wherein determining the new importance sampling weight function for the new origin comprises:

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

projecting the new origin onto the line passing through the origin and the center of gravity of the one or more failing samples to determine a projected origin; and

determining the new importance sampling weight function with respect to the projected origin.

17. The apparatus of claim 15, wherein determining the new importance sampling weight function for the new origin comprises:

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

moving the uniform distribution 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 to determine a set of projected samples with respect to the new origin; and

determining the new importance sampling function based on the set of projected samples.

18. The apparatus of claim 15, wherein the instructions further cause the processor to:

repeat selecting a new origin, determining a new importance sampling weight function for the new origin, applying the new importance weight function to the uniform distribution set of samples to for a weighted set of samples, and determining a failure rate for the device based on the weighted set of samples for the new origin for a set of process variations.

19. The apparatus of claim 15, wherein determining the new importance sampling weight function for the new origin comprises:

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

20. The apparatus of claim 15, wherein the new importance sampling weight function is as follows: