Method for placing logic functions and cells in a logic design using floor planning by analogy

• US 5,696,693 A
• Filed: 03/31/1995
• Issued: 12/09/1997
• Est. Priority Date: 03/31/1995
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Paul, Richard F., Boehm, Arthur F., Rusterholz, John T., Kerzman, Joseph P., Rezek, James E., Aubel, Mark D.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Kik, Phallaka
• Application Number:
  US08/414,881
• Time in Patent Office: 984 Days
• Field of Search: 364/488, 364/490, 364/491, 364/489, 364/578
• US Class Current: 716/119
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A method used by a computer-aided design system for placing logic functions and cells in a floor plan of a very large scale integrated circuit chip. The structure of a set of selected logic functions and cells to be placed is compared to a set of selected logic functions and cells which have previously been placed in the floor plan. If the number of cells and the structure of the sets are analogous, the selected logic functions and cells to be placed are automatically assigned physical positions in the floor plan based on the physical position and structure of the selected logic functions and cells that have already been placed, and on an orientation mode. The orientation mode provides for the reflection of the placement of the selected logic functions and cells about the horizontal axis, the vertical axis, or both the horizontal and vertical axes. The size of the sets of selected logic functions and cells may be arbitrarily large, thereby providing advantages over simple manual placement of logic functions and cells in a floor plan.

Claims

1. In a system for designing an integrated circuit chip, the integrated circuit chip design having logic functions composed of cells, the logic functions and cells being specified in at least one logic design hierarchy structured as a graph and stored in a database, logic functions being represented as non-leaf nodes in the graph and cells being represented as leaf nodes in the graph, the graph having sub-graphs, each sub-graph having a root node representing a logic function, the logic functions and cells being assigned to physical positions in a floor plan of the integrated circuit chip, the system including an automatic placement system for accepting placement directives, and the floor plan including areas on the integrated circuit chip called placement regions, a computer-implemented method for placing logic functions and cells in a floor plan comprising the steps of:

(a) setting an orientation mode indicating an orientation of physical placement of a logic function or cell;

(b) selecting a first set of nodes in the logic design hierarchy that have been previously placed in the floor plan or previously stored in the database;

(c) selecting a second set of nodes in the logic design hierarchy for placement in the floor plan;

(d) comparing said first set of nodes to said second set of nodes, and returning to step (b) when said first set of nodes and said second set of nodes are non-analogous; and

(e) placing said second set of nodes in the floor plan, said placing step comprising the steps of

(e1) selecting a target node from said second set of nodes;

(e2) locating a node in the logic design hierarchy which is the parent of said target node;

(e3) updating the physical position of said target node in the floor plan according to said orientation mode and according to the physical position of a source node in said first set of nodes corresponding to said target node when said source node is an absolutely placed leaf node;

(e4) assigning said target node to a placement region in the floor plan and updating a placement directive for said target node when said source node is a region-placed node; and

(e5) leaving said target node unplaced when said source node is unplaced.

2. The computer-implemented method of claim 1, wherein said first set of nodes and said second set of nodes are selected from different logic design hierarchies.

3. The computer-implemented method of claim 1, wherein said comparing step (d) comprises the step of verifying that the number of nodes in said first set of nodes equals the number of nodes in said second set of nodes.

4. The computer-implemented method of claim 3 wherein said comparing step (d) further comprises the step of verifying that nodes in said first set of nodes and nodes in said second set of nodes have analogous parent-child relationships.

5. The computer-implemented method of claim 1, wherein updating step (e3) comprises the steps of:

calculating an offset for said corresponding node from the physical position of the root node of the sub-graph in the logic design hierarchy representing said first set of nodes;

reflecting said offset for said corresponding node according to said orientation mode;

calculating a physical position of said target node based on said offset and the physical position of the root node of the sub-graph in the logic design hierarchy representing said second set of nodes; and

updating said target node'"'"'s placement location and orientation.

6. The computer-implemented method of claim 5, further including the step of displaying said target node'"'"'s placement.

7. The computer-implemented method of claim 5, wherein said reflecting step includes reflecting said offset about the horizontal axis, reflecting said offset about the vertical axis, reflecting said offset about both the horizontal axis and the vertical axis, or not reflecting said offset according to said orientation mode.

8. The computer-implemented method of claim 1, wherein updating step (e4) comprises the steps of:

calculating an offset of said corresponding node from the physical position of the root node of the sub-graph in the logic design hierarchy representing said first set of nodes;

reflecting said offset according to said orientation mode;

calculating a physical position of a placement region in the floor plan for said target node from said offset and the physical position of the root node of the sub-graph in the logic design hierarchy representing said second set of nodes; and

updating said selected target node'"'"'s placement region.

9. The computer-implemented method of claim 8, wherein said reflecting step includes reflecting said offset about the horizontal axis, reflecting said offset about the vertical axis, reflecting said offset about both the horizontal axis and the vertical axis, or not reflecting said offset according to said orientation mode.

10. The computer-implemented method of claim 8, further including the step of building a data structure for storing said target node'"'"'s placement region information.

11. The computer-implemented method of claim 10, further including the step of displaying said target node'"'"'s placement region.

12. In a computer-aided design system for designing a very large scale integrated (VLSI) circuit chip, the VLSI circuit chip design having logic functions composed of cells, the logic functions and cells being specified in at least one logic design hierarchy structured as a graph and stored in a database, logic functions being represented as non-leaf nodes in the graph and cells being represented as leaf nodes in the graph, the graph having sub-graphs, each sub-graph having a root node representing a logic function, the logic functions and cells being assigned to physical positions in a floor plan of the VLSI circuit chip, the computer-aided design system including an automatic placement system for accepting placement directives, and the floor plan including areas on the VLSI circuit chip called placement regions, a computer-implemented method for placing logic functions and cells in a floor plan comprising the steps of:

(a) setting an orientation mode indicating an orientation of physical placement of a logic function or cell;

(b) selecting at least one source node in the logic design hierarchy that has been previously placed in the floor plan or previously stored in the database;

(c) selecting at least one target node in the logic design hierarchy for placement in the floor plan;

(d) building a sorted source list including said at least one source node;

(e) building a sorted target list including said at least one target node;

(f) comparing said sorted source list to said sorted target list, and returning to step (b) when said sorted source list and said sorted target list are non-analogous;

(g) deleting any pre-existing placement directives for target nodes in said sorted target list; and

(h) placing every target node of said sorted target list in the floor plan, said placing step comprising the steps of

(h1) selecting a target node from said sorted target list;

(h2) locating a node in the logic design hierarchy which is the parent of said selected target node;

(h3) updating the physical position of said selected target node in the floor plan according to said orientation mode and the physical position of a source node in said sorted source list corresponding to said selected target node when said source node is an absolutely placed leaf node;

(h4) assigning said selected target node to a placement region in the floor plan and updating the placement directive for said selected target node when said source node is a region-placed node; and

(h5) leaving said selected target node unplaced when said source node is unplaced.

13. The computer-implemented method of claim 12, wherein said at least one source node and said at least one target node are selected from different logic design hierarchies.

14. The computer-implemented method of claim 12, wherein said comparing step (f) comprises the step of verifying that the number of source nodes in said sorted source list equals the number of target nodes in said sorted target list.

15. The computer-implemented method of claim 14 wherein said comparing step (f) further comprises the step of verifying that source nodes in said sorted source list and target nodes in said sorted target list have analogous parent-child relationships.

16. The computer-implemented method of claim 12, wherein updating step (h3) comprises the steps of:

(a) calculating an offset for said corresponding source node from the physical position of the root node of the sub-graph in the logic design hierarchy representing source nodes in said sorted source list;

(b) reflecting said offset for said corresponding source node according to said orientation mode;

(c) calculating a physical position of said selected target node based on said offset and the physical position of the root node of the sub-graph in the logic design hierarchy representing target nodes in said sorted target list;

(d) updating said selected target node'"'"'s placement location and orientation; and

(e) displaying said selected target node'"'"'s placement.

17. The computer-implemented method of claim 16, wherein said reflecting step includes reflecting said offset about the horizontal axis, reflecting said offset about the vertical axis, reflecting said offset about both the horizontal axis and the vertical axis, or not reflecting said offset according to said orientation mode.

18. The computer-implemented method of claim 12, wherein updating step (h4) comprises the steps of:

(a) calculating an offset of said corresponding source node from the physical position of the root node of the sub-graph in the logic design hierarchy representing source nodes in the sorted source list;

(b) reflecting said offset according to said orientation mode;

(c) calculating a physical position of a placement region in the floor plan for said selected target node from said offset and the physical position of the root node of the sub-graph in the logic design hierarchy representing target nodes in said sorted target list;

(d) building a data structure for storing said selected target node'"'"'s placement region information;

(e) updating said selected target node'"'"'s placement region; and

(f) displaying said selected target node'"'"'s placement region.

19. The computer-implemented method of claim 18, wherein said reflecting step includes reflecting said offset about the horizontal axis, reflecting said offset about the vertical axis, reflecting said offset about both the horizontal axis and the vertical axis, or not reflecting said offset according to said orientation mode.

20. A computer system for placing logic functions and cells in a floor plan of a design for an integrated circuit chip, the integrated circuit chip design having logic functions composed of cells specified in a logic design hierarchy, the logic design hierarchy being represented as a graph structure, logic functions being represented as non-leaf nodes in the graph structure and cells being represented as leaf nodes in the graph structure, the graph structure having sub-graphs each having a root node representing a logic function, the floor plan having areas on the integrated circuit chip called placement regions, the system including an automatic placement system for accepting placement directives, and comprising:

means for setting an orientation mode, said orientation mode indicating an orientation of physical placement in the floor plan of a logic function or cell;

first selection means for selecting a first set of nodes in the logic design hierarchy that have been previously placed in the floor plan, said first set of nodes capable of including both leaf nodes and non-leaf nodes;

second selection means for selecting a second set of nodes in the logic design hierarchy for placement in the floor plan, said second set of nodes capable of including both leaf nodes and non-leaf nodes;

comparison means for comparing said first set of nodes to said second set of nodes to determine if the number of said first set of nodes is the same as the number of said second set of nodes and to determine if the graph structure of said first set of nodes is the same as the graph structure of said second set of nodes; and

placement means for placing said second set of nodes in the floor plan according to said first set of nodes and said orientation mode, and for updating placement directives for said second set of nodes.

21. The computer system of claim 20 wherein said placement means comprises:

offset calculation means for calculating offsets of said first set of nodes;

reflection metals for reflecting the physical positions of said first set of nodes according to said orientation mode;

position calculation means for calculating physical positions of said second set of nodes from said offsets and the reflected physical positions of said first set of nodes; and

updating means for updating said physical positions of said second set of nodes.

22. The computer system of claim 21, further comprising display means for displaying the placement of said selected target nodes of the integrated circuit chip design.

23. The system of claim 21, wherein said reflection means includes

means for reflecting the physical positions of said first set of nodes about the horizontal axis;

and

means for reflecting the physical positions of said first set of nodes about the vertical axis.

24. A computer system for placing logic functions and cells in a floor plan of a design for a very large scale integrated (VLSI) circuit chip based on a set of previously placed logic functions and cells, the VLSI circuit chip design having logic functions composed of cells specified in a logic design hierarchy, the logic design hierarchy being structured as a graph structure, logic functions being represented as non-leaf nodes in the graph and cells being represented as leaf nodes in the graph structure, the graph structure having sub-graphs each having a root node representing a logic function, the floor plan having areas on the VLSI circuit chip called placement regions, the system including an automatic placement system for accepting placement directives, and comprising:

means for setting an orientation mode, said orientation mode indicating an orientation of physical placement in the floor plan of a logic function or cell;

source selection means for selecting as selected source nodes at least one source node existing at any level in the logic design hierarchy that has been previously placed in the floor plan;

target selection means for selecting as selected target nodes at least one target node existing at any level in the logic design hierarchy for placement in the floor plan;

a source list comprising a list of names of said selected source nodes, pointers to said selected source nodes, and pointers to parent nodes in the logic design hierarchy of said selected source nodes;

a target list comprising a list of names of said selected target nodes, pointers to said selected target nodes, and pointers to parent nodes in the logic design hierarchy of said selected target nodes;

comparison means for comparing said source list to said target list to determine if the number of nodes in said source list is the same as the number of nodes in said target list and to determined if the graph structure of the logic design hierarchy of said selected source nodes is similar to the graph structure of the logic design hierarchy of said selected target nodes;

initialization means for initializing placement directives for said selected target nodes; and

placement means for placing said selected target nodes of said target list in the floor plan according to the placement of said selected source nodes of said source list and said orientation mode if said comparison means indicates said source list and and target list favorably compare, said placement means further for updating said placement directives of said selected target nodes.

25. The computer system of claim 24 wherein said placement means comprises:

offset calculation means for calculating offsets of said selected source nodes;

reflection means for reflecting the physical positions of said selected source nodes according to said orientation mode;

position calculation means for calculating physical positions of said selected target nodes from said offsets and the reflected physical positions of said selected source nodes;

updating means for updating said physical positions of said selected target nodes; and

display means for displaying the placement of said selected target nodes of the VLSI circuit chip design.

26. The system of claim 25, wherein said reflection means includes

means for reflecting the physical positions of said selected source nodes about the horizontal axis;

and

means for reflecting the physical positions of said selected source nodes about the vertical axis.

27. A computer-aided design system operated by a user to place logic functions and cells in a floor plan of a design for a very large scale integrated (VLSI) circuit chip based on a set of previously placed logic functions and cells, the VLSI circuit chip design having logic functions composed of cells specified in a logic design hierarchy, the logic design hierarchy being structured as a graph structure, logic functions being represented as non-leaf nodes in the graph and cells being represented as leaf nodes in the graph, the graph having-sub-graphs each having a root node representing a logic function, the floor plan having areas on the VLSI circuit chip called placement regions, the computer-aided design system including an automatic placement system for accepting placement directives, and comprising:

display means for displaying the floor plan of a design;

input means for receiving user requests;

processor means coupled to said display means and said input means far processing said user requests; and

floor planning software means operative on said processor, said floor planning software means including

means for setting an orientation mode, said orientation mode indicating an orientation of physical placement in the floor plan of a logic function or cell;

source selection means for selecting as selected source nodes at least one source node existing at any level in the logic design hierarchy that has been previously placed in the floor plan;

target selection means for selecting as selected target nodes at least one target node existing at any level in the logic design hierarchy for placement in the floor plan;

a source list comprising a list of names of said selected source nodes, pointers to said selected source nodes, and pointers to parent nodes in the logic design hierarchy of said selected source nodes;

a target list comprising a list of names of said selected target nodes, pointers to said selected target nodes, and pointers to parent nodes in the logic design hierarchy of said selected target nodes;

comparison means for comparing said source list to said target list to determine if the number and the graph structure of said selected source nodes is the same as the number and the graph structure of, respectively, said selected target nodes;

initialization means for initializing placement directives for said selected target nodes; and

placement means for placing said selected target nodes of said target list in the floor plan according to said selected source nodes of said source list and said orientation mode, and for updating said placement directives, said placement means including

offset calculation means for calculating offsets of said selected source nodes;

reflection means for reflecting the physical positions of said selected source nodes according to said orientation mode;

said reflection means including means for reflecting the physical positions of said selected source nodes about the horizontal axis; and

means for reflecting the physical positions of said selected source nodes about the vertical axis;

position calculation means for calculating physical positions of said selected target nodes from said offsets and the reflected physical positions of said selected source nodes; and

updating means for updating said physical positions of said selected target nodes for subsequent display of said selected target nodes to the user by said display means.

28. In a system for designing an integrated circuit chip, the integrated circuit chip design having logic functions composed of cells, the logic functions and cells being specified as nodes in at least one logic design hierarchy represented as a graph and stored in a database, each of the logic functions and cells being assigned a physical position and an orientation in a floor plan of the integrated circuit chip, the system including an automatic placement system for accepting placement directives, and the floor plan including areas on the integrated circuit chip called placement regions, a computer-implemented method for placing logic functions and cells in a floor plan comprising the steps of:

(a) selecting a first set of nodes in the logic design hierarchy that have been previously placed in the floor plan and previously stored in the database, each of said first set of nodes representing a logic function or a cell;

(b) selecting a second set of nodes in the logic design hierarchy for placement in the floor plan, each of said second set of nodes representing a logic function or a cell;

(c) comparing said first set of nodes to said second set of nodes, and returning to said step (b) when said first set of nodes and said second set of nodes are non-analogous; and

(d) assigning a placement to each node in said second set of nodes that is analogous to the placement of a corresponding node in said first set of nodes.

29. The computer-implemented method of claim 28, wherein said assigning step includes assigning a physical position and orientation to each of said second set of nodes according to the physical position and orientation of said corresponding node in said first set of nodes.

30. The computer-implemented method of claim 29, wherein the orientation of said second set of nodes is assigned according to a predetermined orientation mode.

31. The computer-implemented method of claim 28, wherein said assigning step includes assigning a placement region in the floor plan and updating a placement directive for each node in said second set of nodes that is a region-placed node.

32. The computer-implemented method of claim 28, wherein said assigning step includes leaving a node in said second set of nodes unplaced if said corresponding node in said first set of nodes is unplaced.

33. The computer-implemented method of claim 28, wherein said first set of nodes is selected from logic design hierarchies that are different from the logic design hierarchies from which said second set of nodes are selected.

34. The computer-implemented method of claim 28, further including the step of displaying the placement of the nodes in said second set of nodes.

35. The computer-implemented method of claim 28, wherein said comparing step comprises the step of verifying that the number of nodes in said first set of nodes equals the number of nodes in said second set of nodes.

36. The computer-implemented method of claim 35 wherein said comparing step further comprises the step of verifying that nodes in said first set of nodes and nodes in said second set of nodes have analogous hierarchical relationships.

37. The computer-implemented method of claim 28, wherein said assigning step comprises the steps of:

designating as the first root node the node in said first set of nodes which is a root node in the graph representing the logic design hierarchy for said first set of nodes;

designating as the second root node the node in said second set of nodes which is a root node in the graph representing the logic design hierarchy for said second set of nodes;

calculating an offset for said second root node from the physical position of said first root node;

calculating the physical position for each of said nodes in said second set of nodes based on said offset and the physical position of said second root node; and

updating the placement location and orientation for each of said nodes in said second set of nodes based on said calculating step.

38. The computer-implemented method of claim 37, wherein the assigning step further includes the step of reflecting said offset for said second root node according to a predetermined orientation mode.

39. The computer-implemented method of claim 38, wherein said reflecting step includes reflecting said offset about the horizontal axis, reflecting said offset about the vertical axis, reflecting said offset about both the horizontal axis and the vertical axis, or not reflecting said offset according to said orientation mode.