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

Article

Free access

OPTIMISTA: state minimization of asynchronous FSMs for optimum output logic

Authors:

Robert M. Fuhrer,

Steven M. NowickAuthors Info & Claims

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

Pages 7 - 13

Published: 07 November 1999 Publication History

Abstract

The optimal state minimization problem is to select a reduced state machine having the best logic implementation over all possible state reductions and encodings. A recent algorithm, OPTIMIST [3], was the first general solution to this problem for synchronous FSMs. In this paper, we present the first solution for asynchronous FSMs.

This paper makes two contributions. First, we introduce OPTIMISTA, a new algorithm which guarantees optimum 2-level output logic for asynchronous FSMs. In asynchronous machines, output logic is often critical: it usually determines the machine latency. The algorithm is formulated as a binate constraint satisfaction problem, which is solved using a binate solver. The second contribution is a novel alternative result: the unreduced machine itself can be used directly to obtain minimum-cardinality output logic.

Thus, this paper presents two approaches: using OPTIMISTA, which simultaneously performs state and logic minimization; or using no state reduction (if output logic cardinality is of sole interest). Extensions for literal optimization, targetted to multi-level logic, are also proposed.

References

[1]

O. Coudert and J.C. Madre. New ideas for solving covering problems. In DAC-1995, pages 641-646, 1995.

Digital Library

[2]

R.M. Fuhrer, B. Lin, and S.M. Nowick. Symbolic hazardfree minimization and encoding of asynchronous finite state machines. In ICCAD-1995, 1995.

Digital Library

[3]

R.M. Fuhrer and S.M. Nowick. Optimist: State minimization for optimal 2-level logic implementation. In ICCAD-1997, 1997.

Digital Library

[4]

R.M. Fuhrer, S.M. Nowick, M. Theobald, N.K. Jha, B. Lin, and L. Plana. Minimalist: An environment for the synthesis, verification and testability of burst-mode asynchronous machines. Technical Report CUCS-020-99, Columbia University, July 1999.

[5]

Robert M. Fuhrer. Sequential optimization of asynchronous and synchronous finite-state machines: Algorithms and tools. Technical report, Columbia University, 1999. Ph.D. Thesis.

Digital Library

[6]

A. Grasselli and F. Luccio. A method for minimizing the number of internal states in incompletely specified sequential networks. IEEE TEC, EC-14:350-359, June 1965.

[7]

G. Hachtel, J.K. Rho, F. Somenzi, and R. Jacoby. Exact and heuristic algorithms for the minimization of incompletely specified state machines. IEEE Trans. on CAD, CAD- 13(2):167-177, February 1994.

Digital Library

[8]

T. Kam, T. Villa, R.K. Brayton, and A. Sangiovanni- Vincentelli. A fully implicit algorithm for exact state minimization. In DAC-1994.

Digital Library

[9]

B. Lin and F. Somenzi. Minimization of symbolic relations. In ICCAD-1990, pages 88-91, 1990.

[10]

A. Marshall, B. Coates, and E Siegel. The design of an asynchronous communications chip. Design and Test, June 1994.

Digital Library

[11]

G. De Micheli, R. K. Brayton, and A. Sangiovanni- Vincentelli. Optimal state assignment for finite state machines. IEEE Transactions on CAD, CAD-4(3):269-285, July 1985.

[12]

S.M. Nowick and B. Coates. Uclock: Automated design of high-performance unclocked state machines. In ICCD-1994, 1994.

Digital Library

[13]

S.M. Nowick and D.L. Dill. Automatic synthesis of locallyclocked asynchronous state machines. In ICCAD-1991.

[14]

S.M. Nowick and D.L. Dill. Exact two-level minimization of hazard-free logic with multiple-input changes. IEEE Transactions on CAD, 14(8):986-997, August 1995.

Digital Library

[15]

Steven M. Nowick. Automatic synthesis of burst-mode asynchronous controllers. Technical report, Stanford University, 1993. Ph.D. Thesis.

Digital Library

[16]

M. Paull and S. Unger. Minimizing the number of states in incompletely specified sequential switching functions. IRE Trans. on Elec. Comp., EC-8:356-367, Sept. 1959.

[17]

S.H. Unger. Asynchronous Sequential Switching Circuits. New York: Wiley-Interscience, 1969.

Digital Library

[18]

K.Y. Yun, D.L. Dill, and S.M. Nowick. Synthesis of 3D asynchronous state machines. In ICCD-1992.

Digital Library

Cited By

Almukhaizim SMakris Y(2007)Concurrent Error Detection Methods for Asynchronous Burst-Mode MachinesIEEE Transactions on Computers10.1109/TC.2007.102556:6(785-798)Online publication date: 1-Jun-2007
https://dl.acm.org/doi/10.1109/TC.2007.1025
Almukhaizim SMakris Y(2005)Concurrent Error Detection in Asynchronous Burst-Mode ControllersProceedings of the conference on Design, Automation and Test in Europe - Volume 210.1109/DATE.2005.101(1272-1277)Online publication date: 7-Mar-2005
https://dl.acm.org/doi/10.1109/DATE.2005.101
Jacobson HMyers CGopalakrishnan GSentovich E(2000)Achieving fast and exact hazard-free logic minimization of extended burst-mode gC finite state machinesProceedings of the 2000 IEEE/ACM international conference on Computer-aided design10.5555/602902.602970(303-311)Online publication date: 5-Nov-2000
https://dl.acm.org/doi/10.5555/602902.602970

Index Terms

OPTIMISTA: state minimization of asynchronous FSMs for optimum output logic

Recommendations

Intuitionistic Trilattice Logics

We take up a suggestion by Odintsov (2009, Studia Logica, 91, 407–428) and define intuitionistic variants of certain logics arising from the trilattice SIXTEEN₃ introduced in Shramko and Wansing (2005, Journal of Philosophical Logic, 34, 121–153 and ...
Proving Isomorphism of First-Order Logic Proof Systems in HOL
Completeness and decidability of converse PDL in the constructive type theory of Coq
CPP 2018: Proceedings of the 7th ACM SIGPLAN International Conference on Certified Programs and Proofs

The completeness proofs for Propositional Dynamic Logic (PDL) in the literature are non-constructive and usually presented in an informal manner. We obtain a formal and constructive completeness proof for Converse PDL by recasting a completeness proof ...

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

3
Total Citations
View Citations
148
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)3

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Almukhaizim SMakris Y(2007)Concurrent Error Detection Methods for Asynchronous Burst-Mode MachinesIEEE Transactions on Computers10.1109/TC.2007.102556:6(785-798)Online publication date: 1-Jun-2007
https://dl.acm.org/doi/10.1109/TC.2007.1025
Almukhaizim SMakris Y(2005)Concurrent Error Detection in Asynchronous Burst-Mode ControllersProceedings of the conference on Design, Automation and Test in Europe - Volume 210.1109/DATE.2005.101(1272-1277)Online publication date: 7-Mar-2005
https://dl.acm.org/doi/10.1109/DATE.2005.101
Jacobson HMyers CGopalakrishnan GSentovich E(2000)Achieving fast and exact hazard-free logic minimization of extended burst-mode gC finite state machinesProceedings of the 2000 IEEE/ACM international conference on Computer-aided design10.5555/602902.602970(303-311)Online publication date: 5-Nov-2000
https://dl.acm.org/doi/10.5555/602902.602970

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

Media

Figures

Other

Tables

View Table of Contents