Hierarchical circuit partitioning using sliding windows

• US 6,301,694 B1
• Filed: 09/24/1997
• Issued: 10/09/2001
• Est. Priority Date: 09/25/1996
• Status: Expired due to Term

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Lee, Fung Fung, Tse, John
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): GARBOWSKI, LEIGH M
• Application Number:
  US08/936,112
• Time in Patent Office: 1,476 Days
• Field of Search: 395/500.08, 395/500.09, 395/500.1, 395/500.11, 716/7, 716/8, 716/9, 716/10, 716/11, 716/2
• US Class Current: 716/117
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

Systems and methods of hierarchical circuit partitioning are provided. More specifically, the invention utilizes a sliding window which is moved over portions of a hierarchical structure representing a programmable logic device. The window includes some but not all containers of the hierarchical structure so that logic cells may be partitioned within the window. After the logic cells are partitioned in the window, the window is moved to a different location of the hierarchical structure. By utilizing a sliding window, the invention is able to recursively partition logic cells into portions of the hierarchical structure which increases the overall efficiency of the partitioning.

Claims

1. A method of partitioning a network of interconnected elements comprising:

providing a hierarchical graph representing interconnected resources with nodes of the hierarchical graph representing resources and edges of the graph representing interconnections between the resources;

assigning the elements to nodes of the hierarchical graph;

selecting a first portion of the nodes of the hierarchical structure as a window;

partitioning the elements within the window;

if the elements within the window at a given node are not legally partitioned during partitioning, identifying a reason said elements were not legally partitioned;

recording said reason;

moving the window to a different location on the hierarchical structure, thereby selecting a second portion of the nodes as the window; and

repeating the partitioning step, the identifying step, and the recording step.

2. The method of claim 1, further comprising repeating the moving step and the repeating step until all the elements are legally partitioned.

3. The method of claim 1 wherein the moving step and the repeating step are executed recursively.

4. The method of claim 3, further comprising executing recursively the moving step and the repeating step until all the elements are legally partitioned.

5. The method of claim 1, further comprising the steps of:

moving the window to the given node; and

partitioning the elements within the window taking into account the recorded reason.

6. The method of claim 1 wherein the partitioning minimizes a cost function of the containers within the window.

7. The method of claim 1 wherein the hierarchical structure is selected from the group consisting of homogeneous and heterogeneous structures.

8. The method of claim 1 wherein the window is moved in an order selected from the group consisting of depth-first order and breadth-first order.

9. The method of claim 1 wherein the partitioning includes a procedure selected from the group consisting of a 2-level multi-way partitioning, repeated pairwise Kernighan-Lin type bipartitioning, and simulated annealing.

10. The method of claim 1 wherein the elements are logic elements of a programmable logic device.

11. A programmable logic device having been partitioned by the method of claim 10.

12. The method of claim 1 further comprising:

assigning weight values to the nodes;

calculating a cost function for the nodes within the window based on the weight value; and

partitioning the nodes within the window according to the cost function.

13. The method of claim 12 further comprising revising the weight values based on availability of the resources for a particular node.

14. The method of claim 12 wherein the cost function is calculated by multiplying a cut size by the weight value.

15. The method of claim 12 further comprising adjusting the weight values after the partitioning.

16. A method of partitioning a network of interconnected elements to resources in a hierarchical structure comprising:

providing a hierarchical graph representing interconnected resources with nodes of the hierarchical graph representing resources and edges of the graph representing interconnections between the resources;

assigning the elements to nodes of the hierarchical graph;

selecting a first portion of the nodes of the hierarchical structure as a window;

partitioning the elements within the window;

if the elements within the window at a given node are not legally partitioned during partitioning, identifying a reason said elements were not legally partitioned;

recording said reason;

moving the window to a different location on the hierarchical structure, thereby selecting a second portion of the nodes as the window;

selectively inflating the window to include more nodes; and

repeating the partitioning step.

17. The method of claim 16 wherein the window is inflated to include nodes of the hierarchical structure that include previously legally partitioned elements.

18. The method of claim 16, further comprising the step of deflating the window to its original size once the elements within the window are legally partitioned.

19. The method of claim 16 wherein the window initially includes a root node of the hierarchical structure.

20. In a computer system, a method of partitioning a network of interconnected elements into a hierarchical structure comprising:

providing a hierarchical graph representing the hierarchical structure, the hierarchical graph having a root node;

defining a window, a root node within the window being the root node of the hierarchical graph;

partitioning the logic elements to nodes within the window, wherein when the elements cannot be legally partitioned within the window, identifying and recording a reason said elements were not legally partitioned;

defining a subgraph for each descendant node of the root node; and

recursively executing the defining step, the partitioning step, the defining step, and the recursively executing step for each subgraph, wherein the subgraph is the hierarchical graph for the recursive execution.

21. The method of claim 20 further comprising taking the recorded reason into account when partitioning the logic elements.

22. The method of claim 20 further comprising:

when the elements cannot be legally placed within the window, inflating the window partitioning the logic elements in the inflated window and then deflating the window.

23. The method of claim 20 further comprising:

assigning weight values to the nodes;

calculating a cost function for the nodes within the window based on the weight value; and

partitioning the nodes within the window according to the cost function.