ACMs − preliminaries
Dr Fei Xia and Dr Alex Bystrov
Prerequisites
Copyright By PowCoder代写 加微信 powcoder
• Petri nets
• State-transition diagrams – Reachabilitygraphs
• Basic understanding of flip-flops, latches, registers and their operations
• Basic understanding of how clock signals are used in computing hardware
26/10/20 ACM preliminaries, EEE8087 1
ACM resources
• on “atomic register” and on “asynchronous communication mechanisms”
– Google,IEEExplore,etc.
• Research papers on this subject by the μSystems
Research Group, Newcastle University
– BrowseourpublicationsintheComfortandCoherent projects from
http://async.org.uk/comfort/publications.html and http://async.org.uk/coherent/coherent_publications.html
26/10/20 ACM preliminaries, EEE8087 2
Asynchronous Data Communications
• A complex system may include a number of different digital sub-systems, e.g. computers
• A major problem is how to transfer data from one sub-system to another
ACM preliminaries, EEE8087 3
Itboilsdowntodatacommunicationsbetweentwo processes, each running on a different digital computation device, e.g. computer
Weviewtheseprocessesasa‘writer’anda‘reader’ and the goal is to transfer data from the writer to the reader correctly and efficiently
Asynchronous Data Communications • Schematic diagram of the data transfer
Computer 1 Writer
Computer 2 Reader
26/10/20 ACM preliminaries, EEE8087 4
Fundamental Problem
• Synchronization
– Differentcomputerstendtoberunondifferentclocks
– Butatthebasiclevel,abitofdataissent/received through the smallest memory, i.e. flip-flops or latches
Computer 2
Computer 1
26/10/20 ACM preliminaries, EEE8087
Fundamental Problem
• Synchronization
– Thelatchesinvolvedneedtobeonthesameclock
– This‘sameclock’needstobetheclockofComputer1 or Computer 2 but these two are not the same!
Computer 2
Computer 1
26/10/20 ACM preliminaries, EEE8087
Synchronization for data transfer • Synchronizers
– Devicesthatmakethetwosidesofthedatatransfer (writer and reader) run on effectively the same clock
– Losingdatacorrectness
• Problems
ACM preliminaries, EEE8087 7
Metastabilitymeansthatfor100%correctnessyou need waiting of unbounded time
Waitingonlyforboundedtimeyouhavenon-zero probabilities of data errors
• Waiting, if unbounded, violates real-time requirements
• Insert a buffer between reader and writer so either side can move on without waiting for the other side?
• Let’s look at the Petri net model of an n-space buffer for asynchronous data communication
26/10/20 ACM preliminaries, EEE8087 8
Typical n-space buffers
• First in first out (FIFO)
– Thisisthemostcommonbufferbetweentwo different digital devices
• Last in first out (LIFO)
– Alsoknownasastack,thisislesscommonbetween
two different digital devices
• Random access memory (RAM)
– Generallyknownasabag,ifaccessistrulyrandom there is very little real use for it
26/10/20 ACM preliminaries, EEE8087 9
Petri net model of a FIFO buffer • FIFO with n spaces between writer and reader
Writer Reader
26/10/20 ACM preliminaries, EEE8087 10
Each space may be empty (E) or full (F)
• The entire buffer may be empty (reader waits) or full (writer waits)
Writer Reader
26/10/20 ACM preliminaries, EEE8087 11
• Asynchronous communication mechanism between reader and writer
Writer Reader
26/10/20 ACM preliminaries, EEE8087 12
• For fully asynchronous data communication
• No waiting by either writer or reader, single-space buffer
• Wide usage in real-time systems
– Example: public clocks
– ‘Writer’ is the clock’s internal mechanism
– ‘Readers’ are people looking at the clock
– If nobody looks at the clock during an update cycle, it updates anyway – the ‘lost’ value is not used
– If people look at the clock during an update cycle, the ‘data’ stays the same until the next update
– If someone reads the clock multiple times during an update cycle, they read the same value – the same value is re-used
26/10/20 ACM preliminaries, EEE8087
Full reader/writer asynchrony
• Known by a number of different names, but the same thing conceptually
– : Atomic register https://lamport.azurewebsites.net/pubs/interprocess.ps
– : Pool (four-slot ACM) https://ieeexplore.ieee.org/document/41349
• Writer updates value (overwriting)
• Reader does not modify value (re-reading)
• Buffer always contains one valid data item
– Initialized with valid data value before a run
• Synchronized to the writer when writing, to the reader when reading
– But how to accommodate simultaneous reading/writing?
26/10/20 ACM preliminaries, EEE8087 14
ACM preliminaries recap • NoACM
– Fullysynchronizeddatatransfer–readerandwritermust be on the same clock during data transfer and reading and writing happens on the same data at the same time
• Traditional buffers (FIFO etc.)
– Someasynchronyallowedfordatatransfer–readerand writer usually do not access the same data item at the same time
– Waitingcannotbefullyavoided
• Fully asynchronous ACM
– Nowaitingbyeitherside,dataalwaysvalid
26/10/20 ACM preliminaries, EEE8087 15
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com