Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2002-05-07
2004-11-30
Thompson, A. M. (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06826740
ABSTRACT:
FIELD OF THE INVENTION
The invention is generally related to integrated circuits and integrated circuit design, and in particular to automated buffer insertion during physical design of integrated circuits.
BACKGROUND OF THE INVENTION
Electronic integrated circuits, or “chips” have become significantly more complex as circuit fabrication technologies have improved. It is not uncommon for integrated circuits to incorporate hundreds of millions of transistors, with a comparable number of interconnects, or signal paths, integrated together onto a single piece of silicon substrate no larger than the size of a coin. In addition, often the same functionality that once required multiple chips can now be integrated onto the same chip, a concept often referred to as “system-on-chip” technology.
The design of integrated circuits has likewise become more difficult as complexity has increased. Whereas early chips were often designed gate by gate, more advanced integrated circuits incorporating millions of gates represent too much of an undertaking for early design methodologies. Likewise, another important aspect of integrated circuit design is that of testing and verifying an integrated circuit design, both from the standpoint of verifying that a design will logically operate as intended, and of ensuring that a design will comply with the physical limitations that are inherent in any integrated circuit, i.e., to ensure that all timing and delay constraints are met.
As a result, a variety of software design applications, or tools, have been developed to assist designers with designing and testing integrated circuits.
Generally when utilizing these tools, the overall design process is represented by two stages. The first stage is referred to as logic design, where the desired functional operation of an integrated circuit is initially defined and tested. The second stage is referred to as physical design, where the logic design created during the logic design stage is processed to select actual circuit components to implement the functions defined in the logic design, and to lay out the components on an integrated circuit and route interconnects therebetween. The interconnections between circuit elements are often referred to as nets, and the nets are generally routed afer placement of circuit components at specific locations on an integrated circuit.
One important parameter that must be accounted for during the design of an integrated circuit is that of timing. In particular, due to factors such as resistance, capacitance, switching delays, etc., signals that are propagated through an integrated circuit require some finite amount of time to reach various destinations. In any given integrated circuit design, however, often signals must reach destinations within a certain time frame (typically before the end of a clock cycle), lest data be missed due its late arrival at a destination. Timing particularly becomes troublesome for relatively long interconnects, as the inherent resistance and capacitance of such interconnects may delay the arrival of a signal on a long interconnect beyond that which is acceptable under the normal operating conditions for an integrated circuit.
Timing is often accounted for in both the logic and physical design stages of an integrated circuit. However, during the logic design stage, timing parameters for the various nets in a design are typically estimated using formulas, and these estimates are often not particularly accurate. Timing analysis is also performed during the physical design stage, and a developer may be required to refine a design after timing analysis if it is determined during the physical design stage that timing parameters are not acceptable.
Given the rather gross estimates made during the logic design stage, it is not uncommon for an integrated circuit design to meet timing constraints in the logic design stage, but not meet the timing constraints after layout and routing during the physical design stage. As a result, various types of post-layout optimization algorithms are often utilized to address many of these timing problems in an automated manner. By doing so, a designer may not be required to return to the logic design stage for manual refinements of a design, which can substantially simplify the design process.
One such type of post-layout optimization is automated buffer insertion. In particular, the addition of one or more inverting or non-inverting buffers into a relatively long interconnect in an integrated circuit design will typically improve the timing parameters for that interconnect due to reduced load, reduced delay, and reduced slew, and often without altering the overall length of an interconnect. Thus, by the selective addition of buffers to a design, often previously non-compliant designs can be optimized in an automated manner to bring those designs into compliance with timing constraints.
Most conventional automated buffer insertion algorithms place buffers using a pre-existing routing tree. A routing tree is typically created for each “net” in a design, i.e., for each interconnect between a signal source and one or more signal sinks. In many instances, each routing tree is configured as a Steiner tree, which attempts to generate the shortest orthogonal path or “route” between any source and its sinks. Additional points, known as Steiner points, are typically added to routes so that, between any non-orthogonal nodes along a route, interconnect segments are routed in a vertical-horizontal or horizontal-vertical manner, thus creating one or more L-shaped spans between a source and its sinks.
One problem associated with many conventional automated buffer insertion algorithms, however, typically arises when a relatively large number of similar nets need to be routed, with all of the sources for those nets disposed in one small region and all of the sinks for those nets disposed in another small region, e.g., for a bus or similar multi-signal interface. In such an instance, where all of the Steiner routes are similar, the locations for the buffers added by a conventional automated buffering insertion process will typically be located in approximately the same locations. Then, once the buffers are placed, the subsequent routing of interconnects is substantially constrained, causing difficulties associated with routing a large number of interconnects through the same general region of an integrated circuit.
Put another way, without the buffers, a router is free to select any orthogonal path to traverse from each source to each corresponding sink. Moreover, as tracks fill, the router can use different equivalent routes. However, after buffers are inserted, the router is forced to follow nearly the same path for all nets, since it must work its way through the buffers. As a result, the placement of the buffers essentially defines the routes. Consequently, substantial congestion may arise in particular regions of an integrated circuit design due to the placement of buffers in close proximity to one another. Conventional automated buffer insertion algorithms have thus been found to cause significant congestion in many integrated circuit designs in the instances where a number of relatively long interconnects are required to be routed between roughly the same regions on an integrated circuit design.
Therefore, a significant need exists in the art for a manner of relieving congestion in an integrated circuit design caused by the placement of buffers as a result of automated buffer insertion performed during post-layout optimization of an integrated circuit design.
SUMMARY OF THE INVENTION
The invention addresses these and other problems associated with the prior art by providing an apparatus, program product and method in which a congestion relief algorithm is used in connection with automated buffer insertion to relieve potential congestion during post-layout optimization of an integrated circuit design. The congestion relief algorithm is utilized to manipulate a plurality of L-shaped spans defined in a routing tree, and is configu
Dimyan Magid Y.
International Business Machines - Corporation
Thompson A. M.
Wood Herron & Evans LLP
LandOfFree
Automated buffer insertion incorporating congestion relief... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Automated buffer insertion incorporating congestion relief..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automated buffer insertion incorporating congestion relief... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3289211