HIERARCHICAL ANALOG IC PLACEMENT SUBJECT TO SYMMETRY, MATCHING AND PROXIMITY CONSTRAINTS

• US 20090235219A1
• Filed: 05/26/2009
• Published: 09/17/2009
• Est. Priority Date: 10/31/2007
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Springsoft USA Incorporated (Synopsys Incorporated)
• Inventors: LIN, Po-Hung, CHAO, Wei-Chung, LIN, Shyh-Chang
• Granted Patent: US 7,873,928 B2
• Time in Patent Office: Days
• US Class Current: 716/119
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A placement tool generates an optimal placement for a plurality of device modules within an analog integrated circuit (IC) subject to device matching, symmetry, and proximity constraints by first defining a multiple-level hierarchy of constraint groups, wherein each constraint group consists of elements that are subject to one of the placement constraints. Each element of each constraint group consists of either of one of the device modules or another one of the constraint groups residing at a lower level of the hierarchy. The tool then generates a hierarchical B*-tree representation of a trial placement for the IC including a separate node representing each constraint group of the hierarchy and a separate node for each of device module not included in any of the constraint groups. Each node representing a constraint group defines relative positions within the IC of each the device modules or lower level constraint groups forming the constraint group that are consistent with the placement constraint on the constraint group. The placement tool iteratively perturbs the hierarchical B*-tree to generate a sequence of trial placements for the IC design and then evaluates a cost function for each trial placement to select a best one of the trial placements as the optimal trial placement.

Claims

1. Computer-readable media containing instructions, which when read and executed by a computer, causes the computer to execute a method for selecting a placement for device modules that are to form an integrated circuit (IC) described by an IC design, wherein the selected placement satisfies a set of placement constraints, wherein the method comprises the steps of:

a. processing the IC design to define a multiple-level hierarchy of groups, wherein each group consists of elements that are subject to one of the placement constraints, and wherein each element of each group at each level of the hierarchy consists of either one of the device modules or another one of the groups residing at a lower level of the hierarchy;

b. generating a hierarchal representation of a trial placement for the IC comprising a separate group representation for each group of the hierarchy and a separate device representation for each of the device modules not included in any of the groups, wherein each group representation defines relative positions within the IC of the elements of the group that are consistent with the placement constraint on the elements of the group and each device representation defines a relative position of the device module it represents,

c. iteratively perturbing the hierarchical representation to generate a sequence of hierarchical representations of trial placements for the IC design;

d. separately evaluating a cost function for each trial placement that is a measure of placement quality, and

e. based on cost function evaluations carried out at step d, selecting a best one of the trial placements generated at step c as the selected placement.

2. The computer-readable media in accordance with claim 1

wherein the hierarchical representation of a trial placement for the IC generated at step b is a first HB*-tree comprising a plurality of nodes representing separate ones of the devices modules and groups.

3. The computer-readable media in accordance with claim 2

wherein one of the placement constraints is a symmetry constraint, and

wherein a node of the first HB*-tree comprises an automatically symmetric-feasible B*-tree (ASF-B*-tree) representation of a placement for a set of the device modules forming a symmetry group that is subject to the symmetry constraint.

4. The method in accordance with claim 3

wherein the ASF-B*-tree defines a symmetry island placement for all of the device modules forming the symmetry group in which each device module of the symmetry group abuts at least one other device module of the symmetry group such that all device modules of the symmetry group form a connected placement.

5. The computer-readable media in accordance with claim 4

wherein the symmetry island placement defined by an ASF-B*-tree representing the symmetry group about an axis of symmetry, and

wherein the ASF-B*-tree represents positions of device modules of the symmetry group residing on only one side of the axis of symmetry.

6. The computer-readable media in accordance with claim 5 wherein at least one perturbation of the hierarchal representation carried out at step c comprises altering the ASF-B*-tree to one of rotating a device module, repositioning a device module, and swapping positions of two device modules within the trial placement defined by the ASF-B*-tree.

7. The computer-readable media in accordance with claim 4 wherein at least one perturbation of the hierarchal representation carried out at step c comprises altering the ASF-B*-tree to alter a type of the symmetry of the symmetry island it defines from any one of vertical, horizontal, and two-dimensional symmetry to any other one of vertical, horizontal and two-dimensional symmetry.

8. The computer-readable media in accordance with claim 2 wherein at least one perturbation of the hierarchal representation carried out at step c comprises altering the HB*-tree to one of rotating a device module, repositioning a device module, and swapping positions of two device modules within the trial placement defined by the HB*-tree.

9. The computer-readable media in accordance with claim 2,

wherein the HB*-tree comprises nodes representing device modules and nodes representing symmetry island edges.

10. The computer-readable media in accordance with claim 2

wherein one of the placement constraints is a hierarchical proximity constraint,

wherein a node of the first HB*-tree comprises a second HB*-tree representation of a placement for a set of the device modules that are subject to the hierarchal proximity constraint.

11. The computer-readable media in accordance with claim 10 wherein step c comprises hierarchically packing the second HB*tree.

12. The computer-readable media in accordance with claim 2

wherein one of the placement constraints is a matching constraint and

wherein a node of the first HB*-tree comprises a representation of a placement for a set of the device modules that are subject to the matching constraint.

13. The computer-readable media in accordance with claim 3

wherein at least one of the placement constraints is a hierarchical symmetry constraint,

wherein at least one node of the first ASF-B*-tree comprises a second ASF-B*-tree representation of a placement for a set of the device modules that are subject to the hierarchal symmetry constraint.

14. The computer-readable media in accordance with claim 13 wherein step c comprises hierarchically packing the second ASF-B*tree.

15. The computer-readable media in accordance with claim 3

wherein one of the placement constraints is a matching constraint and

wherein a node of the first ASF-B*-tree comprises a representation of a placement for a set of the device modules that are subject to the matching constraint.