System and method for multi-constraint domain electronic system design mapping

• US 5,781,446 A
• Filed: 05/07/1996
• Issued: 07/14/1998
• Est. Priority Date: 05/07/1996
• Status: Expired due to Fees

• Current Assignee: Flexible Solutions, Inc.
• Original Assignee: Flexible Solutions, Inc.
• Inventors: Wu, Tom J.
• Primary Examiner(s): Voeltz, Emanuel T.
• Assistant Examiner(s): GARBOWSKI, LEIGH M
• Application Number:
  US08/648,302
• Time in Patent Office: 798 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491
• US Class Current: 716/122
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: H05K 3/0005 for designing circuits by computer

Abstract

Visualization of how multiple constraints may effect design implementation choices and characterization of design spaces is provided by a system for computer aided design of a higher level electronic system which is itself constructed from lower level entities. A plurality of violation free regions is defined, with each region being determined by a particular entity-to-entity spacing rule or rule set. The multiplicity of violation free regions define ranges of valid position placements for entities within a particular constraint domain. Multiple constraint domains are handled by defining additional violation free regions which determine ranges of valid position placements for entities which satisfy the various additional constraint domains. The various violation free regions are logically combined to define a resulting violation free volume in which a component may be placed which will satisfy the constraints of all of the constraint domains whose violation free regions have been logically combined.

Claims

1. A system for computer aided design of a higher level electronic system which is constructed of a multiplicity of lower level entities the relative placement positions of each of which is limited by a multiplicity of dissimilar constraints defining an n-dimensional constraint domain, the system comprising:

a multiplicity of dissimilar input indicia sets, each indicia set representing a particular one of a corresponding set of dissimilar entity-to-entity layout spacing rules; and

a multiplicity of design spaces, each design space defining a respective one of the multiplicity of dissimilar constraint domains and comprising violation free regions defining those areas in which an entity may be placed without violating an entity-to-entity spacing rule, each design space associated with a particular one of the multiplicity of dissimilar input indicia sets, the violation free regions of each design space constructed in accordance with the particular input indicia set associated with that design space.

2. The system of claim 1 further comprising logic means for combining violation free regions of at least two design spaces to define thereby a resulting violation free volume in which an entity may be placed without violating the entity-to-entity spacing rules of either design space.

3. The system of claim 2 wherein said violation free regions of said multiplicity of dissimilar constraint domains are iteratively combined to define thereby a resulting violation free volume in which an entity may be placed without violating the entity-to-entity spacing rules of any dissimilar constraint domain.

4. The system of claim 3 wherein said higher level electronic system is selected from the group consisting of printed circuit boards, VLSI integrated circuits and multi-chip modules and wherein said multiplicity of lower entities is selected from the group consisting of printed circuit board components, standard cells and module chips.

5. The system of claim 3 wherein each violation free region is adaptively reconfigured upon placement of an entity to exclude said placed entity and thereby define a next violation free volume in which a next entity may be placed.

6. A system for computer aided design of a higher level electronic system which is constructed of a multiplicity of lower level entities the relative positions of each of which is limited by a multiplicity of dissimilar constraints defining an n-dimensional constraint domain, the system comprising:

means for evaluating a first protocol set comprising a first constraint domain to thereby define first violation free regions in which an entity may be positioned;

means for evaluating a second protocol set comprising a second constraint domain unrelated to the first constraint domain to thereby define second violation free regions in which an entity may be positioned; and

logic means for combining the first and second violation free regions to define thereby a resulting violation free volume in which an entity may be placed, whereby the violation free volume represents an entity placement design space within which an entity will satisfy the constraints of both the first and second constraint domains.

7. A system in accord with claim 6, wherein the first violation free region defines a range of valid position placements for an entity which satisfies the first protocol set of the first constraint domain, the first violation free region thereby mapping an available design space for the entity in that constraint domain.

8. A system in accord with claim 7, wherein the second violation free region defines a range of valid position placements for an entity which satisfies the second protocol set of the second constraint domain, the second violation free region thereby mapping an available design space for the entity in that constraint domain.

9. A system in accord with claim 8, wherein the first and second violation free regions are expressed as polygons, the areas enclosed thereby defining the range of valid position placements for an entity in the respective constraint domains.

10. A system in accord with claim 9, wherein the resulting violation free volume is expressed as polyhedra, the volume enclosed thereby defining a range of valid position placements for an entity which satisfies the constraints of both the first and second constraint domains.

11. A system in accord with claim 10, wherein each violation free region is dynamically reconfigured upon placement of an entity with respect thereto to exclude said placed entity from the range of valid position placements to thereby define a next violation free volume in which a next entity may be placed.

12. A system in accord with claim 10, wherein the first protocol set comprises physical layout design rule indicia selected from the group consisting of entity size, entity-to-entity spacing, entity height, entity orientation entity thermal dissipation and automatic insertion clearance rules.

13. A system in accord with claim 10, wherein the second protocol set comprises electrical design rule indicia selected from the group consisting of interconnect routability, interconnect channel density, interconnect delays, signal critical timing and skew, EMI emissions and signal noise.

14. A method for designing a higher level electronic system which is itself constructed of a multiplicity of lower level entities the relative positions of each of which is limited by a multiplicity of dissimilar constraints defining an n-dimensional constraint domain, the method comprising:

defining first violation free regions in which an entity may be positioned by evaluating a first protocol set comprising a first constraint domain;

defining second violation free regions in which an entity may be positioned by evaluating a second protocol set comprising a second constraint domain unrelated to the first constraint domain;

logically combining the first and second violation free regions to define thereby a resulting violation free volume in which an entity may be placed, whereby the violation free volume represents an entity placement design space within which an entity will satisfy the dissimilar constraints of both the first and second constraint domains.

15. A method in accord with claim 14, wherein the first violation free region defines a range of valid position placements for an entity which satisfies the first protocol set of the first constraint domain, the first violation free region thereby mapping an available design space for the entity in that constraint domain.

16. A method in accord with claim 15, wherein the second violation free region defines a range of valid position placements for an entity which satisfies the second protocol set of the second constraint domain, the second violation free region thereby mapping an available design space for the entity in that constraint domain.

17. A method in accord with claim 16, wherein the first and second violation free regions are expressed as polygons, the areas enclosed thereby defining the range of valid position placements for an entity in the respective constraint domains.

18. A system in accord with claim 17, wherein the resulting violation free volume is expressed as polyhedra, the volume enclosed thereby defining a range of valid position placements for an entity which satisfies the constraints of both the first and second constraint domains.

19. The method of claim 14, wherein the logical combination step includes one or more operations selected from the group consisting of logically ANDing, logically ORing, or displaying a logical union of the regions.

20. The method of claim 14, further comprising:

initializing the system by placing a first entity in an arbitrary position, the first entity in cooperation with the first protocol set of the first constraint domain defining the first violation free region in which a next entity may be positioned;

selecting a next entity to be positioned;

placing the next entity in a next position; and

verifying that the next entity placement position is in the first violation free region, whereby the violation free region is dynamically altered by the placement of the next entity.