Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2002-08-27
2004-10-19
Garbowski, Leigh M. (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C703S013000, C706S013000
Reexamination Certificate
active
06807652
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method for the optimization of robust designs using a search engine, and a search engine for implementing such a method. More particularly, the present invention relates to optimization of the design of semiconductor circuit products, and the design of semiconductor product manufacturing processes, where decision making in the search engine is made under uncertainty.
BACKGROUND OF THE INVENTION
A search engine is an algorithm, typically implemented on a general purpose computer, that traverses a space of possible candidate designs in a manner to try to find one or more improved candidate designs by trying to improve upon one or more objective functions. Search engines can be used to solve complex problems that are intractable and defy direct solution, or for which theoretically known approaches are impractical because they require too much time or other resources or are too inconvenient to bother modeling.
Search engines differ by the search space or design space on which they operate. For example, the design space of a typical parameter search engine is a subset of a multidimensional space of real numbers, i.e. R
n
. Other candidate spaces are also possible, for example, data structures such as a tree, a graph, etc.
Search engines are used in a variety of disciplines ranging from academic research to industrial applications. Because of the widespread use of search engines, they have been carefully studied. Techniques have been discovered to improve performance and eliminate unproductive search paths. While some of the techniques and principles are generally applicable, other techniques or refinements are based on the specific nature of the problem in question.
One example of the need to refine search engine techniques is in engineering or industrial design problems in which there is a need to deal with uncertainty. For example, in the large-scale production of any manufacture, real-world considerations such as machine tolerances, individual variation in components and other factors affect the quality and performance of the final product. Such variations can often be regarded as random and modelled, for example, using a Gaussian probability distribution. Robustness is a characteristic of a design that qualifies how well that design performs in the face of variation. A robust design process refers to an approach to reducing the effects of variation by predicting the likely magnitude of such variations and accounting for them in the specifications, models and design of the product.
Since automated search techniques can be used to aid design, it is useful to consider incorporating robustness into automated search in a robust design process.
One well-known approach to robust search problems is the “brute-force” Monte Carlo search method. Monte Carlo sampling is the process of drawing random samples from a process that has variation. The “brute-force” Monte Carlo search method replaces a standard objective function with a variation-induced objective function by taking a fixed number of Monte Carlo samples, then performing a statistical estimate on those samples, and trying to optimize those statistical estimates in the same manner as if they were deterministic objective functions. This method is combined with standard search engines that have typically originally been used in search on deterministic objective functions, e.g. evolutionary algorithms and simulated annealing. The “brute force” Monte Carlo search method is quite problem independent because it is independent of specific characteristics of the underlying variation; it just needs to be able to draw Monte Carlo samples. This makes it a very useful in attacking problems that are not solvable in closed form; it is, in general a very flexible approach to robust optimization, and is sometimes the only conceivable method of robust optimization for particular problems.
As is well known in statistical theory, increasing the sample size can reduce the amount of uncertainty in estimation of the underlying process. Accordingly, the standard technique to reduce the uncertainty in “brute-force” Monte Carlo search method is to increase the (pre-set) number of samples. Unfortunately, increasing the sample size increases the amount of computing power and other resources required. It is not uncommon to run 50 or even 500 Monte Carlo samples at a design point in order to keep uncertainty low. That means that “brute-force” Monte Carlo search need roughly 50 to 500 more computational effort than a comparable non-robust search. If the computing demands are excessive, then the finite amount of available resources, including time, may constrain the types of problems that can be solved by this approach. It is, therefore, desirable to provide a method that preserves the utility and power of such search engines while reducing the computing demands and constraints that are associated with existing methods.
Other types of search engines invented for robust design problems employ relatively fast, specialized algorithms that rely on a particular closed form description of the underlying process, or make assumptions about the underlying process. The advantage is that these techniques are able to use less computational effort than a generalized “brute force” Monte Carlo search method. The drawback is that these approaches are only able to solve a subset of all robust optimization problems.
In summary, the “brute force” Monte Carlo approach to robust design has the advantage of broad applicability and flexibility, with the disadvantage of needing significant computing resources. The approach of having specialized algorithms for robust design has the advantage of needing less computational resources, with the disadvantage of limited applicability and flexibility. Accordingly, there is a desire to have an approach to robust design that has broad applicability and flexibility, yet requires less computing resources than the “brute-force” Monte Carlo approach.
SUMMARY OF THE INVENTION
It is an object of the present invention to obviate or mitigate at least one disadvantage of previous methods associated with search engines applied to robust design.
The present invention generally provides a method of comparing two or more competing candidate solutions and determining the best candidate within the framework of a search algorithm that incorporates a competition, such as evolutionary computing, simulated annealing, pattern searching with stochastic elements or tabu searching.
The present invention further provides a method of dealing with randomness in the optimization of one or more objective functions in the design of semiconductor products and their related manufacturing processes. This method is applicable to search algorithms having one or more stochastic objective functions. The present invention also provides a system or search engine associated with the above methods.
According to an aspect of the present invention there is provided in robust design problems using a search engine, a method of selecting one of a first and second semiconductor technology design candidates, the method comprising: randomly sampling said first candidate to obtain a first random sample; determining at least one objective function value from said first random sample; randomly sampling said second candidate to obtain a second random sample; determining at least one objective function value from said second random sample; determining, based on said first and second objective function values comparison-oriented statistical estimates relating the first and second design candidates; selecting, if possible, based on at least one decision rule and said comparison-oriented statistical estimates, one of said design candidates; and repeating the previous steps until one of said design candidates has been selected.
According to a second aspect of the present invention, there is provided in robust design problems using a search engine, a computer-readable program product for selecting one of first and second semiconductor technolog
LandOfFree
Method of robust semiconductor circuit products design using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of robust semiconductor circuit products design using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of robust semiconductor circuit products design using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3271054