Sequential Optimization of Asynchronous and Synchronous Finite-State Machines

1. Introduction.- 1.1 The Case for Asynchronous Circuits.- 1.2 Asynchronous Controllers.- 1.3 Sequential Synthesis.- 1.4 Toward Global Solutions to Optimal Synthesis.- 1.5 Asynchronous Sequential Synthesis.- 1.6 Book Contributions.- 1.7 Outline of Book.- 2. Background.- 2.1 Finite State Machines.- 2.2 Boolean Functions and Logic Synthesis.- 2.3 Sequential Hazards.- 2.4 Input Encoding.- 2.5 Unate and Binate Covering.- 3. Burst-Mode Synthesis Path Walk-Through.- 4. CHASM: Optimal State Assignment for Asynchronous FSM’s.- 4.1 Overview of CHASM.- 4.2 Background: Optimal State Assignment for Synchronous Machines.- 4.3 Problem Statement and CHASM Overview.- 4.4 Multiple-Valued Hazard-free 2-Level Logic Minimization.- 4.5 CHASM Method.- 4.6 Optimal State Assignment with Fed-back Outputs.- 4.7 Theoretical Results.- 4.8 Experimental Results.- 5. OPTIMIST: Optimal State Minimization for Synchronous FSM'S.- 5.1 Introduction.- 5.2 Background and Related Work.- 5.3 Optimal State Minimization: Overview.- 5.4 Symbolic Primes: RGPI’s.- 5.5 Constraint Generation.- 5.6 Symbolic Instantiation.- 5.7 Examples.- 5.8 Theoretical Results.- 5.9 Efficient RGPI Generation.- 5.10 Experimental Results.- 5.11 Conclusions and Future Work.- 6. Optimisto: Synchronous State Minimization for Optimum Output Logic.- 6.1 Introduction.- 6.2 Output-Targeted Minimization for Synchronous FSM’s.- 6.3 Example.- 6.4 Theoretical Results.- 6.5 Cost Function.- 6.6 Experimental Results.- 6.7 Conclusions and Future Work.- 7. OPTIMISTA: Asynchronous State Minimization for Optimum Output Logic.- 7.1 The Challenge of State Mapping for OPTIMISTA.- 7.2 OPTIMISTA: Method Flow.- 7.3 State Compatible Generation.- 7.4 Symbolic Prime Implicant Generation.- 7.5 Binate Constraint Generation.- 7.6 State MappingIncompatibility Constraints.- 7.7 Binate Constraint Solution.- 7.8 Instantiation.- 7.9 Theoretical Results.- 7.10 Efficient Generation of State Mapping Incompatibility Constraints.- 7.11 Experimental Results.- 7.12 Conclusions and Future Work.- 8. MINIMALIST: An Extensible Toolkit for Burst-Mode Synthesis.- 8.1 Introduction.- 8.2 Background and Overview.- 8.3 MINIMALIST Framework.- 8.4 MINIMALIST Tools.- 8.5 A Synthesis Session.- 8.6 Experimental Results.- 8.7 Conclusion.- 9. Conclusions.- Appendices.- Multiple-Valued Hazard-free Logic Minimization.- A.1 Multiple-Valued Functions and Hazards.- A.2 Circuit Model.- A.3 Multiple-Valued Multiple-Input Changes.- A.4 Multiple-Valued Function Hazards.- A.5 Multiple-Valued Logic Hazards.- A.6 Problem Abstraction.- A.7 Symbolic Hazard-Free Minimization.- A.7.1 Conditions for a Hazard-Free Transition.- A.7.2 Hazard-Free Covers.- A.7.3 Exact Hazard-Free Multiple-Valued Minimization.- A.7.4 Generation of MVI DHF-Prime Implicants.- A.7.5 Generation of the DHF-Prime Implicant Table.- A.7.6 Generation of a Minimum Cover.- A.7.7 Multiple-Output Minimization.- Efficient Generation of State Mapping Constraints.- B.1 Horizontal Required Cubes.- B.2 Vertical Required Cubes.- MINIMALIST Shell and Command Set.