Leading-One Prediction with Concurrent Position Correction.
AbstractThis paper describes the design of a leading-one prediction (LOP) logic for floating-point addition with an exact determination of the shift amount for normalization of the adder result. Leading-one prediction is a technique to calculate the number of leading zeros of the result in parallel with the addition. However, the prediction might be in error by one bit and previous schemes to correct this error result in a delay increase. The design presented here incorporates a concurrent position correction logic, operating in parallel with the LOP, to detect the presence of that error and produce the correct shift amount. We describe the error detection as part of the overall LOP, perform estimates of its delay and complexity, and compare with previous schemes.
INTRODUCTION
Leading-one prediction is used in floating-point adders to eliminate the delay of the
determination of the leading-one position of the adder output from the critical path. This
determination is needed to perform the normalization of the result. Since the latency
of floating-point addition is significant in many applications, this prediction might be of
practical importance.
The direct way to perform the normalization is illustrated in Figure 1a). Once
the result has been computed, the Leading-One Detector (LOD) 1 counts and codes the
number of leading zeros and then, the result is left shifted. However, this procedure
can be too slow, since it is necessary to wait until the result is computed to determine
the shift amount. Alternatively, as shown in Figure 1b), the normalization shift can
be determined in parallel with the significands addition. The Leading-One Predictor
anticipates the amount of the shift for normalization from the operands. Once
the result of the addition is obtained, the normalization shift can be performed since
the shift has been already determined. This approach has been used in some recent
floating-point unit design and commercial processors [3, 7, 8, 9, 11, 18, 19].
As described below, the basic schemes developed for the leading-one predictor give
the position with a possible error of one bit. Because of this, a second step consists of
detecting and correcting this error, but this step increases the overall delay. To avoid this
delay increase, we propose a correction procedure which detects the error in parallel with
1 The LOD is also called LZD (Leading Zero Detector)
2 The LOP is also called LZA (Leading Zero Anticipator)
LOD
input A input B
result
result
input A input B
SIGNIFICAND
ADDER / SUB.
shift
coding
a) b)
ADDER / SUB.
SIGNIFICAND
shift
coding

Figure

1: Magnitude Addition and Normalization for a Floating-point Adder Unit.
the determination of the position, so that the correction can be performed concurrently
with the first stage of the shifter. The evaluation and comparison presented show that
it is plausible that this can be achieved in a specific implementation, both for the single
datapath and the double datapath cases.
1.1 Previous work
Several LOPs has been recently proposed in the literature [4, 17, 19]. We briefly discuss
each of them.
The LOP described in [19] has the general structure shown in Figure 2a). As
described in detail in Section 2, the pre-encoding examines pairs of bits of the operands
and produces a string of zeros and ones, with the leading one in the position corresponding
to the leading one of the addition result. This string is used by the LOD to produce an
encoding of the leading-one position. Because of the characteristics of the pre-encoding
the resulting leading-one position might have an error of one bit. Therefore, it is necessary
to correct the error by an additional one bit left shift, called the compensate shift and
performed after the basic normalization shift. This compensate shift increases the delay
of the floating-point addition. The design in [19] is performed for the case in which
during the alignment step, the operands are compared and swapped so that the result of
the subtraction is always positive. This simplifies the implementation of the adder and
of the LOP. However, it cannot be used in the case of floating-point adders with double
datapath, as explained further in Section 5.
B:
A:
B:
A:
B:
A:
compensate
shift
normalization
LOD
ADDER
O P
Pre-encoding
ADDER
LOD
Pre-encoding
O P
ADDER
detection
tree
c)
shift
LOD
O P
correction
Pre-encoding
normalization
shift
a)
carry select
correction
shift
normalization
shift
carries

Figure

2: LOP architectures. a) Without concurrent correction. b) With concurrent
correction based on carry checking. c) With concurrent correction based on parallel
detection tree
In [4] a LOP with concurrent position correction based on carry checking is de-
scribed. Its general structure is shown in Figure 2b). It has been designed as part of
a multiply-add-fused (MAF) unit [5, 9]. As in the previous scheme, the LOP has the
possibility of a wrong prediction by one position. To perform the correction, the carry
in the adder going into the anticipated leading-one position is checked and the position
is corrected according the carry value. The correction is done in the last stage of the
normalization shift. Therefore, in principle the correction does not increase the delay.
However, as we show in Section 5, the carry detection is slow so that it introduces an
additional delay in the floating-point addition. A similar scheme is proposed in [17].
1.2 Contribution
The main contribution of this paper is to propose and evaluate a method to perform the
correction to the one position error of the basic LOP during the normalization shift without
producing any delay degradation. This is achieved by detecting the error condition
concurrently with the basic LOP (and therefore, with the significands adder).
We describe the development of the detection and correction scheme in a systematic
way. Since this description has much in common with the description of the basic LOP,
we also include the latter.
The proposed LOP operates for the general case in which the output of the adder
can be positive or negative. A version for the case in which the operands to the adder are
previously compared so that the result of the subtraction is always positive is described
in [1].
Our approach (Figure 2c)) to the basic LOP is similar to that of [19], extended to
the case in which the output of the adder can be positive or negative. It is based on
the location of some bit patterns producing the leading-one and the binary coding of
its position by means of a binary tree. Moreover, we include another pre-encoding and
trees to detect the occurrence of an error in the basic LOP. The output of these trees is
then used to correct the output of the LOD so that the correct shift is performed. Since
the detection and correction can be performed before the last stage of the normalization
shift, the delay of the addition is not increased.
Since almost all the floating-point processors [6, 10, 13] use the IEEE standard [15],
we consider the case of sign-and-magnitude representation of the operands.
The paper is organized as follows. In Section 2 the structure of the LOP is presented.
After that, the different modules of the LOP are described: the leading-one position
encoding in Section 3 and the concurrent position correction in Section 4. Then, in
Section 5, our design is evaluated and compared with other LOPs. Finally, in Section 6,
the effect on the floating-point addition latency is discussed.
GENERAL STRUCTURE
We now give an overview of the structure of the leading-one predictor we propose. Then,
in the following sections we consider individual modules. As stated in the introduction,
the two significands are in sign-and-magnitude and the LOP is only applicable when
the effective operation is a subtraction. As shown in Figure 1b), the LOP predicts the
position of the leading-one in the result, in parallel with the subtraction of significands.
The LOP operates on the significands after alignment. We denote by A = a
being a 0 and b 0 the most significant bits
and the operation to be performed by the
magnitude adder is jA \Gamma Bj 3 . We develop a LOP for the general case in which either
3 Note that we consider only the positive aligned significands and do not consider the signs of the
floating-point operands
correct
AND
NORMALIZATION
for Concurrent
Correction
for Leading-One
Encoding
string of symbols
(n symbols)
string of 0s and 1s
(n bits)
DETECTION
Vlog n bits
CORRECT.
MODULE
COARSE
| A - B | (from adder)
normalized

Figure

3: General structure of the proposed LOP
B. This is in contrast with the simplified LOP considering only A - B,
which was proposed in [19] and for which we added the concurrent correction in [1].
This extension is necessary because the LOPs described in [19] and [1] are suitable only
for floating-point adders where the operands are swapped to obtain always a positive
result in the case of an effective subtraction. As discussed further in Section 5, this
is effective only for single-datapath floating-point adders which have a comparator in
parallel with the alignment shift. In contrast, the LOP we propose can be incorporated
also in floating-point adders which swap the operands depending only on the exponent
difference. In these cases, the result of an effective subtraction may be negative when
the exponents are equal.
As shown in Figure 3, the LOP is divided into two main parts: the encoding of
the leading-one position and the correction of this position. Moreover, these parts are
composed of the following components:
Encoding
ffl A pre-encoding module that provides a string of zeros and ones, with the
defining the leading-one position. After this leading one, it
is immaterial what the rest of the string is.
ffl An encoding tree (also called leading-one detector (LOD) to encode the position
of the most-significant 1 into a
to drive the shifter for normalization. In addi-
tion, the bit V indicates when the result is 0.
Correction
ffl A pre-encoding module providing a string of symbols that is used to determine
whether a correction is needed. As indicated in Figure 3, there is significant
commonality between both pre-encoding modules.
ffl A detection tree to determine whether the position indicated by the encoding
tree has to be corrected (incremented by one)
ffl A correction module that performs the correction, if necessary, in parallel with
the operation of the barrel shifter.
In Sections 3 and 4 we describe these two parts and the corresponding modules and trees.
3 POSITION ENCODING
3.1 Pre-encoding module
As indicated in Figure 3, this module produces a string of zeros and ones. As a first
step in the production of this string we perform a radix-2 signed-digit subtraction of the
significands. We obtain
This operation is done on each bit slice (without carry propagation), that is
for clarity, the \Gamma1 will be represented as 1.
We now consider the string W to determine the position of the leading one. For-
mally, the determination of this position requires a conversion of the signed-digit representation
into a conventional binary representation. However, as we see now this conversion
is not actually required.
To simplify the discussion we consider separately the cases W ?
The notation used throughout the paper is the following: x denotes an arbitrary
substring and 0 k , 1 k , and 1 k denote strings of k 0's, 1's, and 1's, respectively, with k - 0.
The alternative situations for the location of the leading one are described in the diagram
of

Figure

4. The last level of the diagram indicates all the possible combinations of W
in radix 2 signed-digit and non-redundant binary representations, together with the
location of the leading-one. Since W ? 0, the first digit w i different from 0 has to be
equal 1. Therefore, the top of the diagram shows the w string 0 k 1(x). For the substring
(x) two situations can be identified as follows:
S1 The digit of w following the first 1 is either 0 or 1. In this case, the leading one is
located in position k 2. This is shown by considering two cases (see
1. The digit following the first 1 is 1. That is,
Clearly, the conversion of W to conventional representation has a 1 in position
k+1 since any borrow produced by a negative x is absorbed by the 1 at position
k+ 2. In this situation a leading one in position i is identified by the substring
2. The digit following the first 1 is 0. That is,
Now, two possibilities exist with respect to x, namely,
ffl (x) is positive or zero. The position of the leading one is k + 1, since there
is no borrow from (x).
ffl (x) is negative. The position of the leading one is because of the
borrow produced by (x). That is,
The problem with this situation is that it is not possible to detect it by
inspecting a few digits of w since it depends on the number of zeros before
the - 1. Consequently, we assume that the position is k+1 and correct later.
The leading 1 in position i is identified by the substring
(0;
@ @
ae
ae
ae
ae
ae
ae
ae
ae
ae
Z
Z
Z
Z
Z
Z
Z
Z
Z
Z ~0kj
(0;
@ @
ae
ae
ae
ae
ae
ae
ae
ae
ae
Z
Z
Z
Z
Z
Z
Z
Z
Z
Z ~0k
\Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega
positive
negative
or
zerok
0(x)\Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega
positive
negative
or
zerok
+Correction
Correction
Assume
position
+Patterns
1),
Assume
position
+Patterns
1),(1

Figure

4: Bit patterns for W ? 0

Table

1: Leading-one position for W ? 0
Bit Pattern Leading-one Position Substring
First
10fpositive or zerog First
First 0 after the
Last 1 of the string k
0fpositive or zerog Last 1 of the string k
First 0 after the last
* correction needed
In summary, for S1 the leading one in position i is identified by the substrings
S2 The first 1 of W is followed by a string of - 1s. That is,
If the string of - 1s is of length j the position of the leading 1 is
depending on a similar situation as in S1. Consequently, using the same approach
we assume that the position is k correct later. A leading one in position
i is identified by substrings
This discussion is summarized in Table 1. By combining the S1 and S2 cases, the
leading-one position in determined by the substrings,
Case
The same analysis can be extended to determine the leading one position when W ! 0.
This is achieved by exchanging the role of 1 and - 1 in the W ? 0 case. Therefore, the
leading-one position is identified by the following substrings,
Case
In this case there is no leading one. The encoding tree will provide a signal indicating
this situation. Therefore, it is immaterial what the encoding is.
3.1.1 String to identify the leading-one position
We now produce the string of zeros and ones which has as first one the leading-one. We
call string. The corresponding bit of F is obtained by combining the
substrings described before. To simplify the description of F , the values of digit w i equal
to 1, 0 or 1, are now called respectively. That is, for each bit position of the
input operands, the following functions are defined:
With this notation the substrings are,
ffl For W ? 0,
ffl For
Figure 5a) and 5b) show examples of the computation of F (pos) and F (neg) according
to equations (2) and (3).
It would be possible now to use both strings F (pos) and F (neg) to encode the
position of the leading one in separate LODs and to choose between them when the sign
is known. However, it is more efficient to combine both strings and have a single LOD 4 .
The simplest way to combine them would be to OR the two expressions. However, this
produces an incorrect result because, for instance, a 1 of f i (neg) can signal a leading-one
position that is not correct for a positive W . An example of this is given in Figure 5c).
Because of the above-mentioned problem we use also w i\Gamma1 in the substrings that
are ORed to produce the combined F . From Figure 4 we see that the substring w i w
identifies the leading one only when w Similarly, the substring w i w
identifies the position when w Consequently, the extended expression is
e
In contrast, as will be discussed in Section 4, we will use two separate strings for the detection of
the pattern for correction.
B:
A:
W:
s
W:
F:
c)
a) F(pos) b) F(neg)
d) Combined F
B:
W:
A:
s
W:
s

Figure

5: Computation of the intermediate encoding
Similarly, for the negative string
Combining both equations we obtain
This can be transformed to
e
An example of the calculation of string F is given in Figure 5d).
Note that for the case We postpone the description of
the implementation of this module until we have discussed also the pre-encoding for the
concurrent correction, since these modules share components.

Figure

Design of an 8-bit LOD. a) Tree implementation. b) Logic structure of the
4-bit LOD block
3.2 Encoding tree
Once the string F has been obtained, the position of the leading one of F has to be
encoded by means of a LOD tree [14, 19]. Figure 6a) shows the structure of an 8-bit
LOD, following the scheme and notation described in [14]. Bit V of each LOD block
indicates if there is some 1 in the group of bits under consideration in such block, and
P encodes the relative position of the 1. As an example, Figure 6b) shows the logic
structure of a 4 bit LOD block (block LOD-4 in the tree). Note that the logic structure
of the LOD-8 block will be similar, with the multiplexer having 2 bit inputs and a 3 bits
output. The relative position of the 1 inside each group is obtained by concatenation of
depending if the 1 is the block of V 0 or V 1, respectively. The
final P encodes the position of the leading one.
In case we obtain the final This indicates that a shift of n
bits should be performed.
4 CONCURRENT POSITION CORRECTION
As explained in Section 3, the position of the leading one predicted from the input
operands has one bit error for the following patterns of W :
1.
A:
tree tree
positive
Pre-encoding logic
correct
negative
correction
G
G
Positive encoding Negative encoding
for concurrent correction
is present
pattern
is present
pattern
is present
pattern
negative
positive

Figure

7: Detection of a correction pattern
2.
In these cases the position has to be corrected by adding 1 to the encoding calculated
in the tree. Therefore, the concurrent position correction has two steps: (1) detection
of when it is necessary to correct and (2) correction of the position encoding. The first
step is carried out in parallel with the leading-one encoding and the second one with the
normalization shifting.
4.1 Detection

Figure

7 shows the general scheme for the detection of a correction pattern. As explained
before the detection is performed by two modules: a pre-encoding module and a detection
tree. In the pre-encoding logic, two different strings are obtained: G p is used to detect
the presence of a positive correction pattern (case W ? to detect a negative
correction pattern (case W ! 0). As done for the position encoding of the previous
section, it is possible to combine both strings and have one tree to detect both types of
patterns. However, we have found that this complicates substantially the tree, so that
we have opted by using two different trees: G p is processed by the positive tree and G n
by the negative tree. We now describe these modules.

Table

2: Relation between W and a) G p and b) G n
otherwise z
a)
otherwise z
4.1.1 Pre-encoding module
For this pre-encoding we use the W string obtained before. Two new encodings are
constructed to carry out the detection, G p to detect a positive correction pattern, and
G n to detect a negative one. In both cases, it is necessary to distinguish between the
digit values 1 and - 1. Therefore, digits in the string G p and G n can take values f\Gamma1; 0; 1g.
To simplify the notation, we use n, z and p for - 1, 0 and 1, respectively. Specifically, for
the positive case, to detect the two patterns of W we construct the string G p and detect
the pattern
Similarly, for G n we detect the pattern
Let us consider G what we need to detect is the pattern
consisting of the leading one followed by zeros and terminating in a - 1, we do as follows:
ffl use the F (p) string described by expression (2) of Section 3. This will give us the
leading one followed by zeros.
ffl for the combination w This will give us the position of
the - 1.
The resulting relation between substrings of W and digits of G p is shown in Table 2a).
Note that for substrings w and n of G p are
set. According to the previous discussion, these cases have to be interpreted as n. This
interpretation is performed by the positive detection tree.

Figure

8 indicates for each pattern of W the corresponding string G p . As can be
seen, G p has the pattern z k pz q n only for the cases in which correction is needed.
a)
correction needed
c)
d)
correction needed
f)

Figure

8: Patterns in the string G p for W ? 0 case.
In a similar way, the pre-encoding G n is obtained. Table 2b) shows the relation
between W and the digits of G n .
4.1.2 Implementation
The pre-encoding module implements the expressions for F , G p , and G n , namely
ffl For F
ffl For G p
ffl For G n
The implementation is shown in Figure 9.
4.1.3 Detection Tree
To detect if one of the two patterns for correction is present a binary tree can be used,
being the input to the tree the intermediate encoding G. However, if a single tree is
used to detect the positive pattern (pz k n) and the negative one (nz k p), the number of
values of each node of the tree would be large, resulting in a complex and slow hardware
implementation. Therefore, we propose to use two different trees, one to detect the
positive pattern (positive tree) and other to detect the negative pattern (negative tree).
As shown in Figure 7, these two trees operate in parallel, but if one of the patterns is
present, only the corresponding tree will detect it.
Positive Tree
The positive tree receives as input the string G P and has to detect if the pattern z k pz q n(x)
is present. A node of the tree has five possible values, Z, P , N , Y , and U , representing
a

Figure

9: Implementation of the pre-encoding logic
the following substrings:
where Y indicates that the pattern has been detected and U indicates a string incompatible
with the pattern.
Each node of the tree receives as input the output from two nodes of the preceding
level and produces the combined value. Figure 10a) illustrates how the nodes of different
level are combined and Table 3a) shows the function table of a node of the tree. The left
input of the node is represented in the first column of the table and the right input in
the first row. Output Y is the result of the combination of a left P and a right N value.
Once the Y value has been set, the combination with any other right input results in

Table

3: Node functions a) for the positive tree and b) for the negative tree
Z
U U U U U U
a)
Z
U U U U U U
Y , since once the string has been found in the most-significant digits of the string, the
least-significant digits have no effect.

Figure

10b) shows an example of the detection of the pattern. In this case, the
pattern z 5 pz 8 n (x) is present in the string and the result is that the position has to be
corrected (value Y ).
Note that, if the first digit different from z in G p is n, that is, we are examining a
negative W string with the positive tree, then the value obtained as output in the last
level of the tree will be N .
For a simple implementation we encode the five values with four variables and assign
code 0000 to value U . With this encoding, the logic equations are,
input and the
right input, respectively.
Negative Tree
The negative tree is obtained by exchanging the role of P and N in the positive tree. It
receives as input the G n string. The node function is shown in Table 3b).
Similarly to the positive detection tree, if a positive W string is processed, the final
value obtained is P .
String G p least-significant
digits
node node
Level
Level i
a)
Y
Z P Z N N
z z
Z
z z
Z
z z
Z
left right
Z
z z
Z
z z z p
z z
Z
z z
string detected
most-significant
digits

Figure

10: Binary tree to detect the correction pattern
Implementation
The hardware implementation of the nodes in the positive tree (equations (7)) and the
negative tree is shown in Figure 11.
4.2 Correction of the normalization shift
The last step in the LOP we propose is the correction of the leading-one position. The
correction is done by incrementing by one the shift amount. As done in [19], to reduce
the delay of the shifter it is convenient to decode the shift amount in parallel with the
adder (if there is sufficient time). Moreover, because of implementation constraints, the
shifter has more than one stage. As shown in Figure 12, the stages are organized from
the coarsest to the finest. This last one performs a shift by one of several contiguous
positions, say from 0 to k f binary positions. As indicated in the Figure, we perform
the correction at this last stage, so that the shifter has to be modified to shift from 0
to positions. This should have a negligible effect on the delay of the last stage.
Notice that the selection between correction and no-correction can be made in parallel
with the previous stages of the shifter.
Z
Y P N
Z

Figure

Hardware implementation of a tree node
5 EVALUATION AND COMPARISON
In this section the LOP architecture we propose is evaluated in terms of delay of the critical
path and added hardware complexity. Then, we compare it with implementations of
the two schemes discussed in Section 1.1, namely the LOP without concurrent correction
and the LOP with concurrent correction based on carry checking.
5.1 Evaluation
To evaluate the LOP, we carry out a timing analysis of the architecture, where the critical
path of the addition and normalization shift for bits is calculated. Moreover, we
estimate the additional hardware needed for the concurrent correction.
Timing Analysis
We estimate the delay of the differents blocks of the architecture using as unit the delay
of a simple gate (2-input NAND). These delays are summarized in Table 4a). Some of the
estimations are obtained from [19], where a thorough comparison is performed between
the LOPs described in [19] and [4].
The delay of the pre-encoding logic F , G p and G n has been calculated according
the hardware implementation proposed in Figure 9. To compute the delay of the LOD
and of the detection tree, we have considered trees with six levels. The first level of the
decoder decoder
ls bits
decoder
partial shift
f
Leading-one position
ms bits
unnormalized |A - B|
first stage
of the shifter
of the shifter
second stage
last stage
of the shifter
normalized |A - B|
correction
(from
correct
tree)
detection
shift
partial shift partial shift

Figure

12: Concurrent correction of the leading-one position
LOD is composed only of NOR gates and the delay of the remaining levels is determined
by a 2-input multiplexer. However, for levels 3, 4, 5 and 6 the control input to the
multiplexers are known in advance, before the inputs are obtained from the previous
level [14]. Therefore, the delay of those levels can be estimated in 2 t nand each. This
results in a total delay for the LOD of 12 t nand
The delay of each level of the detection tree is determined by a two-level NAND-
NAND network (see Figure 11). Note that the Z output has a load of 7 gates; however,
the load of the slowest path in the node, the Y output, is only of 1 gate. Therefore, the
load of Z does not affect the global delay of the node.
We consider that the normalization shift is carried out in two stages, coarse shift and
fine shift, each operating on three bits of the shift amount. Consequently, each shifter is
implemented by 8-input multiplexers. Moreover, buffers are needed at the control input
of the shifters, due to the heavy load of those lines.

Figure

13a) shows the general structure and the delay of each of the parallel paths
in the adder, LOP, and shifter. Note that the slowest path goes through the adder

Table

4: a) Delay of the basic components of the LOP and b) Gate count of the LOP
buffer 3
2-input MUX 3
Pre-encoding F 6
Pre-encoding G p , G n 4
Detection tree 12
Shift correction 3
Adder
Coarse shifter 5
Fine shifter 5
Values obtained from [19]
a)
ELEMENT Gates
Pre-encoding F 650
Pre-encoding G p and G n 320
Detection tree 1000
Shift decoding
correction
(34 t nand ), whereas the path through the pre-encoding F and LOD tree has almost the
same delay, 33 t nand and the path through the detection tree has a lower delay. It has to
be pointed out that the concurrent correction is out of the critical path.
Hardware components
To evaluate the hardware complexity of the concurrent correction we include only the
components of the LOP. The estimation includes only the active components (gates) and
not the interconnections. Table 4b) summarizes the total count of logic gates for
bits.
The gate count of the pre-encoding logic F , G p and G n has been obtained from
the implementation shown in Figure 9. The count for the logic F includes all the gates,
except those gates that are exclusive to compute G p and G n . Therefore, for each bit we
consider that 12 gates are devoted to compute F and 6 to compute G p and G n .
As said before, the LOD and the detection tree are composed of dlog 2
being n the number of bits of the significands. The LOD has different modules for
each level of the tree. Thus, each module, except in the first level, is composed of an
gate and a 2-input multiplexer; however, the number of bits of the multiplexer
inputs depends on the level. For 54 bits, the total number of 2-input multiplexers is 49.
Modules in the first level do not have a multiplexer. The number of gates of each level
COARSE
SELECT.
ADDER
ADDER
c)
PRE-ENCOD.
ADDER
DETECT.
CORRECT.
CARRIES
PRE-ENCOD.
a)
LOD
and
COARSE
control lines
buffer
COMP.
COARSE
LOD
and
PRE-ENCOD.
LOD
and
CORRECT.
adder fine
buf.
detection tree
G
F buf.26LODcoarse5
dec.
shift
corr.
a)
adder
F buf.26LOD
coarse fine5
shift
comp.buf.
dec.
shift
adder fine
coarse
F6prefix tree7
finecarries
22 7corr. buf.
select carry
dec.
coarse
buf.
dec.
c)

Figure

13: General structure and critical path delay of a) LOP with concurrent correction
based on detection tree, b) LOP without concurrent correction and c) LOP with
concurrent correction based on carries checking.
of the detection tree has been derived from the implementation in Figure 11. We have
included also the gate count of the shift decoding an the shift correction.
5.2 Comparison
In this section we compare our LOP architecture with concurrent correction with two
other LOP alternatives: a LOP without concurrent correction and a LOP with a correction
scheme based on the utilization of the addition carries. We use the same estimates
of module delays and number of gates for all three schemes. Their main characteristics
are the following:
1. LOP without concurrent correction (Figure 13b)). This is an extension of the
one described in [19] to the case in which the output of the adder can be either
positive or negative. Since the LOD determines the position of the leading-one
within an error of one bit, a compensation shift is included once the normalization
has been performed. We have estimated the delay of the compensate shifter to be
of 2 t nand , in addition to the delay of the buffer required for the shift control. The
corresponding delay diagram is shown in Figure 13b).
2. LOP with concurrent correction based on carries (Figure 13c)). As discussed
in [4, 17], the error in the leading-one position can be detected by checking the carry
in the corresponding position. Therefore, for this scheme, the carries from the adder
have to be calculated explicitly and the corresponding carry selected according to
the output of the LOD. To accomplish this selection it is preferable that the LOD
output consist of a string of 1s followed by 0s. Therefore, the LOD is implemented
by a prefix tree and the carry selection is performed by a set of 2-input AND gates,
followed by an gate. Because of the characteristics of the LOD output, the
delay of the fine decoder is larger than in the other schemes; however, it is not in
the critical path. Note that the carry selection and shift correction can be done in
parallel with the coarse shifter. Because of this, it is convenient to reduce as much
as possible the delay of the fine shift. To accomplish this, as done in [4], the coarse
shifter is hexadecimal. Figure 13c) shows the corresponding timing diagram.

Table

5 summarizes the critical paths of the three schemes and shows that, with our
estimations, the LOP with concurrent correction presented here results in a reduction of
about 13%.
The estimation of the number of gates in the LOP of the two schemes we are
comparing with is given in Table 6. The total gate count for the three LOPs is summarized
in

Table

7. The LOP with concurrent correction presented here has the larger number of
gates: it almost doubles the gate count of the LOP without concurrent correction and it
is approximately 10% larger than the gate count of the LOP with concurrent correction

Table

5: Comparison of the critical path delay
LOP without LOP with concurrent
Our LOP concurrent correction correction based on carries
Critical path delay 34 t nand
Improvement 13 % 13 %

Table

Gate count for the a) LOP without concurrent correction and b) LOP with
concurrent correction based on carry checking
ELEMENT Gates
Pre-encoding F 650
Coarse shift decoding 40
Fine shift decoding 120
Compensate shift 160
a)
ELEMENT Gates
Pre-encoding F 650
Prefix Tree 1100
Carry selection 110
Coarse shift decoding 40
Fine shift decoding 120
correction
based on carry checking. However, this gate count is a small part of the number of gates
of the floating-point adder.
5.3 Actual implementations
To put in perspective the comparison estimations we have presented, we now briefly
summarize actual LOP implementations recently described in the literature.
In [19] the implementation of a floating-point adder using LOP without concurrent
correction is presented. It includes the compensate shifter after the normalization. The
floating-point adder was fabricated with 0:5 -m CMOS process technology with triple
metal interconnections. The main difference with respect to LOP without concurrent
correction we have described in section 5.2, comes from the fact that in [19] the result
of the subtraction is always positive so that the pre-encoding logic can be simplified.
The delay of the LOP is 8 ns and the time devoted to the compensate shifter is 1 ns.
Therefore, it can be concluded that by incorporating the concurrent correction based on
a detection tree and, consequently, eliminating the compensate shifter, the delay of the

Table

7: Gate count for concurrent correction
LOP Gates
LOP with detection tree 2260
LOP without concurrent correction 1200
LOP with carry checking 2050
LOP could be improved to 7 ns.
In [5, 9] the implementation of the IBM RS-6000 floating-point unit, with 1 -m
CMOS technology using triple-level metal, is described. It incorporates a floating-point
multiply-add-fused unit and uses a LOP with concurrent correction based on carry
checking. The LOD has been designed to accommodate the partial-decode scheme used
in the shifters. The normalization shift is accomplished in two stages: the first stage
produces a hexadecimal shift and the second stage a fine shift of (0,1,2,3).
The LOD calculates only the hexadecimal position of the leading-one, as a string of 1s
followed by 0s, and then it is necessary to decode the binary position of the leading-one.
This is the configuration we have used for this kind of LOP in the comparison.
The LOP design is detailed in [4]. The leading-one position anticipation is carried-out
digitwise. That is, the input data is processed in blocks of 4 bits and it provides a
shift signal for each block. Those shift signals constitute the coarse shift. To obtain the
shift signals a prefix tree is used. It receives as input the generate (G, both inputs are
1), propagate (P, only one input is 1) and zero (Z, both inputs are 0) signals, which are
also used for adder. The output of the tree specifies the leading-one position inside a
group of four bits. These signals are used both for the control of the shifters and for the
selection of the carries.
6 FLOATING-POINT ADDITION LATENCY REDUCTION
We now consider the effect of the proposed concurrent correction on the overall latency
of the floating-point addition. This depends on the delay of the other parts of this adder
and, in a pipelined implementation, on the processor cycle time. We consider separately
the effect on the single-datapath and on the double-datapath implementations.
Latency reduction in single-datapath floating-point adders

Figure

14a) shows the block diagram of a single-datapath floating-point adder using a
LOP without concurrent position correction [10, 13]. The adder has been pipelined into
five stages, as done in [19]. The significand addition is performed in a one's complement
SIGNIF. SIGNIF.
EXP. EXP.
STAGES
MUX MUX MUXexponent
difference
correction
concurrent
detection
concurrent
and
without
sign of
exp. diff.
exp. diff.
ADDER ADDER
(one's comp.) (one's comp.)
1-bit shift
MSB
1-bit shift
sign bit
MSB
bit invert.
MSB
sign bit
shift correct.
control
sign A
add/sub.
RIGHT
bit invert.
control
mux
a)
OUTPUT ALIGNER
INCR.
EXP.
COMPENSATION
control bit invert.
OUTPUT ALIGNER
mux

Figure

14: a) Single datapath floating-point adder without comparison (we have included
concurrent rounding). b) Reduced latency single datapath floating-point adder without
comparison (with concurrent rounding and LOP with concurrent correction)
form [5]. This way, if the result is negative the recomplementation consists in a bit
inversion. Alternatively, a compound adder could be used [2, 16].
The fourth stage perfoms the rounding and normalization of the adder result (note
that the inverters to recomplement the result are also included in this stage). As shown
in the Figure, these operations can be performed in two parallel paths [19], one for the
inversion and massive left shift and the other for the 1-bit shift and the rounding. This
is possible because
1. The value computed in the significand adder can be negative only whe the exponent
difference is zero. In this case, a full normalization left shift may be needed but no
rounding is required. Consequently, the bit inverters can operate in parallel with
the rounding logic.
2. On the other hand, for an exponent difference larger than zero two situations can
occur:
ffl The two most-significant bits of the adder result are zero. This can occur only
when the exponent difference is one (or zero, but this case has been analyzed
separately). A normalization by a left shift of more than one bit is needed and,
after that, the result is exact and no rounding is required. The mux selects
the output of the shift module as the addition result.
ffl At least one of the two most-significant bits of the adder result is one. This
situation can occurs for any exponent difference. Note that a normalized adder
result is included in this situation. The maximum normalization shift is one
and the normalized result will have to rounded. This limited normalization
shift is carried out in the 1-bit shift module and then, the mux selects the
output of the round module as result.
In the case of an effective addition, rounding is always required, but there is never
a normalization left shift. However, a significand overflow can occur needing a one bit
right-shift normalization. This right shift is also carried out in the 1-bit shift module in
the

Figure

.
The adder with the LOP with concurrent correction is similar except that the
compensation shifter and the exponent incrementer in the fifth stage are eliminated.
This might permit to merge the two last stages, as shown in Figure 14b). Note that this
merging might not be possible without the concurrent correction because of the delay of
the compensate shifter and the exponent incrementer.
A similar scheme and latency reduction is obtained for the single datapath floating-point
adder with comparison [6, 19]. In this case, a comparator is included in the second
stage to assure that, in the case of an effective subtraction, the smaller operand is subtracted
from the larger one and, therefore, the result is always positive. The latency
reduction obtained for this kind of adder is analyzed in [1].
and rounding
addition/subtraction0
SIGNIF.
EXP.
SIGNIF.
EXP.
exponent
difference
sign bit
LOP without
correction
concurrent
effective subtraction
and rounding
1-bit shift
MSB
MSB
FAR CLOSE
exp. diff.
effect. oper.
eff. add.
sign of
exp. diff.
control
add/sub.
sign A
control
shift
eff. sub.
ADDER
COMPOUND
(bit
1-bit shift
bit inverter
RIGHT
bit inverter
COMPOUND
ADDER
alignment
1-bit shift
EXP.
INCR.
control
mux
OUTPUT ALIGNER
EXP.
INCR. shift
Compensate

Figure

15: Latency of the double datapath floating-point adder
Latency reduction in double-datapath floating-point adders

Figure

15 shows an double-datapath architecture [11, 12]. In it, the FAR datapath
computes effective subtractions with exponent differences larger than one as well as all
effective additions. On the other hand, effective subtractions with an exponent difference
equal or smaller than one are computed in the CLOSE datapath. The pipelining of the
adder into four stages has been derived by transforming the pipelined single datapath
floating-point adder without comparison of Figure 14 and considering the components
delays specified in [19] and in Section 5.
In both paths the addition/subtraction is combined with the rounding in the compound
adder [2, 11, 16]. This adder computes A selects one of
these to perform the rounding. Moreover, in the CLOSE datapath it is used to perform
the two's complement of the result just by a bit-wise inversion. In [11, 16] an array of half
adders is included in the compound adder of the FAR datapath to compute A
required for the rounding to infinity when there is a significand overflow. However, [2]
describes a modification that replaces this array by a right shift of the operands by one
position for an effective addition. This way, the result can be either normalized or with
one leading zero, which is the same situation as for subtraction. Consequently, the rounding
is performed in the same way for both addition and subtraction. The shift of the
operands is implemented by the right shifter and by the parallel 1-bit shifter, so that this
modification reduces the delay, since it eliminates de array of half adders.
In the FAR datapath to assure a positive result of the adder, the smaller operand is
complemented for effective subtraction. In this way, the result conversion is eliminated.
Moreover, in that path no full-length normalization is required, since the maximum left
shift of the result is one bit.
With respect to the CLOSE datapath, in the case of equal exponents, the result
can be negative. But, as there is no alignment right shift, the result is exact and no
rounding is necessary. In the case of a exponent difference equal to one, the maximum
alignment shift is one bit, so no complete alignment shifter is required. On the other hand,
both cases may require a full-length normalization shift. Therefore, the LOP is needed
only in the CLOSE datapath. Note that, as in this datapath the effective operation is
always subtraction, bit inverters for the smaller operand have been included inside the
compound adder. Since in the case of an effective subtraction between operands with
equal exponents the result can be negative, the negative result has to converted to a sign-
and-magnitude representation. The converted result is formed by bit-inverting output
A +B of the compound adder. That is,
In this way, the result conversion is reduced to a bitwise inversion at the output of the
compound adder.
Since both the 1-bit alignment shift and the 1-bit normalization shift have a small
delay this implementation has a shorter critical path than the single datapath case of

Figure

14.
To determine the influence of the LOP with concurrent correction on the latency,
we analyze the total delay of the two paths using LOPs with and without concurrent
correction. We see that, as expected, the elimination of the compensation shifter in the
CLOSE datapath reduces the total delay of this path. Then, as described below, there
is some flexibility to pipeline the two paths into several stages, so that the latency is
reduced.
Considering the blocks in the CLOSE and in the FAR paths, we see that both paths
have almost the same modules:
SIGNIF.
EXP.
SIGNIF.
EXP.
exponent
difference
COMPOUND
ADDER
(four levels)
ADDER
COMPOUND
sign bit
MSB
exp. diff.
effect. oper.
control
mux
FAR CLOSE
sign of
exp. diff.
eff. sub.
concurrent
LOP and
detection
control
add/sub.
sign A
eff. add.
control
shift
shift corr.
(bit
1-bit shift
bit inverter
1-bit shift SHIFT
RIGHT
COMPOUND
ADDER
(two levels)
EXP.
INCR.
MUX 1-bit shift
OUTPUT ALIGNER
bit inverter

Figure

Double datapath floating-point adder with reduced latency
CLOSE. Exponent difference and operand swapping, 1-bit right shifter (alignment),
compound adder, bit inverter, normalization left shifter, compensate shifter, mux
and output aligner.
FAR. Exponent difference and operand swapping, alignment right shifter, bit in-
verter, compound adder, 1-bit left shifter(normalization), mux and output aligner.
Then, the only difference between the two datapaths is the Compensate shift in the
CLOSE datapath. Consequently, if concurrent correction is used and the Compensate
shift is eliminated, both paths have the same delay, allowing a pipelining into four stages
with a smaller stage delay. It might be even possible to obtain a three stage pipeline, as
shown in Figure 16.
7 CONCLUSIONS
We have presented a Leading-One Prediction (LOP) algorithm and its implementation
to obtain an exact prediction of the normalization shift in floating-point adders. The
prediction permits to reduce the delay of the adder since, as the LOP is operating in parallel
with the adder, the normalization shift is known before the result of the significand
addition. The LOP algorithm presented here is general since it can operate with adders
in which the result can be positive or negative.
The predicted leading one position can have an error of one bit. Our approach
includes the logic necessary to concurrently detect when the prediction will be wrong
and to correct the normalization shift. This permits the elimination of the compensation
shifter required in the adders with a LOP that does not includes concurrent shift correc-
tion. Although the concurrent correction increases the number of gates required for the
LOP, this increase should not be significant since the LOP is only a small portion of the
overall floating-point adder.
The detection and correction logic operates in parallel with the LOP and the significant
adder, and it does not introduce any additional delay to the adder. This improves
the performance with respect to LOPs with concurrent correction based on the checking
of the carries of the significand adder, where the logic necessary to carry out the checking
introduces an additional delay. We have estimated that the delay of the significant
addition and normalization shifter is reduced by approximately 13% using our LOP algorithm
with respect to both LOP without concurrent correction and LOP with concurrent
correction based on carry checking.
This improvement can be used to reduce the latency of a pipelined floating-point
adder. We have shown that the latency of a single data-path adder can be reduced from
five to four cycles while maintaining ' the same critical path delay. Similarly, the latency
of a double datapath floating-point adder can be reduced from four to three cycles.



--R


Rounding in Floating-Point Addition using a Compound Adder
UltraSparc: The Next Generation Superscalar 64-bit Sparc





Design of the IBM RISC System/6000 Floating-Point Execution Unit

The SNAP Project: Design of Floating-Point Arithmetic Units
A variable Latency Pipelined Floating-point Adder

An Algorithmic and Novel Design of a Leading Zero Detector Cir- cuit: Comparison with Logic Synthesis
Computer Architecture.
An Improved Algorithm for High-Speed Floating-Point Addition

Design and Implementation of the SNAP Floating Point Adder.

--TR

--CTR
R. V. K. Pillai , D. Al-Khalili , A. J. Al-Khalili , S. Y. A. Shah, A Low Power Approach to Floating Point Adder Design for DSP Applications, Journal of VLSI Signal Processing Systems, v.27 n.3, p.195-213, March 1, 2001
Chi Huang , Xinyu Wu , Jinmei Lai , Chengshou Sun , Gang Li, A design of high speed double precision floating point adder using macro modules, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
Khalid H. Abed , Raymond E. Siferd, CMOS VLSI Implementation of a Low-Power Logarithmic Converter, IEEE Transactions on Computers, v.52 n.11, p.1421-1433, November
leading-one prediction;floating-point addition;normalization