Advanced Components in the Variable Precision Floating-Point

Library
Xiaojun Wang, Sherman Braganza, Miriam Leeser
Department of Electrical and Computer Engineering
Northeastern University, Boston, MA, USA
{xjwang,sbraganz,mel}@[Link]

Abstract 1 Introduction

One of the applications of reconfigurable hardware

is to accelerate algorithms initially implemented in
Optimal reconfigurable hardware implementations software and run on a general purpose processor. The
may require the use of arbitrary floating-point formats prime candidates are those algorithms that are highly
that do not necessarily conform to IEEE specified regular and parallel, such as image and signal process-
sizes. We have previously presented a variable preci- ing applications. To achieve acceleration, custom dat-
sion floating-point library for use with reconfigurable apaths are built in reconfigurable hardware using ei-
hardware. We recently added three advanced com- ther fixed-point or floating-point arithmetic. In either
ponents: floating-point division, floating-point square case, optimal bitwidths of the signals in the datap-
root and floating-point accumulation to our library. ath are application specific, and depend on the values
These advanced components use algorithms that are they carry. To increase potential parallelism and to
well suited to FPGA implementations and exhibit a reduce the power dissipation of the circuit, we wish
good tradeoff between area, latency and throughput. to minimize the bitwidth of each signal. Hence, it is
The floating-point format of our library is both gen- important to have fine-grained control over the data-
eral and flexible. All IEEE formats, including 64-bit path bitwidths throughout the whole design process.
double-precision format, are a subset of our format. Arbitrary fixed-point formats are not difficult to im-
All previously published floating-point formats for re- plement and are in common use. However, due to the
configurable hardware are a subset of our format as inherent complexity of floating-point representation,
well. The generic floating-point format supported by arbitrary floating-point formats are much harder to
all of our library components makes it easy and con- implement though they are no less desirable.
venient to create a pipelined, custom datapath with We have implemented a variable precision floating-
optimal bitwidth for each operation. Our library can point library [1]. Our library supports general flex-
be used to achieve more parallelism and less power dis- ible formats which can be parameterized to accept
sipation than adhering to a standard format. To fur- any bitwidth operand including the IEEE standard
ther increase parallelism and reduce power dissipation, formats. Most earlier work only supports either
our library also supports hybrid fixed and floating- IEEE formats or the authors’ non-general application-
point operations in the same design. The division and specific formats. Each component in our library has
square root designs are based on table lookup and Tay- a ready signal and a done signal to support pipelin-
lor series expansion, and make use of memories and ing. All the hardware modules, including the three ad-
multipliers embedded on the FPGA chip. The itera- vanced components presented in this paper, are fully
tive accumulator utilizes the library addition module pipelined. Our library includes components to convert
as well as buffering and control logic to achieve perfor- between fixed-point and floating-point format, which
mance similar to that of the addition by itself. They allows the user to implement the optimal hybrid data-
are all fully pipelined designs with clock speed com- path comprised of both fixed-point and floating-point
parable to that of other library components to aid the operators in a single design. In this paper, we discuss
designer in implementing fast, complex, pipelined de- three advanced components recently added to our li-
signs. brary: floating-point division (fp div), floating-point

14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'06)

0-7695-2661-6/06 $20.00
Authorized licensed use©limited
2006 to: Indian Institute of Technology Hyderabad. Downloaded on September 30,2024 at 21:21:54 UTC from IEEE Xplore. Restrictions apply.
 square root (fp sqrt) and floating-point adder accu- floating point library from Lyons [13]. Both libraries
mulation (fp acc). These components all exhibit good provide a variety of variable precision floating point
tradeoffs between area, latency and throughput. components that are easily parameterizable. Both
support conversion from different formats. Our library
1.1 Related Work provides more support for pipelining and for exception
handling. The divide and square root components in
Early implementations of floating point on FP- the Lyons library are SRT radix 4 and radix 2 respec-
GAs used non-standard formats, largely because im- tively. These designs should exhibit longer latencies.
plementing IEEE compliant single precision add and In addition, their library does not include an accumu-
multiply was impractical [2, 3]. Some ideas from early lator component.
papers incorporated into our library include turn- Users of our floating point library can make use of
ing normalization into a separate component [4] and complementary research [14] focused on automatically
adding signals to synchronize the flow of data through optimizing the bitwidth of floating-point operands.
pipelines [5].
Floating-point division and square root are harder 1.2 Floating-Point Library
to implement due to the complexity of the algorithms.
Dido et al. [6] calculate the inverse of the denomina- Our parameterized floating-point library [1] con-
tor based on a lookup table, followed by multiplying sists of three types of components: format control,
that inverse by the numerator. This method is only arithmetic operations, and format conversion. For-
feasible for small dividers. Roesler and Nelson [7] im- mat control includes modules denorm and rnd norm.
plemented a Newton-Raphson based floating-point di- The first is used for denormalizing (introducing the
vider. However, it has long latency due to the iter- implied integer bit that is required for computation)
ative nature of the algorithm. The tradeoffs of de- and the second is used for rounding and normaliz-
signing a floating-point divider based on the higher ing. Arithmetic operations include modules fp add,
radix SRT algorithm was studied by Wang and Nel- fp sub, fp mul, fp div, fp sqrt and fp acc, that
son [8]. The IEEE double-precision floating-point di- are used for floating-point addition, subtraction, mul-
vider described by Paschalakis and Lee [9] is a non- tiplication, division, square root and accumulation
pipelined design that uses the simple radix-2 digit- respectively. Format conversion includes modules
recurrence algorithm. Therefore, it has small area but fix2float and float2fix. The first is used to con-
low throughput with a latency of 60 clock cycles for vert from fixed-point representation (both unsigned
double-precision division. Underwood [10] discusses and signed) to floating-point representation and the
the feasibility of supporting IEEE double precision second converts floating-point to fixed-point. Format
floating point on FPGAs. He presents add, multi- conversion allows for the implementation of both fixed
ply and divide components that are IEEE compliant. and floating-point computations within the same ap-
The divider is bit serial and exhibits long latency. plication.
square root. Previously published work on floating- Table 1 shows the name, function and latency (in
point square root implementations [8, 9] uses the sim- clock cycles) of all the modules. Two of our advanced
ple radix-2 digit-recurrence algorithm. The divider components fp div and fp sqrt, have latencies vary-
and square root presented in this paper differ from ing with the bitwidth of the floating-point format. We
previously presented FPGA implementations. They will see later that they have much longer latencies for
are well suited to implementation on modern FPGAs wider bitwidth format than the other library modules
because they use a mix of small table lookup and due to their intrinsic complexity. The fp acc compo-
multipliers. They are also non-iterative and easily nent has a latency varying with both bitwidth and the
pipelined. number of operands. The reason for the longer latency
Floating-point accumulators and multiply- of these three components is that we attempted to
accumulators have been previously discussed and make all library modules have as similar a clock period
implemented [11, 12]. However, our design for the as possible in order to achieve the highest throughput
floating-point accumulator does not require stalling pipeline.
or compiler assistance [12], and does not rely on Our floating-point format is depicted in Fig. 1 along
application characteristics to avoid data hazards [11]. with two examples – IEEE 32-bit single-precision for-
Our design is well suited to be implemented on an mat and IEEE 64-bit double-precision format. Each
FPGA. hardware module of our library can be parameterized
The closest work to ours is the variable precision to accept any floating-point format with any bitwidth

14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'06)

0-7695-2661-6/06 $20.00
Authorized licensed use©limited
2006 to: Indian Institute of Technology Hyderabad. Downloaded on September 30,2024 at 21:21:54 UTC from IEEE Xplore. Restrictions apply.
 Table 1: Floating-point Hardware Modules and Their Latency in Clock Cycles
Module Function Latency
denorm Introduction of implied integer digit 0
rnd norm Normalizing and rounding 2
fp add/fp sub Addition/Subtraction 4
fp mul Multiplication 3
fp div Division variable
fp sqrt Square Root variable
fp acc Accumulator variable
fix2float/fix2float unsigned Unsigned/signed fixed-point to floating-point conversion 4/5
float2fix/float2fix signed Floating-point to unsigned/signed fixed-point conversion 4/5

Biased Significand s=1.f ponent starts to process the input data which should
Sign exponent (the 1 is hidden) be valid then or earlier. Upon completion, the com-
ponent makes the output values available on the data
+/- e+bias f outputs and sets the done signal to high. These hand-
shaking signals allow our library components to be
32-bits: 8 bits, bias=127 23+1 bits, single-precision format
easily assembled into a pipelined datapath.
64-bits: 11 bits, bias=1023 52+1 bits, double-precision format
Our library also supports some error handling.
Each module in our library has an exception in sig-
nal and an exception out signal. An error fed into
Figure 1: The ANSI/IEEE Standard Floating-Point one component with the exception in signal high or
Number Representation Formats detected inside this component, is propagated to the
exception out signal. In this manner, error signals
are propagated through a pipeline along with their
exponent and mantissa. All designs in our library corresponding results.
are written in VHDL. The VHDL description of each In this paper we discuss the newest additions to our
module accepts the parameters exp bits and man bits. floating-point library: division, square root, and accu-
The exp bits represents the bitwidth of the exponent mulation. These three advanced components are pre-
and man bits represents the bitwidth of the mantissa. sented in Section 2. In Section 3, we describe the area,
These parameters are compile-time variables; they al- latency and throughput of a wide range of floating-
low the bitwidth of each unit in the datapath to be point formats for these three components. Finally,
parameterized, thus optimizing the amount and the discussion and conclusions are in Sections 4 and 5.
structure of logic needed to implement a circuit. In
other words, the designer has the flexibility to build a
custom datapath by specifying the exact bitwidth of 2 Advanced Floating-Point Compo-
each datapath unit. nents
Fig. 2 shows a generic library component. Each
Divide, square root, and accumulate are important
operations in many high performance signal process-
INPUTS
ing applications. We have implemented floating-point
OUTPUTS
DATA INPUTS GENERIC Floating DATA OUTPUTS
division, square root and accumulation. Both the di-
READY
CLK Point Component DONE
vision [15] and square root [16] algorithms are based
EXCEPTION_OUT
EXCEPTION_IN

on table lookup and Taylor series expansion, and use

a combination of small table lookup and small multi-
pliers to obtain the first few terms of the Taylor se-
Figure 2: A Generic Library Component ries. These algorithms are particularly well-suited for
implementation on an FPGA with embedded RAM
and embedded multipliers such as the Altera Stratix
component in our library has a ready signal and a and Xilinx Virtex family devices. They are also non-
done signal. When the ready signal is high, the com- iterative algorithms which makes them easy to fit into

14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'06)

0-7695-2661-6/06 $20.00
Authorized licensed use©limited
2006 to: Indian Institute of Technology Hyderabad. Downloaded on September 30,2024 at 21:21:54 UTC from IEEE Xplore. Restrictions apply.
 the pipeline of a big design with other library modules 2m bits 2m bits
without affecting the throughput of the whole design. Dividend X Divisor Y
An accumulate component has been designed and
implemented for our floating-point library that uses
2m bits m bits
a buffering approach[17] to avoid data hazards. This
approach uses a minimum of device resources, scales Multiplier Lookup Table
well with increasing mantissa size and operates at a
frequency comparable to that of a single floating-point 2m+2 bits 2m+2 bits

add. It is the only iterative component in our library. Multiplier

2m bits
2.1 Floating-Point Divider Result

The divider we built follows a previously published

algorithm [15]. Assume a dividend X and a divisor Y , Figure 3: Table-Lookup Based Divider
both 2m bit fixed-point numbers in the range of [1,2).
They can be expanded in the form:
Using this table-lookup based divider as the core,
X = 1 + 2−1 x1 + 2−2 x2 + · · · + 2−(2m−1) x2m−1 (1) a floating-point divider can be built. Floating-point
Y = 1 + 2−1 y1 + 2−2 y2 + · · · + 2−(2m−1) y2m−1 (2) division can be implemented as:

where xi , yi ∈ {0, 1}. The divisor Y can be further (−1)s1 × m1 × 2e1

= (−1)s1 ⊕s2 × (m1 /m2 ) × 2(e1 −e2 )
decomposed into a higher order bit part Yh and a lower (−1)s2 × m2 × 2e2
order bit part Yl , which are defined as: (6)
The sign of the quotient is the exclusive OR (XOR)
Yh = 1 + 2−1 y1 + 2−2 y2 + · · · + 2−m ym (3) of the signs of the input operands; the exponent of
Yl = 2−(m+1) ym+1 + 2−(m+2) y(m+2) + the quotient is the difference of exponents of the in-
put operands; and the mantissa of the quotient is the
· · · + 2−(2m−1) y2m−1 (4) quotient of mantissas of the input operands. The man-
tissa is obtained using the table-lookup based divider
The range of Yh is between 1 and Yhmax (= 2 − 2−m ),
core shown in Fig. 3. The computation of sign, ex-
and the range of Yl is between 0 and Ylmax (= 2−m −
ponent, and mantissa can be implemented in parallel.
2−(2m−1) ). To calculate X/Y using the Taylor series:
Exception detection is implemented in parallel with
X X X Yl Y2 the computation of the quotient mantissa.
= = (1 − + l2 − · · ·)
Y Yh + Yl Yh Yh Yh
2.2 Floating-Point Square Root
1
≈ X × (Yh − Yl ) × 2 (5)
Yh The square root we built is also based on a pre-
viously published algorithm [16]. It also uses table
Since Yh > 2m Yl , the maximum fractional error in
lookup and Taylor series expansion, but it is much
equation (5) is less than 2−2m , or 1/2 ulp 1 . Divi-
more complicated than the divider. Fig. 4 shows the
sion based on equation (5) is also straightforward to
three steps to complete a square root: reduction, eval-
implement in FPGA hardware. It requires only two
uation, and post processing. Let Y be an n bit fixed-
multiplications and one table-lookup for Y12 . Fig. 3
h point number in the range of [1,2) and let k be an
shows a schematic representation of equation (5). integer such that
The BlockRAMs and embedded multipliers that
the Xilinx Virtex-II FPGA provides are used in our k = n/4
implementation for table lookup and multiplication.
Table lookup via BlockRAM takes only one clock cy- The first step is to reduce Y to a k bit number A
cle. The multipliers are pipelined multipliers and their (−2−k < A < 2−k ) such that the square root of Y can
latency varies with the size of the multiplier. Thus, the be easily obtained from a function of f (A). This f (A)
overall latency of the divider also varies with its size. will be evaluated in the next step. A can be obtained
as:
1 ulp is an acronym for unit in the last place. The least

significant bit of the fraction of a number is the last place A = Y × R̂ − 1 (7)

14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'06)

0-7695-2661-6/06 $20.00
Authorized licensed use©limited
2006 to: Indian Institute of Technology Hyderabad. Downloaded on September 30,2024 at 21:21:54 UTC from IEEE Xplore. Restrictions apply.
 2−k , A has the form:
Y

Reduce the input Y A = A2 z 2 + A3 z 3 + A4 z 4 + · · · (10)

Reduction to a very small number A

A where z = 2−k and |Ai | = 2k −√1. Our goal is to com-

00... 00 A2 A3 A4 pute the approximation B = 1 + A. Using Taylor
Compute first terms
series expansion:
Evaluation
of Taylor series √
B = 1+A
(11)
M B= f(A ) ≈1+ A 1 2 4 1 5 1 3 6
2 − 8 A2 z − 4 A2 A3 z + 16 A2 z

Postprocessing This requires only two k × k multipliers and one 2k × k

Multiplier
multiplier as shown in Fig. 6.
sqrt(Y )

A 4k bits
0...00 A2 A3 A4
Figure 4: Table-Lookup Based Square Root

A2 A3 A2
k bits k bits k bits
(k)
R̂ = 1/Y (8) ^2 Multiplier

where Y (k) is Y truncated to its k th bit. A 4k bit

A2 A2* A2 A2*A3
k bits 2k bits
number M is also generated:
Multiplier

M = 1/ R̂ (9) A2* A2 * A2

This M will be used in the post processing step to

Multiple Operand
correct the final result due to the reduction step. Fig. 5 Signed Adder
shows the data flow of this reduction step. Two table-
lookups with k address bits each are required for R̂ B 4k bits
and M respectively and one (k + 1) × 4k multiplier is
required for A.
Figure 6: Evaluation Step of Square Root
Y 4k bits
At the end, we need to correct the result B by mul-
Y (k )
Y
tiplying it by M from the reduction step. This re-
quires one multiplier and is done in the post processing
k bits k bits
step. The overall error of all three steps is analyzed
M R as 2.39 × 2−4k [16].
Table Table Similar to division, lookup tables are built using
BlockRAMs with one clock cycle latency. Multipli-
^
R k + 1 bits
4k bits ers are built using embedded multipliers which are
pipelined with various latencies depending on their
Multiplier size. So the overall latency of the square root also
^
varies with its size.
M 4k bits A=Y R -1
Using this table-lookup based square root as the
core, a floating-point square root can be built. The
0...00 A2 A3 A4
sign of the square root and input operand should al-
4k bits ways be 0. Otherwise, an error is raised. The ex-
ponent of the square root is half the exponent of the
Figure 5: Reduction Step of Square Root input operand if the input exponent is even. If the in-
put exponent is odd, the exponent of the square root
is half the input exponent minus one and the mantissa
The second step is evaluation. Since −2−k < A < of the square root needs to be multiplied by a constant

14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'06)

0-7695-2661-6/06 $20.00
Authorized licensed use©limited
2006 to: Indian Institute of Technology Hyderabad. Downloaded on September 30,2024 at 21:21:54 UTC from IEEE Xplore. Restrictions apply.
 √
factor 2. We combine this constant multiplication in IN1
the computation of M in the reduction√ step. In other
words, √we have one extra table for 2M . Whether
DEMUX
M or 2M is selected depends on whether the in-
put exponent is even or odd. The mantissa of the
MUX_A MUX_B
square root is the square root of the mantissa of the
input operand, which can be obtained using the table-
lookup based square root core shown in Fig. 4. Similar
FP_ADD
to other components, the exponent and mantissa are
NORM
computed in parallel since they are independent. Ex-
0-count2 0-count1
ception handling is implemented in parallel as well.
variable_shift

2.3 Floating-Point Accumulator

buf0
The accumulator in our library is based on a buf1
buf2
floating-point adder. A buffer is inserted to ensure
that no data hazards occur. A similar idea was used by
Zhuo and Prasanna [17] to implement their reduction OUT1
circuit for matrix vector multiplication. The general
concept is as follows: Figure 7: Accumulate Decomposed Into Components
Assuming a new, valid input arrives every clock cy-
cle, every two clock cycles there is enough data (i.e.
two operands) to begin the pipelined floating-point tion. The normalizer used is an updated version of
add. Once the normalized output is produced, it can the one described in [1]. Rather than use one large
be buffered and re-introduced into the adder input leading-zero counter, it breaks the mantissa into two
chain in-between the times that new data is input into sections, counts the number of leading zeroes in each
the add unit. The number of additions per cycle con- section and adds them together depending on some
verges to one for large numbers of continuously valid additional control logic. This method of dividing up
new inputs and the maximum buffer size required is the leading-zero counter provides faster and smaller
three words. In addition, none of the operands are de- normalize implementations [11]. We plan to use this
pendent since they have traversed the entire pipeline approach to improve the normalize component in the
and have been written back. These statements have library.
been examined and proven correct [17]. Exception handling is provided via the excep-
The control logic behind the sets of conditions re- tion in and exception out lines. An exception in-
quired are implemented as separate state machines, put to the accumulator causes the related operand to
one controlling the insertion of new operands into the be set to zero and the accumulation continues. An
iterative addition chain and the other managing the output exception is asserted when the accumulation
feedback of old outputs back into the chain. The out- is complete and the calculated sum (not including the
puts of these state machines dictate the actions of the erroneous input) is driven on the output lines. Over-
multiplexer and demultiplexer shown in Fig. 7, as well flow and underflow exceptions are generated internally
as control the registering of values. Overall latency in- by the fp add unit. These cause the output to wrap
formation for the accumulator is presented in Table 2. to zero and continue accumulating. In this event an
exception is also asserted upon completion.
Component Latency(Cycles)
Input mux 1
FP add 4 3 Experimental Results
Normalize 2
Buffering 1
3.1 Experimental Setup
Table 2: Table of Component Latencies
All designs presented in this paper are implemented
on an Atlanta board from Mercury Computer Sys-
The accumulator differs from other library compo- tems, Inc. Fig. 8 shows the module architecture of
nents in that normalization is implicit in the opera- this board. This board integrates an FPGA with Pow-

14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'06)

0-7695-2661-6/06 $20.00
Authorized licensed use©limited
2006 to: Indian Institute of Technology Hyderabad. Downloaded on September 30,2024 at 21:21:54 UTC from IEEE Xplore. Restrictions apply.
 theses. The sign bit is assumed. The fifth column of
both tables represents IEEE single-precision format
32(8, 23). The last column of Table 4 is the IEEE
double-precision format 64(11, 52). The quantities for
the area of each design in both tables are evaluated
using three metrics - number of slices, number of on-
board BlockRAMs and number of 18 × 18 embedded
multipliers. The Xilinx Virtex-II XC2V6000 FPGA
has a total number of 33792 slices, 144 on-board Block-
RAMS, and 144 embedded multipliers.
Our results show that both the area and the la-
Figure 8: Architecture of the Mercury Atlanta Board tency of our floating-point divider and square root are
small compared to most other divider and square root
implementations. For an IEEE single-precision for-
mat divider, it takes 14 clock cycles to generate the
erPC G4 microprocessors in the RACEway switch fab-
final result with a 7.7ns clock period resulting in a
ric architecture. Some of the main features of the
total latency of 108ns. Note that non-iterative algo-
Atlanta board are: one Xilinx Virtex-II XC2V6000
rithms are employed for both our divider and square
FPGA compute node at a speed grade of -5; 12MB of
root compared to most other divider and square root
DDR SRAM and 256MB of DDR SDRAM both run-
ning at 133MHz; 52 pairs of LVDS I/O lines; and a implementations. The non-iterative nature of the al-
gorithm allows them be fully pipelined and thus the
dual-processor PCI module with two PowerPCs. Each
throughput is one result per clock cycle. This allows
PowerPC compute node consists of a 500 MHz Pow-
them to easily fit into the pipeline of a big design with
erPC 7410 microprocessor. In this work we only make
other library modules without decreasing the through-
use of the FPGA.
put of the whole design. The throughput of our IEEE
All our designs are written in VHDL and synthe-
single-precision format divider is as high as 129 million
sized using Synplify Pro 8.0. The bitstream is gen-
results per second. Meanwhile, this design only takes
erated using Xilinx ISE 6.3i and downloaded to the
1% of the slices, 4% of the BlockRAMs, and 5% of the
Virtex-II XC2V6000 FPGA on the Atlanta board.
embedded multipliers on the FPGA chip. Similarly,
This section presents experimental results for each
our floating-point square root shows a good tradeoff
of the three advanced modules (fp div, fp sqrt and
between area, latency and throughput.
fp acc) for a wide range of floating-point formats
including IEEE single-precision and double-precision It is an obvious observation from both tables that
formats. All the advanced hardware modules have the wider the floating-point bitwidth, the larger and
been tested both in simulation and in hardware. For slower the circuit. For wider designs, not only does the
simulation, we use a testbench that tests a combina- clock period increase, but also the number of clock cy-
tion of random numbers and corner cases for various cles to generate the final result. Our goal is to keep
bitwdith floating-point formats. For testing on the the clock period relatively constant over a wide range
reconfigurable board, we send the same set of num- of bitwidths and formats. Therefore we have to add
bers through the PCI bus to the FPGA board, do the more pipeline stages to wider bitwidths as a compro-
computation on the board, then read them back to the mise. This results in a steadily increasing latency with
host PC. increasing bitwidth.
The largest floating-point components that we can
3.2 Experimental Results for Floating- implement is limited by the number of on-board Block-
Point Divider and Square Root RAMs. As we can see from both tables, the number of
BlockRAMs required increases at a much faster rate
Tables 3 and 4 show the area, latency and through- compared to the number of slices and the number of
put of several different floating-point formats includ- embedded multipliers as bitwidth increases. This is
ing IEEE single-precision format for division and both because the sizes of the tables (in Fig. 3) for the di-
IEEE single-precision and double-precision format for vider and (Fig. 5) square root increase exponentially
square root. The format is represented by the total while other parts of the design increases polynomially
number of bits, the number of exponent bits followed with the increase in bitwidth. Fig. 3 shows that di-
by the number of mantissa bits are shown in paren- vider requires one table with the size of 2m × (2m + 2).

14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'06)

0-7695-2661-6/06 $20.00
Authorized licensed use©limited
2006 to: Indian Institute of Technology Hyderabad. Downloaded on September 30,2024 at 21:21:54 UTC from IEEE Xplore. Restrictions apply.
 Table 3: Area, Latency and Throughput for Floating-Point Division
Floating Point Format 8(2,5) 16(4,11) 24(6,17) 32(8,23) 40(10,29)
number of slices 66 (1%) 115 (1%) 281 (1%) 361 (1%) 617 (1%)
number of BlockRAM 1 (1%) 1 (1%) 1 (1%) 7 (4%) 62 (43%)
number of 18 × 18 embedded multiplier 2 (1%) 2 (1%) 8 (5%) 8 (5%) 8 (5%)
clock period (ns) 4.9 6.8 7.8 7.7 8.0
maximum frequency (MHz) 202 146 129 129 125
number of clock cycles to generate final results 10 10 14 14 14
latency(ns) = clock × number of clock cycles 49 68 109 108 112
throughput (million results per second) 202 146 129 129 125

Table 4: Area, Latency and Throughput for Floating-Point Square Root

Floating Point Format 8(2,5) 16(4,11) 24(6,17) 32(8,23) 48(9,38) 64(11,52)

number of slices 85 (1%) 172 (1%) 308 (1%) 351 (1%) 779 (2%) 1572 (4%)
number of BlockRAM 3 (2%) 3 (2%) 3 (2%) 3 (2%) 13 (9%) 116 (80%)
number of 18 × 18 embedded multiplier 4 (2%) 7 (4%) 9 (6%) 9 (6%) 16 (11%) 24 (16%)
clock period (ns) 6.1 7.2 7.8 8.0 8.8 9.7
maximum frequency (MHz) 165 139 129 125 114 103
number of clock cycles to generate final results 9 12 13 13 16 17
latency(ns) = clock × number of clock cycles 55 86 101 104 140 165
throughput (million results per second) 165 139 129 125 114 103

The address of this table is m-bits wide, where m is to the assertion of the done line by the accumulator
half the width of the mantissa bitwidth. Fig. 5 shows varies between nine cycles for only two inputs, to a
square root has more tables but the address of each maximum of thirty five cycles for a sufficiently large
table is k-bits wide, which is only 1/4 of the man- number of inputs. This is for an eight cycle pipeline
tissa bitwidth. Therefore, the size of tables for the length. Increasing the pipeline length by one increases
square root increases much more slowly than that of the worst case delay to more than forty cycles.
the divider. For small bitwidths, square root requires The rate at which the overall cycle time as well as
more BlockRAMs than the divider, while for large the latency increases with respect to the number of
bitwidths, it requires fewer. The largest floating-point operands is shown in Fig. 9. For an even number of
square root we can design is IEEE double-precision operands, the worst case latency is thirty two cycles.
64(11,52), which requires about 80% (116 out of 144) For an odd number it is thirty five cycles.
of on-board BlockRAMs for this chip. The largest
floating-point divider we can implement on the Virtex- The results presented in Table 5 are taken from
II 6000 is the 40(10,29) format. This format requires post place and route reports using the Xilinx ISE
6.3i toolset. The floating point representation dif-
about 43% (62 out of 144) of on-board BlockRAMs.
Since the table size for the divider more than doubles fers from that above in that 3 guard bits are used
when the width of the address increases just by one to maintain accuracy. As can be seen, the slice
count increases approximately linearly with respect to
bit, the next larger design will result in insufficient on-
board BlockRAMs on this chip. We are investigating bitwidth. Frequency decreases by 23 percent when go-
ing from single-precision to double-precision. Unlike
using a similar algorithm as that used for square root
to implement division. fp div and fp sqrt, this component does not utilize
BlockRAMs or embedded multipliers and its overall
3.3 Experimental Results for Floating- latency depends on the number of operands.
Point Accumulator Although a single floating-point add based on the
fp add component takes up fewer slices than an equiv-
The number of clock cycles from the de-assertion alent bitwidth accumulator, it operates at a similar
of the ready line (signaling the end of valid input), frequency. A single-precision add (with the same num-

14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'06)

0-7695-2661-6/06 $20.00
Authorized licensed use©limited
2006 to: Indian Institute of Technology Hyderabad. Downloaded on September 30,2024 at 21:21:54 UTC from IEEE Xplore. Restrictions apply.
 module, we are able to implement the mean updat-
Total number of CLK cycles
ing step in FPGA hardware. This greatly reduces
Accumulator Latency Graph
Cycles from end of input to done the communication overhead between host and FPGA
80
board and further accelerates the runtime. We are also
70
investigating using the new fp acc component in this
Number of CLK cycles

60
implementation.
50
Note that on-board BlockRAMs are used for all our
40
tables in this work. Our philosophy is to reserve LUTs
30
for other components, such as adders. Hence our de-
20
sign is limited by the size of on-board BlockRAMs.
10
In Table 3, the largest divider 40(10,29) uses 43% of
0
0 5 10 15 20 25 30 35 40 BlockRAMs but only 1% of slices. Larger dividers
Number of Operands
could be implemented by using LUTs as distributed
memory. We are planning to investigate this in future
designs to achieve wider bitwidths.
Figure 9: Graph of Accumulator Delay The method of accumulation used in the fp acc
component scales well in terms of speed and size as
bitwidth increases. This can clearly be seen in Ta-
ble 5. Its greatest drawback is that the delay from the
Bitwidth 24 32 47 64
(E,M,Grd) 6,17,3 8,23,3 9,37,3 11,52,3 end of input to the assertion of the done signal in-
Slices 431 558 843 1145 creases rapidly with respect to pipeline length. Thus
Freq. (MHz) 149 140 123 108 optimal use of this accumulator is made when utiliz-
Period (ns) 6.7 7.1 8.1 9.25 ing short pipelines or over a large number of accumu-
lations. Comparing the accumulator with an imple-
Table 5: Table of Accumulator Frequency vs. Size mentation using a stalling technique and a four-stage
adder, this point occurs with an accumulation of eight
floating-point numbers.
Rounding support is currently provided via a pa-
ber of guard bits) operates at 136 MHz, while a double
rameterizable number of guard bits. The library
precision version operates at 126 MHz. Thus the ac-
rounding module can then be used post-accumulation
cumulator speed is within 15% of the floating-point
to provide a more accurate final sum. If a greater
add for the sizes discussed here.
degree of rounding accuracy is required, the normal-
ize in the accumulator can be replaced with the full
round norm library component to provide round-to-
4 Discussion nearest functionality. This is easily accomplished since
the round norm and the accumulator normalize both
Many signal processing algorithms can be accel- take two cycles and use similar inputs and outputs.
erated using reconfigurable hardware. To achieve a
good speedup compared to running software on a gen-
eral purpose processor, fine-grained control over the 5 Conclusions
bitwidth of each component in the datapath is de-
sired. This goal can be achieved by using our vari- Three advanced floating-point components -
able precision floating-point library. To demonstrate division (fp div), square root (fp sqrt) and ac-
the division implementation, we incorporate it into our cumulation (fp acc) have recently been added to
previous implementation of the K-means clustering al- our variable precision floating-point library. All
gorithm applied to multispectral satellite images [1]. three of these advanced components as well as
With the lack of floating-point divider, the mean up- all other hardware modules in our floating-point
dating step in each iteration of the K-means algorithm library are fully parameterized and fully pipelined.
has to be moved to the host computer for calculation. Several different floating-point formats, including
The new means calculated on the host then have to be IEEE single-precision and double-precision formats
moved back to FPGA board for next iteration of the for these components are discussed. Our results
algorithm. This dramatically decreases the speedup of show that these components exhibit a good tradeoff
the hardware implementation. With our new fp div between area, latency and throughput, and are easily

14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'06)

0-7695-2661-6/06 $20.00
Authorized licensed use©limited
2006 to: Indian Institute of Technology Hyderabad. Downloaded on September 30,2024 at 21:21:54 UTC from IEEE Xplore. Restrictions apply.
 pipelined. Our library supports the creation of [8] X. Wang and B. E. Nelson, “Tradeoffs of de-
custom format floating-point datapaths, as well as signing floating-point division and square root
hybrid fixed and floating-point implementations using on Virtex FPGAs,” in 11th IEEE Symposium
these components. All the components are available on Field-Programmable Custom Computing Ma-
as part of the variable precision floating point library chines, pp. 195–203, April 2003.
from:
[9] S. Paschalakis and P. Lee, “Double precision
[Link]/groups/rcl/projects/floatingpoint/.
floating-point arithmetic on FPGAs,” in IEEE
International Conference on Field-Programmable
Technology, pp. 352–358, Dec. 2003.
Acknowledgements
[10] K. D. Underwood, “FPGAs vs. CPUs: trends in
This research was funded in part by Mercury Com- peak floating-point performance,” in 12th Inter-
puters and by the NSF ERC Center CenSSIS. national Symposium on Field Programmable Gate
Arrays, pp. 171–180, Feb. 2004.
[11] Y. Dou, S. Vassiliadis, G. K. Kuzmanov, and
References G. N. Gaydadjiev, “64-bit floating-point FPGA
matrix multiplication,” in 13th International
[1] P. Belanović and M. Leeser, “A library of param-
Symposium on Field-Programmable Gate Arrays,
eterized floating-point modules and their use,”
Feb. 2005.
in 12th International Conference on Field Pro-
grammable Logic, pp. 657–666, Sept. 2002. [12] Z. Luo and M. Martonosi, “Accelerating
pipelined integer and floating-point accumula-
[2] B. Fagin and C. Renard, “Field programmable
tions in configurable hardware with delayed addi-
gate arrays and floating point arithmetic,” IEEE
tion techniques,” in IEEE Transactions on Com-
Transactions on VLSI Systems, vol. 2, pp. 365–
puters, vol. 49, pp. 208–218, March 2000.
367, Sept. 1994.
[13] “A VHDL library of parametris-
[3] N. Shirazi, A. Walters, and P. Athanas, “Quan-
able floating-point and LNS oper-
titative analysis of floating point arithmetic on
ators for FPGA.” [Link]
FPGA based custom computing machines,” in
[Link]/[Link]/FPLibrary/.
IEEE Symposium on FPGAs for Custom Com-
puting Machines, pp. 155–162, April 1995. [14] A. A. Gaffar, O. Mencer, W. Luk, and P. Y. K.
Cheung, “Unifying Bit-width Optimisation for
[4] L. Louca, T. A. Cook, and W. H. Johnson, “Im- Fixed-point and Floating-point Designs,” in 12th
plementation of IEEE single precision floating IEEE Symposium on Field-Programmable Cus-
point addition and multiplication on FPGAs,” in tom Computing Machines, pp. 79–88, April 2004.
IEEE Symposium on FPGAs for Custom Com-
puting Machines, pp. 107–116, April 1996. [15] P. Hung, H. Fahmy, O. Mencer, and M. J. Flynn,
“Fast division algorithm with a small lookup ta-
[5] C. S. Gloster, Jr. and I. Sahin, “Floating-Point ble,” in 33rd Asilomar Conference on Signals,
Modules Targeted for Use with RC Compilation Systems and Computers, vol. 2, pp. 1465–1468,
Tools,” in Earth Science Technology Conference, May 1999.
Aug. 2001.
[16] M. D. Ercegovac, T. Lang, J.-M. Muller, and
[6] J. Dido, N. Geraudie, et al., “A flexible floating- A. Tisserand, “Reciprocation, square root, in-
point format for optimizing data-paths and op- verse square root, and some elementary functions
erators in FPGA based DSPs,” in International using small multipliers,” IEEE Transactions on
Symposium on Field Programmable Gate Arrays, Computers, vol. 49, pp. 628–637, July 2000.
pp. 50–55, Feb. 2002.
[17] L. Zhuo, G. R. Morris, and V. K. Prasanna,
[7] E. Roesler and B. E. Nelson, “Novel opti- “Designing scalable FPGA-based reduction cir-
mizations for hardware floating-point units in a cuits using pipelined floating-point cores,” in 19th
modern FPGA architecture,” in 12th Interna- International Parallel and Distributed Processing
tional Conference on Field-Programmable Logic, Symposium, April 2005.
pp. 637–646, 2002.

14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'06)

0-7695-2661-6/06 $20.00
Authorized licensed use©limited
2006 to: Indian Institute of Technology Hyderabad. Downloaded on September 30,2024 at 21:21:54 UTC from IEEE Xplore. Restrictions apply.