Wire-length prediction using statistical techniques

ABSTRACT

We address the classic wire-length estimation problem and propose a new statistical wire-length estimation approach that captures the probability distribution function of net lengths after placement and before routing. The wire-length prediction model was developed using a combination of parametric and non-parametric statistical techniques. The model predicts not only the length of the net using input parameters extracted from the floorplan of a design, but also probability distributions that a net with given characteristics obtained after placement will have a particular length. The model is validated using both learn-and-test and resubstitution techniques. The model can be used for a variety of purposes, including the generation of a large number of statistically sound and therefore realistic instances of designs. We applied the net models to the probabilistic buffer insertion problem and obtained substantial improvement in net delay after routing.

REFERENCES

• 1: Charles Alpert , Anirudh Devgan, Wire segmenting for improved buffer insertion, Proceedings of the 34th annual conference on Design automation, p.588-593, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266291]
• 2: [2] L. Breiman, et al. Classification and Regression Trees. Chapman and Hall, 1984.
• 3: [3] B. Efron and R. Tibshirani. An introduction to the bootstrap. Chapman & Hall, 1993.
• 4: [4] W. C. Elmore. The transient analysis of damped linear networks with particular regard to wideband amplifiers. In Journal of Applied Physics, volume 19 of 1,1948.
• 5: Vishal Khandelwal , Azadeh Davoodi , Akash Nanavati , Ankur Srivastava, A Probabilistic Approach to Buffer Insertion, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.560, November 09-13, 2003 [doi>10.1109/ICCAD.2003.16]
• 6: [6] J. L. Wong, et al. Wire-length prediction using statistical and probabilistic techniques. UCLA Technical Report #040027, pages 1-8, July 2004.
• 7: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 8: [8] L. P. P. P. van Ginneken. Buffer placement in distributed rc-tree networks for minimal elmore delay. In Int'l Symposium on Circuits and Systems, pages 865-868, December 1990.