On wirelength estimations for row-based placement

ABSTRACT

Wirelength estimation in VLSI layout is fundamental to any pre-detailed routing estimate of timing or routability. In this paper, we develop new wirelength estimation techniques appropriate for top-down floor-planning and placement synthesis of row-based VLSI layouts. Our methods include accurate, linear-time approaches, often with sublinear time complexity for dynamic updating of estimates (e.g., for annealing placement). The new techniques offer advantages not only for early on-line wirelength estimation during top-down placement, but also for a posteriori estimation of routed wirelength given a final placement. In developing these new estimators, we have made several theoretical contributions. Notably, we have resolved the long-standing discrepancy between region-based and bounding box-based RSMT estimation techniques; this leads to new estimates that are functions of instance size n and aspect ratio AR.

REFERENCES

• 1: J. Beardwood, l H. Halton, and I. M. Hammersley. The shortest path through m~ny points. In Proceedings of the Cambridge PMiosophicd Society55, pages 299-327, 1959.
• 2: Chih-Liang Eric Cheng, RISA: accurate and efficient placement routability modeling, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.690-695, November 06-10, 1994, San Jose, California, United States
• 3: E R. K. Chnng and F. K. Hwang. The largest minimal rectilinear steiner trees for aset ofn points enclosed in a rectangle with given perimeter. Networks, 9(1):19--36, Spring 1979.
• 4: W. E,. Donath. Placement and average interconnection lengths of computer logic. IEF~ Transactions on Circuits and Systems, CAS-26(4):272-277, April 1979.
• 5: A.A. El Gamal. TWoMimensional stochastic model for interconnections in master slice integrated circuits./EEE Transactions on Cimtdts and Systems, CAS-28(2):127-138, February 1981.
• 6: M. Feu~ Connectivity of random logic. LEEE Transactions on Computers, (2-31 (1):29-33, January 1982.
• 7: J. Grifiith, G.Robins, J. S. Salowe, and T. Zhang. Closing the gap: Near-optimal steiner trees in polynomial time. IEEE Transactions on Computer-Aided Design of Integrated Circuits arm Systems, 13(11):1351-1365, November 1994.
• 8: T. Hamada , C.-K. Cheng , P. M. Chau, A wire length estimation technique utilizing neighborhood density equations, Proceedings of the 29th ACM/IEEE conference on Design automation, p.57-61, June 08-12, 1992, Anaheim, California, United States
• 9: W. Hebgen and G. Zimmelxnanm Hierarchical netlength estimation for timing prediction. In Proceedings of the ACM/SIGDA Physical Design Workshop, pages 118-125, 1996.
• 10: E K. Hwang. On steiner minimal trees with rectilinear distance. Siam Journal of Applied Mathematics, pages 104-114, January 1976.
• 11: Andrew B. Kahng , Sudhakar Muddu, Efficient Gate Delay Modeling for Large Interconnect Loads, Proceedings of the 1996 IEEE Multi-Chip Module Conference (MCMC '96), p.202, February 06-07, 1996
• 12: A. B. Katmg and G. Robins. On Optimal Interconnections for VLSI. Kluwer, 1994.
• 13: M. Pedram and B. Preas. Intercormection length estimation for optimized standard cell layouts. In Proceedings IEEE International Conf. on Computer-Aided Design, pages 390-393, 1989.
• 14: C. Sechen. Average interconneetion length estimation for random and optimized placements. In Proceedings IEEE International Conf. on Computer-Aided Design, pages 190-193, 1987.
• 15: Timothy Law Snyder , J. Michael Steele, A Priori Bounds on the Euclidean Traveling Salesman, SIAM Journal on Computing, v.24 n.3, p.665-671, June 1995 [doi>10.1137/S0097539792226771]
• 16: I. M. Steele. Growth rates of euclidean minimal spanning trees with power weighted edges. Annals of Probability, 16(4):1767- 1787, 1988.
• 17: J. Michael Steele , Timothy Law Snyder, Worst-case growth rates of some classical problems of combinatorial optimization, SIAM Journal on Computing, v.18 n.2, p.278-287, April 1989 [doi>10.1137/0218019]
• 18: D. Stroobandt. Improving Donath's technique for estimating the average interconnection length in computer logic. Technical report, Univ. Ghent ELIS Dept., June 1996.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing; Layout

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Design, Performance, Theory