More Web Proxy on the site http://driver.im/

Article

Free access

Retiming with non-zero clock skew, variable register, and interconnect delay

Authors:

Eby G. FriedmanAuthors Info & Claims

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

Pages 234 - 241

Published: 06 November 1994 Publication History

Abstract

A retiming algorithm is presented which includes the effects of variable register, clock distribution, and interconnect delay. These delay components are incorporated into retiming by assigning Register Electrical Characteristics (RECs) to each edge in the graph representation of the synchronous circuit. A matrix (called the Sequential Adjacency Matrix or SAM) is presented that contains all path delays. Timing constraints for each data path are derived from this matrix. Vertex lags are assigned ranges rather than single values as in standard retiming algorithms. The approach used in the proposed algorithm is to initialize these ranges with unbounded values and continuously tighten these ranges using localized timing constraints until an optimal solution is obtained. The algorithm is demonstrated on modified MCNC benchmark circuits and both increased clock frequencies and elimination of all race conditions are observed.

References

[1]

C.E. Leiserson and J. B. Saxe, "Retiming Synchronous Circuitry," Algorfthmica, Vol. 6, pp. 5-35, January 1991.

[2]

A.T. Ishii, C. E. Leiserson, and M. C. Papeefthymion, "Optimizing Two-Phase, Level-Clocked Circuitry," Proceedings of the 1992 Brown/MIT Conference on Advanced Research in VLSI and Parallel Systems, pp. 245-264, March 1992.

[3]

G. De Micheli, "Synchronous Logic Synthesis: Algorithms for Cycle-Time Minimization," IEEE Transactions on Computer-Aided Design, Vol. CAD-10, No. 1, pp. 63--73, January 1991.

[4]

J.P. Fishburn, "Clock Skew Optimization," IEEE Transactions on Computers, Vol. 39, No. 7, pp. 945-951, July 1990.

Digital Library

[5]

E.G. Friedman, "The Application of Localized Clock Distribution Design to Improving the Performance of Retimed Sequential Circuits," Proceedings of the IEEE Asia.Pacific Conference on Circuits and Syzt~u, pp. 12-17, December 1992.

[6]

T. Soynte, E. G. Friedman, and J.' H. Mulligan, Jr., "Integration of Clock Skew and Register Delays into a Retiming Algorithm,' Proceedings of the IEEE International Syml~sium on Circuits and Systems, pp. 1483-1486, May 1993.

[7]

B. Lockyear and C. EbeIIng, "The Practical Application of Retiming to the Design of High-Peff~ Systems," Proceedings of the IEEE International Conference on Computer-Aided Design, pp. 288- 295, Nove~ 1993.

Digital Library

[8]

T. Soyata and E. G. Friedman, "Synchronous Pefformmu~ and Reliability Improvement in Pipelined ASICs," Proceedings of the ASIC Conference, September 1994.

[9]

S. Simon, E. Bernard, M. Sauer, and J. A. Nossek, "A New Retiming Algorithm for Circuit Design," Proceedings of the IEEE International Symposium on Circuits and Systems, pp. 4.35-4.38, May/June 1994.

[10]

L. Chao and E. H. Slut, "Retiming and Clock Skew for Synchfoaons Systems," Proceedings of the IEEE Interna~onal Symposium on Circuits and Systems, pp. 1.283-I.286, May/June 1994.

[11]

E.G. Friedman and J. H. Mulligan, "Clock Frequency and Latency in Synchronous Digital Systems," IEEE Transactions on Signal Processing, VoL 39, No. 4, pp. 930-934, April 1991.

[12]

E.G. Friedman, "Clock Distribution Design in VLSI Circtdts -- an Overview," Proceedings of the IEEE International Symposiwn on Circuits and Systems, pp. 1475-1478, May 1993.

[13]

K.A. Sakallah, T. N. Medge, T. M. Bmks, and E. S. Davidsm, "Synchronization of Pipelines," IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, VoL CAD--12, No. 8, pp. I 132-1146, August 1993.

[14]

S. Malik, E. M. Sentovich, R. K. Brayton, and A. Sangiovanni- Vincentelli, "Retiming and Resynttz~is: Optimizing Sequential Networks with Combinatorial Techniques," IEEE Transactions on Computer-Aided Design, VoL CAD-10, No. 1, pp. 74-84, January 1991.

[15]

E.L. Lawler, Combinatorial Optim~on: Networks and Matroide. Holt, Rinehart and Winston, NewYork, 1976.

[16]

R. Lisanke, "Logic Synthesis and Optimization Benchnmrks User Guide:. Version 2.0," Tech. Rep., Microelectronics Center of North Carolina, December 1988.

[17]

S. Yang, "Logic Synthesis and Optimization Benchmarks User Guide: Version 3.0," Tech. Rep., Microelectronics Center of North Carolina, January 1991.

Cited By

Chu CYoung ETong DDechu S(2003)Retiming with Interconnect and Gate DelayProceedings of the 2003 IEEE/ACM international conference on Computer-aided design10.5555/996070.1009894Online publication date: 9-Nov-2003
https://dl.acm.org/doi/10.5555/996070.1009894
Seidl UEckl KJohannes F(2003)Performance-Directed Retiming for FPGAs Using Post-Placement Delay InformationProceedings of the conference on Design, Automation and Test in Europe - Volume 110.5555/789083.1022818Online publication date: 3-Mar-2003
https://dl.acm.org/doi/10.5555/789083.1022818
Neumann IKunz WErnst R(2001)Placement driven retiming with a coupled edge timing modelProceedings of the 2001 IEEE/ACM international conference on Computer-aided design10.5555/603095.603115(95-102)Online publication date: 4-Nov-2001
https://dl.acm.org/doi/10.5555/603095.603115
Show More Cited By

Index Terms

Retiming with non-zero clock skew, variable register, and interconnect delay
1. Hardware
  1. Electronic design automation
    1. Logic synthesis
      1. Circuit optimization

Recommendations

Delay insertion method in clock skew scheduling
ISPD '05: Proceedings of the 2005 international symposium on Physical design

This paper describes a delay insertion method that improves the efficiency of clock skew scheduling. Clock skew scheduling is performed on synchronous circuits in order to improve the performance of a circuit; most often by permitting the circuit to ...
Delay insertion method in clock skew scheduling

This paper describes a delay insertion method that improves the efficiency of clock skew scheduling. It is shown that reconvergent paths limit the improvement of circuit performance achievable through clock skew scheduling. A delay insertion method is ...
Type-matching clock tree for zero skew clock gating
DAC '08: Proceedings of the 45th annual Design Automation Conference

Clock skew minimization is always very important in the clock tree synthesis. Due to clock gating, the clock tree may include different types of logic gates, e.g., AND gates, OR gates, and buffer gates. If the logic gates at the same level are in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

November 1994

771 pages

ISBN:0897916905

Chairmen:
Jochen A. G. Jess
Eindhoven Univ. of Technology, Eindhoven, The Netherlands
,
Richard Rudell
Synopsys, Inc., Mountain View, CA

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS: Computer Society

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 06 November 1994

Check for updates

Qualifiers

Article

Conference

ICCAD '94

Sponsor:

SIGDA
IEEE-CS

ICCAD '94: International Conference on Computer Aided Design

November 6 - 10, 1994

California, San Jose, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
192
Total Downloads

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

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chu CYoung ETong DDechu S(2003)Retiming with Interconnect and Gate DelayProceedings of the 2003 IEEE/ACM international conference on Computer-aided design10.5555/996070.1009894Online publication date: 9-Nov-2003
https://dl.acm.org/doi/10.5555/996070.1009894
Seidl UEckl KJohannes F(2003)Performance-Directed Retiming for FPGAs Using Post-Placement Delay InformationProceedings of the conference on Design, Automation and Test in Europe - Volume 110.5555/789083.1022818Online publication date: 3-Mar-2003
https://dl.acm.org/doi/10.5555/789083.1022818
Neumann IKunz WErnst R(2001)Placement driven retiming with a coupled edge timing modelProceedings of the 2001 IEEE/ACM international conference on Computer-aided design10.5555/603095.603115(95-102)Online publication date: 4-Nov-2001
https://dl.acm.org/doi/10.5555/603095.603115
Ranjan ASrivastava AKarnam VSarrafzadeh MRoy KKang SKoh C(2001)Layout aware retimingProceedings of the 11th Great Lakes symposium on VLSI10.1145/368122.368153(25-30)Online publication date: 1-Mar-2001
https://dl.acm.org/doi/10.1145/368122.368153
Lalgudi KPapaefthymiou MPreas B(1995)DELAYProceedings of the 32nd annual ACM/IEEE Design Automation Conference10.1145/217474.217546(304-309)Online publication date: 1-Jan-1995
https://dl.acm.org/doi/10.1145/217474.217546

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Table of Conten