Simultaneous placement and wiring for VLSI chips
First Claim
1. A computerized integral method for automatically placing components of a logic network and determining the wiring connections of a wiring network to them on a master-slice 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 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; and
repeating said dividing and partitioning steps (a) and (b) for each of said cells and assigned component subsets forming subsets of cells with assigned component subsets on successive levels, until an elementary cell resolution is obtained;
wherein the improvement comprises including after each iteration of executing said steps (a) and (b) the additional steps of;
(c) performing a placeability analysis to determine whether all components of a component subset can be placed in the assigned cell subset;
(d) determining which subnetworks of said wiring 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.
1 Assignment
0 Petitions
Accused Products
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 of decreasing size, the set of components is partitioned into subsets 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.
197 Citations
16 Claims
-
1. A computerized integral method for automatically placing components of a logic network and determining the wiring connections of a wiring network to them on a master-slice 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 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; and repeating said dividing and partitioning steps (a) and (b) for each of said cells and assigned component subsets forming subsets of cells with assigned component subsets on successive levels, until an elementary cell resolution is obtained; wherein the improvement comprises including after each iteration of executing said steps (a) and (b) the additional steps of; (c) performing a placeability analysis to determine whether all components of a component subset can be placed in the assigned cell subset; (d) determining which subnetworks of said wiring 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A computerized system for automatically placing components of a logic network on a master-slice VLSI chip and integrally globally determining the wiring connections of a wiring network to said components, comprising:
-
means for determining the number of elementary cell rows and columns available on the area of said chip and the available wiring tracks per said rows and columns; assignment means for determining the set of components of said logic network to be placed and respectively assigning subsets thereof successively to a hierarchy of sets of said elementary cells; analysis means for performing a placeability analysis to determine whether all components of each said subset can be placed in the respective assigned cell set; wiring connection means for globally determining the wiring connections for subnetworks of said wiring network to the components within said subsets and over the wiring tracks between said subsets for each of said hierarchical sets of cells; and partitioning means for iteratively actuating said assignment means, said analysis means and said wiring connection means beginning with two sets of elementary cells and continuing by successively subdividing said sets of elementary cells through successive levels until the number of said cell sets equals said number of elementary cells, whereupon the component placement and global wiring are complete. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
Specification