A New Methodology The Design of Asynchronous Digital Circuits
A New Methodology The Design of Asynchronous Digital Circuits
A New Methodology The Design of Asynchronous Digital Circuits
S. K. Roy*
S. K. Desai
E(. Nanda
Abstract
trol Protocols
T h i s paper discusses a n e w design methodology f o r asynchronous digital circuits. T h e methodology as based on a n
event driven scheme and follows t h e double-rail logic handshake protocol. A n e w logic gate, called the Universal Gate,
is designed; this is the basic building block of the methodology. It i s shown t h a t t h e methodology is completely delay
insensitive. A s an example, the Shift Multiplier (71,is implemented.
1. Introduction
As the number of active devices on a chip and the device
speed increase and the minimum feature size goes down, the
clock becomes a major limiting factor in synchronous circuits[l]. Theoretically, an asynchronous design has several
advantages over the synchronous design. Due to the absence of a clocking signal, there is no clock skew problem
and there is a decrease in the power consumption. Also,
asynchronous circuits give an average case instead of a worst
case performance and result in easing of global timing issues. They also have a better potential for technology migration. Also, due to the absence of a clocking signal asynchronous circuits are, in general, more difficult to design.
Though many methodologies exist for asynchronous design
[3], automation of design has still not been fully achieved.
In the sections that follow, a novel method for designing
asynchronous circuits is outlined. It is based on a new basic gate whose design has been given here. This, it is hoped,
will make the design methodology easy to automate.
The next section overviews a general technique for communicating asynchronously. A new gate design, called the
Universal Gate, on which this methodology is based is presented in Section 3. Logic minimization techniques are discussed in Section 4. These are illustrated in detail by considering the design of an ADDER. Memory interface circuits
are presented in Section 5 and we conclude in Section 6 by
integrating the principles developed and applying them to
the design of a shift multiplier [7].
342
I (+-.-
It is not possible t o use normal level sensitive logic elements such as AND, OR, INVERT t o realise equivalent
logic blocks for the asynchronous counterparts based on our
way of representing data values. This is the motivation for
realising the Universal gate proposed here. We show how t o
render this gate to give the AND , OR, INVERT elements in
the NRZ asynchronous paradigm. Furthermore, we donot
seperate the data representation from the control signalling
as in the Micropipeline case. This we conjecture will enable a uniform and simpler way t o synthesize asynchronous
designs.
A two input AND gate actually has four input lines and
two output lines. The AND gate generates an event on
the output1 line if and only if all the inputl lines show
transitions. If any of the inputo lines shows a transition
then the outputo generates an event. It must be noted here
that an output event occurs only after all the input events
have been received.
It can be seen that the two-rail AND and OR gates are
essentially the same circuit. If we interchange the two input
rails of a pair for all the pairs, and also interchange the
output rails, then the AND circuit becomes an OR circuit
and the OR becomes the AND.
The two-rail NOT gate is realised simply by interchanging the inputl and the inputo rails. Now a transition on the
inputo,l rail will result in a transition on the outputl.0 rail
which realises the two-rail NOT gate.
As seen in the above discussion, only one gate needs t o be
realised t o implement any boolean function in the two-rail
non-return-to-zero protocol. We describe the functionality
of such a gate. Since all logic functions for the given set of
inputs can be obtained from the the same gate, we call it a
Univeral gate (U-gate).
In the two-input U-gate discussed here, two two-rail inputs and four single rail outputs are present. The output
transitions occur depending on the four possible input combination : 00, 01, 10 and 11; and depending on the input,
one of the four output lines shows a transition. Therefore
t o realise the two-rail AND gate, we identify the output
line corresponding to the 11 input as the output1 rail and
remaining outputs are disjunctively combined using XOR
gates as the outputo rail. The two rail OR gate can also be
realised similarly.
The two-input U-gate is shown in Figure 1. It is designed using eight XOR and four Muller-C elements [1,6].
Two XORs and one Muller-C element form a block. Four
instances of the block with appropriate feedback gives a
two-input U-gate. Each rail-input is fed to two blocks. Each
block receives two rail inputs and two feedback signals from
U-gate outputs in a manner in which each XOR gate in a
block receives only one input rail signal and one feedback
signal. The outputs of the four Muller-C elements constitute the four output lines of the U-gate.
Assume that transitions occur on input rails A1 and B1.
The XOR gates will pass the transitions to the inputs of
the Muller-C elements. As a result both inputs of MullerC element 3 will f i e thereby resulting in an output event
on Ma. C elements 2 and 1 will also see a transition on
one of their inputs. Since valid inputs were received and a
valid output generated, this state of these two C elements
is not acceptable as an initial state. This is because in
this state, C elements 2 anid 3 see a transition on one of
their inputs and are therefore waiting for a transition on
the other input. So if a transition now occurs on Bo then C
element 2 will fire even if no input is received on the A input
line. This is obviously an error. Rectifying it requires that
the transitioii on the input of C elements 2 and 3 must be
negated by forcing another transition on those lines. This
is done by feeding back ME3 t o the relevant inputs of C
elements 2 and 3 via the XOR gates. So now when M3 fires
another transition occurs at the inputs of the XOR gates
which have AL1or B1 as inputs. These transitions cancel the
earlier transitions. Note thatt M3 is not fed back to Block 3
XOR gates as this would again result in an error. This can
343
7 7
0001 11 10
00 01 11 10
0 0 0 1 0
1 0 1 1 1
1 1 0 1 0
CanyOut = A . ( B + C ) + B.C
B3 1
-L
gate generates all the 2" minterms. By disjunctively combining the required minterms, a Boolean function can be
realised. The major stumbling block in this approach is the
complexity of the U-gates. The two-input U-gate has four
blocks, and the outputs are fed back as eight feedbacks.
The three-input U-gate is composed of a two-input U-gate
plus eight blocks, and the total number of feedbacks are 32.
In a four-input U-gate, the total number of feedbacks is 96.
This makes the U-gates with a large number of inputs very
complex and huge. As a result this approach can be used
only if the number of inputs is small.
The third approach is a mixture of the above two methods. It is well known that any n-input Boolean function can
be decomposed and represented in terms of Boolean functions with smaller number of inputs. A function f can be
expressed in terms of two functions f1 and f 2 as under.
f ( X 1 , 52...9 2")
= fl[fi(zl,zZ,
...,zk),
{zk+l, ...,zn)]
344
OUTPUT
7
\Row 1
NjZ.-!
LY---L.--
CARRYOUT
5. Memory Interface
AI and A0 are the two rail.$of the input A. The output is single rail.
It i s in the form o f a single pulse of duration D.
345
A-
__ -__
Stage I1
Two-rail output
Two-rail output
in the
in the
return-to-zero protocol non-return-to-zero protocol
RE
r------
Stake 1
346
A in
B in
+-
START
J.
out shiftM
shiftM.
To Control Path<
-7OutPut
[6] Ivan E. Sutherland. Micropipelines. Communications 0.f the ACM, Voll. 32, no. 6, June 1989.
[7] D. Gajslki, N. Dutt, A. Wu, and S. Lin. High Level
Synthesis: Introduction to Chip and Systems Design.
Kluwer Academic Puldishers , 1992.
References
April 1996.
341