Synchronization and Arbitration in Digital Systems

✍ Scribed by David J. Kinniment

• Year: 2008
• Tongue: English
• Leaves: 282
• Edition: 1
• Category: Library

✦ Synopsis

Today’s networks of processors on and off chip, operating with independent clocks, need effective synchronization of the data passing between them for reliability. When two or more processors request access to a common resource, such as a memory, an arbiter has to decide which request to deal with first. Current developments in integrated circuit processing are leading to an increase in the numbers of independent digital processing elements in a single system. With this comes faster communications, more networks on chip, and the demand for more reliable, more complex, and higher performance synchronizers and arbiters. Written by one of the foremost researchers in this area of digital design, this authoritative text provides in-depth theory and practical design solutions for the reliable working of synchronization and arbitration hardware in digital systems.The book provides methods for making real reliability measurements both on and off chip, evaluating some of the common difficulties and detailing circuit solutions at both circuit and system levels. Synchronization and Arbitration in Digital Systems also presents:mathematical models used to estimate mean time between failures in digital systems;a summary of serial and parallel communication techniques for on-chip data transmission;explanations on how to design a wrapper for a locally synchronous cell, highlighting the issues associated with stoppable clocks;an examination of various types of priority arbiters, using signal transition graphs to show the specification of different designs (from the simplest to more complex multi-way arbiters) including ways of solving problems encountered in a wide range of applications;essential information on systems composed of independently timed regions, including a discussion on the problem of choice and the factors affecting the time taken to make choices in electronics.With its logical approach to design methodology, this will prove an invaluable guide for electronic and computer engineers and researchers working on the design of digital electronic hardware. Postgraduates and senior undergraduate students studying digital systems design as part of their electronic engineering course will struggle to find a resource that better details the information given inside this book

✦ Table of Contents

Synchronization and Arbitration in Digital Systems......Page 1
Contents......Page 7
Preface......Page 11
List of Contributors......Page 15
Acknowledgements......Page 17
1.1 INTRODUCTION......Page 19
1.2 THE PROBLEM OF CHOICE......Page 20
1.3 CHOICE IN ELECTRONICS......Page 21
1.4 ARBITRATION......Page 23
1.5 CONTINUOUS AND DISCRETE QUANTITIES......Page 24
1.6 TIMING......Page 25
1.7 BOOK STRUCTURE......Page 27
Part I......Page 29
2 Modelling Metastability......Page 31
2.1 THE SYNCHRONIZER......Page 32
2.2 LATCH MODEL......Page 39
2.3 FAILURE RATES......Page 41
2.3.1 Event Histograms and MTBF......Page 46
2.4 LATCHES AND FLIP-FLOPS......Page 50
2.5 CLOCK BACK EDGE......Page 53
3.1 LATCHES AND METASTABILITY FILTERS......Page 57
3.2 EFFECTS OF FILTERING......Page 59
3.3 THE JAMB LATCH......Page 60
3.3.1 Jamb Latch Flip-. op......Page 63
3.4 LOW COUPLING LATCH......Page 65
3.5 THE Q-FLOP......Page 67
3.6 THE MUTEX......Page 68
3.7 ROBUST SYNCHRONIZER......Page 70
3.8 THE TRI-FLOP......Page 73
4.1 NOISE......Page 77
4.2 EFFECT OF NOISE ON A SYNCHRONIZER......Page 80
4.3.1 Synchronous Systems......Page 81
4.3.2 Asynchronous Systems......Page 84
5.1 CIRCUIT SIMULATION......Page 87
5.1.1 Time Step Control......Page 88
5.1.2 Long-term τ......Page 89
5.1.3 Using Bisection......Page 91
5.2 SYNCHRONIZER FLIP-FLOP TESTING......Page 93
5.3 RISING AND FALLING EDGES......Page 97
5.4 DELAY-BASED MEASUREMENT......Page 99
5.5 DEEP METASTABILITY......Page 101
5.6 BACK EDGE MEASUREMENT......Page 113
5.7.1 Failure Measurement......Page 115
5.7.2 Synchronizer Selection......Page 116
6 Conclusions Part I......Page 119
Part II......Page 121
7.1 LATENCY AND THROUGHPUT......Page 123
7.2 FIFO SYNCHRONIZER......Page 126
7.3 AVOIDING SYNCHRONIZATION......Page 128
7.4 PREDICTIVE SYNCHRONIZERS......Page 131
7.5.1 Locally Delayed Latching (LDL)......Page 133
7.5.2.1 Synchronization error detection......Page 136
7.5.2.2 Pipelining......Page 140
7.5.2.3 Recovery......Page 141
7.6 ASYNCHRONOUS COMMUNICATION MECHANISMS (ACM)......Page 143
7.6.2 Three-slot Mechanism......Page 146
7.6.3 Four-slot Mechanism......Page 148
7.6.4 Hardware Design and Metastability......Page 150
7.7.1.1 No acknowledge......Page 151
7.7.1.2 Unsynchronized reset back edge......Page 152
7.7.2.1 Disturbing a metastable latch......Page 153
7.7.2.2 The second chance......Page 154
7.7.2.3 Metastability blocker......Page 155
7.7.3.2 The redundant synchronizer......Page 156
8.1 COMMUNICATION ON CHIP......Page 161
8.1.1 Comparison of Network Architectures......Page 165
8.2 INTERCONNECT LINKS......Page 168
8.3.1 Using One Line......Page 173
8.3.2 Using Two Lines......Page 175
8.4 DIFFERENTIAL SIGNALLING......Page 177
8.5 PARALLEL LINKS......Page 179
8.5.1 One Hot Codes......Page 180
8.5.2 Transition Signalling......Page 184
8.5.3 n of m Codes......Page 185
8.5.4 Phase Encoding......Page 186
8.5.4.1 Phase encoding sender......Page 190
8.5.4.2 Receiver......Page 191
8.5.5 Time Encoding......Page 193
8.6 PARALLEL SERIAL LINKS......Page 198
9 Pausible and Stoppable Clocks in GALS......Page 201
9.1 GALS CLOCK GENERATORS......Page 202
9.2 CLOCK TREE DELAYS......Page 206
9.3 A GALS WRAPPER......Page 208
10 Conclusions Part II......Page 211
Part III......Page 215
11.1 INTRODUCTION......Page 217
11.2 ARBITER DEFINITION......Page 218
11.3 ARBITER APPLICATIONS, RESOURCE ALLOCATION POLICIES AND COMMON ARCHITECTURES......Page 220
11.4 SIGNAL TRANSITION GRAPHS, OUR MAIN MODELLING LANGUAGE......Page 223
12.1 BASIC CONCEPTS AND CONVENTIONS......Page 227
12.1.1 Two-phase or Non-return-to-zero (NRZ) Protocols......Page 228
12.1.2 Four-phase or Return-to-zero (RTZ) Protocols......Page 229
12.2 SIMPLE ARBITRATION BETWEEN TWO ASYNCHRONOUS REQUESTS......Page 230
12.3 SAMPLING THE LOGIC LEVEL OF AN ASYNCHRONOUS REQUEST......Page 235
12.4 SUMMARY OF TWO-WAY ARBITERS......Page 240
13 Multi-way Arbiters......Page 243
13.1 MULTI-WAY MUTEX USING A MESH......Page 244
13.2 CASCADED TREE ARBITERS......Page 245
13.3 RING-BASED ARBITERS......Page 248
14.1 INTRODUCTION......Page 253
14.2 PRIORITY DISCIPLINE......Page 254
14.3 DAISY-CHAIN ARBITER......Page 256
14.4 ORDERED ARBITER......Page 257
14.5 CANONICAL STRUCTURE OF PRIORITY ARBITERS......Page 258
14.6 STATIC PRIORITY ARBITER......Page 259
14.7 DYNAMIC PRIORITY ARBITER......Page 264
15 Conclusions Part III......Page 271
References......Page 273
Index......Page 279