Constraint programming based method for bus-aware macro-block pin placement in a hierarchical integrated circuit layout

• US 8,234,615 B2
• Filed: 08/04/2010
• Issued: 07/31/2012
• Est. Priority Date: 08/04/2010
• Status: Active Grant

• Current Assignee: Globalfoundries US Incorporated (GlobalFoundries, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Ramji, Shyam, Dubrov, Bella, Freund, Ari, Mark, Edward F., Schell, Timothy A., Eran, Haggai
• Primary Examiner(s): Kik, Phallaka
• Application Number:
  US12/849,973
• Publication Number:
  US 20120036491A1
• Time in Patent Office: 727 Days
• Field of Search: 716/122, 716/123, 716/124, 716/129, 716/130, 716/131, 716/132, 703/16
• US Class Current: 716/129
• CPC Class Codes: G06F 2111/04 Constraint-based CAD
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

Assigning pins to macro-blocks of an Integrated Circuit (IC) chip is described. The macro-block pin assignments are automatically placed using Constraint Programming (CP) techniques to position the pins on the periphery of a macro-block. Bus-ordering and pin-spacing constraints are performed considering all the nets forming the IC design simultaneously. The CP formulation includes modeling detailed and discrete constraints required to achieve an optimal pin-assignment. A stochastic CSP solver is used to define the cost function on search points giving full assignments to all the variables. The macro-block pins are ultimately moved to computed locations.

Claims

1. A bus-interconnectivity aware method for assigning macro-block pins in a hierarchical integrated circuit (IC) chip floorplan comprising:

a) using a computer, accessing information related to the chip floorplan of said IC chip;

b) grouping macro-block pins into buses based on connectivity;

c) formulating a constraint programming (CP) model for macro-block pin-assignment corresponding to said chip floorplan, and optimizing said formulation by solving said CP model;

d) minimizing length of interconnects linking said macro-blocks;

e) using a computer, placing said macro-block pins at a periphery of selected macro-blocks maintaining bus-ordering and pin-spacing constraints of all nets forming said chip floorplan; and

f) reducing wire crossing by computing said macro-pins relative order within each bus-pin group.

2. The method as recited in claim 1, wherein in step e) said placing said macro-block pins at the periphery of selected macro-blocks is performed on all the nets of said IC chip design concurrently.

3. The method recited in claim 1 wherein said CP formulation comprises modeling discrete constraints required to achieve a realizable pin-assignment.

4. The method recited in claim 1, further comprising using a Constraints Satisfaction Program (CSP) solver by defining a cost function on search points giving full assignments to all variables.

5. The method recited in claim 4, wherein said CSP uses a stochastic process.

6. The method as recited in claim 4 further comprising defining said CP formulation for said pin assignment and solving predetermined constraint satisfaction criteria (CSP).

7. The method recited in claim 4 wherein said cost of a point corresponds to a measure of how far said point is from feasibility.

8. The method recited in claim 4 wherein said cost of a point is a sum of individual costs attached by said constraints.

9. The method as recited in claim 4, wherein following said invocation of said CSP, placing all the pins is obtained by ordering the pins of each bus in a region allotted to said bus.

10. The method as recited in claim 9, wherein said ordering of the pins within a bus enables the pins forming said buses to be grouped together in accordance to their relative same ordering and according to their respective clockwise or counter-clockwise orientation.

11. The method as recited in claim 9, wherein for each bus ordering the pins is performed either clockwise or counterclockwise depending on relative positions of macro-block instance and depending on whether they are mirrored or rotated, different orientations are used for different buses.

12. The method as recited in claim 11, wherein said orientations for each bus are heuristically tested independently and selected based on buses yielding a lower cost.

13. The method as recited in claim 11, wherein random orientations are initially performed, followed by iterating through said buses in a random order, and wherein each bus is inverted when its orientation is found to lower said cost.

14. The method recited in claim 1 wherein said CP includes problems having natural formulations in terms of known constraints.

15. The method recited in claim 1, wherein constraints are added or removed.

16. The method as recited in claim 1, wherein said formulation of CP for said pins further comprises:

i) variables representing macro-block pins;

ii) variable domains comprising un-blocked macro-block periphery;

iii) constraints including non-overlapping macro-pins and minimum pin-to-pin spacing; and

iv) objective functions comprising half-perimeter wire length summed over all the nets.

17. The method as recited in claim 1, further comprising computing violation costs of non-overlap constraint of a macro-block instance, comprising:

i.) splitting buses wrapping through a macro-block origin;

ii.) sorting together starting and ending points of all said buses, keeping for each point its identity as a starting point or ending point; and

iii.) iterating through the sorted points keeping track of a total number of starting points encountered and the number of ending points encountered.

18. The method as recited in claim 17, wherein said buses formed by sets of pins grouped together have constituent pins of each bus placed contiguously within a space allotted thereto, enabling each bus thus positioned to be modeled as a single Constraint Satisfaction Criteria (CSP) variable.

19. The method as recited in claim 1, further comprising performing said pin-assignment per macro-block and not per instance, wherein all copies of a macro-block share same relative placement of pins.

20. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps of providing a bus-interconnectivity aware method for assigning macro-block pins in a hierarchical integrated circuit (IC) chip floorplan, the method steps comprising:

a) using a computer, accessing information related to the chip floorplan;

b) grouping macro-block pins into buses based on connectivity;

c) formulating a constraint programming (CP) model for macro-block pin-assignment corresponding to said chip floorplan, and optimizing said formulation by solving said CP model;

d) minimizing length of interconnects linking said macro-blocks;

e) using a computer, placing said macro-block pins at a periphery of selected macro-blocks maintaining bus-ordering and pin-spacing constraints of all nets forming said chip floorplan; and

f) reducing wire crossing by computing said macro-pins relative order within each bus-pin group.