Logic Synthesis of Asynchronous... | Buy

This book is devoted to logic synthesis and design techniques for asynchronous circuits. It uses the mathematical theory of Petri Nets and asynchronous automata to develop practical algorithms implemented in a public domain CAD tool. Asynchronous circuits have so far been designed mostly by hand, and are thus much less common than their synchronous counterparts, which have enjoyed a high level of design automation since the mid-1970s. Asynchronous circuits, on the other hand, can be very useful to tackle clock distribution, modularity, power dissipation and electro-magnetic interference in digital integrated circuits. This book provides the foundation needed for CAD-assisted design of such circuits, and can also be used as the basis for a graduate course on logic design.

Introduction	p. 1
A Little History	p. 1
Advantages of Asynchronous Logic	p. 3
Modularity	p. 3
Power Consumption and Electromagnetic Interference	p. 4
Performance	p. 6
Asynchronous Control Circuits	p. 7
Delay Models	p. 10
Operating Modes	p. 11
Design Flow	p. 13
Specification of Asynchronous Controllers	p. 13
From Timing Diagrams to Signal Transition Graphs	p. 14
Choice in Signal Transition Graphs	p. 15
Transition Systems and State Graphs	p. 16
State Space	p. 16
Binary Interpretation	p. 17
Deriving Logic Equations	p. 19
System Behavior	p. 19
Excitation and Quiescent Regions	p. 19
Next-state Functions	p. 20
State Encoding	p. 21
Logic Decomposition and Technology Mapping	p. 23
Synthesis with Relative Timing	p. 25
Summary	p. 27
Background	p. 29
Petri Nets	p. 29
The Dining Philosophers	p. 31
Structural Theory of Petri Nets	p. 37
Incidence Matrix and State Equation	p. 37
Transition and Place Invariants	p. 38
Calculating the Reachability Graph of a Petri Net	p. 39
Encoding	p. 41
Transition Function and Reachable Markings	p. 42
Transition Systems	p. 44
Deriving Petri Nets from Transition Systems	p. 45
Regions	p. 45
Properties of Regions	p. 47
Excitation Regions	p. 47
Excitation-Closure	p. 48
Place-Irredundant and Place-Minimal Petri Nets	p. 49
Algorithm for Petri Net Synthesis	p. 52
Generation of Minimal Pre-regions	p. 53
Search for Irredundant Sets of Regions	p. 54
Label Splitting	p. 55
Event Insertion in Transition Systems	p. 57
Logic Synthesis	p. 61
Signal Transition Graphs and State Graphs	p. 62
Signal Transition Graphs	p. 62
State Graphs	p. 64
Excitation and Quiescent Regions	p. 65
Implementability as a Logic Circuit	p. 66
Boundedness	p. 66
Consistency	p. 67
Complete State Coding	p. 69
Output Persistency	p. 70
Boolean Functions	p. 73
ON, OFF and DC Sets	p. 73
Support of a Boolean Function	p. 73
Cofactors and Shannon Expansion	p. 74
Existential Abstraction and Boolean Difference	p. 74
Unate and Binate Functions	p. 74
Function Implementation	p. 74
Boolean Relations	p. 75
Gate Netlists	p. 75
Complex Gates	p. 76
Generalized C-Elements	p. 76
C-Elements with Complex Gates	p. 78
Deriving a Gate Netlist	p. 79
Deriving Functions for Complex Gates	p. 79
Deriving Functions for Generalized C-Elements	p. 81
What is Speed-Independence?	p. 82
Characterization of Speed-Independence	p. 85
Related Work	p. 85
Summary	p. 86
State Encoding	p. 87
Methods for Complete State Coding	p. 91
Constrained Signal Transition Event Insertion	p. 94
Speed-Independence Preserving Insertion	p. 95
Selecting SIP-Sets	p. 101
Transformation of State Graphs	p. 103
Completeness of the Method	p. 107
An Heuristic Strategy to Solve CSC	p. 115
Generation of I-Partitions	p. 115
Exploring the Space of I-Partitions	p. 116
Increasing Concurrency	p. 117
Cost Function	p. 118
Estimation of Logic	p. 119
Examples of CSC Conflict Elimination	p. 119
Related Work	p. 122
Summary	p. 123
Logic Decomposition	p. 125
Overview	p. 126
Architecture-Based Decomposition	p. 132
Logic Decomposition Using Algebraic Factorization	p. 134
Overview	p. 134
Combinational Decomposition	p. 135
Hazard-Free Signal Insertion	p. 137
Pruning the Solution Space	p. 138
Finding a Valid Excitation Region	p. 139
Progress Analysis	p. 141
Local Progress Conditions	p. 142
Global Progress Conditions	p. 145
Logic Decomposition Using Boolean Relations	p. 146
Overview	p. 148
Specifying Permissible Decompositions with BRs	p. 150
Functional Representation of Boolean Relations	p. 154
Two-Level Sequential Decomposition	p. 155
Heuristic Selection of the Best Decomposition	p. 160
Signal Acknowledgment and Insertion	p. 160
Experimental Results	p. 161
The Cost of Speed Independence	p. 163
Summary	p. 164
Synthesis with Relative Timing	p. 167
Motivation	p. 167
Synthesis with Timing	p. 169
Why Relative Timing?	p. 169
Abstraction of Time	p. 170
Design Flow	p. 171
Lazy Transition Systems and Lazy State Graphs	p. 172
Overview and Example	p. 173
First Timing Assumption	p. 173
Second Timing Assumption	p. 174
Logic Minimization	p. 176
Summary	p. 177
Timing Assumptions	p. 177
Difference Assumptions	p. 179
Simultaneity Assumptions	p. 179
Early Enabling Assumptions	p. 181
Synthesis with Relative Timing	p. 182
Implementability Properties	p. 182
Synthesis Flow with Relative Timing	p. 184
Synthesis Algorithm	p. 185
Automatic Generation of Timing Assumptions	p. 186
Ordering Relations	p. 188
Delay Model	p. 190
Rules for Deriving Timing Assumptions	p. 190
Back-Annotation of Timing Constraints	p. 193
Correctness Conditions	p. 196
Problem Formulation	p. 197
Finding a Set of Timing Constraints	p. 198
Experimental Results	p. 201
Academic Examples	p. 201
A FIFO Controller	p. 203
RAPPID Control Circuits	p. 206
Summary	p. 206
Design Examples	p. 209
Handshake Communication	p. 210
Handshake: Informal Specification	p. 210
Circuit Synthesis	p. 211
VME Bus Controller	p. 217
VME Bus Controller Specification	p. 217
VME Bus Controller Synthesis	p. 219
Lessons to be Learned from the Example	p. 225
Controller for Self-timed A/D Converter	p. 225
Top Level Description	p. 226
Controller Synthesis	p. 227
Decomposed Solution for the Scheduler	p. 232
Synthesis of the Data Register	p. 235
Quality of the Results	p. 236
Lessons to be Learned from the Example	p. 237
"Lazy" Token Ring Adapter	p. 237
Lazy Token Ring Description	p. 238
Adapter Synthesis	p. 239
A Model for Performance Analysis	p. 242
Lessons to be Learned from the Example	p. 243
Other Examples	p. 243
Other Work	p. 245
Hardware Description Languages	p. 245
Structural and Unfolding-based Synthesis	p. 247
Direct Mapping of STGs into Asynchronous Circuits	p. 249
Datapath Design and Interfaces	p. 250
Test Pattern Generation and Design for Testability	p. 251
Verification	p. 252
Asynchronous Silicon	p. 253
Conclusions	p. 255
References	p. 257
Index	p. 269
Table of Contents provided by Publisher. All Rights Reserved.

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.