ACMs − taxonomy and use cases
Dr Fei Xia and Dr Alex Bystrov
Question from last session
Copyright By PowCoder代写 加微信 powcoder
• Organizing ACMs into types according to whether overwriting and re-reading are permitted
• It’s possible to organize ACMs into four main types
No overwriting
Overwriting (asynchrony for writer)
No re-reading
FIFO buffers (channel type)
OW buffers (signal type)
Re-reading (asynchrony for reader)
RR buffers (message type)
OWRR buffers (pool type)
27/10/20 ACM taxonomy and use cases, EEE8087 1
Channel type ACM
• Example: bounded FIFO buffer
– Themostwidely-usedtypeofdeviceforasynchronous data communication
– Existsinalmostalldigitalsystems • Advantages
– Manydesignlibraries
– Sophisticatedandmaturedesignmethods
– Directlysuitablefortraditionaltasksincomputing
• Disadvantages
– Beingusedinmanycaseswhereitisnotsuitableor optimal
ACM taxonomy and use cases, EEE8087 2
Channel type ACM
• Decouples the clock domains to some degree – Goodforsystem-leveldesign,plugandplay
– Goodforreal-timesystems,tosomeextent
• Regulates the data flow
– Smoothenthedataflow
– Maketheexecutiononbothsidesmorepredictableand easier to organize
– Reducecommunicationlinkcongestion(betteruseof wires)
• Must use for transferring such data as computer programs, entertainment media, voice, etc.
27/10/20 ACM taxonomy and use cases, EEE8087 3
Pool type ACM
• Offers full asynchrony to both writer and reader
• Good for sensing, monitoring, and control systems
• Digital mimic of an analogue wire
https://www.tutorialspoint.com/digital_communication/digital_communication_sampling.htm
27/10/20 ACM taxonomy and use cases, EEE8087 4
Signal type ACM
• Full asynchrony for the writer
• Reader must wait if buffer is empty
– Doesnotre-usepreviousdataitems
– Goodforevent-drivenreader-side
– Whenthereisnonewdata,thereader-sidesubsystem
may enter an idle state
– Doesnotneedtoreceiveeveryitemofdataever generated, only requires data freshness
27/10/20 ACM taxonomy and use cases, EEE8087 5
Message type ACM
• Writer needs to know that every message has been acted on
– Previousdataitemmusthavebeenreadbeforea write can happen
– WritermayenteridlemodeifdatainACMhasnot been read
– Effectivelyanevent-drivenwriter
• Reader has full asynchrony, can re-read
– Nodatafreshnessrequirement,butaloseversionof data sequencing is maintained
27/10/20 ACM taxonomy and use cases, EEE8087 6
To compare
• All ACMs must maintain data coherence (the atomicity of each data item not to be broken)
• Signal and pool has data freshness
• Channel and message has data sequencing
• Channel: writer and reader may become event-driven
• Signal: reader event-driven
• Message: writer event-driven
• Pool: neither side event-driven
• Current reality: all of these are implemented by FIFO buffers at the bottom level – non-ideal
27/10/20 ACM taxonomy and use cases, EEE8087 7
More about signal type ACM
• How many data slots do we need?
• Obviously a 4-slot pool can be modified to realize a wonderfully safe signal but can we save on slots?
– Trya2-slotsolutionfirstmaybe?
• Starting from the functional specification
27/10/20 ACM taxonomy and use cases, EEE8087 8
More about signal type ACM
• How many data slots do we need?
• Obviously a 4-slot pool can be modified to realize a wonderfully safe signal but can we save on slots?
– Trya2-slotsolutionfirstmaybe?
• Starting from the functional specification
overwrite write
ACM taxonomy and use cases, EEE8087
2-slot signal
• From the functional specification, try and see if 2 slots are enough using a state graph
• Reader waiting states: s1 and s4
• Reader never repeats on the same slot
• Writer repeats on the same slot
• 2 slots potentially can work! s1
rd0 wr1 s3
wr0 s5 wr0
rd1 wr0 s0
27/10/20 ACM taxonomy and use cases, EEE8087
Would adding slots help?
• When writer is accessing slot 1 and reader has already read from slot 0, reader must wait
• However, writer might actually be overwriting slot 1, in which case the data being erased is more fresh (does not violate data freshness as the overwriting has not completed) than slot 0
• If there is a third slot, this would not keep the reader idle
27/10/20 ACM taxonomy and use cases, EEE8087 11
3-slot signal
• State graph can be obtained by modifying the 3-
slot pool state graph
– Poolisshownontheright-> – Notetheredre-readingarcs
0 w1 1 w2 w2
r0 w1 r0 w2 r0 w0
r1 r1 w2 r1 w0 r1 w1
r2 r2 w0 r2
ACM taxonomy and use cases, EEE8087
3-slot signal
• State graph can be obtained by modifying the 3-
slot pool state graph
– Justremovethere-readingarcs
– Notethatcomparedtothe2-slot
signal, this version allows more r0 reading accesses before it runs out of slots and needs to wait
– Example:non-waitingr0->r1->r2
– Morecommunicationwithoutfreshnessviolations
r2 w0 r2 w1 01
27/10/20 ACM taxonomy and use cases, EEE8087
More about message
• Similar to signal, a message can be implemented using 2 slots
• But again 3 slots allows more asynchrony and less writer waiting:
r1 r1 w2 r1 w0 r1 w1
r2 r2 w0 r2
27/10/20 ACM taxonomy and use cases, EEE8087
What about a 3-space FIFO?
• Try and derive the state graph specification for a 3- space FIFO, based on reading and writing actions
• Assume the data storage spaces in the channel ACM to be addressed in the same way as the slots in the pool, signal and message examples, i.e. spaces 0, 1, 2
• Can you list some fundamental differences in spite of similarities between the state graphs?
27/10/20 ACM taxonomy and use cases, EEE8087 15
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com