research-article

A general model for performance optimization of sequential systems

Authors:

Dmitry Bufistov,

Jordi Cortadella,

Mike Kishinevsky,

Sachin SapatnekarAuthors Info & Claims

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

Pages 362 - 369

Published: 05 November 2007 Publication History

Abstract

Retiming, c-slow retiming and recycling are different transformations for the performance optimization of sequential circuits. For retiming and c-slow retiming, different models that provide exact solutions have already been proposed. An exact model for recycling was yet unknown. This paper presents a general formulation that covers the combination of the three schemes for performance optimization. It provides an exact model based on integer linear programming that resorts to the structural theory of marked graphs. A set of experiments has been designed to show the benefits in performance obtained by combining retiming and recycling. The results also show the applicability of the method in large circuits.

References

[1]

C. E. Leiserson and J. B. Saxe, "Retiming synchronous circuitry." Algorithmica, vol. 6, no. 1, pp. 5--35, 1991.

Digital Library

[2]

N. V. Shenoy, "Retiming: Theory and practice." Integration, the VLSI Journal, vol. 22, no. 1, pp. 1--21, 1997.

Digital Library

[3]

S. S. Sapatnekar and R. B. Deokar, "Utilizing the timing shew equivalence in a practical algorithm for retiming large circuits," IEEE Transactions on Computer-Aided Design, vol. 15, no. 10, pp. 1237--1248, Oct. 1996.

Digital Library

[4]

C. Lin and H. Zhou, "Retiming for wire pipelining in systems-on-chip." in Proc. International Conf. Computer-Aided Design (ICCAD), Nov. 2003, pp. 215--220.

Digital Library

[5]

V. Nookala and S. S. Sapatnekar, "A method for correcting the functionality of a wire-pipelined circuit," in Proc. ACM/IEEE Design Automation Conference, June 2004, pp. 570--575.

Digital Library

[6]

L. P. Carloni, K. L. McMillan, A Saldanha, and A. L. Sagiovanni-Vincentelli, "A methodology for correct-by-construction latency insensitive design," in Proc. International Conf. Computer-Aided Design (ICCAD), Nov. 1999, pp. 309--315.

Digital Library

[7]

L. P. Carloni and A. L. Sangiovanni-Vincentelli, "Performance analysis and optimization of latency insensitive systems," in Proc. ACM/IEEE Design Automation Conference, June 2000, pp. 361--367.

Digital Library

[8]

T. E. Williams, "Performance of iterative computation in self-timed rings," Journal of VLSI Signal Processing, vol. 7, no. 1/2, pp. 17--31, Feb. 1994.

Digital Library

[9]

R. Manohar and A. J. Martin, "Slack elasticity in concurrent computing." in Proc. 4th International Conference on the Mathematics of Program Construction, ser. Lecture Notes in Computer Science, J. Jeuring, Ed., vol. 1422, 1998, pp. 272--285.

Digital Library

[10]

P. A. Beerel, N.-H. Kim, A. Lines, and M. Davies, "Slack matching asynchronous designs," in Proc. of the 12th Int. Symp. on Asynchronous Circuits and Systems, 2006.

Digital Library

[11]

P. Prakash and A. J. Martin, "Slack matching quasi delay-insensitive circuits," in Proc. of the 12th Int. Symp. on Asynchronous Circuits and Systems, 2006.

Digital Library

[12]

M. R. Casu and L. Macchiarulo, "A new approach to latency insensitive design," in Proc. Digital Automation Conference (DAC), June 2004, pp. 576--581.

Digital Library

[13]

J. Cortadella, M. Kishinevsky, and B. Grundmann, "Synthesis of synchronous elastic architectures," in Proc. ACM/IEEE Design Automation Conference, July 2006, pp. 657--662.

Digital Library

[14]

L. P. Carloni and A. L. Sangiovanni-Vincentelli, "Combining retiming and recycling to optimize the performance of synchronous circuits," in 16th Symp. on Integrated Circuits and System Design (SBCCI), Sept. 2003, pp. 47--52.

Digital Library

[15]

H. J. Touati and R. K. Brayton, "Computing the initial states of retimed circuits," IEEE Trans. on CAD of Integrated Circuits and Systems, vol. 12, no. 1, pp. 157--162, 1993.

Digital Library

[16]

R. Lu and C.-K. Koh, "Performance analysis of latency-insensitive systems," IEEE Transactions on Computer-Aided Design, vol. 25, no. 3, pp. 469--483, 2006.

Digital Library

[17]

T. Murata, "Petri Nets: Properties, analysis and applications," Proceedings of the IEEE, pp. 541--580, Apr. 1989.

[18]

F. Commoner, A. W. Holt, S. Even, and A. Pnueli, "Marked directed graphs," Journal of Computer and System Sciences, vol. 5, pp. 511--523, 1971.

Digital Library

[19]

T. Murata, "Circuit theoretic analysis and synthesis of marked graphs," IEEE Trans. Circuits and Systems, vol. CAS-24, no. 7, pp. 400--405, July 1977.

[20]

C. Ramchandani, "Analysis of asynchronous concurrent systems by Petri nets," Project MAC, TR-120, M.I.T., Cambridge, MA, 1974.

Digital Library

[21]

M. C. Papaefthymiou. "Understanding retiming through maximum average-delay cycles," Mathematical Systems Theory, vol. 27, no. 1, pp. 65--84, 1994.

Digital Library

[22]

J. Campos, G. Chiola, and M. Silva, "Ergodicity and throughput bounds for petri nets with unique consistent firing count vector," IEEE Transactions on Software Engineering, vol. 17, no. 2, pp. 117--125, 1991.

Digital Library

[23]

C. Papadimitriou, Computational Complexity. Addison-Wesley, 1995.

[24]

"CPLEX," http://www.ilog.com/products/cplex.

Cited By

Josipović LSheikhha SGuerrieri AIenne PCortadella J(2021)Buffer Placement and Sizing for High-Performance Dataflow CircuitsACM Transactions on Reconfigurable Technology and Systems10.1145/347705315:1(1-32)Online publication date: 9-Nov-2021
https://dl.acm.org/doi/10.1145/3477053
(2010)Elastic systemsProceedings of the Eighth ACM/IEEE International Conference on Formal Methods and Models for Codesign10.1109/MEMCOD.2010.5558639(149-158)Online publication date: 1-Jul-2010
https://dl.acm.org/doi/10.1109/MEMCOD.2010.5558639
Bufistov DCortadella JGalceran-Oms MJúlvez JKishinevsky M(2009)Retiming and recycling for elastic systems with early evaluationProceedings of the 46th Annual Design Automation Conference10.1145/1629911.1629988(288-291)Online publication date: 26-Jul-2009
https://dl.acm.org/doi/10.1145/1629911.1629988

Recommendations

General division algorithms for residue number systems
Extended sequential logic for synchronous circuit optimization and its applications

In this paper, we present a new approach for the extension of sequential logic functionality of D flip-flop in order to perform an additional Boolean function simultaneously along with its usual bit-storage function. We show that a combinational ...
Retiming-based factorization for sequential logic optimization

Current sequential optimization techniques apply a variety of logic transformations that mainly target the combinational logic component of the circuit. Retiming is typically applied as a postprocessing step to the gate-level implementation obtained ...

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

3
Total Citations
View Citations
138
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

Josipović LSheikhha SGuerrieri AIenne PCortadella J(2021)Buffer Placement and Sizing for High-Performance Dataflow CircuitsACM Transactions on Reconfigurable Technology and Systems10.1145/347705315:1(1-32)Online publication date: 9-Nov-2021
https://dl.acm.org/doi/10.1145/3477053
(2010)Elastic systemsProceedings of the Eighth ACM/IEEE International Conference on Formal Methods and Models for Codesign10.1109/MEMCOD.2010.5558639(149-158)Online publication date: 1-Jul-2010
https://dl.acm.org/doi/10.1109/MEMCOD.2010.5558639
Bufistov DCortadella JGalceran-Oms MJúlvez JKishinevsky M(2009)Retiming and recycling for elastic systems with early evaluationProceedings of the 46th Annual Design Automation Conference10.1145/1629911.1629988(288-291)Online publication date: 26-Jul-2009
https://dl.acm.org/doi/10.1145/1629911.1629988

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