Power-delay optimization in VLSI microprocessors by wire spacing

ABSTRACT

The problem of optimal space allocation among interconnect wires in a VLSI layout, in order to minimize the switching power consumption and the average signal delay, is addressed in this article. We define a Weighted Power-Delay Sum (WPDS) objective function and derive necessary and sufficient conditions for the existence of optimal interwire space allocation, based on the notion of capacitance density. At the optimum, every wire must be in equilibrium of its line-to-line weighted capacitance density on its two opposite sides, and the WPDS of the whole circuit is minimal if and only if capacitance density is uniformly distributed across the entire layout. This condition is shown to be equivalent to all paths of the layout cross-capacitance graph having the same length and all cuts having the same flow. An implementation which has been used in the design of a recent commercial high-end microprocessor and yielded 17% power reduction and 9% delay reduction in top-level interconnects is presented.

REFERENCES

• 1: Abou-Seido, A. I., Nowak, B., and Chu, C. 2002. Fitted Elmore delay: A simple and accurate interconnect delay model. In Proceedings of IEEE International Conference on Computer Design, 422--427.
• 2: Bakoglu, H. 1990. Circuits, Interconnections, and Packaging for VLSI. Addison-Wesley.
• 3: Boese, K. D., Kahng, A. B., McCoy, B. A., and Robins, G. 1993. Fidelity and near-optimality of Elmore-based routing constructions. In ICCAD Digest of Technical Papers, 81--84.
• 4: Borkar, S. 2001. Low-power design challenges for the decade. Proceedings of the Conference on Asia South Pacific Design Automation, 293--296.
• 5: Cederbaum, I., Koren, I., and Wimer, S. 1992. Balanced block spacing for VLSI layout. Disc. Appl. Math. 40, 3, 308--318.
• 6: Chaudhary, K., Onozawa, A., and Kuh, E. 1993. A spacing algorithm for performance enhancement and cross-talk reduction. In Proceedings of the IEEE/ACM International Conference on CAD, 697--702.
• 7: Chiluvuri, V. K. R. and Koren, I. 1995. Layout-synthesis techniques for yield enhancement. IEEE Trans. Semiconductor Manufactur. 8, 2, 178--187.
• 8: Chen, P., Kirkpatrick, D. A., and Keutzer, K. 2000. Miller factor for gate-level coupling delay calculation. In Proceedings of the ICCAD, 68--74.
• 9: Cheng, C.-K., Lillis, J., Lin, S., and Chang, N. 1999. Interconnect Analysis and Synthesis. Wiley-Interscience.
• 10: Cong, J., He, L., Koh, C. K., and Pan, Z. 2001. Interconnect sizing and spacing with consideration of coupling capacitance. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 20, 9, 1164--1169.
• 11: Cormen, T. H., Leiserson, C. H., and Rivest, R. L. 2001. Introduction to Algorithms, 2nd Ed. MIT Press.
• 12: Devadas, S. and Malik, S. 1995. A survey of optimization techniques targeting low-power VLSI circuits. Proceedings of the 32nd ACM/IEEE Conference on Design Automation, 242--247.
• 13: Gao, T. and Liu, C. L. 1996. Minimum cross-talk channel routing. IEEE Trans. Comput.-Aided Des. Integr. Care Syst. 15, 5, 465--474.
• 14: Genossar, D. and Shamir, N. 2003. Intel® Pentium® M processor power estimation, budgeting, optimization, and validation. Intel Technol. J. 7, 43--50.
• 15: Hanchate, N. and Ranganathan, N. 2006. A linear-time algorithm for wire sizing with simultaneous optimization of interconnect delay and cross-talk noise. In Proceedings of the 19th International Conference on VLSI Design, 283--290.
• 16: He, J-A and Kobayashi, H. 1998. Simultaneous wire sizing and wire spacing in post-layout performance optimization. In Proceedings of the ASP-DAC Design Automation Conference, 373--378.
• 17: Ho, R., Mai, K., and Horowitz, M. 2001. The future of wires. Proc. IEEE 89, 4, 490--501.
• 18: Hu, T. C. 1969. Integer Programming and Network Flows. Addison Wesley.
• 19: ITRS. 2005. ITTS report. http://www.itrs.net/reports.html
• 20: Jhang, K., Ha, S., and John, C. 1994. A segment rearrangement approach to channel routing under the cross-talk constraints. In Proceedings of the Asia-Pacific Conference on Circuits and Systems, 536--541.
• 21: Kahng, A., Masuko, K., and Muddu, S. 1996. Analytical delay models for VLSI interconnects under ramp input. In Proceedings of the IEEE International Conference on Computer-Aided Design (ICCAD), 30--36.
• 22: Li, C., Xie, M., Cong, C-K Koh, J., and Madden, P. H. 2007. Routability-driven placement and white space allocation. IEEE Trans. Comput.-Aided. Des. Integr. Circ. Syst. 25, 5, 858--871.
• 23: Luenberger, D. G. 1984. Linear and Nonlinear Programming. Addison Wesley, Chapter 6.5.
• 24: Macii, E., Poncino, M., and Salerno, S. 2003. Combining wire swapping and spacing for low-power deep-submicron buses. In Proceedings of the 13th ACM Great Lakes Symposium on VLSI, 198--202.
• 25: Magen, N., Kolodny, A., Weiser, U., and Shamir, N. 2004. Interconnect-Power dissipation in a microprocessor. In Proceedings of the International Workshop on System Level Interconnect Prediction, 7--13.
• 26: Miyoshi, T., Wakabayashi, S., Koide, T., and Yoshida, N., 1995. An MCM routing algorithm considering crosstalk. In Proceedings of the International Symposium on Circuits and Systems, 211--214.
• 27: Mui, M. L., Benerjee, K., and Mehortra, A. 2004. A global interconnect optimization scheme for nanometer scale VLSI with implications for latency, bandwidth, and power dissipation. IEEE Trans. Electon. Devices 51, 2, 195--203.
• 28: Onazawa, A., Chaudhary, K., and Kuh, E. S. 1995. Performance driven spacing algorithm using attractive and repulsive constraints for submicron LSI's. IEEE Trans. Comput.-Aided. Des. Integr. Circ. Syst. 14, 707--719.
• 29: Saxena, P. and Liu, C. L. 2000. An algorithm for cross-talk-driven wire perturbation. IEEE Trans. Comput.-Aided. Des. Integr. Circ. Syst. 19, 6, 691--702.
• 30: Seshu, S. and Reed, M. B. 1961. Linear Graphs and Electrical Networks. Addison-Wesley, Reading, MA.
• 31: Sylvester, D. and Keutzer, K.. 1998. Getting to the bottom of deep submicron. In Proceedings of the IEEE/ACM International Conference on CAD, 203--211.
• 32: Wang, D. and Kuh, E. S. 1998. A performance driven MCM router with special considerations of cross-talk reduction. In Proceedings of the Design Automation and Test in Europe, 466--470.
• 33: Wimer, S., Koren, I., and Cederbaum, I. 1988. Floorplans, planar graphs, and layout. IEEE Trans. Circ. Syst. 35, 3, 267--278.
• 34: Wimer, S., Michaely, S., Moiseev, K., and Kolodny, A. 2006. Optimal bus sizing in migration of processor design. IEEE Trans. Circ. Syst. I 53, 5, 1089--1100.
• 35: Xtreme. A Wire Spacing Tool for Manufacturing Yield Enhancement. Sagantec.

INDEX TERMS

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

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

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

General Terms:
Algorithms, Design

Keywords:
Wire spacing, delay-optimization, interconnect optimization, power optimization