Method and apparatus for automatic synthesis, placement and routing of complex structures

• US 6,424,959 B1
• Filed: 06/17/1999
• Issued: 07/23/2002
• Est. Priority Date: 06/17/1999
• Status: Expired due to Term

• Current Assignee: John R. Koza
• Original Assignee: John R. Koza
• Inventors: Bennett, Forrest H. III, Koza, John R.
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): Holmes, Michael B.
• Application Number:
  US09/336,373
• Time in Patent Office: 1,132 Days
• Field of Search: 706/13, 706/27, 706/921, 706/919, 707/102, 716/8
• US Class Current: 706/13
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: Y10S 706/919 Designing, planning, programming, CAD, CASE
• CPC Class Codes: Y10S 706/921 Layout, e.g. circuit, construction

Abstract

The present invention consists of a method and apparatus for the automatic creation of the topology, component sizing, placement, and routing of complex structures, such as electronic circuits or mechanical systems, to satisfy prespecified high-level design goals. The present invention uses a population of entities which are evolved over a series of generations by an iterative process involving the application of operations, such as mutation, crossover, reproduction, and architecture-altering operations. The individuals in the population are each developed, in a developmental process, into a structure that may potentially satisfy the design goals. The present invention also determines the placement of components within the developing structure and determining the routing of the connecting means (wires for electrical circuits) between the components. The behavior of the structures is evaluated in relation to the high-level design goals, and those structures more closely satisfying the design goals are evolved further until a structure is generated that either meets the prespecified design goal. In this manner, the topology, component sizing, placement, and routing of a complex structure may be obtained.

Claims

1. In a system having at least one entity, wherein each entity comprises at least one constructing action, a system-implemented iterative process for creating a design of a structure that satisfies prespecified design goals, the iterative process comprising the iteration of a series of steps which comprises:

executing at least one constructing action in the at least one entity to develop a structure comprising a plurality of components, the execution of the at least one constructing actions determining both the topological connections between components of the structure and the physical location of each of the components of the structure,

ascertaining the degree to which the structure satisfies the prespecified design goals,

selecting from among the at least one entity, wherein an entity that satisfies the prespecified design goals to a greater degree than another entity is preferred,

creating at least one candidate entity by applying an operation to modify at least one of the selected entities.

2. The process defined in claim 1 wherein executing at least one constructing action comprises determining at least one value for at least one of the plurality of components.

3. The process defined in claim 1 wherein executing at least one constructing action comprises determining the physical location of connections between components of the structure.

4. The process defined in claim 1 wherein creating at least one candidate entity comprises performing a mutation operation on the at least one selected entity.

5. The process defined in claim 4 wherein selecting from among at least one entity is performed by simulating annealing.

6. The process defined in claim 4 wherein selecting from among at least one entity is performed by hill climbing.

7. The process defined in claim 1 wherein said at least one entity comprises a population of entities.

8. The process defined in claim 7 wherein creating at least one candidate entity comprises performing crossover among a group of at least two entities of the population, the group comprising a selected entity and at least one other entity from the population, wherein crossover is performed so that the new entity created comprises at least a portion of each of the at least two entities.

9. The process defined in claim 1, wherein creating at least one candidate entity comprises performing reproduction.

10. The process defined in claim 7 wherein creating at least one candidate entity comprises performing an architecture-altering operation.

11. The process defined in claim 7 wherein selecting one of the at least one entity is performed by fitness proportionate selection.

12. The process defined in claim 7 wherein selecting one of the at least one entity is performed by tournament selection.

13. The process defined in claim 1 wherein at least one of entity comprises at least one externally invokable sub-entity and at least one internally invokable sub-entity, said at least one externally invokable sub-entity capable of including at least one invocation of said at least one internally invokable sub-entity.

14. The process defined in claim 13 wherein said at least one entity comprises at least two internally invokable sub-entities and wherein at least one of said internally invokable sub-entities is capable of including at least one invocation of another of said internally invokable sub-entities.

15. The process defined in claim 1 wherein said at least one entity comprises a randomly created entity.

16. The process defined in claim 1 wherein said at least one entity comprises an entity supplied to the process.

17. The process defined in claim 1 wherein ascertaining the degree to which an entity satisfies the prespecified design goals comprises evaluating the entity by simulating the entity.

18. The process defined in claim 1 wherein ascertaining the degree to which an entity satisfies the prespecified design goals comprises evaluating the entity by observing a physical realization of the entity.

19. The method defined in claim 1 wherein each of said at least one entities conforms to a constrained syntactic structure.

20. The process defined in claim 1 wherein each of said at least one entities is an electrical circuit.

21. The process defined in claim 20 wherein the connections comprise wires.

22. The process defined in claim 1 wherein each of said at least one entities is a mechanical system.

23. The process defined in claim 2 further comprises using an arithmetic-performing subtree to determine said at least one value.

24. The process defined in claim 2 further comprising using a number subject to perturbation by a Gaussian probability distribution to determine said at least one value.

25. The process defined in claim 1 further comprising determining physical location of each of the components of the structure after execution of constructing actions in the entity.

26. The process defined in claim 1 further comprising determining physical location components of the structure during a developmental process by progressively adjusting the physical location of at least one component.

27. The method defined in claim 1 further comprising adjusting the topology of the components by:

determining a size of a first component within the structure; and

adjusting positions of all other components in the structure to compensate for the size of the first component.

28. The process defined in claim 1 wherein ascertaining the degree to which an entity satisfies the prespecified design goals comprises considering parasitic effects between the components of said structure.

29. The process defined in claim 1 wherein ascertaining the degree to which an entity satisfies the prespecified design goals comprises considering the total area occupied by all the components of the structure.

30. The process defined in claim 1 wherein executing constructing actions comprises restraining execution of constructing actions to ensure components are physically located inside a prespecified area.

31. The process defined in claim 1 wherein the at least one entity comprises a population of entities, and further comprising:

dividing the population entities into a plurality of groups;

performing one or more operations of each iteration with respect to each entity in each group using a separate processing node.

32. An iterative computer-implemented process for creating a structural design that satisfies prespecified design goals, the process invoking iterations, each iteration comprising:

developing a structure by executing constructing actions in an entity to simultaneously specify a topological arrangement of components, component values and placement of components with respect to each other; and

determining behavior of the developed structure.

33. An apparatus, for creating a design of a structure that satisfies prespecified design goals, in a system having at least one entity, wherein each entity comprises at least one constructing action, the apparatus comprising:

means for executing at least one constructing action in the at least one entity to develop a structure comprising a plurality of components, the execution of the at least one constructing actions determining both the topological connections between components of the structure and the physical location of each of the components of the structure;

means for ascertaining the degree to which the structure satisfies the prespecified design goals;

means for selecting from among the at least one entity, wherein an entity that satisfies the prespecified design goals to a greater degree than another entity is preferred; and

means for creating at least one candidate entity by applying an operation to modify at least one of the selected entities.

34. The apparatus defined in claim 33 wherein the means for executing at least one constructing action comprises means for determining at least one value for at least one of the plurality of components.

35. The apparatus defined in claim 33 wherein the means for executing at least one constructing action comprises means for determining the physical location of connections between components of the structure.

36. The apparatus defined in claim 33 wherein the means for creating at least one candidate entity comprises means for performing a mutation operation on the at least one selected entity.

37. The apparatus defined in claim 36 wherein the means for selecting selects from among at least one entity using simulating annealing.

38. The apparatus defined in claim 36 wherein the means for selecting selects from among at least one entity using hill climbing.

39. The apparatus defined in claim 33 wherein said at least one entity comprises a population of entities.

40. The apparatus defined in claim 39 wherein the means for creating at least one candidate entity comprises means for performing crossover among a group of at least two entities of the population, the group comprising a selected entity and at least one other entity from the population, wherein crossover is performed so that the new entity created comprises at least a portion of each of the at least two entities.

41. The apparatus defined in claim 33 wherein the means for creating at least one candidate entity comprises means for performing reproduction.

42. The apparatus defined in claim 39 wherein the means for creating at least one candidate entity comprises means for performing an architecture-altering operation.

43. The apparatus defined in claim 39 wherein the means for selecting selects one of the at least one entity using fitness proportionate selection.

44. The apparatus defined in claim 39 wherein the means for selecting selects one of the at least one entity using tournament selection.

45. The apparatus defined in claim 33 wherein at least one of entity comprises at least one externally invokable sub-entity and at least one internally invokable sub-entity, said at least one externally invokable sub-entity capable of including at least one invocation of said at least one internally invokable sub-entity.

46. The apparatus defined in claim 45 wherein said at least one entity comprises at least two internally invokable sub-entities and wherein at least one of said internally invokable sub-entities is capable of including at least one invocation of another of said internally invokable sub-entities.

47. The apparatus defined in claim 33 wherein said at least one entity comprises a randomly created entity.

48. The apparatus defined in claim 33 wherein said at least one entity comprises an entity supplied to the process.

49. The apparatus defined in claim 33 wherein the means for ascertaining the degree to which an entity satisfies the prespecified design goals comprises means for evaluating the entity by simulating the entity.

50. The apparatus defined in claim 33 wherein the means for ascertaining the degree to which an entity satisfies the prespecified design goals comprises means for evaluating the entity by observing a physical realization of the entity.

51. The apparatus defined in claim 33 wherein each of said at least one entities conforms to a constrained syntactic structure.

52. The apparatus defined in claim 33 wherein each of said at least one entities is an electrical circuit.

53. The apparatus defined in claim 52 wherein the connections comprise wires.

54. The apparatus defined in claim 33 wherein each of said at least one entities is a mechanical system.

55. The apparatus defined in claim 34 further comprises means for determining said at least one value using an arithmetic-performing subtree.

56. The apparatus defined in claim 34 further comprising means for determining said at least one value using a number subject to perturbation by a Gaussian probability distribution.

57. The apparatus defined in claim 33 further comprising means for determining physical location of each of the components of the structure after execution of constructing actions in the entity.

58. The apparatus defined in claim 33 further comprising means for determining physical location components of the structure during a developmental process by progressively adjusting the physical location of at least one component.

59. The apparatus defined in claim 33 further comprising means for adjusting the topology of the components, wherein the means for adjusting comprises:

means for determining a size of a first component within the structure; and

means for adjusting positions of all other components in the structure to compensate for the size of the first component.

60. The apparatus defined in claim 33 wherein the means for ascertaining the degree to which an entity satisfies the prespecified design goals comprises means for considering parasitic effects between the components of said structure.

61. The apparatus defined in claim 33 wherein the means for ascertaining the degree to which an entity satisfies the prespecified design goals comprises means for considering the total area occupied by all the components of the structure.

62. The apparatus defined in claim 33 wherein the means for executing constructing actions comprises means for restraining execution of constructing actions to ensure components are physically located inside a prespecified area.

63. The apparatus defined in claim 33 wherein the at least one entity comprises a population of entities, and further comprising:

means for dividing the population entities into a plurality of groups; and

means for performing one or more operations of each iteration with respect to each entity in each group using a separate processing node.

64. An apparatus for creating a structural design that satisfies prespecified design goals, the apparatus comprising:

means for developing a structure by executing constructing actions in an entity to simultaneously specify a topological arrangement of components, component values and placement of components with respect to each other; and

means for determining behavior of the developed structure.

65. A machine-readable medium having stored thereon executable code which causes a machine to perform a method, for creating a design of a structure that satisfies prespecified design goals, in a system having at least one entity, wherein each entity comprises at least one constructing action, the method comprising:

executing at least one constructing action in the at least one entity to develop a structure comprising a plurality of components, the execution of the at least one constructing actions determining both the topological connections between components of the structure and the physical location of each of the components of the structure;

ascertaining the degree to which the structure satisfies the prespecified design goals;

selecting from among the at least one entity, wherein an entity that satisfies the prespecified design goals to a greater degree than another entity is preferred; and

creating at least one candidate entity by applying an operation to modify at least one of the selected entities.

66. The machine-readable medium defined in claim 65 wherein executing at least one constructing action comprises determining at least one value for at least one of the plurality of components.

67. The machine-readable medium defined in claim 65 wherein executing at least one constructing action comprises determining the physical location of connections between components of the structure.

68. The machine-readable medium defined in claim 65 wherein creating at least one candidate entity comprises performing a mutation operation on the at least one selected entity.

69. The machine-readable medium defined in claim 68 wherein selecting from among at least one entity is performed by simulating annealing.

70. The machine-readable medium defined in claim 68 wherein selecting from among at least one entity is performed by hill climbing.

71. The machine-readable medium defined in claim 65 wherein said at least one entity comprises a population of entities.

72. The machine-readable medium defined in claim 71 wherein creating at least one candidate entity comprises performing crossover among a group of at least two entities of the population, the group comprising a selected entity and at least one other entity from the population, wherein crossover is performed so that the new entity created comprises at least a portion of each of the at least two entities.

73. The machine-readable medium defined in claim 65 wherein creating at least one candidate entity comprises performing reproduction.

74. The machine-readable medium defined in claim 71 wherein creating at least one candidate entity comprises performing an architecture-altering operation.

75. The machine-readable medium defined in claim 71 wherein selecting one of the at least one entity is performed by fitness proportionate selection.

76. The machine-readable medium defined in claim 71 wherein selecting one of the at least one entity is performed by tournament selection.

77. The machine-readable medium defined in claim 65 wherein at least one of entity comprises at least one externally invokable sub-entity and at least one internally invokable sub-entity, said at least one externally invokable sub-entity capable of including at least one invocation of said at least one internally invokable sub-entity.

78. The machine-readable medium defined in claim 77 wherein said at least one entity comprises at least two internally invokable sub-entities and wherein at least one of said internally invokable sub-entities is capable of including at least one invocation of another of said internally invokable sub-entities.

79. The machine-readable medium readable medium defined in claim 65 wherein said at least one entity comprises a randomly created entity.

80. The machine-readable medium defined in claim 65 wherein said at least one entity comprises an entity supplied to the process.

81. The machine-readable medium defined in claim 65 wherein ascertaining the degree to which an entity satisfies the prespecified design goals comprises evaluating the entity by simulating the entity.

82. The machine-readable medium defined in claim 65 wherein ascertaining the degree to which an entity satisfies the prespecified design goals comprises evaluating the entity by observing a physical realization of the entity.

83. The machine-readable medium defined in claim 65 wherein each of said at least one entities conforms to a constrained syntactic structure.

84. The machine-readable medium defined in claim 65 wherein each of said at least one entities is an electrical circuit.

85. The machine-readable medium defined in claim 84 wherein the connections comprise wires.

86. The machine-readable medium defined in claim 65 wherein the method each of said at least one entities is a mechanical system.

87. The machine-readable medium defined in claim 66 wherein the method further comprises using an arithmetic-performing subtree to determine said at least one value.

88. The machine-readable medium defined in claim 66 wherein the method further comprises using a number subject to perturbation by a Gaussian probability distribution to determine said at least one value.

89. The machine-readable medium defined in claim 65 wherein the method further comprises determining physical location of each of the components of the structure after execution of constructing actions in the entity.

90. The machine-readable medium defined in claim 65 where in the method further comprises determining physical location components of the structure during a developmental process by progressively adjusting the physical location of at least one component.

91. The machine-readable medium defined in claim 65 wherein the method further comprises adjusting the topology of the components by:

determining a size of a first component within the structure; and

adjusting positions of all other components in the structure to compensate for the size of the first component.

92. The machine-readable medium defined in claim 65 wherein ascertaining the degree to which an entity satisfies the prespecified design goals comprises considering parasitic effects between the components of said structure.

93. The machine-readable medium defined in claim 65 wherein ascertaining the degree to which an entity satisfies the prespecified design goals comprises considering the total area occupied by all the components of the structure.

94. The machine-readable medium defined in claim 65 wherein executing constructing actions comprises restraining execution of constructing actions to ensure components are physically located inside a prespecified area.

95. The machine-readable medium defined in claim 65 wherein the at least one entity comprises a population of entities, and wherein the method further comprises:

dividing the population entities into a plurality of groups; and

performing one or more operations of each iteration with respect to each entity in each group using a separate processing node.

96. A machine-readable medium having stored thereon executable code which causes a machine to perform a method, for creating a structural design that satisfies prespecified design goals, the method comprising:

developing a structure by executing constructing actions in an entity to simultaneously specify a topological arrangement of components;

component values and placement of components with respect to each other; and

determining behavior of the developed structure.