research-article

Power-delay optimization in VLSI microprocessors by wire spacing

Authors:

Konstantin Moiseev,

Avinoam Kolodny,

Shmuel WimerAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 14, Issue 4

Article No.: 55, Pages 1 - 28

https://doi.org/10.1145/1562514.1562523

Published: 28 August 2009 Publication History

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.

Digital Library

[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.

Digital Library

[5]

Cederbaum, I., Koren, I., and Wimer, S. 1992. Balanced block spacing for VLSI layout. Disc. Appl. Math. 40, 3, 308--318.

Digital Library

[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.

Digital Library

[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.

Digital Library

[9]

Cheng, C.-K., Lillis, J., Lin, S., and Chang, N. 1999. Interconnect Analysis and Synthesis. Wiley-Interscience.

Digital Library

[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.

Digital Library

[11]

Cormen, T. H., Leiserson, C. H., and Rivest, R. L. 2001. Introduction to Algorithms, 2nd Ed. MIT Press.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Cited By

Moiseev KWimer SKolodny A(2015)Timing-constrained power minimization in VLSI circuits by simultaneous multilayer wire spacingIntegration, the VLSI Journal10.1016/j.vlsi.2014.03.00248:C(116-128)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1016/j.vlsi.2014.03.002
Shaphir EPinter RWimer S(2014)Cell-based interconnect migration by hierarchical optimizationIntegration, the VLSI Journal10.1016/j.vlsi.2013.10.00347:2(161-174)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1016/j.vlsi.2013.10.003
Shaphir EPinter RWimer S(2014)Efficient cell-based migration of VLSI layoutOptimization and Engineering10.1007/s11081-014-9257-716:1(203-223)Online publication date: 28-Mar-2014
https://doi.org/10.1007/s11081-014-9257-7
Show More Cited By

Index Terms

Power-delay optimization in VLSI microprocessors by wire spacing
1. Applied computing
  1. Arts and humanities
    1. Architecture (buildings)
      1. Computer-aided design
  2. Physical sciences and engineering
    1. Engineering
      1. Computer-aided design
2. Hardware
  1. Electronic design automation
    1. Physical design (EDA)

Recommendations

Timing-aware power-optimal ordering of signals

A computationally efficient technique for reducing interconnect active power in VLSI systems is presented. Power reduction is accomplished by simultaneous wire spacing and net ordering, such that cross-capacitances between wires are optimally shared. ...
Interconnect power and delay optimization by dynamic programming in gridded design rules
ISPD '10: Proceedings of the 19th international symposium on Physical design

The lithography used for 32 nanometers and smaller VLSI process technologies restricts the admissible interconnect widths and spaces to a small set of discrete values with some interdependencies, so that traditional interconnect sizing by continuous-...
Buffered Steiner tree construction with wire sizing for interconnect layout optimization
ICCAD '96: Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design

This paper presents an efficient algorithm for buffered Steiner tree construction with wire sizing. Given a source and n sinks of a signal net, with given positions and a required arrival time associated with each sink, the algorithm finds a Steiner ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 14, Issue 4

August 2009

226 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/1562514

Issue’s Table of Contents

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 28 August 2009

Accepted: 01 March 2009

Revised: 01 January 2009

Received: 01 October 2008

Published in TODAES Volume 14, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
358
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Moiseev KWimer SKolodny A(2015)Timing-constrained power minimization in VLSI circuits by simultaneous multilayer wire spacingIntegration, the VLSI Journal10.1016/j.vlsi.2014.03.00248:C(116-128)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1016/j.vlsi.2014.03.002
Shaphir EPinter RWimer S(2014)Cell-based interconnect migration by hierarchical optimizationIntegration, the VLSI Journal10.1016/j.vlsi.2013.10.00347:2(161-174)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1016/j.vlsi.2013.10.003
Shaphir EPinter RWimer S(2014)Efficient cell-based migration of VLSI layoutOptimization and Engineering10.1007/s11081-014-9257-716:1(203-223)Online publication date: 28-Mar-2014
https://doi.org/10.1007/s11081-014-9257-7
Moiseev KKolodny AWimer SMoiseev KKolodny AWimer S(2014)Multi-net Sizing and Spacing in General LayoutsMulti-Net Optimization of VLSI Interconnect10.1007/978-1-4614-0821-5_7(107-165)Online publication date: 16-Oct-2014
https://doi.org/10.1007/978-1-4614-0821-5_7
Moiseev KKolodny AWimer SMoiseev KKolodny AWimer S(2014)Multi-net Sizing and Spacing of Bundle WiresMulti-Net Optimization of VLSI Interconnect10.1007/978-1-4614-0821-5_6(63-106)Online publication date: 16-Oct-2014
https://doi.org/10.1007/978-1-4614-0821-5_6
Moiseev KKolodny AWimer S(2012)The complexity of VLSI power-delay optimization by interconnect resizingJournal of Combinatorial Optimization10.1007/s10878-010-9355-123:2(292-300)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1007/s10878-010-9355-1
Moiseev KKolodny AWimer SSaxena PChang Y(2010)Interconnect power and delay optimization by dynamic programming in gridded design rulesProceedings of the 19th international symposium on Physical design10.1145/1735023.1735061(153-160)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.1145/1735023.1735061
Moiseev KKolodny AWimer S(2010)Interconnect bundle sizing under discrete design rulesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2010.205163329:10(1650-1654)Online publication date: 1-Oct-2010
https://dl.acm.org/doi/10.1109/TCAD.2010.2051633

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents