research-article

Implementing Sequential Machines as Self-Timed Circuits

Authors:

Ilana David,

Ran Ginosar,

Michael YoeliAuthors Info & Claims

IEEE Transactions on Computers, Volume 41, Issue 1

Pages 12 - 17

https://doi.org/10.1109/12.123378

Published: 01 January 1992 Publication History

Publisher Site

Abstract

A self-timed finite state machine (FSM) is described. It is based on a formally proven, efficient implementation of self-timed combinational logic and a self-timed master-slave register. Temporal behavioral constraints are formalized, and the system is shown to abide by them. The synthesis method is algorithmic and serves as an automatic compiler of self-timed FSMs. The specification of the FSM is given by a state table, similar to that of synchronous machines. The circuit operates according to a sequence of events that replaces the role of the central clock in the synchronous FSM. The inputs and outputs of the circuit are double-rail (or ternary) and the circuit produces a completion signal. The method is compared with other approaches.

References

[1]

{1} T. S. Anantharaman, "A delay insensitive regular expression recognizer," IEEE VLSI Tech. Bull., vol. 1, no. 2, Sept. 1986.

Google Scholar

[2]

{2} T. A. Chu, "Synthesis of self-timed VLSI circuits from graph-theoretic specifications," Ph.D. dissetation, Massachusetts Institute of Technology, 1987.

Google Scholar

[3]

{3} I. David, R. Ginosar, and M. Yoeli, "An efficient implementation of Boolean functions as self-timed circuits," IEEE Trans. Comput., this issue, pp. 2-11.

Crossref

Google Scholar

[4]

{4} I. David, R. Ginosar, and M. Yoeli, "Implementing sequential machines as self-timed circuits," Tech. Rep. 692, Dep. Elec. Eng., Technion, Nov. 1988.

Google Scholar

[5]

{5} J. C. Ebergen, "Translating programs into delay-insensitive circuits," Ph.D. dissertation, Eindhoven Univ. of Technology, 1987.

Google Scholar

[6]

{6} Z. Kohavi, Switching and Finite Automata Theory, 2nd ed. New York: McGraw-Hill, 1978.

Crossref

Google Scholar

[7]

{7} A. J. Martin, "Compiling communicating processes into delay insensitive VLSI circuits," Distributed Comput., vol. 1, no. 3, pp. 226-234, 1986.

Crossref

Google Scholar

[8]

{8} A. J. Martin, "Programming in VLSI: From communicating processes to delay-insensitive circuits," Caltech-CS-TR-89-1, Dep. Comput. Sci., California Institute of Technology, 1989.

Crossref

Google Scholar

[9]

{9} C. Mead and L. Conway, Introduction to VLSI Systems. Reading, MA: Addison-Wesley, 1980.

Digital Library

Google Scholar

[10]

{10} C. E. Molnar, T. P. Fan, and F. U. Rosenberger, "Synthesis of delay-insensitive modules," in Proc. 1985 Chapel Hill Conf. VLSI, Chapel Hill, NC, May 15-27, 1985, pp. 67-86.

Google Scholar

[11]

{11} M. Rem, "Concurrent computations and VLSI circuits," in Control Flow and Data Flow; Concepts of Distributed Computing, M. Broy, Ed. Berlin, Germany, Springer-Verlag, 1985, pp. 399-437.

Crossref

Google Scholar

[12]

{12} C. L. Seitz, "System timing," in Introduction to VLSI Systems, C. Mead and L. Conway, Eds. Reading, MA: Addison-Wesley, 1980, pp, 218-262.

Google Scholar

[13]

{13} J. L. A., Van de Snepscheut, Trace Theory and VLSI Design, LNCS 200, 1985.

Google Scholar

Cited By

View all

Tadros RBeerel P(2020)A Theoretical Foundation for Timing Synchronous Systems Using Asynchronous StructuresACM Transactions on Design Automation of Electronic Systems10.1145/337335525:2(1-28)Online publication date: 3-Feb-2020
https://dl.acm.org/doi/10.1145/3373355
Yeandel JThulborn DJones S(1998)The Design and Implementation of an On-Line Testable UARTJournal of Electronic Testing: Theory and Applications10.1023/A:100822051588112:3(187-198)Online publication date: 1-Jun-1998
https://dl.acm.org/doi/10.1023/A%3A1008220515881
Yeandel JThulborn DJones S(1997)An on-line testable UART implemented using IFISProceedings of the 15th IEEE VLSI Test Symposium10.5555/832297.836351Online publication date: 27-Apr-1997
https://dl.acm.org/doi/10.5555/832297.836351
Show More Cited By

Index Terms

Implementing Sequential Machines as Self-Timed Circuits
1. Hardware
  1. Hardware validation
    1. Functional verification
      1. Simulation and emulation
  2. Integrated circuits
    1. Logic circuits
      1. Combinational circuits
2. Theory of computation
  1. Formal languages and automata theory

Recommendations

Optimization of NULL convention self-timed circuits

Self-timed logic design methods are developed using Threshold Combinational Reduction (TCR) within the NULL Convention Logic (NCL) paradigm. NCL logic functions are realized using 27 distinct transistor networks implementing the set of all functions of ...
Self-Timed Carry-Lookahead Adders
Special issue on computer arithmetic

Integer addition is one of the most important operations in digital computer systems because the performance of processors is significantly influenced by the speed of their adders. This paper proposes a self-timed carry-lookahead adder in which the ...
An Efficient Implementation of Boolean Functions as Self-Timed Circuits

The authors propose a general synthesis method for efficiently implementing any family of Boolean functions over a set of variables, as a self-timed logic module. Interval temporal logic is used to express the constraints that are formulated for the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 41, Issue 1

January 1992

129 pages

ISSN:0018-9340

Editor:
Earl Swartzlander
Univ. of Texas at Austin

Issue’s Table of Contents

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 January 1992

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Tadros RBeerel P(2020)A Theoretical Foundation for Timing Synchronous Systems Using Asynchronous StructuresACM Transactions on Design Automation of Electronic Systems10.1145/337335525:2(1-28)Online publication date: 3-Feb-2020
https://dl.acm.org/doi/10.1145/3373355
Yeandel JThulborn DJones S(1998)The Design and Implementation of an On-Line Testable UARTJournal of Electronic Testing: Theory and Applications10.1023/A:100822051588112:3(187-198)Online publication date: 1-Jun-1998
https://dl.acm.org/doi/10.1023/A%3A1008220515881
Yeandel JThulborn DJones S(1997)An on-line testable UART implemented using IFISProceedings of the 15th IEEE VLSI Test Symposium10.5555/832297.836351Online publication date: 27-Apr-1997
https://dl.acm.org/doi/10.5555/832297.836351
Kol RGinosar RSamuel G(1996)Statechart methodology for the design, validation, and synthesis of large scale asynchronous systemsProceedings of the 2nd International Symposium on Advanced Research in Asynchronous Circuits and Systems10.5555/785164.785218Online publication date: 18-Mar-1996
https://dl.acm.org/doi/10.5555/785164.785218
Linder DHarden J(1996)Phased LogicIEEE Transactions on Computers10.1109/12.53712645:9(1031-1044)Online publication date: 1-Sep-1996
https://dl.acm.org/doi/10.1109/12.537126

Abstract

References

Cited By

Index Terms

Recommendations

Optimization of NULL convention self-timed circuits

Self-Timed Carry-Lookahead Adders

An Efficient Implementation of Boolean Functions as Self-Timed Circuits

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations