A priori prediction of tightly clustered connections based on heuristic classification trees

ABSTRACT

In this paper we describe a methodology to predict the tightly clustered (shorter) connections in the final optimal placement of an arbitrary netlist. This new methodology is based on classifying the connections in the netlist into several groups based on their topological characteristics. The most important characteristic that helps in this classification of connections is the presence of multiple paths between two nodes in a netlist. We show that this new methodology consistently results in identifying shorter connections much better than previous models and is independent of the placement approach used. In fact, on average, the cumulative length of the identified shorter connections is 36% (with Simulated Annealing), 33% (with Capo8.8) and 33% (with Dragon) less than those identified by a current mutual contraction model [10]. The model on average identifies 27% more connections than the minimum required for coarsening the netlist and reducing its size in half.

REFERENCES

• 1: W. E. Donath, "Placement and average interconnection lengths of computer logic," in IEEE Transactions on Circuits and Systems, vol. CAS-26, pp. 272--277, April 1979.
• 2: W. E. Donath, "Wire length distributions for placements of computer logic," in IBM Journal Research and Development, vol. 25, pp. 152--155, May 1981.
• 3: M. Pedram and B. Preas, "Interconnection length estimation for optimized standard cell layouts," in Proceedings of International Conference on Computer-Aided Design, 1989, pp. 390--393.
• 4: H. T. Heineken and W. Maly, "Standard cell interconnect length prediction from structural circuit attributes," in Proceedings of Custom Integrated Circuits Conference, 1996, pp. 167--170.
• 5: A. E. Caldwell, A. B. Kahng, S. Mantik, I. L. Markov and A. Zelikovsky, "On wire length estimations for row-based placement," in IEEE Transactions on Computer-Aided Design, vol. 18, pp. 1265--1278, September 1999.
• 6: A. Alvandpour, P. Larsson-Edefors and C. Svensson, "GLMC: Interconnect length estimation by growth-limited multifold clustering," in Proceedings of IEEE International Symposium on Circuits and Systems, 2000, pp. 465--468.
• 7: Srinivas Bodapati , Farid N. Najm, Pre-layout estimation of individual wire lengths, Proceedings of the 2000 international workshop on System-level interconnect prediction, p.93-98, April 08-09, 2000, San Diego, California, United States [doi>10.1145/333032.333038]
• 8: J. A. Davis, V.K. De and J.D.Meindl, "A stochastic wire-length distribution for gigascale integration (GSI) -- Part I: Derivation and validation," in IEEE Transactionson Electronic Devices, vol. 45, pp. 580--589, March 1998.
• 9: D. Stroobandt and J. V. Campenhout, "Accurate interconnection length estimations for predictions early in the design cycle," in VLSI Design, vol. 10, pp. 1--20, June 1999.
• 10: Bo Hu , Malgorzata Marek-Sadowska, Wire length prediction based clustering and its application in placement, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776035]
• 11: IBM Placement Benchmarks {Online}. Available: http://er.cs.ucla.edu/benchmarks/ibm-place/
• 12: Capo Placement Tool {Online}. Available: http://vlsicad.eecs.umich.edu/BK/PDtools/tar.gz/Placement-bin/
• 13: Dragon Placement Tool {Online}. Available: http://er.cs.ucla.edu/Dragon/

INDEX TERMS

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

General Terms:
Documentation, Theory

Keywords:
wire length prediction