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