Accelerating seismic computations using customized number representations on FPGAs

Circuit Design: Basic Arithmetic &
Elementary Function Evaluation

After profiling range information for the variables in the target code, the second step is to map the code into a circuit design described in ASC.

As a high-level FPGA programming language, ASC provides hardware data-types, such as HWint, HWfix and HWfloat. Users can specify the bit-width values for hardware variables, and ASC automatically generates corresponding arithmetic units for the specified bit-widths. It also provides configurable options to specify different optimization modes, such as AREA, LATENCY and THROUGHPUT. In the THROUGHPUT optimization mode, ASC automatically generates a fully-pipelined circuit. These features make ASC an ideal hardware compilation tool to re-target a piece of software code onto the FPGA hardware platform.

ASC does not have inherent support for LNS numbers. This part is covered by our previous work on the LNS arithmetic library generator (Fu et al., 2007), which produces optimized LNS arithmetic units with customizable bit-width values, also in ASC format.

Thus, with support for fixed-point, floating-point and LNS arithmetic operations, the target Fortran code can be transformed into ASC C++ code in a straightforward manner. We also have interfaces provided by ASC and the LNS library generator to modify the internal settings of these arithmetic units.

In seismic applications, evaluation of elementary functions takes a large part in the application. For instance, in the first piece of target code we try to accelerate, the `complex exponential function'. A large part of the computation is to evaluate the square root and sine/cosine functions. To map these functions into efficient units on the FPGA board, we use a table-based uniform polynomial approximation approach, based on Dong-U Lee's work on optimizing hardware function evaluation (Lee et al., 2005). The evaluation of the two functions can be divided into three different phases (Muller, 1997):

• Range Reduction: reduce the range of the input variable $x$ into a small interval that is convenient for the evaluation procedure. The reduction can be multiplicative (e.g. $x' = x / 2^{2n}$ for square root function) or additive (e.g. $x' = x - 2\pi\dot n$).
• Function Evaluation: approximate the value of the function using a polynomial within the small interval.
• Range Reconstructions: map the value of the function in the small interval back into the full range of the input variable $x$.

To keep the whole unit small and efficient, we use degree-one polynomial so that only one multiplication and one addition are needed to produce the evaluation result. Meanwhile, to preserve the approximation error at a small scale, the reduced evaluation range is divided into uniform segments. Each segment is approximated with a degree-one polynomial, using the minimax algorithm. In the case of the `complex exponential' code segment, the square root function is approximated with 384 segments in the range of [0.25, 1] with a maximum approximation error of $4.74\times10^{-7}$, while the sine and cosine functions are approximated with 512 segments in the range of [0, 2] with a maximum approximation error of $9.54\times10^{-7}$.

Accelerating seismic computations using customized number representations on FPGAs