US5640327A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for partitioning resources for interconnections
Assignee: Microsemi SoC Corp
•
Filing: 1996-02-09
•
Granted: 1997-06-17
•
Expires: 2016-02-09
Abstract
Abstract An apparatus and method for determining how to interconnect a plurality of components of a system, given a limited number of interconnect resources available to a device. First, it is determined whether the system meets the capacity constraints of the device. If the requirements exceed the capacity, a larger device is necessary. Otherwise, a topmost interconnection level is established. This topmost level is partitioned into four different partitions. The components are assigned and optimized to these four partitions. Next, a lower level of interconnection is established for one or more of these four partitions. Each of these lower levels are, in turn, partitioned into four different partitions. Components are then assigned and optimized to these partitions. This process is repeated for even lower levels until routing of the interconnections for the system is achieved. Thereupon, the components are physically interconnected from the lower levels to the topmost level according to the routing pattern that was determined in the establishing, partitioning, and said optimizing steps.
Inventors
- 👤 Benjamin S. Ting
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 01:57
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
252 words
A method for placement of components of a device into partitions, said device having a defined surface area for placement of the components, said device having multiple mutually distinct levels of interconnect resources, the interconnect resources of each subsequent level of the level of the multiple levels spanning a proportionately shorter distance than the interconnect resources of an immediately prior level, said method comprising the steps of: a) establishing a first level of partitions corresponding to a first level of interconnect resources of the multiple levels of interconnect resources by dividing the surface area of the device into a plurality of first partitions, said first level of interconnect resources crossing a boundary between adjacent partitions of the first level of partitions; b) optimizing an assignment of each component to one of said plurality of first partitions based upon interconnect resources comprising the first level of interconnect resources; c) establishing subsequent levels of partitions until a predefined level is reached, said subsequent levels of partitions corresponding to respective subsequent levels of interconnect resources, each subsequent level of interconnect resources crossing a boundary between adjacent partitions of a corresponding level of partitions, each subsequent level of partitions generated by dividing each immediate prior level partition into a corresponding plurality of subsequent partitions and optimizing the assignment of each component in the prior level partition to one of the corresponding plurality of subsequent partitions based upon the subsequent level of interconnect resources and levels of interconnect resources prior to the subsequent level of interconnect resources.
Claim 2
Independent Claim
252 words
A method for placement of components of a device into partitions, said device having a defined surface area for placement of the components, said device having multiple mutually distinct levels of interconnect resources, the interconnect resources of each subsequent level of the level of the multiple levels spanning a proportionately shorter distance than the interconnect resources of an immediately prior level, said method comprising the steps of: a) establishing a first level of partitions corresponding to a first level of interconnect resources of the multiple levels of interconnect resources by dividing the surface area of the device into a plurality of first partitions, said first level of interconnect resources crossing a boundary between adjacent partitions of the first level of partitions; b) optimizing an assignment of each component to one of said plurality of first partitions based upon interconnect resources comprising the first level of interconnect resources; c) establishing subsequent levels of partitions until a predefined level is reached, said subsequent levels of partitions corresponding to respective subsequent levels of interconnect resources, each subsequent level of interconnect resources crossing a boundary between adjacent partitions of a corresponding level of partitions, each subsequent level of partitions generated by dividing each immediate prior level partition into a corresponding plurality of subsequent partitions and optimizing the assignment of each component in the prior level partition to one of the corresponding plurality of subsequent partitions based upon the subsequent level of interconnect resources and levels of interconnect resources prior to the subsequent level of interconnect resources.
Claim 3
Dependent Claim
43 words
The method as set forth in claim 1, further comprising the steps of determining whether the components exceed the capacity constraints of the device, and performing steps a), b) and c) if the components do not exceed the capacity constraints of the device.
Claim 4
Dependent Claim
37 words
The method of claim 2, wherein capacity constraints of said device includes the number of components of said system, number of interconnect resources, number of components that can fit within the surface area, and input/output routing access.
Claim 5
Dependent Claim
41 words
The method of claim 1, wherein said step of establishing a first level of partitions divides the surface area into four partitions and said step of establishing subsequent levels of partitions divides each immediate prior level partition into four subsequent partitions.
Claim 6
Dependent Claim
30 words
The method of claim 4, wherein the span of each interconnect resource that crosses a partition boundary is proportional to lengths of two of said partitions of a corresponding level.
Claim 7
Dependent Claim
30 words
The method of claim 5, wherein said lengths of two of said partitions of said corresponding level is proportional to half a length of two partitions of a subsequent level.
Claim 8
Dependent Claim
32 words
The method of claim 6, wherein said lengths of said two of said partitions of said corresponding level is proportional to twice the length of two partitions of an immediate prior level.
Claim 9
Dependent Claim
34 words
The method of claim 1, wherein said step of optimizing an assignment of each component to one of said plurality of first partitions is a function of partition capacity, routing resources, and access resources.
Claim 10
Dependent Claim
35 words
The method as set forth in claim 1, wherein the predefined level is reached when partition capacity constraints are exceeded, said partition capacity constraints comprising a number of interconnect resources located across boundaries of partitions.
Claim 11
Dependent Claim
21 words
The method as set forth in claim 1, wherein the predefined level corresponds to the number of levels of interconnect resources.
Claim 12
Independent Claim
255 words
An apparatus for placement of components of a device into partitions, said device having a defined surface area for placement of the components, said device having multiple mutually distinct levels of interconnect resources, the interconnect resources of each subsequent level of the level of the multiple levels spanning a proportionately shorter distance than the interconnect resources of an immediately prior level, said apparatus comprising: a) means for establishing a first level of partitions corresponding to a first level of interconnect resources of the multiple levels of interconnect resources by dividing the surface area of the device into a plurality of first partitions, said first level of interconnect resources crossing a boundary between adjacent partitions of the first level of partitions; b) means for optimizing an assignment of each component to one of said plurality of first partitions based upon interconnect resources comprising the first level of interconnect resources; c) means for establishing subsequent levels of partitions until a predefined level is reached, said subsequent levels of partitions corresponding to respective subsequent levels of interconnect resources, each subsequent level of interconnect resources crossing a boundary between adjacent partitions of a corresponding level of partitions, each subsequent level of partitions generated by dividing each immediate prior level partition into a corresponding plurality of subsequent partitions and optimizing the assignment of each component in the prior level partition to one of the corresponding plurality of subsequent partitions based upon the subsequent level of interconnect resources and levels of interconnect resources prior to the subsequent level of interconnect resources.
Claim 13
Independent Claim
255 words
An apparatus for placement of components of a device into partitions, said device having a defined surface area for placement of the components, said device having multiple mutually distinct levels of interconnect resources, the interconnect resources of each subsequent level of the level of the multiple levels spanning a proportionately shorter distance than the interconnect resources of an immediately prior level, said apparatus comprising: a) means for establishing a first level of partitions corresponding to a first level of interconnect resources of the multiple levels of interconnect resources by dividing the surface area of the device into a plurality of first partitions, said first level of interconnect resources crossing a boundary between adjacent partitions of the first level of partitions; b) means for optimizing an assignment of each component to one of said plurality of first partitions based upon interconnect resources comprising the first level of interconnect resources; c) means for establishing subsequent levels of partitions until a predefined level is reached, said subsequent levels of partitions corresponding to respective subsequent levels of interconnect resources, each subsequent level of interconnect resources crossing a boundary between adjacent partitions of a corresponding level of partitions, each subsequent level of partitions generated by dividing each immediate prior level partition into a corresponding plurality of subsequent partitions and optimizing the assignment of each component in the prior level partition to one of the corresponding plurality of subsequent partitions based upon the subsequent level of interconnect resources and levels of interconnect resources prior to the subsequent level of interconnect resources.
Claim 14
Dependent Claim
33 words
The apparatus as set forth in claim 11, wherein the means for establishing a first level of partitions, means for optimizing and means for establishing subsequent levels of partitions comprises a computer system.
Claim 15
Dependent Claim
44 words
The apparatus as set forth in claim 11, wherein the means for establishing a first level of partitions divides the surface area into four partitions and the means for establishing subsequent levels of partitions divides each immediate prior level partition into four subsequent partitions.
Claim 16
Dependent Claim
30 words
The apparatus of claim 13, wherein a span of each interconnect resource that crosses a partition boundary is proportional to lengths of two of said partitions of a corresponding level.
Claim 17
Dependent Claim
30 words
The apparatus of claim 14, wherein said lengths of two of said partitions of said corresponding level is proportional to half the length of two partitions of a subsequent level.
Claim 18
Dependent Claim
32 words
The apparatus of claim 15, wherein said lengths of said two of said partitions of said corresponding level is proportional to twice the length of two partitions of an immediate prior level.
Claim 19
Dependent Claim
63 words
The apparatus as set forth in claim 11, further comprising a means for determining whether the components exceed the capacity constraints of the device, and controlling such that the means for establishing a first level of partitions, means for optimizing and means for establishing subsequent levels of partitions do not execute if the components do not exceed the capacity constraints of the device.
Claim 20
Dependent Claim
21 words
The apparatus as set forth in claim 11, wherein the predefined level corresponds to the number of levels of interconnect resources.
Claim 21
Dependent Claim
44 words
The apparatus as set forth in claim 11, wherein said means for optimizing an assignment of each component to a plurality of first partitions and means for establishing subsequent levels of partitions optimize as a function of partition capacity, routing resources, and access resources.
Claim 22
Independent Claim
170 words
A method for partitioning a surface area of a programmable logic device into four partitions corresponding to a level of routing resources of said programmable logic device, said method comprising the steps of: dividing said surface area in two in a first axis; dividing said surface area in two in a second axis, wherein said second axis intersects said first axis perpendicularly and said surface area is divided into said four partitions; determining said routing resources that are required to implement a circuit design based on a routing pattern of the routing resources, said step of determining said routing resources determining extra routing resources needed to route connections between a first component located within a first partition of the four partitions to a second component located within a second partition of the four partitions, wherein the first and second partitions are diagonally opposed partitions and the routing resources needed to provide L-shaped connections are included; optimizing said routing resources in relation to a component capacity of said programmable logic device.
Claim 23
Independent Claim
170 words
A method for partitioning a surface area of a programmable logic device into four partitions corresponding to a level of routing resources of said programmable logic device, said method comprising the steps of: dividing said surface area in two in a first axis; dividing said surface area in two in a second axis, wherein said second axis intersects said first axis perpendicularly and said surface area is divided into said four partitions; determining said routing resources that are required to implement a circuit design based on a routing pattern of the routing resources, said step of determining said routing resources determining extra routing resources needed to route connections between a first component located within a first partition of the four partitions to a second component located within a second partition of the four partitions, wherein the first and second partitions are diagonally opposed partitions and the routing resources needed to provide L-shaped connections are included; optimizing said routing resources in relation to a component capacity of said programmable logic device.
Claim 24
Dependent Claim
88 words
The method of claim 20, further comprising the steps of determining a number of components of said programmable logic device, a number of routing resources that span across boundaries of said four partitions, and input/output routing accesses; wherein said steps of dividing said surface area in two in a first axis, dividing said surface area in two in a second axis, determining and optimizing are not performed if the number of components, the number of routing resources that span boundaries and input/output routing accesses exceeds a device capacity.
Claim 25
Dependent Claim
29 words
The method of claim 21 wherein a span of one of said L shaped connections that crosses two boundaries is proportional to a length of four of said partitions.
Claim 26
Dependent Claim
28 words
The method of claim 21, wherein a span of a routing resource that crosses one of said boundaries is proportional to lengths of two of said four partitions.
References Cited (Backward Citations)
US3617714A
Cited
US4612618A
Cited
US4554625A
Cited
US4593363A
Cited
US4577276A
Cited
US4688072A
Cited
US4713773A
Cited
US4754408A
Cited
US4777606A
Cited
US4908772A
Cited
US4918614A
Cited
US5046017A
Cited
US5224057A
Cited
US5251147A
Cited
US5375069A
Cited
US5128871A
Cited
US5218551A
Cited
US5224056A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-06-16 | 2000-12-16 | 2001-06-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-06-16 | 2004-12-16 | 2005-06-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-06-16 | 2008-12-16 | 2009-06-17 | $7700.00 | Window Closed / Lapsed |