We turn now to the problem of adding two real 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 and be integers of width , with . We shall compute, in constant time (independent of and ), a positive integer such that is either or . We begin by defining a function that returns the desired exponent . 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 11.2.1   (lop) Let , , , and . For all , let . Then

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

• If , then conclude that and hence . Therefore, simply terminate with the value .

• If and , then we must have . Replace with and continue.

• If , , and , then conclude that . Examine and , and execute one of the following accordingly:

• If and , then replace with and with , effectively subtracting from both and . Replace with and continue.

• In all other cases, it may be shown that . Therefore, terminate with the value .

• If , , and , then follow the same procedure as in (3) with and are reversed.

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

(lop-bnds) Let , , and . If , , and , then .

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

and , then

If , then and since , . Thus,

Suppose . Then by Lemma 2.3.18,

----

If , then

--

and by inductive hypothesis,

We may assume, therefore, that .

Suppose that . Then

--

and induction yields

In the remaining case, . By Lemma 2.2.22,
 ---- ---- --

By Lemma 2.2.1,

--

Thus,

and

Finally, we have

Thus, we require an efficient method for computing a number such that . First, we handle the relatively simple case . Note that the time required for the computation is two gate delays.

(lop-thm-1) Let with , and let

Then and .

PROOF: Since

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

Using induction, we shall prove the more general result that for all ,

First note that by Lemmas 3.1.13, 3.2.4, and 2.2.23,

and similarly, by Lemmas 3.1.14, 3.2.5, and 2.3.16,

If , then

and

Suppose . By Lemma 2.3.14, . If and , then , , and by Definition 11.2.1 and inductive hypothesis,

On the other hand, if either or , then and

The next lemma covers the more complicated case , which requires three gate delays. Figure 11.6 contains an illustration of this case.

(lop-thm-2) Let such that and . Let

and

Then and .

PROOF: Let . Since ,

and therefore it will suffice to show that and . In fact, we shall derive the following more general result: For all , if and , then and

For the case , note that implies , hence , while .

We proceed by induction. Let . Note that for ,

 and     and     or and     and     or and     and     or and     and

For ,

and

It follows that for ,
 and if     then     and if     then

But since , , and since ,
 and if     then     and if     then

If , then ; hence, and

Next, suppose and . If , then , hence and

But if , then and

Finally, suppose and . If , then , , and

But if , then and

David Russinoff 2017-08-01