From nowick@cs.columbia.edu Tue Jun 20 18:44:33 1995
Date: Tue, 20 Jun 95 13:35:44 EDT
From: Steven Nowick
To: asynchronousprivate@cs.columbia.edu
Subject: [Victor Varshavsky : Carrychain lenth]
ReplyTo: asynchronous@hohum.stanford.edu
ContentLength: 8595
XLines: 172
Status: RO
Received: from cs.columbia.edu (cs.columbia.edu [128.59.10.13]) by ober.cs.columbia.edu (8.6.12/8.6.6) with ESMTP id WAA03535 for ; Wed, 14 Jun 1995 22:41:36 0400
Received: from hohum.Stanford.EDU (hohum.Stanford.EDU [36.22.0.200]) by cs.columbia.edu (8.6.12/8.6.6) with SMTP id WAA22718 for ; Wed, 14 Jun 1995 22:41:34 0400
Received: by hohum.Stanford.EDU (5.57/Ultrix3.0C)
id AA11260; Wed, 14 Jun 95 19:10:41 PDT
Received: from pross70.uaizu.ac.jp (pross70 [163.143.176.102]) by uaizugw5.uaizu.ac.jp (8.6.10+2.4W/3.2Wuaizugw.uaizu.ac.jp03/30/94) with ESMTP
id LAA03267; Thu, 15 Jun 1995 11:41:25 +0900
Received: from localhost (localhost [127.0.0.1]) by pross70.uaizu.ac.jp (8.6.10+2.4W/3.2Wrsvss2.uaizu.ac.jp03/17/94) with ESMTP
id LAA28497; Thu, 15 Jun 1995 11:41:25 +0900
MessageId: <199506150241.LAA28497@pross70.uaizu.ac.jp>
To: jose@watson.ibm.com
Cc: asynchronous@hohum.stanford.edu
Subject: Carrychain lenth
Date: Thu, 15 Jun 1995 11:41:24 +0900
From: Victor Varshavsky
ContentType: text
ContentLength: 7480
Dear Jose A. Tierno,
Unfortunately, my Email retourned me. I try again.
 Forwarded Message
>From MAILERDAEMON@profsv1.uaizu.ac.jp Wed Jun 14 14:31:25 1995
Received: from uaizugw5.uaizu.ac.jp (uaizugw5 [163.143.103.55]) by profsv1.uaizu.ac.jp (8.6.10+2.4W/3.2Wrsvss2.uaizu.ac.jp03/17/94) with ESMTP
id OAA23917 for ; Wed, 14 Jun 1995 14:31:19 +0900
Received: from localhost (localhost) by uaizugw5.uaizu.ac.jp (8.6.10+2.4W/3.2Wuaizugw.uaizu.ac.jp03/30/94) with internal
id OAA26416; Wed, 14 Jun 1995 14:31:15 +0900
Date: Wed, 14 Jun 1995 14:31:15 +0900
From: Mail Delivery Subsystem
Subject: Returned mail: User unknown
MessageId: <199506140531.OAA26416@uaizugw5.uaizu.ac.jp>
To:
The original message was received at Wed, 14 Jun 1995 14:31:05 +0900
from pross70 [163.143.176.102]
 The following addresses had delivery problems 
(unrecoverable error)
 Transcript of session follows 
... while talking to cs.columbia.edu.:
>>> RCPT To:
<<< 550 ... User unknown
550 ... User unknown
 Original message follows 
ReturnPath: victor@uaizu.ac.jp
Received: from pross70.uaizu.ac.jp (pross70 [163.143.176.102]) by uaizugw5.uaizu.ac.jp (8.6.10+2.4W/3.2Wuaizugw.uaizu.ac.jp03/30/94) with ESMTP
id OAA26414; Wed, 14 Jun 1995 14:31:05 +0900
Received: from localhost (localhost [127.0.0.1]) by pross70.uaizu.ac.jp (8.6.10+2.4W/3.2Wrsvss2.uaizu.ac.jp03/17/94) with ESMTP
id OAA28075; Wed, 14 Jun 1995 14:31:04 +0900
MessageId: <199506140531.OAA28075@pross70.uaizu.ac.jp>
To: asynchronous@hohum.stanford.edu
cc: asynchronousprivate@cs.columbia.edu, victor@uaizu.ac.jp
Subject: Re: ["Jose A. Tierno" : Carrychain Length]
Inreplyto: Your message of "Tue, 13 Jun 1995 18:22:49 EDT."
Date: Wed, 14 Jun 1995 14:31:03 +0900
From: Victor Varshavsky
Dear Jose A.Tierno,
Fragments from an article we are preparing now might be of interest
for you. Actually, the article will be devoted to the possibility of
using incorporated datadependent delays in asynchronous design. We
consider an adder as an example.
"...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 selftimed 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."
"...First, let us consider the distribution of lengths of carry chains
ina nonbinary (scaleofk) adder. Like in a binary adder, a
singledigit adder consists of two parts: the sum production circuit
S_{i}=(A_{i}+B_{i}+C_{i1})_{modk} and the carry production circuit
C_{i}=Sign(A_{i}+B_{i}+C_{i+1}k). The sum production circuit is
always waiting for the value of the carry from the preceding
digit. The carry production circuit can be in two states: in the state
of waiting (W) when A_{i}+B_{i}=k1 (C_{i}=C_{i1}) and in the state
of readiness (R) otherwise. If the digits of the summands are
distributed with equal probabilities, the probability of the waiting
state is p_{w}=1/k and that of the readiness state is p_{r}=(k1)/k.
Let us define a chain of carries as a sequence of digit adders in the
waiting state which has its direct ancestor and successor in the
readiness state. P_{N}(j) is the probability that an Ndigit adder has
a chain of carries with the length not less than j. This probability
can be represented as a sum of the probabilities of two mutually
excluding events (fig.1):
a) N1 least significant digits contain a chain of carries with the
length not less than j;
b) there is no such a chain in the Nj1 least significant digits and
the j+1 most significant digits contain a chain of states like:
WW.....WWR which appears with the probability (k1)/k^{j+1}.
Hence, P_{N}(j)=P_{N1}(j)+(1P_{Nj1}(j))(k1)(1/k)^{j+1} (1)
< N >

 < N1 >
 
 < j1 > < Nj1 >
______ _____________ _______
          
 W  W ... W  W  R  * ... *  * 
______ ____________ ______
To solve the recurrent equation (1), one should determine the initial
conditions. The least significant bit of the adder can come to the
state W only with cycle adding (we will not consider this case
here). Then P_{N}(j)=0 if j >= N; P_{N}(N1)=(1/k)^{N1} and
P_{N}(0)=(11/k)^{N1}. And, at least, the expectation of the
maximum chain of carries in an Ndigit adder for a single adding
operation is
d_{N}=E_{j}P_{N}(j) (j=(1,N1)) (2)
The results of the numerical solution of the recurrent equation (1)
are given in Tab 1. These results are intriguing by themselves and may
be interesting and useful for designers.
Table 1
___________________________________________________
 \ k/i     
N(bits)\  2/1  4/2  16/4  256/8 
____ ___\______________________________________
     
 16  3.24  1.19  0.18  0.004 
_______________________________________________
     
 32  4.29  1.7  0.38  0.012 
_______________________________________________
     
 64  5.31  2.2  0.67  0.027 
_______________________________________________
     
 96  5.9  2.5  0.86  0.042 
_______________________________________________
In Tab 1, the expectations of maximum length of a chain carries
are given for Nbit adders (d_{N}) divided to groups of length
i=\log_{2}k bits with carrylookahead circuits in each group.
For the first time, von Neumann's result was given in the report by
Burks, Goldstain and von Neumann "Preliminary consideration......."
first published in 60's in Datamation. Although, by all appearances,
this result was taken from von Neumann's unpublished work "First draft
of a report on the EDVAC, Contract No W670ORD4926. A reference can
be found in [1]  Briley B.E. "Some new results on average worst
carry." IEEE Trans. Comp. 1973, vol. C22, No.5, pp.459463.
[2]  Varshavsky V.I., Rosenblum L.Ya., Starodubtzev N.A. "About
average time for carry forming on the deadbeat counter and adder",
Automaton and Computer Engineering, 1975, No.3, pp.8896, Riga (in
Russian). This journal was translated into English and the translation
was published in the USA.
Sincerely yours,
Victor Varshavsky.
 End of Forwarded Message