Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2002-01-25
2004-07-20
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C702S021000, C706S020000
Reexamination Certificate
active
06766497
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to computerized optimization techniques and more specifically to techniques based on a genetic model.
BACKGROUND OF THE INVENTION
Due to the large number of variables involved, some optimization problems have an exceedingly large solution space. For example, selecting design parameters such as size and threshold voltage for each of thousands of instances (i.e., gates) in an integrated circuit to minimize power consumption while maintaining acceptable timing performance is such a problem.
One approach to solving complex optimization problems is genetic optimization, an iterative, computer-implemented technique in which candidate solutions are generated using a genetic model. The genetic model typically includes a set of N randomly generated chromosomes, each chromosome comprising a number of genes. Since each gene represents a particular state of a parameter to be optimized in one part of a system (e.g., the size of one instance in an integrated circuit), each chromosome represents a possible solution to the global optimization problem. In a typical application, the configuration specified by each chromosome is evaluated, and a figure of merit or “score” is assigned to each chromosome. For example, in the case of an integrated circuit design, a circuit having the characteristics of each chromosome may be simulated to assign a score indicating the desirability of its power consumption and timing performance. Once each chromosome has been assigned a score, the N chromosomes may be “mated” or “mutated” in various ways to create other potential solutions or “children,” which may, in turn, be evaluated and assigned a score. If a child has a higher score than one of the original N chromosomes, the chromosome with the lowest score may be discarded. Eventually, the candidate solutions generated in this fashion may converge to the global optimum.
A key aspect of such a genetic algorithm is reproduction, the method by which new solutions are generated during each “mating season.” In one well-known approach, pairs of chromosomes or “mating combinations” are formed, and mating combinations are randomly selected for possible mating. If the composite score of a mating combination is higher than a predetermined threshold, the chromosomes are mated. Otherwise, they are not mated. However, this approach can lead to too many or too few children being produced during each mating season, if the threshold is set too high or too low. The consequence in either case is slower convergence.
It is thus apparent that there is a need in the art for an improved method and system for reproduction in a genetic optimization process.
SUMMARY OF THE INVENTION
A method is provided for reproduction in a computer-implemented optimization process based on a genetic model. Both a system and a computer-readable storage medium containing program instructions are provided for carrying out the method.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.
REFERENCES:
patent: 5930780 (1999-07-01), Hughes et al.
patent: 6181945 (2001-01-01), Lee
patent: 6363368 (2002-03-01), Shinagawa
patent: 2002/0010692 (2002-01-01), Sasagawa et al.
patent: 2002/0095393 (2002-07-01), McHaney
patent: 2002/0169563 (2002-11-01), de Carvalho Ferreira
Li et al., “Nonlinear mixed integer programming problems using genetic algorithm and penalty function” Systems, Man, and Cybernetics, 1996., IEEE International Conference on, vol.: 4, Oct. 14-17, 1996 pp. 2677-2682 vol. 4.*
Lin et al., “Genetic algorithm for optimal distribution system planning” Power System Technology, 1998. Proceedings. POWERCON '98. 1998 International Conference on, vol.: 1, Aug. 18-21, 1998 pp. 241-245 vol. 1.*
Pham et al., “Genetic algorithm using gradient-like reproduction operator” Electronics Letters , vol.: 31 Issue:18 , Aug. 31, 1995 pp. 1558-1559.*
Alexander Schatten, Genetic Algorithms Short Tutorial, Jul. 8, 2001, pp. 1-12, http://www.ifs.tuwien.ac.at/aschatt/info/ga/genetic.html.
Croft Thomas M.
Liu Andrea
LandOfFree
Method and system for reproduction in a genetic optimization... 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 and system for reproduction in a genetic optimization..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for reproduction in a genetic optimization... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3194792