Gain matrix for hierarchical circuit partitioning

Details Gain matrix for hierarchical circuit partitioning Gain matrix for hierarchical circuit partitioning

1997-05-27

2001-04-03

Smith, Matthew (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000

Reexamination Certificate

active

06212668

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention refers generally to graph partitioning, and more particularly, to partitioning a network of cells into disjoint blocks.
The problem of partitioning interconnected cells between limited resources is well known in the art. This problem arises in many areas. The task is to divide a number of cells, which have some type of interaction between them, among a number of resources. A goal is to minimize the cost of the interaction between the cells. The cost may be measured by a variety of values, depending upon the nature of the network. The cost of the interactions is often referred to as the cutsize.
For example, in the area of circuit partitioning for integrated circuits, discrete logic functions may be allocated to specific logic elements. The connections between different logic elements require the use of interconnect resources such as conductive wires. By minimizing the number of interconnections required between logic elements, the total number of wires needed for a particular design may be reduced. This allows a larger design to fit into a smaller area. The cost of this network may be measured by the number of interconnections needed.
Another area, for example, in which partitioning may be used is in parallel processing. Some parallel processing applications require that a large number of individual computations be assigned to a smaller number of processors. However, often the individual computations depend on results from other computations. This requires the processors to communicate. These communications slow down the speed in which the calculation can be completed. The cost of this network may be measured by the amount of time spent communicating. It is desirable to allocate the computations to processors such that the communication costs are minimal. Many other applications for this invention may be readily apparent to one skilled in the art.
The problem of graph partitioning has been extensively considered in the literature. See, for example, B. W. Kernighan and S. Lin, “
An Efficient Heuristic Procedure For Partitioning Graphs
”, and Laura A. Sanchis, “
Multiple
-
Way Network Partitioning
”, both of which are incorporated herein by reference for all purposes. Traditionally, in order to solve a network partitioning problem, the network has been described as a hierarchical graph. Each node in the graph represents a possible resource and each edge connecting the nodes represents a possible interconnection between the resources. The graph is a hierarchical graph wherein each node contains zero or more subnodes (its children or descendants) but can only be a descendant of one other node (its parent or ancestor.) The cells (i.e., those items which are to be assigned to the resources) are only placed in leaf nodes. Leaf nodes are those nodes at the lowest level of the graph. By definition, leaf nodes have no descendants.
A typical three-level hierarchical graph is depicted in FIG.
2
. Each level of the graph depicts a different level of hierarchy. For example, in the case of circuit partitioning, the H
0,0
node may refer to the entire network; whereas, the H
2,0
node may be a particular group of logic elements within the network. The cells, for example cells a and b in the H
2,0
node, may refer to particular logic elements. The subscripts in the node references are given to simplify discussion of particular nodes and are representative of the level of the node and a node number within that level.
As described above, the objective of partitioning is to place all the cells legally into the graph such that the interconnections among the nodes are minimized. This has traditionally been done using gain vectors. By this traditional method, a gain vector may be calculated for each possible move of each cell. A gain vector contains information of the change in number of interconnections (i.e., cutsize) in the graph due to moving a particular cell. A first entry in the gain vector represents the change in the cutsize that would be realized if the cell were moved. The second entry represents the likely change in cutsize from a subsequent cell move if the cell were moved now. For example, it assumes the current move has been made, and then determines what the next probable move would be and how that move will affect the cutsize. In other words, it does a lookahead estimation which predicts how future cell moves will be affected by moving the cell. The number of entries in the gain vector is dependant how many levels of lookahead are desired.
Values for the gain vectors are calculated and the cell with the best gain vector may be moved. The gain vectors are then recalculated and the procedure is repeated for the remaining cells. This may continue until a desirable partition is found. This method is described in the Sanchis reference cited above.
A limitation of the traditional method is that it does not take into account the effect at all hierarchal levels. It is only a two level approach and therefore will not find the move that will be the best from a global standpoint. It is therefore desirable to find a method which will place all cells into a block such that the costs are minimized for all levels of the design. An improved method for graph partitioning is therefore desirable.
SUMMARY OF THE INVENTION
A method is provided for partitioning a network of cells into a plurality of disjoint blocks of cells. The network may be represented as a hierarchical graph. Gain vectors may be calculated for multiple levels of the graph. A gain matrix is formed from the gain vectors. The cells are assigned to the disjoint blocks of cells using the gain matrices.
In an embodiment of the present invention, the gain vectors are calculated for a particular level using a subgraph of the hierarchical graph. The subgraph may be a two-level graph comprising the nodes of the hierarchical graph at the particular level being considered.
In an embodiment of the present invention, after an initial partition is made, a gain matrix is created for each potential move of each cell. Values of these gain matrices are calculated and compared. A best move cell may be selected and moved based on the values. The cell that was moved may then be locked and the process repeated for the remaining unlocked cells.
In an embodiment of the present invention, the gain matrices are compared by calculating a value for each gain matrix. The value may be a sum of all entries in the gain matrix. Alternatively, the gain matrix may be multiplied by a weight matrix and then summed.
A further understanding of the nature and advantages of the inventions presented herein may be realized by reference to the remaining portions of the specification and the attached drawings.


REFERENCES:
patent: 4617479 (1986-10-01), Hartmann et al.
patent: 4791590 (1988-12-01), Ku et al.
patent: 4871930 (1989-10-01), Wong et al.
patent: 4903107 (1990-02-01), Chan et al.
patent: 4918379 (1990-04-01), Jongepier
patent: 5031111 (1991-07-01), Chao et al.
patent: 5128871 (1992-07-01), Schmitz
patent: 5187671 (1993-02-01), Cobb
patent: 5218551 (1993-06-01), Agrawal et al.
patent: 5224056 (1993-06-01), Chene et al.
patent: 5229953 (1993-07-01), Isozaki et al.
patent: 5241224 (1993-08-01), Pedersen et al.
patent: 5260611 (1993-11-01), Cliff et al.
patent: 5305229 (1994-04-01), Dhar
patent: 5309371 (1994-05-01), Shikata et al.
patent: 5311443 (1994-05-01), Crain et al.
patent: 5341308 (1994-08-01), Mendel
patent: 5359538 (1994-10-01), Hui et al.
patent: 5392227 (1995-02-01), Hiserote
patent: 5469003 (1995-11-01), Kean et al.
patent: 5475830 (1995-12-01), Chen et al.
patent: 5477474 (1995-12-01), Southgate et al.
patent: 5485396 (1996-01-01), Brasen et al.
patent: 5485547 (1996-01-01), Maruno
patent: 5495419 (1996-02-01), Rostoker et al.
patent: 5508939 (1996-04-01), Kim et al.
patent: 5513124 (1996-04-01), Trimberger et al.
patent: 5519629 (1996-05-01), Snider
patent: 5521836 (1996-05-01), Hartoog et al.
patent: 5557533 (1996-09-01), Koford et al.
patent: 5574893 (1996-11-01), Southgate et al.
patent: 5696503 (1997-

Affiliated with

Also associated with

Rating

Gain matrix for hierarchical circuit partitioning does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Gain matrix for hierarchical circuit partitioning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Gain matrix for hierarchical circuit partitioning will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2540547