Gain matrix for hierarchical circuit partitioning

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.

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.