Method and apparatus for optimizing electronic design

• US 6,446,239 B1
• Filed: 01/07/1999
• Issued: 09/03/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: Greidinger, Yaacov (Jacob), Sargisian, Sedrak, Hui, Siu-Tong, Markosian, Ara
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): Kik, Phallaka
• Application Number:
  US09/227,023
• Time in Patent Office: 1,335 Days
• Field of Search: 716/1-21
• US Class Current: 716/122
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A system is disclosed for compacting an initial electronic layout of cells within an initial layout boundary. The system includes forming paths extending from a bottom edge of the layout to a top edge. The paths intersect cells of the initial layout. The system determines which of the paths are critical paths. Critical cuts are then determined. A critical cut is a cut that severs critical paths. A set of cells associated with a critical cut are removed from the layout and replaced in order to reduce the initial layout boundary.

Claims

1. A method for compacting an initial electronic layout of cells within an initial layout boundary, said initial layout boundary including a bottom edge and a top edge, said method for compacting comprising the steps of:

forming paths extending from said bottom edge to said top edge, said paths intersecting cells of said initial layout;

determining which of said paths are critical paths, each critical path contains line segments all of which are saturated;

removing a set of said cells of said initial layout that are associated with said critical paths;

replacing said set of said cells with replacement cells at one or more locations which allow said initial layout boundary to be reduced in a dimension; and

reducing said initial layout boundary in said dimension.

2. The method of claim 1, wherein:

said paths arc formed for each layer of said cells.

3. The method of claim 1, wherein:

at least one cell of said set of said cells replaced in said step of replacing overlaps on at least one layer with another of said cells.

4. The method of claim 1, wherein said step of removing further comprises the steps of:

defining critical cuts for said critical paths, each critical cut severs each critical path; and

selecting a first critical cut, said set of said cells removed during said step of removing are associated with said first critical cut.

5. The method of claim 4, wherein said step of removing further comprises the step of:

ranking said critical cuts based on cost.

6. The method of claim 5, wherein:

cost of a particular critical cut is determined based on at least one of a group of evaluation parameters consisting of;

power, timing and area.

7. The method of claim 1, wherein said step of replacing comprises the steps of:

selecting one cell of said set of said cells; and

performing at least one of a group of operations for said one cell, said group of operations includes replacing said one cell with a rotated version of said one cell, replacing said one cell with different shaped version of said one cell and substituting another cell for said one cell.

8. The method of claim 7, wherein said step of selecting comprises the steps of:

ranking said set of said cells based on cost; and

selecting said one cell because it has a best cost.

9. The method of claim 8, wherein:

cost is determined on the basis of at least one of a group of evaluation parameters consisting of;

power, timing and area.

10. An apparatus for compacting an initial electronic layout of cells within an initial layout boundary, said initial layout boundary including a bottom edge and a top edge, said apparatus comprising:

means for forming paths extending from said bottom edge to said top edge, said paths intersecting cells of said initial layout;

means for determining which of said paths are critical paths, each critical path containing line segments all of which are saturated;

means for removing a set of said cells of said initial layout that are associated with said critical paths;

means for replacing said set of said cells with replacement cells at one or more locations which allow said initial layout boundary to be reduced in a dimension; and

means for reducing said initial layout boundary in said dimension.

11. A computer usable storage medium having computer readable program code embodied therein for compacting an initial electronic layout of cells within an initial layout boundary, said initial layout boundary including a bottom edge and a top edge said computer readable program code including:

first computer readable program code, said first computer readable program code forms paths extending from said bottom edge to said top edge, said paths intersecting cells of said initial layout;

second computer readable program code, said second computer readable program code determines which of said paths are critical paths, each critical path containing line segments all of which are saturated;

third computer readable program code, said third computer readable program code removes a set of said cells of said initial layout that are associated with said critical paths;

fourth computer readable program code, said fourth computer readable program code replaces said set of said cells with replacement cells at one or more locations which allow said initial layout boundary to be reduced in a dimension; and

fifth computer readable program code, said fifth computer readable program code reduces said initial layout boundary in said dimension.

12. A computer usable storage medium according to claim 11, wherein:

said paths are formed for each layer of a cell.

13. A computer usable storage medium according to claim 11, wherein:

at least one cell of said set of said cells overlaps. on at least one layer with another of said cells.

14. A computer usable storage medium according to claim 11, wherein said third computer readable program code further comprises:

computer readable program code means for defining critical cuts for said critical paths, each critical cut severs each critical path; and

computer readable program code means for selecting a first critical cut, said set of said cells are associated with said first critical cut.

15. A computer usable storage medium according to claim 14, wherein the computer readable program code means for defining critical cuts further comprises:

computer readable program code means for ranking said critical cuts based on cost.

16. A computer usable storage medium according to claim 15, wherein:

cost of a particular critical cut is determined based on at least one of a group of evaluation parameters consisting of;

power, timing and area.

17. A computer usable storage medium according to claim 11, wherein said fourth computer readable program code further comprises:

computer readable program code means for selecting one cell of said set of said cells; and

computer readable program code means for performing at least one of a group of operations for said one cell, said group of operations includes replacing said one cell with a rotated version of said one cell, replacing said one cell with different shaped version of said one cell and substituting another cell for said one cell.

18. A computer usable storage medium according to claim 17, wherein the computer readable program code means for selecting further comprises:

computer readable program code means for ranking said set of said cells based on cost; and

computer readable program code means for selecting said one of said set of cells as having a best cost.

19. A computer usable storage medium according to claim 18, wherein said cost is determined based on at least one of a group of evaluation parameters consisting of:

power, timing and area.

20. A method for compacting an initial electronic layout of cells within an initial layout boundary, said initial layout boundary including a bottom edge and a top edge, said method for compacting comprising the steps of:

identifying one or more critical paths in said initial layout, said critical paths include adjacent cells which are too close together;

identifying a first critical cut severing a set of said critical paths, said first critical cut identifies at least one cell from each critical path of said set of critical paths; and

removing and replacing said at least one cell from each critical path.

21. A method according to claim 20, wherein said step of identifying a first critical cut comprises the step of:

identifying a set of critical cuts, each of said set of critical cuts servers each critical path;

ranking all of said critical cuts based on cost; and

choosing said first critical cut as having a best cost.

22. A method according to claim 20, wherein said step of identifying one for more critical paths comprises the steps of:

forming paths extending from said bottom edge to said top edge, said paths include edge segments between cells of said initial layout; and

determining which of said paths are critical paths, said critical paths include adjacent cells which are too close together.

23. A method according to claim 20, wherein said step of removing and replacing comprises the steps of:

adding replacement cells at one or more locations which allow said initial layout boundary to be reduced in a dimension; and

reducing said initial layout boundary in said dimension.

24. A method according to claim 23, wherein said step of adding replacement cells includes performing one of a set of operations, said set of operations comprises:

replacing a first cell with a rotated version of said first cell;

replacing said first cell with a different shaped version of said first cell; and

substituting another cell for said first cell.

25. A method according to claim 20, wherein said step of removing and replacing includes the step of:

reducing said initial layout boundary.

26. A method according to claim 20, wherein:

said critical paths are formed from edge segments that are saturated on at least one layer.

27. A method according to claim 20, wherein said step of removing and replacing 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.

28. A method according to claim 27, wherein said step of identifying one or more critical paths includes the steps of:

forming paths extending from said bottom edge to said 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 because cells are too close together; and

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

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 compacting an initial electronic layout of cells within an initial layout boundary, said initial layout boundary including a bottom edge and a top edge, said method for compacting comprising the steps of:

identifying one or more critical paths in said initial layout, said critical paths include adjacent cells which are too close together;

identifying a first critical cut severing a set of said critical paths, said first critical cut identifies at least one cell from each critical path of said set of critical paths; and

removing and replacing said at least one cell from each critical path.

30. One or more processor readable storage devices according to claim 29, wherein said step of removing and replacing comprises the steps of:

adding replacement cells at one or more locations which allow said initial layout boundary to be reduced in a dimension; and

reducing said initial layout boundary in said dimension.

31. One or more processor readable storage devices according to claim 30, wherein said step of identifying a first critical cut comprises the step of:

identifying a set of critical cuts, each of said set of critical cuts servers each critical path;

ranking all of said critical cuts based on cost; and

choosing said first critical cut as having a best cost.

32. One or more processor readable storage devices according to claim 30, wherein said step of identifying one or more critical paths comprises the steps of:

forming paths extending from said bottom edge to said top edge, said paths include edge segments between cells of said initial layout; and

determining which of said paths are critical paths, said critical paths include adjacent cells which are too close together.

33. One or more processor readable storage devices according to claim 30, wherein:

said critical paths are formed from edge segments that are saturated on at least one layer.

34. One or more processor readable storage devices according to claim 29, wherein said step of removing and replacing 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.

35. One or more processor readable storage devices according to claim 29, wherein said step of identifying one or more critical paths includes the steps of:

forming paths extending from said bottom edge to said 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 because cells are too close together; and

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

36. An apparatus for compacting an initial electronic layout of cells within an initial layout boundary, said initial layout boundary including a bottom edge and a top edge, said apparatus comprising:

an interface;

a storage device; and

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

identifying one or more critical paths in said initial layout, said critical paths include adjacent cells which are too close together;

identifying a first critical cut severing each of said critical paths, said first critical cut identifies at least one cell from each critical path;

removing and replacing said at least one cell from each critical path; and

reducing said initial layout boundary due to said step of removing and replacing.

37. An apparatus according to claim 36, wherein said step of identifying a critical cut comprises the steps of:

identifying a set of critical cuts, each of said set of critical cuts servers each critical path;

ranking all of said critical cuts based on cost; and

choosing said first critical cut as having a best cost.

38. An apparatus according to claim 36, wherein said step of identifying one or more critical paths comprises the steps of:

forming paths extending from said bottom edge to said top edge, said paths include edges between cells of said initial layout; and

determining which of said paths are critical paths, said critical paths include adjacent cells which are too close together.

39. An apparatus according to claim 38, wherein:

said critical paths are formed from edge segments that are saturated on at least one layer.

40. An apparatus according to claim 36, wherein said step of removing and replacing 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.