Site News  |   Monitor Keywords  |   Monitor Archive  |   Organizer  |   Account Info  |

Model-building optimization

Model-building optimization description/claims

This application claims the benefit of priority of U.S. Provisional Patent Application No. 60/974,614 filed Sep. 24, 2007, which is incorporated herein by reference.

The applicant acknowledges the participation of K.U. Leuven Research and Development in the development of this invention.

The present invention relates generally to multi-objective optimization techniques of multi-parameter designs. In particular, the present invention related to multi-objective optimization of electric circuit designs such as analog, mixed-signal and custom digital electrical circuit designs.

Designers of electrical circuits routinely face the task of optimizing performance of analog, mixed-signal and custom digital circuits, hereinafter referred to generally as electrical circuit designs (ECDs). In optimizing such ECDs, the designers aim to set device sizes on the ECUs such as to obtain optimum performances for one or more performance metric of the ECDs. In design-for-yield optimization, the designers aim to set the device sizes such that the maximum possible percentage of manufactured chips meets all performance specifications.

In general, a given ECD will have multiples goals in the form of a plurality of constraints and objectives. A simplifying assumption that can sometimes be made to optimize such ECDs is to assume that a measure of the quality of a given ECD can be reduced to a single cost function, which generally depends on the design variables and performance metrics of the ECD, and which can optimized by any suitable method. To arrive at a value of the cost function for a given design point usually requires multiple circuit simulations of the ECD.

One way for designers to choose circuit device sizes to minimize the related cost function is to use a software-based optimization tool 20 shown at FIG. 1. The optimization tool 20 includes a problem setup module 22 that includes particulars of the ECD to be optimized. The problem setup module 22 is connected to an optimizer 24, which is also connected to a simulation module 26. The particulars of the ECD can include a netlist of the ECD, performance metrics, design variables, process variables and environmental variables of the ECD. The problem setup module 22 also defines the steps to be followed to measure the performance metrics as a function of the ECD's several variables. The problem setup module 22 is in fact where the problem to be studied by the system 20 is setup.

The performance metrics can be a function of these various variables. The design variables can include, e.g., widths and lengths of devices of the ECD. The process variables can be related to random variations in the ECD manufacturing. The environmental variables can include, e.g., temperature, load conditions and power supply. The problem setup module 22 can also include further information about design variables, such as minimum and maximum values; additional environmental variables, such as a set of environmental points to be used as “corners” with which to simulate the ECD; and random variables, which can be in the form of a probability density function from which random sample values can be drawn.

As will be understood by the skilled worker, the procedure to be followed to measure the performance metrics can be in the form of circuit testbenches that are combined with the netlist to form an ultimate netlist. The ultimate netlist can be simulated by a simulation module 26, which is in communication with the problem setup module 22. The simulation module 26 can include, for example, one or more circuit simulators such as, for example, SPICE simulators. The simulation module 26 calculates waveforms for a plurality of candidate designs of the ECD. The waveforms are then processed to determine characteristic values of the ECD. As will be understood by the skilled worker, the plurality of candidate designs is a series of ECDs differing slightly from each other in the value of one or more of their variables.

The problem setup, as defined by the problem setup module 22, is acquired by the simulation module 26, which uses one or more simulators to simulate data for multiple candidate designs of the ECD. The simulation data is stored in a database 28 from where it can be accessed by a processor module 30, which can include, for example, a sampler or a characterizer. The processor module 30 is also in communication with the problem setup module 22. Given the problem setup, the sampler and/or characterizer can perform “sampling” and/or “characterization” respectively, of the ECD in question, by processing the simulation data, to produce characteristic data of the ECD. Based on this characteristic data, the processor module 30 can calculate one or more characteristic values of the ECD. During the course of a sampling or characterization, the database 28 can be populated with the characteristic data provided by the processor module 30 and with the one or more characteristic values of the ECD.

One of the characteristic values is that of the single cost function for a given ECD simulation. Other characteristic values can include, for example, a yield estimate for a given design point, histograms for each performance metric, 2D and 3D scatter plots with variables that include performance metrics, design variables, environmental variables, and process variables. A characteristic value can also represent, amongst others, the relative impact of design variables on yield, the relative impact of design variables on a given performance metric, the relative impact of all design variables vs. all process variables vs. all environmental variables, tradeoffs of yield vs. performances, and yield value for a sweep of a design variable.

The system 20 also includes a display module 32 and a user input module 34 that are used by the designer to set up the optimization problem, invoke an optimization run, and monitor progress and results that get reported back via the database 28. The processor module 30 selects the ECD's candidate designs that have the lowest single cost function values and displays these to the designer within finite time (e.g., overnight) and computer resource constraints (e.g., 5 CPUs available).

Optimization is a challenge due to the nature of the particular design problem. The time taken to compute/simulate/measure the value of the single cost function of a single ECD candidate design can take minutes or more. Therefore only a limited number of candidate designs can actually be examined given the resources at hand. The single cost function is usually a blackbox, which means that it is possibly non-convex, non-differentiable and possibly non-continuous. Consequently, this precludes the use of optimization algorithms that might take advantage of those properties. That is, it is not possible to use algorithms that exploit many simplifying assumptions.

Similar optimization problems exist in many fields other than electric circuit design. In fact, they exist in almost all engineering fields that have parameterizable design problems where simplifying assumptions cannot be made and that have means of estimating a design's cost functions such as with, e.g., a dynamical systems simulator. Such fields include, for example, automotive design, airfoil design, chemical process design and robotics design. As will be understood by the skilled worker, computing a cost function at a given design point, in generally any technical field, can actually include physical processes, such as running a physical robot or automatically performing laboratory experiments according to design points and measuring the results.

As is known in the art, a locally optimal design is one that has lower cost than all its immediate neighbors in design space, whereas a globally optimal design is one for which no other design in the whole design space has a lower cost function. As such, a blackbox optimization problem can be further classified into global or local optimization, depending on whether a globally optimal solution is desired (or at least targeted) or, a locally optimal solution is sufficient. As is also known, a convex mapping is one in which there is only one locally optimal design in the whole design space, and therefore it is also the globally optimal design. A nonconvex mapping means that there is more than one locally optimal design in the design space. Over the years, multiple global blackbox search algorithms have been developed, such as, for example, simulated annealing, evolutionary algorithms, tabu search, branch & bound, iterated local search and particle swarm optimization. Local search algorithms are also numerous and include, for example, Newton-method derivatives, gradient descent and derivative-free pattern search methods.

The challenge in designing optimization algorithms for such problems is to make the most use out of every cost function evaluation that has been made as the optimization progresses through its iterations. One type of optimization algorithms that does this are model-building optimization (MBO) algorithms. An MBO algorithm typically builds models based on candidate designs, also referred to as design points, and on their respective cost function values as they become available at various iterations of the optimization algorithm. That is, MBO algorithms use the set of of {design point, cost} tuples—and use regression-style modeling approaches to help choose the next candidate point(s).

A very notable MBO with a single overall cost function is the Efficient Global Optimization (EGO) algorithm: D. Jones, M. Schonleau, and W. Welch, “Efficient Global Optimization”, J. Global Optimization, vol. 13, pp. 455-592, 1998. More recently, variants with multiple cost functions have emerged too, e.g. J. Knowles, “ParEGO: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems, IEEE Transactions on Evolutionary Computation, No. 1, February 2006, pp. 50-66.

• Provisional Patent
• Utility Patent

• What Is a Patent?
• What Is a Trademark or Servicemark?
• What Is a Copyright?
• Patent Laws