This grant provides funding for the development and characterization of a method for controlling multi-level design optimization. This method is intended to apply to design problems that are carried out in a series of stages or abstraction levels, where the result of each level sets the problem for the next level. For instance, in microprocessor design one level might represent the microprocessor as a set of boolean logic formulas, another might convert these formulas into wiring diagrams of transistors, and another might convert the wiring diagram into a specific layout of wires and doping regions on the chip. The method assumes that we have an optimizer for each level and that each optimizer uses stochastic methods, such as simulated annealing, genetic algorithms, or multi-start hill climbing. The method coordinates and controls the use of these optimizers to explore the space of alternative designs in an efficient way, based on an estimate it makes for each current alternative at each level of what the `utility` would be of using that alternative as the basis for generating the desired final design, where utility is the value of the resulting final design minus the cost in design effort to find it. Currently this method has had an initial feasibility test on one task domain. The primary goals of this research are to better test the generality of this approach and to extend it to as broad as possible a class of problems and models of cost. If successful, the research funded by this grant will result in a version of this method that is applicable to a broad spectrum of design optimization tasks, along with a characterization of what kinds of tasks it is most useful for, of how best to apply it to a given task, and of how well it can be expected to perform. This should lead to improved tradeoffs between design time and design quality in many design domains.
