A Comparison of Three Rounding Algorithms for IEEE Floating-Point Multiplication.
AbstractA new IEEE compliant floating-point rounding algorithm for computing the rounded product from a carry-save representation of the product is presented. The new rounding algorithm is compared with the rounding algorithms of Yu and Zyner [26] and of Quach et al. [17]. For each rounding algorithm, a logical description and a block diagram is given, the correctness is proven, and the latency is analyzed. We conclude that the new rounding algorithm is the fastest rounding algorithm, provided that an injection (which depends only on the rounding mode and the sign) can be added in during the reduction of the partial products into a carry-save encoded digit string. In double precision format, the latency of the new rounding algorithm is $12$ logic levels compared to $14$ logic levels in the algorithm of Quach et al. and $16$ logic levels in the algorithm of Yu and Zyner.
Introduction
Every modern microprocessor includes a
oating-point multiplier that complies with the IEEE
754 Standard [13]. The latency of the FP multiplier is critical to the
oating-point performance
since a large portion of the FP instructions consists of FP multiplications. For example, Oberman
reports that FP multiplications account for 37% percent of the FP instructions in benchmark
applications [17].
A lot of research has been devoted to optimizing the latency of adding the partial products to
produce the product, e.g. [1, 2, 6, 9, 15, 16, 18, 19, 20, 21, 26, 28, 29, 30]. More recently, work on
rounding the product according to the IEEE 754 Standard has been published [4, 7, 10, 22, 23, 24,
25, 31, 33, 34]. Assuming that the multiplier outputs a carry-save encoded digit string representing
the exact product, the following natural question arises: What is the fastest method to compute
the rounded product given the exact product represented by carry-save encoded digit string?
We consider and compare three rounding algorithms: (a) the algorithm of Quach et al. [23],
which we denote by the QTF algorithm; (b) the algorithm of Yu and Zyner [31], which we denote
by the YZ algorithm; and (c) a new algorithm that is based on injection based rounding [10],
which we denote by the ES algorithm. We provide block diagrams of these rounding algorithms,
optimized for speed. We measure the latency of the algorithms in logic levels to enable technology
independent comparisons. The main building blocks of these algorithms are similar, and consist of
a compound adder and the computation of a sticky and carry bits. Thus, the costs of the three
algorithms are similar, and the interesting question is nding the fastest algorithm.
We focus on double precision multiplication in which each signicand is represented by 53
bits. The algorithms assume that the signicands are normalized, namely, in the range [1; 2), and
therefore, their product is in the range [1; 4). We do not consider the cases that deal with denormal
or special values since supporting denormal values can be obtained by using an extended exponent
range [14, 25, 32] and the computation on special values can be done in parallel [12]. The three
algorithms share the following techniques:
1. The product represented by a carry-save encoded digit string of 106 digits in the case of double
precision is partitioned into a lower part and an upper part. The upper part is added by a
compound adder that computes the binary representations of sum and sum+ ulp, where ulp
denotes a unit in the last position, and sum denotes the sum of the upper part. A carry-bit,
a round-bit, and a sticky-bit is computed from the lower part.
2. The rounding decision is computed in two paths: the non-over
ow path works under the
assumption that the exact product is in the range [1; 2), and over
ow path works under the
assumption that the product is in the range [2; 4). Although the sum of the upper part,
denoted by sum, does not equal the exact product, the most signicant bit of sum controls
the selection between these two paths.
The main dierences between the three rounding algorithms are outlined, as follows.
1. The rounding decision. The QTF and ES algorithms simplify the rounding decision by an
early addition of a value (this value is called the prediction in the QTF algorithm and the
injection in the ES algorithm). In the QTF algorithm, the prediction depends on the rounding
mode and on the carry-save digit positioned 53 digits to the right of the radix point. In the
ES algorithm, the injection depends only on the rounding mode and we assume that it is
added in with the partial products, and thus the product already includes the injection. The
rounding decision in the YZ algorithm is based on customary rounding tables.
2. The position in which the carry-save encoded product is partitioned into a lower part and an
upper part diers in the three algorithms. In the YZ algorithm the lower and upper parts are
separated by a \buer" of three carry-save digits in positions [51 : 53], where the position of a
digit denotes how many digits it is to the right of the radix point. In the other two algorithms
the upper part consists of positions and the lower part consists of position [53 : 104].
The latencies of the proposed designs that implement these algorithms in terms of logic levels are
the following: The latency of the ES algorithm is 12 logic levels, the latency of the QTF algorithm
is 14 logic levels, and the latency of the YZ algorithm is 16. Note that we modied and adapted
the QTF and YZ algorithms for minimum latency.
Supporting all four rounding modes of the IEEE 754 Standard is an error prone task. We
therefore provide correctness proofs of all three algorithms which formalize and clarify the tricky
aspects. From this point of view, the YZ algorithm is easiest to prove and the QTF algorithm is
the most intricate (especially the rounding decision logic).
The paper is organized as follows. In Section 2, preliminary issues are described, such as:
notation, conventions we use regarding IEEE rounding, and the general setting. In Section 3, a
straightforward rounding algorithm is reviewed. This algorithm is described to provide an outline
the task of rounding after the exact product is computed. It does not attempt to parallelize the
task of rounding, and therefore, has a long latency. In Sections 4-6, each rounding algorithm is
described, proven, and analyzed. In Section 7, we discuss how the latencies of the algorithms
increase as the precision is increased. In Section 8, a summary and conclusion is given. Due to
space limitations some of the sections are omitted and can be found in the full version [11].
Preliminaries
Notation Let x i x binary string. By we denote the binary
string x z1 x z 1 +1    x z 2
. We also sometimes refer to x i as x[i]. Since we deal with fractions, we index
binary encoded bit strings by x so that x i is associated with the weight 2 i . The value
encoded by x[z denoted by jx[z
IEEE rounding The IEEE-754-1985 Standard denes four rounding modes: round toward 0,
round toward +1, round toward 1, and round to nearest (even). Based on the sign of the
number the rounding modes round toward +1 and round toward 1 can be reduced to the
rounding modes RZ (round to zero) and RI (round to innity) [23]. Thus leaving only three
rounding modes: RI, RZ, and RNE (round to nearest - even).
Furthermore, Quach et al. [23] suggested to implement RNE by round to nearest (up), denoted
by RNU. The rounding mode RNU is dened as follows. If x is between two successive representable
r RNU
The reason that RNE can be implemented by RNU is that r RNU (x) 6= r RNE (x)
and the least signicant bit (LSB) of the binary encoding of y 2 is 1. Therefore, obtaining r RNE (x)
from r RNU (x) can be accomplished by \pulling down" the LSB, when
For the sake of clarity, we dene rounding to zero (RZ) of signicands in the range [1; 4) in
double precision. Note, that this denition excludes the post-normalization shift that takes place
when the number is in the binade [2; 4).
Denition 1 Let x 2 [1; 4), then r RZ (x) is dened by
r RZ
where x div 2 ' is the integer q that satises:
General setting In this paper we consider a double precision multiplier. We assume that the
signicands are prenormalized, namely, that the values of the two signicands are in the range
[1; 2) and that each signicand is represented by a binary string with bits in positions [0 : 52]. The
exact product of the two signicands is in the range [1; 4) and is encoded by a binary string with
bits in positions (Note that the weight of the bit in position [ 1] is 2). For the sake of
simplicity, we ignore the exponent and sign-bit paths.
Floating point multipliers perform the computation in two phases. In the rst phase, an addition
tree reduces the partial products to a carry-save encoded digit string that represents the exact
product. In the second phase, a binary string representing the rounded product is computed from
the carry-save encoded string. This paper discusses implementations of the second phase.
3 Naive IEEE rounding
In this section we review a simple but slow IEEE compliant algorithm for rounding after multiplication
[5].
3.1 Description
The input consists of two binary strings sum and carry each having 106 bits which are indexed
from 1 to 104. The sum of the binary numbers represented by sum and carry equals the exact
product exact 2 [1; 4).
Rounding is computed as follows (the computation of the exponent string is omitted):
1. Reduce the rounding mode to one of three rounding modes based one the sign of the product.
2. 2:1-compression. The sum and carry strings are added to obtain a single binary string
namely Note that since the exact product is in the range
[1; 4), the the most signicant bit of X is in position [ 1].
3. Normalization. If jXj  2, then jX jXj. This is implemented by
a conditional shift by at most one position to the right. Note that X 0 is indexed from 0 to
4. Compute sticky. The sticky-bit equals
5. Compute rounding decision. The rounding decision rd 2 f0; 1g is based on the rounding
mode, the bits: and the sticky-bit. Note that the rounding mode at
this stage already incorporates the sign.
6. Increment. Compute be the binary string that represents
the sum.
7. Post-normalize. If jY
The signicand string of the rounded product is given by Y 0 .
3.2 Delay analysis
The latency of steps 1, 3, and 5 of the naive rounding procedure is at least logarithmic in the
length of the binary strings sum and carry. The other steps require only constant delay. If every
pipeline stage can accommodate at most one logarithmic depth circuit, then an implementation of
the naive rounding procedure requires at least 3 pipeline stages.
4 The ES rounding algorithm
In this section we review injection based rounding [10], and present an implementation for double
precision that requires (under assumptions specied in Sec. 4.5) only 12 logic levels.
4.1 Injection based rounding
Rounding by injection reduces the rounding modes RI and RNU to RZ [10]. The reduction is based
on adding an injection that depends only on the rounding mode, as follows:
The eect of adding injection is summarized in the following equation:
where mode 2 fRZ;RNU;RIg.

Figure

1 depicts the reduction of RNU and RI to RZ by injection assuming that the number to
be rounded is in the range [1; 2).
If the exact product, denoted by exact, is in the range [2; 4), then the injection must be xed
in order to make the reduction to RZ correct. The correction amount, denoted by inj correct,
is dened by
Therefore, if X is in the range [2; 4) the eect of adding the injection and the correction amount is
summarized in the following equation:
where mode 2 fRZ;RNU;RIg.
Our assumption is that injection is added in the multiplier adder array, and therefore
This completes the description of injection based rounding for numbers in the range [1; 4).
4.2 The rounding algorithm
In this section we present the new ES algorithm for rounding in
oating-point multiplication that
is based on injection based rounding.

Figure

2 depicts a block diagram of the ES rounding algorithm. The rounding algorithm works
under the assumption that the sum and carry-strings already include the injection (but not the
injection correction) and proceeds as follows:
1. The sum and carry-strings are divided into a high part and a low part. The high part
consists of positions and the low part consists of positions [53 : 104].
2. The low part is input to the box that computes the carry, round and sticky-bits, dened as
follows:
where  52     104 is the binary string that satises:
3. The higher part is input to a line of Half Adders and produces the output (X sum
and Note that the bit LX is in position 52, and that no carry is generated
to position 2, because the exact product is less than 4 (even after adding the injection).
4. are input to the Compound Adder, that outputs the sum
and the incremented sum jY
5. The Increment Decision box receives the round-bit (R), the carry-bit (C[52]), the LSB (LX ),
the MSB (Y 0[ 1]) and the rounding modes (RN , RI). The output signal inc indicates
whether Y 0 or Y 1 is to be selected.
6. The most signicant bits Y 0[ 1] and Y 1[ 1] indicate whether Y 0 and Y 1 are in the range
[2; 4). Depending on these bits, Y 0 and Y 1 are normalized as follows:
shif t right(Y
shif t right(Y
7. The rounded result (except for the least signicant bit) is selected between Z0 and Z1 according
to the increment decision inc, as follows:
8. In case the rounding mode is RNE, the least signicant bit needs to be corrected since RNE
and RNU do not always result with the same least signicant bit. The correction of the least
signicant bit is computed by two parallel paths; one path working under the assumption that
the rounded result over
ows (i.e. greater than or equal to 2), and the other path working
under the assumption that the rounded result does not over
ow.
The path that computes the correction of the LSB under the \no-over
ow" assumption is
implemented by the box called \x L (novf)". The inputs of the \x L (novf)" box are the
round bit R, the sticky bit S, and a signal RNE indicating whether the rounding mode is
round to nearest even. When the output, denoted by not(pd), equals zero the LSB should be
pulled down.
The path that computes the correction of the LSB under the \over
ow" assumption is implemented
by the box called \x L (ovf)". The inputs of the \x L (ovf)" box are the LX bit,
the carry-bit C[52], the round bit R, the sticky bit S, and the signal RNE. When the output,
denoted by not(pd'), equals zero the LSB should be pulled down.
Note that the pull down signals are inactive if the rounding mode is not RNE.
9. The least signicant bit of the rounded result before xing the LSB (in case of a discrepancy
between RNE and RNU) equals one of three values:
(a) if the rounded result does not over
ow, then the LSB equals LX  C[52];
(b) if the rounded result over
ows and the increment decision is not to increment, then the
(c) if the rounded result over
ows and the increment decision is to increment, then the LSB
The xing of the LSB is implemented by combining (using AND-gates) the pull-down signals
with the corresponding candidates for the LSB signals.
The outputs of the 3 AND-gates are denoted by: L 0 (inc), L 0 (ninc), and L(inc). For the sake
of clarity, we introduce the signal L(ninc), which equals L(inc).
10. The LSB of the rounded result equals L(ninc) if no over
ow occurred and no increment took
place. The LSB of the rounded result equals L(inc) if no over
ow occurred and an increment
took place. The LSB of the rounded result equals L 0 (ninc) if an over
ow occurred and no
increment took place. The LSB of the rounded result equals L 0 (inc) if an over
ow occurred
and an increment took place.
According to the 4 cases, the LSB of the rounded result is selected depending on the over
ow
signals and the increment decision
4.3 Details
In this section we describe the functionality of three boxes in gure 2, that have not been fully
described yet.
Fix L (novf). This box belongs to the path that assumes that the product is in the range [1; 2).
Recall that there might be a discrepancy between RNE and RNU when a tie occurs, namely, when
the exact product equals the midpoint between two successive representable numbers. Let exact
denote the value of the exact product, the \Fix L (novf)" generates a signal not(pd) that satises:
exact 2 [1; occurs and RNE)
When a tie occurs there are two possibilities: (a) If RNU and RNE agree, then both yield a rounded
result with a LSB equal to zero. Pulling down the LSB in this case is not required, but causes no
damage. (b) If RNU and RNE disagree, then the LSB of the RNU result must be pulled down.
Without the addition of the injection, a tie occurs when an injection
of 2 53 is already included, a tie occurs when Therefore the not(pd) signal is
dened by:
Fix L' (ovf). This box belongs to the path that assumes that the product is in the range [2; 4).
The \Fix L' (ovf)" generates a signal not(pd') that satises:
exact 2 [2; occurs and RNE)
The dierence between not(pd') and not(pd) is that not(pd') is used under the assumption that the
product is greater than or equal to 2. Without the addition of the injection, a tie occurs (in case of
over
ow) when LX an injection of 2 53 is already included, a
tie occurs when LX  Therefore the not(pd') signal is dened by:
Increment Decision. The increment decision box has two paths, depending on whether an
over
ow occurs. The path working under the assumption that no over
ow occurs (i.e. Y 0[
produces an increment decision, if LX 2. The path working under the assumption that an
over
ow occurs (i.e. Y 0[ needs to take into account the correction of the injection, denoted
by inj correct. It produces an increment decision, if LX 2.
Therefore the inc signal is dened by:
4.4 Correctness proof
The tricky part in our algorithm is the correctness of the inc signal. As long as the bit Y 0[ 1]
indicates correctly whether the exact product is greater than or equal to 2, Equations (1) and (2)
imply that the inc signal is correct. But one should also consider the cases that Y 0[ 1] fails to
indicate correctly the binade of the exact product. Namely: (a) Y 0[ and the exact product
is greater than or equal to 2; and (b) Y 0[ and the exact product (without the injection) is
less than 2.
The source of such errors is due to the fact that jY does not always equal the the 53
most-signicant bits of the exact product. Recall that
The lower part of the product (corresponding to positions [53 : 104] in the registers sum and
carry) as well as LX do not eect the value of Y 0[ 1]. However, the injection might have an
eect on Y 0[ 1] since it is added-in in the multiplier array, depending on how the multiplier array
is implemented (Wallace tree, etc.
The following claim shows that when such mismatches occur, the rounded product equals 2.
Moreover, in these cases both paths: the one working under the assumption that no over
ow occurs,
and the one working under the assumption that over
ow occurs, yield the result 2. Therefore,
correct rounding is obtained even when Y 0[ 1] fails to indicate correctly the binade of the exact
product.
exact denote the exact product, and let sum and carry satisfy jsumj
exact injection. Then correct rounding of exact can be computed as follows:
r mode
r RZ (exact
r RZ (exact
Proof: We consider two main cases: (a) Y 0[
(a) Suppose Y 0[ exact < 2 then the claim follows from Eq. (1). If exact  2, then
exact
. The reason for this is the possible contribution of LX  2 52 2 f0; 2 52 g and
have Therefore,
exact
The correction of the injection satises 0  inj correct  2 52 , therefore:
exact
According to Eq. (2), in this case r mode
However, in this case
r RZ (exact
because rounding to zero maps both intervals: 2.
(b) Suppose Y 0[ exact  2 then the claim follows from Eq. (2). If exact < 2, then
since injection 2 [0; 2 52 ), it follows that
exact
The proof now follows the proof in case (a). 2
proves that Y 0[ 1] can be used for controlling the selection of the right rounded result.
The following claim proves that our implementation of the computation of r mode (exact) is correct.
Note, that the claim does not deal with xing the LSB to obtain RNE from RNU.
r RZ (exact
2. If Y 0[
r RZ (exact
exact
where tail 2 [0; 2 52 ). This implies that
r RZ (exact
The inc signal in this case equals 1 i the addition of LX and C[52] generates a carry to position
51. If inc = 0, then simple addition takes place:
r RZ (exact
If inc = 1, there are two cases: in the rst case, the increment does not cause an over
ow, and
again simple addition takes place. If an over
ow is caused, then since only 53 bits are output, the
bit L x  C[52] is discarded. This completes the proof of the rst part of the lemma.
Suppose Y 0[
Therefore,
exact
This implies that
r RZ (exact
and the lemma follows. 2
4.5 Delay analysis
In the section we present a delay analysis of the rounding algorithm depicted in Fig. 3. Our analysis
is based on the following assumptions:
1. Consider a carry look-ahead adder, and let dCLA denote the delay of the 53-bit adder measured
in logic levels. We assume, that the MSB of the sum has a delay of at most dCLA 1 logic
levels. This assumption is easy to satisfy if the carry look-ahead adder of Brent and Kung
is used [3]. Otherwise, satisfying this assumption may require arranging the parallel-prex
network so that the MSB is ready one logic level earlier.
2. The compound adder is implemented so that the delay of the sum is dCLA and the delay of
the incremented sum is dCLA + 1. This can be obtained by oring the carry-generate and
carry-propagate signals [27, Lemma 1].
3. Consider the box in which the carry, round and sticky bits are computed. According to the
rst assumption, since the widths of this box and the compound adder are similar, the delay
of the carry bit is dCLA 1 logic levels and the delay of the round bit is dCLA logic levels.
The delay of the sticky bit is estimated to be dCLA 2 logic levels, based on the fast sticky
bit computation presented in [31].
4. We assume that the delay associated with buering a fan-out of 53 is one logic level.

Figure

3 depicts the block diagram of the injection based rounding algorithm annotated with
timing estimates. We assigned dCLA the value of 8 logic levels. This implies that the sticky bit is
valid after 6 logic levels, the carry-bit C[52] is valid after 7 logic levels, and the round-bit is valid
after 8 logic levels. Similarly, the sum Y 0 is valid after 9 logic levels, the MSB Y 0[ 1] is valid after
8 logic levels, the incremented sum Y 1 is valid after 10 logic levels, and the MSB Y 1[ 1] is valid
after 9 logic levels.

Figure

4 depicts implementations of the Fix L (novf), Fix L' (ovf), and Increment Decision
boxes annotated with timing estimates. These timing estimates are used in Fig. 3 to obtain the
estimated delay of 12 logic levels for the rounded product.
5 The YZ rounding algorithm
In this section we review and analyze the rounding algorithm of Yu and Zyner, which was reported
to have been implemented in the ULTRASparc RISC microprocessor [31]. We refer to this algorithm
as the YZ rounding algorithm.
5.1 Description

Figure

5 depicts a block diagram of the YZ rounding algorithm. This description diers from the
description in [31] in two ways:
1. In [31] the sum output by the 3-bit adder has only three bits. We believe that this is a
mistake, and that the sum should have four bits (we denote this sum by Z[50 : 53]).
2. The sum and the incremented sum in [31] is fed to a 4 : 1-mux, which selects one of them
either shifted to the right or not. We propose to normalize the sum and the incremented
sum before the selection takes place. This early normalization helps reduce the delay of the
rounding circuit at the cost of two shifters rather than one.
The algorithm is described below:
1. The sum and carry-strings are divided into a high part and a low part. The high parts
consist of positions and the low parts consist of positions [54 : 104].
2. The low part is input to the box that computes the carry and sticky bits, dened as follows:
where  53     104 is the binary string that satises:
3. The higher part is input to a line of Half Adders and produces the output X sum
Note that no carry is generated to position [ 2], because the exact product
is less than 4.
4. The high part X sum divided into two parts. Positions
are fed into the Compound Adder, that outputs the sum Y and the incremented
sum jY are added with the carry bit
C[53] to produce the sum Z[50 : 53].
5. The processing of Z[50 : 53] is split into two paths; one working under the assumption that
the rounded product will not over
ow (i.e. less than 2), and the other path working under
the assumption that the rounded product will over
ow.
The no-over
ow path computes a rounding decision, rd[52], in the round dec. (novf) box.
The rounding decision rd[52] is added with Z[50 : 52] in the -novf box to produce the sum
In Claim 3 we prove that this 3 bit addition does not produce a carry bit
in position 49. The sum Z novf [50 : 52] has two roles: positions are the result bits
in positions [51 : 52] if no over
ow occurs, and position [50] is used to detect if a carry is
generated in position [50] if no over
ow occurs. The bit Z novf [50] decides whether the upper
or the incremented sum Y 1[0 : 50] should be selected in the no-over
ow case.
The over
ow path computes a rounding decision, rd 0 [51], in the round dec. (ovf) box. The
rounding decision rd 0 [51] is added with Z[50 : 51] in the -ovf box to produce the sum
In Claim 3 we prove that this 2 bit addition does not produce a carry bit
in position 49. The sum Z ovf [50 : 51] has two roles: position [51] serves as the result bit
in position [52] if over
ow occurs, and position [50] is used to decide whether an increment
should take place in the upper part
6. The decision which path should be chosen is made by the select decision box. First, an
over
ow signal ovf is computed as follows:
The over
ow signal ovf determines whether Z ovf [50] or Z novf [50] is chosen as the carry-bit
that eects position [50], and therefore, determines the increment decision inc:
Z ovf [50] if
Z novf [50] if
7. The two least signicand bits of the rounded product are computed as follows:
If no over
ow occurs
Therefore the lower mux selects these bits for result[51 : 52] when
If an over
ow occurs [51]. The bit result[51] depends on
whether an increment takes place or not:
Y 0[50] if inc = 0:
Note that inc = Z ovf [50] if ovf = 1. Since the signal Z ovf [50] is ready earlier than inc, we
use Z ovf [50] to control the selection:
Y 1[50] if Z ovf
Y 0[50] if Z ovf
The selection between Y 1[50] and Y 0[50] is done by the sel multiplexer in Fig. 5.
8. The most signicant bits Y 0[ 1] and Y 0[ 1] indicate whether Y 0 and Y 1 are in the range
[2; 4). Depending on these bits, Y 0 and Y 1 are normalized as follows:
shif t right(Y
shif t right(Y
9. The rounded result (except for the least signicant bit) is selected between Z0 and Z1 according
to the increment decision inc signal, as follows:
5.2 Correctness
In this section we provide a proof that adding the rounding decision does not generate a carry-bit
in position 49. This claim applies both to the no-over
ow path and to the over
ow path.
denote the sum that is output by the 3-bit adder as depicted in Fig. 5. Let
rd[52] denote the rounding decision for the no-over
ow path, and let rd 0 [51] denote the rounding
decision for the over
ow path. Then,
Proof: The partial compression [8] caused by the half-adder line implies that
(jX sum
This follows by the fact that X sum [i] and X carry [i cannot be both equal to one. Adding C[53]
increases the above range by 2 4 , yielding that
The contribution of rd 0 [51]  2 2 is in the range [0; 4=16], and therefore, Eq. 13 follows. The
contribution of rd[52]  2 3 is in the range [0; 2=16], and therefore, Eq. 14 follows. 2
5.3 Delay analysis

Figure

6 depicts the YZ rounding algorithm annotated with timing estimates. We use the same
assumptions on the delays of signals that are used in Sec. 4.5. We argue that at least 16 logic levels
are required. The path in which the sum and incremented sum are computed does not lie on the
critical path. The critical path consists of the carry-bit computation, the 3-bit adder, the round
dec. (novf) box, the -novf box, the select decision box, a driver, and the upper mux.
We considered the following optimizations to minimize delay for a lower bound on the required
number of logic levels:
1. The 3-bit adder is implemented by conditional sum adder; the late carry-in bit C[53] selects
between the sum and the incremented sum. This is a fast implementation because the bits
of X carry and X sum are valid after one logic level and the carry-bit C[53] is valid after 7 logic
levels.
2. The rounding decision boxes are implemented by cascading two levels of multiplexers that are
controlled by Z[52 : 53] in the no-over
ow path and by by Z[51 : 52] in the over
ow path. In
the over
ow path, Z[53] is combined with sticky-bit, and hence the rounding decision required
3 logic levels. In the no-over
ow path, only 2 logic levels are required.
3. The addition of the rounding decision bit required only one logic level using a conditional
sum adder.
4. The inc signal is valid after 3 more logic levels, due to the need to compute the signal ovf in
two logic levels (see Eq. 11), and one selection according to Eq. 12.
5. The inc signal passes through a driver due to the large fanout. This driver incurs a delay of
one logic level, and controls the upper mux to output the result after 16 logic levels.
6 The QTF rounding algorithm
Quach et al. [23] presented methods for IEEE compliant rounding. Their technique is a generalization
of the rounding algorithm of Santoro et al. [24]. In this section we present a rounding
algorithm that is based on the method of Quach et al. while aiming for minimum delay.
Apart from reducing the rounding modes to RZ;RNU and RI, the key idea used in the methods
of Quach et al. and Santoro et al. is to inject a prediction bit that is based on the rounding mode
and the values of sum[53] and carry[53]. The injection of the prediction bit reduces the number
of possibilities of the rounded result.
In this section we deviate from Quach et al. [23] in the following points:
1. The presentation in the paper of Quach et al. is separated according to the rounding mode.
Since we are investigating rounding algorithms that support all the rounding modes, we
integrated the rounding modes into one algorithm.
2. Quach et al. suggest several options for the choice of the prediction logic in RNU. Only one
possibility was suggested in modes RZ and RI. Since the prediction logic lies on the critical
path, we chose to simplify the prediction logic as much as possible by dening:
pred
3. Quach et al. separate the rounding decision and the compound adder. They use a 3-way
compound adder that computes sum; sum 2. The correct sum is selected by
the control logic. We are interested in a faster design, and therefore, we break the 3-way
adder into a Half-Adder line, a 2-way compound adder, and a mux. The control logic uses
an output of the 2-way compound adder, and the LSB (in case of no over
ow) is generated
by the control logic as well as the increment decision.
6.1 Description

Figure

7 depicts a block diagram of a rounding algorithm that we suggest based on Quach et al. [23].
There are many similarities between the rounding algorithm based on injection rounding and the
rounding algorithm based on Quach et al., so we point out the dierences and the new notations.
Before being input to the compound adder, the high part of the sum and carry pass through
two lines of Half-Adders. The rst line makes room for the prediction bit. The second pass enables
separating the bit LX 0 in position [52] (this is, in fact, part of a 3-way compound adder). The
increment decision has two paths: one for over
ow and the other for no-over
ow. The MSB Y 0[ 1]
selects which path outputs the increment decision inc. In addition the increment decision computes
the LSB (before xing for RNE) in case an over
ow does not occur.
6.2 Details
In this section we describe the details of the increment decision box and the LSB-x for RNE box.
Increment decision box. The outputs of the increment decision box are the increment decision
inc and the bit L that equals the LSB of the rounded product before xing in case no over
ow
occurs. The increment decision is partitioned into two paths. One for the case that an over
ow
occurs which computes the signal inc ovf , and the other path for the case that no over
ow occurs
which computes the signal incnovf . The following equations dene the signals inc ovf ; inc novf , and
inc.
inc
(R
pred
pred
inc
(S _ R _ pred
pred
The output inc equals inc novf or inc ovf bit according to bit Y 0[ 1].
inc novf if Y 0[
inc ovf if Y 0[
The bit L, which equals the LSB of the rounded product (before xing) in case no over
ow
occurs, is dened by:
R  LX 0  C[52] if RNU
pred if RI
Note that the case of RI is complicated due to the possibility that pred 6= C[52]. If pred = C[52],
then pred 6= C[52], the the eect of the wrong prediction is reversed by
pred  C[52].
LSB-x for RNE. The LSB-x for RNE box outputs two signals: not(pd) is used to pull-down
the LSB if a \tie" occurs, but no over
ow occurs, and not(pd 0 ) is used to pull-down the LSB if a
\tie" and an over
ow occur. These signals are dened as follows:
In contrast to injection based rounding no injection or prediction is contained in the LX 0 , R
and S-bit computation in RNE. If no over
ow occurs, a \tie" occurs 0, in which
case the LSB should be pulled down for RNE. Therefore,
If over
ow occurs, a \tie" occurs i which case the LSB
should be pulled down for RNE. Therefore,
6.3 Correctness
In this section we prove the correctness of the selection signal inc. The proof is divided into two
parts. In the rst part, we assume that Y 0[ the exact product is in the range [2; 4). In
the second part, we prove that even if the Y 0[ 1] signals over
ow incorrectly, then the selection
signal inc is still correct.
correctly whether the exact product is in the range [2; 4).
Then the inc signal signals correctly whether an increment is required for rounding.
Proof: We consider separately the cases of over
ow and no over
ow. For each case we consider
the three possible rounding modes. The question which we address is whether the rounding decision
in conjunction with the compression of the lower part of the carry-save representation produces a
carry into position 51. The inc signal should be 1 i a carry is generated into position 51.
Suppose no over
ow occurs, namely Y 0[
1. In rounding mode RZ, only truncation takes place, and therefore, a carry into position 51 is
generated 2.
2. In rounding mode RNU, the rounding decision is to increment (in position 52) if the round-bit
equals 1. This increment generates a carry to position 52, and hence, a carry is generated
into position 51 2.
3. In rounding mode RI, the rounding decision is to increment (in position 52) if
One needs to take into account the prediction that was already added to the product. We
consider two sub-cases:
(a) If pred, then the contributions of pred and C[52] cancel out, and therefore,
C[52] should be ignored. The rounding decision generates a carry into position 51 i
(R
(b) If C[52] 6= pred, then this implies that Therefore, the
rounding decision without the prediction would have been to increment in position 52.
pred = 1, this increment already took place, and an additional carry should not
be generated into position 51.
Suppose that over
ow occurs, namely, Y 0[
1. In rounding mode RZ, since only truncation takes place, this case is identical to the case of
no over
ow.
2. In rounding mode RNU, the rounding decision is determined by the bit in position 52 which
Therefore, there are two cases: either a carry is generated into position
51 since LX 0 or a carry is generated into position 51 by the rounding decision.
Combining these cases implies that a carry is generated into position 51 i
3. In rounding mode RI, we consider two cases: (i) If pred, then we may ignore C[52]
and the prediction since their contributions cancel out. In this case, the rounding decision is
to increment i or (L X pred, then
We consider two sub-cases:
(a) If LX then the eect of the prediction was restricted to changing LX 0 from 0 to 1.
Therefore, the rounding decision is based on R _ S. Since the rounding decision
is to increment.
(b) If LX then the eect of the prediction was to generate a carry into position 51 in
the second half-adder line and to change LX 0 from 1 to 0. This means that without the
prediction, LX 0 would have been equal to 1, which implies that the rounding decision
would have been to increment. Since an increment already took place, an additional
increment is not required.The selection between inc ovf and inc novf is controlled by Y 0[ 1], although Y 0[ 1] might not
signal correctly the case of over
ow. The following claim shows that when Y 0[ 1] does not signal
over
ow correctly, both choices are equal, and hence, the inc signal is correct.
does not signal an over
ow correctly, namely, Y 0[
exact < 2, or Y 0[ exact  2. Then, inc inc novf .
Proof: The proof is divided into two cases:
1. Y 0[ exact < 2. This case can only occur when pred
Therefore, it is restricted to rounding mode RI. Since
pred  2 52
it follows that LX This implies that in this case inc ovf = inc novf , as required.
2. Y 0[ exact  2. This discrepancy can only occur if
Therefore,
is smaller than 2 and a multiple of 2 52 , it follows that
This implies that LX 1. Consider the three rounding modes: In RZ, inc inc novf . In
RI, if excluding the possibility of this case. In RNU, since
and and the claim follows.6.4 Delay analysis

Figure

8 depicts the rounding algorithm based on Quach et al. [23] with delay annotation. The delay
assumptions that are used here are similar to those used in the two previous rounding algorithms.
The rounding algorithm depicted in Fig. 8 uses a prediction logic which lies on the critical path.
The delay of the prediction logic is two logic levels.
Following Quach et al., Fig. 8 depicts a non-optimized processing order in which the post-
normalization shift takes place after the round selection. The increment decision box is assumed
to be organized as follows: The bits S, C[52], R and Y 0[ 1] are valid after 6; 7; 8; 10 logic levels,
respectively. To minimize delay we implement the rounding equations by 4 levels of multiplexers,
so that the results can be selected conditionally the signals as they arrive. Thus, a total delay of 15
logic levels is obtained. By performing post-normalization before the round selection takes place,
one logic level can be saved to obtain a total delay of 14 logic levels.
7 Higher Precisions
How do these rounding algorithms scale when higher precisions are used? One can see that the
parts in the presented rounding algorithms that depend on the length of the signicands are:
the half-adders, the compound adder, the sticky, round, and carry-bit computation, the selection
multiplexers, and the drivers for amplifying the signals that control the wide multiplexers.
When precision is increased, the widths of upper and lower parts of the carry and save strings
grow, but they still stay almost equal to each other. This implies that our assumptions on the
relative delay of the carry-bit computation and the compound adder do not need to be changed.
Moreover, it is expected that as precision grows, the gap between the delay of computing the
carry-bit and the sticky-bit grows, so that the sticky-bit computation will not lie on the critical
path. This implies that a rst order estimate (ignoring additional delay due to increased fanout
and interconnection length) of the delays of the rounding algorithms for precision p can be stated
as follows:
1. The delay of the injection based rounding algorithm is 4 logic levels plus the delay of the sum
computation of the p-bit compound adder dCLA (p).
2. The delay of the YZ rounding algorithm is 8
3. The delay of the rounding algorithm based on Quach et al.[23] with the optimization (in
which the post-normalization takes place before the selection) is 6 levels.
8 Summary and Conclusions
A new IEEE compliant
oating-point rounding algorithm for computing the rounded product from a
carry-save representation of the product is presented. The new rounding algorithm is compared with
two previous rounding algorithms. To make the comparison as relevant as possible, we considered
optimizations of the previous algorithms which improve the delay. For each rounding algorithm,
a logical description and a block diagram is given, the correctness is proven, and the latency is
analyzed.
Our conclusion is that the new ES rounding algorithm is the fastest rounding algorithm, provided
that an injection is added in during the reduction of the partial products into a carry-save
encoded digit string. With the ES algorithm the rounded product can be computed in 12 logic
levels in double precision (i.e. when the signicands are 53 bits long). In \precision independent"
terms, the critical path consists of a compound adder and 4 additional logic levels.
If the injection is not added in during the reduction of the partial products into a carry-save
encoded digit string, then an extra step of adding in the injection is required. This step amounts
to a carry-save addition, and the latency associated with it is that of a full-adder, namely, 2 logic
levels. Thus, if the injection is added in late, then the latency of the ES rounding algorithm is 14
logic levels.
The addition of the injection during the reduction of the partial products can be accomplished
without a slowdown or with a very small slowdown. The justication for this is: (a) The partial
products are usually obtained by Booth recoding and by selecting (e.g. 5:1 multiplexer), and hence,
are valid much later than the injection; and (b) The delay of adding the partial products does not
increase strictly monotonically as a function of the number of partial products. The delay incurred
by adding in the injection, if any, depends on the length of the signicands and on the organization
of the adder tree.
The other two rounding algorithms do not require an injection, and in double precision, the
latency of the QTF rounding algorithm is 14 logic levels. The critical path consists of a compound
adder and 6 additional logic levels. The YZ rounding algorithm ranks as the slowest rounding
algorithm, with a latency of 16 logic levels, and the critical path consists of a compound adder and
8 additional logic levels.



--R

Area and Performance Optimized CMOS Multipliers.
Fast Multiplication: Algorithms and Implementation.
A Regular Layout for Parallel Adders.
Method for rounding using redundant coded multiply result.

Some schemes for parallel multipliers.
Method and apparatus for rounding in high-speed multipliers
Recoders for partial compression and rounding.
Fast multiplier bit-product matrix reduction using bit- ordering and parity generation
A Dual Mode IEEE multiplier.
A comparison of three rounding algorithms for IEEE oating- point multiplication
Parallel method and apparatus for detecting and completing oating point operations involving special operands.
IEEE standard for binary oating-point arithmetic
Multistep gradual rounding.
Design strategies for optimal multiplier circuits.

Design Issues in High Performance Floating Point Arithmetic Units.
The SNAP project: Design of oating point arithmetic units.
A method for speed optimized partial product reduction and generation of fast parallel multipliers using an algorithmic approach.
Reducing the number of counters needed for integer multiplication.
Generation of high speed CMOS multiplier- accumulators
Floating Point Multiplier Performing IEEE Rounding and Addition in Parallel.
On fast IEEE rounding.
Rounding algorithms for IEEE multipliers.
How to half the latency of IEEE compliant oating-point multiplication

A reduced-Area Scheme for Carry-Select Adders
A very fast multiplication algorithm for VLSI implementation.
A suggestion for parallel multipliers.
A new design technique for column compression multipliers.
oating point multiplier
Method and apparatus for partially suporting subnormal operands in oating point multiplication.
Shared rounding hardware for multiplier and division/square root unit using conditional sum adder.
Circuitry for rounding in a oating point multiplier.







9L 13L 13L 14L 15L 14L 13L 16L 16L 9L 8L 10L
--TR

--CTR
Peter-Michael Seidel , Guy Even, Delay-Optimized Implementation of IEEE Floating-Point Addition, IEEE Transactions on Computers, v.53 n.2, p.97-113, February 2004
Ahmet Akkas , Michael J. Schulte, Dual-mode floating-point multiplier architectures with parallel operations, Journal of Systems Architecture: the EUROMICRO Journal, v.52 n.10, p.549-562, October 2006
Nhon T. Quach , Naofumi Takagi , Michael J. Flynn, Systematic IEEE rounding method for high-speed floating-point multipliers, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.5, p.511-521, May 2004
floating-point multiplication;IEEE 754 Standard;floating-point arithmetic;IEEE rounding