ACMs − a single bit
Dr Fei Xia and Dr Alex Bystrov
• Writer and reader may access the ACM fully asynchronously
Copyright By PowCoder代写 加微信 powcoder
– Nosynchronizationbetweenthetwoprocesses – Nowaitingbyeitherside
– Overwriting
– Re-reading
• Conceptual single-space buffer
– Permanentlyholdingavaliddataitem
26/10/20 ACMs, EEE8087 1
ACM data requirements • Data coherence
ACMs, EEE8087 2
Completedataitemswrittenorread,notmodified mid-transfer
Readerdoesnotobtainanyreassembleddataitem that contains parts from different items provided by writer (e.g. you do not get the name of one person and age of another in the same record if ids are being transferred)
ACM data requirements
• Data freshness
– Specifictothepool
– Readerdoesnotobtainanydataitemthatisolder than the most recently fully written item in the ACM
– Notrelevantformulti-stagetraditionalbufferssuchas FIFO
• Data sequencing
– Reader’sinputdataitemsfollowthesameorderas
they are written by the writer (for pool and FIFO)
26/10/20 ACMs, EEE8087 3
• The data communication is assumed to consist of the transfer of a stream of multiple data items
• A data item is a data record/packet/file of the same type/size for each data communication instance
ACMs, EEE8087 4
Thesizeinparticularisnotdeterminedwithouta concrete mechanism and use case
Couldbequitelarge–generallyassumednotpossibleto transfer one item during a single reader or writer clock cycle (otherwise the problem is trivial and uninteresting)
Special case: data item = 1 bit
• To transfer a single bit, a simple method is to copy it from one register to another
– WriterrunsonComputer1andreaderrunson computer 2
Computer 2
Computer 1
ACMs, EEE8087
Flip-flop review
• For a level-triggered flip-flop, when clock=1 (or 0, depending on the design), Q is set to D
• Otherwise, Q keeps its value no matter what D does
• For an edge-triggered flip-flop, Q is only set to D during an active edge of the clock (again the actual active edge could be rising or falling, depending on the design)
26/10/20 ACMs, EEE8087 6
Operations of the FFs
• Writer puts data on wire by setting Q of FF1 using Clock1, reader samples the data on wire using Clock2
Computer 1
Computer 2
26/10/20 ACMs, EEE8087
Operations of the FFs
• Assuming rising edge protocol, on the rising edge of Clock2 the value of QFF1 is copied to DFF2
Computer 1
Computer 2
26/10/20 ACMs, EEE8087
However …
• What if on the rising edge of Clock2 the value of QFF1 is being changed according to Clock1?
Computer 1
Computer 2
26/10/20 ACMs, EEE8087
Clocked D-latch requirements
• D-latch is an example, same is true for all types of clocked FFs and latches
– WhenyouwanttosamplethedataontheDinput, relative to the clock edge, that data needs to satisfy “setup and hold” conditions
– Otherwiseyouarenotguaranteedcorrectdigital behaviour
– Inotherwords,whenyousamplethedataitmustnotbe in a state of change
– Thisisbecauseyourreadinglatchisnotapuredigital device, but an analogue device approximating a digital device
ACMs, EEE8087 10
Switching element review
• Example: MOSFET
– AMOSFETcannotswitchbetween0and1in0time
– Anyswitchthatcanswitchbetween0and1encoded by two discrete values of any physical quantity (voltage, current, displacement, etc.) cannot implement 0-time switching unless it can supply power = ∞, which does not exist
– SwitchinginaMOSFETinvolvesthechargingor discharging of a non-0 capacitance through a non-0 resistance
Saumitra R Mehrotra &
ACMs, EEE8087 11
Sampling a wire using a clock edge
• This is an analogue process
– Theclockedgeisnotverticalintime
– Clocksignalrising/fallingtakestime≠0
– The change of signal QFF1 on the writer side is not vertical in time
– Thischangetakestime≠0
• When these two events are very close or overlap in time
– The sampled DFF2 signal on the reader side is non- deterministic
ACMs, EEE8087 12
Metastability in synchronizers • Picture from Prof Delong Shang, IMECAS
– Whensamplingclockandsignal change clash in time, uncertain DFF2 may cause QFF2 to take non-0 and non-1 values for unbounded time
1.5 1.0 0.5 0.0
1.4 1.2 1.0 0.8 0.6 0.4 0.2 0.0
1.5 1.0 0.5 0.0
5.2 5.4 5.6
– FF2latchesthishalfwayvalueso that Q =Qbar =0.5 (for instance)
– Itissortofstablebutnotreally,hence
5.2 5.4 5.6
the word metastability
– QFF2eventuallysettlestooneofthe binary values non-deterministically
26/10/20 ACMs, EEE8087
5.2 5.4 5.6
voltage (V) voltage (V) voltage (V)
Mechanical system analogy
• The sampling circuit may be regarded as a wedge/hill entrusted with determining if a ball is falling down the left or right hand half of the space
– Iftheballisonthelefthandside,itslidesdowntheleft hand side of the hill to a valley on the left, indicating 0
– Iftheballisontherighthandside,itslidesdownthe right hand side of the hill to a valley on the right, indicating 1
– Iftheballisdeadcentre,however,itmaybalanceontop of the wedge shape for unbounded time, as any wedge, no matter how sharp, is flat/level on top, just as the bottom of the ball it is flat/level
26/10/20 ACMs, EEE8087 14
Non-determinism in decision making
• People used to think decision making was deterministic
– Zhuangzi(C4,BCE)reasonedthathecoulddefinitely make a choice between fish and bear’s paw by free will
– Aristotle(C4,BCE)ridiculedtheideathatifamanis equally thirsty and hungry, and given food and drink, he could die of hunger/thirst because of indecision
– Al-Gazhali(C11-12,CE)thoughtthatamanpossessesan inherent quality the nature of which is to differentiate things, therefore two seemingly the same dates with equal desirability will not impede the choosing of one
26/10/20 ACMs, EEE8087 15
Non-determinism in decision making • , c. 1340
– Shouldtwocoursesbejudgedequal,thenthewill cannot break the deadlock, all it can do is to suspend judgment until the circumstances change, and the right course of action is clear.
– The(in)famous“Buridan’sass”paradox
– PicturecreditedtoNewYorkHerold,c.1900
26/10/20 ACMs, EEE8087 16
What about the maths?
• Metastability has exponential decay
– Inotherwords,thelongerthetime,themorelikely any metastability has settled, but the settling probability increase is highest in the beginning (near time = 0) but reduces towards time = ∞
• Mean time between failure of a synchronizer because of metastability
Tp propagationdelayof FF2
FD data frequency (FF1) FC clock frequency (FF2) tr resolution time (sync period)
τ time related to setup and hold (FF2)
ACMs, EEE8087
In other words
• MTBF is greater (better) if
– FF2 is faster (sharper wedge/hill in the mechanical analogy)
– Both data change and sampling clocks are slow
– Resolution time requirement is relaxed (you can wait for a longer time before synchronization must be completed – usually realized with multiple layers of FFs on the reader side)
• In other words, you need to use fast semiconductor slowly
– When you read claims that someone’s metastability MTBF is longer than your lifetime or even the lifetime of the universe, be very suspicious
ACMs, EEE8087 18
In other words
• Asynchronous data transfer does not always work even for a single bit
– Howcanwethenorganizelarge-sizedataitemstobe passed from writer to reader?
• Turns out this is overly pessimisticJ • Question:
– Whydoweseemtoonlycareforthesettlingofthe signal/data (potentially unbounded delay) and not for the value it settles to (non-deterministic 0 or 1)?
26/10/20 ACMs, EEE8087 19
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com