Chapter 7
Modular Asynchronous Circuits
7.1 About Asynchronous Circuits
Asynchronous circuits are sequential circuits which operate without any global
clock control. In an asynchronous circuit each component starts its computation
as soon as all the required data are available and transmits its outputs to the
next components, as soon as its computation is completed. In synchronous
(clock-controlled) circuits, the transfer of data is delayed until the
occurrence of the next clock signal. Thus, an asynchronous circuit may, in
principle, be faster than its synchronous counterpart. Furthermore, the
asynchronous approach assists in reducing the power consumption. Thus, they are
particularly of interest in connection with portable devices and airborne
systems.
However, it turns out that synchronous
circuits are easier to design than asynchronous ones. But in recent years there
has been a great surge of interest in asynchronous designs, in view of the
above advantages. Both the practical as well as the theoretical aspects of such
designs were extensively investigated.
7.2
Modular
Asynchronous Circuits
In this text we are particularly
interested in modular asynchronous circuits, which are designed as a
composition of basic modules. Such modules are more complex than simple
gates; their correct behaviour is to be assured by
suitable circuit design, rather than by logic design. A
special class of such circuits are delay-insensitive circuits, the
correct behaviour of which does not depend on delays
due their components or their interconnections. They are easier to design and
to verify than arbitrary asynchronous circuits.
7.3 Dynamic (Edge-based) vs. Level-based Behaviour
The conventional approach to the
behavioral description of digital circuits is based on observing the values of
inputs and outputs at suitably chosen, discrete points in time. In a
synchronous circuit, for example, the frequency of these observations is in
accordance with the clock rate.
In contrast to this static or level-based
approach to behavioral descriptions, the dynamic approach applied in
this Course, is based on observing external events of the circuit, i.e.
changes of the value of an input or output. A dynamic description of the
behavior of a digital system consists of listing all admissible sequences of
external events, subject to restrictions imposed on the environment.
We are interested in the order in time,
in which the events occur, and not in the actual time intervals involved. The
dynamic viewpoint is particularly applicable, and is indeed widely used, with
respect to asynchronous circuits.
This approach to the behavior of
asynchronous circuits is quite similar to the way, processes/agents are
described, e.g., in CSP, CCS, and LOTOS.
7.4 An Illustrative Example
As illustrative example
of the dynamic approach, we consider a two-input XOR-gate.
Here we use capital letters to denote Boolean
variables; the corresponding lower-case letters will denote level-changes. We
denote the inputs by A and B, and the output by Z. This
gate is stable iff (A#B)=Z
and otherwise unstable. The logical XOR operator # is defined by F#T=T#F=T
and F#F=T#T=F.
We
assume that the environment of this gate is restricted in the following way.
(1) an input may change only if the gate is stable.
(2) only one input may change at any time.
About (1): assume A=B=Z=T; thus the gate
is unstable and Z has the tendency to change. Assume that this output change
from T to F occurs fast enough, before a change of input A (from T to F)
becomes effective. Since (F#T)=T, this input change
will restore the output to T. Thus a short F-pulse may occur. In asynchronous
circuits such pulses may interfere with the correct operation of the circuit,
and should be prevented.
About (2): you will easily verify that in
the case when both inputs are changed together in some stable state, one input
change may become effective fast, and the other
slowly. This may again lead to a short detrimental output pulse.
The admissible state
transitions may be summarized as follows:
(1) If the state is
stable, each of the input changes 'a' and 'b' are applicable; the resulting
state will be unstable.
(2) If the state is
unstable, only an output change 'z' may occur; the resulting state is stable.
Using Blot we may represent the above XOR
gate as follows:
XOR = a;z;XOR [ ] b;z;XOR
In this text we will use the graphical symbol
To represent the
XOR-gate. Viewed as asynchronous
module, this gate is also referred to as 2-MERGE or simple as MERGE.
I assume you have no problem in
converting the above Blot specification into a proper LOTOS-file XOR.lotos. Please try! Then compare with the listing below.
File XOR.lotos
specification XOR[a,b,z]:noexit behaviour
XOR[a,b,z]
where
process XOR[a,b,z]: noexit:=
a;z;XOR[a,b,z] [] b;z;XOR[a,b,z]
endproc
endspec
7.5 Other Modules
The asynchronous circuits we consider are
assumed to be composed of basic components ("modules"), which are in
general more complex than simple gates. The correct behavior of such modules is
to be ensured by proper circuit design (at the transistor level), rather than
by logic design.
The XOR-gate discussed in Section 7.4 is
an example of such an asynchronous circuit module.
INVERTER
The INVERTER is another such module . The INVERTER, with input A and output Z, is stable iff Z=~A. If started in the (unstable) state Z=A, its
dynamic behaviour may be specified by the Blot
expression
INV = *[z;a]
The usual graphical symbol of the
INVERTER is
We assume that each module adheres to the
following "fundamental mode restriction", which we already formulated
in connection with the XOR-module.
(*) In a stable
condition an input may be applied; in an unstable condition no input may be
applied, but an output must occur.
C-Element
The C-Element plays an important role in
connection with asynchronous circuits. It is sequential, i.e., its output is
not uniquely determined by its inputs. The circuit has two Boolean inputs A,B and one output Z. Its dynamic behavior is represented by
the following Blot expression:
CEL = a;b;z;CEL [ ] b;a;z;CEL
The CEL-circuit has a similar function as
a SET-RESET flip-flop. The SET command is A=B=T, and the RESET command is
A=B=F.
The CEL-circuit may be realized by means
of a MAJORITY-gate implementing the Boolean function Z<=>((A/\B)\/(A/\C)\/(B/\C)),
(also known as the full-adder carry-out function). In a MAJORITY-gate the
output is evidently determined by the majority of the input values. A
CEL-circuit can be obtained from a MAJORITY-gate by providing a feedback
connection from Z to the input C, which consequently is no longer an
independent input.
The graphical symbol of the C-Element is
The CEL circuit may also be
specified by the Blot expression
CEL1 = *[a;z] || *[b;z]
Applying the laws of Chapters 2 and 3, we
can prove that CEL and CEL1 are equal (i.e., strongly
equivalent). Here is a sketch of this proof.
CEL1 = *[a;z] || *[b;z]
= a;*[z;a] || b;*[z;b]
= a;b;z;CEL1 [ ] b;a;z;CEL1
Hence, CEL1 = CEL .
ICEL-Element
The ICEL circuit is obtained from the CEL
circuit by connecting an INVERTER to the A-input of the CEL circuit. It can be
specified by the Blot expression
ICEL = *[z;a] || *[b;z]
The corresponding graphical symbol is
where the small circle o represents an inverter.
Exercise Ex7.1
Use the laws of Chapters 2 and 3 to
prove:
ICEL = b;z;CEL
Exercise Ex7.2
Use CADP to prove the preceding
assertion.
TOGGLE
This is yet another basic module we are
interested in. It has one Boolean input A and two Boolean outputs Y,Z. Its (dynamic) behaviour may be
described by the following Blot expression:
TOGGLE = *[a;y;a;z] .
We will use the symbol
to depict the TOGGLE.
].
7.6 Modular Networks
A modular network is obtained by suitably
interconnecting a finite number of modules. The modules of such a network must
adhere to the following restriction.
If p is an input of
any module, there may be at most one module with p as output. In such a case
the output p of this particular module is connected to every input p occurring
in any other module. Such an interconnection p may be declared either as an
output node of the network, or as an internal node.
7.7 Further
To get a glimpse into the world of
asynchronous circuits go to [ASYNC].
For alternative representations of
modules and additional modules see [EDIS].
7.8 References
[ASYNC] The Asynchronous Logic Home Page
http://www.cs.man.ac.uk/amulet/async/index.html
[EDIS]
Encyclopedia of Delay-Insensitive Systems
http://edis.win.tue.nl