Timing optimization for multi-source nets: characterization and optimal repeater insertion

ABSTRACT

This paper presents new results in the area of timingoptimization for multi-source nets. The Augmented RC-Diameter (ARD) is proposed as a natural and practical performance metric and a linear time algorithm for computingthe ARD of a multi-source net is presented. Building onthe ARD, an algorithm for optimal repeater insertion is presented: for a given multi-source topology the algorithm efficiently identifies an optimal assignment of repeaters to prescribed insertion points under the "min cost timing feasible"problem formulation. The algorithm has been implementedand preliminary experimental results are promising.

REFERENCES

• 1: Clarkson, K.L. "More output-sensitive geometric algorithms," Proc. 35th Annual Symposium on Foundations of Computer Science, 1994 pp. 695-702
• 2: J.J. Cong, K.S. Leung, "Optimal Wiresizing Under Elmore Delay Model," IEEE Trans. on CAD, v. 14 no. 3 (1995) pp. 321-336.
• 3: J.J. Cong, P.H. Madden, "Performance driven routing with multiple sources," Proc. IEEE Symposium on Circuits and Systems, 1995 pp. 203-6
• 4: Jason Cong , Lei He, Optimal wiresizing for interconnects with multiple sources, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.568-574, November 05-09, 1995, San Jose, California, United States
• 5: Sanjay Dhar , Mark A. Franklin, Delay optimization algorithms for tree models of mos circuits, 1987
• 6: W.C. Elmore, "The Transient Response of Damped Linear Network with particular Regard to Wideband Amplifiers," J. Applied Physics 19 (1948), pp 55-63.
• 7: T. B. Huang, Y.C. Jeng et, al "Bidirectional Bus Repeater," U.S. Patent ~ 5,202,593, Apr. 13, 1993.
• 8: D.Y. Kao, C.C. Tsai, C.-K. Cheng, T.T. Lin, "New Design and Implementation for Signal Repeaters," VLSI/CAD workshop, Taiwan, pp. 173-176, Aug. 17- 19, 1995.
• 9: H. T. Kung , F. Luccio , F. P. Preparata, On Finding the Maxima of a Set of Vectors, Journal of the ACM (JACM), v.22 n.4, p.469-476, Oct. 1975 [doi>10.1145/321906.321910]
• 10: 3. Lillis, C.-K. Cheng, T.-T. Lin, "Optimal Wire Sizing and Buffer Insertion for Low Power and a Generalized Delay Model," IEEE Journal of Solid State Circuits, vol. 31, no. 3, March 1996, pp. 437-447.
• 11: John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin , Ching-Yen Ho, New performance driven routing techniques with explicit area/delay tradeoff and simultaneous wire sizing, Proceedings of the 33rd annual conference on Design automation, p.395-400, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240594]
• 12: N. Menezes, Intel Corp., private communication, Oct. 1996.
• 13: J. Rubinstein, P. Penfield, and M.A. Horowitz, "Signal Delay in RC Tree Networks," IEEE Trans. on CAD 2(3) (1983), pp 202-211.
• 14: Sachin S. Sapatnekar, RC interconnect optimization under the Elmore delay model, Proceedings of the 31st annual conference on Design automation, p.387-391, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196430]
• 15: C.C. Tsai, D.Y. Kao, and C.-K. Cheng, "Performance Driven Bus Buffer Insertion," IEEE Trans. on CAD, April 1996, pp. 429-437
• 16: L.P.P.P van Ginneken, "Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay," Proc. International Symposium on Circuits and Systems, 1990, pp 865-868.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

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