Logic Synthesis for Asynchronous Controllers and Interfaces

This book is the result of a long friendship, of a broad international co­ operation, and of a bold dream. It is the summary of work carried out by the authors, and several other wonderful people, during more than 15 years, across 3 continents, in the course of countless meetings, workshops and discus­ sions. It shows that neither language nor distance can be an obstacle to close scientific cooperation, when there is unity of goals and true collaboration. When we started, we had very different approaches to handling the mys­ terious, almost magical world of asynchronous circuits. Some were more theo­ retical, some were closer to physical reality, some were driven mostly by design needs. In the end, we all shared the same belief that true Electronic Design Automation research must be solidly grounded in formal models, practically minded to avoid excessive complexity, and tested "in the field" in the form of experimental tools. The results are this book, and the CAD tool petrify. The latter can be downloaded and tried by anybody bold (or desperate) enough to tread into the clockless (but not lawless) domain of small-scale asynchronicity. The URL is http://www.lsi. upc. esr j ordic/petrify. We believe that asynchronous circuits are a wonderful object, that aban­ dons some of the almost militaristic law and order that governs synchronous circuits, to improve in terms of simplicity, energy efficiency and performance.

1. Introduction.- 1.1 A Little History.- 1.2 Advantages of Asynchronous Logic.- 1.2.1 Modularity.- 1.2.2 Power Consumption and Electromagnetic Interference.- 1.2.3 Performance.- 1.3 Asynchronous Control Circuits.- 1.3.1 Delay Models.- 1.3.2 Operating Modes.- 2. Design Flow.- 2.1 Specification of Asynchronous Controllers.- 2.1.1 From Timing Diagrams to Signal Transition Graphs.- 2.1.2 Choice in Signal Transition Graphs.- 2.2 Transition Systems and State Graphs.- 2.2.1 State Space.- 2.2.2 Binary Interpretation.- 2.3 Deriving Logic Equations.- 2.3.1 System Behavior.- 2.3.2 Excitation and Quiescent Regions.- 2.3.3 Next-state Functions.- 2.4 State Encoding.- 2.5 Logic Decomposition and Technology Mapping.- 2.6 Synthesis with Relative Timing.- 2.7 Summary.- 3. Background.- 3.1 Petri Nets.- 3.1.1 The Dining Philosophers.- 3.2 Structural Theory of Petri Nets.- 3.2.1 Incidence Matrix and State Equation.- 3.2.2 Transition and Place Invariants.- 3.3 Calculating the Reachability Graph of a Petri Net.- 3.3.1 Encoding.- 3.3.2 Transition Function and Reachable Markings.- 3.4 Transition Systems.- 3.5 Deriving Petri Nets from Transition Systems.- 3.5.1 Regions.- 3.5.2 Properties of Regions.- 3.5.3 Excitation Regions.- 3.5.4 Excitation-Closure.- 3.5.5 Place-Irredundant and Place-Minimal Petri Nets.- 3.6 Algorithm for Petri Net Synthesis.- 3.6.1 Generation of Minimal Pre-regions.- 3.6.2 Search for Irredundant Sets of Regions.- 3.6.3 Label Splitting.- 3.7 Event Insertion in Transition Systems.- 4. Logic Synthesis.- 4.1 Signal Transition Graphs and State Graphs.- 4.1.1 Signal Transition Graphs.- 4.1.2 State Graphs.- 4.1.3 Excitation and Quiescent Regions.- 4.2 Implement ability as a Logic Circuit.- 4.2.1 Boundedness.- 4.2.2 Consistency.- 4.2.3 Complete State Coding.- 4.2.4 Output Persistency.- 4.3 Boolean Functions.- 4.3.1 ON, OFF and DC Sets.- 4.3.2 Support of a Boolean Function.- 4.3.3 Cofactors and Shannon Expansion.- 4.3.4 Existential Abstraction and Boolean Difference.- 4.3.5 Unate and Binate Functions.- 4.3.6 Function Implementation.- 4.3.7 Boolean Relations.- 4.4 Gate Netlists.- 4.4.1 Complex Gates.- 4.4.2 Generalized C-Elements.- 4.4.3 C-Elements with Complex Gates.- 4.5 Deriving a Gate Net list.- 4.5.1 Deriving Functions for Complex Gates.- 4.5.2 Deriving Functions for Generalized C-Elements.- 4.6 What is Speed-Independence?.- 4.6.1 Characterization of Speed-Independence.- 4.6.2 Related Work.- 4.7 Summary.- 5. State Encoding.- 5.1 Methods for Complete State Coding.- 5.2 Constrained Signal Transition Event Insertion.- 5.2.1 Speed-Independence Preserving Insertion.- 5.3 Selecting SIP-Sets.- 5.4 Transformation of State Graphs.- 5.5 Completeness of the Method.- 5.6 An Heuristic Strategy to Solve CSC.- 5.6.1 Generation of I-Part it ions.- 5.6.2 Exploring the Space of I-Partitions.- 5.6.3 Increasing Concurrency.- 5.7 Cost Function.- 5.7.1 Estimation of Logic.- 5.7.2 Examples of CSC Conflict Ehmination.- 5.8 Related Work.- 5.9 Summary.- 6. Logic Decomposition.- 6.1 Overview.- 6.2 Architecture-Based Decomposition.- 6.3 Logic Decomposition Using Algebraic Factorization.- 6.3.1 Overview.- 6.3.2 Combinational Decomposition.- 6.3.3 Hazard-Free Signal Insertion.- 6.3.4 Pruning the Solution Space.- 6.3.5 Finding a Valid Excitation Region.- 6.3.6 Progress Analysis.- 6.3.7 Local Progress Conditions.- 6.3.8 Global Progress Conditions.- 6.4 Logic Decomposition Using Boolean Relations.- 6.4.1 Overview.- 6.4.2 Specifying Permissible Decompositions with BRs.- 6.4.3 Functional Representation of Boolean Relations.- 6.4.4 Two-Level Sequential Decomposition.- 6.4.5 Heuristic Selection of the Best Decomposition.- 6.4.6 Signal Acknowledgment and Insertion.- 6.5 Experimental Results.- 6.5.1 The Cost of Speed Independence.- 6.6 Summary.- 7. Synthesis with Relative Timing.- 7.1 Motivation.- 7.1.1 Synthesis with Timing.- 7.1.2 Why Relative Timing?.- 7.1.3 Abstraction of Time.- 7.1.4 Design Flow.- 7.2 Lazy Transition Systems and Lazy State Graphs.- 7.3 Overview and Example.- 7.3.1 First Timing Assumption.- 7.3.2 Second Timing Assumption.- 7.3.3 Logic Minimization.- 7.3.4 Summary.- 7.4 Timing Assumptions.- 7.4.1 Difference Assumptions.- 7.4.2 Simultaneity Assumptions.- 7.4.3 Early Enabhng Assumptions.- 7.5 Synthesis with Relative Timing.- 7.5.1 Implementability Properties.- 7.5.2 Synthesis Flow with Relative Timing.- 7.5.3 Synthesis Algorithm.- 7.6 Automatic Generation of Timing Assumptions.- 7.6.1 Ordering Relations.- 7.6.2 Delay Model.- 7.6.3 Rules for Deriving Timing Assumptions190..- 7.7 Back-Annotation of Timing Constraints.- 7.7.1 Correctness Conditions.- 7.7.2 Problem Formulation.- 7.7.3 Finding a Set of Timing Constraints.- 7.8 Experimental Results.- 7.8.1 Academic Examples.- 7.8.2 A FIFO Controller.- 7.8.3 RAPPID Control Circuits.- 7.9 Summary.- 8. Design Examples.- 8.1 Handshake Communication.- 8.1.1 Handshake: Informal Specification.- 8.1.2 Circuit Synthesis.- 8.2 VME Bus Controller.- 8.2.1 VME Bus Controller Specification.- 8.2.2 VME Bus Controller Synthesis.- 8.2.3 Lessons to be Learned from the Example.- 8.3 Controller for Self-timed A/D Converter.- 8.3.1 Top Level Description.- 8.3.2 Controller Synthesis.- 8.3.3 Decomposed Solution for the Scheduler.- 8.3.4 Synthesis of the Data Register.- 8.3.5 Quality of the Results.- 8.3.6 Lessons to be Learned from the Example.- 8.4 “Lazy” Token Ring Adapter.- 8.4.1 Lazy Token Ring Description.- 8.4.2 Adapter Synthesis.- 8.4.3 A Model for Performance Analysis.- 8.4.4 Lessons to be Learned from the Example.- 8.5 Other Examples.- 9. Other Work.- 9.1 Hardware Description Languages.- 9.2 Structural and Unfolding-based Synthesis.- 9.3 Direct Mapping of STGs into Asynchronous Circuits.- 9.4 Datapath Design and Interfaces.- 9.5 Test Pattern Generation and Design for Testability.- 9.6 Verification.- 9.7 Asynchronous Silicon.- 10. Conclusions.- References.