From victor@u-aizu.ac.jp Fri Jun 23 07:30:25 1995
To: david.kinniment@ncl.ac.uk
Cc: Victor Varshavsky , Alex.Yakovlev@ncl.ac.uk,
asynchronous-request@hohum.stanford.edu,
asynchronous-private@pharos.cs.columbia.edu
Subject: Re: Asynchronous adders
In-Reply-To: Your message of "Wed, 21 Jun 1995 11:50:09 GMT."
<2C95228102A@tankytop.ncl.ac.uk>
Date: Fri, 23 Jun 1995 15:28:03 +0900
From: Victor Varshavsky
Content-Length: 6356
X-Lines: 136
Status: RO
>> From: "Alex Yakovlev"
>> Subject: from adder exchange
>Dear Prof Varshavsky
>
>Alex Yakovlev forwarded a copy of your recent e-mail on asynchronous
>addition to me for interest. In it you mention:
>
>> >"...As it was shown by von Neumann, when adding binary numbers, the
>> >expectation of maximum carry chain length d_{N} < log_{2}N [1]. In
>> >[2], we managed to find out the exact solution of recurrence von
>> >Neumann's equations for the case of self-timed binary adder (carry
>> >chains with values 0 and 1 are taken into account) and to show that,
>> >when 8 =< N =< 256, d_{N} =< log_{2}N - 0.66."
>> >
>
>These results assume a random distribution of input operands.
>This is rarely the case, since in many additions the accuracy
>required is much less than the full word length. This often leads to a
>shorter than expected carry path, but unfortunately, a significant
>proportion of additions (much larger than expected from random inputs)
>are additions with a result of zero, for example from comparisons
>with a loop variable, in which the carry propagates the full length
>of the adder. the average carry path in a real sytem is therefore
>longer than expected from an analysis based on random inputs and the
>performance of an asynchronous adder is worse than might be expected.
>For a typical distribution see:
>
>J.D.Garside, "A CMOS VLSI Implementation of an Asynchronous
>ALU." Proceedings of the IFIP Conference on Asynchronous Design
> Methodologies, Manchester, UK, 1993.
>
> David Kinniment,
> Dept of Electrical and Electronic Engineering,
> The University,
> Newcastle upon Tyne, NE1 7RU, UK.
>
> email: david.kinniment@newcastle.ac.uk
> Tel : +44 191 222 7338
> Fax : +44 191 222 8180
Dear David,
Your remark is very appropriate and true. However, the the question I
answered was associated with von Neumann's estimation.
Indeed, the modes of adding random equiprobable operands and the mode
of a counter with fixed increment differ. Moreover, there are quite
different estimations of carry length for a counter and adder working
in the counter mode.
Finding the average carry length and average phase duration in
self-timed counters is trivial:
with probability 1/2 (a half of all cases) there is no carry (1 digit
switches);
with probability 1/4 (a quarter of all cases) the carry length is 1 (2
digits switch);
with probability 1/8 (one eighth of all cases) the carry length is 2,
etc.
Then the average phase duration for the full adding cycle is:
D(n)=1/2+2(1/4)+3(1/8)+4(1/16)+...+n/(1/2^n).....=2-(n+2)(1/2)^n (1)
If an n-bit counter with negative increment (decrement) counts
starting from some initial set K = 2^m < 2^n, at the last step the
chain carry length increases by (n-m) with some influence to the
average 1/2^m; the average phase duration is:
D(n,m)= 2-(m+2)/2^m+(n-m)/2^m = 2+(n-2m-2)/2^m (2)
For the case 2^(m-1) < K < 2^m, the average duration calculation is
somewhat more complicated and depends on the code that represents K.
Another situation arises when a counter is used as a counter.
First of all, the estimations of carry chain lengths for the initial
model formulated by von Neumann and for a self-timed adder differ as
it was shown in [2]. Let the following numbers add:
101111111111111........11
+
100000000000000........00
-------------------------
011111111111111........11
>From von Neumann's point of view (and it is valid for a counter, too),
the length of a carry chain in this example is 1. In a self-timed
adder, it equals n-2 because a self-timed adder "waits" for the carry
value acknowledge produced without respect to whether it is 1 or 0.
Hence, if a self-timed adder functions in the counter mode, in the
simplest case with decrement 1, the average length of the maximum
carry chain (the average length, not the expectation!) is equal to the
expectation (here "expectation") of the length of a maximum chain of
equal bit values in equiprobable n-bit codes. The calculation of this
value leads to the same reccurent equations as the calculation of the
average maximum carry length does when random operands are added
with the same initial conditions and, respectively, with the same
results, i.e. the average step duration of the order log2n. The fact
that a self-timed counter is faster than a self-timed adder in the
counter mode is well-known in the self-timing folklore more than 20
years. The relative delay in a self-timed adder used as a counter
sharply increases if m << n (that is rather common in computing and
control algorithms) due to the delay of carry propagation in the
non-functioning "tail" in every act of counting (the delay is always
>= n-m). A similar situation appears when one works with operands of
few bits.
This fact was well-known and understood long time ago. That's why even
in early processors there was the possibility that an adder could deal
with shorten operands (for example, by separate bytes with the carry
between them blocked). It is easy to understand that the influence of
the "tail" can be removed also by using a data-controlled indicator.
As for the article by J.D.Garside, it contradicts to absolutely
nothing and disproves nothing. An analytic estimation is an absolutely
precise thing within the initial hypotheses, this is the nature of
science. At one time there was a popular expression in Russia: "the
triumph of science over common sense." Whether to believe or not to
scientific results is a subject of religion, not science. How to use
these results is methodology of a particular work
I didn't expect that the answer to the question about where, when and
how von Neumann calculated the average maximum carry length and the
information of a problem that was enough fully investigated in 60-70's
would cause such a correspondence. I should also notice that analytic
estimations are always helpful and there is a lot of examples of
devices where the hypothesis of equiprobable distribution of operand
values took place.
Sincerely yours,
Victor Varshavsky