US4577276A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Placement of components on circuit substrates
Assignee: Nokia Bell Labs
•
Filing: 1983-09-12
•
Granted: 1986-03-18
•
Expires: 2003-09-12
Abstract
Abstract In laying out integrated circuits on a substrate, the placement of the components relative to each other is important in minimizing conductor area and hence chip area. Large scale integration often uses polycells which are lined up in rows to realize the digital logic circuitry. A partitioning procedure is disclosed which iteratively separates the cells into maximally connected subcells, eventually to assign them to rows so as to minimize conductor area. A technique called terminal propagation takes into account at every iteration the location of connections outside of the partitioned area. Rectilinear Steiner trees are generated to aid in terminal propagation.
Inventors
- 👤 Alfred E. Dunlop
- 👤 Brian W. Kernighan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 18:04
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
124 words
An integrated circuit fabricated in accordance with a design procedure comprising the steps of (a) determining a plurality of modules of integrated circuit components from which said integrated circuit can be fabricated, (b) successively partitioning said plurality of modules into successively smaller subsets of modules maximally connected within subsets and minimally connected between subsets in accordance with a known partitioning algorithm, (c) successively dividing the area of a substrate into subareas proportional to the areas of the polycells in said subsets, (d) placing said modules on said substrate in accordance with the subarea location to which said modules are assigned, and (e) propagating connections to terminal external to each of said subareas to the periphery of the respective subareas prior to said partitioning step.
Claim 2
Dependent Claim
124 words
An integrated circuit fabricated in accordance with a design procedure comprising the steps of (a) determining a plurality of modules of integrated circuit components from which said integrated circuit can be fabricated, (b) successively partitioning said plurality of modules into successively smaller subsets of modules maximally connected within subsets and minimally connected between subsets in accordance with a known partitioning algorithm, (c) successively dividing the area of a substrate into subareas proportional to the areas of the polycells in said subsets, (d) placing said modules on said substrate in accordance with the subarea location to which said modules are assigned, and (e) propagating connections to terminal external to each of said subareas to the periphery of the respective subareas prior to said partitioning step.
Claim 3
Dependent Claim
55 words
The integrated circuit of claim 1 further fabricated in accordance with a design procedure including the step of (f) computing a rectilinear Steiner tree on all of said terminals external to said subareas, and (g) using the intersections of said Steiner tree with the periphery of said subarea as the projection of said external terminal.
Claim 4
Dependent Claim
32 words
The integrated circuit of claim 2 further fabricated in accordance with a design procedure including the step of (h) ignoring all of said intersections centrally located on the boundary between said subareas.
Claim 5
Independent Claim
127 words
The method of designing integrated circuits comprising the steps of (a) determining a plurality of modules of integrated circuit components from which said integrated circuit can be fabricated, (b) successively partitioning said plurality of modules into successively smaller subareas of modules maximally connected within subsets and minimally connected between subsets in accordance with a known partitioning algorithm, (c) successively dividing the area of a substrate with subareas proportional to the areas of said modules in said subsets, (d) assigning said modules to locations on the integrated circuit substrate in accordance with the locations of said subareas to which the respective modules are assigned, and (e) propagating connections from elements external to each of said subareas to the periphery of the respective subarea prior to said partitioning steps.
Claim 6
Independent Claim
127 words
The method of designing integrated circuits comprising the steps of (a) determining a plurality of modules of integrated circuit components from which said integrated circuit can be fabricated, (b) successively partitioning said plurality of modules into successively smaller subareas of modules maximally connected within subsets and minimally connected between subsets in accordance with a known partitioning algorithm, (c) successively dividing the area of a substrate with subareas proportional to the areas of said modules in said subsets, (d) assigning said modules to locations on the integrated circuit substrate in accordance with the locations of said subareas to which the respective modules are assigned, and (e) propagating connections from elements external to each of said subareas to the periphery of the respective subarea prior to said partitioning steps.
Claim 7
Dependent Claim
52 words
The method of designing integrated circuits according to claim 4 further including the steps of (f) computing a rectilinear Steiner tree on all of said connections external to said subareas, and (g) using the intersections of said Steiner tree with the periphery of said subareas as the projection of said external connection.
Claim 8
Dependent Claim
29 words
The method of designing integrated circuits according to claim 5 further including the steps of (h) ignoring all of said intersections centrally located on the boundary between said subareas.
Claim 9
Dependent Claim
141 words
An integrated circuit fabricated in accordance with a design procedure comprising the step of (a) determining a plurality of polycells of integrated circuit components from which said integrated circuit can be fabricated, (b) successively partitioning said plurality of polycells into successively smaller subareas of polycells maximally connected between subsets in accordance with a known partitioning algorithm, (c) successively dividing the area of a substrate with subareas proportional to the area of said polycells in said subsets, (d) dividing said substrate into horizontal or vertical areas corresponding in number to the desired number of rows of said polycells, (e) assigning said polycells to rows in accordance with the proportion of said subareas falling into the corresponding horizontal area and, (f) propagating connections from elements external to each of said subareas to the periphery of the respective subarea prior to said partitioning step.
Claim 10
Dependent Claim
141 words
An integrated circuit fabricated in accordance with a design procedure comprising the step of (a) determining a plurality of polycells of integrated circuit components from which said integrated circuit can be fabricated, (b) successively partitioning said plurality of polycells into successively smaller subareas of polycells maximally connected between subsets in accordance with a known partitioning algorithm, (c) successively dividing the area of a substrate with subareas proportional to the area of said polycells in said subsets, (d) dividing said substrate into horizontal or vertical areas corresponding in number to the desired number of rows of said polycells, (e) assigning said polycells to rows in accordance with the proportion of said subareas falling into the corresponding horizontal area and, (f) propagating connections from elements external to each of said subareas to the periphery of the respective subarea prior to said partitioning step.
Claim 11
Dependent Claim
52 words
The method of designing integrated circuits according to claim 7 further including the steps of (g) computing a rectilinear Steiner tree on all of said connections external to said subareas, and (h) using the intersections of said Steiner tree with the periphery of said subarea as the projection of said external connection.
Claim 12
Dependent Claim
29 words
The method of designing integrated circuits according to claim 8 further including the step of (i) ignoring all of said intersections centrally located on the boundary between said subareas.
References Cited (Backward Citations)
US3617714A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1989-03-17 | 1989-09-16 | 1990-03-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1993-03-17 | 1993-09-16 | 1994-03-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1997-03-17 | 1997-09-16 | 1998-03-18 | $7700.00 | Window Closed / Lapsed |