Data processing: artificial intelligence – Machine learning – Genetic algorithm and genetic programming system
Reexamination Certificate
1999-06-17
2002-07-23
Black, Thomas (Department: 2121)
Data processing: artificial intelligence
Machine learning
Genetic algorithm and genetic programming system
C706S919000, C706S921000, C714S006130, C714S724000, C716S030000
Reexamination Certificate
active
06424959
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of automatic development of complex structures; more particularly, the present invention relates to the automatic creation of the topology, component sizing, placement, and routing of components in complex structures, such as, for example, electrical circuits or mechanical system.
BACKGROUND OF THE INVENTION
Engineers are often called upon to design complex structures, such as electrical circuits or mechanical systems, that satisfy certain high-level design goals or requirements. The design of such structures is ordinarily thought to require human intelligence and typically involves intricate tradeoffs between competing design considerations.
Electrical circuits, for example, are composed of a variety of types of components, including resistors, capacitors, inductors, diodes, transistors, and energy sources. The individual components of an electrical circuit may be connected to one another in a particular topological arrangement to form an electrical circuit. Moreover, the actual physical location on a printed circuit board, a silicon wafer, or other substrate is often important in determining the behavior or usefulness of a circuit.
Similarly, mechanical structures are composed from a variety of types of components, including springs, dash pots, wheels, belts, gears, pulleys, and so forth. The individual components of a mechanical system are connected to one another in a particular topological arrangement. Moreover, the actual physical location of the components, in two or three dimensions, in relation to each other plays a crucial role in determining the behavior of a mechanical system.
In designing an electrical circuit, mechanical structure, or other complex structure, the goal is to attain certain desired values of one or more observable behavioral quantities (e.g., certain voltages at certain times or frequencies at a certain probe point in the circuit, velocity of a certain mechanical part at a certain time) and, often, certain values of certain additional characteristics (e.g., the cost or number of components).
The creation of a complex structure typically requires creation of the topology, component sizing, placement, and routing of components of complex structures where the structure satisfies certain user-specified high-level design requirements.
The topology of an electrical circuit or mechanical system refers to the number of components, the type of each component (e.g., resistor, spring), and a list of all the connections between the leads of the components (e.g., leads of a resistor, ends of a spring). Topology also includes information about whether a particular lead or other type of interface point of a particular component is connected, in a graphical sense, to the lead of another component. That is, “topology” herein refers to whether or not a connection exists between two particular leads or interface points of components, and does not include information about the actual physical location (placement) of the component or about the actual physical location (routing) of the connecting means (wires, in the case of circuits) that connect the leads of components.
The sizing of a circuit refers to the component value(s) of each component. The sizing of a component is typically a numerical value (e.g., the capacitance of a capacitor, the spring constant of a spring), but is sometimes a non-numerical parameter (e.g., whether an electrical energy source is AC or DC, or the material used for a particular mechanical component).
Placement involves the assignment of each of the circuit's components to a particular physical location. In the case of electrical circuits, electrical components are placed onto a printed circuit board, silicon wafer, or other substrate. In mechanical systems, placement involves the assignment of each of the system's components to a particular physical location in two or three dimensions.
Routing involves the assignment of a particular physical location to the connecting mechanism (e.g., wires) between the leads of the structure's components.
The actual physical location (placement) of components, in two or three dimensions, is almost always crucial to the operation of mechanical systems.
Similarly, for electrical circuits, the actual physical location (placement) of components and the actual physical location (routing) of the wires that connect the components is often important for various different reasons. For example, it may be desirable to minimize the total area occupied by the circuit. Two circuits may have identical topology and sizing (e.g., the same number of transistors and capacitors whose leads are topologically connected in the same way), but one circuit may be preferable to the other because it is laid out in such a way that it occupies less space. In addition, the routing is often crucial because it affects the distance between two components (thereby affecting, say, the time required for an electrical signal to travel between two components along a wire). Also, the exact physical location of each component and wire is important because electrical components subtly interact with one another based on their physical location. These interactions, called parasitic effects, are generally small in magnitude (relative to other effects within the circuit) and can sometimes be ignored in simple circuits operating in non-challenging regimes. However, for many operating regimes, it is impossible to design a practical circuit without considering parasitic effects. For example, parasitic effects may crucially affect the performance of a circuit operating, say, at radio frequencies (RF).
Search Techniques
There are many techniques for searching a space for its optimum points, including, as examples, hill-climbing, simulated annealing, and genetic programming.
A search through any search space involves starting with one or more entities (points) from the search space, ascertaining the “goodness” of the entity for solving the problem at hand, creating a new candidate entity by modifying an existing entity, ascertaining the “goodness” of the new candidate entity, and using the “goodness” measure to select among entities. The “goodness” measure is typically called the “fitness measure” when talking about genetic programming and “energy level” when talking about simulated annealing. The term “fitness” will be used below to refer to either the fitness measure in a genetic programming sense and the energy level in a simulated annealing sense.
Search by Use of Hill Climbing
Simple hill climbing involves starting with a single initial entity (point) in the search space, ascertaining the fitness of the entity, creating a new (usually nearby) candidate entity, ascertaining the fitness of the new candidate entity, and using the fitness measure to select between the preexisting entity and the new candidate entity. In hill climbing, a new candidate point with a better fitness than the preexisting point is unconditionally selected. Conducting a search using hill climbing through a space of entities in a nontrivial problem typically results in the search becoming trapped at a local optimum point rather than finding the global optimum point of the search space.
Search by Use of Simulated Annealing
Simulated annealing (Kirkpatrick, Gelatt, and Vecchi 1983; Aarts and Korst 1989) resembles hill climbing in that it is a point-to-point search technique. Like hill climbing, it employs a problem-specific probabilistic modification operation (usually called a mutation when talking about simulated annealing) for modifying the current entity (point) in the search space in order to obtain a new candidate entity. At each step of the search, the current point in the search space is modified using the modification operator and the new point's fitness is ascertained. In general terms, the beginning of a run of simulated annealing conducts a broad-based search for promising regions of the search space, while the end of the run resembles does hill-climbing in a localized area.
Specificall
Bennett, III Forrest H.
Koza John R.
Black Thomas
Blakely , Sokoloff, Taylor & Zafman LLP
Holmes Michael B.
Koza John R.
LandOfFree
Method and apparatus for automatic synthesis, placement and... 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 apparatus for automatic synthesis, placement and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for automatic synthesis, placement and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2917487