US4908772A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Integrated circuits with component placement by rectilinear partitioning
Assignee: AT&T Inc
•
Filing: 1987-03-30
•
Granted: 1990-03-13
•
Expires: 2007-03-30
Abstract
Abstract An integrated circuit, and a method for laying out and creating the integrated circuit, which contains large circuit blocks placed at any desired location on a chip, with the rest of the circuitry placed in the remaining non-rectangular area on the chip. The layout takes account of connections from within the circuit area to connection points external to the area. The procedure for the automatic layout proceeds in two steps. The first step is global partitioning and placement, and the second is detailed placement. The global partitioning performs the logical partitioning of the cells into clusters to be placed among and between the macro cells and the external terminals, with each cluster being eventually laid-out in a rectangular area. The second step involves the detailed placement of cells within the rectangular areas. Partitioning is accomplished by an iterative process, where at each iterative step the non-rectangular area is divided into two parts of approximately equal size. The circuitry to be placed in each of the divided areas is then partitioned in proportion to the size of the areas in accordance with known techniques, coupled with a novel terminal reassignment procedure.
Inventors
- 👤 Mely C. Chi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 21:43
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
186 words
An integrated circuit having a predetermined area for placing components (FIG. 3 101, 102) and further having input/output terminals (FIG. 3 104), macro cells situated in said area (FIG. 3 103), and a plurality of interconnected integrated circuit cells situated in said area and connected to said macro cells and to said input/output terminals, where said integrated circuit is made in accordance with a process COMPRISING: a step of situating said macro cells on said area without regard to edges of said area; a step of iteratively, partitioning that portion of said area that is left after said situating of said macro cells, to develop a plurality of rectangular areas; a step of assigning said input/output terminals to specific ones of said plurality of rectangular areas; a step of allocating portions of said plurality of interconnected integrated circuit cells to each of said rectangular areas in proportion to the size of said rectangular areas, and accounting for said situating of said macro cells and said assigning of said input/output terminals; and a step of situating allocated portions of said integrated circuit cells in said rectangular areas.
Claim 2
Dependent Claim
186 words
An integrated circuit having a predetermined area for placing components (FIG. 3 101, 102) and further having input/output terminals (FIG. 3 104), macro cells situated in said area (FIG. 3 103), and a plurality of interconnected integrated circuit cells situated in said area and connected to said macro cells and to said input/output terminals, where said integrated circuit is made in accordance with a process COMPRISING: a step of situating said macro cells on said area without regard to edges of said area; a step of iteratively, partitioning that portion of said area that is left after said situating of said macro cells, to develop a plurality of rectangular areas; a step of assigning said input/output terminals to specific ones of said plurality of rectangular areas; a step of allocating portions of said plurality of interconnected integrated circuit cells to each of said rectangular areas in proportion to the size of said rectangular areas, and accounting for said situating of said macro cells and said assigning of said input/output terminals; and a step of situating allocated portions of said integrated circuit cells in said rectangular areas.
Claim 3
Independent Claim
149 words
A method for laying out integrated circuits comprising input ports, output ports, macro cells requiring rectilinear integrated circuit layout areas, and a plurality of integrated circuit cells within a predetermined area and in accordance with a procedure comprising the steps of: placing said macro cells at chosen locations of said area without regard to the circumference of said area, thereby leaving a rectilinear area for laying out said plurality of integrated circuit cells; successively dividing said rectilinear area of said integrated circuit cells into rectangular areas; propagating connections from said input ports and said output ports to said rectangular areas; successively partitioning said plurality of integrated circuit cells into sets assigned to said rectangular areas that account for the relative areas of said rectangular areas and for said step of propagating connections; and placing said integrated circuit cells assigned to each of said rectangular areas on said assigned areas.
Claim 4
Independent Claim
149 words
A method for laying out integrated circuits comprising input ports, output ports, macro cells requiring rectilinear integrated circuit layout areas, and a plurality of integrated circuit cells within a predetermined area and in accordance with a procedure comprising the steps of: placing said macro cells at chosen locations of said area without regard to the circumference of said area, thereby leaving a rectilinear area for laying out said plurality of integrated circuit cells; successively dividing said rectilinear area of said integrated circuit cells into rectangular areas; propagating connections from said input ports and said output ports to said rectangular areas; successively partitioning said plurality of integrated circuit cells into sets assigned to said rectangular areas that account for the relative areas of said rectangular areas and for said step of propagating connections; and placing said integrated circuit cells assigned to each of said rectangular areas on said assigned areas.
Claim 5
Independent Claim
190 words
A method for laying out integrated circuits comprising input ports, output ports, macro cells requiring rectilinear integrated circuit layout areas, and a plurality of integrated circuit cells within a predetermined area and in accordance with a procedure comprising the steps of: placing said macro cells at chosen locations of said area without regard to the circumference of said area, thereby leaving a rectilinear area for laying out said plurality of integrated circuit cells; dividing said rectilinear area of said integrated circuit cells into subareas with a cut line engulfing at least one vertex of said rectilinear area for laying out said integrated circuit cells; propagating connections from said input ports and said output ports to edges of said subareas; partitioning said plurality of integrated circuit cells into sets, equal in number to the number of said subareas and assigned to said subareas, with said partitioning accounting for the relative size of said subareas and for said step of propagating connections; repeating said steps of dividing, propagating, and partitioning until all subareas are rectangular; and placing said integrated circuit cells assigned to each of said rectangular subareas on said assigned subareas.
Claim 6
Independent Claim
190 words
A method for laying out integrated circuits comprising input ports, output ports, macro cells requiring rectilinear integrated circuit layout areas, and a plurality of integrated circuit cells within a predetermined area and in accordance with a procedure comprising the steps of: placing said macro cells at chosen locations of said area without regard to the circumference of said area, thereby leaving a rectilinear area for laying out said plurality of integrated circuit cells; dividing said rectilinear area of said integrated circuit cells into subareas with a cut line engulfing at least one vertex of said rectilinear area for laying out said integrated circuit cells; propagating connections from said input ports and said output ports to edges of said subareas; partitioning said plurality of integrated circuit cells into sets, equal in number to the number of said subareas and assigned to said subareas, with said partitioning accounting for the relative size of said subareas and for said step of propagating connections; repeating said steps of dividing, propagating, and partitioning until all subareas are rectangular; and placing said integrated circuit cells assigned to each of said rectangular subareas on said assigned subareas.
Claim 7
Dependent Claim
78 words
The method of claim 3, further including a step interposed following said step of propagating connections, of reassigning terminal connections from an edge of a first subarea to an edge of second subarea when said step of propagating connections propagates terminals to said edge of said first subarea, and said edge is too close to another, parallel, edge of said first subarea to support the placement of integrated circuit cells between said edge and said other, parallel, edge.
Claim 8
Dependent Claim
26 words
The method of claim 3, wherein said cut line is consistently taken in a preselected direction parallel to one edge of said integrated circuit layout area.
References Cited (Backward Citations)
US3617714A
Cited
US4554625A
Cited
US4593363A
Cited
US4577276A
Cited
US4630219A
Cited
US4700317A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-03-12 | 1993-09-11 | 1994-03-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-03-12 | 1997-09-11 | 1998-03-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-03-12 | 2001-09-11 | 2002-03-13 | $7700.00 | Window Closed / Lapsed |