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

research-article

Wire retiming as fixpoint computation

Authors:

Hai ZhouAuthors Info & Claims

IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Volume 13, Issue 12

Pages 1340 - 1348

https://doi.org/10.1109/TVLSI.2005.862726

Published: 01 December 2005 Publication History

Abstract

In system-on-chips (SOCs), a nonnegligible part of operation time is spent on global wires with long delays. Retiming-that is moving flip-flops in a circuit without changing its functionality-can be explored to pipeline long interconnect wires in SOC designs. The problem of retiming over a netlist of macro-blocks, where the internal structures may not be changed and flip-flops may not be inserted on some wire segments is called the wire retiming problem. In this paper, we formulate the constraints of the wire retiming problem as a fixpoint computation and use an iterative algorithm to solve it. Experimental results show that this approach is multiple orders more efficient than the previous one.

References

[1]

P. Cocchini, "Concurrent flip-flop and repeater insertion for high performance integrated circuits," in Proc. Intl. Conf. on Computer-Aided Design, 2002, pp. 268-273.

Digital Library

[2]

N. Akkiraju and M. Mohan, "Spec based flip-flop and buffer insertion," in Proc. Int. Conf. on Computer Design, 2003, pp. 270-275.

Digital Library

[3]

S. Hassoun and C. J. Alpert, "Optimal path routing in single- and multiple-clock domain systems," IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 22, no. 11, pp. 1580-1588, Nov. 2003.

Digital Library

[4]

C. E. Leiserson, F. M. Rose, and J. B. Saxe, "Optimizing synchronous circuitry by retiming," in Proc. 3rd Caltech Conf. Advanced Research in VLSI, 1983, pp. 86-116.

[5]

N. Shenoy and R. Rudell, "Efficient implementation of retiming," in Proc. Int. Conf. on Computer-Aided Design, 1994, pp. 226-233.

Digital Library

[6]

G. Even, I. Y. Spillinger, and L. Stok, "Retiming revisited and reversed," IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 15, no. 3, pp. 348-357, Mar. 1996.

Digital Library

[7]

R. B. Deokar and S. S. Sapatnekar, "A fresh look at retiming via clock skew optimization," in Proc. Design Automation Conf., 1995, pp. 310-315.

Digital Library

[8]

K. N. Lalgudi and M. C. Papaefthymiou, "An efficient tool for retiming with realistic delay modeling," in Proc. Design Automation Conf., San Francisco, CA, Jun. 1995.

Digital Library

[9]

P. Pan, A. K. Karandikar, and C. L. Liu, "Optimal clock period clustering for sequential circuits with retiming," IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 17, no. 6, pp. 489-498, Jun. 1998.

Digital Library

[10]

H. Zhou, "Deriving a new efficient algorithm for min-period retiming," in Proc. Asian and South Pacific Design Automation Conf., 2005.

Digital Library

[11]

T. Soyata, E. G. Friedman, and J. H. Mulligan, "Incorporating interconnect, register, and clock distribution delays into the retiming process," IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 16, no. 1, pp. 105-120, Jan. 1997.

Digital Library

[12]

J. Cong and S. K. Lim, "Physical planning with retiming," in Proc. Int. Conf. on Computer-Aided Design, Nov. 2000, pp. 2-7.

Digital Library

[13]

H. Zhou and C. Lin, "Retiming for wire pipelining in system-on-chip," IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 23, no. 9, pp. 1338-1345, Sep. 2004.

Digital Library

[14]

C. Chu, E. F. Y. Young, D. K. Y. Tong, and S. Dechu, "Retiming with interconnect and gate delay," in Proc. Int. Conf. on Computer-Aided Design, 2003, pp. 221-226.

Digital Library

[15]

D. K. Y. Tong and E. F. Y. Young, "Performance-driven register insertion in placement," in Int. Symp. on Physical Design, 2004, pp. 53-60.

Digital Library

[16]

H. Zhou, D. F. Wong, I.-M. Liu, and A. Aziz, "Simultaneous routing and buffer insertion with restrictions on buffer locations," IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 19, no. 7, pp. 819-824, 2000.

Digital Library

[17]

R. H. J. M. Otten and R. Brayton, "Planning for performance," in Proc. Design Automation Conf., 1998, pp. 122-127.

Digital Library

[18]

B. A. Davey and H. A. Priestley, Introduction to Lattices and Order. Cambridge, U.K.: Cambridge Univ. Press, 1990.

[19]

T. H. Cormen, C. E. Leiserson, and R. H. Rivest, Introduction to Algorithms. Cambridge, MA: MIT Press, 1989.

Digital Library

[20]

P. Cousot and R. Cousot, "Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints," in ACM Symp. on Principles of Programming Languages, Los Angeles, CA, Jan. 1977, pp. 238-252.

Digital Library

[21]

G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, "Multilevel hypergraph partitioning: Application in VLSI domain," in Proc. Design Automation Conf., 1997, pp. 526-529.

Digital Library

Cited By

Lin CWang JZhou H(2019)Clustering for processing rate optimizationIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2006.88639914:11(1264-1275)Online publication date: 21-Nov-2019
https://dl.acm.org/doi/10.1109/TVLSI.2006.886399
Lin CXie AZhou HLauwereins RMadsen J(2007)Design closure driven delay relaxation based on convex cost network flowProceedings of the conference on Design, automation and test in Europe10.5555/1266366.1266382(63-68)Online publication date: 16-Apr-2007
https://dl.acm.org/doi/10.5555/1266366.1266382
Lin CZhou HSentovich E(2006)An efficient retiming algorithm under setup and hold constraintsProceedings of the 43rd annual Design Automation Conference10.1145/1146909.1147149(945-950)Online publication date: 24-Jul-2006
https://dl.acm.org/doi/10.1145/1146909.1147149

Wire retiming as fixpoint computation

Recommendations

Optimal wire retiming without binary search

The problem of retiming over a netlist of macroblocks to achieve minimal clock period, where block internal structures may not be changed and flip-flops may not be inserted on some wire segments, is called the optimal wire retiming problem. This paper ...
Retiming for wire pipelining in system-on-chip

At the integration scale of system-on-chips (SOCs), the conflicts between communication and computation will become prominent even on a chip. A big fraction of system time will shift from computation to communication. In synchronous systems, a large ...
Multilevel global placement with retiming
DAC '03: Proceedings of the 40th annual Design Automation Conference

Multiple clock cycles are needed to cross the global interconnects for multi-gigahertz designs in nanometer technologies. For synchronous designs, this requires retiming and pipelining on global interconnects. In this paper, we present a practical ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Very Large Scale Integration (VLSI) Systems

IEEE Transactions on Very Large Scale Integration (VLSI) Systems Volume 13, Issue 12

December 2005

74 pages

ISSN:1063-8210

Issue’s Table of Contents

Copyright © 2005.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 December 2005

Revised: 30 May 2005

Received: 12 August 2004

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lin CWang JZhou H(2019)Clustering for processing rate optimizationIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2006.88639914:11(1264-1275)Online publication date: 21-Nov-2019
https://dl.acm.org/doi/10.1109/TVLSI.2006.886399
Lin CXie AZhou HLauwereins RMadsen J(2007)Design closure driven delay relaxation based on convex cost network flowProceedings of the conference on Design, automation and test in Europe10.5555/1266366.1266382(63-68)Online publication date: 16-Apr-2007
https://dl.acm.org/doi/10.5555/1266366.1266382
Lin CZhou HSentovich E(2006)An efficient retiming algorithm under setup and hold constraintsProceedings of the 43rd annual Design Automation Conference10.1145/1146909.1147149(945-950)Online publication date: 24-Jul-2006
https://dl.acm.org/doi/10.1145/1146909.1147149

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents