Logic Synthesis for Asynchronous Controllers and Interfaces: With 146 FiguresSpringer Science & Business Media, 12 במרץ 2002 - 273 עמודים 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. |
תוכן
Introduction | 1 |
12 Advantages of Asynchronous Logic | 3 |
122 Power Consumption and Electromagnetic Interference | 4 |
123 Performance | 6 |
13 Asynchronous Control Circuits | 7 |
131 Delay Models | 10 |
132 Operating Modes | 11 |
Design Flow | 13 |
61 Overview | 126 |
62 ArchitectureBased Decomposition | 132 |
63 Logic Decomposition Using Algebraic Factorization | 134 |
632 Combinational Decomposition | 135 |
633 HazardFree Signal Insertion | 137 |
634 Pruning the Solution Space | 138 |
635 Finding a Valid Excitation Region | 139 |
637 Local Progress Conditions | 142 |
211 From Timing Diagrams to Signal Transition Graphs | 14 |
212 Choice in Signal Transition Graphs | 15 |
22 Transition Systems and State Graphs | 16 |
222 Binary Interpretation | 17 |
23 Deriving Logic Equations | 19 |
233 Nextstate Functions | 20 |
24 State Encoding | 21 |
25 Logic Decomposition and Technology Mapping | 23 |
26 Synthesis with Relative Timing | 25 |
27 Summary | 27 |
Background | 29 |
311 The Dining Philosophers | 31 |
32 Structural Theory of Petri Nets | 37 |
322 Transition and Place Invariants | 38 |
33 Calculating the Reachability Graph of a Petri Net | 39 |
331 Encoding | 41 |
332 Transition Function and Reachable Markings | 42 |
34 Transition Systems | 44 |
35 Deriving Petri Nets from Transition Systems | 45 |
352 Properties of Regions | 47 |
354 ExcitationClosure | 48 |
355 Placeirredundant and PlaceMinimal Petri Nets | 49 |
36 Algorithm for Petri Net Synthesis | 52 |
361 Generation of Minimal Preregions | 53 |
362 Search for Irredundant Sets of Regions | 54 |
363 Label Splitting | 55 |
37 Event Insertion in Transition Systems | 57 |
Logic Synthesis | 61 |
41 Signal Transition Graphs and State Graphs | 62 |
412 State Graphs | 64 |
413 Excitation and Quiescent Regions | 65 |
42 Implementability as a Logic Circuit | 66 |
422 Consistency | 67 |
423 Complete State Coding | 69 |
424 Output Persistency | 70 |
43 Boolean Functions | 73 |
433 Cofactors and Shannon Expansion | 74 |
437 Boolean Relations | 75 |
441 Complex Gates | 76 |
443 CElements with Complex Gates | 78 |
45 Deriving a Gate Netlist | 79 |
452 Deriving Functions for Generalized CElements | 81 |
46 What is SpeedIndependence? | 82 |
461 Characterization of SpeedIndependence | 85 |
47 Summary | 86 |
State Encoding | 87 |
51 Methods for Complete State Coding | 91 |
52 Constrained Signal Transition Event Insertion | 94 |
521 SpeedIndependence Preserving Insertion | 95 |
53 Selecting SIPSets | 101 |
54 Transformation of State Graphs | 103 |
55 Completeness of the Method | 107 |
56 An Heuristic Strategy to Solve CSC | 115 |
562 Exploring the Space of IPartitions | 116 |
563 Increasing Concurrency | 117 |
57 Cost Function | 118 |
571 Estimation of Logic | 119 |
58 Related Work | 122 |
59 Summary | 123 |
Logic Decomposition | 125 |
638 Global Progress Conditions | 145 |
64 Logic Decomposition Using Boolean Relations | 146 |
641 Overview | 148 |
642 Specifying Permissible Decompositions with BRs | 150 |
643 Functional Representation of Boolean Relations | 154 |
644 TwoLevel Sequential Decomposition | 155 |
645 Heuristic Selection of the Best Decomposition | 160 |
65 Experimental Results | 161 |
651 The Cost of Speed Independence | 163 |
66 Summary | 164 |
Synthesis with Relative Timing | 167 |
711 Synthesis with Timing | 169 |
713 Abstraction of Time | 170 |
714 Design Flow | 171 |
72 Lazy Transition Systems and Lazy State Graphs | 172 |
73 Overview and Example | 173 |
732 Second Timing Assumption | 174 |
733 Logic Minimization | 176 |
734 Summary | 177 |
741 Difference Assumptions | 179 |
743 Early Enabling Assumptions | 181 |
75 Synthesis with Relative Timing | 182 |
752 Synthesis Flow with Relative Timing | 184 |
753 Synthesis Algorithm | 185 |
76 Automatic Generation of Timing Assumptions | 186 |
761 Ordering Relations | 188 |
762 Delay Model | 190 |
77 BackAnnotation of Timing Constraints | 193 |
771 Correctness Conditions | 196 |
772 Problem Formulation | 197 |
773 Finding a Set of Timing Constraints | 198 |
78 Experimental Results | 201 |
782 A FIFO Controller | 203 |
783 RAPPID Control Circuits | 206 |
Design Examples | 209 |
81 Handshake Communication | 210 |
812 Circuit Synthesis | 211 |
82 VME Bus Controller | 217 |
822 VME Bus Controller Synthesis | 219 |
823 Lessons to be Learned from the Example | 225 |
831 Top Level Description | 226 |
833 Decomposed Solution for the Scheduler | 232 |
834 Synthesis of the Data Register | 235 |
835 Quality of the Results | 236 |
836 Lessons to be Learned from the Example | 237 |
841 Lazy Token Ring Description | 238 |
842 Adapter Synthesis | 239 |
843 A Model for Performance Analysis | 242 |
844 Lessons to be Learned from the Example | 243 |
Other Work | 245 |
92 Structural and Unfoldingbased Synthesis | 247 |
93 Direct Mapping of STGs into Asynchronous Circuits | 249 |
94 Datapath Design and Interfaces | 250 |
95 Test Pattern Generation and Design for Testability | 251 |
96 Verification | 252 |
97 Asynchronous Silicon | 253 |
Conclusions | 255 |
| 257 | |
| 271 | |
מהדורות אחרות - הצג הכל
Logic Synthesis for Asynchronous Controllers and Interfaces <span dir=ltr>J. Cortadella</span> אין תצוגה מקדימה זמינה - 2017 |
מונחים וביטויים נפוצים
algorithm arcs assume assumptions asynchronous circuits behavior binary bipartition Boolean function Boolean relation C-element characteristic function complex gate Computer-Aided Design concurrency reduction consider constraints corresponding CSC conflicts csc0 cycle datapath DC-set decomposed defined delay model delay-insensitive denoted derived dsr+ dtack EB(b encoding environment equation ER(x ER(x+ example excitation region exit borders firing gate delays gate implementation handshake hazard-free IEEE Computer Society IEEE Transactions input borders input events International Karnaugh map labeled logic decomposition logic synthesis LzTS methods minimal mutex MWFEB(b netlist non-input optimization output signal performance persistency Petri net Petri Nets petrify pre-regions problem Proc result Sect sequential shown in Fig Signal Transition Graphs signal transitions SIP-sets solution speed-independent circuits subset techniques tion token transition system trigger unreachable violations VLSI VME bus controller
קטעים בולטים
עמוד 257 - Average-case optimized transistor-level technology mapping of extended burst-mode circuits," in Proc. International Symposium on Advanced Research in Asynchronous Circuits and Systems, 1998, pp. 70-79. [21] P. Beerel and TH-Y. Meng, "Automatic gate-level synthesis of speedindependent circuits,