Delay Insensitive Circuits -- Structures, Semantics, and Strategies

Description

a self-contained, full length tutorial treatment of delay insensitive circuit design and verification suitable for independent study at the graduate or professional levels Contents......Page 4 Background and Motivation......Page 15 Why to Study Delay Insensitive Circuits......Page 17 Audience......Page 18 Technological neutrality......Page 19 Configurable devices......Page 20 Concurrency theory......Page 21 Random tips on reading this book......Page 22 How not to do it with logic gates......Page 25 Towards a reusable implementation......Page 26 How not to do it with DI primitives......Page 27 Better building blocks......Page 28 Implications of the current solution......Page 29 Ways forward from the current solution......Page 30 A two-output primitive......Page 32 Yet another majority gate......Page 33 Back to the drawing board......Page 35 What a sequencer does......Page 37 Implications of this solution......Page 38 The Lay of the Land......Page 41 The process model......Page 42 Block diagrams......Page 44 Methodology......Page 45 Flattening......Page 46 Trace structural composition......Page 47 Notation and conventions of Petri nets......Page 49 Expressiveness of Petri nets......Page 51 Compositionality of Petri nets......Page 52 Limitations of Petri nets......Page 54 Combinator examples......Page 55 Repetition......Page 58 Conditional execution......Page 60 Adaptation to an environment......Page 61 Reachability graphs......Page 67 Reachability graph algorithms......Page 68 Operation......Page 71 Limitations......Page 73 Utility......Page 74 Quiescent traces......Page 75 Trace analysis......Page 76 From transducers to trace recognizers......Page 77 A preliminary subgraph......Page 78 Edge cases......Page 79 Other trace recognizers......Page 80 Interim remarks......Page 83 Formal Models......Page 85 Petri Net Plumbing......Page 87 Domains and ranges......Page 88 Ordinals......Page 89 A concrete model......Page 90 Presets and postsets......Page 91 Open Petri nets......Page 92 Process models......Page 93 Rewriting......Page 94 Sums......Page 97 Completion......Page 99 Parallel composition......Page 102 Sequential composition......Page 103 Choice......Page 105 Recursion......Page 111 Math usage......Page 121 Graphs......Page 122 Ordinals......Page 127 Overview......Page 128 Derivation......Page 129 Divergence propagation......Page 130 Disabled inputs......Page 132 Numbered vertices......Page 134 Anonymous edge reduction......Page 135 Overview......Page 137 Derivation......Page 138 Redundant path elimination......Page 141 Overview......Page 143 Derivation......Page 144 Overview......Page 149 Derivation......Page 153 Finite automata......Page 157 Sequences......Page 158 State graphs......Page 159 Deterministic finite automata......Page 160 The transducer......Page 161 Overview......Page 162 Derivation......Page 166 Overview......Page 169 Derivation......Page 172 Non-deterministic relational trace recognizer......Page 175 Deterministic relational trace recognizer......Page 177 Alternative extensional descriptions......Page 179 Overview......Page 181 Preparation......Page 186 Specification......Page 191 Process combinators revisited......Page 193 Block Building......Page 195 Creating a list......Page 196 Deleting from a list......Page 197 Inverse of a list......Page 198 Primitive blocks......Page 200 Hierarchical blocks......Page 201 Block combinators......Page 203 Block algebra......Page 204 Conventions about schematics......Page 205 Specifying a schematic by a netlist......Page 206 From hierarchical blocks to netlists......Page 207 Non-unit lists......Page 208 Unit lists......Page 209 Non-unit lists......Page 210 Unit lists......Page 211 From blocks and netlists to processes......Page 212 Alphabet soup......Page 213 More transformations......Page 215 Connection patterns......Page 216 Schematic capture......Page 217 Permutations......Page 221 Generalized terminal rotations......Page 230 Cascades......Page 233 Module Families......Page 235 Petri net optimizations......Page 237 Parallel fusion......Page 238 Serial transition fusion......Page 239 Serial place fusion......Page 241 Self-loop place removal......Page 243 Redundant cycle removal......Page 244 Miscellaneous static optimizations......Page 246 The whole mix......Page 247 Overview......Page 248 Specifications......Page 249 The continuing saga......Page 252 Cardinality and modularity......Page 253 Specifications......Page 254 Implications......Page 260 Three-terminal primitive generalizations......Page 265 Arbiter generalizations......Page 268 Decisions, Decisions......Page 271 Ordered trees......Page 272 Computation......Page 273 Notation......Page 274 Lateral......Page 275 Bilateral......Page 277 General......Page 281 Quadrangular decision waits......Page 285 Basic......Page 287 Vertical......Page 291 General......Page 295 A revised planar decision wait generating function......Page 296 Multidimensional decision waits......Page 298 Dendriform......Page 299 Crossbar......Page 301 Decision wait transformations......Page 303 Permuting along the axes......Page 304 Permuting the axes......Page 305 Optimized decision waits......Page 306 Global decompositions......Page 307 Quadrangular......Page 308 Dendriform......Page 309 Crossbar......Page 310 General......Page 311 Thin on the Ground......Page 315 Ordinals......Page 316 Transposing......Page 317 Coordinates......Page 318 Coordinate transformations......Page 319 Permuting along the axes......Page 320 Permuting the axes......Page 321 Fallback position......Page 322 Degenerate......Page 323 Separable......Page 324 Spanning......Page 327 Enmeshed......Page 333 Multidimensional sparse decision waits......Page 342 Dendriform......Page 343 Crossbar......Page 345 Optimization......Page 352 Sparse global decompositions......Page 353 General combining form......Page 354 Decomposition strategies......Page 355 Input symbol assignment......Page 357 Process specification......Page 358 Correctness......Page 359 All About Arbiters......Page 361 Permutations......Page 362 Probability theory......Page 363 Mesh......Page 364 Dendriform......Page 374 Token ring......Page 381 General......Page 388 Transfer functions......Page 390 Probability vectors and distributions......Page 391 Incremental transfer function......Page 393 Incremental token distribution......Page 398 Cumulative transfer function......Page 399 Access patterns......Page 401 Temporal locality......Page 402 Expectation......Page 405 Optimization......Page 406 A two-wire protocol......Page 411 Dual rail codes......Page 412 Constant weight codes......Page 413 General delay insensitive codes......Page 414 Encoders......Page 415 Basic......Page 417 Front optimized......Page 418 Back optimized......Page 419 Decoders......Page 420 Basic......Page 421 Joinable......Page 429 Factorable......Page 430 Partitionable......Page 434 General......Page 436 Sequencers......Page 437 Majority gates......Page 439 Transcoders......Page 440 Basic......Page 442 Partitionable......Page 444 General......Page 446 Working on the Railroad......Page 449 Adders......Page 450 Subtracters......Page 458 Buffers......Page 462 Transcoding algorithm......Page 467 Circuit derivation......Page 469 Sperner to dual rail conversion......Page 473 Preparation......Page 474 Derivation......Page 475 Dual rail toggles......Page 480 Channel demultiplexers......Page 481 Channel multiplexers......Page 482 Micropipeline controllers......Page 484 A parallel transcoder......Page 486 Synthesis......Page 489 State Based Synthesis......Page 491 The uncomplicated case......Page 492 Complications......Page 493 Non-quiescent processes......Page 494 Non-deterministically concurrent processes......Page 495 Anti-refined transducers......Page 499 Feedback anti-refined transducers......Page 500 Basic synthesis......Page 505 Decomposition......Page 507 Building blocks......Page 509 Loose ends......Page 516 Input reduction......Page 519 Decomposition......Page 520 Combining form......Page 525 State reduction......Page 526 Combining form......Page 527 Decomposition......Page 528 Combining form......Page 530 Overview......Page 533 Mutual recurrences......Page 535 Ad hoc solution......Page 536 Solution by lists of functions......Page 537 Solution by dependence graphs......Page 538 Refined canonical forms......Page 540 Decomposition......Page 542 Interacting state based synthetic communities......Page 543 Places......Page 544 State based transition arrays......Page 545 Combining form......Page 547 Interacting direct mapped synthetic communities......Page 551 Overview......Page 553 Transitions......Page 554 Lockable transitions......Page 559 Monitors......Page 562 Direct mapped transition arrays......Page 567 A naive solution......Page 569 A better solution......Page 570 Concluding remarks......Page 571 Appendices......Page 573 CMOS inverters......Page 575 Unexposed delays......Page 576 Conclusions......Page 577 Theoretical primer......Page 579 Continuity......Page 580 Ordering of functions......Page 581 CPO Structure......Page 582 Least upper bounds......Page 583 Continuity of process combinators......Page 584 Further work......Page 585 Decision Wait Metrics......Page 587 Quadrangular......Page 588 Cascading......Page 589 Critical path length......Page 590 Cascading......Page 592 Quadrangular......Page 594 Dendriform......Page 597 Crossbar......Page 599 General......Page 601 Latencies as a vector space......Page 603 Manhattan distances......Page 604 Expected wire delays......Page 605 Parallel combination of latency vectors......Page 606 Contention......Page 609 Tree......Page 612 Mesh......Page 613 Token ring......Page 615 General......Page 618 Dual Rail Buffer Cell Theory of Operation......Page 621 Bibliography......Page 631