====== Analog-to-asynchronous elements ======

Analog-to-asynchronous (A2A) elements is a family of asynchronous arbitration primitives designed to increase the resilience and efficiency of the new generation of circuits and systems. This includes primitives for synchronisation and decision-making with an emphasis on interfacing analogue and digital worlds, sampling of non-persistent signals, cross-domain communication, and efficient handling of sensor events.

===== Synchronisation primitives =====

This section covers the primitives for the synchronisation of hazard-free signal transitions in asynchronous circuits with potentially hazardous signals coming from the environment.

==== WAIT and WAIT0 ====

The WAIT element controls an asynchronous handshake ''<color red>ctrl</color>\ /\ <color blue>san</color>'' by a non-persistent input ''<color red>sig</color>''. According to the WAIT STG below, ''<color red>sig</color>'' is unconstrained and is allowed to switch between ''0'' and ''1'' values with no regard to the output handshake -- this is captured by the loop with signal transitions ''<color red>sig+</color>'' and ''<color red>sig-</color>''. Initially ''<color red>ctrl</color>=<color blue>san</color>=0'' and WAIT is in the dormant mode, i.e. its input ''<color red>sig</color>'' is isolated from the output ''<color blue>san</color>''. By raising ''<color red>ctrl</color>'' input, the element can be switched into the waiting mode, where it stays until ''<color red>sig</color>'' becomes high and stays high for sufficiently long for internal event ''e'' to fire. The output ''<color blue>san+</color>'' is then produced and //persistently// held until WAIT is reset by ''<color red>ctrl-</color>''. Here and further on, the output ''<color blue>san</color>'' is the `sanitised' (persistent) version of the `dirty' (non-persistent) input ''<color red>sig</color>''. 

Note that an input spike (''<color red>sig+</color>'' followed by ''<color red>sig-</color>'') in the waiting mode can be too short for the WAIT element to register it, in which case the spike is ignored and WAIT remains in the waiting mode. The non-persistent behaviour and the associated metastability is fully contained within the element, guaranteeing a clean hazard-free output. This is achieved using the mutual-exclusion ''MUTEX'' element\ [(Kinniment_2008_book)]. Note that the output of the inverter in the implementation of WAIT is non-persistent, but this non-persistency will never propagate to ''<color blue>san</color>''.

<WRAP column third>
|{{ wait-box.circuit.svg?50%,nolink |}}|
|  WAIT block diagram\\ <wrap download>{{wait-box.circuit.work}}</wrap>  |
</WRAP>
<WRAP column third>
|{{ wait.stg.svg?35%,nolink |}}|
|  WAIT behaviour (conceptual)\\ <wrap download>{{wait.stg.work}}</wrap>  |
</WRAP>
<WRAP column third>
|{{ wait.circuit.svg?50%,nolink |}}|
|  WAIT implementation\\ <wrap download>{{wait.circuit.work}}</wrap>  |
</WRAP>

The WAIT STG above is not a valid STG specification and should only be viewed as a generator of possible traces: Note that this STG is not [[:help:verification#stg_properties|output-determinate]]\ [(Khomenko_2008_FI)], which is an important correctness criterion. That is, there are two different states reachable via the observable trace ''<color red>ctrl+ sig+ sig-</color>'', with one of them enabling ''<color blue>san+</color>'' and the other not, depending on whether unobservable transition ''e'' fired between ''<color red>sig+</color>'' and ''<color red>sig-</color>''. Hence, if viewed as a contract between the circuit and its environment, this STG is self-contradictory: It simultaneously requires the circuit to produce ''<color blue>san+</color>'' after trace ''<color red>ctrl+ sig+ sig-</color>'', and forbids it to do so. However, in this particular case the contradiction is resolved by making output ''<color blue>san+</color>'' //optional// after this trace, as shown in the state graph below. Note that the semantics of STGs is defined so that an enabled output must either fire or be disabled\ [(Khomenko_2008_FI)], i.e. outputs are always compulsory (i.e.\ there is no way to express an optional output in an STG). However, the issue is encapsulated inside WAIT -- the environment of WAIT sees ''<color blue>san+</color>'' as an input, and inputs are considered optional in STGs\ [(Khomenko_2008_FI)].

<WRAP center>
|  {{ sg-wait.svg?60%,nolink |}}  |
|  WAIT state graph  |
</WRAP>

The symmetric version of the element that waits for the input to become low is called WAIT0; its top-level block diagram, the STG specification and the implementation are as follows:

<WRAP group>

<WRAP column third>
|{{ wait0-box.circuit.svg?50%,nolink |}}|
|  WAIT0 block diagram\\ <wrap download>{{wait0-box.circuit.work}}</wrap>  |
</WRAP>
<WRAP column third>
|{{ wait0.stg.svg?35%,nolink |}}|
|  WAIT0 behaviour (conceptual)\\ <wrap download>{{wait0.stg.work}}</wrap>  |
</WRAP>
<WRAP column third>
|{{ wait0.circuit.svg?50%,nolink |}}|
|  WAIT0 implementation\\ <wrap download>{{wait0.circuit.work}}</wrap>  |
</WRAP>

</WRAP>

WAIT and WAIT0 are fundamental synchronisation primitives which are used for implementing other, more sophisticated elements presented below. 
==== RWAIT and RWAIT0 ====

RWAIT and RWAIT0 are modifications of the WAIT and WAIT0 elements, respectively, with a possibility to persistently cancel the waiting request. This is useful when the input is no longer expected to change or the change is no longer relevant for the asynchronous controller, and hence the output handshake needs to be released.

The additional input ''<color red>frc</color>'' can be used to force the reset of the output handshake in the waiting mode. The STG specifies that the output transition ''<color blue>san+</color>'' can be caused either by ''<color red>sig+</color>''\ (the top branch) or by ''<color red>frc+</color>''\ (the bottom branch). The implementation reflects the resulting //OR-causality//\ [(Yakovlev_1996_FMSD_OR)]: the inputs ''<color red>sig</color>'' and ''<color red>frc</color>'' are simply combined via a NOR gate, whose output is synchronised with the handshake ''<color blue>ctrl</color>\ /\ <color red>san</color>'' using the WAIT0 element.

<WRAP group>
<WRAP column half>
|  {{ rwait-box.circuit.svg?50%,nolink |}}  |
|  RWAIT block diagram\\ <wrap download>{{rwait-box.circuit.work}}</wrap>  |

|  {{ rwait.circuit.svg?50%,nolink |}}  |
|  RWAIT implementation\\ <wrap download>{{rwait.circuit.work}}</wrap>  |
</WRAP>
<WRAP column half>
|  {{ rwait.stg.svg?35%,nolink |}}  |
|  RWAIT specification\\ <wrap download>{{rwait.stg.work}}</wrap>  |
</WRAP>
</WRAP>

-----

<WRAP group>
<WRAP column half>
|  {{ rwait0-box.circuit.svg?50%,nolink |}}  |
|  RWAIT0 block diagram\\ <wrap download>{{rwait0-box.circuit.work}}</wrap>  |

|  {{ rwait0.circuit.svg?50%,nolink |}}  |
|  RWAIT0 implementation\\ <wrap download>{{rwait0.circuit.work}}</wrap>  |
</WRAP>
<WRAP column half>
|  {{ rwait0.stg.svg?35%,nolink |}}  |
|  RWAIT0 specification\\ <wrap download>{{rwait0.stg.work}}</wrap>  |
</WRAP>
</WRAP>

==== WAIT01 and WAIT10 ====

WAIT01 and WAIT10 elements wait for a rising or falling edge of the input signal, respectively. Note that this is subtly different from waiting for a high or low input value, e.g. a signal can be initially low, and to generate a falling edge event it must first go high. The WAIT01 specification tracks the input changes via two dummy transitions that are enabled in sequence when ''<color red>sig</color>=0'' and ''<color red>sig</color>=1'' hold. This can be implemented by connecting WAIT0 and WAIT in sequence.

<WRAP group>
<WRAP column third>
|  {{ wait01-box.circuit.svg?50%,nolink |}}  |
|  WAIT01 block diagram\\ <wrap download>{{wait01-box.circuit.work}}</wrap>  |
</WRAP>
<WRAP column third>
|  {{ wait01.stg.svg?35%,nolink |}}  |
|  WAIT01 specification\\ <wrap download>{{wait01.stg.work}}</wrap>  |
</WRAP>
<WRAP column third>
|  {{ wait01.circuit.svg?50%,nolink |}}  |
|  WAIT01 implementation\\ <wrap download>{{wait01.circuit.work}}</wrap>  |
</WRAP>
</WRAP>

-----

An element waiting for an arbitrary fixed pattern of alternating 0s and 1s, e.g. the symmetric WAIT10 element, can be implemented analogously.

<WRAP group>
<WRAP column third>
|  {{ wait10-box.circuit.svg?50%,nolink |}}  |
|  WAIT10 block diagram\\ <wrap download>{{wait10-box.circuit.work}}</wrap>  |
</WRAP>
<WRAP column third>
|  {{ wait10.stg.svg?35%,nolink |}}  |
|  WAIT10 specification\\ <wrap download>{{wait10.stg.work}}</wrap>  |
</WRAP>
<WRAP column third>
|  {{ wait10.circuit.svg?50%,nolink |}}  |
|  WAIT10 implementation\\ <wrap download>{{wait10.circuit.work}}</wrap>  |
</WRAP>
</WRAP>

==== WAIT2 ====

WAIT2 is another combination of WAIT and WAIT0: it uses a //2-phase// output handshake, waiting for high and low input values, one after the other. One can think of WAIT2 as a //2-phase// version of the WAIT element, or as a //C-element// whose input ''<color red>sig</color>'' is hardened against hazards.

The STG contains two loops: the inner ''<color red>sig</color>'' loop, which is unconstrained, and the outer handshake loop that synchronises the rising (''<color red>ctrl+</color>-><color blue>san+</color>'') and the falling (''<color red>ctrl-</color>-><color blue>san-</color>'') phases with conditions ''<color red>sig</color>=1'' and ''<color red>sig</color>=0'', respectively.

The implementation uses a toggle-like controller to steer the rising and falling edges of ''<color red>ctrl</color>'' to the inputs of the WAIT and WAIT0 elements, in sequence, and take care of their appropriate reset.

<WRAP group>
<WRAP column third>
|  {{ wait2-box.circuit.svg?50%,nolink |}}  |
|  WAIT2 block diagram\\ <wrap download>{{wait2-box.circuit.work}}</wrap>  |
</WRAP>
<WRAP column third>
|  {{ wait2.stg.svg?35%,nolink |}}  |
|  WAIT2 specification\\ <wrap download>{{wait2.stg.work}}</wrap>  |
</WRAP>
<WRAP column third>
|  {{ wait2.circuit.svg?50%,nolink |}}  |
|  WAIT2 implementation\\ <wrap download>{{wait2.circuit.work}}</wrap>  |
</WRAP>
</WRAP>

===== Decision-making primitives =====

This section presents a family of decision-making components that perform non-trivial event coordination and rely on the previously introduced synchronisation primitives.

==== WAITX ====

The WAITX element arbitrates between two non-persistent inputs ''{<color red>sig1</color>, <color red>sig2</color>}'', producing a clean asynchronous dual-rail handshake: depending on which of the two signals arrives first, exactly one of the grant signals ''{<color blue>g1</color>, <color blue>g2</color>}'' is issued. The place ''me'' with two consuming arcs represents the arbitration decision that needs to be made: if the inputs arrive very close to each other, both of the two dummy transitions can become enabled but only one of them can occur, since ''me'' can have at most one token. In the reset phase both branches are merged in the place ''mrg''.

<WRAP group>
<WRAP column half>
|  {{ waitx-box.circuit.svg?50%,nolink |}}  |
|  WAITX block diagram\\ <wrap download>{{waitx-box.circuit.work}}</wrap>  |
</WRAP>
<WRAP column half>
|  {{ waitx.stg.svg?35%,nolink |}}  |
|  WAITX specification\\ <wrap download>{{waitx.stg.work}}</wrap>  |
</WRAP>
</WRAP>

<WRAP group>
|  {{ waitx.circuit.svg?50%,nolink |}}  |
|  WAITX implementation\\ <wrap download>{{waitx.circuit.work}}</wrap>  |
</WRAP>


WAITX isolates the outputs both from the metastability associated with non-persistent inputs, as well as from the metastability associated with making the decision of which input signal arrives first. The implementation relies on RWAIT elements for synchronisation with non-persistent signals, and uses a MUTEX element to make the decision on their arrival order. See\ [(Khomenko_2017_ASYNC_WAITX)] for further implementation details and for a generalisation to more than 2 input signals.


==== WAITX2 ====

WAITX2 behaves as WAITX in the rising phase and as WAIT0 in the falling phase, i.e. it does not release the output asynchronous handshake until the winning input signal goes low. It uses a 2-phase output handshake similarly to WAIT2, and the specification, is therefore a combination of the STGs for WAITX and WAIT2.

The implementation comprises WAITX and two WAIT0 elements controlled by toggle-like asynchronous logic, which activates the right WAIT0 element in the reset phase. The synthesis and technology mapping of the control was performed using conventional asynchronous design approaches automated in Workcraft.

<WRAP group>
<WRAP column half>
<WRAP column half>
|  {{ waitx2-box.circuit.svg?50%,nolink |}} |
|  WAITX2 block diagram\\ <wrap download>{{waitx2-box.circuit.work}}</wrap>  |
</WRAP>
<WRAP column half>
| {{ waitx2.stg.svg?35%,nolink |}} |
|  WAITX2 specification\\ <wrap download>{{waitx2.stg.work}}</wrap>  |
</WRAP>
</WRAP>
<WRAP column half>
| {{ waitx2.circuit.svg?50%,nolink |}}  |
|  WAITX2 implementation\\ <wrap download>{{waitx2.circuit.work}}</wrap>  |
</WRAP>
</WRAP>
==== SAMPLE ====

The purpose of the SAMPLE element is to check whether the voltage on the input ''<color red>sig</color>'' is above the threshold. The specification is similar to that of WAITX but the two dummy transitions are controlled by conditions corresponding to the state of the same input ''<color red>sig</color>''. The implementation is based on WAITX that decides which of the two inputs, ''<color red>sig</color>'' or its inverted version, becomes high first. Note that both inputs of WAITX may be high at the same time, e.g. during a transition of ''<color red>sig</color>'', in which case SAMPLE is allowed to make an arbitrary decision. However, if the input signal is stable, no metastability resolution is required and SAMPLE can therefore quickly produce the correct output.

<WRAP group>
<WRAP column third>
|  {{ sample-box.circuit.svg?50%,nolink |}}  |
|  SAMPLE block diagram\\ <wrap download>{{sample-box.circuit.work}}</wrap>  |
</WRAP>
<WRAP column third>
|  {{ sample.stg.svg?35%,nolink |}}  |
|  SAMPLE specification\\ <wrap download>{{sample.stg.work}}</wrap>  |
</WRAP>
<WRAP column third>
|  {{ sample.circuit.svg?50%,nolink |}}  |
|  SAMPLE specification\\ <wrap download>{{sample.circuit.work}}</wrap>  |
</WRAP>
</WRAP>

==== Opportunistic Merge ====

The opportunistic merge OM element merges two request-acknowledgement channels ''{<color red>r1</color>\ /\ <color blue>a1</color>,\ <color red>r2</color>\ /\ <color blue>a2</color>}'' into one ''<color blue>r</color>\ /\ <color red>a</color>'' and can opportunistically bundle requests from different input channels if they arrive sufficiently close to each other.

The conceptual state graphs clarifies the difference between the standard merge element\ [(Greenstreet_1999_ASYNC_Merge)] and OM. The conceptual state graph of the merge element is shown on the left. Note that the bottom state of the graph is not persistent: outputs a1 and a2 disable each other, hence this is a decision-making element. The state graph for OM, shown on the right, has an additional //opportunistic bundle// transition labelled by ''{<color blue>a1</color>,\ <color blue>a2</color>}'' that sends acknowledgements to both input channels.

<WRAP group>
<WRAP column third>
|  {{ om-box.circuit.svg?50%,nolink |}}  |
|  OM block diagram\\ <wrap download>{{om-box.circuit.work}}</wrap>  |
</WRAP>
<WRAP column third>
|  {{ merge.sg.svg?50%,nolink |}}  |
|  MERGE specification (conceptual)  |
</WRAP>
<WRAP column third>
|  {{ om.sg.svg?50%,nolink |}}  |
|  OM specification (conceptual)  |
</WRAP>
</WRAP>
<WRAP center>
|{{ om.circuit.svg?50%,nolink |}}|
|  OM implementation\\ <wrap download>{{om.circuit.work}}</wrap>  |
</WRAP>

The intended application of OM is to handle concurrent (and potentially correlated) requests from several clients to a kind of service that benefits all the clients simultaneously. Examples include triggering an alarm by (any of) several sensors, re-charging of a shared DRAM, and various kinds of power management. All these use cases benefit from serving multiple requests in bundles. The STG specification of OM, as well as further implementation details can be found in\ [(Mokhov_2015_ASYNC_OM)].

The input channels of OM are assumed to be hazard-free, but one can use the synchronisation primitives to generate clean hazard-free handshakes from hazardous input signals, e.g. produced by analogue sensors.


[(Kinniment_2008_book>D. Kinniment: “Synchronization and Arbitration in Digital Systems”, Wiley Publishing, 2008.)]

[(Khomenko_2008_FI>V. Khomenko, M. Schaefer and W. Vogler: “Output-Determinacy and Asynchronous Circuit Synthesis”, IOS Press, Fundamenta Informaticae 88(4) (2008) 541-579. Special Issue on Best Papers from ACSD'2007.)]

[(Yakovlev_1996_FMSD_OR>A. Yakovlev, M. Kishinevsky, A. Kondratyev, L. Lavagno, M. Pietkiewicz-Koutny: “On the models for asynchronous circuit behaviour with OR causality”, Formal Methods in System Design, vol. 9(3), pp. 189–233, 1996.)]

[(Khomenko_2017_ASYNC_WAITX>V. Khomenko, D. Sokolov, A. Mokhov, A. Yakovlev: “WAITX: an arbiter for non-persistent signals”, Proc. Asynchronous Circuits and Systems (ASYNC), 2017.)]

[(Greenstreet_1999_ASYNC_Merge>M. Greenstreet: "Real-time merging", Proc. Asynchronous Circuits and Systems (ASYNC), pp. 186–198, 1999.)]

[(Mokhov_2015_ASYNC_OM>A. Mokhov, V. Khomenko, D. Sokolov, A. Yakovlev: “Opportunistic merge element”, Proc. Asynchronous Circuits and Systems (ASYNC), pp. 116–123, 2015.)]