research-article

Timing optimization by restructuring long combinatorial paths

Authors:

Jürgen Werber,

Dieter Rautenbach,

Christian SzegedyAuthors Info & Claims

ICCAD '07: Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design

Pages 536 - 543

Published: 05 November 2007 Publication History

Abstract

We present an implementation of an algorithm for constructing provably fast circuits for a class of Boolean functions with input signals that have individual starting times. We show how to adapt this algorithm to logic optimization for timing correction at late stages of VLSI physical design and report experimental results on recent industrial chips. By restructuring long critical paths, our code achieves worst-slack improvements of up to several hundred picoseconds on top of traditional timing optimization techniques.

References

[1]

C. Bartoschek, S. Held, D. Rautenbach, J. Vygen, Efficient Generation of Short and Fast Repeater Tree Topologies, International Symposium on Physical Design (2006), 120--127.

Digital Library

[2]

S. Held, Fast Gate Sizing and Timing Closure for Multi-Million Cell Designs, Report No. 07969, Research Institute for Discrete Mathematics, University of Bonn, 2007.

[3]

B. Korte, D. Rautenbach, J. Vygen: BonnTools: Mathematical Innovation for Layout and Timing Closure of Systems on a Chip, Proceedings of the IEEE 95 (2007), 555--572.

[4]

J. Liu, S. Zhou, H. Zhu, C.-K. Cheng, An Algorithmic Approach for Generic Parallel Adders, International Conference on Computer-Aided Design 2003, 734--740.

Digital Library

[5]

V. G. Oklobdzija, D. Villeger, S. S. Liu, A Method for Speed Optimized Partial Product Reduction and Generation of Fast Parallel Multipliers Using an Algorithmic Approach, IEEE Transactions on Computers 45 (1996), 294--306.

Digital Library

[6]

D. Rautenbach, C. Szegedy, J. Werber, Delay optimization of linear depth boolean circuits with prescribed input arrival times, Journal of Discrete Algorithms 4 (2006), 526--537.

Digital Library

[7]

D. Rautenbach, C. Szegedy, J. Werber, Asymptotically Optimal Boolean Circuits for Functions of the Form g_n-1(g_n-2(.g₃(g₂(g₁(x₁, x₂), x₃), x₄)., x_n-1), x_n) given Input Arrival Times, Report No. 03931, Research Institute for Discrete Mathematics, University of Bonn, 2003.

[8]

J. E. Savage, Models of Computation: Exploring the Power of Computing, Addison-Wesley Longman, Reading, MA, 1998.

Digital Library

[9]

P. F. Stelling, V. Oklobdzija, Design strategies for the final adder in a parallel multiplier, 29th Asilomar Conference on Signals, Systems and Computers (1995), 591.

Digital Library

[10]

P. F. Stelling, V. Oklobdzija, Design strategies for optimal hybrid final adders in a parallel multiplier, Journal of VLSI Signal Processing Systems 14 (1996), 321--331.

Digital Library

[11]

I. Sutherland, B. Sproull, D. Harris, Logical Effort: Designing Fast CMOS Circuits, Morgan Kaufmann, San Francisco, CA, 1999.

Digital Library

[12]

L. Stok et al., BooleDozer: Logic synthesis for ASICs, IBM Journal of Research and Development 40 (1996), 407--430.

Digital Library

[13]

L. Trevillyan, D. Kung, R. Puri, L. N. Reddy, M. A. Kazda, An Integrated Environment for Technology Closure of Deep-Submicron IC Designs, IEEE Design & Test of Computers 21 (2004), 14--22.

Digital Library

[14]

http://www.cs.utexas.edu/users/cart/trips/index.html.

[15]

W.-C. Yeh, C.-W. Jen, Generalized Earliest-First Fast Addition Algorithm, IEEE Transactions on Computers 52 (2003), 1233--1242.

Digital Library

Cited By

Brenner UHermann A(2019)Faster Carry Bit Computation for Adder Circuits with Prescribed Arrival TimesACM Transactions on Algorithms10.1145/334032115:4(1-23)Online publication date: 25-Jul-2019
https://dl.acm.org/doi/10.1145/3340321
Held SSpirkl S(2017)Binary Adder Circuits of Asymptotically Minimum Depth, Linear Size, and Fan-Out TwoACM Transactions on Algorithms10.1145/314721514:1(1-18)Online publication date: 14-Dec-2017
https://dl.acm.org/doi/10.1145/3147215
Held SSpirkl S(2017)Fast Prefix Adders for Non-uniform Input Arrival TimesAlgorithmica10.1007/s00453-015-0067-x77:1(287-308)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1007/s00453-015-0067-x
Show More Cited By

Recommendations

Timing optimization via nest-loop pipelining considering code size

Embedded systems have strict timing and code size requirements. Software pipelining is one of the most important optimization techniques to improve the execution time of loops by increasing the parallelism among successive loop iterations. However, ...
Timing Optimization of Nested Loops Considering Code Size for DSP Applications
ICPP '04: Proceedings of the 2004 International Conference on Parallel Processing

Software pipelining for nested loops remains a challenging problem for embedded system design. The existing software pipelining techniques for single loops can only explore the parallelism of the innermost loop, so the final timing performance is ...
Timing optimization by replacing flip-flops to latches
ASP-DAC '04: Proceedings of the 2004 Asia and South Pacific Design Automation Conference

Latch circuits have advantage for timing and are widely used for high-speed custom circuits. However, ASIC design flows are based on the circuits with flip-flops. Then, ASIC designers don't use latches. This paper describes a new timing optimization ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '07: Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design

November 2007

933 pages

ISBN:1424413826

General Chair:
Georges Gielen
ESAT-MICAS, Katholieke Univ. Leuven, Leuven, Belgium

Sponsors

CEDA: Council on Electronic Design Automation
SIGDA: ACM Special Interest Group on Design Automation
IEEE CASS/CANDE
IEEE-CS\DATC: IEEE Computer Society

Publisher

IEEE Press

Publication History

Published: 05 November 2007

Check for updates

Qualifiers

Research-article

Conference

ICCAD07

Sponsor:

CEDA
SIGDA
IEEE-CS\DATC

ICCAD07: The International Conference on Computer-Aided Design 2007

November 5 - 8, 2007

California, San Jose

Acceptance Rates

ICCAD '07 Paper Acceptance Rate 139 of 510 submissions, 27%;

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
169
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Brenner UHermann A(2019)Faster Carry Bit Computation for Adder Circuits with Prescribed Arrival TimesACM Transactions on Algorithms10.1145/334032115:4(1-23)Online publication date: 25-Jul-2019
https://dl.acm.org/doi/10.1145/3340321
Held SSpirkl S(2017)Binary Adder Circuits of Asymptotically Minimum Depth, Linear Size, and Fan-Out TwoACM Transactions on Algorithms10.1145/314721514:1(1-18)Online publication date: 14-Dec-2017
https://dl.acm.org/doi/10.1145/3147215
Held SSpirkl S(2017)Fast Prefix Adders for Non-uniform Input Arrival TimesAlgorithmica10.1007/s00453-015-0067-x77:1(287-308)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1007/s00453-015-0067-x
Markov IHu JKim MHu A(2012)Progress and challenges in VLSI placement researchProceedings of the International Conference on Computer-Aided Design10.1145/2429384.2429441(275-282)Online publication date: 5-Nov-2012
https://dl.acm.org/doi/10.1145/2429384.2429441
Martinello OMarques FRibas RReis ADe Micheli GAl-Hashimi BMueller WMacii E(2010)KL-cutsProceedings of the Conference on Design, Automation and Test in Europe10.5555/1870926.1871112(777-782)Online publication date: 8-Mar-2010
https://dl.acm.org/doi/10.5555/1870926.1871112
Krishnaswamy SRen HModi NPuri RRoychowdhury J(2009)DeltaSynProceedings of the 2009 International Conference on Computer-Aided Design10.1145/1687399.1687546(789-796)Online publication date: 2-Nov-2009
https://dl.acm.org/doi/10.1145/1687399.1687546
Plaza SMarkov IBertacco VPan DNam G(2008)Optimizing non-monotonic interconnect using functional simulation and logic restructuringProceedings of the 2008 international symposium on Physical design10.1145/1353629.1353653(95-102)Online publication date: 13-Apr-2008
https://dl.acm.org/doi/10.1145/1353629.1353653

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten