Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2001-03-28
2002-11-26
Lam, Tuan T. (Department: 2816)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06487697
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates generally to the computer aided design of integrated circuits. More specifically, the invention relates to methods and apparatus automating the insertion of buffers during the design phase of an integrated circuit.
2. Description of the Related Art
Integrated circuits comprise a large number of circuit elements, mainly transistors, interconnected by a large number of wires. Some of the transistors (“drivers”) drive other circuit elements (“driven elements”). The number of drivedriven elements coupled to the output of a driver is known as the fanout of the driver.
The “ramptime” of the driven elements coupled to a driver depends on the amount of capacitance and resistance “seen” by that driver, which in turn depends on the number of driven elements connected to the output of that driver and the length of the wires that interconnect the driver with its driven elements. If a driver's load exceeds a certain threshold, the ramptime for its driven elements will also exceed a corresponding threshold, and the circuit will not function properly. To avoid this problem, during the design phase of an integrated circuit, additional drivers known as buffers are selectively inserted between drivers and driven elements.
Since each added buffer increases power consumption, it is generally desirable to minimize the number of buffers that are added. Also, since each buffer adds its own delay, it is generally desirable to minimize the number of levels of added buffers, where a single level of buffers is a set of buffers that drive other buffers or the design's driven elements. (E.g. a buffer driving a buffer that drives a number of original driven elements corresponds to two levels of buffers.) It is also desirable to insert buffers in such a way as to minimize the overall interconnect length. Currently, buffer insertion is often performed manually; given the large number of possible buffer insertion points and the complexity of the above mentioned design goals, it is desirable to automate the location of buffer insertion points.
One proposed automated method for selecting buffer insertion points involves finding a best “path” through a directed graph. A Fast Algorithm for Context-Aware Buffer Insertion, Jagannathan, Hur and Lillis, Design Automation Conference '2000, pp. 368-373; Routing Tree Construction Under Fixed Buffer Locations, Cong and Yuan, Design Automation Conference '2000, pp. 379-384. More particularly, a directed graph is created with a source (the original driver within a circuit), sinks (driven elements) and nodes in the graph representing possible buffer insertion points between the sources and sinks. Typically, the possible buffer insertion points are chosen randomly, subject to the floorplanning constraints of the integrated circuit (i.e. buffers can only be inserted within certain portions of the circuit). Edges connect “neighboring nodes”; two nodes are considered to be neighbors if the corresponding buffers (would) lie within a threshold distance that is process dependent.
The resulting graph has a large number of possible paths from the source to any sink, where each path represents a possible set of buffer insertions points and corresponding connections therebetween. Various methods are employed (Id.) to find a best path; the nodes in this best path are then the chosen buffer insertion points.
However, it is not clear how effectively the directed graph method would function for high fanout nets (e.g. nets with thousands or tens of thousands of fanouts). In particular, the computation time required to implement directed graph algorithms for high fanout nets may be unacceptably long. Further, it is no clear how well directed graph methods would achieve the previously mentioned design goals for buffer insertion methods.
In sum, there is a need for a method and apparatus that can efficiently locate buffer insertion points for high fanout nets while at least reasonably satisfying buffer insertion design goals.
SUMMARY OF THE INVENTION
To achieve the foregoing, the present invention is a method and apparatus for decreasing the ramptime of a high fanout net in an integrated circuit. The preferred method is applied after the elements comprising the circuit have been laid out but not yet connected together (i.e. the circuit has been “placed” but not yet “routed”.)
According to an implementation of the present invention, it is determined whether a net has a ramptime violation. If so, all of the driven elements are clustered in such a manner that the total load (capacitance) of the driver decreases. The preferred clustering method minimizes the number of inserted buffers, the total interconnect length, and the number of levels of the inserted buffer tree. After clustering, one level of buffers is inserted into the net. More particularly, one buffer is inserted for each cluster created in the previously mentioned step; each of the inserted buffers drives its corresponding cluster. The buffers that are inserted will not have any ramptime violation. Therefore, each insertion of a level of buffers reduces the overall ramptime of the net.
After insertion of a level of buffers, the ramptime of the net is checked once again. If it is still not acceptable, the aforementioned clustering and insertion are repeated and the above cycle is iterated until there is no ramptime violation. During the first iteration of clustering and buffer insertion, the original circuit elements are clustered. After the first iteration of clustering and buffer insertion, the driven elements that are clustered are the buffers that were inserted in the previous iteration. In this manner, levels of buffers may be inserted into the net.
The preferred clustering method is based upon the concept of a “bounding box.” For any given net, a bounding box is determined according to the location of the net's driver and the distribution of all that driver's driven elements. A bounding box corresponds to a rectangular region within the integrated circuit in which a driver and all of its associated driven elements reside. The outer boundaries of a bounding box are defined based on the maximum x and y coordinates as well as the minimum x and y coordinates of all pins, that are not already directly driven by a buffer, connected to the net being considered (driver and all driven elements). The driven elements furthest away from the driver define the outer boundaries of the bounding box.
A bounding box, and therefore the net that it represents, may be partitioned into a plurality of regions, where once again each region corresponds to a physical region on the integrated circuit. The bounding box that contains the entire net is partitioned into four rectangular regions that all meet at the net's driver while all other bounding boxes, which result from subsequent partitions, are partitioned from their centers into four equal sized rectangular regions. The original bounding box (region) is a “parent” region while the regions resulting from the partition are the “children” of that parent. Each of the children regions may be partitioned, and so on, creating a number of levels of regions.
To perform the preferred clustering method, the bounding box of a net is determined. The bounding box is partitioned, preferably into four equal sized rectangular regions, as previously described. One of the children regions is selected and the number of driven elements therein (ND) is checked against the maximum number of allowable fanouts (MF). MF is dictated by the design rules for any particular process technology. The first time that elements are clustered, the driven elements are the original circuit elements on the integrated circuit. For each subsequent clustering, the driven elements are the buffers that were inserted during the most recent clustering.
If the number of driven elements of the selected child region (ND) is greater than the maximum number of allowable fanouts (MF), the child is partitioned iteratively until a region is fou
Lu Aiguo
Pavisic Ivan
Zolotykh Andrej A.
Cox Cassandra
Lam Tuan T.
LSI Logic Corporation
Westman Champlin & Kelly
LandOfFree
Distribution dependent clustering in buffer insertion of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distribution dependent clustering in buffer insertion of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distribution dependent clustering in buffer insertion of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2985261