Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2001-03-15
2003-07-08
Wong, Don (Department: 2821)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06591411
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention is directed to an apparatus and method for determining buffered Steiner trees for complex circuits.
2. Description of Related Art
It is now widely accepted that interconnect performance is becoming increasingly dominant over transistor and logic performance in the deep submicron regime. Buffer insertion is now a fundamental technology used in modern VLSI design methodologies. As gate delays decrease with increasing chip dimensions, however, the number of buffers required quickly rises. It is expected that close to 800,000 buffers will be required for 50 nanometer technologies. It is critical to automate the entire interconnect optimization process to efficiently achieve timing closure.
The problem of inserting buffers to reduce the delay on signal nets has been recognized and studied. A closed form solutions for two-pin nets have been proposed by van Ginneken. Van Ginneken's dynamic programming algorithm, described in “Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay,” Int'l Symposium on Circuits and Systems, 1990, pp. 865-868, which is hereby incorporated by reference, has become a classic in the field. Given a fixed Steiner tree topology, the van Ginneken algorithm finds the optimal buffer placement on the topology under an Elmore delay model for a single buffer type and simple gate delay model. Several extensions to this work have been proposed. Together, these enhancements make the van Ginneken style of buffer insertion quite potent as it can handle many constraints, buffer types, and delay models, while retaining optimality under many of these conditions. Most recently, research on buffer insertion has focused on accommodating various types of blockage constraints.
The primary shortcoming with the van Ginneken style of buffer insertion is that it is limited by the given Steiner topology. Thus, buffer insertion has been combined with Steiner tree constructions using a two-step approach of first constructing a Steiner tree, then running van Ginneken style buffer insertion. An optimal solution can be realized using the two-step approach if one uses the “right” Steiner tree (i.e., the tree resulting from ripping buffers out of the optimal solution) since the buffer insertion step is optimal. Of course, finding the right tree is difficult since the buffer insertion objective cannot be directly optimized.
The problem of obtaining the “right” Steiner tree becomes even more difficult as the complexity of the circuit design increases. Thus, it would be beneficial to have an apparatus and method of identifying an optimal Steiner tree for complex circuit designs.
SUMMARY OF THE INVENTION
The present invention provides an apparatus and method for determining buffered Steiner trees for complex circuits. The apparatus and method first clusters sinks with similar characteristics such as criticality, polarity and distance. The purpose of this step is to potentially isolate positive sinks from negative ones and non-critical sinks from critical ones. The present invention then constructs low-level Steiner trees over each of these clusters. Finally, a top-level timing driven Steiner tree is computed where each cluster is treated as a sink. The top-level tree is then merged with the low-level trees to yield a solution for the entire net.
REFERENCES:
patent: 2001/0009031 (2001-07-01), Nitta et al.
patent: 2001/0010090 (2001-07-01), Boyle et al.
Lukas P.P.P. Van Ginneken, Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay, 1990, ISCAS, vol. 2, pp. 865-868, New Orleans, LA, May 1-3.
Alpert Charles Jay
Gandham Rama Gopal
Hu Jiang
Quay Stephen Thomas
Sullivan Andrew James
International Business Machines - Corporation
Salys Casimer K.
Tran Thuy Vinh
Walder, Jr. Stephen J.
Wong Don
LandOfFree
Apparatus and method for determining buffered steiner trees... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for determining buffered steiner trees..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for determining buffered steiner trees... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3102031