Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-05-24
2002-02-12
Nelms, David (Department: 2818)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
36
Reexamination Certificate
active
06347393
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to integrated circuit design methods and in particular to a design method for buffer insertion within integrated circuits. Still more particularly, the present invention relates to a method for optimizing buffer selection using downstream &pgr;-models.
2. Description of Related Art
Scaling process technology into the deep submicron regime has made interconnect performance more dominant than transistor and logic performance. With the continued scaling of process technology, resistance per unit length of the interconnect continues to increase, capacitance per unit length remains roughly constant, and transistor or logic delay continues to decrease. This trend has led to the increasing dominance of interconnect delay over logic delay. Process technology options, such as use of copper wires, can only provide temporary relief. The trend of increasing interconnect dominance is expected to continue. Timing optimization techniques, such as wiresizing, buffer insertion, and sizing have gained widespread acceptance in deep submicron design (see Cong et al. J. Cong, L. He, C.-K. Koh, and P. H. Madden, “Performance Optimization of VLSI Interconnect Layout”, Integration: the
VLSI Journal,
21, 1996, pp. 1-94. In particular, buffer insertion techniques can significantly reduce interconnect delay. To the first order, interconnect delay is proportional to the square of the length of the wire. Inserting buffers effectively divides the wire into smaller segments, which makes the interconnect delay almost linear in terms of its length, though buffer delays must now be considered. Buffers can also be used to fix slew, capacitance, and noise violations while reducing power, resulting in automated buffer insertion becoming increasingly pervasive as the ratio of device to interconnect delay continues to decrease.
Buffer insertion has been an active area of study in recent years. Closed formed solutions have been proposed by Adler and Friedman, “Repeater Design to Reduce Delay and Power in Resistive Interconnect”,
IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing,
Vol. CAS II-45, No. 5, pp. 607-616, May 1998; Alpert and Devgan, “Wire Segmenting For Improved Buffer Insertion”, 34th
IEEE/ACM Design Automation Conference,
1997, pp. 588-593; and Dhar and Franklin, “Optimum Buffer Circuits for Driving Long Uniform Lines”,
IEEE Journal of Solid
-
State Circuits,
26(1), 1991, pp. 32-40, all of which consider inserting buffers on a 2-pin net. Chu and Wong, “Closed Form Solution to Simultaneous Buffer Insertion/Sizing and Wire Sizing”,
International Symposium on Physical Design,
1997, pp. 192-197, proposed a closed form solution to simultaneous wiresizing and buffer insertion. The works of Culetu et al., “A Practical Repeater Insertion Method in High Speed VLSI Circuits”, 35th
IEEE/ACM Design Automation Conference,
1998, pp. 392-395, Kannan et al., “A Methodology and Algorithms for Post-Placement Delay Optimization”, 31st
IEEE/ACM Design Automation Conference,
1994, pp. 327-332; and Lin and Marek-Sadowska, “A Fast and Efficient Algorithm for Determining Fanout Trees in Large Net-works”, Proc. of the
European Conference on Design Automation,
1991, pp. 539-544, teach inserting buffers on a tree by iteratively finding the best location for a single buffer. Approaches which simultaneously construct a routing tree and insert buffers have been proposed by Kang et al., “Delay Bounded Buffered Tree Construction for Timing Driven Floorplanning”,
IEEE/ACM Intl. Conf. Computer
-
Aided Design,
1997, pp. 707-712; Lillis et al., “Simultaneous Routing and Buffer Insertion for High Performance Interconnect”, Proc. 6
th
Great Lakes Symposium on Physical Design,
1996, pp 7-12; and Okamoto and Cong, “Interconnect Layout Optimization by Simultaneous Steiner Tree Construction and Buffer Insertion”,
Fifth ACM/SIGDA Physical Design Workshop,
1996, pp. 1-6. Chu and Wong, “A New Approach to Simultaneous Buffer Insertion and Wire Sizing”,
IEEE/ ACM International Conference on Computer
-
Aided Design,
1997, pp. 614-621, present an iterative optimization which simultaneously performs wiresizing and buffer insertion on a 2-pin net.
In 1990, Van Ginneken, “Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay”,
Proc. International Symposium on Circuits and Systems,
1990, pp. 865-868, proposed a dynamic programming algorithm which finds the optimal solution using the Elmore wire delay model and a linear gate delay model. The algorithm only permits a single, non-inverting buffer type to be considered. Several extensions and variants have been proposed to this fundamental approach, Alpert and Devgan, “Wire Segmenting For Improved Buffer Insertion”, 34th
IEEE/ACM Design Automation Conference,
1997, pp. 588-593; Alpert, Devgan and Quay, “Buffer Insertion for Noise and Delay Optimization”, 35th
IEEE/ACM Design Automation Conference,
1998, pp. 362-367; Lillis, “Timing Optimization for Multi-Source Nets: Characterization and Optimal Repeater Insertion”, 34th
IEEE/ACM Design Automation Conference,
1997, pp. 214-219; Lillis et al., “Optimal Wire Sizing and Buffer Insertion for Low Power and a Generalized Delay Model”,
IEEE Journal of Solid
-
State Circuits,
31(3), 1996, pp. 437-447; Lillis et al., “Simultaneous Routing and Buffer Insertion for High Performance Interconnect”,
Proc.
6
th
Great Lakes Symposium on Physical Design,
1996, pp 7-12; and Okamoto and Cong, “Interconnect Layout Optimization by Simultaneous Steiner Tree Construction and Buffer Insertion”,
Fifth ACM/SIGDA Physical Design Workshop,
1996, pp. 1-6. Lillis et al., “Optimal Wire Sizing and Buffer Insertion for Low Power and a Generalized Delay Model”,
IEEE Journal of Solid
-
State Circuits,
31(3), 1996, pp. 437-447, extended Van Ginneken's algorithm to simultaneously perform wiresizing and buffer insertion with a buffer library that contains both inverting and non-inverting buffers. In addition, Lillis et al. show, in “Optimal Wire Sizing and Buffer Insertion for Low Power and a Generalized Delay Model”, how to control the total number of buffers inserted and how to integrate input slew into the gate delay function. Later, Lillis showed in “Timing Optimization for Multi-Source Nets: Characterization and Optimal Repeater Insertion”, how to modify Van Ginneken's algorithm to handle nets with multiple sources. Alpert and Devgan proposed in “Wire Segmenting For Improved Buffer Insertion” a wire segmenting pre-processing algorithm to handle the one-buffer-per-wire limitation of Van Ginneken's algorithm, which results in a smooth trade-off between solution quality and run time. Alpert et al. showed in “Buffer Insertion for Noise and Delay Optimization”, how to simultaneously modify the algorithm to avoid coupling noise while only suffering a slight delay penalty.
All of the variants to Van Ginneken's algorithm and most other works in buffer insertion (with the exceptions of V. Adler and E. G. Friedman, “Repeater Design to Reduce Delay and Power in Resistive Interconnect”, and S. Dhar and M. A. Franklin, “Optimum Buffer Circuits for Driving Long Uniform Lines”), use both simplified gate and wire delay models. The Elmore delay model can significantly overestimate interconnect delay, as it incorporates only the first moment of the impulse response. Similarly, using lumped capacitance instead of effective capacitance can overestimate delay by ignoring resistive shielding, as described in Qian, Pullela, and Pillage, “Modeling the “Effective Capacitance” for the RC Interconnect of CMOS Gates”,
IEEE Trans. Computer
-
Aided Design,
13(12), 1994, pp. 1526-1535. As the driver resistance becomes comparable to the resistance of the interconnect it drives, some of the downstream capacitance becomes shielded from the gate. In effect, the driver is not driving the entire downstream lumped capacitance but rather an effective capacitance that is less than the total lumped capacitance. It has been empiric
Alpert Charles Jay
Devgan Anirudh
Quay Stephen Thomas
Le Thong
Nelms David
Salys Casimer K.
Yee Duke W.
LandOfFree
Method and apparatus for performing buffer insertion with... 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 and apparatus for performing buffer insertion with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing buffer insertion with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2943162