Article

Free access

Timing driven gate duplication: complexity issues and algorithms

Authors:

Ankur Srivastava,

Ryan Kastner,

Majid SarrafzadehAuthors Info & Claims

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

Pages 447 - 450

Published: 05 November 2000 Publication History

PDF eReader

Abstract

This paper addresses the issue of timing driven gate duplication for delay optimization. Gate duplication has been used extensively for cutset minimization but the usefulness in minimizing the circuit delay has not been addressed. This paper studies the complexity issues in timing driven gate duplication and proposes an algorithm for solving the so called global gate duplication problem. Delay improvements over highly optimized results from SIS have been reported.

References

[1]

A. Srivastava, R Kastner and M. Sarrafzadeh. "Complexity Issues in Gate Duplication". In Workshop Handouts, International Workshop on Logic Synthesis, May 2000.

Google Scholar

[2]

A. Srivastava, R Kastner and M. Sarrafzadeh. "Gate Duplication for Performance Optimization". In Internal Memo, Northwestern University, June 2000.

Google Scholar

[3]

C. Chen and C. Tsui. "Timing Optimization of Logic Network using Gate Duplication". In Proc. Asia and South Pacific Design Automation Conference, pages 233-236, January 1999.

Google Scholar

[4]

E.M. Sentovich, K.J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P.R. Stephan, R.K. Brayton, A.L. Sangiovanni-Vincentelli. SIS: A System for Sequential Circuit Synthesis. Memorandum No. UCB/ERL M92/41, Department of EECS. UC Berkeley, May 1992.

Google Scholar

[5]

I. Neumann, D. Stoffel, H. Hartje and W. Kunz. "Cell Replication and Redundancy Elimination During Placement for Cycle Time Optimization". In Proc. International Conference on Computer Aided Design, pages 25-30, November 1999.

Digital Library

Google Scholar

[6]

C. Kring and A.R.Newton. "A Cell replication Approach to Mincut-Based Circuit Partitioning". In Proc. International Conference on Computer Aided Design, pages 2-5, November 1991.

Google Scholar

[7]

M. Enos, S. Hauck and M. Sarrafzadeh. "Evaluation and Optimization of Replication Algorithms for Logic Bipartitioning". In IEEE Transactions on Computer Aided Design, pages 1237-1248, September 1999.

Digital Library

Google Scholar

[8]

R. Murgai. "On the Complexity of Minimum-delay Gate Resizing/Technology Mapping under Load-dependent Delay Model". In Workshop Handouts, International Workshop on Logic Synthesis, pages 209-211, June 1999.

Google Scholar

[9]

R. Murgai. "On the Global Fanout Optimization Problem". In Proc. International Conference on Computer Aided Design, pages 511-515, November 1999.

Digital Library

Google Scholar

Cited By

View all

Kim HLillis JPan DNam G(2008)A framework for layout-level logic restructuringProceedings of the 2008 international symposium on Physical design10.1145/1353629.1353652(87-94)Online publication date: 13-Apr-2008
https://dl.acm.org/doi/10.1145/1353629.1353652
Kim HLillis JHrkić MQu GIsmail YNarayanan VZhou H(2006)Techniques for improved placement-coupled logic replicationProceedings of the 16th ACM Great Lakes symposium on VLSI10.1145/1127908.1127959(211-216)Online publication date: 30-Apr-2006
https://dl.acm.org/doi/10.1145/1127908.1127959
Chen GCong JSchmit HWilton S(2005)Simultaneous timing-driven placement and duplicationProceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays10.1145/1046192.1046200(51-59)Online publication date: 20-Feb-2005
https://dl.acm.org/doi/10.1145/1046192.1046200
Show More Cited By

Recommendations

Timing driven gate duplication in technology independent phase
ASP-DAC '01: Proceedings of the 2001 Asia and South Pacific Design Automation Conference

We propose a timing driven gate duplication algorithm for the technology independent phase. Our algorithm is a generalization of the gate duplication strategy suggested in [1]. Our technique gets a more global view by duplicating multiple gates at a ...
The J-K Gate

For many years two-input NAND, AND, NOR, OR and EX-OR gates have been commercially available as cheap quad TTL integrated circuits (IC's). Ideas on quad programmable two-input gates (three inputs per gate) have been published in the literature but have ...
Timing driven gate duplication

In the past few years, gate duplication has been studied as a strategy for cutset minimization in partitioning problems. This paper addresses the problem of delay optimization by gate duplication. We present an algorithm to solve the gate duplication ...

Comments

Information & Contributors

Information

Published In

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

November 2000

558 pages

ISBN:0780364481

Conference Chair:
Ellen M. Sentovich
Cadence Berkley Labs., Berkley, California

Publisher

IEEE Press

Publication History

Published: 05 November 2000

Check for updates

Qualifiers

Article

Conference

ICCAD '00

Sponsor:

SIGDA

ICCAD '00: International Conference on Computer Aided Design

November 5 - 9, 2000

California, San Jose

Acceptance Rates

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

Upcoming Conference

ICCAD '24

Sponsor:
sigda

IEEE/ACM International Conference on Computer-Aided Design

October 27 - 31, 2024

New York , NY , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
290
Total Downloads

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

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kim HLillis JPan DNam G(2008)A framework for layout-level logic restructuringProceedings of the 2008 international symposium on Physical design10.1145/1353629.1353652(87-94)Online publication date: 13-Apr-2008
https://dl.acm.org/doi/10.1145/1353629.1353652
Kim HLillis JHrkić MQu GIsmail YNarayanan VZhou H(2006)Techniques for improved placement-coupled logic replicationProceedings of the 16th ACM Great Lakes symposium on VLSI10.1145/1127908.1127959(211-216)Online publication date: 30-Apr-2006
https://dl.acm.org/doi/10.1145/1127908.1127959
Chen GCong JSchmit HWilton S(2005)Simultaneous timing-driven placement and duplicationProceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays10.1145/1046192.1046200(51-59)Online publication date: 20-Feb-2005
https://dl.acm.org/doi/10.1145/1046192.1046200
Srivastava AKastner RChen CSarrafzadeh M(2004)Timing driven gate duplicationIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.5555/986333.98633712:1(42-51)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.5555/986333.986337
Hrkić MLillis JBeraudo GMalik SFix LKahng A(2004)An approach to placement-coupled logic replicationProceedings of the 41st annual Design Automation Conference10.1145/996566.996761(711-716)Online publication date: 7-Jun-2004
https://dl.acm.org/doi/10.1145/996566.996761
Chen GCong JMalik SFix LKahng A(2004)Simultaneous placement with clustering and duplicationProceedings of the 41st annual Design Automation Conference10.1145/996566.1142989(740-772)Online publication date: 7-Jun-2004
https://dl.acm.org/doi/10.1145/996566.1142989
Beraudo GLillis JGetreu IFix LLavagno L(2003)Timing optimization of FPGA placements by logic replicationProceedings of the 40th annual Design Automation Conference10.1145/775832.775885(196-201)Online publication date: 2-Jun-2003
https://dl.acm.org/doi/10.1145/775832.775885

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

Cited By

Recommendations

Timing driven gate duplication in technology independent phase

The J-K Gate