7.7 Solving Design for Manufacturability Problems

**Figure 7.5:** This figure illustrates the formulation of solving design for manufacturability problems. A computationally expensive function is approximated and the set of admissible points is the set of the points whose function value is above a certain limit. In order to find the probability of getting admissible points for given distributions of the variables, an integral has to be evaluated numerically, where the computational effort using the expensive function would be prohibitive.
$\includegraphics[width=0.7\linewidth]{figures/bernstein-dfm-ana-example}$

In this section we discuss how to solve design for manufacturability problems taking advantage of interpolations or good global approximations like those provided by generalized Bernstein polynomials. The problem can be formulated as follows. Let be a real valued continuous function on a multi-dimensional interval $I:=[a_1,b_1]\times\cdots\times[a_m,b_m] \subset \mathbb{R}^n$ and let $\phi_k$ be the probability density of the variable . Often we have

$\displaystyle x_k \sim N(\mu_k,\sigma_k)\qquad\forall k\in\{1,\ldots,m\},$

i.e., each

conforms to a normal distribution. (The type of distribution does not matter for our discussion, but in practice the variables usually conform to a normal distribution.)

Without loss of generality we will consider the case where is to be maximized. Let be a real number. We call a point $x=\in\mathbb{R}^m$ admissible if $x\in I$ and $f(x)\ge B$ and denote the set of admissible points by

$\displaystyle A_{f,B} := \{ x\in I \mid f(x)\ge B\}.$

In the general case the probability densities $\phi_k$ depend on parameters and we have to choose these parameters such that

$\displaystyle \int_{\mathbb{R}^n} \chi_A(x) \phi_1(x_1)\cdots\phi_m(x_m) \mathrm{d}x_1 \ldots \mathrm{d}x_m$

becomes maximal.

In the case where all variables conform to a normal distribution we have the probability densities

$\displaystyle \phi_k(x)={1\over\sigma_k\sqrt{2\pi}} \mathrm{e}^{-(x-\mu_k)^2/2\sigma_k^2}$

and have to maximize

$\displaystyle g_A(\mu_1,\sigma_1,\ldots,\mu_m,\sigma_m):= \int_{\mathbb{R}^m} \chi_A(x) \phi_1(x_1)\cdots\phi_m(x_m) \mathrm{d}x_1 \ldots \mathrm{d}x_m.$

Hence design for manufacturability problems can be rigorously stated as the problem of maximizing

. This is illustrated in Figure 7.5.

In TCAD problems the evaluation of is computationally very expensive, since it entails simulations of device behavior. Hence the evaluation of $\chi_A$ is computationally expensive as well and thus the integration and evaluating is prohibitively expensive. If the function is substituted by its approximation $\tilde f:= B_{f,n_1,\ldots,n_m}$ on , we substitute the set of admissible points by $\tilde A := A_{\tilde f,B} = \{ x\in I \mid \tilde f(x)\ge B\}$ . Then $\chi_{\tilde A}$ can be evaluated much faster and hence evaluating $\tilde g := g_{\tilde A}$ becomes feasible and the problem of maximizing $\tilde g$ can now be attacked using optimization algorithms. Because $\tilde f$ converges uniformly to (Theorem 7.10), $\tilde g$ converges to when $n_k\to\infty$ .

These considerations again underline the importance of the theorems proven in Section 7.4 and conclude this chapter. In the next chapter, another application of this generalization of the Bernstein polynomials is discussed.

Clemens Heitzinger 2003-05-08