Modeling spatial correlations
View Patent ↗Modeling spatial correlations of semiconductor characteristic variations is disclosed. In one embodiment, a method includes developing a solution for each of a plurality of specific forms of spatial correlations of a characteristic of a circuit design and developing a plurality of solution methods for a given spatial correlation; selecting one of the solutions that is closest to a desired spatial correlation; and modeling the desired spatial correlation using the selected solution.
1. A method comprising:
performing using a computer:
developing a solution for each of a plurality of specific forms of spatial correlations of a characteristic of a circuit design and developing a plurality of solution methods for a given spatial correlation, wherein the developing includes:
dividing a two-dimensional chip region into a sub-region grid of I rows and J columns,
defining a two-dimensional spatial correlation C(i, j; k, l) on the sub-region grid such that each grid point (i, j) or (k, l) represents one sub-region, and
treating two instances of the characteristic within a common sub-region as perfectly correlated, and treating two instances of the characteristic in different sub-regions as either partially correlated or completely un-correlated;
selecting one of the solutions that is closest to a desired spatial correlation; and
modeling the desired spatial correlation using the selected solution.
2. The method of claim 1 , wherein the modeling includes modeling the desired spatial correlation as a translational invariant having a correlation range of (M−1) rows in a row direction and of (N−1) columns in a column direction such that:
C ( i,j;i±m,j±n )= F ( M,m;N,n ),
F ( M, 0; N, 0)=1, F ( M,M;N,n )= F ( M,m;N,N )=0,
m=0,1,2, . . . ,M, n=0,1,2, . . . ,N;
and for all others, C(i, j; k, l)=0, and
a solution therefore uses (I+M−1)(J+N−1) independent stochastic variables to represent IJ correlated characteristic variables:
x
ij
=
x
0
+
σ
∑
k
=
1
M
∑
l
=
1
N
A
kl
g
i
+
k
-
1
,
j
+
l
-
1
,
i
=
1
,
2
,
…
,
I
,
j
=
1
,
2
,
…
,
J
,
where x ij is an instance of the characteristic in sub-region (i, j), x 0 is a mean value of the characteristic, σ is a standard deviation of the characteristic, each g ij is an independent stochastic, random variable of mean zero and standard deviation one, and MN coefficients A kl satisfy a total of MN conditions:
F
(
M
,
m
;
N
,
n
)
=
∑
k
=
1
M
-
m
∑
l
=
1
N
-
n
A
k
,
l
A
k
+
m
,
l
+
n
,
m
=
0
,
1
,
2
,
…
,
M
-
1
,
n
=
0
,
1
,
2
,
…
,
N
-
1.
3. The method of claim 1 , wherein the two-dimensional spatial correlation is represented as a product of two one-dimensional spatial correlations:
F ( M,m;N,n )= f 1 ( M,m ) f 2 ( N,n ), m= 0,1,2, . . . , M, n= 0,1,2, . . . , N,
where the one-dimensional spatial correlations have relations:
f i ( M, 0)=1 , f 1 ( M,M )=0,
f 2 ( N, 0)=1, f 2 ( N,N )=0, and
a two-dimensional solution is given by a product of two one-dimensional solutions:
A kl =a k b l , k=1,2, . . . ,M, l=1,2, . . . ,N,
where M coefficients a k satisfy M relations:
∑
k
=
1
M
-
m
a
k
a
k
+
m
=
f
1
(
M
,
m
)
,
m
=
0
,
1
,
2
,
…
,
M
-
1
,
and
N coefficients b l satisfy N relations:
∑
l
=
1
N
-
n
b
l
b
l
+
n
=
f
2
(
N
,
n
)
,
n
=
0
,
1
,
2
,
…
,
N
-
1.
4. The method of claim 3 , wherein one of the plurality of one-dimensional spatial correlations includes a linear-decay spatial correlation:
f
1
(
M
,
m
)
=
1
-
m
M
,
m
=
0
,
1
,
2
,
…
,
M
,
which has a solution:
a
k
=
1
M
,
k
=
1
,
2
,
…
,
M
.
5. The method of claim 3 , wherein one of the plurality of one-dimensional spatial correlations includes a spatial correlation of Gaussian distribution:
f
(
M
,
m
)
=
exp
(
-
η
2
m
2
4
M
2
)
,
m
=
1
,
2
,
…
,
M
-
1
,
which has a solution of being also a truncated Gaussian distribution but with a smaller (x 1/√{square root over (2)}) standard deviation:
a
k
=
βexp
[
-
η
2
(
k
-
k
0
)
2
2
M
2
]
,
k
=
1
,
2
,
…
,
M
,
k
0
=
1
2
(
M
+
1
)
,
where β is a normalization constant.
6. The method of claim 3 , wherein one of the plurality of one-dimensional spatial correlations includes a spatial correlation of Lorentzian distribution:
f
(
M
,
m
)
=
1
1
+
(
η
m
/
M
)
2
,
m
=
1
,
2
,
…
,
M
-
1
,
which has a solution of being also a truncated Lorentzian distribution but with a 50% smaller half width at half height:
a
k
=
β
1
+
[
2
η
(
k
-
k
0
)
/
M
]
2
,
k
=
1
,
2
,
…
,
M
,
k
0
=
1
2
(
M
+
1
)
,
where β is a normalization constant.
7. The method of claim 3 , wherein the developing includes developing a plurality of one-dimensional correlations by starting from an expression for a k and finding corresponding spatial correlation f 1 (M, m), and starting from an expression for b l and finding corresponding spatial correlation f 2 (N, n).
8. The method of claim 3 , wherein the developing includes developing a solution for a given one-dimensional spatial correlation f(M, m) using two Fourier transforms along with a max( ) operation and a square root operation:
a
k
=
β
1
∫
0
+
∞
α
(
ω
)
cos
[
ω
(
k
-
k
0
)
]
ⅆ
ω
,
k
=
1
,
2
,
…
,
M
,
k
0
=
1
2
(
M
+
1
)
,
where β1 is a normalization constant,
α(ω)=±√{square root over (max(φ(ω),0))},
φ(ω) is a Fourier transform of the one-dimensional spatial correlation f(M, m),
ϕ
(
ω
)
=
2
∫
0
M
f
(
M
,
m
)
cos
(
ω
m
)
ⅆ
m
,
and m in the spatial correlation f(M, m) has been extended to a real value, and includes developing a solution for a given two-dimensional spatial correlation F(M, m; N, n) using the Fourier transforms along with a max( ) operation and a square root operation:
A
k
,
l
=
β
2
∫
0
+
∞
∫
0
+
∞
B
(
ω
,
v
)
cos
[
ω
(
k
-
k
0
)
]
cos
[
v
(
l
-
l
0
)
]
ⅆ
v
ⅆ
ω
,
k
=
1
,
2
,
…
,
M
,
l
=
1
,
2
,
…
,
N
,
k
0
=
1
2
(
M
+
1
)
,
l
0
=
1
2
(
N
+
1
)
,
where β 2 is a normalization constant,
B (ω, v )=±√{square root over (max(Φ(ω, v ),0))},
Φ(ω, v) is a Fourier transform of the two-dimensional spatial correlation F(M, m; N, n),
Φ
(
ω
,
ν
)
=
4
∫
0
M
∫
0
N
F
(
M
,
m
;
N
,
n
)
cos
(
ω
m
)
cos
(
ν
n
)
ⅆ
n
ⅆ
n
,
and m and n in the spatial correlation F(M, m; N, n) have been extended to be real.
9. The method of claim 1 , wherein the desired spatial correlation is based on hardware measurement data.
10. The method of claim 1 , wherein the developing includes changing a set of unrealistic correlation coefficients to a set of realistic correlation coefficients.
11. A system comprising:
means for developing a solution for each of a plurality of specific forms of spatial correlations of a characteristic of a circuit design and a plurality of solution methods for a given spatial correlation, wherein the developing means:
divides a two-dimensional chip region into a sub-region grid of I rows and J columns,
defines a two-dimensional spatial correlation C(i, j; k, l) on the sub-region grid such that each grid point (i, j) or (k, l) represents one sub-region, and
treats two instances of the characteristic within a common sub-region as perfectly correlated, and treats two instances of the characteristic in different sub-regions as either partially correlated or completely un-correlated;
means for selecting one of the solutions that is closest to a desired spatial correlation; and
means for modeling the desired spatial correlation using the selected solution.
12. The system of claim 11 , wherein the modeling means models the desired spatial correlation as a translational invariant having a correlation range of (M−1) rows in a row direction and of (N−1) columns in a column direction such that:
C ( i,j;i±m,j±n )= F ( M,m;N,n ),
F ( M, 0; N, 0)=1, F ( M,M;N,n )= F ( M,m;N,N )=0,
m=0,1,2, . . . ,M, n=0,1,2, . . . ,N;
and for all others, C(i, j; k, l)=0, and
a solution therefor uses (I+M−1)(J+N−1) independent stochastic variables to represent IJ correlated characteristic variables:
x
ij
=
x
0
+
σ
∑
k
=
1
M
∑
l
=
1
N
A
kl
g
i
+
k
-
1
,
j
+
l
-
1
,
i
=
1
,
2
,
…
,
I
,
j
=
1
,
2
,
…
,
J
,
where x ij is an instance of the characteristic in sub-region (i, j), x 0 is a mean value of the characteristic, σ is a standard deviation of the characteristic, each g ij is an independent stochastic, random variable of mean zero and standard deviation one, and MN coefficients A kl satisfy a total of MN conditions:
F
(
M
,
m
;
N
,
n
)
=
∑
k
=
1
M
-
m
∑
l
=
1
N
-
n
A
k
,
l
A
k
+
m
,
l
+
n
,
m
=
0
,
1
,
2
,
…
,
M
-
1
,
n
=
0
,
1
,
2
,
…
,
N
-
1.
13. The system of claim 11 , wherein the two-dimensional spatial correlation is represented as a product of two one-dimensional spatial correlations:
F ( M,m;N,n )= f 1 ( M,m ) f 2 ( N,n ), m= 0,1,2, . . . , M, n= 0,1,2, . . . , N,
where the one-dimensional spatial correlations have relations:
f 1 ( M, 0)=1, f 1 ( M,M )=0,
f 2 ( N, 0)=1, f 2 ( N,N )=0, and
a two-dimensional solution is given by a product of two one-dimensional solutions:
A kl =a k b l , k=1,2, . . . ,M, l=1,2, . . . ,N,
where M coefficients a k satisfy M relations:
∑
k
=
1
M
-
m
a
k
a
k
+
m
=
f
1
(
M
,
m
)
,
m
=
0
,
1
,
2
,
…
,
M
-
1
,
and
N coefficients b l satisfy N relations:
∑
l
=
1
N
-
n
b
l
b
l
+
n
=
f
2
(
N
,
n
)
,
n
=
0
,
1
,
2
,
…
,
N
-
1.
14. The system of claim 11 , wherein one of the plurality of one-dimensional spatial correlations includes a linear-decay spatial correlation:
f
1
(
M
,
m
)
=
1
-
m
M
,
m
=
0
,
1
,
2
,
…
,
M
,
which has a solution:
a
k
=
1
M
,
k
=
1
,
2
,
…
,
M
.
15. The system of claim 11 , wherein one of the plurality of one-dimensional spatial correlations includes a spatial correlation of Gaussian distribution:
f
(
M
,
m
)
=
exp
(
-
η
2
m
2
4
M
2
)
,
m
=
1
,
2
,
…
,
M
-
1
,
which has a solution of being also a truncated Gaussian distribution but with a smaller (x 1/√{square root over (2)}) standard deviation:
a
k
=
βexp
[
-
η
2
(
k
-
k
0
)
2
2
M
2
]
,
k
=
1
,
2
,
…
,
M
,
k
0
=
1
2
(
M
+
1
)
,
where β is a normalization constant.
16. The system of claim 11 , wherein one of the plurality of one-dimensional spatial correlations includes a spatial correlation of Lorentzian distribution:
f
(
M
,
m
)
=
1
1
+
(
η
m
/
M
)
2
,
m
=
1
,
2
,
…
,
M
-
1
,
which has a solution of being also a truncated Lorentzian distribution but with a 50% smaller half width at half height:
a
k
=
β
1
+
[
2
η
(
k
-
k
0
)
/
M
]
2
,
k
=
1
,
2
,
…
,
M
,
k
0
=
1
2
(
M
+
1
)
,
where β is a normalization constant.
17. The system of claim 11 , wherein the developing includes developing a solution for a given one-dimensional spatial correlation f(M, m) using two Fourier transforms along with a max( ) operation and a square root operation,
a
k
=
β
1
∫
0
+
∞
α
(
ω
)
cos
[
ω
(
k
-
k
0
)
]
ⅆ
ω
,
k
=
1
,
2
,
…
,
M
,
k
0
=
1
2
(
M
+
1
)
,
where β 1 is a normalization constant,
α(ω)=±√{square root over (max(φ(ω),0))},
φ(ω) is a Fourier transform of the one-dimensional spatial correlation f(M, m),
ϕ
(
ω
)
=
2
∫
0
M
f
(
M
,
m
)
cos
(
ω
m
)
ⅆ
m
,
ω
≥
0
,
and m in the spatial correlation f(M, m) has been extended to a real value, and includes developing a solution for a given two-dimensional spatial correlation F(M, m; N, n) using the Fourier transforms along with a max( ) operation and a square root operation,
A
k
,
l
=
β
2
∫
0
+
∞
∫
0
+
∞
B
(
ω
,
ν
)
cos
[
ω
(
k
-
k
0
)
]
cos
[
ν
(
l
-
l
0
)
]
ⅆ
ν
ⅆ
ω
,
k
=
1
,
2
,
…
,
M
,
l
=
1
,
2
,
…
,
N
,
k
0
=
1
2
(
M
+
1
)
,
l
0
=
1
2
(
N
+
1
)
,
where β 2 is a normalization constant, B(ω, v)=±√{square root over (max(Φ(ω, v), 0))}, Φ(ω, v) is a Fourier transform of the two-dimensional spatial correlation F(M, m; N, n),
Φ
(
ω
,
ν
)
=
4
∫
0
M
∫
0
N
F
(
M
,
m
;
N
,
n
)
cos
(
ω
m
)
cos
(
ν
n
)
ⅆ
n
ⅆ
m
,
and m and n in the spatial correlation F(M, m; N, n) have been extended to be real.
18. A program product stored on a computer-readable, non-transitory medium, which when executed by a computer, models spatial correlations, the program product comprising:
program code for developing a solution for each of a plurality of specific forms of spatial correlations of a characteristic of a circuit design and for developing a plurality of solution methods for a given spatial correlation, wherein the developing program code:
divides a two-dimensional chip region into a sub-region grid of I rows and J columns,
defines a two-dimensional spatial correlation C(i, j; k, l) on the sub-region grid such that each grid point (i, j) or (k, l) represents one sub-region, and
treats two instances of the characteristic within a common sub-region as perfectly correlated, and treats two instances of the characteristic in different sub-regions as either partially correlated or completely un-correlated;
program code for selecting one of the solutions that is closest to a desired spatial correlation; and
program code for modeling the desired spatial correlation using the selected solution.