next up previous contents
Next: Trailing One Prediction Up: Addition Previous: Bit Vector Addition   Contents

Leading One Prediction

We turn now to the problem of adding two rational numbers that are encoded in a floating-point format. The following procedure represents a naive approach to the design of a floating point adder:

(1) Compare the exponent fields of the summands to determine the right shift necessary to align the significands;

(2) Perform the required right shift on the significand field that corresponds to the lesser exponent;

(3) Add (or subtract) the aligned significands, together with the appropriate rounding constant;

(4) Determine the left shift required to normalize the result;

(5) Perform the left shift and adjust the exponent accordingly;

(6) Compute the final result by assembling the sign, exponent, and significand fields.

Under the constraints imposed by contemporary technology and prevailing microprocessor clock frequencies, each of the above operations might reasonably correspond to a single clock cycle, resulting in a six-cycle implementation. It is possible, however, to improve on this cycle count by executing some of these operations in parallel.

While a large left shift might be required (in the case of subtraction, if massive cancellation occurs), and a large right shift might be required (if the exponents are vastly different), only one of these possibilities will be realized for any given pair of inputs. Thus, an efficient adder typically includes two data paths, called the close and far paths. On the close path, the sum is computed under the assumption that subtraction is to be performed and the exponents differ by at most 1. Thus, the summands are aligned quickly, but two cycles are dedicated to Steps (4) and (5). On the far path, which handles the remaining case, Steps (1) and (2) require two cycles, but the sum is easily normalized. A concurrent analysis of the exponents determines which of these paths is actually used to produce the final result. Since each path is traversed in three cycles, the total latency of the operation is reduced from six to four.

However, in order for the operation to be effectively pipelined without duplicating the adder hardware, the addition must be performed on the same cycle along both paths; moreover, the paths must merge before the addition is performed. This is made possible by a technique known as leading one prediction, which allows the left shift (of the close path) to be determined, and in fact performed, in advance of the subtraction. Consequently, steps (4) and (5) of the close path may be executed concurrently with steps (1) and (2) of the far path. Meanwhile, the exponent analysis is performed in time to select the inputs to the adder.

The objective of leading one prediction is the location of the highest index at which a one occurs in the difference of two bit vectors. Although the precise computation of this index is in general as complex as the subtraction itself, a useful approximate solution may be obtained more quickly.

Let $ a$ and $ b$ be integers of width $ e$ , with $ 0<b<a$ . We shall compute, in constant time (independent of $ a$ and $ b$ ), a positive integer $ \lambda$ such that $ expo(a-b)$ is either $ expo(\lambda)$ or $ expo(\lambda)-1$ . We begin by defining a function $ lop$ that returns the desired exponent $ expo(\lambda)$ . We are not concerned with the efficiency of this computation, since it is not actually implemented in our final solution, but is used only in the proof of its correctness.

Definition 6.2.1   (lop) Let $ a \in \mathbb{N}$ , $ b\in \mathbb{N}$ , $ k \in \mathbb{N}$ , and $ d \in \{0,1,-1\}$ . For all $ i \in \mathbb{N}$ , let $ c_{i} = a[i]-b[i]$ . Then

$\displaystyle lop(a,b,d,k) = \left\{\begin{array}{ll} 0 & \mbox{if $k=0$}\\ lo... ... k & \mbox{if $k>0$ and $d\neq 0$ and $d \neq -c_{k-1}$}.\end{array} \right.$

The computation of $ lop$ may be thought of as a traversal of the vectors $ a$ and $ b$ from left to right. At each stage, we examine the bits of $ a$ and $ b$ at some index $ k<n$ under the assumption that $ a[n:k+1] = b[n:k+1]$ . Accordingly, one of the following four steps is executed, resulting either in termination or a decrement of $ k$ :

(1) If $ k = 0$ , then conclude that $ \vert a-b\vert = \vert a[0]-b[0]\vert = 1$ and hence $ expo(a-b) = 0$ . Therefore, simply terminate with the value $ lop = 0$ .

(2) If $ k>0$ and $ a[k] = b[k]$ , then we must have $ a[n:k] = b[n:k]$ . Replace $ k$ with $ k-1$ and continue.

(3) If $ k>0$ , $ a[k] = 1$ , and $ b[k] = 0$ , then conclude that $ a>b$ . Examine $ a[k-1]$ and $ b[k-1]$ , and execute one of the following accordingly:

(i) If $ a[k] = 0$ and $ b[k] = 1$ , then replace $ a[k:k-1]$ with $ \verb!b!01$ and $ b[k:k-1]$ with $ \verb!b!00$ , effectively subtracting $ 2^{k-1}$ from both $ a$ and $ b$ . Replace $ k$ with $ k-1$ and continue.

(ii) In all other cases, it may be shown that $ k-1 \leq expo(a-b) \leq k$ . Therefore, terminate with the value $ lop = k$ .

(4) If $ k>0$ , $ b[k] = 1$ , and $ a[k] = 0$ , then follow the same procedure as in (3) with $ a$ and $ b$ are reversed.

The correctness of this computation is established by the following lemma.

  (lop-bnds) Let $ a \in \mathbb{N}$ , $ b\in \mathbb{N}$ , and $ n \in \mathbb{N}$ . If $ a < 2^{n}$ , $ b < 2^{n}$ , and $ a \neq b$ , then $ lop(a,b,0,n)-1 \leq expo(a-b) \leq lop(a,b,0,n)$ .

PROOF: More generally, we shall show, by induction on $ k$ , that if

$\displaystyle d=a[n:k]-b[n:k]$

and $ -1 \leq d \leq 1$ , then

$\displaystyle lop(a,b,d,k)-1 \leq expo(a-b) \leq lop(a,b,d,k).$

If $ k = 0$ , then $ a-b = a[n:k]-b[n:k] = d$ and since $ a \neq b$ , $ \vert d\vert = 1$ . Thus,

$\displaystyle expo(a-b) = 0 = lop(a,b,d,k).$

Suppose $ k>0$ . Then by Lemma 2.3.14,

$\displaystyle a[n:k$-$\displaystyle 1] - b[n:k$-$\displaystyle 1] = 2a[n:k]+a[k$-$\displaystyle 1] + 2b[n:k]+b[k$-$\displaystyle 1] = 2d + c_{k\mbox{-1}}.$

If $ d=0$ , then

$\displaystyle a[n:k$-$\displaystyle 1] - b[n:k$-$\displaystyle 1] = c_{k\mbox{-1}},$

and by inductive hypothesis,
$\displaystyle lop(a,b,d,k)-1$ $\displaystyle =$ $\displaystyle lop(a,b,c_{k\mbox{-}1},k-1)-1$  
  $\displaystyle \leq$ $\displaystyle expo(a-b)$  
  $\displaystyle \leq$ $\displaystyle lop(a,b,c_{k\mbox{-}1},k-1) = lop(a,b,d,k).$  

We may assume, therefore, that $ d \neq 0$ .

Suppose that $ d=-c_{k-1}$ . Then

$\displaystyle a[n:k$-$\displaystyle 1] - b[n:k$-$\displaystyle 1] = 2d + c_{k\mbox{-1}} = d$

and induction yields
$\displaystyle lop(a,b,d,k)-1$ $\displaystyle =$ $\displaystyle lop(a,b,d,k-1)-1$  
  $\displaystyle \leq$ $\displaystyle expo(a-b)$  
  $\displaystyle \leq$ $\displaystyle lop(a,b,d,k-1) = lop(a,b,d,k).$  

In the remaining case, $ d=c_{k-1}$ . By Lemma 2.2.19,
$\displaystyle a-b$ $\displaystyle =$ $\displaystyle a[n:0] - b[n:0]$  
  $\displaystyle =$ $\displaystyle (2^{k-1}a[n:k$-$\displaystyle 1] + a[k$-$\displaystyle 2:0]) - (2^{k-1}b[n:k$-$\displaystyle 1] + b[k$-$\displaystyle 2:0])$  
  $\displaystyle =$ $\displaystyle 2^{k-1}(a[n:k$-$\displaystyle 1] - b[n:k$-$\displaystyle 1]) + (a[k$-$\displaystyle 2:0]-b[k$-$\displaystyle 2:0])$  
  $\displaystyle =$ $\displaystyle 2^{k-1}(2d+c_{k-1}) + (a[k$-$\displaystyle 2:0]-b[k$-$\displaystyle 2:0]).$  

By Lemma 2.2.1,

$\displaystyle -2^{k-1} < a[k$-$\displaystyle 2:0]-b[k$-$\displaystyle 2:0] < 2^{k-1}.$

Thus,

$\displaystyle \vert a-b\vert > 2^{k-1}\cdot 3 + 2^{k-1} = 2^{k+1}$

and

$\displaystyle \vert a-b\vert > 2^{k-1}\cdot 3 - 2^{k-1} = 2^k.$

Finally, we have

$\displaystyle lop(a,b,d,k)-1 = k-1 \leq expo(a-b) \leq k = lop(a,b,d,k).$

Figure 6.6: Leading One Prediction
\begin{figure}\begin{eqnarray*} a & = & \mbox{\tt 1\;0\;1\;1\;0\;1\;1\;0\;0\;0\;... ...\;0\;0\;0\;0\;0\;0\;0\;0\;1\;0\;0\;1\;0\;0\;...\;0} \end{eqnarray*} \end{figure}

Thus, we require an efficient method for computing a number $ \lambda$ such that $ expo(\lambda) = lop(a,b,0,e+1)$ . First, we handle the relatively simple case $ expo(b) < expo(a)$ . Note that the time required for the computation is two gate delays.

  (lop-thm-1) Let $ a,b \in \mathbb{N}^{*}$ with $ expo(b) < expo(a) = e$ , and let

$\displaystyle \lambda = (2a)[e:0] \;\vert\; \verb! !(2b)[e:0].$

Then $ \lambda > 0$ and $ expo(\lambda)-1 \leq expo(a-b) \leq expo(\lambda)$ .

PROOF: Since

$\displaystyle lop(a,b,0,e+1) = lop(a,b,1,e) = lop(a[e-1:0],b,1,e),$

it will suffice to show, according to Lemma 6.2.1, that

$\displaystyle lop(a[e-1:0],b,1,e) = expo(\lambda).$

Using induction, we shall prove the more general result that for all $ k \leq e$ ,

$\displaystyle lop(a,b,1,k) = expo(\lambda[k:0]).$

First note that by Lemmas 3.2.9, 3.1.7, and 2.2.20,
$\displaystyle \lambda[k:0]$ $\displaystyle =$ $\displaystyle (2a)[e:0][k:0] \;\vert\; (\verb! !(2b)[e:0])[k:0]$  
  $\displaystyle =$ $\displaystyle (2a)[k:0] \;\vert\; \verb! !(2b)[k:0],$  

and similarly, by Lemmas 3.2.10, 3.1.8, and 2.3.12,
$\displaystyle \lambda[k]$ $\displaystyle =$ $\displaystyle \lambda[k:0][k]$  
  $\displaystyle =$ $\displaystyle (2a)[k:0][k] \;\vert\; \verb! !(2b)[k:0][k]$  
  $\displaystyle =$ $\displaystyle (2a)[k] \;\vert\; \verb! !(2b)[k].$  

If $ k = 0$ , then

$\displaystyle \lambda[k:0] = \lambda[0] = (2a)[0] \;\vert\; \verb! !(2b)[0] = 0 \;\vert\; 1 = 1$

and

$\displaystyle expo(\lambda[k:0]) = 0 = lop(a,b,1,k).$

Suppose $ k>0$ . By Lemma 2.3.10, $ \lambda[k] = a[k-1] \;\vert\; b[k-1]$ . If $ a[k-1]=0$ and $ b[k-1]=1$ , then $ \lambda[k] = 0$ , $ \lambda[k:0] = \lambda[k-1:0]$ , and by Definition 6.2.1 and inductive hypothesis,

$\displaystyle lop(a,b,1,k) = lop(a,b,1,k-1) = expo(\lambda[k-1:0]) = expo(\lambda[k:0]).$

On the other hand, if either $ a[k-1]=1$ or $ b[k-1]=0$ , then $ \lambda[k] = 0$ and

$\displaystyle lop(a,b,1,k) = k = expo(\lambda[k:0]).$

The next lemma covers the more complicated case $ expo(b)=expo(a)$ , which requires three gate delays. Figure 6.2 contains an illustration of this case.

  (lop-thm-2) Let $ a,b \in \mathbb{N}^{*}$ such that $ a \neq b$ and $ expo(a) = expo(b) = e > 1$ . Let
$\displaystyle \lambda_{t}$ $\displaystyle =$ $\displaystyle a[e:0] \;\hat{ }\; \verb! !b[e:0],$  
$\displaystyle \lambda_{g}$ $\displaystyle =$ $\displaystyle a[e:0] \;\&\; \verb! !b[e:0],$  
$\displaystyle \lambda_{z}$ $\displaystyle =$ $\displaystyle \verb! !(a[e:0] \;\vert\; \verb! !b[e:0])[e:0],$  


$\displaystyle \lambda_{0}$ $\displaystyle =$ $\displaystyle (\lambda_{t}[e:2] \;\&\; \lambda_{g}[e-1:1] \;\&\; \verb! !\lambda_{z}[e-2:0]) \;\vert$  
    $\displaystyle (\verb! !\lambda_{t}[e:2] \;\&\; \lambda_{z}[e-1:1] \;\&\; \verb! !\lambda_{z}[e-2:0]) \;\vert$  
    $\displaystyle (\lambda_{t}[e:2] \;\&\; \lambda_{z}[e-1:1] \;\&\; \verb! !\lambda_{g}[e-2:0]) \;\vert$  
    $\displaystyle (\verb! !\lambda_{t}[e:2] \;\&\; \lambda_{g}[e-1:1] \;\&\; \verb! !\lambda_{g}[e-2:0]),$  

and

$\displaystyle \lambda = \{\lambda_{0}[e-2:0], \verb! !\lambda_{t}[0]\} = 2\lambda_{0}+1-\lambda_{t}[0].$

Then $ \lambda > 0$ and $ expo(\lambda)-1 \leq expo(a-b) \leq expo(\lambda)$ .

PROOF: Let $ c_{i} = a[i]-b[i]$ . Since $ c_{e}=0$ ,

$\displaystyle lop(a,b,0,e+1) = lop(a,b,0,e) = lop(a,b,c_{e-1},e-1),$

and therefore it will suffice to show that $ \lambda \neq 0$ and $ lop(a,b,c_{e-1},e-1) = expo(\lambda)$ . In fact, we shall derive the following more general result: For all $ n \in \mathbb{N}$ , if $ n \leq e-1$ and $ a[n:0] \neq b[n:0]$ , then $ \lambda[n:0] \neq 0$ and

$\displaystyle expo(\lambda[n:0]) = \left\{\begin{array}{ll} lop(a,b,c_{n},n) & ... ...0$ or $c_{n+1}=0$}\\ lop(a,b,-c_{n},n) & \mbox{otherwise}.\end{array} \right.$

For the case $ n=0$ , note that $ a[0] \neq b[0]$ implies $ \lambda[0:0] =1$ , hence $ expo(\lambda[0:0]) = 0$ , while $ lop(a,b,c_{0},0) = lop(a,b,-c_{0},0) = 0$ .

We proceed by induction. Let $ 0<n\leq e-1$ . Note that for $ 0 \leq k \leq e-2$ ,

$\displaystyle \lambda_{0}[k] = 1$ $\displaystyle \Leftrightarrow$ $\displaystyle \lambda_{t}[k+2]=1$    and $\displaystyle \lambda_{g}[k+1]=1$    and $\displaystyle \lambda_{z}[k]=0,$    or  
    $\displaystyle \lambda_{t}[k+2]=0$    and $\displaystyle \lambda_{z}[k+1]=1$    and $\displaystyle \lambda_{z}[k]=0,$    or  
    $\displaystyle \lambda_{t}[k+2]=1$    and $\displaystyle \lambda_{z}[k+1]=1$    and $\displaystyle \lambda_{g}[k]=0,$    or  
    $\displaystyle \lambda_{t}[k+2]=0$    and $\displaystyle \lambda_{g}[k+1]=1$    and $\displaystyle \lambda_{g}[k]=0.$  

For $ 0 \leq k \leq e$ ,

$\displaystyle \lambda_{t}[k] = 1 \Leftrightarrow c_{k} = 0,$  $\displaystyle \lambda_{g}[k] = 1 \Leftrightarrow c_{k} = 1,$  and  $\displaystyle \lambda_{z}[k] = 1 \Leftrightarrow c_{k} = -1.$

It follows that for $ 0 \leq k \leq e-2$ ,
$\displaystyle \lambda_{0}[k] = 1$ $\displaystyle \Leftrightarrow$ $\displaystyle c_{k+1} \neq 0,$    and  
    if $\displaystyle c_{k+2} = 0$    then $\displaystyle c_{k} \neq -c_{k+1},$    and  
    if $\displaystyle c_{k+2} \neq 0$    then $\displaystyle c_{k} \neq c_{k+1}.$  

But since $ n>0$ , $ \lambda[n] = \lambda_{0}[n-1]$ , and since $ n \leq e-1$ ,
$\displaystyle \lambda[n] = 1$ $\displaystyle \Leftrightarrow$ $\displaystyle c_{n} \neq 0,$    and  
    if $\displaystyle c_{n+1} = 0$    then $\displaystyle c_{n-1} \neq -c_{n},$    and  
    if $\displaystyle c_{n+1} \neq 0$    then $\displaystyle c_{n-1} \neq c_{n}.$  

If $ c_{n} = 0$ , then $ \lambda[n]=0$ ; hence, $ \lambda[n:0] = \lambda[n-1:0] \neq 0$ and

$\displaystyle expo(\lambda[n:0])=expo(\lambda[n-1:0])=lop(a,b,c_{n-1},n-1)=lop(a,b,c_{n},n).$

Next, suppose $ c_{n} \neq 0$ and $ c_{n+1}=0$ . If $ c_{n-1}=-c_{n}$ , then $ \lambda[n]=0$ , hence $ \lambda[n:0] = \lambda[n-1:0] \neq 0$ and

$\displaystyle expo(\lambda[n:0])$ $\displaystyle =$ $\displaystyle expo(\lambda[n-1:0])$  
  $\displaystyle =$ $\displaystyle lop(a,b,-c_{n-1},n-1)$  
  $\displaystyle =$ $\displaystyle lop(a,b,-c_{n-1},n)$  
  $\displaystyle =$ $\displaystyle lop(a,b,c_{n},n).$  

But if $ c_{n-1} \neq -c_{n}$ , then $ \lambda[n]=1$ and

$\displaystyle expo(\lambda[n:0])=n=lop(a,b,c_{n},n).$

Finally, suppose $ c_{n} \neq 0$ and $ c_{n+1} \neq 0$ . If $ c_{n-1}=c_{n}$ , then $ \lambda[n]=0$ , $ \lambda[n:0] = \lambda[n-1:0] \neq 0$ , and

$\displaystyle expo(\lambda[n:0])$ $\displaystyle =$ $\displaystyle expo(\lambda[n-1:0])$  
  $\displaystyle =$ $\displaystyle lop(a,b,-c_{n-1},n-1)$  
  $\displaystyle =$ $\displaystyle lop(a,b,-c_{n-1},n)$  
  $\displaystyle =$ $\displaystyle lop(a,b,-c_{n},n).$  

But if $ c_{n-1} \neq c_{n}$ , then $ \lambda[n]=1$ and

$\displaystyle expo(\lambda[n:0])=n=lop(a,b,-c_{n},n).~$

next up previous contents
Next: Trailing One Prediction Up: Addition Previous: Bit Vector Addition   Contents
David Russinoff 2007-01-03