The efficiency and performance of floating-point FPGAs have been limited by long latencies and routing congestion. Furthermore, the traditional FPGA design flow, based on writing register-level hardware descriptions in Verilog or VHDL, is not well-suited to implementing complex floating-point algorithms.
Altera has developed a new floating-point design flow that aims to streamline the implementation of floating-point digital signal processing algorithms on Altera FPGAs, enabling these designs to achieve the highest levels of performance and efficiency to date. Instead of constructing a data path consisting of elementary floating-point operators (e.g., multiplication followed by addition followed by squaring), the floating-point compiler generates a data path that combines elementary operators into a single function or data path. This eliminates the redundancies present in traditional floating-point FPGA designs. Furthermore, Altera's design flow is a high-level, model-based design flow that utilizes Altera's DSP Builder Advanced Blockset with MATLAB and MathWorks Simulink. Altera expects that this high-level approach will allow FPGA designers to implement and verify complex floating-point algorithms more quickly than with traditional HDL-based design.
BDTI has conducted an independent analysis of Altera's floating-point DSP design flow. BDTI's objective was to understand the performance achievable with Altera FPGAs for high-level floating-point DSP applications and to evaluate the usability of Altera's floating-point DSP design flow. This article presents BDTI's findings, along with background information and details of the methodology used.
1. Introduction
Two examples of floating-point design
Advances in digital chips allow complex algorithms, previously limited to research, to enter common embedded computing applications. For example, linear algebra (and specifically the solution of systems involving large sets of linear equations simultaneously) has been used for many years primarily in research, where large-scale computing resources are available and real-time calculations are generally not required. Solving large systems requires matrix inversion or some type of matrix decomposition. In addition to the computational capacity requirements, these techniques can suffer from numerical instability if sufficient dynamic range is not used. Therefore, the efficient and accurate implementation of these algorithms is only practical on floating-point devices.
Altera recently introduced floating-point computing capabilities in its DSP Builder Advanced Blockset toolkit to simplify the implementation of floating-point DSP algorithms on Altera FPGAs and improve the performance and efficiency of floating-point designs compared to traditional FPGA design techniques. In a previous article [1], BDTI analyzed and evaluated the performance and efficiency of Altera's Quartus II v11.0 software toolkit on an example implementation of the single-channel floating-point Cholesky solver, synthesized for the 40 nm Stratix IV and Arria IV FPGAs.
In this article, we evaluate the effectiveness of Altera's proposed solution using the new version 12.0 of the Quartus II software tool and explore the capabilities of Altera's 28 nm Stratix V and Arria V FPGAs. To perform this evaluation, BDTI focused on solving a large number of simultaneous linear equations using two types of decompositions: a multichannel Cholesky matrix decomposition and QR decomposition with the Gram-Schmidt process. These decompositions, along with forward and backward substitutions, provide a solution for the vector x in a simultaneous set of linear equations of the form Ax = B.
Matrix decomposition is used in numerous military radar applications, such as Space-Time Adaptive Processing (STAP), and various estimation problems in digital communications. QR decomposition is commonly used on any m x n matrix A, while Cholesky decomposition is the most widely used algorithm for a square, symmetric, positive-definite matrix due to its high computational efficiency. Both decompositions employ computationally intensive algorithms that require high data precision, necessitating floating-point operations. Furthermore, the two examples discussed in this article utilize scalar products and nested loops within the algorithm, operations which are prevalent in a wide range of digital signal processing applications related to linear algebra and finite impulse response (FIR) filters.
The examples described in this article solve simultaneous sets of linear equations of complex data using both methods and present the results. Using the QR solver, as explained in Section 4, an Altera Stratix V FPGA is capable of performing 315 matrix decompositions per second of size 400x400, at a speed of 203 MHz, achieving 162x10⁹ floating-point operations per second (GFLOPS).
The two design examples evaluated in this article are part of the DSP Builder v12.0 software tool or can be ordered from [
Floating-Point Design Flow:
FPGAs have not generally been the platform of choice for high-level floating-point applications. Although FPGA vendors provide floating-point primitive libraries, the performance of FPGAs in floating-point applications has been severely limited. The inefficiency of traditional floating-point FPFA designs is partly due to the highly segmented nature and arithmetic structures of floating-point operators, which create high data path latency and routing congestion. In turn, these latencies create difficult-to-manage problems in data-dependent designs. The end result is often a design with a low operating frequency.
Altera's DSP Builder Advanced Blockset tool flow addresses these obstacles at both the architecture and system design levels. Altera's floating-point compiler combines large sections of the data path into a single floating-point function instead of generating them by composing elementary floating-point operators. This is accomplished by analyzing the bit growth in the data path and choosing the optimal input normalization to allocate sufficient precision along the data path in order to eliminate as many normalization and denormalization steps as possible, as shown in Figure 1. The IEEE 754 format is used only at the data path boundaries; larger mantissa widths are used in the data path itself to increase dynamic range and decrease the need for normalization and denormalization steps between successive operators. Normalization and denormalization functions use fast barrel shifters with a width of up to 48 bits for a single-precision floating-point number. This consumes a significant amount of logic and routing resources and is the main reason why FPGA-based floating-point implementations have not been efficient. The combined data path methodology eliminates a significant number of fast barrel shifters. Higher-precision mantissa multiplications utilize Altera's 27-bit x 27-bit multiplier mode on the Stratix V and Arria V devices. Figure 1(b) compares the combined data path methodology for the simple case of a string with two adders and the traditional implementation shown in Figure 1(a). The combined data path in Figure 1(b) eliminates interoperator redundancy by suppressing the denormalization of the first adder's output and the normalization of the second adder's input. The elimination of added logic and routing, along with the use of hardware multipliers, makes timing and latency predictable for complex data paths. Single- and double-precision IEEE 754 floating-point algorithms are implemented with fewer logic resources and higher performance. Altera claims that a combined data path reduces logic resources and latency by 50% compared to the equivalent data path implemented using elementary operators [2]. Furthermore, as a result of the wider representation of internal data, the accuracy of the data is generally higher than that achieved by a library using elementary IEEE 754 floating-point operators.
Altera's floating-point DSP design workflow incorporates Altera's DSP Builder Advanced Blockset and Quartus II software tool, as well as MATLAB and MathWorks Simulink. The Simulink environment allows the designer to work at the algorithmic behavior level to describe, debug, and verify complex systems. Simulink features such as data type propagation and vector data processing are integrated into DSP Builder Advanced Blockset, enabling the designer to quickly explore the algorithmic design space.
To evaluate the efficiency and performance of Altera's floating-point design flow, BDTI used the DSP Builder Advanced Blockset tool to validate two examples, both of which involved solving a set of simultaneous linear equations using complex data types in a single-precision floating-point representation. One solution was obtained using Cholesky decomposition, while the other employed QR decomposition via the Gram-Schmidt process. Section 2 of this article describes the implementation of the two floating-point examples. Section 3 explains BDTI's experience with the design flow and the toolkit. Section 4 presents the performance of the implementation using two Altera FPGAs: the high-end, mid-sized Stratix V 5SGSMD5K2F40C2n and the mid-range Arria V 5AGTFD7K3F40I3N. Finally, Section 5 presents BDTI's conclusions.
2. Implementation
Background Information
Numerous applications involve sets of linear equations of the form Ax = b. Whether it's an optimization problem involving linear least squares, a Kalman filter for predicting a problem, or estimation in a MIMO communication channel, the problem still consists of finding a numerical solution for a set of linear equations of the form Ax = b. For a general matrix of size m by n, where m is the height of the matrix and n its width, QR decomposition can be used to solve for the vector x. The algorithm decomposes A into an orthonormal matrix Q of size m by n and an upper triangular matrix R of size n by n. Since Q is orthonormal, QTQ = I and Rx = QTb. Since R is an upper triangular matrix, x can be easily solved for by back substitution without even needing to invert the original matrix A. In the QR example in this article, we work with overdetermined matrices where m ≠ n.
When matrix A is symmetric and positive definite, as in the covariance matrices that arise in many problems, Cholesky decomposition and solver are commonly used. The algorithm finds the inverse of matrix A, thus solving the vector x as x = A⁻¹b. Cholesky decomposition is at least twice as efficient as QR decomposition, depending on the decomposition algorithms used. Since these decomposition algorithms are recurrent in nature and include division, a large numerical dynamic range is required as the matrix size increases. In most cases, even for matrices as small as 4x4, for example, in MIMO channel estimation, floating-point operations are performed. For larger systems that require higher performance, such as in military applications, floating-point speed is often prohibitive for embedded systems. Designers frequently abandon the algorithm altogether in search of a less optimal solution or resort to high-performance floating-point processors, with the resulting increase in cost and design effort.
Author:
By the Berkeley Design Technology, Inc. team. October 2012
(Continued in February)
