Toward better wireload models in the presence of obstacles

ABSTRACT

Efficient and accurate interconnect estimation is crucial to design convergence. With System-on-Chip design, IP blocks form routing obstacles that cannot be accounted for by existing a priori wirelength estimations. In this paper, we identify two distinct effects of obstacles on interconnection length: (i) changes due to the redistribution of interconnect terminals and (ii) detours that have to be made around the obstacles. Theoretical expressions of both effects for point-to-point nets with a single obstacle are derived and compared to experimental observations. We also experimentally assess these effects for multi-terminal interconnections and in the presence of multiple obstacles. We single out cases where the effects are additive, which suggests the use of lookup tables and equivalent blockage relations. Our results are applicable in chip planning tools, where they enable improved accounting for obstacles in a priori wirelength estimation schemes.

REFERENCES

• 1: B. S. Landman and R. L. Russo, "On a Pin versus Block Relationship for Partitions of Logic Graphs", IEEE Trans. on Computer, C-20, 1971, pp. 1469-1479.
• 2: W. E. Donath, "Placement and Average Interconnection Lengths of Computer Logic", IEEE Trans. on Circuits and Systems, CAS-26(4), 1979, pp. 272-277.
• 3: J. A. Davis, V. K. De and J. D. Meindl, "A Stochastic Wire- Length Distribution for Gigascale Integration(GSI)-part 1: Derivation and Validation", IEEE Trans. on Electron Dev., 45, 1998, pp. 580-589.
• 4: D. Stroobandt, "Tutorial: A Priori Wire Length Estimations Based on Rent's Rule", Workshop on System-Level Interconnect Prediction (SLIP), 1999, pp. 3-50.
• 5: Philip Christie , Dirk Stroobandt, The interpretation and application of Rent's rule, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.6, p.639-648, Dec. 2000 [doi>10.1109/92.902258]
• 6: D. Stroobandt and J. Van Campenhout, "Accurate Interconnection Length Estimations for Predictions Early in the Design Cycle,", VLSI Design, Special Issue on Physical Design in Deep Submicron, 10(1), 1999, pp. 1-20.
• 7: Dirk Stroobandt , Herwig Van Marck, Efficient representation of interconnection length distributions using generating polynomials, Proceedings of the 2000 international workshop on System-level interconnect prediction, p.99-105, April 08-09, 2000, San Diego, California, United States [doi>10.1145/333032.333039]
• 8: Andrew E. Caldwell , Andrew B. Kahng , Stefanus Mantik , Igor L. Markov , Alex Zelikovsky, On wirelength estimations for row-based placement, Proceedings of the 1998 international symposium on Physical design, p.4-11, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274536]
• 9: 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
• 10: Lou Scheffer , Eric Nequist, Why interconnect prediction doesn't work, Proceedings of the 2000 international workshop on System-level interconnect prediction, p.139-144, April 08-09, 2000, San Diego, California, United States [doi>10.1145/333032.333044]
• 11: Technical Report, April 2000. Anonymous for review process. http://www.geocities.com/aspdac2001.
• 12: L. Kou, G. Markowsky and L. Berman, "A Fast Algorithm for Steiner Trees," Acta Informatica, 15(2), 1981, pp. 141-145.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

General Terms:
Design, Experimentation, Performance, Theory