US2012046929A1PendingUtilityA1
Statistical Design with Importance Sampling Reuse
Est. expiryAug 20, 2030(~4.1 yrs left)· nominal 20-yr term from priority
G06F 30/33G06F 30/20G06F 2111/08G06F 11/008G06F 11/079G06F 11/076G06F 30/3308
51
PatentIndex Score
0
Cited by
0
References
0
Claims
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
exact text as granted — not AI-modifiedWhat is claimed is:
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:
w
(
x
)
=
Π
σ
σ
np
exp
(
-
0.5
(
x
-
x
np
σ
np
)
2
)
/
exp
(
-
0.5
(
x
-
x
COG
σ
)
2
)
where 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, σ is the standard deviation of x, and σ np is the standard deviation associated with the new point of projected origin.
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:
w
(
x
)
=
Π
σ
σ
np
exp
(
-
0.5
(
x
-
x
np
σ
np
)
2
)
/
exp
(
-
0.5
(
x
-
x
COG
σ
)
2
)
where 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, σ is the standard deviation of x, and σ np is the standard deviation associated with the new point of projected origin.
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:
w
(
x
)
=
Π
σ
σ
np
exp
(
-
0.5
(
x
-
x
np
σ
np
)
2
)
/
exp
(
-
0.5
(
x
-
x
COG
σ
)
2
)
where 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, σ is the standard deviation of x, and σ np is the standard deviation associated with the new point of projected origin.
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.Join the waitlist — get patent alerts
Track US2012046929A1 — get alerts on status changes and closely related new filings.
We store only your email — no account needed. See our privacy policy.