Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2001-04-11
2002-09-17
Wong, Don (Department: 2821)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06453453
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to solving linear assignment problems often arising for combinational layout problems in integrated circuit design, such as routing and pin and buffer assignment.
BACKGROUND OF THE INVENTION
Linear assignment problems are employed to solve and optimize combinational layout problems for integrated circuit design. For example, combinational channel routing layouts, pin positioning and buffer assignments are often treated as linear assignment problems of placing objects in an ordered system of boxes. Assignment problems are used to locate, in an undirected graph G, a match M that is a subset of an edge E, M
E, such that no vertex is incident to more than one edge. The linear assignment problem assumes that graph G is complete with edge weights, and seeks a perfect match of minimum weight. The match is called “perfect” if each vertex is incident to exactly one edge.
Integrated circuit design often poses problems of assigning objects to boxes with minimal penalties where the number of object/box combinations exceeds 10
6
. Classical linear assignment problems are ineffective where the number of objects and boxes of the problem reach 10
4
to 10
6
or more. Consequently, it was common to reduce the problem to more manageable pieces and solve each piece individually. The solved pieces were re-assembled, and adjustments were made to the solution. However, the reduction and re-assembly processes were difficult, and often introduced unexpected cost functions to the solution. There is, accordingly, a need for a more effective solution to linear assignment problems that can handle large numbers of combinational assignments, such as for use in integrated circuit layout design.
SUMMARY OF THE INVENTION
The present invention provides an effective solution of the linear assignment problem for an ordered system of boxes with linear topology and with unimodal penalty functions for objects.
The present invention provides a process for optimizing a layout of objects in an ordered system of boxes with minimal penalty from a collection of boxes containing the objects. A hierarchy is created containing a top level, a bottom level and one or more intermediate levels. The bottom level contains at least as many generalized boxes as original boxes in the assignment problem. The top and intermediate levels each contains an integer number
n
2
or
n
+
1
2
generalized boxes where n is the integer number of generalized boxes in the next lower level. The top level contains one generalized box. All objects of the assignment problem are placed in the generalized box of the top level. A first local task is executed to transition the contents of a generalized box of a higher level to at least two generalized boxes of the next lower level. A second local task is executed to the contents of a plurality of generalized boxes of lower level to minimize a global penalty function. Thereafter, the first and second tasks are executed through successive iterations until all of the objects are placed in the boxes of the bottom level in a layout having minimal penalty function.
In one form, the invention is manifest in a computer readable program containing code that, when executed by a computer, causes the computer to perform the process steps to layout the objects.
REFERENCES:
patent: 5933356 (1999-08-01), Rostoker et al.
patent: 6321370 (2001-11-01), Suzuki et al.
patent: 6378109 (2002-04-01), Young et al.
Andreev Alexander E.
Bolotov Anatoli A.
Raspopovic Pedja
LSI Logic Corporation
Vu Jimmy T
Westman Champlin & Kelly
Wong Don
LandOfFree
Process for solving assignment problems in integrated... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Process for solving assignment problems in integrated..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Process for solving assignment problems in integrated... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2875327