Article

Free access

A methodology for correct-by-construction latency insensitive design

Authors:

Luca P. Carloni,

Kenneth L. McMillan,

Alexander Saldanha,

Alberto L. Sangiovanni-VincentelliAuthors Info & Claims

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

Pages 309 - 315

Published: 07 November 1999 Publication History

Abstract

In Deep Sub-Micron (DSM) designs, performance will depend critically on the latency of long wires. We propose a new synthesis methodology for synchronous systems that makes the design functionally insensitive to the latency of long wires. Given a synchronous specification of a design, we generate a functionaly equivalent synchronous implementation that can tolerate arbitrary communication latency between latches. By using latches we can break a long wire in short segments which can be traversed while meeting a single clock cycle constraint. The overall goal is to obtain a design that is robust with respect to delays of long wires, in a shorter time by reducing the multiple iterations between logical and physical design, and with performance that is optimized with respect to the speed of the single components of the design. In this paper we describe the details of the proposed methodology as well as report on the latency insensitive design of PDLX, an out-of-order microprocessor with speculative-execution.

References

[1]

R Beerel and T.H.-Y. Meng. Automatic gate-level synthesis of speed-independent circuits. In Proc. International Conf. Computer- Aided Design (ICCAD), pages 581-587. IEEE Computer Society Press, November 1992.]]

Digital Library

[2]

Janusz A. Brzozowski and Jo C. Ebergen. On the delay-sensitivity of gate networks. IEEE Transactions on Computers, 41(11):1349- 1360, November 1992.]]

Digital Library

[3]

Steven M. Burns. Performance Analysis and Optimization of Asynchronous Circuits. PhD thesis, California Institute of Technology, 1991.]]

Digital Library

[4]

L. E Carloni, K. L. McMillan, and A. L. Sangiovanni-Vincentelli. Latency Insensitive Protocols. In Proc. of the l lth Intl. Conf. on Computer-Aided Verification (N. Halbwachs and D. Peled editors), pages 123-133. LNCS 1633, Springer, July 1999.]]

Digital Library

[5]

Wesley A. Clark. Macromodular computer systems. In AFIPS Conference Proceedings: 1967 Spring Joint Computer Conference, volume 30, pages 335-336, Atlantic City, NJ, 1967. Academic Press.]]

Digital Library

[6]

Wesley A. Clark and Charles E. Molnar. The promise of macromodular systems. In Digest of Papers of the Six Annual IEEE Computer Society International Conference, pages 309-312, San Francisco, CA, 1972. IEEE Press.]]

[7]

J. Cong. Challenges and Opportunities for Design Innovations in Nanometer Technologies. In SRC Design Sciences Concept Paper, December 1997.]]

[8]

J. Cong, L. He, K.Y. Khoo, C.K. Koh, and Z. Pan. Interconnect Design for Deep Submicron ICs. In Proc. Intl. Conf. on Computer- Aided Design, pages 478-585. IEEE, November 1997.]]

Digital Library

[9]

D. Matzke. Will Physical Scalability Sabotage Performance Gains? IEEE Computer, 8(9):37-39, September 1997.]]

Digital Library

[10]

D. Sylvester and K. Keutzer. Getting to the Bottom of Deep Submicron. In Proc. Intl. Conf. on Computer-Aided Design, November 1998.]]

Digital Library

[11]

A1 Davis and Steven M. Nowick. Asynchronous circuit design: Motivation, background, and methods. In Graham Birtwistle and A1 Davis, editors, Asynchronous Digital Circuit Design, Workshops in Computing, pages 1-49. Springer-Verlag, 1995.]]

[12]

David L. Dill. Trace Theory for Automatic Hierarchical Verification of Speed-Independent Circuits. ACM Distinguished Dissertations. MIT Press, 1989.]]

Digital Library

[13]

Jo C. Ebergen. A formal approach to designing delay-insensitive circuits. Distributed Computing, 5(3):107-119, 1991.]]

Digital Library

[14]

W. Gosti, A. Narayan, R.K. Brayton, and A. Sangiovanni- Vincentelli. Wireplanning in Logic Synthesis. In Proc. Intl. Conf. on Computer-Aided Design, pages 26-33. IEEE, November 1998.]]

Digital Library

[15]

John L. Hennessy and David A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, San Mateo, CA, 1996.]]

Digital Library

[16]

S. Hojat and P. Villarrubia. An Integrated Placement and Synthesis Approach for Timing Closure of Power PC Microprocessors. In Proc. Intl. Conf. on Computer Design. VLSI in Computers and Processors, pages 206-210. IEEE, October 1997.]]

Digital Library

[17]

M. B. Josephs and J. T. Udding. An overview of DI algebra. In Proc. Hawaii International Conf. System Sciences, volume I. IEEE Computer Society Press, January 1993.]]

[18]

L.N. Kannan, ER. Suaris, and H. Fang. A Methodology and Algorithms for Post-Placement Delay Optimization. In Proc. of the Design Automation Conf., pages 327-332, June 1994.]]

Digital Library

[19]

H. Kapadia and M. Horowitz. Using Partitioning to Help Convergence in the Standard-Cell Design Automation Method. In Proc. of the Design Automation Conf., pages 592-597, June 1999.]]

Digital Library

[20]

A. Kondratyev, M. Kishinevsky, B. Lin, E Vanbekbergen, and A. Yakovlev. Basic gate implementation of speed-independent circuits. In Proc. ACM/IEEE Design Automation Conference, pages 56-62, June 1994.]]

Digital Library

[21]

E. A. Lee and A. Sangiovanni-Vincentelli. A Framework for Comparing Models of Computation. IEEE Transactions on Computer- Aided Design, 17(12):1217-1229, December 1998.]]

Digital Library

[22]

A. Lu, H. Eisenmann, G. Stenz G., and F.M. Johannes. Combining Technology Mapping with Post-Placement Resynthesis for Performance Optimization. In Proc. Intl. Conf. on Computer Design. VLSI in Computers and Processors, pages 616-621. IEEE, October 1998.]]

Digital Library

[23]

Alain J. Martin. The limitations to delay-insensitivity in asynchronous circuits. In William J. Dally, editor, Advanced Research in VLSI, pages 263-278. MIT Press, 1990.]]

Digital Library

[24]

Charles E. Molnar, Ting-Pien Fang, and Frederick U. Rosenberger. Synthesis of delay-insensitive modules. In Henry Fuchs, editor, 1985 Chapel Hill Conference on Very Large Scale Integration, pages 67- 86. Computer Science Press, 1985.]]

[25]

R. H. J. M. Otten and R. K. Brayton. Planning for Performance. In Proc. of the Design Automation Conf., pages 122-127, June 1998.]]

Digital Library

[26]

Fred U. Rosenberger, Charles E. Molnar, Thomas J. Chaney, and Ting-Pien Fang. Q-modules: Internally clocked delay-insensitive modules. IEEE Transactions on Computers, C-37(9):1005-1018, September 1988.]]

Digital Library

[27]

A. Salek, J. Lou, and M. Pedram. A DSM design flow: Putting Floorplanning, Technology Mapping and Gate Placemente Together. In Proc. of the Design Automation Conf., pages 287-290, June 1998.]]

Digital Library

[28]

K. Sato, M. Kawarabayashi, H. Emura, and N. Maeda. Post-Layout Optimization for Deep Submicron Design. In Proc. of the Design Automation Conf., pages 740-745, June 1996.]]

Digital Library

[29]

S.J. Schaffer and W.W. LaRue. BONES DESIGNER: a Graphical Environment for Discrete-Event Modeling and Simulation. In MAS- COTS '94. Proc. of the 2nd. Intl. Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, pages 371-374, Los Alamitos - CA, February 1994. IEEE.]]

Digital Library

[30]

The DLX Software. ftP://max'stanf~rd'edu/pub/hennessy-patters~n's~fiware"]]

[31]

R. M. Tomasulo. An Efficient Algorithm for Exploiting Multiple Arithmetic Units. IBM Journal Research and Development, 11:25- 33, January 1967.]]

Digital Library

[32]

Jan Tijmen Udding. A formal model for defining and classifying delay-insensitive circuits. Distributed Computing, 1(4):197-204, 1986.]]

Cited By

Carloni LCota EGuglielmo GGiri DKwon JMantovani PPiccolboni LPetracca M(2019)Teaching Heterogeneous Computing with System-Level Design MethodsProceedings of the Workshop on Computer Architecture Education10.1145/3338698.3338893(1-8)Online publication date: 22-Jun-2019
https://dl.acm.org/doi/10.1145/3338698.3338893
Khailany BKhmer EVenkatesan RClemons JEmer JFojtik MKlinefelter APellauer MPinckney NShao YSrinath STorng CXi SZhang YZimmer B(2018)A modular digital VLSI flow for high-productivity SoC designProceedings of the 55th Annual Design Automation Conference10.1145/3195970.3199846(1-6)Online publication date: 24-Jun-2018
https://dl.acm.org/doi/10.1145/3195970.3199846
(2015)Implementing latency-insensitive dataflow blocksProceedings of the 2015 ACM/IEEE International Conference on Formal Methods and Models for Codesign10.1109/MEMCOD.2015.7340485(179-187)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1109/MEMCOD.2015.7340485
Show More Cited By

Index Terms

A methodology for correct-by-construction latency insensitive design
1. Applied computing
  1. Physical sciences and engineering
    1. Electronics
    2. Engineering
2. Hardware
  1. Emerging technologies
  2. Robustness

Recommendations

Construction of Latency-Bounded Clock Trees
ISPD '16: Proceedings of the 2016 on International Symposium on Physical Design

Clock trees must be constructed to function even under the influence of on-chip variations (OCV). Bounding the latency of a clock tree, i.e., the maximum delay from the tree root to any sequential element, is important because the latency correlates ...
A Reliable Clock Tree Design Methodology for ASIC Designs
ISQED '00: Proceedings of the 1st International Symposium on Quality of Electronic Design

In deep sub-micron era, an ASIC chip may contain millions of gates and have the requirements of low power and high performance. The ability to construct multiple clock trees effectively is very important. A clock tree design methodology is presented. At ...
Timing closure through a globally synchronous, timing partitioned design methodology
DAC '04: Proceedings of the 41st annual Design Automation Conference

A method to mitigate timing problems due to global wire delays is proposed. The method follows closely a fully synchronous design flow and utilizes only true digital library elements. The design is partitioned into isochronous blocks at system level, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

November 1999

613 pages

ISBN:0780358325

Sponsors

IEEE-EDS: Electronic Devices Society
SIGDA: ACM Special Interest Group on Design Automation
IEEE-CAS: Circuits & Systems
IEEE-CS: Computer Society

Publisher

IEEE Press

Publication History

Published: 07 November 1999

Check for updates

Qualifiers

Article

Conference

ICCAD '99

Sponsor:

IEEE-EDS
SIGDA
IEEE-CAS
IEEE-CS

ICCAD '99: The International Conference on Computer Aided Design.

November 7 - 11, 1999

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

46
Total Citations
View Citations
300
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)7

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Carloni LCota EGuglielmo GGiri DKwon JMantovani PPiccolboni LPetracca M(2019)Teaching Heterogeneous Computing with System-Level Design MethodsProceedings of the Workshop on Computer Architecture Education10.1145/3338698.3338893(1-8)Online publication date: 22-Jun-2019
https://dl.acm.org/doi/10.1145/3338698.3338893
Khailany BKhmer EVenkatesan RClemons JEmer JFojtik MKlinefelter APellauer MPinckney NShao YSrinath STorng CXi SZhang YZimmer B(2018)A modular digital VLSI flow for high-productivity SoC designProceedings of the 55th Annual Design Automation Conference10.1145/3195970.3199846(1-6)Online publication date: 24-Jun-2018
https://dl.acm.org/doi/10.1145/3195970.3199846
(2015)Implementing latency-insensitive dataflow blocksProceedings of the 2015 ACM/IEEE International Conference on Formal Methods and Models for Codesign10.1109/MEMCOD.2015.7340485(179-187)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1109/MEMCOD.2015.7340485
Casu MMantovani P(2015)A synchronous latency-insensitive RISC for better than worst-case designIntegration, the VLSI Journal10.1016/j.vlsi.2014.01.00348:C(72-82)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1016/j.vlsi.2014.01.003
Chen YZeng XZhou HFettweis GNebel W(2014)Recovery-based resilient latency-insensitive systemsProceedings of the conference on Design, Automation & Test in Europe10.5555/2616606.2616733(1-6)Online publication date: 24-Mar-2014
https://dl.acm.org/doi/10.5555/2616606.2616733
Sinha RRoop PSalcic ZBasu SRosenstiel WMacii E(2012)Correct-by-construction multi-component SoC designProceedings of the Conference on Design, Automation and Test in Europe10.5555/2492708.2492871(647-652)Online publication date: 12-Mar-2012
https://dl.acm.org/doi/10.5555/2492708.2492871
Méry DSingh NTrong GHluchy LQuyet TCastelli EDuc KChi MTran V(2012)Critical systems development methodology using formal techniquesProceedings of the 3rd Symposium on Information and Communication Technology10.1145/2350716.2350720(3-12)Online publication date: 23-Aug-2012
https://dl.acm.org/doi/10.1145/2350716.2350720
Huang JChen YHo Y(2011)Throughput optimization for latency-insensitive system with minimal queue insertionProceedings of the 16th Asia and South Pacific Design Automation Conference10.5555/1950815.1950932(585-590)Online publication date: 25-Jan-2011
https://dl.acm.org/doi/10.5555/1950815.1950932
Galceran-Oms MGotmanov ACortadella JKishinevsky M(2011)Microarchitectural Transformations Using ElasticityACM Journal on Emerging Technologies in Computing Systems10.1145/2043643.20436487:4(1-24)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1145/2043643.2043648
Casu MColazzo SMantovani PAtienza DXie YAyala JStevens K(2011)Coupling latency-insensitivity with variable-latency for better than worst case designProceedings of the 21st edition of the great lakes symposium on Great lakes symposium on VLSI10.1145/1973009.1973043(163-168)Online publication date: 2-May-2011
https://dl.acm.org/doi/10.1145/1973009.1973043
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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

Media

Figures

Other

Tables

View Table of Contents