Gain matrix for hierarchical circuit partitioning

• US 6,212,668 B1
• Filed: 05/27/1997
• Issued: 04/03/2001
• Est. Priority Date: 05/28/1996
• Status: Expired due to Term

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Tse, John, Lee, Fung Fung
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): Siek, Vuthe
• Application Number:
  US08/863,880
• Time in Patent Office: 1,407 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 716/7, 716/2, 716/8
• US Class Current: 716/125
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A method for partitioning a group of cells in a network into a set of disjoint blocks of cells. The network is represented by a hierarchical graph with each level representing a hierarchy of resources, leaf nodes representing the blocks of cells, and edges representing interconnections between resources. A gain matrix is formed by combining a gain vector for each level of hierarchy for each possible move. Cells are moved between leaf nodes based on the gain matrix computed.

Claims

1. A method of partitioning a network of cells into a plurality of disjont blocks of cells comprising:

representing said network as a hierarchial graph with a plurality of nodes at a first level and a plurality of nodes at a second level, the plurality of nodes at the first level being descendent from the plurality of nodes at the second level;

distributing the cells to said plurality of nodes at the first level to form an initial partition;

calculating a first gain vector for a first cell at said first level, the first gain vector representing a cost associated with moving the first cell from a first node of the plurality of nodes at the first level to a second node of the plurality of nodes at the first level;

calculating a second gain vector for said first cell as if the cells in the plurality of nodes on the first level were in their respective parent nodes at said second level, the second gain vector representing a cost associated with moving the first cell from a third node on the second level to a fourth node at the second level, wherein the first and second gain vectors form a gain matrix for the first cell; and

selectively moving the first cell to a different node depending on said gain matrix.

2. The method of claim 1 wherein said distributing is accomplished using a greedy algorithm.

3. The method of claim 1 wherein a gain matrix is formed for each possible move of said first cell.

4. The method of claim 3 wherein said selectively moving further comprises:

calculating a value for each of said gain matrices;

selecting a best move cell using said values; and

moving said best move cell.

5. The method of claim 4 further comprising the steps of:

before said calculating first gain vector, unlocking all of said cells;

after said moving said best move cell, locking said best move cell; and

repeating said calculating first and second gain vectors, said calculating value, said selecting a best move, said moving and said locking until a minimum number of cells are unlocked.

6. The method of claim 5 wherein said mimimum number is zero.

7. The method of claim 4 wherein said value is calculated by summing entries of said gain matrix.

8. The method of claim 4 further comprising:

creating a weight matrix;

multiplying each gain matrix by said weight matrix; and

summing entries of said gain matrix to calculate said value.

9. The method of claim 8 further comprising dynamically altering said weight matrix.

10. The method of claim 1 wherein said calculating first and second gain vectors further comprise:

creating a first subgraph comprising nodes from said first level;

calculating said first gain vector according to said first sub graph; and

creating a second subgraplh comprising nodes from said second level; and

calculating said second gain vector according to said second subgraph.

11. The method of claim 1 wherein said plurality of disjoint blocks are logic array blocks of a programmable logic device.

12. The method of claim 1 wherein said network is a netlist for a programmable logic device.

13. The method of claim 1 wherein said hierarchical graph further comprises a third level, wherein nodes on said third level represent a first set of conductors of a programmable logic device, nodes on said second level represent a second set of conductors of said programmable logic device, nodes on said first level represent a set of logic array blocks of said programmable logic device, and said cells represent logic elements of said programmable logic device.

14. A semiconductor device, said semiconductor device having been partitioned using the method of claim 1.

15. A digital system, said digital system comprising:

a processing unit; and

a semiconductor device having been partitioned using the method of claim 1.

16. The method of claim 1 wherein the first node and the second node are distinct nodes.

17. The method of claim 1 wherein the third node and the fourth node are distinct nodes.

18. A method of partitioning a network of cells into a plurality of disjoint blocks of cells comprising:

representing said network as a hierarchial graph having a first level and a second level;

distributing said cells to nodes at said first level of said graph to create an initial partiton;

recording said initial partition as a best partition;

unlocking each cell;

calculating a first gain vector for each possible move of each unlocked cell as said first level, the first gain vector representing a cost associated with moving a first cell from a first node at the first level to a second node at the first level;

calculating a second gain vector for each possible move of each unlocked cell as if the cells were in their respective parent nodes at said second level, the second gain vector repesenting a cost associated with moving the first cell from a third node on the second level to a fourth node on the second level, the first and second gain vectors forming a gain matrix for each unlocked cell;

calculating a value for each of said gain matrices;

finding a best move cell using said values, said best move cell representing a best cell that is the most desirable cell to move based on at least one criterion;

moving said best move cell to create a new partition;

locking said best move cell;

repeating said calculating gain vectors, said calculating a value, said finding a move cell, said moving and said locking until a minimum number of cells are locked;

if said new partition is better than said best partition, then recording said new partition as said best partition.

19. The method of claim 18 wherein said distribution step is accomplished using a greedy algorithm.

20. The method of claim 18 wherein said minimum number is zero.

21. The method of claim 18 wherein said value is calculated by summing entries of said gain matrix.

22. The method of claim 18 further comprising:

creating a weight matrix;

multiplying each gain matrix by said weight matrix; and

summing entries of said gain matrix to calculate said value.

23. The method of claim 22 further comprising dynamically altering said weight matrix.

24. The method of claim 18 wherein said calculating first and second gain vectors further comprise:

creating a first subgraph comprising nodes from said first level;

calculating said first gain vector from said first subgraph; and

creating a second subgraph comprising nodes from said second level; and

calculating said second gain vector from said second subgraph.

25. A semiconductor device, said semiconductor device having been partitioned using the method of claim 18.

26. A digital system comprising:

a processing unit; and

a semiconductor device having been partitioned using the method of claim 18.

27. A computer program product for partitioning a network of cells into a plurity of disjoint blocks, said computer program product embodying computer readable code on a storage medium for causing a processor to:

represent said network as a hierarchial graph with a plurality of nodes at a first level and a plurality of nodes at a second level, the plurality of nodes at the first level being descendent from the plurality of nodes at the second level;

p1 distribute the cells to said plurality of nodes at the first level to form an initial partition.

calculate a first gain vector for a first cell at said first level, the first gain vector representing a cost associaed wih moving the first cell from a first node of the plurality of nodes at the first level to a second node of the plurality of nodes at the first level;

calculating a second gain vector for said first cell as if the cells in the plurality of nodes on the first level were in their respective parent nodes at said second level, the second gain vector representing a cost associated with moving the first cell from a third node on the second level to a fourth node at the second level, wherein the first and second gain vectors form a gain matrix for the first cell; and

selectively move the first cell to a different node depending on said gain matrix.