Statistical design with importance sampling reuse

Patent metadata

Field	Value
Publication number	US-10387235-B2
Application number	US-201615161462-A
Country	US
Kind code	B2
Filing date	May 23, 2016
Priority date	Aug 20, 2010
Publication date	Aug 20, 2019
Grant date	Aug 20, 2019

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.

First claim

What is claimed is:

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:

w
⁡

(
x
)

=

Πexp
⁡

(

-
0.5

*

(

x
-

x
np

σ

)

2

)

/

exp
⁡

(

-
0.5

*

(

x
-

x
COG

σ

)

2

)

x is process variation variable of the device, x np is a new point of a projected origin for the process variation variable x, x COG is the center of gravity of the one or more failing samples, and σ is the standard deviation of x.

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:

w
⁡

(
x
)

=

Π
⁢

σ

σ
np

⁢

exp
⁡

(

-
0.5

⁢

(

x
-

x
np

σ
np

)

2

)

Assignees

• IBM
• Int Buisness Machines Corporation

Inventors

• Joshi Rajiv V
• Kanj Rouwaida N
• Nassif Sani R
• Radens Carl J

Classifications

• G06F2111/08

  Probabilistic or stochastic CAD · CPC title

• G06F30/20

  Design optimisation, verification or simulation (optimisation, verification or simulation of circuit designs G06F30/30) · CPC title

• G06F30/33 Primary

  Design verification, e.g. functional simulation or model checking · CPC title

• G06F11/076 Primary

  by exceeding a count or rate limit, e.g. word- or bit count limit · CPC title

• G06F11/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 title