Alternative Number Formats on
FPGAs
My work is part of a
larger project on efficient use of alternative number
formats on FPGAs.
Motivation
Signal
processing algorithms are some of the most challenging
computations. Typically, signal processing algorithms are
computationally intensive, need to be done in real-time, and require a
large dynamic range. The requirement for a large dynamic range
prohibits the use of fixed-point number systems. This leads to
the use of the floating point numbers or logarithmic number system
(which is a floating point system with a mantissa = 1 and an fixed
point exponent).
FPGA
designers started mapping floating point arithmetic units to FPGA’s in
the mid 90’s. With the increasing density of the devices, there
have been many full floating point arithmetic units implemented on a
FPGA. The dynamic range of floating point comes at the cost of
lower precision and increased complexity over fixed point.
Logarithmic number system offers similar range and error
characteristics as floating point but may have some advantages in
complexity over floating point for certain applications.
Specifically, multiplication and division are performed as addition and
subtraction respectively with logarithms. The simplification of
multiplication and division is countered by the difficulty of addition
and subtraction with logarithms. Since floating point arithmetic
is still difficult to implement on FPGAs, any gains in area or
performance that may be realized by using logarithms will help
facilitate the expansion of FPGA's domain into algorithms that
require a large dynamic range.
Research
We are
developing a logarithmic number system library in Verilog to compare it
to existing floating point libraries on placed and routed area, and
throughput latency. The designs will be compared using Xilinx
VertexII FPGAs and Xilinx’s tools. Multiplication and division
become addition and subtraction in log space and powers becomes
multiplications while addition/subtraction becomes a complicated
task. This leads us to believe that the logarithmic number system
will be advantageous for applications that require many
multiplication/division/power operations and few
addition/subtractions. However, because a logarithmic number
system chip will need to interface with floating point or fixed point
numbers as inputs and outputs, converters must be designed and included
in any design. These converters will add space and error which
may negate any advantage gained by using logs. We are trying to
characterize these tradeoffs to investigate the viability of the
logarithmic number system on an FPGA.
Current Status
This
project is completed and the findings can be found in either of the two
papers below. The high level is that due to the difficulty
of log addition and subtraction a high percentage (~50-70%) of an
algorithm must be multiplies or divides in order for a logarithm
representation to be a win if no conversion is required. If
conversion is reqired, more multiplies and divides are required to
overcome the converter overhead.
Michael Haselman, Michael Beauchamp, Aaron Wood, Scott
Hauck, Keith Underwood, K. Scott Hemmert, “Comparison of Floating
Point and
Logarithmic Number Systems on a FPGA” IEEE Symposium on
Field-Programmable Custom Computing Machines, 2005.
Masters Thesis
FCCM
05 presentation
