Synchronization, Metastability and Arbitration The Importance of being Discrete

Synchronization, Metastability and Arbitration

The Importance of being Discrete

If we follow these simple rules…

The world doesn’t run on our clock!

The Asynchronous Arbiter: a classic problem

• 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

Violating the Forbidden Zone

• With no “forbidden zone,” all inputs have to be mapped to a valid output. As the input approaches discontinuities in the mapping, it takes longer to determine the answer. Given a particular time bound, you can find an input that won’t be mapped to a valid output within the allotted time.

Unsolvable? that can’t be true...

• We’re 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...

The Mysterious Metastable State

• Recall that the latch output is the solution to two simultaneous constraints:

• The VTC of 2 cascaded gates; and
• Vin = Vout

Metastable State: Properties

• It corresponds to an invalid logic level – the switching threshold of the device.

• Its an unstable equilibrium; a small perturbation will cause it to accelerate toward a stable 0 or 1.

• It will settle to a valid 0 or 1... eventually.

• BUT – depending on how close it is to the Vin = Vout “fixed point” of the device – it may take arbitrarily long to settle out.

• EVERY bistable system exhibits at least one metastable state!

Observed Behavior: typical metastable symptoms

Mechanical Metastability

• If we launch a ball up a hill we expect one of 3 possible outcomes:

• Goes over
• Rolls back
• Stalls at the apex

How do balls relate to digital logic?

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

• 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.

• We can decrease the probability of getting into the metastable state, but we can’t eliminate it…

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 there’s no lower bound on (V0 -VM), there’s no upper bound on the settling time.

• Noise, uncertainty complicate analysis (but don’t help).

Sketch of analysis… I.

• Assume asynchronous 0->1 at TA, clock period CP:

• Whats the FF output voltage, V0, immediately after TA?

Sketch of analysis… II.

• For Vout near VM, Vout(t) is an exponential whose time constant reflects RC/A:

• Given interval T, we can compute a minimum value of ε = |V0-VM| that will guarantee validity after T:

• Probability of metastability after T is computed by probability of a V0 yielding ε(T) …

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:

The Metastable State: a brief history

Ancient Metastability

• Metastability is the occurrence of a persistent invalid output… an unstable equilibria.

Folk Cures the “perpetual motion machine” of digital logic

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

There’s 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 can’t eliminate metastability, we will do the best we can to keep it from contaminating our designs

Modern Reconciliation: delay buys reliability

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

• The higher the clock rate, the more synchronizers should be considered.

Things we CAN’T build

• Bounded-time Asynchronous Arbiter:

• Bounded-time Synchronizer:

• Bounded-time Analog Comparator:

Some things we CAN build

• Unbounded-time Asynchronous Arbiter:

• Unbounded-time Analog Comparator:

• Bounded-time combinational logic:

Interesting Special Case Hacks

• Predictive periodic synchronization:

• Mesochronous communication:

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 can’t be expected to decide which fork to take in bounded time!”.

• Is the accident Ben’s fault?

Every-day Metastability-II

• GIVEN:

• 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

• Can one reliably obey....

• LAW #1: DON’T CROSS LINE while light is RED.
• GO = GREEN
• LAW #2: DON’T BE IN INTERSETION while light is RED.
• PLAUSIBLE STRATEGIES:
• Move at 55. At calculated distance D from light, sample color (using an unbounded-time synchronizer). GO ONLY WHEN stable GREEN.
• Stop 1 foot before intersection. On GREEN, gun it.

Summary

• As a system designer…

• Avoid the problem altogether, where possible
• Use single clock, obey dynamic discipline
• Avoid state. Combinational logic has no metastable states!
• Delay after sampling asynchronous inputs: a fundamental cost of synchronization