Statistical design with importance sampling reuse

• US 10,387,235 B2
• Filed: 05/23/2016
• Issued: 08/20/2019
• 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:
  US15/161,462
• Publication Number:
  US 20160266950A1
• Time in Patent Office: 1,184 Days
• 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 comprising at least one processor and at least one memory, the method comprising:

configuring the at least one memory with instructions, which are executed by the at least one processor and configure the at least one processor to implement an apparatus for determining failure rate of a device using importance sampling reuse;

performing, by the instructions executing on the at least one processor, a distribution sampling over a random sample space for a performance metric for the device with respect to an origin to form a 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 distribution set of samples comprises one or more failing samples;

determining, by the instructions executing on the at least one processor, an importance sampling weight function with respect to the origin;

determining, by the instructions executing on the at least one processor, a new importance sampling weight function with respect to a new origin, wherein the new origin represents alternative values for device parameters corresponding to a process variation or design consideration;

applying, by the instructions executing on the at least one processor, the new importance sampling weight function to the distribution set of samples to form a weighted set of samples;

determining, by the instructions executing on the at least one processor, a failure rate for the device for the alternative values for the device parameters based on the weighted set of samples;

repeating selecting a new origin, determining the new importance sampling weight function for the new origin, and determining a failure rate for the device using the distribution set of samples and the new importance sampling weight function for the new origin for a set of process variations; and

optimizing nominal values for the device parameters with respect to the determined failure rates.

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 a center of gravity of one or more failing samples within the distribution set of 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 a center of gravity of one or more failing samples within the distribution set of samples;

moving the 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.

4. 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 a center of gravity of one or more failing samples within the distribution set of samples and the new origin.

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

6. The method of claim 1, wherein performing the distribution sampling comprises performing the 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.

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

8. A computer program product comprising a non-transitory computer readable storage medium being configured with a computer readable program stored therein, wherein the computer readable program, when executed on at least one processor of a computing device, causes the at least one processor to implement an apparatus for determining failure rate of a device using importance sampling reuse, wherein the computer readable program causes the computing device to:

perform a distribution sampling over a random sample space for a performance metric for a device with respect to an origin to form a 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 distribution set of samples comprises one or more failing samples;

determine an importance sampling weight function with respect to the origin;

determine a new importance sampling weight function with respect to a 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 distribution set of samples to form a weighted set of samples;

determine a failure rate for the device for the alternative values for the device parameters based on the weighted set of samples;

repeating selecting a new origin, determining the new importance sampling weight function for the new origin, and determining a failure rate for the device using the distribution set of samples and the new importance sampling weight function for the new origin for a set of process variations; and

optimizing nominal values for the device parameters with respect to the determined failure rates.

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

determining a line passing through the origin and a center of gravity of one or more failing samples within the distribution set of 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.

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

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

moving the 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.

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

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

12. The computer program product of claim 8, wherein the importance sampling weight function is as follows:

13. An apparatus, comprising:

at least one processor; and

at least one memory coupled to the at least one processor, wherein the at least one memory comprises instructions which, when executed by the at least one processor, cause the at least one processor to implement an apparatus for determining failure rate of a device using importance sampling reuse, wherein the instructions cause the at least one processor to;

perform a distribution sampling over a random sample space for a performance metric for a device with respect to an origin to form a 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 distribution set of samples comprises one or more failing samples;

determine an importance sampling weight function with respect to the origin;

determine a new importance sampling weight function with respect to a 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 distribution set of samples to form a weighted set of samples;

determine a failure rate for the device for the alternative values for the device parameters based on the weighted set of samples;

repeating selecting a new origin, determining the new importance sampling weight function for the new origin, and determining a failure rate for the device using the distribution set of samples and the new importance sampling weight function for the new origin for a set of process variations; and

optimizing nominal values for the device parameters with respect to the determined failure rates.

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

determining a line passing through the origin and a center of gravity of one or more failing samples within the distribution set of 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.

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

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

moving the 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.

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

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

17. The apparatus of claim 13, wherein the importance sampling weight function is as follows: