Synchronization of complex systems
Jordi Cortadella Universitat Politecnica de Catalunya Barcelona, Spain
Thanks to A. Chakraborty, T. Chelcea, M. Greenstreet and S. Nowick
Multiple clock domains
f1/f0 CLK1 CLK2
CLK
CLK (f0)
f2/f0
f3/f0
CLK3
Single clock (Mesochronous)
Rational clock frequencies
Independent clocks (plesiochronous if frequencies closely match)
2
CLK0
The problem: metastability
D Q D Q
R
D Q
R
setup hold
Classical synchronous solution
D Q D Q D Q D Q
T
Mean Time Between Failures f: frequency of the clock fD: frequency of the data tr: resolve time available W: metastability window : resolve time constant
Example
R
# FFs
1 FF 2 FF 3 FF
MTBF
15 min 9 days 23 years
4
MTBF
e tr 2 f f D W
How to live with metastability ?
Metastability cannot be avoided, it must be tolerated. Having a decent MTBF ( years) may result in a tangible impact in latency
Purely asynchronous systems can be designed failure-free
Synchronous and mixed synchronous-asynchronous systems need mechanisms with impact in latency But latency can be hidden in many cases
5
Different approaches
Pausible Clocks (Yun & Donohue 1996) Predict metastability-free transmission windows for domains with related clocks (Chakraborty & Greenstreet 2003) Use the waiting time in FIFOs to resolve metastability (Chelcea & Nowick 2001) And others
The term Globally Asynchronous, Locally Synchronous is typically used for these systems (Chapiro 1984)
Mutual exclusion element
req1
ack1
req2
ack2
Metastability
Mutual exclusion element
Metastability resolver
0
req1
ack2
req2
ack1
An asynchronous data latch with MS resolver can be built similarly
9
Abstraction of the MUTEX
R1
G1
MUTEX
R2 G2
10
A pausible clock generator
Environment
MUTEX [1, 2]
delay
11
Pausible clocks
Req Ack
Cntr
FF
ME MUTEX [1, 2]
delay CLK
Yun & Dooply, IEEE Trans. VLSI, Dec. 1999 Moore et al., ASYNC 2002
12
STARI (Self-Timed At Receivers Input)
Both clocks are generated from the same source The FIFO compensates for skew between transmitter and receiver M. Greenstreet, 1993
13
A Minimalist Interface
FIFO reduces to latch-X and a latch controller x can always be generated in such a way as to reliably transfer data from input to output Chakraborty & Greenstreet, 2002
14
A Minimalist Interface: 3 scenarios
Latch-X setup & hold Latch-R setup & hold x Permitted
The scenario is chosen at initialization
15
A Minimalist Interface: latch controller
The controller detects which transition arrives first (from T and R) and generates X accordingly
16
A Minimalist Interface: rational clocks
17
A Minimalist Interface: arbitrary clocks
Assumption: clocks are stable Each domain estimates the others frequency Residual error corrected using stuff bits
18
Mixed-Timing Interfaces
Async-Sync FIFO
Async-Sync FIFO
Asynchronous Domain Synchronous Domain 2 Synchronous Domain 1
Mixed-Clock FIFOs
Sync-Async FIFO
Chelcea & Nowick, 2001
19
Mixed-Clock FIFO: Block Level
synchronous put inteface
req_put data_put CLK_put
Mixed-Clock FIFO
full
req_get valid_get empty data_get CLK_get
synchronous get interface
20
Mixed-Clock FIFO: Block Level
Initiates put operations Bus for data items
Initiates get operations
Bus for data items
synchronous put inteface
req_put data_put CLK_put
Mixed-Clock FIFO
full
req_get valid_get empty data_get CLK_get
synchronous get interface
Controls put operations
Controls get operations
21
Mixed-Clock FIFO: Block Level
Indicates when FIFO full Indicates data items validity (always 1 in this design)
synchronous put inteface
req_put data_put CLK_put
Mixed-Clock FIFO
full
req_get valid_get empty data_get CLK_get
synchronous get interface
Indicates when FIFO empty
22
Mixed-Clock FIFO: Architecture
full req_put data_put CLK_put
Put Controller
Full Detector
cell
CLK_get data_get valid_get empty
Get Controller
cell
cell
cell
cell
req_get
Empty Detector
23
Mixed-Clock FIFO: Cell Implementation
CLK_put ptok_out
En
en_put
req_put data_put ptok_in
f_i e_i
SR
REG
gtok_out
En
gtok_in
en_get valid data_get
24
CLK_get
Mixed-Clock FIFO: Cell Implementation
CLK_put ptok_out
En
en_put
req_put data_put ptok_in
PUT INTERFACE
f_i e_i
SR
REG
GET INTERFACE
gtok_out
En
gtok_in
en_get valid data_get
25
CLK_get
Synchronization: summary
Resolving metastability implies latency Latency can be often hidden (FIFOs, Chelcea & Nowick) Clock frequencies can be estimated and clock edges predicted under the assumption of stable clocks (Chakraborty & Greenstreet) Pausible clocks are also possible (Yun & Donohue 1996) But still the nicest solutions are totally asynchronous
As presented by Fulcrum Microsystems in the last lecture
26
