+612 9045 4394
 
CHECKOUT
Sequential Optimization of Asynchronous and Synchronous Finite-State Machines : Algorithms and Tools - Robert M. Fuhrer

Sequential Optimization of Asynchronous and Synchronous Finite-State Machines

Algorithms and Tools

Hardcover

Published: 30th June 2001
Ships: 7 to 10 business days
7 to 10 business days
RRP $516.99
$357.90
31%
OFF
or 4 easy payments of $89.48 with Learn more

Other Available Formats (Hide)

  • Paperback View Product Published: 24th October 2012
    $293.53

Asynchronous, or unclocked, digital systems have several potential advantages over their synchronous counterparts. In particular, they address a number of challenging problems faced by the designers of large-scale synchronous digital systems: power consumption, worst-case timing constraints, and engineering and design reuse issues associated with the use of a fixed-rate global clock. Moreover, while for synchronous systems these problems are exacerbated by increasing system size, asynchronous systems promise to scale more gracefully.

List of Figuresp. xiii
List of Tablesp. xvii
Acknowledgmentsp. xix
Introductionp. 1
The Case for Asynchronous Circuitsp. 1
Asynchronous Controllersp. 5
Classical Asynchronous FSM Modelsp. 5
Asynchronous Controller Design Stylesp. 6
Programming in Siliconp. 7
State Transition Graphsp. 7
Asynchronous State Machinesp. 8
Burst-Mode Machinesp. 9
Sequential Synthesisp. 10
Classic Synthesis Trajectoryp. 11
Toward Global Solutions to Optimal Synthesisp. 14
Asynchronous Sequential Synthesisp. 15
Asynchronous Synthesis Pathp. 16
State-of-the-Art Asynchronous Synthesisp. 17
Book Contributionsp. 18
CAD Algorithms and Toolsp. 18
CAD Frameworkp. 20
Scope of the Bookp. 21
Outline of Bookp. 22
Backgroundp. 25
Finite State Machinesp. 25
Synchronous FSM'sp. 25
Burst-Mode Asynchronous Specificationsp. 28
Boolean Functions and Logic Synthesisp. 35
Binary Functionsp. 35
Symbolic Functionsp. 36
Hazard-free Logic Minimizationp. 37
Sequential Hazardsp. 45
Critical Racesp. 46
Essential Hazardsp. 47
Input Encodingp. 48
Unate and Binate Coveringp. 49
Burst-Mode Synthesis Path Walk-Throughp. 53
Chasm: Optimal State Assignment for Asynchronous FSM'sp. 59
Overview of CHASMp. 60
Background: Optimal State Assignment for Synchronous Machinesp. 61
Problem Statement and CHASM Overviewp. 67
State Assignment for Asynchronous Machinesp. 68
Multiple-Valued Hazard-free 2-Level Logic Minimizationp. 68
CHASM Methodp. 71
Symbolic Hazard-Free Logic Minimizationp. 71
Encoding Constraintsp. 72
Constraint Solution and Logic Minimizationp. 77
Optimal State Assignment with Fed-back Outputsp. 78
Theoretical Resultsp. 79
Machine Instantiationp. 79
Correctness of Binary Coverp. 82
Optimality of Binary Coverp. 92
Experimental Resultsp. 92
Optimist: Optimal State Minimization for Synchronous FSM'sp. 95
Introductionp. 96
Background and Related Workp. 97
State Minimizationp. 97
The State Mapping Problemp. 102
Previous Workp. 102
Optimal State Minimization: Overviewp. 104
Optimal State Minimization and Input Encodingp. 104
Symbolic Primesp. 105
Constraint Generationp. 107
Constraint Solutionp. 108
Symbolic Instantiationp. 109
Symbolic Primes: RGPI'sp. 110
Generating RGPI Seedsp. 110
Non-Seed RGPI'sp. 111
Constraint Generationp. 115
Constraint Matrix Variablesp. 116
Cost Modelp. 116
Constraintsp. 116
Flow of Constraint Solutionp. 119
Efficient Constraint Solutionp. 120
Symbolic Instantiationp. 120
Examplesp. 121
Theoretical Resultsp. 124
Correctnessp. 124
Optimalityp. 128
Efficient RGPI Generationp. 130
Efficient RGPI Seed Generationp. 131
Efficient RGPI Generationp. 135
Experimental Resultsp. 135
Conclusions and Future Workp. 136
Optimisto: Synchronous State Minimization for Optimum Output Logicp. 141
Introductionp. 141
Output-Targeted Minimization for Synchronous FSM'sp. 143
Overview of Problem Formulationp. 143
Overview of Methodp. 144
Symbolic Primesp. 145
Binate Constraintsp. 145
Constraint Solutionp. 148
Symbolic Implicant Instantiationp. 148
Method Summaryp. 149
Examplep. 150
Theoretical Resultsp. 151
Correctness of Constraint-Satisfaction Methodp. 152
Optimality of the Unminimized Machinep. 153
Optimality of the Constraint-Satisfaction Methodp. 154
Cost Functionp. 156
Experimental Resultsp. 157
Conclusions and Future Workp. 158
Optimista: Asynchronous State Minimization for Optimum Output Logicp. 161
The Challenge of State Mapping for Optimistap. 162
Hazard-Free Output Coveringp. 163
Existence of Hazard-Free Next-state Logicp. 163
Proper Burst-Mode Operationp. 164
Optimista: Method Flowp. 165
State Compatible Generationp. 166
Symbolic Prime Implicant Generationp. 169
Binate Constraint Generationp. 169
Constraint Variablesp. 169
Constraint Roadmapp. 169
State Coveringp. 170
State Mappingp. 170
State Mapping Coherencyp. 171
Functional Coveringp. 171
State Closurep. 173
State Mapping Incompatibilityp. 174
State Mapping Incompatibility Constraintsp. 174
Basic Elements in the Case Analysisp. 175
Horizontal Required Cubes for the Source Statep. 178
Horizontal Required Cubes for Destination Statep. 179
Generating Horizontal State Mapping Incompatibility Constraintsp. 180
Vertical Required Cubes for the Source Statep. 181
Vertical Required Cubes for the Destination Statep. 182
Generating Vertical State Mapping Incompatibility Constraintsp. 182
Binate Constraint Solutionp. 183
Instantiationp. 184
Theoretical Resultsp. 186
Correctness of OPTIMISTAp. 186
Optimality of the Unminimized Machinep. 188
Optimality of OPTIMISTAp. 190
Efficient Generation of State Mapping Incompatibility Constraintsp. 191
Experimental Resultsp. 191
Conclusions and Future Workp. 192
Minimalist: An Extensible Toolkit for Burst-mode Synthesisp. 195
Introductionp. 196
Background and Overviewp. 197
Comparison: Burst-Mode Synthesis Toolkitsp. 197
Comparative Summary: MINIMALIST vs. Previous Toolsp. 198
MINIMALIST Frameworkp. 198
MINIMALIST Toolsp. 198
State Minimizationp. 198
CHASMp. 200
HFMINp. 202
ESPRESSO-HFp. 203
IMPYMINp. 203
Synthesis-for-Testabilityp. 203
Verifierp. 204
A Synthesis Sessionp. 204
Experimental Resultsp. 206
Experimental Set-upp. 206
Performance-Oriented Comparison with 3Dp. 207
Area-Oriented Comparison with 3Dp. 210
Area-Oriented Comparison with UCLOCKp. 210
Optimal Encoding for Output-Targeted Synthesisp. 211
Exploring Varying Code Lengthsp. 213
Basic Synthesis Scriptsp. 215
Conclusionp. 216
Conclusionsp. 219
Appendicesp. 222
Multiple-Valued Hazard-free Logic Minimizationp. 223
Multiple-Valued Functions and Hazardsp. 223
Circuit Modelp. 223
Multiple-Valued Multiple-Input Changesp. 223
Multiple-Valued Function Hazardsp. 224
Multiple-Valued Logic Hazardsp. 225
Problem Abstractionp. 226
Symbolic Hazard-Free Minimizationp. 226
Conditions for a Hazard-Free Transitionp. 226
Hazard-Free Coversp. 227
Exact Hazard-Free Multiple-Valued Minimizationp. 228
Generation of MVI DHF-Prime Implicantsp. 229
Generation of the DHF-Prime Implicant Tablep. 230
Generation of a Minimum Coverp. 230
Multiple-Output Minimizationp. 230
Efficient Generation of State Mapping Constraintsp. 233
Horizontal Required Cubesp. 234
Vertical Required Cubesp. 235
MINIMALIST Shell and Command Setp. 243
Indexp. 257
Table of Contents provided by Syndetics. All Rights Reserved.

ISBN: 9780792374251
ISBN-10: 0792374258
Audience: Professional
Format: Hardcover
Language: English
Number Of Pages: 258
Published: 30th June 2001
Publisher: Springer
Country of Publication: NL
Dimensions (cm): 23.5 x 15.5  x 1.91
Weight (kg): 1.28