Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-06-07
2002-04-02
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06367052
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to methods of producing optimized designs using a computer system by controlling the operation of a hierarchy or sequence of applications of design optimization programs, design quality estimation programs and value computation programs. In particular these methods can be used to produce designs useful for developing machinery, articles of manufacture, compositions of matter, thereof.
BACKGROUND OF THE INVENTION
An important characteristic of stochastic optimization methods, such as simulated annealing, genetic algorithms and multi-start hill climbing, is that they can be run again and again on the same inputs, each time potentially producing a different answer. Some of the answers will be better, some worse. Indeed, it is common to run such algorithms a few times, and to use the best of the answers produced. The difficulty is in determining how many times.
The issue is complicated by the fact that in many cases the output of the optimizer is not a final artifact. Rather, the design task at hand is being done in a series of stages, or levels of abstraction, and the output of one optimizer is in turn used as input to another stage of design. For example, in designing a microprocessor, we might start with an instruction set, implement that as a set of register transfers, implement the register transfers as boolean logic, implement the boolean logic as a “net list” defining how specific circuit modules are to be wired together, implement the net list by choosing specific locations for the circuit modules and wires on the surface of a VLSI chip, etc. Thus, if several consecutive levels of design are to be done by stochastic methods, we really have a tree of alternate designs, whose leaves are the final, concrete designs, and whose internal nodes are designs at intermediate levels.
Each time an optimizer at any level gives us an output, the skilled artisan faces a choice of what to do next. The question is whether one should declare the best design one has so far at this level to be “good enough” and proceed to use it as input to the next level, or whether one should rerun the optimizer in hopes of getting a better design at the current level, or whether one should go back up to some higher level in the tree and try again there.
Current practice is often to use a “waterfall” approach, i.e. run the optimizer at one level some number of times, choose the best result, and proceed forwards. This would be an optimal approach if one had a completely accurate way of evaluating designs at intermediate levels (i.e., evaluating how good a final design one will get from this intermediate design), but in practice all one normally has are heuristics that tell us approximately how good an intermediate design is. In order to tell, e.g., which of two intermediate designs is actually better, we may have to try generating one or more designs at the next level from each of them.
The present invention presents an alternative to the waterfall method, which we call “rational best first” (RBF) search, that is capable of doing this kind of exploratory design. We will describe RBF and present empirical data from one example design task showing that RBF can be a large improvement over waterfall search.
The key insight behind RBF is that a good control method is not one that finds the best design (since finding the absolute best design takes exponential time), but one that gives the best tradeoff between computation cost and design quality, and that therefore control decisions should be based on an analysis of the utility and the cost of each possible action.
SUMMARY OF THE INVENTION
In order to define the value, i.e. the utility, of running an optimizer, we have to define the value of the designs it produces. We will assume that we are given the values of the ground level objects, in the form of a function that maps an object's score into its value. We define the value of an intermediate level design to be the profit we will get from using that design as a starting point—i.e., the expected value of the final ground level design it will lead to, minus the expected cost of the computation needed to go from that intermediate level design to the final design.
Using this definition of value allows us to compare two designs that are at different levels of abstraction, and leads to a simple heuristic: always work on the design with the highest estimated profit, at whatever level it is on. Of course, to make this operational we need a way to estimate the profit inherent in an intermediate-level design, but it turns out that we can use the ground level values and some fairly simple statistical reasoning to do so.
One embodiment of the invention includes: A method for controlling a hierarchy or sequence of applications of design optimization programs, design quality estimation programs and value computation programs, in a computer system to improve the tradeoff between quality of a final design result and computation time expended in the optimization programs to get that result, each design optimization program in the sequence taking as input the previous design program's result; a first design optimization program taking as input one or more specifications of an overall design task and a last program producing as output a complete design result for said task; said method including the steps of:
1. inputting said one or more specifications of said overall design task and initializing a set of design objects to include at least said one or more specifications;
2. computing the initial estimate of the utility of designing from said specifications using said design optimization programs, said utility being defined as the average value of the final result of a design process starting with said specification, minus the average cost in computer time of said design process; wherein each of said optimization programs when run multiple times will produce different intermediate design results of varying quality as measured by said design quality estimation programs, and each of said optimization programs having a known or estimated cost in computer time per run, said value computation program taking as data the design quality of the overall design result of the overall design task as measured by the design quality estimation programs, and producing as output a value to the user of said overall design result in comparable units to the known or estimated costs of running said optimization programs;
3. choosing as a current design object from the set of design objects, the design object whose estimated utility is greatest; examining and recognizing if said current design object is a complete design result for the overall design task, and if so producing an output of said current design object as the final design result of the overall design task, and if not proceeding to step 4;
4. Running the appropriate optimization program with said current design object as input to produce a new design object as a result, running an appropriate design quality estimation program on said new design object, estimating the utility as defined above of said new design object, and adding said new design object to said set of design objects;
5. Revising the estimate of utility for the current design object based on the quality of the new design object, and revising the utility estimates of all ancestor design objects from which the current design object was derived, based on the revised utility estimate of the current design object; and repeating from step 3.
In another embodiment of the invention, the method includes computation of the utility of a new design object that is a complete design result for the overall design task by running the value computation program on the new design object.
In another embodiment of the invention the method includes applying a specific algorithm when computing the utility of the new design object that is not a complete design result for the overall design task. The conditions and algorithms applied in such an instance are:
Compute the threshold score, s
Davison Brian D.
Hall J. Storrs
Steinberg Louis I.
Hoffmann & Baron , LLP
Rutgers The State University of New Jersey
Smith Matthew
Thompson A. M.
LandOfFree
Method of producing optimized designs using computer systems... 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 producing optimized designs using computer systems..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of producing optimized designs using computer systems... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2901970