EP0133466A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Simultaneous placement and wiring for VLSI chips
Assignee: International Business Machines Corp
•
Filing: 1984-06-28
•
Granted: —
•
Expires: 2004-06-28
Abstract
Abstract For designing the layout of a master-slice VLSI chip steps for placing components and for determining the wiring pattern interconnecting them are alternated in an iterative process. The chip area is partitioned into subareas (G-, G<sup>+</sup>) of decreasing size, the set of components is partitioned into subsets (X', X") which fit to the respective subareas, and after each partitioning step the global wiring is determined for the existing subnets of the whole network. Due to this interrelation of placement and wiring procedures, advantages with respect to total wire length, overflow number of wires, and processing time can be gained.
Inventors
- 👤 Michael Burstein
- 👤 Se June Hong
- 👤 Richard Neil Pelavin
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-28 13:02
CPC Classifications
H; H10; H10D; H10D84/00; H10D84/90; G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
196 words
Method of placing components of a logic network and determining wiring connections between them on a VLSI chip, comprising the steps of - (a) dividing the chip area into first and second portions constituting a first and a second cell, and - (b) partitioning the logic network into first and and second portions comprising, respectively, a first and a second subset of the components of the logic network, and assigning each of the component subsets to one of the cells; said dividing and partitioning steps (a) and (b) being repeated for each of said cells and assigned component subsets until an elementary cell resolution is obtained; characterized by including after each iteration executing said steps (a) and (b) the additional steps of - (c) performing a placeability analysis to deter-. mine whether all components of a subset can be placed in the assigned cell, - (d) determining which subnetworks of the logic network cross newly generated cell boundaries, - (e) determining for each subnetwork the global wiring for the subset of cells through which the subnetwork passes, so that after the final iteration step leading to elementary cell resolution component placement and global wiring are complete.
Claim 2
Dependent Claim
196 words
Method of placing components of a logic network and determining wiring connections between them on a VLSI chip, comprising the steps of - (a) dividing the chip area into first and second portions constituting a first and a second cell, and - (b) partitioning the logic network into first and and second portions comprising, respectively, a first and a second subset of the components of the logic network, and assigning each of the component subsets to one of the cells; said dividing and partitioning steps (a) and (b) being repeated for each of said cells and assigned component subsets until an elementary cell resolution is obtained; characterized by including after each iteration executing said steps (a) and (b) the additional steps of - (c) performing a placeability analysis to deter-. mine whether all components of a subset can be placed in the assigned cell, - (d) determining which subnetworks of the logic network cross newly generated cell boundaries, - (e) determining for each subnetwork the global wiring for the subset of cells through which the subnetwork passes, so that after the final iteration step leading to elementary cell resolution component placement and global wiring are complete.
Claim 3
Dependent Claim
66 words
Method in accordance with claim 1, characterized in that said placeability analysis is based on a shape function sh(x) for each of the components or circuits x to be placed, said shape function defining for each component or circuit x the rectangular area consisting of a single elementary cell or of a plurality of elementary cells, that is required for accomodating the respective component or circuit.
Claim 4
Dependent Claim
57 words
Method in accordance with claim 2, characterized in that the placeability analysis is further based on legal position data LP(x) for each of the components or circuits x to be placed, said legal position data defining the set of elementary cells on which the respective component or circuit, or a given portion of it, can be placed.
Claim 5
Dependent Claim
63 words
Method in accordance with claim 1, characterized in that for executing said global wiring step (e) for each subnetwork, the subset of cells through which the respective subnetwork passes is subdivided into rectangular cell groups which are two cells wide, and that a partial wiring procedure is executed for each such cell group to obtain the global wiring on the respective partitioning level.
Claim 6
Dependent Claim
61 words
Method in accordance with claim 4, characterized in that for obtaining the global wiring for a cell group consisting of a 2 x n cell array, the wiring is first determined for a single cell pair, then extended to include a further coll pair in each of a plurality of steps, until all cell pairs of the cell group are included.
Claim 7
Dependent Claim
53 words
Method in accordance with claim 1, characterized in that the initial data for the placement and wiring procedures comprise a net list including the set X of components or circuits to be placed and the set E of subnetworks to be formed, defining for each subnetwork the components or circuits assigned to it.
Claim 8
Dependent Claim
95 words
Method in accordance with claim 6, characterized in that said initial data further comprise placement data including, for each component or circuit x to be placed, a shape function sh(x) defining how many elementary cells in a rectangular array are required for placing the component; a list LP(x) of the set of elementary cells which can serve as a legal position for the respective component; and two values BLhx and BLvx indicating the numbers of horizontal and vertical wiring tracks which will be blocked in an assigned cell due to internal wiring of the component.
Claim 9
Dependent Claim
49 words
Method in accordance with claim 6 or 7, characterized in that said initial data further comprise as substrate data the numbers p and q of elementary cells in horizontal and vertical direction, and the numbers h(i) and v(j) of available wiring tracks for each cell row and cell column.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.