ACMs − the pool type
Dr and Dr Alex Bystrov
Question from last session
Copyright By PowCoder代写 加微信 powcoder
• Why do we seem to only care for the settling of the signal/data (potentially unbounded delay) and not for the value it settles to (non-deterministic 0 or 1)?
– Metastability may only happen if the data wire is changing value
(from 0 to 1 or from 1 to 0) when it is sampled by a clock edge
– Metastability settling to 0 or 1 is equivalent to sampling either just before this value change or after this value change
– Therefore this is not an error
• However, what about multi-bit words?
– Different bits could settle to different before/after, destroying data coherence
ACMs – pool, EEE8087 1
Reading materials
• Research papers related to these sessions
https://ieeexplore.ieee.org/document/1309114
https://ieeexplore.ieee.org/abstract/document/1134344
http://www.async.org.uk/comfort/publications/yak_xia.ps.gz
http://www.staff.ncl.ac.uk/i.g.clark/publications/ICACSD_2001.ps.gz
http://www.async.org.uk/comfort/publications/xia_async2001.pdf.gz
https://www.researchgate.net/publication/220444250_Automating_Sy nthesis_of_Asynchronous_Communication_Mechanisms
27/10/20 ACMs – pool, EEE8087 2
More than a single bit
• Large data items therefore must not be directly sampled through synchronizers
• Need a rethink
• Considering the FIFO example
– Readerandwriterareneverrequiredtobeonthe same clock
– Onlyobligedtowaitbythedatastate,i.e.bufferbeing empty or full
– Indirectsynchronization 27/10/20
ACMs – pool, EEE8087 3
• An ACM includes some memory sited between a writer and a reader processes and accessible by both
• An ACM must provide access mechanisms or access procedures, through which
– Writercanhavewritingaccesstothememoryand – Readercanhavereadingaccesstothememory
• Memory is the necessary resource
• Access mechanisms are the control protocols
27/10/20 ACMs – pool, EEE8087 4
• Writer and reader may access the ACM fully asynchronously
– Nosynchronizationbetweenthetwoprocesses – Nowaitingbyeitherside
– Overwriting
– Re-reading
• Conceptual single-space buffer
– Permanentlyholdingavaliddataitem
27/10/20 ACMs – pool, EEE8087 5
Pool-type ACMs
• Enough memory to support the following access protocols
• Permanent valid data item in the memory
• Writer overwrites the memory, replacing
(updating) the data item in the pool
• Reader may re-read the same data item it obtained from the previous round of reading access, if no newer item has since been updated
• Data coherence and data freshness required
27/10/20 ACMs – pool, EEE8087 6
Petri net model
• Always available to both writer and reader
• Reading and writing can happen in any order
Writer Reader
ACMs – pool, EEE8087
Only a single physical space in the memory
• This is intuitively not enough
– Ifthereisnosynchronizationbetweenthewriterand reader, simultaneous accesses cannot be ruled out
– Writerandreadercouldclashintimeonthesingle item data memory in the pool
– Datacoherenceanddatafreshnesscannotbe maintained
• What about two data spaces in the pool memory – enough to contain two data items?
27/10/20 ACMs – pool, EEE8087 8
Data slots
• A data slot is enough memory to hold a single item of data, designated to hold a single item of data, with an ACM’s memory element
• An ACM may include multiple physical slots for storing a single valid data item between writer and reader
• The multiple slots serve to provide writer and reader with enough space to avoid simultaneous clashes on the same physical memory location
• A FIFO (channel type) buffer typically includes multiple data slots, which are used for storing multiple data items
27/10/20 ACMs – pool, EEE8087 9
How about data coherence and freshness?
• Data coherence
– Completedataitemswrittenorread,notmodified
mid-transfer
– Noproblem
• Data freshness
ACMs – pool, EEE8087 10
Readerdoesnotobtainanydataitemthatisolder than the most recently fully written item in the ACM
Howcanthisbemaintainediftherearemultipledata slots, all claiming to store the same data item?
Imagine having two data slots
• If writer comes in and reader is not accessing, writer overwrites the slot containing the oldest data item
• If reader comes in and writer is not accessing, reader reads the slot containing the newest data item
– Mayre-read
• If writer comes in and reader is accessing – Readermustbereadingonlyoneoftheslots – Writeroverwritestheotherslot
• If reader comes in and writer is accessing
– Writermustbeoverwritingonlyoneoftheslots – Readerreadstheotherslot
27/10/20 ACMs – pool, EEE8087 11
In other words
• Writer and reader never clash on the same slot
– Datacoherenceisthereforemaintained
• Reader always goes to the newest completely written slot and when there is a choice, writer always overwrites the slot containing the oldest data item, leaving the other slot for the reader
– Datafreshnessisthereforemaintained
• Or is it? Try setting up a Petri net model for a two- slot pool and verify with reachability analysis (advanced task)
27/10/20 ACMs – pool, EEE8087 12
Thinking a bit more
• Writer comes in and settles on slot 0 to write
• During this writing access reader comes in, has to go to slot 1
• Writer finishes writing slot 0, prepares next data item, comes back, finds reader still not finished with slot 1, so writes slot 0 again
– Cannot wait
• Reader finishes reading slot 1, uses data item, comes back, finds writer still not finished with slot 0, so reads slot 1 again
– Cannot wait
• Repeat same events till end of time
27/10/20 ACMs – pool, EEE8087 13
Thinking a bit more
• Writer comes in and settles on slot 0 to write
• During this writing access reader comes in, has to go to slot 1
• Writer finishes writing slot 0, prepares next data item, comes back, finds reader still not finished with slot 1, so writes slot 0 again
– Cannot wait
• Reader finishes reading slot 1, uses data item, comes back, finds writer still not finished with slot 0, so reads slot 1 again
– Cannot wait
• Repeat same events till end of time
In this scenario, neither data coherence nor data freshness is violated, but there is no data communication!
Two slots are not
27/10/20 ACMs – pool, EEE8087
More than just data slots
Automating Synthesis of Asynchronous Communication Mechanis
• Reader needs to tell writer which slot it is accessing
, ˆnio ,
• Writer needs to tell reader which slot it is accessing, and
Department of Software School of Electrical, Electronic an
which slot contains the newest completely written data
Universitat Polite`cnica de Catalunya, Spain Computer Engineering
• These can be accomplished through control variables
http://www.lsi.upc.edu Univ. of Newcastle upon Tyne, UK
• Control variables are typically small-size and the data slots
are typically large-size
– Managing the access of large memory by passing information through small memory, i.e. single-bit latches
http://www.ncl.ac.uk/eece
Writer Reader data data
– This means that you no longer care about which value Asynchmroenotaustdaabtlaecsoimgnmaulnsiecattiloens mtoe,cyhoanuisjumst(mACaMkes)sure it has
have beensexttelensdivwelhyesntuydoieuduasedtahtaecvoanlunectors between independently timed processes in digital systems. In pre- vious work, systematic ACM synthesis methods have been
Figure 1. ACM with shared memory a
sibly control variables
27/10/20 ACMs – pool, EEE8087
proposed. In this paper, we advance this work by develop-
Control variables
Shared memory
ing algorithms and software tools which automate the major
Adding slots
• Reading, writing and latest slots
• Indicating we potentially can solve this with 3 slots?
• State graph of a 3-slot pool
– No simultaneous access of the
same slot by writer/reader r0
r0 w1 r0 w2 r0 w0 w0
– Reader always follows writer
– If writer is stuck on a slot, reader re-reads
– If reader is stuck on a slot, writer alternates in the other two slots
– Not possible to have both sides live and no communication (no livelock)
r1 r1 w2 r1 w0 r1 w1
r2 r2 w0 r2 w1 r2
ACMs – pool, EEE8087 16
Three-slots pool
• In theory, 3 data slots in the ACM memory are enough to ensure correct pool behaviour under most circumstances
• However, this requires 3-value (ternary) control variables, which do not have the correct metastability resistance
• Also, under extreme asynchrony, the 3-slot pool may fail the data requirements
• For instance, if you can fit an entire cycle of one side into the setting of a control variable of the other, data coherence may not be guaranteed
– Setting a control variable is the fastest action compared with data access (reading/writing) and the preparation and use of data
ACMs – pool, EEE8087 17
Four-slot pool
• Therefore, in practice, we use 4-slot pools
• Control variables are in vectors of binaries, of which any time only a single bit is modified (back to Boolean, cf. ternary for 3-slot)
• Metastability-resistance proven and
• All properties verified with reachability analysis
– Even if you fit an arbitrary number of cycles on one side into the setting of a binary control variable on the other you won’t be able to violate data coherence or freshness
• All failure modes are to do with metastability leak on some of the control variables
ACMs – pool, EEE8087 18
When a control variable is used, it has a half value
Can be mitigated by lengthening the time between the reading of a control variable and its use, sort of similar to multi-stage synchronizers
Four-slot pool algorithm ’s 4-slot pool:
ACM storage in a 2×2 matrix of slots, called d[x,y] with Boolean x, y
Boolean control variables n, l, and r Boolean two-element vectors v[x] and s[x] := is assignment
27/10/20 ACMs – pool, EEE8087 19
Other types of ACMs • Question
– CanyouthinkofothertypesofACMs,basedon allowing and not allowing overwriting and allowing and not allowing re-reading?
27/10/20 ACMs – pool, EEE8087 20
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com