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.3 Asynchronous Control Circuits.- 2. Design Flow.- 2.1 Specification of Asynchronous Controllers.- 2.2 Transition Systems and State Graphs.- 2.3 Deriving Logic Equations.- 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.2 Structural Theory of Petri Nets.- 3.3 Calculating the Reachability Graph of a Petri Net.- 3.4 Transition Systems.- 3.5 Deriving Petri Nets from Transition Systems.- 3.6 Algorithm for Petri Net Synthesis.- 3.7 Event Insertion in Transition Systems.- 4. Logic Synthesis.- 4.1 Signal Transition Graphs and State Graphs.- 4.2 Implement ability as a Logic Circuit.- 4.3 Boolean Functions.- 4.4 Gate Netlists.- 4.5 Deriving a Gate Net list.- 4.6 What is Speed-Independence?.- 4.7 Summary.- 5. State Encoding.- 5.1 Methods for Complete State Coding.- 5.2 Constrained Signal Transition Event 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.7 Cost Function.- 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.4 Logic Decomposition Using Boolean Relations.- 6.5 Experimental Results.- 6.6 Summary.- 7. Synthesis with Relative Timing.- 7.1 Motivation.- 7.2 Lazy Transition Systems and Lazy State Graphs.- 7.3 Overview and Example.- 7.4 Timing Assumptions.- 7.5 Synthesis with Relative Timing.- 7.6 Automatic Generation of Timing Assumptions.- 7.7 Back-Annotation of Timing Constraints.- 7.8 Experimental Results.- 7.9 Summary.- 8. Design Examples.- 8.1 Handshake Communication.- 8.2 VME Bus Controller.- 8.3 Controller for Self-timed A/D Converter.- 8.4 “Lazy” Token Ring Adapter.- 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.