Apparatus and method for partitioning resources for interconnections

• US 5,640,327 A
• Filed: 02/09/1996
• Issued: 06/17/1997
• Est. Priority Date: 01/25/1994
• Status: Expired due to Fees

• Current Assignee: Actel Corporation (Microchip Technology Incorporated)
• Original Assignee: BTR Incorporated (Schneider Electric SE)
• Inventors: Ting, Benjamin S.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): GARBOWSKI, LEIGH M
• Application Number:
  US08/599,122
• Time in Patent Office: 494 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 326/37, 326/39, 326/41, 326/47, 326/101, 340/825.83
• US Class Current: 716/121
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. The method as set forth in claim 1, wherein the predefined level corresponds to the number of levels of interconnect resources.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. The apparatus as set forth in claim 11, wherein the predefined level corresponds to the number of levels of interconnect resources.

19. 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.

20. 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.

21. 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.

22. 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.

23. 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.