Structured design method for high density standard cell and macrocell layout of VLSI chips
First Claim
1. A method for laying out an assemblage of intermixed fixed size and shape rectangular macrocells and amorphous clusters of standard cell logic elements in a target region, comprising the steps of:
- performing a first affinity factor evaluation of first affinity factors of all possible pairs of logic elements;
generating low-order standard cell subdomains consisting of logic element pairs having the most positive first affinity factors;
performing a second affinity factor evaluation of the affinity factors of all possible pair combinations of standard cell subdomains and logic elements;
generating higher-order standard cell subdomains, consisting of pairings of one of (a) standard cell subdomains with other standard cell subdomains, (b) standard cell subdomains with logic elements, and (c) logic elements with other logic elements, which pairings include only sets having identical second affinity factors;
iteratively repeating said performing a second affinity factor evaluation and generating higher-order steps to generate standard cell domains until combining any pair results in a second affinity factor more negative than zero;
performing a third affinity factor evaluation of the affinity factors of all possible pairs of macrocells and standard cell domains;
pairing those of said macrocells and standard cell domains having the most positive value of said third affinity factor to form superdomains;
3 Assignments
0 Petitions
Accused Products
Abstract
A chip layout system lays out chips including adjustable-shaped domains of standard cells and fixed-size macrocells. The system orders those standard cells which have interconnections into binary pairs or groupings of two. The binary pairs are grouped in higher and higher order groupings based upon evaluations of the area of the grouping and the sum of the lengths of the interconnections. All possible permutations of placement configuration including some rotations of various elements are further evaluated and the final placement is established on the basis of a minimum area, minimum interconnect length criterion. During the processing, the aspect ratios of the various domains and grouping of domains are adjusted to optimize their placement on the chip surface.
186 Citations
21 Claims
-
1. A method for laying out an assemblage of intermixed fixed size and shape rectangular macrocells and amorphous clusters of standard cell logic elements in a target region, comprising the steps of:
-
performing a first affinity factor evaluation of first affinity factors of all possible pairs of logic elements; generating low-order standard cell subdomains consisting of logic element pairs having the most positive first affinity factors; performing a second affinity factor evaluation of the affinity factors of all possible pair combinations of standard cell subdomains and logic elements; generating higher-order standard cell subdomains, consisting of pairings of one of (a) standard cell subdomains with other standard cell subdomains, (b) standard cell subdomains with logic elements, and (c) logic elements with other logic elements, which pairings include only sets having identical second affinity factors; iteratively repeating said performing a second affinity factor evaluation and generating higher-order steps to generate standard cell domains until combining any pair results in a second affinity factor more negative than zero; performing a third affinity factor evaluation of the affinity factors of all possible pairs of macrocells and standard cell domains; pairing those of said macrocells and standard cell domains having the most positive value of said third affinity factor to form superdomains; - View Dependent Claims (3, 9, 20, 21)
-
-
2. performing a fourth affinity factor evaluation of the affinity factors of all possible pairs of superdomains, standard cell domains and macrocells;
-
forming higher-order superdomains by pairing those of said remaining superdomains, standard cell domains and macrocells having the most positive values of said fourth affinity factor; iteratively repeating said forming and performing a fourth affinity evaluation steps until only one superdomain remains to form a binary tree structure having plural subtrees of different levels, each subtree including a root node and plural leaf nodes remote from said root node. - View Dependent Claims (8, 13, 15, 17, 18, 19)
-
- 4. tagging as B root superdomains those superdomains at the root of each of said B subtrees;
-
5. identifying as A subtrees those subtrees in said binary tree structure in which the number of said B root superdomains is less than a second predetermined number;
tagging as A root superdomains those superdomains at the root of each of said A subtrees;
-
6. iteratively repeating said steps of identifying those A subtrees and tagging as A root superdomains to form subtrees of successively higher level until the entirety of said binary tree has been classified and only a single superdomain remains, whereby the root of each subtree becomes a leaf of the next higher level subtree;
beginning with the A subtree of highest level and proceeding in descending order level, successively forming all permutations, within said target area, of right-left, top-bottom configurations of those superdomains which form the leaves of said A subtree of highest order of said binary tree structure, while retaining a rectangular superdomain form with an aspect ratio selected to accept any macrocells contained therein; - View Dependent Claims (14)
-
7. for each subtree for which all right-left, top-bottom permutations are formed, evaluating the sum of the lengths of the connections between the interconnected superdomains of each permutation, and selecting for further evaluation that one permutation for which a quality criterion is optimized, said quality criterion including the consideration that said sum of the lengths of the connections should be minimized;
-
iteratively repeating said successively forming all permutations and evaluating the sum of the lengths of the connections steps for all A subtrees until all A subtrees have been processed and only B subtrees remain; forming all possible permutations of each B subtree, and for each of said possible permutation of each B subtree, forming all possible domain right-left, top-bottom topological permutations, and for each of said topological permutations, calculating a quality criterion including at least one of (a) minimum area, (b) aspect ratio match, and (c) minimum the sum of the lengths of the connections between the interconnected domains; and selecting, from all of said possible permutations of each of said B subtrees and from all of said topological permutations of said B subtrees, that one permutation for which said quality criterion is optimized.
-
-
10. for each macrocell, placing said macrocell in a mirror-X position, relative to its current position, and evaluating the total lengths of the interconnecting nets;
comparing, a first time, said total lengths of the interconnecting nets with a standard, and if better than said standard, setting the current position of said macrocell to equal said mirror-X position;
-
11. for each macrocell, placing said macrocell in a mirror-Y position relative to said current position, and evaluating the total lengths of said interconnecting nets;
-
comparing a second time, said total lengths of said interconnecting nets with said standard, and if better than said standard, setting said current position of said macrocell to equal said mirror-Y position; for each macrocell, placing said macrocell in a 180°
rotation position relative to said current position, and evaluating the total lengths of said interconnecting nets;comparing, a third time, said total lengths of said interconnecting nets with said standard, and if better than said standard, setting said current position of said macrocell to said 180°
rotation position; andrepeating said (a) placing said macrocell in a mirror-X position, (b) comparing a first time, (c) placing said macrocell in a mirror-Y position, (d) comparing a second time, (e) placing said macrocell in a 180°
rotation position, and (f) comparing, a third time steps until all macrocells remain in said current position throughout an iteration.
-
-
16. for all type B subtrees of said one layout variation for which said second quality criterion is optimized, generating all possible permutations of the form of said B subtree;
for each of said permutations of the form of said B subtree, generating all possible topological variations of the leaf nodes, and selecting that one topological variation of the leaf nodes of that one permutation of the form of said B subtree for which a third quality criterion is optimized.
Specification