Method and apparatus for providing multiple electronic design solutions

• US 6,449,761 B1
• Filed: 01/07/1999
• Issued: 09/10/2002
• Est. Priority Date: 03/10/1998
• Status: Expired due to Term

• Current Assignee: Synopsys Incorporated
• Original Assignee: Monterey Design Systems, Inc. (Synopsys Incorporated)
• Inventors: Frankle, Jon, Markosian, Ara, Greidinger, Yaacov (Jacob)
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): GARBOWSKI, LEIGH M
• Application Number:
  US09/227,491
• Time in Patent Office: 1,342 Days
• Field of Search: 716/1, 716/2, 716/8, 716/9, 716/10, 716/11, 716/7
• US Class Current: 716/122
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

An electronic computer aided design system provides for automated operation of a plurality of design tools to produce multiply design solutions to an initial circuit layout. Through the user entry of relative weights for: power, timing and area, different solutions to an initial layout can be generated exhibiting the requested balance of improvements over the original layout. A novel parts placement process is disclosed which prioritizes the reconfiguration of the initial design in a manner which assures that the multiple solutions will be generated which exhibit improved performance over the original layout in accordance with the priorities established by the user.

Claims

1. A method for generating multiple new solutions to an initial layout of cells, comprising the steps of:

identifying a set of critical paths in said initial layout, each critical path includes adjacent cells which are too close together;

identifying a set of critical cuts, each critical cut severing each of said critical paths; and

creating said new solutions, each new solution corresponds to one of said critical cuts, each new solution is created by removing and replacing at least one cell from each critical path based on said corresponding critical cut, each new solution provides a new layout of cells and differs from said initial layout in relative placement of cells.

2. The method of claim 1, further comprising the step of:

ranking said new solutions according to user defined relative weights for target parameters.

3. The method of claim 2, wherein:

said target parameters include power, timing and area.

4. The method of claim 2, further comprising the steps of:

determining a highest ranked new solution according to said set of relative weights; and

creating additional solutions based on said highest ranked new solution.

5. The method of claim 4, wherein said step of creating additional solutions includes the steps of:

identifying critical paths in said highest ranked new solution;

identifying a set of critical cuts in said highest ranked new solution; and

determining said additional solutions, each additional solution corresponds to a critical cut in said highest ranked new solution, each additional solution is created by removing and replacing cells in said highest ranked new solution.

6. The method of claim 2, further comprising the step of:

reporting said ranking of said new solutions.

7. The method of claim 1, further comprising the step of:

graphically displaying said new solutions.

8. The method of claim 1, wherein said removing and replacing of cells in said step of creating new solutions includes the steps of:

removing a first set of cells;

compressing said initial layout;

constructing channels in said compressed initial layout; and

fitting variants of said first set of cells into said channels.

9. A method according to claim 8, wherein:

said variants of said first set of cells includes different sized versions of said first set of cells, different shaped versions of said first set of cells and different oriented versions of said first set of cells.

10. The method of claim 1, wherein said step of identifying a set of critical paths includes the steps of:

forming paths extending from a bottom edge to a top edge, said paths intersecting cells of said initial layout, said paths each including line segments linking a lower cell to an upper cell;

determining which line segments are saturated; and

determining which of said paths are critical paths, each critical path contains line segments which are saturated on at least one routing layer.

11. The method of claim 1, wherein:

said step of identifying a set of critical cuts includes ranking said critical cuts; and

said step of creating new solutions includes selecting a subset of said critical cuts based on said ranking, said new solutions correspond to said subset of said critical cuts.

12. The method of claim 1, wherein:

adjacent cells are too close together if routing cannot take place.

13. The method of claim 1, further comprising the step of:

determining whether adjacent cells are too close together, including comparing a required spacing between a layer of adjacent cells to a spacing between said adjacent cells in said initial layout.

14. One or more processor readable storage devices for storing processor readable code, said processor readable code for programming one or more processors to perform a method for generating multiple new solutions to an initial layout of cells, the method comprising the steps of:

identifying critical paths in said initial layout, each critical path includes adjacent cells which are too close together;

identifying a set of critical cuts, each critical cut severing each of said critical paths; and

creating said new solutions, each new solution corresponds to one of said critical cuts, each new solution is created by removing and replacing at least one cell from each critical path based on said corresponding critical cut, each new solution provides a new layout of cells and differs from said initial layout in relative placement of cells.

15. The computer readable program code means of claim 14, further comprising:

computer readable program code means for ranking the solutions in the solution list.

16. The computer readable program code means of claim 15, wherein the ranking of the solutions is deter mined on the basis of at least one of the following group of evaluation parameters consisting of:

power, timing and area.

17. One or more processor readable storage devices according to claim 15, wherein said method further comprising the steps of:

determining a highest ranked new solution according to said set of relative weights; and

creating additional solutions based on said highest ranked new solution.

18. One or more processor readable storage devices according to claim 17, wherein said step of creating additional solutions includes the steps of:

identifying critical paths in said highest ranked new solution;

identifying a set of critical cuts in said highest ranked new solution; and

determining said additional solutions, each additional solution corresponds to a critical cut in said highest ranked new solution, each additional solution is created by removing and replacing cells in said highest ranked new solution.

19. One or more processor readable storage devices according to claim 14, wherein said removing and replacing of cells in said step of creating new solutions includes the steps of:

removing a first set of cells;

compressing said initial layout;

constructing channels in said compressed initial layout; and

fitting variants of said first set of cells into said channels.

20. One or more processor readable storage devices according to claim 14, wherein step of identifying critical paths includes the step of:

forming paths extending from a bottom edge to a top edge, said paths intersecting cells of said initial layout, said paths each including line segments linking a lower cell to an upper cell;

determining which line segments are saturated; and

determining which of said paths are critical paths, each critical path contains line segments which are saturated on at least one routing layer.

21. One or more processor readable storage devices according to claim 14, wherein:

said step of identifying a set of critical cuts includes ranking said critical cuts; and

said step of creating new solutions includes selecting a subset of said critical cuts based on said ranking, said new solutions correspond to said subset of said critical cuts.

22. An apparatus used for generating multiple new solutions to an initial layout of cells, comprising:

an interface;

a storage device; and

a processor in communication with said interface and said storage device, said process performs a method comprising the steps of;

identifying critical paths in said initial layout, each critical path includes adjacent cells which are too close together,

identifying a set of critical cuts, each critical cut severing each of said critical paths, and

creating said new solutions, each new solution corresponds to one of said critical cuts, each new solution is created by removing and replacing at least one cell from each critical path based on said corresponding critical cut, each new solution provides a new layout of cells and differs from said initial layout in relative placement of cells.

23. An apparatus according to claim 22, wherein said method further comprises the steps of:

ranking said new solutions according to user defined relative weights for target parameters;

determining a highest ranked new solution according to said set of relative weights; and

creating additional solutions based on said highest ranked view solution.

24. An apparatus according to claim 22, wherein said step of creating additional solutions includes the steps of:

identifying critical paths in said highest ranked new solution;

identifying a set of critical cuts in said highest ranked new solution; and

determining said additional solutions, each additional solution corresponds to a critical cut in said highest ranked new solution, each additional solution is created by removing and replacing cells critical paths in said highest ranked new solution.

25. An apparatus according to claim 22, wherein said removing and replacing of cells in said step of creating new solutions includes the steps of:

removing a first set of cells;

compressing said initial layout;

constructing channels in said compressed initial layout; and

fitting variants of said first set of cells into said channels.

26. A method for generating multiple new solutions to an initial layout of cells, each new solution provides a new layout of cells and differs from said initial layout in relative placement of cells, said method comprising the steps of:

receiving a set of relative weights for target parameters;

creating a first set of new solutions, each new solution in said first set is created by removing and replacing cells from said initial layout;

ranking said first set of new solutions according to said set of relative weights;

determining a highest ranked solution from said first set of new solutions; and

creating a second set of new solutions each new solution in said second set is created by removing and replacing cells from said highest ranked solution from said first set of new solutions.

27. A method according to claim 26, further comprising the steps of:

ranking said second set of new solutions according to said set of relative weights; and

reporting said ranking of said second set of new solutions.

28. A method according to claim 26, wherein:

said target parameters include power, timing, and area.

29. One or more processor readable storage devices for storing processor readable code, said processor readable code for programming one or more processors to perform a method for generating multiple new solutions to an initial layout of cells, each new solution provides a new layout of cells and differs from said initial layout in relative placement of cells, said method comprising the steps of:

receiving a set of relative weights for target parameters;

creating a first set of new solutions, each new solution in said first set is created by removing and replacing cells from said initial layout;

ranking said first set of new solutions according to said set of relative weights;

determining a highest ranked solution from said first set of new solutions; and

creating a second set of new solutions, each new solution in said second set is created by removing and replacing cells from said highest ranked solution from said first set of new solutions.

30. One or more processor readable storage devices according to claim 29, wherein said method further comprises the steps of:

ranking said second set of new solutions according to said set of relative weights; and

reporting said ranking of said second set of new solutions.

31. One or more processor readable storage devices according to claim 29, wherein:

said target parameters include power, timing, and area.