Optimal wiresizing for interconnects with multiple sources

ABSTRACT

In this paper, we study the optimal wiresizing problem for nets with multiple sources under the RC tree model and the Elmore delay model. We decompose the routing tree for a multisource net into the source subtree (SST) and a set of loading subtrees (LSTs), and show that the optimal wiresizing solution satisfies a number of interesting properties, including: LST separability, the LST monotone property, the SST local monotone property, and the dominance property. Furthermore, we study the optimal wiresizing problem using a variable segment-division rather than an a priori fixed segment-division as in all previous works and reveal the bundled refinement property. These properties lead to efficient algorithms to compute the optimal solutions. We have tested our algorithm on nets extracted from the multilayer layout for a high-performance Intel microprocessor. Accurate SPICE simulation shows that our methods reduce the average delay by up to 23.5% and the maximum delay by up to 37.8%, respectively, for the submicron CMOS technology when compared to the minimal wire width solution. In addition, the algorithm based on the variable segment-division yields a speedup of over 100× time and does not lose any accuracy, when compared with the algorithm based on the a priori fixed segment-division.

REFERENCES

• 1: ALPERT, C. J., Hu, T. C., HUANG, J. H., AND KAHNG, A.B. 1993. A direct combination of the Prim and Dijkstra constructions for improved performance-driven routing. In Proceedings of the IEEE International Symposium on Circuits and Systems, (Chicago, IL, May), 1869- 1872.
• 2: Kenneth D. Boese , Andrew B. Kahng , Gabriel Robins, High-performance routing trees with identified critical sinks, Proceedings of the 30th international conference on Design automation, p.182-187, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164662]
• 3: CHAN, H. 1995. Private communication.
• 4: 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]
• 5: 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]
• 6: 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
• 7: CONG, J. AND HE, L. 1995b. Optimal wiresizing for interconnects with multiple sources. UCLA Computer Science, Tech. Rep. 95-00031, Aug.
• 8: CONG, J. AND HE, L. 1995c. Simultaneous transistor and interconnect sizing based on the general dominance property. UCLA Computer Science, Tech. Rep. 95-00046 (Dec.).
• 9: 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
• 10: Jason Cong , Cheng-Kok Koh, Simultaneous driver and wire sizing for performance and power optimization, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.2 n.4, p.408-425, Dec. 1994 [doi>10.1109/92.335010]
• 11: 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
• 12: CONG, J. AND LEUNG, K. S. 1995. Optimal wiresizing under the distributed Elmore delay model. IEEE Trans. CAD 14, 3 (March), 321-336.
• 13: CONG, g. AND MADDEN, P.H. 1995. Performance-driven routing with multiple sources. In Proceedings of the IEEE International Symposium on Circuits and Systems. (Seattle, WA, April), 203-206.
• 14: CONG, J., KAHNG, A. B., ROBINS, G., SARRAFZADEH, M., AND WONG, C.K. 1992. Provably good performance-driven global routing. IEEE Trans. CAD 11, 6 (June), 739-752.
• 15: Jason Cong , Kwok-Shing Leung , Dian Zhou, Performance-driven interconnect design based on distributed RC delay model, Proceedings of the 30th international conference on Design automation, p.606-611, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165065]
• 16: ELMORE, W. C. 1948. The transient response of damped linear network with particular regard to wideband amplifier. J. Appl. Phys. 19, 55-63.
• 17: FISHBURN, g. P. AND DUNLOP, A.E. 1985. TILOS: A posynomial programming approach to transistor sizing. In Proceedings of the IEEE International Conference on Computer-Aided Design, (San Jose, CA, Nov.) 326-328.
• 18: VAN GINNEKEN, L. P. P. P. 1990. Buffer placement in distributed RC-tree networks for minimal Elmore delay. In Proceedings of the International Symposium on Circuits and Systems (New Orleans, LA, May), 865-868.
• 19: HODES, T. D., MCCOY, B. A., AND ROBINS, G. 1994. Dynamically-wiresized Elmore-based routing constructions. In Proceedings of the International Symposium on Circuits and Systems (London, England, May), 463-466.
• 20: Xianlong Hong , Tianxiong Xue , Ernest S. Kuh , Chung-Kuan Cheng , Jin Huang, Performance-driven Steiner tree algorithm for global routing, Proceedings of the 30th international conference on Design automation, p.177-181, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164658]
• 21: KAHNG, A. B. AND ROBINS, G. 1992. A new class ofiterative Steiner tree heuristics with good performance. In Proceedings of the IEEE International Conference on Computer-Aided Design (San Jose, CA, Nov.), 893-902.
• 22: John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin, Optimal wire sizing and buffer insertion for low power and a generalized delay model, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.138-143, November 05-09, 1995, San Jose, California, United States
• 23: 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]
• 24: McCoY, B. A. AND ROBINS, G. 1994. Non-tree routing. In Proceedings of the International European Design and Test Conference Symposium on Circuits and Systems (Paris, Feb.), 430-434.
• 25: MCNC DESIGNERS' MANUAL. North Carolina Microelectronic Center.
• 26: 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
• 27: 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
• 28: Takumi Okamoto , Jason Cong, Buffered Steiner tree construction with wire sizing for interconnect layout optimization, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.44-49, November 10-14, 1996, San Jose, California, United States
• 29: RUBINSTEIN, J., PENFIELD, P., AND HOROWITZ, M.A. 1983. Signal delay in RC tree networks. IEEE Trans. CAD 2, 3, 202-211.
• 30: SANCHETI, P. K. AND SAPATNEKAR, S.S. 1994. Interconnect design using convex optimization. In Proceedings of the IEEE Custom Integrated Circuits Conference, (San Diego, CA, May) 549-552.
• 31: 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]
• 32: Tianxiong Xue , Ernest S. Kuh, Post routing performance optimization via multi-link insertion and non-uniform wiresizing, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.575-580, November 05-09, 1995, San Jose, California, United States
• 33: Tianxiong Xue , Ernest S. Kuh , Qinjian Yu, A Sensitivity-Based Wiresizing Approach to Interconnect Optimization of Lossy Transmission Line Topologies, Proceedings of the 1996 IEEE Multi-Chip Module Conference (MCMC '96), p.117, February 06-07, 1996

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing; Layout
          Nouns: SPICE

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
Elmore delay, bundled refinement, decomposition of multi-source routing tree, dominance property, fidelity, high performance, interconnect optimization, layout optimization, local refinement, multi-source net, multi-source routing tree, optimal wiresizing, variable segment-division