Greedy wire-sizing is linear time

ABSTRACT

In interconnect optimization by wire-sizing, minimizing weighted sink delay has been shown to be the key problem. Wire-sizing with many important objectives such as minimizing total area subject to delay bounds or minimizing maximum delay can all be reduced to solving a sequence of weighted sink delay problems by Lagrangian relaxation [1, 3]. GWSA, first introduced in [10] for discrete wire-sizing and later extended in [2] to continuous wire-sizing, is a greedy wire-sizing algorithm for the weighted sink delay problem. Although GWSA has been experimentally shown to be very efficient, no mathematical analysis on its convergence rate has ever been reported. In this paper, we consider GWSA for continuous wire sizing. We prove that GWSA converges linearly to the optimal solution, which implies that the run time of GWSA is linear with respect to the number of wire segments for any fixed precision of the solution. Moreover, we also prove that this is true for any starting solution. This is a surprising result because previously it was believed that in order to guarantee convergence, GWSA had to start from a solution in which every wire segment is set to the minimum (or maximum) possible width. Our result implies that GWSA can use a good starting solution to achieve faster convergence. We demonstrate this point by showing that the minimization of maximum delay using Lagrangian relaxation can be speed up by 57.7%.

REFERENCES

• 1: Chung-Ping Chen , Yao-Wen Chang , D. F. Wong, Fast performance-driven optimization for buffered clock trees based on Lagrangian relaxation, Proceedings of the 33rd annual conference on Design automation, p.405-408, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240596]
• 2: Chung-Ping C'hen and D. F. Wong. A fast Mgorithm for optimal wire-sizing under Elmore delay model. In Proc. IEEE ISCAS, volume 4, pages 412-415, 1996.
• 3: Chung-Ping Chen , Hai Zhou , D. F. Wong, Optimal non-uniform wire-sizing under the Elmore delay model, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.38-43, November 10-14, 1996, San Jose, California, United States
• 4: Chung Chen , Chris C. N. Chu , D. F. Wong, Fast and Exact Simultaneous Gate and Wire Sizing by Lagrangian Relaxation, University of Texas at Austin, Austin, TX, 1998
• 5: Jason Cong , Lei He, An efficient approach to simultaneous transistor and interconnect sizing, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.181-186, November 10-14, 1996, San Jose, California, United States
• 6: 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]
• 7: 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]
• 8: Jason Cong , Cheng-Kok Koh, Simultaneous driver and wire sizing for performance and power optimization, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.206-212, November 06-10, 1994, San Jose, California, United States
• 9: J. Cong , C. Koh , K. Leung, Simultaneous buffer and wire sizing for performance and power optimization, Proceedings of the 1996 international symposium on Low power electronics and design, p.271-276, August 12-14, 1996, Monterey, California, United States
• 10: Jason Cong , Kwok-Shing Leung, Optimal wiresizing under the distributed Elmore delay model, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.634-639, November 07-11, 1993, Santa Clara, California, United States
• 11: W. G. Elmore. The transient response of damped linear network with particular regard to wideband amplifiers. J. Applied Physics, 19:55--63, 1948.
• 12: 1t. S. Tsay. An exact zero-skew clock routing algorithm. IEEE Trans. Computer-Aided Design, 12(2):242-249, February 1993.

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
  B.8 Performance and Reliability

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Experimentation, Performance, Theory, Verification