Optimal non-uniform wire-sizing under the Elmore delay model

ABSTRACT

We consider non-uniform wire-sizing for general routing trees under the Elmore delay model. Three minimization objectives are studied: (1) total weighted sink-delays; (2) total area subject to sink-delay bounds; and (3) maximum sink delay. We first present an algorithm NWSA-wd for minimizing total weighted sink-delays based on iteratively applying the wire-sizing formula. We show that NWSA-wd always converges to an optimal wire-sizing solution. Based on NWSA-wd and the Lagrangian relaxation technique, we obtained two algorithms NWSA-db and NWSA-md which can optimally solve the other two minimization objectives. Experimental results show that our algorithms are efficient both in terms of runtime and storage. For example, NWSA-wd, with linear runtime and storage, can solve a 6201-wire segment routing-tree problem using about 1.5-second runtime and 1.3-MB memory on an IBM RS/6000 workstation.

REFERENCES

• 1: Chung-Ping Chen , Yao-Ping Chen , D. F. Wong, Optimal wire-sizing formula under the Elmore delay model, Proceedings of the 33rd annual conference on Design automation, p.487-490, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240611]
• 2: C.-P. Chen, D. F. Wong. "A fast algorithm for optireal wire-sizing under Elmore delay model" Proc. IEEE ISCAS, vol. 4, pp. 412-415, 1996.
• 3: J. Cong and K. Leung, "Optimal wiresizing under Elmore delay model," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems 14(3), pp. 321-336, 1995.
• 4: W. C. Elmore, "The transient response of damped linear networks with particular regard to wide band amplifiers", J. Applied Physics, 19(1), 1948.
• 5: Noel Menezes , Satyamurthy Pullela , Florentin Dartu , Lawrence T. Pillage, RC interconnect synthesis—a moment fitting approach, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.418-425, November 06-10, 1994, San Jose, California, United States
• 6: Noel Menezes , Ross Baldick , Lawrence T. Pileggi, A sequential quadratic programming approach to concurrent gate and wire sizing, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.144-151, November 05-09, 1995, San Jose, California, United States
• 7: R.-S. Tsay, "Exact zero skew," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systerns, Feb. 1993.
• 8: M. L. Fisher, "An applications oriented guide to Lagrangian relaxation," Interfaces, 15:2, pp. 10-21, March-April 1985.
• 9: J. P. Fishburn and C. A. Schevon, "Shaping a distributed-RC line to minimize Elmore delay", IEEE Transactions on Circuits and Systems-I: Fundamental Theory and Applications, Vol. 42, No. 12, pp. 1020- 1022, December 1995.
• 10: D. G. Luenberger, Linear and Nonlinear Programming, Addison-Wesley Pub. Company Inc., 1984.
• 11: 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]
• 12: 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

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

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

General Terms:
Algorithms, Experimentation, Performance, Theory, Verification

Keywords:
Elmore delay model, IBM RS/6000 workstation, Lagrangian relaxation, NWSA-db, NWSA-md, NWSA-wd algorithm, circuit analysis computing, general routing trees, maximum sink delay, minimization objectives, optimal nonuniform wire sizing, routing-tree problem, sink-delay bounds, total area, total weighted sink-delays, wire-sizing formula