Synchronization, Metastability

and Arbitration
Did you vote for Bush or Gore?
Didnt have enough time to decide.
Well, which hole did you punch?
Both, but not very hard...

WARD &
HALSTEAD

"If you can't be just,

be arbitrary"

6.004
NERD KIT

- Wm Burroughs, Naked Lunch

- US Supreme Court 12/00

Handouts: Lecture Slides

6.004 Spring 2003

3/04/03

L08 - Synchronization 1

The Importance of being Discrete

We avoid possible errors by disciplines that avoid asking the tough
questions using a forbidden zone in both voltage and time
dimensions:

Digital Values:

Digital Time:
Problem: Which transition
happened first? questions
Solution: Dynamic Discipline:
avoid asking such questions
in close races

Problem: Distinguishing voltages

representing 1 from 0
Solution: Forbidden Zone: avoid
using similar voltages for 1
and 0

tS

VOUT
VOH
VIH

VIL

Clk

VOL
VOL VIL

6.004 Spring 2003

VIH VOH

VIN

tH

3/04/03

tCD
tPD
L08 - Synchronization 2

If we follow these simple rules

Can we guarantee that our system will always work?
In

DQ

In
Combinational
logic

DQ

Combinational
logic

DQ

Out
Combinational
logic

DQ

Out

Clk

Combinational
logic

DQ

Combinational
logic

DQ

Combinational
logic

DQ

Out

With careful design we can make sure that the dynamic

discipline is obeyed everywhere*...
* well, almost everywhere...
6.004 Spring 2003

3/04/03

L08 - Synchronization 3

The world doesnt run on our clock!

What if each button input is
an asynchronous 0/1
level?
0

But what
About the
Dynamic
Discipline?

0
1

B0
B1

Lock

To build a system with asynchronous inputs, we have to break the

rules: we cannot guarantee that setup and hold time requirements
are met at the inputs!
So, lets use a synchronizer at each input:
0

U(t)

(Unsynchronized)

Synchronizer

S(t)

Valid except for brief periods

following active clock edges

(Synchronized)

Which edge
Came FIRST?

Clock
6.004 Spring 2003

3/04/03

L08 - Synchronization 4

The Asynchronous Arbiter:

a classic problem
UNSOLVABLE
B:
C:

at t B

at t C

Arbiter specifications:
finite tD (decision time)
finite tE (allowable error)
value of S at time tC+tD:
1 if tB < tC tE
0 if tB > tC + tE
0, 1 otherwise

Arbiter

B:

>t E

C:

tD

S:
CASE 1

6.004 Spring 2003

3/04/03

For NO finite
value of tE and tD
is this spec
realizable, even
with reliable
components!
>t E
tD

CASE 2

tD

CASE 3

L08 - Synchronization 5

Violating the Forbidden Zone

B:
C:

at t B

at t C

Arbiter

Issue: Mapping the continuous variable (tB tC)

onto the discrete variable S in bounded time.
Arbiter
Output

With
Withno
noforbidden
forbiddenzone,
zone,all
allinputs
inputshave
haveto
to
be
bemapped
mappedto
toaavalid
validoutput.
output. As
Asthe
theinput
input
approaches
discontinuities
in
the
mapping,
approaches discontinuities in the mapping,
itittakes
takeslonger
longerto
todetermine
determinethe
theanswer.
answer.
Given
a
particular
time
bound,
you
Given a particular time bound, youcan
canfind
find
an
aninput
inputthat
thatwont
wontbe
bemapped
mappedto
toaavalid
valid
output
outputwithin
withinthe
theallotted
allottedtime.
time.

o
B
Earlier
6.004 Spring 2003

(t B=t C)

C
Earlier
3/04/03

t B-t C

L08 - Synchronization 6

Unsolvable?
that cant be true...
DECISION TIME is TPD of flop.

Lets just use a D Flip Flop:

B:
C:

at t B

ALLOWABLE ERROR is max(tSETUP, tHOLD)

Our logic:

TPD after TC, well have

at t C

Q=0 iff tB + tSETUP < tC

Q=1 iff tC + tHOLD < tB
Q=0 or 1 otherwise.

Were lured by the digital

abstraction into assuming
that Q must be either 1 or 0.
But lets look at the input
latch in the flip flop whe B and
C change at about the same
time...
6.004 Spring 2003

master

slave

3/04/03

L08 - Synchronization 7

The Mysterious Metastable State

Vin

0
1

Vout

Q
Y

Vout

2. Vin = Vout

Latched in
a 1 state

Latched in
an undefined
state

Recall that the latch output is the

solution to two simultaneous
constraints:
1. The VTC of 2 cascaded
gates; and

VTC of
inverter pair

VTC of feedback
path (Vin=Vout)

Latched in
a 0 state

Vin

In addition to our expected stable solutions, we find an unstable

equilibrium in the forbidden zone called the Metastable State
6.004 Spring 2003

3/04/03

L08 - Synchronization 8

Metastable State: Properties

1.

It corresponds to an invalid logic

level the switching threshold of
the device.

2. Its an unstable equilibrium; a small

perturbation will cause it to
accelerate toward a stable 0 or 1.
3. It will settle to a valid 0 or 1...
eventually.
4. BUT depending on how close it is
to the Vin=Vout fixed point of the
device it may take arbitrarily long
to settle out.
5. EVERY bistable system exhibits at
least one metastable state!
6.004 Spring 2003

3/04/03

EVERY bistable system?

Yep, every last one.
Coin flip??
Could land on edge.
Horse race??
Photo finish.
Presidential Election??
(Wheres this twit
been hiding???)
L08 - Synchronization 9

Observed Behavior:
typical metastable symptoms
Following a clock edge on an asynchronous input:

CLK
D
We may see exponentially-distributed metastable intervals:

Q
Or periods of high-frequency oscillation (if the feedback path is long):

6.004 Spring 2003

3/04/03

L08 - Synchronization 10

Mechanical Metastability
If we launch a ball up a hill
we expect one of 3
possible outcomes:
State A

a) Goes over
b) Rolls back
c) Stalls at the apex
Metastable State

State A

6.004 Spring 2003

State B

That last outcome is not

stable.
- a gust of wind
- Brownian motion
- it doesnt take much
3/04/03

L08 - Synchronization 11

How do balls relate to digital logic?

Our hill is simply the derivative
of the VTC (Voltage Transfer
Curve).

Vout

Notice that the higher the gain

thru the transition region,
the steeper the peak of the
hill... making it harder to get
into a metastable state.

Vout
Vin

Vin

6.004 Spring 2003

3/04/03

We can decrease the probability

of getting into the
metastable state, but we
cant eliminate it
L08 - Synchronization 12

The Metastable State:

Why is it an inevitable risk of synchronization?

Our active devices always have a fixed-point voltage, VM, such that
VIN=VM implies VOUT = VM

Violation of dynamic discipline puts our feedback loop at some

voltage V0 near VM

The rate at which V progresses toward a stable 0 or 1 value is

proportional to (V - VM)

The time to settle to a stable value depends on (V0 - VM); its

theoretically infinite for V0 = VM

Since theres no lower bound on (V0 - VM), theres no upper bound

on the settling time.

Noise, uncertainty complicate analysis (but dont help).

6.004 Spring 2003

3/04/03

L08 - Synchronization 13

Sketch of analysis I.
Assume asynchronous 0->1
at TA, clock period CP:

A
Synchronizer

Whats the FF output voltage,

V0, immediately after TA?

S(t)
(Synchronized)

C
Clock

Potential trouble comes when V0 is near the metastable point, VM

1. Whats the probability that the

voltage, V0, immediately after
TA is within of VM?

V0
VM

t A-t C
< tS+tH

P[ V 0 VM ]

CP
6.004 Spring 2003

3/04/03

CP
2

(tS + tH ) (VH VL )
L08 - Synchronization 14

Vin

Sketch of analysis II.

Vout

Vout

1
C

We can model our

combinational
cycle as an
amplifier with gain
A and saturation
at VH, VL

2. For Vout near VM, Vout(t) is an

exponential whose time constant
reflects RC/A:
3. Given interval T, we can compute a
minimum value of = |V0-VM| that will
guarantee validity after T:
4. Probability of metastability after T is
computed by probability of a V0
yielding (T)
6.004 Spring 2003

3/04/03

VH

Slope = A
Vin

VL

Vout(t)- VM e t(A-1)/RC
e t/

(T) (VH VM) e -T/

PM(T) P[|V0-VM| < (T)]

K e -T/
L08 - Synchronization 15

Failure Probabilities vs Delay

Making conservative assumptions about the distribution of V0 and system
time constants, and assuming a 100 MHz clock frequency, we get results
like the following:
Average time
Delay
P(Metastable)
between failures
31 ns

3x10-16

1 year

33.2 ns

3x10-17

10 years

100 ns

10-45

1030 years!

[For comparision:
Age of oldest hominid fossil: 5x106 years
Age of earth: 5x109 years]

Lesson: Allowing a bit of settling time is an

easy way to avoid metastable states in
practice!
6.004 Spring 2003

3/04/03

L08 - Synchronization 16

The Metastable State:

a brief history

Antiquity: Early recognition

Buridens Ass, and other fables

Denial: Early 70s

Widespread disbelief. Early analyses

documenting inevitability of problem
rejected by skeptical journal editors.

Folk Cures: 70s-80s

Popular pastime: Concoct a Cure for

the problem of synchronization
failure. Commercial synchronizer
products.

Reconciliation: 80s-90s

6.004 Spring 2003

Acceptance of the reality:

synchronization takes time.
Interesting special case solutions.
3/04/03

L08 - Synchronization 17

Ancient Metastability
Metastability is the occurrence of a persistent invalid
output an unstable equilibria.
The idea of Metastability is not new:
I Shoulda
Taken 6.004!

The Paradox of Buridans Ass

Buridan, Jean (1300-58), French Scholastic philosopher,
who held a theory of determinism, contending that the
will must choose the greater good. Born in Bethune, he
was educated at the University of Paris, where he studied with
the English Scholastic philosopher William of Ockham (whom
you might recall from his razor business). After his studies were
completed, he was appointed professor of philosophy, and later
rector, at the same university. Buridan is traditionally, but
probably incorrectly, associated with a philosophical dilemma of
moral choice called "Buridan's ass.
In the problem an ass starves to death between two alluring
bundles of hay because it does not have the will to decide which
one to eat.

6.004 Spring 2003

3/04/03

L08 - Synchronization 18

Folk Cures
the perpetual motion machine of digital logic
Bad Idea # 1: Detect metastable state & Fix
Async
Input

FF

"FIXER"

"Clean"
Output

delay

Bug: detecting metastability

is itself subject to
metastable states, i.e., the
fixer will fail to resolve the
problem in bounded time.

Bad Idea #2: Define the problem away by making metastable point a valid output
valid
"0"

valid
"1"

Bug: the memory element will

flip some valid 0 inputs to
1 after a while.
Many other bad ideas involving noise
injection, strange analog circuitry, have
been proposed.

6.004 Spring 2003

3/04/03

L08 - Synchronization 19

Theres no easy solution

so, embrace the confusion.

"Metastable States":
Inescapable consequence of bistable systems
Eventually a metastable state will resolve itself to valid binary
level.
However, the recovery time is UNBOUNDED ... but influenced by
parameters (gain, noise, etc)
Probability of a metastable state falls off EXPONENTIALLY with
time -- modest delay after state change can make it very
unlikely.
Our STRATEGY; since we cant eliminate metastability, we will do
the best we can to keep it from contaminating our designs
6.004 Spring 2003

3/04/03

L08 - Synchronization 20

Modern Reconciliation:
delay buys reliability
A metastable state here
will probably resolve itself
to a valid level before it
gets into my circuit.

Synchronizers, extra flip

flops between the
asynchronous input and
your logic, are the best
insurance against
metastable states.

In

DQ

DQ

Combinational
logic

DQ

Out

Clk

The higher the clock rate,

the more synchronizers
should be considered.

And one here will almost certainly

get resolved.

In

DQ

DQ

DQ

Combinational
logic

DQ

Out

Clk

6.004 Spring 2003

3/04/03

L08 - Synchronization 21

Things we CANT build

1. Bounded-time Asynchronous Arbiter:
B
C

Arbiter

S=0 iff B edge first, 1 iff C edge first,

1 or 0 if nearly coincident

S valid after tpd following (either) edge

2. Bounded-time Synchronizer:
Asynchronous
Input

Output = D at active clock edge, either 1 or 0

iff D invalid near clock edge

Q valid after tpd following active clock edge

3. Bounded-time Analog Comparator:

Continuous
Variable

6.004 Spring 2003

> 3.14159 ?

3/04/03

0 or 1,
finite tpd

L08 - Synchronization 22

Some things we CAN build

1. Unbounded-time Asynchronous Arbiter:
B
C

S valid when Done=1; unbounded time.

Arbiter Done

S=0 iff B edge first, 1 iff C edge first,

1 or 0 if nearly coincident

2. Unbounded-time Analog Comparator:

Continuous
Variable

0 or 1

> 3.14159 ?
Done

After arbitrary interval,

decides whether input at
time of last active clock
edge was above/below
threshold.

3. Bounded-time combinational logic:

Produce an output transition within a
fixed propagation delay of first (or
second) transition on the input.

6.004 Spring 2003

3/04/03

L08 - Synchronization 23

Interesting Special Case Hacks

Predictive periodic synchronization:
Data2

Data1

Exploits fact that, given 2 periodic

clocks, close calls are predictable.
Predicts, and solves in advance,
arbitration problems (thus
eliminating cost of delay)

CKL2
CKL1

Mesochronous communication:
Data1
CLK2
Data2
delay

Constraints on clock timing periodicity,

etc can often be used to hide time
overhead associated with synchronization.

CLK1
CLK2
6.004 Spring 2003

For systems with unsychronized clocks

of same nominal frequency. Data goes
to two flops clocked a half period apart;
one output is bound to be clean. An
observer circuit monitors the slowlyvarying phase relationship between the
clocks, and selects the clean output via
a lenient MUX.

3/04/03

L08 - Synchronization 24

Every-day Metastability - I
Ben Bitdiddle tries the
famous 6.004 defense:
Ben leaves the Bit Bucket
Caf and approaches fork in
the road. He hits the barrier
in the middle of the fork, later
explaining I cant be expected
to decide which fork to take in
bounded time!.

Bit
Bucket
Cafe

Is the accident Bens fault?

Yes; he should have stopped until his
decision was made.
Judge R. B. Trator, MIT 86
6.004 Spring 2003

3/04/03

L08 - Synchronization 25

Every-day Metastability - II
GIVEN:

ST

Normal traffic light:

GREEN, YELLOW, RED sequence

55 MPH Speed Limit
Sufficiently long YELLOW, GREEN
periods
Analog POSITION input
digital RED, YELLOW, GREEN inputs
digital GO output

P
O

Can one reliably obey....

LAW #1: DONT CROSS LINE while light is RED.
GO = GREEN
LAW #2: DONT BE IN INTERSETION while light is RED.

PLAUSIBLE STRATEGIES:
A. Move at 55. At calculated distance D from light, sample color (using an
unbounded-time synchronizer). GO ONLY WHEN stable GREEN.
B. Stop 1 foot before intersection. On GREEN, gun it.
6.004 Spring 2003

3/04/03

L08 - Synchronization 26

Summary
The most difficult decisions
are those that matter the least.
As a system designer
Avoid the problem altogether, where possible
Use single clock, obey dynamic discipline
Avoid state. Combinational logic has no metastable
states!

Sometimes,
I just like
to sit in
my maze
motionless-for a very
long time.

Delay after sampling asynchronous inputs: a

fundamental cost of synchronization
6.004 Spring 2003

3/04/03

L08 - Synchronization 27