Revisiting fidelity: a case of elmore-based Y-routing trees

ABSTRACT

The dominance of interconnect delay in VLSI circuit design is well-known. Construction of routing trees in recent times has to take care of the timing issues for faster design convergence. Thus there is immense scope of research in design and performance of interconnects. Our current work encompasses two aspects of this research. On one hand, we consider the construction of cost-effective global routing trees with the recently introduced Y-interconnects, and on the other hand, we utilize this framework for verifying the supremacy of the Elmore delay estimate for its high fidelity. In order to ensure accurate computation of fidelity, (i) we propose new statistically proven formulae for fidelity, and (ii) compute the fidelity values based on delay estimates for optimal and near-optimal trees. Our experiments on several randomly generated problem instances and benchmarks confirm once again the supremacy of fidelity of Elmore delay over that of linear delay.

REFERENCES

• 1: X Initiative Homepage. http://www.xinitiative.org/, 2003.
• 2: Arif Ishaq Abou-Seido , Brian Nowak , Chris Chu, Fitted Elmore delay: a simple and accurate interconnect delay model, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.7, p.691-696, July 2004 [doi>10.1109/TVLSI.2004.830932]
• 3: Karl V Bury. Statistical Models in Applied Science. J. Wiley & Sons, Inc., 1989.
• 4: Jason Cong , Lei He, Optimal wiresizing for interconnects with multiple sources, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.4, p.478-511, Oct. 1996 [doi>10.1145/238997.239018]
• 5: Chris S. Coulston, Constructing exact octagonal steiner minimal trees, Proceedings of the 13th ACM Great Lakes symposium on VLSI, April 28-29, 2003, Washington, D. C., USA [doi>10.1145/764808.764810]
• 6: Parthasarathi Dasgupta, Revisiting VLSI Interconnects in Deep Sub-Micron: Some Open Questions, Proceedings of the 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design, p.615-620, January 03-07, 2005 [doi>10.1109/ICVD.2005.149]
• 7: M. D. Rostoker et al. Hexagonal architecture. U.S. Patent, No. US6407434B1, June 2002.
• 8: Joseph L. Ganley, Accuracy and fidelity of fast net length estimates, Integration, the VLSI Journal, v.23 n.2, p.151-155, Nov. 1997 [doi>10.1016/S0167-9260(97)00019-9]
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: A. B. Kahng I. Mandoiu Q. Wang H. Chen, Chung-Kuan Cheng and Bo Yao. The y-architecture for on-chip interconnect: Analysis and methodology. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005.
• 11: Hongyu Chen , Bo Yao , Feng Zhou , Chung-Kuan Cheng, The Y-architecture: yet another on-chip interconnect solution, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119957]
• 12: M Hanan. On steiner's problem with rectilinear distance. SIAM Journal of Applied Mathematics, 14(2):255--265, 1966.
• 13: Jason Cong , Lei He , Cheng-Kok Koh , Patrick H. Madden, Performance optimization of VLSI interconnect layout, Integration, the VLSI Journal, v.21 n.1-2, p.1-94, Nov. 1996 [doi>10.1016/S0167-9260(96)00008-9]
• 14: P. Penfield J. Rubinstein and M. A. Horowitz. Signal delay in rc tree networks. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2(3):202--211, July 1983.
• 15: B A McCoy K D Boese, A B Kahng and G Robins. Fidelity and near-optimality of elmore-based routing constructions. In Proceedings of the IEEE International Conference on Computer Design, pages 81--84, October 1993.
• 16: Andrew B. Kahng , Bao Liu, Q-Tree: A New Iterative Improvement Approach for Buffered Interconnect Optimization, Proceedings of the IEEE Computer Society Annual Symposium on VLSI (ISVLSI'03), p.183, February 20-21, 2003
• 17: Bernard A. McCoy Kenneth D. Boese, Andrew B. Kahng and Gabriel Robins. Near - optimal critical sink routing tree constructions. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 14(12):1417--1436, December 1995.
• 18: S. Kotz and N L Johnson. Encyclopedia of Statistical Sciences. J. Wiley & Sons, Inc., 1981.
• 19: D. T. Lee , C. F. Shen, The Steiner Minimal Tree Problem in the lambda-Geormetry Plane, Proceedings of the 7th International Symposium on Algorithms and Computation, p.247-255, December 16-18, 1996
• 20: E Lodi. Routing multiterminal nets in a diagonal model. In Proceedings of the Conference on Information Sciences and Systems, pages 899--902. Dept of EE, Princeton University, 1988.
• 21: J. F. Weng M. Brazil, D. A. Thomas and M. Zachariasen. Canonical forms and algorithms for steiner trees in uniform orientation metrics. Algorithmica, Technical Report, pages 2--22, 2002.
• 22: James Meindl. Tyranny of interconnects. In Proceedings of the International Symp. on Physical Design, pages 18--21, April 2004.
• 23: M.G.Kendall. Rank correlation methods. Charles Griffin, London, 1970.
• 24: T. Jing X-L Hong Q. Zhu, H. Zhou and Y. Yang. Spanning graph-based nonrectilinear steiner tree algorithms. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 24(7):1066--1074, 2005.
• 25: H. Rahaman T. Samanta, P. Ghosal and P. Dasgupta. A heuristic method for constructing hexagonal steiner minimal trees for routing in vlsi. In Proceedings of the International Symposium on Circuits & Systems, pages 1788--1791, 2006.
• 26: Steven L. Teig, The X architecture: not your father's diagonal wiring, Proceedings of the 2002 international workshop on System-level interconnect prediction, April 06-07, 2002, San Diego, California, USA [doi>10.1145/505348.505355]
• 27: A. Thurber and G. Xue. Computing hexagonal steiner trees using pcs. In IEEE International Conference on Electronics, Circuits & Systems, pages 381--384, 1999.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.0 General

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms
  G.3 PROBABILITY AND STATISTICS
      Subjects: Nonparametric statistics

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
Steiner trees, fidelity, rank correlation, routing