MIT OpenCourseWarehttp://ocw.mit.edu For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms. 6.004 Computation Structures Spring 2009 L07 -Synchronization 1 6.004 – Spring 20092/26/09Synchronization, Metastability and Arbitration Due tonight: Lab #2 Lab #1 checkoff meeting "If you can't be just, be arbitrary" -Wm Burroughs, Naked Lunch -US Supreme Court 12/00 Did you vote for Bush or Gore? Didn’t have enough time to decide. Well, which hole did you punch? Both, but not very hard... modified 2/23/09 09:30 L07 -Synchronization 2 6.004 – Spring 20092/26/09The Importance of being Discrete Digital Values: Problem: Distinguishing voltages representing “1” from “0” Solution:Forbidden Zone: avoid using similar voltages for “1” and “0” Digital Time: Problem: “Which transition happened first?” questions Solution: Dynamic Discipline: avoid asking such questions in close races VOLVILVIHVOHVOUT VINVOLVILVIHVOHtStHClkQDtCDtPDWe avoid possible errors by disciplines that avoid asking the tough questions – using a forbidden zone in both voltage and time dimensions: L07 -Synchronization 3 6.004 – Spring 20092/26/09If we follow these simple rules… Can we guarantee that our system will always work? With careful design we can make sure that the dynamic discipline is obeyed everywhere*... D Q D Q OutInCombinationallogicD Q OutCombinationallogicD Q InClkCombinationallogicD Q CombinationallogicD Q CombinationallogicD Q OutCombinationallogic* well, almost everywhere... L07 -Synchronization 4 6.004 – Spring 20092/26/09Which edge Came FIRST? The world doesn’t run on our clock! What if each button input is an asynchronous 0/1 level? Lock B1UB00101To 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:01(Unsynchronized) U(t)(Synchronized) S(t)Clock Synchronizer Valid except for brief periods following active clock edges But what About the DynamicDiscipline? L07 -Synchronization 5 6.004 – Spring 20092/26/09The Asynchronous Arbiter: a classic problem ArbiterBCSB:C:attBattCB:C:S:tDtD>tE>tEtDArbiter specifications: •finite tD (decision time) •finite tE (allowable error) •value of S at time tC+tD:1if tB < tC – tE0if tB > tC + tE0, 1otherwise CASE 1 CASE 2 CASE 3 UNSOLVABLE For NO finite value of tE and tD is this spec realizable, even with reliable components! L07 -Synchronization 6 6.004 – Spring 20092/26/09Violating the Forbidden Zone The image cannot be displayed. Your computer may not have enough memory to open the image, or the image may have been corrupted. Restart your computer, and then open the file again. If the red x still appears, you may have to delete the image and then insert it again.tB-tCArbiter Output1o(tB=tC)BEarlierCEarlierArbiterBCSB:C:attBattCIssue: Mapping the continuous variable (tB – tC)onto the discrete variable S in bounded time.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. L07 -Synchronization 7 6.004 – Spring 20092/26/09Unsolvable? thatcan’t be true... Lets just use a D Flip Flop: DQB:C:attBattCDECISION TIME is TPD of flop. ALLOWABLE ERROR is max(tSETUP, tHOLD)Our logic: TPD after TC, we’ll have Q=0 iff tB + tSETUP < tCQ=1 iff tC+ tHOLD < tBQ=0 or 1 otherwise. 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 when B and C change at about the same time... GDQGDQBCmaster slave L07 -Synchronization 8 6.004 – Spring 20092/26/09The Mysterious Metastable State VinVoutVTC of“closed” latchVTC of feedback path (Vin=Vout)Latched in a ‘0’ stateLatched in a ‘1’ stateLatched in an undefined stateY01QVoutVinRecall that the latch output is the solution to two simultaneous constraints: 1. The VTC of path thru MUX; and 2. Vin = VoutIn addition to our expected stable solutions, we find an unstable equilibrium in the forbidden zone called the “Metastable State” L07 -Synchronization 9 6.004 – Spring 20092/26/09Metastable 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 settleout.5.EVERY bistable system exhibits at least one metastable state! EVERY bistable system? Yep, every last one. Coin flip?? Could land on edge. Horse race?? Photo finish. Presidential Election?? (Where’s this twit been hiding???) L07 -Synchronization 10 6.004 – Spring 20092/26/09Observed Behavior: typical metastable symptoms Following a clock edge on an asynchronous input: We may see exponentially-distributed metastable intervals: Or periods of high-frequency oscillation (if the feedback path is long): CLKDQQL07 -Synchronization 11 6.004 – Spring 20092/26/09Mechanical Metastability If we launch a ball up a hill we expect one of 3 possible outcomes:a) Goes over b) Rolls back c) Stalls at the apex That last outcome is not stable.-a gust of wind -Brownian motion -it doesn’t take muchState AState BMetastable StateState AState BL07 -Synchronization 12 6.004 – Spring 20092/26/09How do balls relate to digital logic?Our hill is analogous to the derivativeof the VTC (Voltage Transfer Curve)… at the metastable point, the derivative (slope) is ZERO.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 – assuming continuous models of physics – we can’t eliminate the slope=0 point!VinVoutinoutVVL07 -Synchronization 13 6.004 – Spring 20092/26/09The 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). L07 -Synchronization 14 6.004 – Spring 20092/26/09Sketch of analysis… I. 01(Synchronized) S(t)Clock Synchronizer Assume asynchronous 0->1 at TA, clock period CP: Whats the FF output voltage, V0, immediately after TA?AC< tS+tHCPVM1. Whats the probability that the voltage, V0, immediately after TA is within of VM?)(2)(][0LHHSMVVCPttVVP+V0tA-tCPotential trouble comes when V0 is near the metastable point, VM…L07 -Synchronization 15 6.004 – Spring 20092/26/09Sketch of analysis… II. We can model our combinational cycle as an amplifier with gain A and saturation at VH, VLA01VoutVin0RCVHVLVout Vin Slope = A 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: Vout(t)-VMet(A-1)/RC et/(T) (VH – VM) e -T/4. Probability of metastability after T is computed by probability of a V0yielding(T) … PM(T) P[|V0-VM| < (T)] K e -T/L07 -Synchronization 16 6.004 – Spring 20092/26/09Failure 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 DelayP(Metastable)between failures 31 ns3x10-161 year 33.2 ns3x10-1710 years 100 ns10-451030 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! L07 -Synchronization 17 6.004 – Spring 20092/26/09The Metastable State: a brief history Antiquity: Early recognition Denial: Early 70s Folk Cures: 70s-80s Reconciliation: 80s-90s Buriden’s Ass, and other fables… Widespread disbelief. Early analyses documenting inevitability of problem rejected by skeptical journal editors. Popular pastime: Concoct a “Cure” for the problem of “synchronization failure”. Commercial synchronizer products. Acceptance of the reality: synchronization takes time. Interesting special case solutions. L07 -Synchronization 18 6.004 – Spring 20092/26/09Ancient Metastability Metastability is the occurrence of a persistent invalid output… an unstable equilibria. The idea of Metastability is not new:The Paradox of Buridan’s 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.L07 -Synchronization 19 6.004 – Spring 20092/26/09Folk Cures the “perpetual motion machine” of digital logic FF"FIXER"delayAsync Input"Clean" OutputBad Idea # 1: Detect metastable state & Fix TheimagecannotTheimagecannotTheimagecannotvalid "0"valid "1"Bad Idea #2: Define the problem away by making metastable point a valid output Bug: detecting metastability is itself subject to metastable states, i.e., the “fixer” will fail to resolve the problem in bounded time. 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. L07 -Synchronization 20 6.004 – Spring 20092/26/09There’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 designsL07 -Synchronization 21 6.004 – Spring 20092/26/09Modern Reconciliation: delay buys reliability D Q D Q OutCombinationallogicD Q InClkA metastable state here will probably resolve itself to a valid level before it gets into my circuit.And one here will almost certainly get resolved. D Q D Q OutCombinationallogicD Q D Q InClkSynchronizers, 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. SETTLING TIME Cures Metastability! L07 -Synchronization 22 6.004 – Spring 20092/26/09Things we CAN’T build 1. Bounded-time Asynchronous Arbiter: S valid after tpd following (either) edge ArbiterBCSS=0 iff B edge first, 1 iff C edge first, 1 or 0 if nearly coincident DQAsynchronous InputOutput = D at active clock edge, either 1 or 0 iff D invalid near clock edge Q valid after tpd following active clock edge 2. Bounded-time Synchronizer: > 3.14159 ? Continuous Variable 3. Bounded-time Analog Comparator: 0 or 1, finite tpd L07 -Synchronization 23 6.004 – Spring 20092/26/09Some things we CAN build 1. Unbounded-time Asynchronous Arbiter: S valid when Done=1; unbounded time. ArbiterBCSS=0 iff B edge first, 1 iff C edge first, 1 or 0 if nearly coincident Done 2. Unbounded-time Analog Comparator: > 3.14159 ? Continuous Variable 0 or 1Done 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. L07 -Synchronization 24 6.004 – Spring 20092/26/09Interesting Special Case Hacks For systems with unsynchronized 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 slowly-varying phase relationship between the clocks, and selects the clean output via a lenient MUX. CLK2Data1 delayData2 CLK1CLK2Mesochronous communication: Constraints on clock timing – periodicity, etc – can often be used to “hide” time overhead associated with synchronization. Exploits fact that, given 2 periodic clocks, “close calls” are predictable.Predicts, and solves in advance, arbitration problems (thus eliminating cost of delay) Predictive periodic synchronization: CLK1Data1 CLK2Data2 L07 -Synchronization 25 6.004 – Spring 20092/26/09Every-day Metastability -I BitBucketCafeThe image cannot be displayed.Yourcomputermay not haveenoughmemoryto open the image, 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? “Yes; he should have stopped until his decision was made.” Judge R. B. Trator, MIT ‘86 L07 -Synchronization 26 6.004 – Spring 20092/26/09Every-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.... 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 positive GREEN transition, gun it. •LAW #1: DON’T CROSS LINE while light is RED. GO = GREEN •LAW #2: DON’T BE IN INTERSECTION while light is RED. L07 -Synchronization 27 6.004 – Spring 20092/26/09Summary 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 synchronizationThe most difficult decisions are those that matter the least. Cartoon of a car stopped at traffic light.Image by MIT OpenCourseWare.