EP0294188A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Hierarchical floorplanning
Assignee: LSI Corp
•
Filing: 1988-06-02
•
Granted: —
•
Expires: 2008-06-02
Abstract
Abstract A system in which logic and/or memory elements are automatically placed on an integrated circuit ("floorplanning"), taking into account the constraints imposed by the logic designer, not only increases the density of the integrated circuit, and the likelihood of routing interconnections among the elements on that circuit, but it also enables the user to quickly modify the floorplan manually, and then graphically display the results of such modifications. By conforming itself to the logic designer's modular, hierarchical design, the system is capable of placing elements at each level of the specified hierarchy, based upon the number of interconnections between elements throughout that hierarchy. The system includes means for estimating the size of elements which have not yet been laid out, and for partitioning groups of elements into successively smaller "slices" of the integrated circuit (using heuristic techniques when exhaustive methods are no longer (feasible) until all elements are placed relative to one another. The system also includes means for determining the precise shapes of elements on the integrated circuit, based upon the relative placement of such elements, and upon the additional area required for routing interconnections among such elements. The functionality of this hierarchical floorplanning system can be embodied in the form of software, hardware or any combination thereof, because the system's hierarchical methodology and structure is independent of its particular embodiment.
Inventors
- 👤 Hossein Modarres
- 👤 Susan Raam
- 👤 Jiun-Hao Lai
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-09 12:09
CPC Classifications
H; H10; H10P; H10P95/00; G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
181 words
A system for placing functions on an integrated circuit, the integrated circuit comprising a hierarchy of N levels of functions, where N is an integer (N ≧ 1) representing the number of hierarchical levels of functionality in the integrated circuit, the first of the levels representing the integrated circuit as a whole, and where n is an integer (1 ≦ n ≦ N) representing the level of any particular function in the hierarchy, the hierarchy defining at least one of the (n)th level functions (a parent function) as a plurality of (n + 1)st level functions (children functions, each being a child function), each child function (which is not also a parent function) being a terminal function, each terminal function being connected to at least one other terminal function, by at least one net, each net defining a plurality of interconnected terminal functions, characterized by: means for determining the location on the integrated circuit of (n)th level children functions (n ≧ 2), relative to one another within their parent, and means for determining the shape of the (n)th level children functions.
Claim 2
Independent Claim
181 words
A system for placing functions on an integrated circuit, the integrated circuit comprising a hierarchy of N levels of functions, where N is an integer (N ≧ 1) representing the number of hierarchical levels of functionality in the integrated circuit, the first of the levels representing the integrated circuit as a whole, and where n is an integer (1 ≦ n ≦ N) representing the level of any particular function in the hierarchy, the hierarchy defining at least one of the (n)th level functions (a parent function) as a plurality of (n + 1)st level functions (children functions, each being a child function), each child function (which is not also a parent function) being a terminal function, each terminal function being connected to at least one other terminal function, by at least one net, each net defining a plurality of interconnected terminal functions, characterized by: means for determining the location on the integrated circuit of (n)th level children functions (n ≧ 2), relative to one another within their parent, and means for determining the shape of the (n)th level children functions.
Claim 3
Dependent Claim
42 words
A system as claimed in claim 2 characterized by: means for calculating the additional area required to interconnect the (n)th level children functions, and means for redetermining the shape of the (n)th level children functions, based in part upon the additional area.
Claim 4
Dependent Claim
25 words
A system as claimed in claim 1 or 2 characterized by means for graphically displaying the location on the integrated circuit of (n)th level functions.
Claim 5
Independent Claim
288 words
A system for estimating the area occupied by (n)th level functions of an integrated circuit, the integrated circuit comprising a hierarchy of N levels of functions, where N is an integer (N ≧ 1) representing the number of hierarchical levels of functionality in the integrated circuit, the first of said levels representing the integrated circuit as a whole, and where n is an integer (1 ≦ n ≦ N) representing the level of any particular function in the hierarchy, the hierarchy defining at least one of the (n)th level functions (a parent function) as a plurality of (n + 1)st functions (children functions, each being a child function), each child function (which is not also a parent function) being a terminal function, each terminal function being connected to at least one other terminal function, by at least one net, each net defining a plurality of interconnected terminal functions, characterized by: means for estimating the area of each terminal function which comprises many small cells the collective layout of which is not specified (macrocells), including means for estimating the number of tracks necessary to interconnect said macrocells, and means for determining the area of the terminal function of macrocells by adding, to the sum of the areas occupied by the macrocells, the product of the number of tracks and the known width of an average track, and means for estimating the area of each function which is not a terminal function, including means for estimating the percentage of the total area of the integrated circuit available for routing connections among functions, and for distributing that available area uniformly to each parent function by summing the areas of each of its children functions, and multiplying that sum by said percentage.
Claim 6
Independent Claim
288 words
A system for estimating the area occupied by (n)th level functions of an integrated circuit, the integrated circuit comprising a hierarchy of N levels of functions, where N is an integer (N ≧ 1) representing the number of hierarchical levels of functionality in the integrated circuit, the first of said levels representing the integrated circuit as a whole, and where n is an integer (1 ≦ n ≦ N) representing the level of any particular function in the hierarchy, the hierarchy defining at least one of the (n)th level functions (a parent function) as a plurality of (n + 1)st functions (children functions, each being a child function), each child function (which is not also a parent function) being a terminal function, each terminal function being connected to at least one other terminal function, by at least one net, each net defining a plurality of interconnected terminal functions, characterized by: means for estimating the area of each terminal function which comprises many small cells the collective layout of which is not specified (macrocells), including means for estimating the number of tracks necessary to interconnect said macrocells, and means for determining the area of the terminal function of macrocells by adding, to the sum of the areas occupied by the macrocells, the product of the number of tracks and the known width of an average track, and means for estimating the area of each function which is not a terminal function, including means for estimating the percentage of the total area of the integrated circuit available for routing connections among functions, and for distributing that available area uniformly to each parent function by summing the areas of each of its children functions, and multiplying that sum by said percentage.
Claim 7
Independent Claim
278 words
A method of estimating the area occupied by (n)th level functions of an integrated circuit, the integrated circuit comprising a hierarchy of N levels of functions, where N is an integer (N ≧ 1) representing the number of hierarchical levels of functionality in the integrated circuit, the first of the levels representing the integrated circuit as a whole, and where n is an integer (1 ≦ n ≦ N) representing the level of any particular function in the hierarchy, the hierearchy defining at least one of said (n)th level functions (a parent function) as a plurality of (n + 1)st level functions (children functions, each being a child function), each child function (which is not also a parent function) being a terminal function, each terminal function being connected to at lest one other terminal function, by at lest one net, each net defining a plurality of interconnected terminal functions, characterized by: estimating the area of each terminal function which comprises many small cells the collective layout of which is not specified (macrocells), including estimating the number of tracks necessary to interconnect the macrocells, and determining the area of the terminal function of macrocells by adding, to the sum of the areas occupied by the macrocells, the product of the number of tracks and the known width of an average track, and estimating the area of each function which is not a terminal function, including estimating the percentage of the total area of the integrated circuit available for routing connections among functions, and distributing that available area uniformly to each parent function by summing the areas of each of its children functions, and multiplying that sum by said percentage.
Claim 8
Independent Claim
278 words
A method of estimating the area occupied by (n)th level functions of an integrated circuit, the integrated circuit comprising a hierarchy of N levels of functions, where N is an integer (N ≧ 1) representing the number of hierarchical levels of functionality in the integrated circuit, the first of the levels representing the integrated circuit as a whole, and where n is an integer (1 ≦ n ≦ N) representing the level of any particular function in the hierarchy, the hierearchy defining at least one of said (n)th level functions (a parent function) as a plurality of (n + 1)st level functions (children functions, each being a child function), each child function (which is not also a parent function) being a terminal function, each terminal function being connected to at lest one other terminal function, by at lest one net, each net defining a plurality of interconnected terminal functions, characterized by: estimating the area of each terminal function which comprises many small cells the collective layout of which is not specified (macrocells), including estimating the number of tracks necessary to interconnect the macrocells, and determining the area of the terminal function of macrocells by adding, to the sum of the areas occupied by the macrocells, the product of the number of tracks and the known width of an average track, and estimating the area of each function which is not a terminal function, including estimating the percentage of the total area of the integrated circuit available for routing connections among functions, and distributing that available area uniformly to each parent function by summing the areas of each of its children functions, and multiplying that sum by said percentage.
Claim 9
Dependent Claim
59 words
A method as claimed in claim 5 characterized in that the step of estimating the number of tracks necessary to interconnect the macrocells comprises the steps of raising the sum of th areas occupied by said macrocells to a power equal to a first constant value, and multiplying that sum raised to that power by a second constant value.
Claim 10
Independent Claim
187 words
A method of placing functions on an integrated circuit, said integrated circuit comprising a hierarchy of N levels of functions, where N is an integer (N ≧ 1) representing the number of hierarchical levels of functionality in the integrated circuit, the first of said levels representing the integrated circuit as a whole, and where n is an integer (a ≦ n ≦ N) representing the level of any particular function in the hierearchy, the hierarchy defining at least one of the (n)th level functions (a parent function) as a plurality of (n + 1)st level functions (children functions, each being a child function), each child function (which is not also a parent function) being a terminal function, each terminal function being connected to at least one other terminal function, by at least one net, each net defining a plurality of interconnected terminal functions, characterized by the steps of: estimating the number of connections between functions throughout all N levels of the hierarchy, and determining the location on the integrated circuit of each (n)th level function in the hierarchy, based in part upon the estimated number of connections.
Claim 11
Independent Claim
187 words
A method of placing functions on an integrated circuit, said integrated circuit comprising a hierarchy of N levels of functions, where N is an integer (N ≧ 1) representing the number of hierarchical levels of functionality in the integrated circuit, the first of said levels representing the integrated circuit as a whole, and where n is an integer (a ≦ n ≦ N) representing the level of any particular function in the hierearchy, the hierarchy defining at least one of the (n)th level functions (a parent function) as a plurality of (n + 1)st level functions (children functions, each being a child function), each child function (which is not also a parent function) being a terminal function, each terminal function being connected to at least one other terminal function, by at least one net, each net defining a plurality of interconnected terminal functions, characterized by the steps of: estimating the number of connections between functions throughout all N levels of the hierarchy, and determining the location on the integrated circuit of each (n)th level function in the hierarchy, based in part upon the estimated number of connections.
Claim 12
Dependent Claim
109 words
A method as claimed in claim 7 characterized in that the step of estimating the number of connections between functions throughout all N levels of the hierarchy comprises the steps of: determining the expected number of connections between the terminal functions connected by each net, by dividing the minimum number of connections among said terminal functions by the total number of permutations of pairs of said terminal functions, and determining the expected number of connections between each nonterminal function and all other functions in the hierarchy, by summing the expected number of connections between the terminal offspring of said nonterminal function and the terminal offspring of said other functions.
Claim 13
Dependent Claim
65 words
A method as claimed in claim 7 characterized in that the step of determining the location on the integrated circuit of each (n)th level function in the hierarchy comprises the step of: determining the location on the integrated circuit of each child function in the hierarchy, such that the child function is placed in the area of the integrated circuit occupied by its parent function.
Claim 14
Dependent Claim
119 words
A method as claimed in claim 7 characterized in that the step of determining the location on the integrated circuit of each (n)th level function in the hierarchy comprises the step of: determining the location of (n)th level children functions relative to one another within their parent, including determining the location of (n)th level children functions relative to one another within their parent, based in part upon said estimated number of connections, and determining the location of (n)th level children functions (n ≧ 3), relative to one another within their parent, based in part upon both the estimated number of connections and the location of (k)th level children functions (k ≦ n), relative to one another within their parent.
Claim 15
Dependent Claim
97 words
A method as claimed in claim 10 characterized in that the step of determining the location of (n)th level children functions relative to one another within their parent comprises the steps of: partitioning said children functions into two groups, determining the location on the integrated circuit of each of said two groups relative to the other, and successively partitioning each of said two groups of functions into two groups, and determining the location on the integrated circuit of each of said latter two groups relative to the other, until each of said groups contains exactly one function.
Claim 16
Dependent Claim
264 words
A method as claimed in claim 11 characterized in that the steps of partitioning the children functions into two groups and determining the location on the integrated circuit of each of the two groups relative to the other, comprises the steps of: dividing the parent function into two regions, such that each of the regions is either on top of, below, to the left of, or to the right of the other, each of the two regions comprising one of the two groups of functions, calculating, for a plurality of the possible permutations of the functions between the two groups, the absolute value of the difference between the sum of the areas of the functions in one of said two groups and the sum of the areas of the functions in the other of the two groups, the absolute value divided by the sum of the areas of the functions in both of the groups (the proportional area difference), using said estimated number of connections to calculate the number of connections between functions in one of the two groups and either functions in the other of the two groups or functions not in either of the two groups but on the same side of the line separating said two regions as is the other of the two groups, and selecting the permutation of the functions between the two groups which yields the minimum sum of the proportional area difference and said number of connections between functions, thereby determining the location on the integrated circuit of each of said two groups relative to the other.
Claim 17
Dependent Claim
91 words
A method as claimed in claim 7 characterized in that the step of determining the location on the integrated circuit of each (n)th level function in the hierarchy comprises the steps of defining a shape function, representing one or more possible shapes of each terminal function, determining the shape function of each parent function by combining the shape functions of its children functions, thereby determining the shape function of the integrated circuit, and selecting the shape of the integrated circuit, thereby determining the shape of each function on the integrated circuit.
Claim 18
Dependent Claim
168 words
A method as claimed in claim 13 characterized in that the step of determining the shape function of each parent function by combining the shape functions of its children functions comprises the steps of: determining whether the location of each child function, relative to another of said child functions, is above, below, to the left of, or to the right of said other child function, determining the X and Y coordinates of said parent's shape function, for each of said child functions which is either above or below said other child function, by calculating for each X coordinate corresponding to the X coordinates of said children functions, the sum of the Y coordinates of each said children functions, and determining the X and Y coordinates of said parent's shape function, for each of said child functions which is either to the left or to the right of said other child function, by calculating, for each Y coordinate corresponding to the Y coordinates of each of said children functions.
Claim 19
Dependent Claim
200 words
A method as claimed in claim 7 characterized in that the step of determining the location on the integrated circuit of each (n)th level function in the hierarchy comprises the steps of determining the locations of (n)th level functions relative to one another within their parent, including determining the location of 2d level children functions, relative to one another within their parent, based in part upon said estimated number of connections, and determining the location of (n)th level children functions (n ≧ 3), relative to one another within their parent, based in part upon both said estimated number of connections and the location of (k)th level children functions (k ≦ n), relative to one another within their parent, and transforming the locations of (n)th level functions relative to one another within their parent into precise locations on the integrated circuit, including defining a shape function, representing one or more possible shapes of each terminal function, determining the shape function of each parent function by combining the shape functions of its children functions, thereby determining the shape function of the integrated circuit, and selecting the shape of the integrated circuit, thereby determining the shape of each function on the integrated circuit.
Claim 20
Dependent Claim
98 words
A method as claimed in claim 15 characterized in that the step of determining the location on the integrated circuit of each (n)th level function in the hierarchy also comprises the steps of: estimating, and allocating to the area occupied by each function, the routing area required to connect that function to other functions on the integrated circuit, and repeating the step of transforming said locations of (n)th level functions relative to one another within their parent into precise locations on the integrated circuit, taking into account said routing area allocated to the area occupied by each function.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.