Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2001-05-16
2003-03-11
Thomas, Tom (Department: 2811)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06532578
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the design of integrated circuits and, in particular, to configuring partitions for locating different circuit or other operational areas on an integrated circuit.
2. Description of Related Art
Design automation of complex VLSI (very large scale integrated) chips is typically associated with long design turnaround time, which, in turn, increases the time-to-market. Two reasons for this large turnaround time problem are slowness of the algorithms, caused by large problem sizes (e.g., hundreds of millions of circuits and nets on a chip); and large number of iterations between different algorithms required to converge to an acceptable solution. Current design tools are reaching their limits of efficiency and speed as the number of circuit components such as transistors, diodes, capacitors, resistors, and the like increase exponentially every year and the complexity of their connectivity increases in quadratic terms of the number of components.
A popular approach towards improving the speed of VLSI design-automation algorithms is partitioning. Partitioning helps the developers of the VLSI design-automation tools to optimize the design parameters within each partition locally. Typically, circuit netlists modeled as hypergraphs are partitioned using various heuristics that have been known to give good results, both in terms of runtime and quality of results.
In the geometric design of VLSI circuits, it is customary to represent circuit components such as terminals, connector corners and vias as a set of points in the X-Y plane. The point set representation of geometric circuits allows the tool developer to concentrate on the underlying geometric relationship among different components rather than their synthetic connectivity relationship as ordained by the circuit designers. One of the major critical issues in any type of partitioning scheme in the development of VLSI design-automation algorithm is the chip real estate. Since the number of components is very large, and the space they occupy is always at premium, it would be advantageous to minimize the total area of the partitions. Normally, there exists an upper bound on the number of such partitions that can be used to solve a particular problem since, as the number of partitions increases, the complexity of the algorithm(s) increases with it. The number of partitions may be determined by the designer on the basis of design constraints.
Bearing in mind the problems and deficiencies of the prior art, it is therefore an object of the present invention to provide an improved method and system for designing and configuring partitions on an integrated circuit or other substrate.
It is another object of the present invention to improve the speed of VLSI design-automation algorithms in partitioning integrated circuits.
A further object of the invention is to provide an improved method and system for creating integrated circuit partitions that minimizes the total area of the partitions.
It is yet another object of the present invention to provide a method of partition design automation which is especially useful for complex very large scale integrated circuit chips.
Still other objects and advantages of the invention will in part be obvious and will in part be apparent from the specification.
SUMMARY OF THE INVENTION
The above and other objects and advantages, which will be apparent to one of skill in the art, are achieved in the present invention which is directed to, in a first aspect, a method of configuring partitions for different circuit or other operational areas on an integrated circuit comprising initially identifying points representing components of an integrated circuit with respect to a coordinate system having a horizontal axis and a vertical axis, and subsequently creating a first isothetic rectangular partition containing all of the identified points of the integrated circuit. The isothetic rectangular partition has sides parallel to the horizontal axis and the vertical axis. The method then continues by subdividing the first isothetic rectangular partition with respect to the horizontal axis by creating a plurality of isothetic rectangular sub-partitions collectively containing all of the identified points of the integrated circuit. Each of the isothetic rectangular sub-partitions contain at least two points not aligned in parallel to the horizontal axis, and each of the isothetic rectangular sub-partitions is separated by a line parallel to the horizontal axis. These isothetic rectangular sub-partitions collectively encompass a minimum area containing all of the identified points. The method also includes subdividing the first isothetic rectangular partition with respect to the vertical axis by creating a plurality of isothetic rectangular sub-partitions collectively containing all of the identified points of the integrated circuit. Each of the isothetic rectangular sub-partitions contain at least two points not aligned in parallel to the vertical axis, and each of the isothetic rectangular sub-partitions is separated by a line parallel to the vertical axis. These isothetic rectangular sub-partitions collectively encompass a minimum area containing all of the identified points. The method then includes comparing the collective area of the isothetic rectangular sub-partitions subdivided with respect to the horizontal axis to the collective area of the isothetic rectangular sub-partitions subdivided with respect to the vertical axis, and determining which of the horizontally divided or vertically divided isothetic rectangular sub-partitions have the smaller area. Once this is accomplished, the method then includes configuring the operational area on the integrated circuit in conformance with the isothetic rectangular sub-partitions determined to have the smaller area.
Preferably, subdividing the first isothetic rectangular partition with respect to the horizontal or vertical axis is by creating a plurality of sets of two isothetic rectangular sub-partitions. The isothetic rectangular sub-partitions in each set is separated by a line parallel to either the horizontal axis or the vertical axis, respectively, and collectively contain all of the identified points of the integrated circuit. For each set, there is determined the total area of the isothetic rectangular sub-partitions in the set, and the set of isothetic rectangular sub-partitions having the smallest total area is selected.
The set of isothetic rectangular sub-partitions having the smallest total area may be selected with respect to the horizontal axis and a set of isothetic rectangular sub-partitions having the smallest total area may be selected with respect to the vertical axis, so that the selected sets are compared to determine which of the horizontally divided or vertically divided isothetic rectangular sub-partitions have the smaller area.
Preferably, the two isothetic rectangular sub-partitions created in each set do not intersect. The method may further include partitioning at least one of the isothetic rectangular sub-partitions in the set determined to have the smaller area by creating a plurality of subsets of two isothetic rectangular sub-partitions. The isothetic rectangular sub-partitions in each subset are separated by a line parallel to either the horizontal axis or the vertical axis and collectively contain all of the identified points of the isothetic rectangular sub-partition being further partitioned. The method then includes, for each subset, determining the total area of the isothetic rectangular sub-partitions in the subset, and selecting the subset of isothetic rectangular sub-partitions having the smallest total area.
The further partitioning may be continued on one or more isothetic rectangular sub-partitions until a desired number of isothetic rectangular sub-partitions having the smallest total area are selected. Preferably, only isothetic rectangular sub-partitions containing at least four identified points are partitioned.
The method step of subdi
Chakraborty Kanad
Mukherjee Maharaj
DeLio & Peterson LLC
International Business Machines - Corporation
Owens Douglas W.
Peterson Peter W.
Schnurmann H. Daniel
LandOfFree
Method of configuring integrated circuits using greedy... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of configuring integrated circuits using greedy..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of configuring integrated circuits using greedy... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3079911