Principles of Asynchronous Cir

Preface xiPart I Asynchronous circuit design – A tutorialAuthor: Jens Sparsø1IntroducTIon 31.1 Why consider asynchronous circuits? 31.2 Aims and background 41.3 Clocking versus handshaking 51.4 Outline of Part I 82Fundamentals 92.1 Handshake protocols 92.1.1 Bundled-data protocols 92.1.2 The 4-phase dual-rail protocol 112.1.3 The 2-phase dual-rail protocol 132.1.4 Other protocols 132.2 The Muller C-element and the indicaTIon principle 142.3 The Muller pipeline 162.4 Circuit implementaTIon styles 172.4.1 4-phase bundled-data 182.4.2 2-phase bundled data (Micropipelines) 192.4.3 4-phase dual-rail 202.5 Theory 232.5.1 The basics of speed-independence 232.5.2 ClassificaTIon of asynchronous circuits 252.5.3 Isochronic forks 262.5.4 Relation to circuits 262.6 Test 272.7 Summary 283Static data-flow structures 293.1 Introduction 293.2 Pipelines and rings 30vvi PRINCIPLES OF ASYNCHRONOUS CIRCUIT DESIGN3.3 Building blocks 313.4 A simple example 333.5 Simple applications of rings 353.5.1 Sequential circuits 353.5.2 Iterative computations 353.6 FOR, IF, and WHILE constructs 363.7 A more complex example: GCD 383.8 Pointers to additional examples 393.8.1 A low-power filter bank 393.8.2 An asynchronous microprocessor 393.8.3 A fine-grain pipelined vector multiplier 403.9 Summary 404Performance 414.1 Introduction 414.2 A qualitative view of performance 424.2.1 Example 1: A FIFO used as a shift register 424.2.2 Example 2: A shift register with parallel load 444.3 Quantifying performance 474.3.1 Latency, throughput and wavelength 474.3.2 Cycle time of a ring 494.3.3 Example 3: Performance of a 3-stage ring 514.3.4 Final remarks 524.4 Dependency graph analysis 524.4.1 Example 4: Dependency graph for a pipeline 524.4.2 Example 5: Dependency graph for a 3-stage ring 544.5 Summary 565Handshake circuit implementations 575.1 The latch 575.2 Fork, join, and merge 585.3 Function blocks – The basics 605.3.1 Introduction 605.3.2 Transparency to handshaking 615.3.3 Review of ripple-carry addition 645.4 Bundled-data function blocks 655.4.1 Using matched delays 655.4.2 Delay selection 665.5 Dual-rail function blocks 675.5.1 Delay insensitive minterm synthesis (DIMS) 675.5.2 Null Convention Logic 695.5.3 Transistor-level CMOS implementations 705.5.4 Martin’s adder 715.6 Hybrid function blocks 735.7 MUX and DEMUX 755.8 Mutual exclusion, arbitration and metastability 775.8.1 Mutual exclusion 775.8.2 Arbitration 795.8.3 Probability of metastability 79Contents vii5.9 Summary 806Speed-independent control circuits 816.1 Introduction 816.1.1 Asynchronous sequential circuits 816.1.2 Hazards 826.1.3 Delay models 836.1.4 Fundamental mode and input-output mode 836.1.5 Synthesis of fundamental mode circuits 846.2 Signal transition graphs 866.2.1 Petri nets and STGs 866.2.2 Some frequently used STG fragments 886.3 The basic synthesis procedure 916.3.1 Example 1: a C-element 926.3.2 Example 2: a circuit with choice 926.3.3 Example 2: Hazards in the simple gate implementation 946.4 Implementations using state-holding gates 966.4.1 Introduction 966.4.2 Excitation regions and quiescent regions 976.4.3 Example 2: Using state-holding elements 986.4.4 The monotonic cover constraint 986.4.5 Circuit topologies using state-holding elements 996.5 Initialization 1016.6 Summary of the synthesis process 1016.7 Petrify: A tool for synthesizing SI circuits from STGs 1026.8 Design examples using Petrify 1046.8.1 Example 2 revisited 1046.8.2 Control circuit for a 4-phase bundled-data latch 1066.8.3 Control circuit for a 4-phase bundled-data MUX 1096.9 Summary 1137Advanced 4-phase bundled-dataprotocols and circuits1157.1 Channels and protocols 1157.1.1 Channel types 1157.1.2 Data-validity schemes 1167.1.3 Discussion 1167.2 Static type checking 1187.3 More advanced latch control circuits 1197.4 Summary 1218High-level languages and tools 1238.1 Introduction 1238.2 Concurrency and message passing in CSP 1248.3 Tangram: program examples 1268.3.1 A 2-place shift register 1268.3.2 A 2-place (ripple) FIFO 126viii PRINCIPLES OF ASYNCHRONOUS CIRCUIT DESIGN8.3.3 GCD using while and if statements 1278.3.4 GCD using guarded commands 1288.4 Tangram: syntax-directed compilation 1288.4.1 The 2-place shift register 1298.4.2 The 2-place FIFO 1308.4.3 GCD using guarded repetition 1318.5 Martin’s translation process 1338.6 Using VHDL for asynchronous design 1348.6.1 Introduction 1348.6.2 VHDL versus CSP-type languages 1358.6.3 Channel communication and design flow 1368.6.4 The abstract channel package 1388.6.5 The real channel package 1428.6.6 Partitioning into control and data 1448.7 Summary 146Appendix: The VHDL channel packages 148A.1 The abstract channel package 148A.2 The real channel package 150Part II Balsa - An Asynchronous Hardware Synthesis SystemAuthor: Doug Edwards, Andrew Bardsley9An introduction to Balsa 1559.1 Overview 1559.2 Basic concepts 1569.3 Tool set and design flow 1599.4 Getting started 1599.4.1 A single-place buffer 1619.4.2 Two-place buffers 1639.4.3 Parallel composition and module reuse 1649.4.4 Placing multiple structures 1659.5 Ancillary Balsa tools 1669.5.1 Makefile generation 1669.5.2 Estimating area cost 1679.5.3 Viewing the handshake circuit graph 1689.5.4 Simulation 16810The Balsa language 17310.1 Data types 17310.2 Data typing issues 17610.3 Control flow and commands 17810.4 Binary/unary operators 18110.5 Program structure 18110.6 Example circuits 18310.7 Selecting channels 190Contents ix11Building library components 19311.1 Parameterised descriptions 19311.1.1 A variable width buffer definition 19311.1.2 Pipelines of variable width and depth 19411.2 Recursive definitions 19511.2.1 An n-way multiplexer 19511.2.2 A population counter 19711.2.3 A Balsa shifter 20011.2.4 An arbiter tree 20212A simple DMA controller 20512.1 Global registers 20512.2 Channel registers 20612.3 DMA controller structure 20712.4 The Balsa description 21112.4.1 Arbiter tree 21112.4.2 Transfer engine 21212.4.3 Control unit 213Part III Large-Scale Asynchronous Designs13Descale 221Joep Kessels & Ad Peeters, Torsten Kramer and Volker Timm13.1 Introduction 22213.2 VLSI programming of asynchronous circuits 22313.2.1 The Tangram toolset 22313.2.2 Handshake technology 22513.2.3 GCD algorithm 22613.3 Opportunities for asynchronous circuits 23113.4 Contactless smartcards 23213.5 The digital circuit 23513.5.1 The 80C51 microcontroller 23613.5.2 The prefetch unit 23913.5.3 The DES coprocessor 24113.6 Results 24313.7 Test 24513.8 The power supply unit 24613.9 Conclusions 24714An Asynchronous Viterbi Decoder 249Linda E. M. Brackenbury14.1 Introduction 24914.2 The Viterbi decoder 25014.2.1 Convolution encoding 25014.2.2 Decoder principle 25114.3 System parameters 25314.4 System overview 254x PRINCIPLES OF ASYNCHRONOUS CIRCUIT DESIGN14.5 The Path Metric Unit (PMU) 25614.5.1 Node pair design in the PMU 25614.5.2 Branch metrics 25914.5.3 Slot timing 26114.5.4 Global winner identification 26214.6 The History Unit (HU) 26414.6.1 Principle of operation 26414.6.2 History Unit backtrace 26414.6.3 History Unit implementation 26714.7 Results and design evaluation 26914.8 Conclusions 27114.8.1 Acknowledgement 27214.8.2 Further reading 27215Processors 273Jim D. Garside15.1 An introduction to the Amulet processors 27415.1.1 Amulet1 (1994) 27415.1.2 Amulet2e (1996) 27515.1.3 Amulet3i (2000) 27515.2 Some other asynchronous microprocessors 27615.3 Processors as design examples 27815.4 Processor implementation techniques 27915.4.1 Pipelining processors 27915.4.2 Asynchronous pipeline architectures 28115.4.3 Determinism and non-determinism 28215.4.4 Dependencies 28815.4.5 Exceptions 29715.5 Memory – a case study 30215.5.1 Sequential accesses 30215.5.2 The Amulet3i RAM 30315.5.3 Cache 30715.6 Larger asynchronous systems 31015.6.1 System-on-Chip (DRACO) 31015.6.2 Interconnection 31015.6.3 Balsa and the DMA controller 31215.6.4 Calibrated time delays 31315.6.5 Production test 31415.7 Summary 315Epilogue 317References 319Index 333