FPGAs offer a powerful and flexible platform to build complex systems on. But the potential - both in density and clock frequency - is often missed. In this work we present a massively parallel FFT, which can process a 32 K point FFT with 32-parallel IEEE-754 single-precision floatingpoint streams of complex data. Each core uses 1281 DSP Blocks, and can be packed into a near 100 % DSP Block density in an Altera Agilex-7 FPGA. Six such cores have been instantiated in a system, using 90 % of the device capability. In all cases our designs close timing at nearly 770 MHz, which is the restricted frequency of the DSP Block in floatingpoint mode. The contributions of this work are manifold. We demonstrate approaches that can be used to fill even larger FPGAs to high density with high performance. We also introduce optimizations for the FFT that can be used by all types of (including non-FFT) applications, from simple implementations to the very large parallel examples we use to demonstrate our research.

Multipliers have always been an important component of computer architecture, but the increasing relevance of Artificial Intelligence (AI) has brought about a massive increase in the number of multipliers on all compute platforms. At the same time, multiplier use for signal processing has also increased unabated. Multiplier architectures have not changed appreciably over the recent past. In this paper, we introduce a new technique for calculating partial products, which can be used with known compression tree and adder combinations. We demonstrate the efficiency of our new multiplier by reporting results from 800MHz to 2GHz in a current 7nm production library, and comparing to the well-known modified Booth’s radix 4 and radix 8 architectures.

Zero-Knowledge Proofs (ZKPs) allow proving a statement's correctness without revealing anything else, enabling privacy in applications like blockchains and digital voting. Recently, Zero-knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARKs) have helped address ZKPs' scalability challenges and gained significant attention. This paper presents a novel scalable FPGA architecture for accelerating the zk-SNARK prover's compute-intensive multi-scalar multiplication (MSM) operation. The architecture exploits MSM's inherent parallelism, using optimized IP for modular arithmetic. Implemented with Intel OneAPI for FPGAs, it achieves 110x-150x speedup over software for the BLS12-381 and BN128 elliptic curves, utilizing a generic Jacobian coordinate system.

Matrix multiplication is a fundamental operation in many fields including artificial intelligence and machine learning, and it often requires significant computational resources. FPGAs have always been a great platform for accelerating such calculations thanks to their inherent parallelism and flexibility regarding data movement. The newly released Agilex-5 FPGA devices introduce several AI-specific hardware features that complement the traditional DSP Block functionality. The fixed-point Tensor Mode of the DSP Block exposes twenty 8-bit signed multipliers organized into two 10-element dot products, having one set of inputs fed from internal DSP Block registers. In this paper, based on the philosophy of efficiently utilizing the low-level features of the new DSP Block, we make use of these structures and construct a flexible 8-bit matrix multiplication engine. The generic matrix-multiplication architecture presented here achieves at steady-state 100% compute resource utilization (no idle states). In the 810-DSP configuration, the engine achieves over 750MHz on an Agilex-5 (fastest speedgrade) device with a throughput of 24.75TOPs and an energy efficiency of 1.65TOPs/W.

Modular multiplication is a key kernel in many computing fields. What makes this function so challenging are the very large word sizes – sometimes in the thousands of bits – that are typically required for the target applications. In this paper we propose a modular multiplication implementation based on a multi-stage hybrid reduction technique. Our proposed approach uses a parameterized number of multiplier-based reduction stages followed by a memory-based reduction. This construction allows for the multiplier-based stages to take advantage of Karatsuba multiplication, resulting in a reduced number of DSP Blocks. Our method also allows specifying the number of multiplier-based stages which adjusts the ratio of multipliers to memory blocks. The resource utilization of the proposed architecture outperforms the existing state-of-the-art modular multiplication designs while offering a user-defined way of distributing resources between memory and DSP Blocks.

tThe CSAIL2019 time-lock puzzle is an unsolved cryptographic challenge introduced by Ron Rivest in 2019, replacing the solved LCS35 puzzle. Solving these types of puzzles requires large amounts of intrinsically sequential computations, with each iteration performing a very large (3,072-bit for CSAIL2019) modular multiplication operation. The complexity of each iteration is several times greater than known field-programmable gate array (FPGA) implementations, and the number of iterations has been increased by about 1,000x compared with LCS35. Because of the high complexity of this new puzzle, a number of intermediate, or milestone, versions of the puzzle have been specified. In this article, we present several FPGA architectures for the CSAIL2019 solver, which we implement on a medium-sized Intel Agilex device. We develop a new multi-cycle modular multiplication method, which is flexible and can fit on a wide variety of sizes of current FPGAs. We introduce a class of multi-cycle squarer-based architectures that allow for better resource and area trade-offs. We also demonstrate a new approach for improving the fitting and timing closure of large, chip-filling arithmetic designs. We used the solver to compute the first 23 out of 28 milestone solutions of the puzzle, which are the first reported results for this problem.

This work presents a set of techniques that allow implementing low-precision floating-point adders based on the embedded hard FP DSP Blocks available in contemporary Intel FPGAs. The presented architectures exploit the properties of these formats during exponent handling to obtain efficient implementations in terms of logic utilization. For instance, a half-precision floating-point adder implementation only requires 1 DSP Block and no extra logic. The newly available IEEE-754 compliant implementations can then be used as drop-in replacements in designs making use of these exact floating-point adder blocks. We present the case of a floating-point FFT implementation that benefits from these proposed architectures in order to substantially reduce logic utilization at the expense of using more DSP blocks.

The CSAIL2019 time-lock puzzle is an unsolved cryptographic challenge introduced by Ron Rivest in 2019, replacing the solved LCS35 puzzle. Solving these types of puzzles requires large amounts of intrinsically sequential computations (i.e. computations which cannot be parallelized), with each iteration performing a very large (3072-bit in the case of CSAIL2019) modular multiplication operation. The complexity of each iteration is several times greater than known FPGA implementations, and the number of iterations has been increased by about 1000x compared to LCS35. Because of the high complexity of this new puzzle, a number of intermediate, or milestone versions of the puzzle have been specified.

Modular exponentiation, especially for very large integers of hundreds or thousands of bits, is a commonly used function in popular cryptosystems such as RSA. The complexity of this algorithm is partly driven by the very large word sizes, which require many - often millions - of primitive operations in a CPU implementation, or a large amount of logic when accelerated by an ASIC. FPGAs, with their many embedded DSP resources have started to be used as well. In almost all cases, the calculations have required multiple - occasionally many - clock cycles to complete. Recently, blockchain algorithms have required very low-latency implementations of modular multiplications, motivating new implementations and approaches.In this paper we show nine different high performance modular exponentiation for 1024-bit operands, using a 1024-bit modular multiplication as it’s core. Rather than just showing a number of completed designs, our paper shows the evolution of architectures which lead to different resource mix options. This will allow the reader to apply the examples to different FPGA targets which may have differing ratios of logic, memory, and embedded DSP blocks. In one design, we show a 1024b modular multiplier requiring 83K ALMs and 2372 DSPs, with a delay of 21.21ns.

The advent of AI has driven the exploration of high-density low-precision arithmetic on FPGAs. This has resulted in new methods in mapping both arithmetic functions as well as dataflows onto the fabric, as well as some changes to the embedded DSP Blocks. Technologies outside of the FPGA realm have also evolved, such as the addition of tensor structures for GPUs, as well as the introduction of numerous AI ASSPs, all of which have a higher claimed performance and efficiency than current FPGAs. In this article, we will introduce the Stratix 10 NX device, which is a variant of FPGA specifically optimized for the AI application space. In addition to the computational capabilities of the standard programmable soft-logic fabric, a new type of DSP Block provides the dense arrays of low-precision multipliers typically used in AI implementations. The architecture of the block is tuned for the common matrix-matrix or vector-matrix multiplications in AI, with capabilities designed to work efficiently for both small and large matrix sizes. The base precisions are INT8 and INT4, along with shared exponent support to support block FP16 and block FP12 numerics. All additions/accumulations can be done in INT32 or IEEE-754 single precision floating point (FP32), and multiple blocks can be cascaded together to support larger matrices. We will also describe methods by which the smaller precision multipliers can be aggregated to create larger multipliers that are more applicable to standard signal processing requirements. In the AI market, the FPGA must compete directly with other types of devices, rather than occupy a unique niche. Deterministic system performance is as important as the performance of individual FPGA elements, such as logic, memory, and DSP. We will show that the feed forward datapath structures that are needed to support the typical AI matrix-vector and matrix-matrix multiplication operations can consistently close timing at over 500 MHz on a mid-speed grade device, even if all of the Tensor Blocks on the device are used. We will also show a full-chip NPU processor implementation that out performs GPUs at the same process node for a variety of AI inferencing workloads, even though it has a lower operating frequency of 365 MHz. In terms of overall compute throughput, Stratix 10 NX is specified at 143 INT8/FP16 TOPs/FLOPs or 286 INT4/FP12 TOPS/FLOPs. Depending on the configuration, power efficiency is in the range of 1–4 TOPs or TFLOPs/W.

The advent of AI has driven the adoption of high density low precision arithmetic on FPGAs. This has resulted in new methods in mapping both arithmetic functions as well as dataflows onto the fabric, as well as some changes to the embedded DSP Blocks. Technologies outside of the FPGA realm have also evolved, such as the addition of tensor structures for GPUs, and also the introduction of numerous AI ASSPs, all of which have a higher claimed performance and efficiency than current FPGAs. In this paper we will introduce the Stratix 10 NX device (NX), which is a variant of FPGA specifically optimized for the AI application space. In addition to the computational capabilities of the standard programmable soft logic fabric, a new type of DSP Block provides the dense arrays of low precision multipliers typically used in AI implementations. The architecture of the block is tuned for the common matrix-matrix or vector-matrix multiplications in AI, with capabilities designed to work efficiently for both small and large matrix sizes. The base precisions are INT8 and INT4, along with shared exponent support for support block floating point FP16 and FP12 numerics. All additions/accumulations can be done in INT32 or IEEE754 single precision floating point (FP32), and multiple blocks can be cascaded together to support larger matrices. We will also describe methods by which the smaller precision multipliers can be aggregated to create larger multiplier that are more applicable to standard signal processing requirements. In terms of overall compute throughput, Stratix 10 NX achieves 143 INT8/FP16 TOPs/FLOPs, or 286 INT4/FP12 TOPS/FLOPs at 600MHz. Depending on the configuration, power efficiency is in the range of 1-4 TOPs or TFLOPs/W.

Encryption - especially the key exchange algorithms such as RSA - is an increasing use-model for FPGAs, driven by the adoption of the FPGA as a SmartNIC in the datacenter. While bulk encryption such as AES maps well to generic FPGA features, the very large multipliers required for RSA are a much more difficult problem. Although FPGAs contain thousands of small integer multipliers in DSP Blocks, aggregating them into very large multipliers is very challenging because of the large amount of soft logic required - especially in the form of long adders, and the high embedded multiplier count. In this paper, we describe a large multiplier architecture that operates in a multi-cycle format and which has a linear area/throughput ratio. We show results for a 2048-bit multiplier that has a latency of 118 cycles, inputs data every 9th cycle and closes timing at 377MHz in an Intel Arria 10 FPGA, and over 400MHz in a Stratix 10. The proposed multiplier uses 1/9 of the DSP resources typically used in a 2048-bit Karatsuba implementation, showing a perfectly linear throughput to DSP-count ratio. Our proposed solution outperforms recently reported results, in either arithmetic complexity - by making use of the Karatsuba techniques, or in scheduling efficiency - embedded DSP resources are fully utilized.

Barrett's algorithm is the most commonly known method of performing a modular multiplication, which is the core of many modern encryption algorithms such as RSA. Barrett's algorithm requires an accurate quotient estimation which in turn requires accurate multiplications. These multiplications operating on word sizes of thousands of bits are particularly expensive to implement in FPGAs, requiring many hundreds or even thousands of embedded DSP components along with large amounts of logic and routing. In this work we show that approximate quotient estimates as results of aggressive multiplier truncations can significantly reduce implementation cost. The looser modified Barrett's output [0; YM) is reduced to [0; M) using a shallow reduction technique based on table lookups and wide additions, taking advantage of new techniques which have recently been introduced for FPGA. We first use these techniques to develop an improved standard Barrett's implementation for 1024b modular multiplication, followed by our approximate method which reduces logic cost in the LSB truncated multiplier by approximately 10%. The effect is more pronounced for very large word sizes, where our relaxed error bounds in the LSB truncated multiplication can reduce the number of operations by 20%.

The importance of AI to FPGA has resulted in ever increasing low precision hard arithmetic features in newer devices. Many FPGAs, including those from Achronix, Intel, and Xilinx, have significantly increased the density of INT8 and INT9 embedded multipliers. Mainstream devices with these enhanced densities still support the traditional intermediate integer (typically 18-bit) multipliers, with IEEE-754 floating-point now becoming more prevalent as well.Recently, Intel introduced the Stratix 10 NX FPGA, which is targeted specifically at AI acceleration. This device contains a new type of AI-specific DSP Block with approximately an order of magnitude higher INT8 density than previous FPGA industry DSP Blocks. Larger standard FPGA integer precisions, however, are not directly supported. Intel has described some methods of aggregating larger multipliers from the NX Blocks, but these are somewhat smaller than typically used by DSP applications. Larger multiplications can also be useful for other AI applications, such as found in training. In this paper, we introduce the concept of signed tuples, which can be used to assemble signed multipliers into more useful larger precision multipliers by leveraging FPGA soft-logic inexpensively. We demonstrate several constructions of INT16 multipliers, with some modes requiring less than 3 ALMs per INT16 multiplier when implemented in a tensor format. We also describe the application of these methods to even larger multipliers and alternate constructs such as complex multiplication. We show that there is essentially no performance degradation or system fitting impact from our method. The mid-size NX device can support up 33 TOPs INT16 (from 29,700 constructed INT16 multipliers on a mid-speed grade device) with this approach, which is higher than any other current or announced monolithic die FPGA. Our methods are not limited to FPGA, or any particular starting precision, and so may be used for other aggregations as well.

International audience

FPGAs are becoming interesting solutions for neural network training acceleration. Efficient implementation of dot-products, as part of matrix-matrix multiply engines, plays a key role towards this. The now de facto standard involves the matrix multiplication on bfloat16 inputs, with all reductions be performed in single-precision arithmetic. We present here a generic hybrid dot-product implementation that: (1) has a user-defined accuracy knob and (2) targets a user-defined logic/DSP ratio. Since our architecture is very specialized to a given target device, we discuss the challenges in generating this architecture automatically.

FPGAs are now being commonly used in the datacenter as smart Network Interface Cards (NICs), with cryptography as one of the strategic application areas. Public key cryptography algorithms in particular require arithmetic with thousands of bits of precision. Even an operation as simple as addition can be difficult for the FPGA when dealing with large integers, because of the high resource count and high latency needed to achieve usable performance levels with known methods. This paper examines the architecture and implementation of high-performance integer adders on FPGAs for widths ranging from 1024 to 8192 bits, in both single-instance and many-core chip-filling configurations. For chip-filling designs the routing impact of these wide busses are assessed, as they often have an impact outside the immediate locality of the structures. The architectures presented in this work show 1 to 2 orders magnitude reduction in the area-latency product over commonly used approaches. Routing congestion is managed, with near 100% logic efficiency (packing) for the adder function. Performance for these largely automatically placed designs are approximately the same as for carefully floor-planned non-arithmetic applications. In one example design, we show a 2048 bit adder in 5021 ALMs, with a latency of 6 clock cycles, at 628 MHz in a Stratix 10 E-2 device.

Interactive intelligent services, such as smart web search, are important datacenter workloads. They rely on dataintensive deep learning (DL) algorithms with strict latency constraints and thus require balancing both data movement and compute capabilities. As such, a persistent approach that keeps the entire DL model on-chip is becoming the new norm for realtime services to avoid the expensive off-chip memory accesses. This approach is adopted in Microsoft's Brainwave and is also provided by Nvidia's cuDNN libraries. This paper presents a comparative study of FPGA, GPU, and FPGA+ASIC in-package solutions for persistent DL. Unlike prior work, we offer a fair and direct comparison targeting common numerical precisions (FP32, INT8) and modern high-end FPGA (Intel® Stratix®10), GPU (Nvidia Volta), and ASIC (10 nm process), all using the persistent approach. We show that Stratix 10 FPGAs offer 2.7× (FP32) to 8.6× (INT8) lower latency than Volta GPUs across RNN, GRU, and LSTM workloads from DeepBench. The GPU can only utilize ~6% of its peak TOPS, while the FPGA with a more balanced on-chip memory and compute can achieve much higher utilization (~57%). We also study integrating an ASIC chiplet, TensorRAM, with an FPGA as system-in-package to enhance on-chip memory capacity and bandwidth, and provide compute throughput matching the required bandwidth. We show that a small 32 mm2 TensorRAM 10nm chiplet can offer 64 MB memory, 32 TB/s on-chiplet bandwidth, and 64 TOPS (INT8). A small Stratix 10 FPGA with a TensorRAM (INT8) offers 15.9× better latency than GPU (FP32) and 34× higher energy efficiency. It has 2× aggregate on-chip memory capacity compared to a large FPGA or GPU. Overall, our study shows that the FPGA is better than the GPU for persistent DL, and when integrated with an ASIC chiplet, it can offer a more compelling solution.

Interactive intelligent services (e.g., smart web search) are becoming essential datacenter workloads. They rely on data-intensive artificial intelligence (AI) algorithms that do not use batch computation due to their tight latency constraints. Since off-chip data accesses have higher latency and energy consumption than on-chip accesses, a persistent AI approach with the entire model stored in on-chip memory is becoming the new norm for real-time AI. This approach is the cornerstone of Microsoft's Brainwave FPGA-based AI cloud and was recently added to Nvidia's cuDNN library. In this work, we implement, optimize and evaluate a Brainwave-like neural processing unit (NPU) on a large Stratix-10 FPGA. We benchmark it against a large Nvidia Volta GPU running cuDNN persistent AI kernels. Across real-time persistent RNN, GRU, and LSTM workloads, we show that Stratix-10 offers ~3× (FP32) and ~10× (INT8) better latency than GPU (FP32), which uses only ~6% of its peak throughput. Then, we propose TensorRAM, an ASIC chiplet for persistent AI that is 2.5D integrated with an FPGA in the same package. TensorRAM enhances the on-chip memory capacity and bandwidth, with enough multi-precision INT8/4/2/1 throughput to match that bandwidth. Multiple TensorRAMs can be integrated with Stratix-10. Our evaluation shows that a small 32-mm2 TensorRAM on 10nm offers 64MB of SRAMs with 32TB/s on-chiplet bandwidth and 64 TOP/s (INT8). A small Stratix-10 with a TensorRAM (INT8) offers 16× better latency and 34× energy efficiency compared to GPU (FP32). Overall, Stratix-10 with TensorRAM offers compelling and scalable persistent AI solutions.

With the advent of machine learning as perhaps the most high-profile application area for FPGAs, there is a compelling reason to improve the provision of smaller precision arithmetic on these devices. INT8 is commonly used for AI inferencing, and along with some additional soft logic for exponent handling, can be an effective solution for training as well. This paper describes techniques for efficiently extracting INT8 multipliers from commonly available INT18 multipliers found in many modern FPGAs. A small amount of soft logic - as little as 7 ALMs per INT8 multiplier - is required to provide pre or post multiplier correction to calculate two INT8 multiplies from a single 18x18 multiplier. We present two configurations for both signed and unsigned representations where two multiplications share one input operand. In addition to the individual INT8 variants, we present full device cases of 22,400 INT8 multipliers organized as DOT32 product arrays, with the soft logic tightly bound to the INT18 based DSP Blocks. A majority of the soft logic and routing in the device is left untouched, and available for application development.

QR decomposition (QRD) is of increasing importance for many current applications, such as wireless and radar. Data dependencies in known algorithms and approaches, combined with the data access patterns used in many of these methods, restrict the achievable performance in software programmable targets. Some FPGA architectures now incorporate hard floating-point (HFP) resources, and in combination with distributed memories, as well as the flexibility of internal connectivity, can support high-performance matrix arithmetic. In this work, we present the mapping to parallel structures with inter-vector connectivity of a new QRD algorithm. Based on a Modified Gram-Schmidt (MGS) algorithm, this new algorithm has a different loop organization, but the dependent functional sequences are unchanged, so error analysis and numerical stability are unaffected. This work has a theoretical sustained-to-peak performance close to 100% for large matrices, which is roughly three times the functional density of the previously best known implementations. Mapped to an Intel Arria 10 device, we achieve 80us for a 256x256 single precision real matrix, for a 417 GFLOP equivalent. This corresponds to a 95% sustained to peak ratio, for the portion of the device used for this work.

Machine Learning is now one of the most active application areas for FPGAs. The more complex recurrent neural network (RNN) topologies require multiple non-linear activation functions, mainly tanh and sigmoid, per iteration. In this paper we will examine the impact of activation function quality - in both area and (especially) latency - on RNN performance. We present a number of architectures for these functions, for both half precision (IEEE754-2008 FP16) and single precision (IEEE754 FP32) floating-point representations. We describe how the IEEE754 single precision hard floating point (HFP) blocks available in current FPGAs ease the implementation of these functions, and we also give an alternate method the tanh function based on integer arithmetic. With the combination of exceptional internal memory bandwidth, direct support of high performance floating point dot products, and the new activation functions, we show that FPGAs can be a highly effective vehicle for these type of neural networks.

Efficient fixed-point function implementation is critical in many FPGA application domains including convolutional neural networks, computer vision, and communication systems. In this work we focus on functions of the form xp, with p ∈ {-1,-1/2,1/2} as part of a function generator targeting FPGAs. The generator implements architectures based on new but also existing algorithms. In this work we present three distinct methods implemented in this generator that outperform state-of-the-art implementations for certain configurations. Traditionally, fixed-point function implementation requires a normalization stage, compute and denormalization (reconstruction) of the result. The first proposed method implements the function holistically, thus saving the logic and latency required during the normalize and reconstruct stages. The second proposed method is based on a novel second order Taylor implementation. The third method is based on the cubic convergence of Halley's method, which is novel in this context. The proposed methods are compared and contrasted against state-of-the art implementations in the context of FPGA targets.

This paper presents an implementation of the floating-point (FP) tangent function, optimized for an FPGA containing hard floating point (HFP) DSP Blocks. This function inputs values in the interval [-π/2,π/2], uses the IEEE-754 single-precision (SP) format, and has an accuracy conforming to OpenCL requirements. The presented architecture is based on a combination of mathematical identities and properties of the tangent function in FP. The resultant design outperforms generic polynomial approximation methods targeting the same resource utilization spectrum, and provides better resource trade-offs than classical CORDIC-based implementations. The presented work is widely available as part of the Intel DSP Builder Advanced Blockset.

Hardware applications in an industrial context often have tight area, latency and throughput requirements or a specific combination thereof. This paper presents a method to improve area and throughput figures for folded circuits generated during a model-based hardware design process. The method targets FPGA implementations and is based on the automatic combination of isomorphic subgraphs and the detailed consideration of pipelined primitive operations for folding core scheduling. In the course of a design space exploration, the user is provided with fine-grain control over the area/throughput trade-off.

In this article we present a novel method for implementing floating point (FP) elementary functions using the new FP single precision addition and multiplication features of the Arria 10 and Stratix 10 DSP Block architecture. Our application examples are$\log (x)$and$\exp (x)$, two of the most commonly required functions for emerging datacenter and computing FPGA targets. We explain why the combination of new FPGA technology, and at the same time, a massive increase in computing performance requirement, fuels the need for this work. We show a comprehensive error analysis, and discuss various implementation trade-offs that demonstrate that the hard FP (HFP) Blocks, in conjunction with the traditional flexibility and connectivity of the FPGA, can provide a robust and high performance solution. The architectures presented in this work meet OpenCL accuracy requirements. Our methods map extensively to embedded structures, and therefore result in significant reduction in logic resources and routing stress compared to current methods. The methods allow leveraging the routing architectures introduced in the Stratix 10 device which results in high-function performance.

In this paper we will present a novel method for implementing floating point (FP) elementary functions using the new FP single precision addition and multiplication features of the Altera Arria~10 DSP Block architecture. Our application example will use log(x), one of the most commonly required functions for emerging datacenter and computing FPGA targets. We will explain why the combination of new FPGA technology, and at the same time, a massive increase in computing performance requirement, fuels the need for this work. We show a comprehensive error analysis, both for the overall function, and each subsection of the architecture, demonstrating that the hard FP (HFP) Blocks, in conjunction with the traditional flexibility and connectivity of the FPGA, can provide a robust and high performance solution. These methods create a highly accurate single precision IEEE754 function, which is OpenCL conformant. Our methods map directly to almost exclusively embedded structures, and therefore result in significant reduction in logic resources and routing stress compared to current methods, and demonstrate that newly introduced FPGA routing architectures can be leveraged to use almost no soft resources. We also show that the latency of the log(x) function can be changed independently of the architecture and function, allowing the performance of the function to be adjusted directly to the system clock rate.

This paper describes the architecture and implementation, from both the standpoint of target applications as well as circuit design, of an FPGA DSP Block that can efficiently support both fixed and single precision (SP) floating-point (FP) arithmetic. Most contemporary FPGAs embed DSP blocks that provide simple multiply-add-based fixed-point arithmetic cores. Current FP arithmetic FPGA solutions make use of these hardened DSP resources, together with embedded memory blocks and soft logic resources, however, larger systems cannot be efficiently implemented due to the routing and soft logic limitations on the devices, resulting in significant area, performance, and power consumption penalties compared to ASIC implementations. In this paper we analyse earlier proposed embedded FP implementations, and show why they are not suitable for a production FPGA. We contrast these against our solution -- a unified DSP Block -- where (a) the SP FP multiplier is overlaid on the fixed point constructs, (b) the SP FP Adder/Subtracter is integrated as a separate unit, and (c) the multiplier and adder can be combined in a way that is both arithmetically useful, but also efficient in terms of FPGA routing density and congestion. In addition, a novel way of seamlessly combining any number of DSP Blocks in a low latency structure will be introduced. We will show that this new approach allows a low cost, low power, and high density FP platform on current production 20nm FPGAs. We also describe a future enhancement of the DSP block that can support subnormal numbers.

This work describes the architecture of a new FPGA DSP block supporting both fixed and floating point arithmetic. Each DSP block can be configured to provide one single precision IEEE-754 floating multiplier and one IEEE-754 floating point adder, or when configured in fixed point mode, the block is completely backwards compatible with current FPGA DSP blocks. The DSP block operating frequency is similar in both modes, in the region of 500MHz, offering up to 2 GMACs fixed point and 1 GFLOPs performance per block. In floating point mode, support for multi-block vector modes are provided, where multiple blocks can be seamlessly assembled into any size real or complex dot products. By efficient reuse of the fixed point arithmetic modules, as well as the fixed point routing, the floating point features have only minimal power and area impact. We show how these blocks are implemented in a modern Arria 10 FPGA family, offering over 1 TFLOPs using only embedded structures, and how scaling to multiple TFLOPs densities is possible for planned devices.

This tutorial describes tools for efficiently implementing floating point applications on FPGAs. We present both the SDK for OpenCL and DSP Builder Advanced Blockset and show that they can be effectively used to implement many floating point applications. The methods for optimizing application performance are also described.

Industrial applications often require processing data with large dynamic ranges at low sample rates. As algorithms become more complex, handling the data range of variables required for fixed-point implementations becomes time consuming, and can also lead to inefficient designs. Floating-point solutions leverage these limitations trading automatic data range handling for a usually higher implementation cost. The adoption of floating-point solutions for this class of applications is conditioned by area and performance requirements. In this paper we present a low-cost floating-point unit which can either be used standalone, or can be attached to a RISC microprocessor. The proposed unit targets modern, multiplier-based FPGAs, computes efficiently costly operations: ×, ÷, 1/x, √x and 1√x, requires less than 700LE and 4-9bit multipliers on a CycloneIV and runs close to 150MHz.

Efficient elementary function implementations require primitives optimized for modern FPGAs. Fixed-point function generators are one such type of primitives. When built around piecewise polynomial approximations they make use of memory blocks and embedded multipliers, mapping well to contemporary FPGAs. Another type of primitive which can exploit the power series expansions of some elementary functions is floating-point polynomial evaluation. The high costs traditionally associated with floating-point arithmetic made this primitive unattractive for elementary function implementation on FPGAs. In this work we present a novel and efficient way of implementing floating-point polynomial evaluators on a restricted input range. We show on the atan(x) function in double precision that this very different technique reduces memory block count by up to 50% while only slightly increasing DSP count compared to the best implementation built around polynomial approximation fixed-point primitives.

This paper presents an FPGA-specific implementation of the floating-point tangent function. The implementation inputs values in the interval [-π/2,π/2], targets the IEEE-754 single-precision format and has an accuracy of 1 ulp. The proposed work is based on a combination of mathematical identities and properties of the tangent function in floating point. The architecture was designed having the {Stratix-IV} DSP and memory blocks in mind but should map well on any contemporary FPGA featuring embedded multiplier and memory blocks. It outperforms generic polynomial approximation targeting the same resource spectrum and provides better resources trade-offs than classical CORDIC-based implementations.The presented work is widely available as being part of the Altera DSP Builder Advanced Blockset.

Many applications require the evaluation of polynomials having floating-point coefficients - one example is rational polynomial approximation, often used to implement some special functions. The most resource efficient polynomial evaluation scheme (Horner) is costly to implement on FPGAs due to the high cost associated with floating-point arithmetic. Floating-point adders are particularly costly due to their alignment stages requiring large barrel shifters. In this work we present a novel FPGA-specific technique for evaluating polynomials using the Horner scheme. Our technique removes the majority of alignment shifters present in floating-point adders by building a fused evaluation operator. It pushes the possible alignment values of the monomials into tables containing multiple shifted coefficient instances which are selected using the exponent of the input argument. Compared to operator assembly this work reduces circuit latency by 30-50% and logic consumption by 40-60%. Our work can be easily extended to other polynomial evaluation methods.

The high performance and capacity of current FPGAs makes them suitable as acceleration co-processors. This article studies the implementation, for such accelerators, of the floating-point power function x y as defined by the C99 and IEEE 754-2008 standards, generalized here to arbitrary exponent and mantissa sizes. Last-bit accuracy at the smallest possible cost is obtained thanks to a careful study of the various subcomponents: a floating-point logarithm, a modified floating-point exponential, and a truncated floating-point multiplier. A parameterized architecture generator in the open-source FloPoCo project is presented in details and evaluated.

Floating-point division is a very costly operation in FPGA designs. High-frequency implementations of the classic digit-recurrence algorithms for division have long latencies (of the order of the number fraction bits) and consume large amounts of logic. Additionally, these implementations require important routing resources, making timing closure difficult in complete designs. In this paper we present two multiplier-based architectures for division which make efficient use of the DSP resources in recent Altera FPGAs. By balancing resource usage between logic, memory and DSP blocks, the presented architectures maintain high frequencies is full designs. Additionally, compared to classical algorithms, the proposed architectures have significantly lower latencies. The architectures target faithfully rounded results, similar to most elementary functions implementations for FPGAs but can also be transformed into correctly rounded architectures with a small overhead. The presented architectures are built using the Altera DSP Builder Advanced framework and will be part of the default blockset.

Solving the Table Maker's Dilemma, for a given function and a given target floating-point format, requires testing the value of the function, with high precision, at a very large number of consecutive values. We give an algorithm that allows for performing such computations on a very regular architecture, and present an FPGA implementation of that algorithm.

Integer addition is a pervasive operation in FPGA designs. The need for fast wide adders grows with the demand for large precisions as, for example, required for the implementation of IEEE-754 quadruple precision and elliptic-curve cryptography. The FPGA realization of fast and compact binary adders relies on hardware carry chains. These provide a natural implementation environment for the ripple-carry addition (RCA) scheme. As its latency grows linearly with operand width, wide additions call for acceleration, which is quite reasonably achieved by addition schemes built from parallel RCA blocks. This study presents FPGA-specific arithmetic optimizations for the mapping of carry-select and carry-increment adders targeting the hardware carry chains of modern FPGAs. Different trade-offs between latency and area are explored. The proposed architectures can be successfully used in the context of latency-critical systems or as attractive alternatives to deeply pipelined RCA schemes.

Polynomial approximation is a very general technique for the evaluation of a wide class of numerical functions of one variable. This article details an architecture generator that inputs the specification of a function and outputs a synthe-sizable description of an architecture evaluating this function with guaranteed accuracy. It improves upon the literature in two aspects. Firstly, it uses better polynomials, thanks to recent advances related to constrained-coefficient polynomial approximation. Secondly, it refines the error analysis of polynomial evaluation to reduce the size of the multipliers used. An open-source implementation is provided in the FloPoCo project, including architecture exploration heuristics designed to use efficiently the embedded memories and multipliers of high-end FPGAs. High-performance pipelined architectures for precisions up to 64 bits can be obtained in seconds.

Most current square root implementations for FPGAs use a digit recurrence algorithm which is well suited to their LUT structure. However, recent computing-oriented FPGAs include embedded multipliers and RAM blocks which can also be used to implement quadratic convergence algorithms, very high radix digit recurrences, or polynomial approximation algorithms. The cost of these solutions is evaluated and compared, and a complete implementation of a polynomial approach is presented within the open-source FloPoCo framework. This polynomial approach allows a shorter latency and higher frequency than the digit recurrence approach, and improves over previous multiplicative approaches. However, the cost of IEEE-compliant correct rounding is shown to be very high.

Integer addition is a universal building block, and applications such as quad-precision floating-point or elliptic curve cryptography now demand precisions well beyond 64 bits. This study explores the trade-offs between size, latency and frequency for pipelined large-precision adders on FPGA. It compares three pipelined adder architectures: the classical pipelined ripple-carry adder, a variation that reduces register count, and an FPGA-specific implementation of the carry-select adder capable of providing lower latency additions at a comparable price. For each of these architectures, resource estimation models are defined, and used in an adder generator that selects the best architecture considering the target FPGA, the target operating frequency, and the addition bit width.

This article presents a generator of floating-point exponential operators targeting recent FPGAs with embedded memories and DSP blocks. A single-precision operator consumes just one DSP block, 18Kbits of dual-port memory, and 392 slices on Virtex-4. For larger precisions, a generic approach based on polynomial approximation is used and proves more resource-efficient than the literature. For instance a double-precision operator consumes 5 BlockRAM and 12 DSP48 blocks on Virtex-5, or 10 M9k and 22 18×18 multipliers on Stratix III. This approach is flexible and is demonstrated to scale up to quadruple-precision, while enabling frequencies close to the FPGA's nominal frequency. All the proposed architectures are last-bit accurate for all the floating-point range. They are available in the open-source FloPoCo framework.

Custom operators, working at custom precisions, are a key ingredient to fully exploit the FPGA flexibility advantage for high-performance computing. Unfortunately, such operators are costly to design, and application designers tend to rely on less efficient off-the-shelf operators. To address this issue, an open-source architecture generator framework is introduced. Its salient features are an easy learning curve from VHDL, the ability to embed arbitrary synthesizable VHDL code, portability to mainstream FPGA targets from Xilinx and Altera, automatic management of complex pipelines with support for frequency-directed pipeline, and automatic test-bench generation. This generator is presented around the simple example of a collision detector, which it significantly improves in accuracy, DSP count, logic usage, frequency and latency with respect to an implementation using standard floating-point operators.

Recent computing-oriented FPGAs feature DSP blocks including small embedded multipliers. A large integer multiplier, for instance for a double-precision floating-point multiplier, consumes many of these DSP blocks. This article studies three non-standard implementation techniques of large multipliers: the Karatsuba-Ofman algorithm, non-standard multiplier tiling, and specialized squarers. They allow for large multipliers working at the peak frequency of the DSP blocks while reducing the DSP block usage. Their overhead in term of logic resources, if any, is much lower than that of emulating embedded multipliers. Their latency overhead, if any, is very small. Complete algorithmic descriptions are provided, carefully mapped on recent Xilinx and Altera devices, and validated by synthesis results.

This article studies two common situations where the flexibility of FPGAs allows one to design application-specific floating-point operators which are more efficient and more accurate than those offered by processors and GPUs. First, for applications involving the addition of a large number of floating-point values, an ad-hoc accumulator is proposed. By tailoring its parameters to the numerical requirements of the application, it can be made arbitrarily accurate, at an area cost comparable to that of a standard floating-point adder, and at a higher frequency. The second example is the sum-of-product operation, which is the building block of matrix computations. A novel architecture is proposed that feeds the previous accumulator out of a floating-point multiplier whose rounding logic has been removed, again improving the area/accuracy tradeoff. These architectures are implemented within the FloPoCo generator, freely available under the LGPL.