Many emerging application domains, such as machine learning, can tolerate limited amounts of arithmetic inaccuracy. When designing custom compute accelerators for these domains, hardware designers can explore tradeoffs that sacrifice accuracy in order to reduce area, delay, and/or power consumption. This paper explores the design space of approximate multipliers using a family of approximate compressors as building blocks for the partial product reduction tree. We present a tool that allows the user to specify an allowable level of error tolerance, and returns the minimum area, delay, or power approximate multiplier that provides that level of accuracy. Our experimental results indicate that our proposed compressors generate more accurate and more efficient approximate multipliers than existing state-of-the-art techniques.

A heuristic is presented to efficiently synthesize approximate adder trees on Altera and Xilinx FPGAs using their carry chains. The mapper constructs approximate adder trees using an approximate quaternary adder as the fundamental building block. The approximate adder trees are smaller than exact adder trees, allowing more operators to fit into a fixed-area device, trading off arithmetic accuracy for higher throughput.

And-Invert Cones (AICs) have been suggested as an alternative to the ubiquitous Look-Up Tables (LUTs) used in commercial FPGAs. The original article suggesting the new architecture made some untested assumptions on the circuitry needed to implement AIC architectures and did not develop completely the toolset necessary to assess comprehensively the idea. In this paper, we pick up the architecture that some of us proposed in the original AIC paper and try to implement it as thoroughly as we can afford. We build all components for the logic cluster at transistor level in a 40~nm technology as well as a LUT-based architecture inspired by Altera's Stratix~IV. We first determine that the characteristics of our LUT-based architecture are reasonably similar to those of the commercial counterpart. Then, we compare the AIC architecture to the baseline on a number of benchmarks, and we find a few difficulties that had been overlooked before. We thus explore other design possibilities around the original design point and show their detailed impact. Finally, we discuss how the very structure of current logic clusters seems not perfectly appropriate for getting the best out of AICs and conclude that, even though they are not confirmed as an immediate blessing today, AICs still offer rich research opportunities.

Despite their many advantages, FPGAs are still inefficient. This inefficiency is mainly due to programmable routing networks; however, FPGA logic blocks also have their share of contribution. From the performance perspective, fewer hops in the routing network translates to a shorter critical path; and that requires large logic blocks capable of covering big portions of circuits. Recent work has shown that And-Inverter Cones (AICs) can considerably reduce the number of logic block levels compared to Look-Up Tables (LUTs). The best performance is achieved when both AICs and LUTs are used, but the AIC implementation requires radical changes in the FPGAs architecture. In this paper, we use AICs as shadow logic for LUTs in LUT-clusters, which requires minimal architectural changes while exploiting the benefits of both AICs and LUTs. The basic idea is to reuse the input crossbar of LUT-clusters for the shadow AICs while combining both LUTs and AICs in the same cluster. We also propose changes in the AIC architecture to enhance mapping on AICs. Our experimental results indicate that the new cluster architecture can reduce the average circuit delay by 12% with respect to standard FPGA clusters. However, this performance gain comes at a price of 43% area overhead in terms of number of logic clusters. Our results show that for a modest 6% increase in area, FPGA manufacturers can move towards next-generation FPGA logic elements. This transition would provide faster design options without major architectural changes.

Despite their many advantages, FPGAs still come with significant overheads in area, delay, and power consumption due to an extreme programmability in both the routing and logic. From the performance perspective, large logic blocks, capable of covering big portions of circuits, lead to fewer hops in the routing network, and thus, to a shorter critical path. Recent work has shown that And-Inverter Cones (AICs) can considerably reduce the number of logic block levels compared to Look-Up Tables (LUTs), in a radically altered FPGAs architecture. In this paper, we use AICs as shadow logic for LUTs, which incurs minimal architectural changes with respect to current FPGAs, while exploiting the benefits of both AICs and LUTs. We also propose changes in the AIC architecture, for a more compact technology mapping. The new architecture reduces the average circuit delay by up to 35% with respect to standard FPGAs at the expense of a 3x increase in the number of the logic clusters. Other benchmarks show more moderate area overheads, e.g., 16% delay improvement for 20% area overhead.

In floating-point datapaths synthesized on FPGAs, the shifters that perform mantissa alignment and normalization consume a disproportionate number of LUTs. Shifters are implemented using several rows of small multiplexers; unfortunately, multiplexer-based logic structures map poorly onto LUTs. FPGAs, meanwhile, contain a large number of multiplexers in the programmable routing network; these multiplexer are placed under static control of the FPGA's configuration bitstream. In this work, we modify some of the routing multiplexers in the intra-cluster routing network of a CLB in an FPGA to implement shifters for floating-point mantissa alignment and normalization; the number of CLBs required for these operations is reduced by 67%. If shifting is not required, the routing multiplexers that have been modified can be configured to operate as normal routing multiplexers, so no functionality is sacrificed. The area overhead incurred by these modifications is small, and there is no need to modify every routing multiplexer in the FPGA. Experiments show that there is no negative impact in terms of clock frequency or routability for benchmarks that do not use the dynamic multiplexers.

Look-Up Tables (LUTs) are universally used in FPGAs as the elementary logic blocks. They can implement any logic function and thus covering a circuit is a relatively straightforward problem. Naturally, flexibility comes at a price, and increasing the number of LUT inputs to cover larger parts of a circuit has an exponential cost in the LUT complexity. Hence, rarely LUTs with more than 4-6 inputs have been used. In this paper we argue that other elementary logic blocks can provide a better compromise between hardware complexity, flexibility, delay, and input and output counts. Inspired by recent trends in synthesis and verification, we explore blocks based on And-Inverter Graphs (AIGs): they have a complexity which is only linear in the number of inputs, they sport the potential for multiple independent outputs, and the delay is only logarithmic in the number of inputs. Of course, these new blocks are extremely less flexible than LUTs; yet, we show (i) that effective mapping algorithms exist, (ii) that, due to their simplicity, poor utilization is less of an issue than with LUTs, and (iii) that a few LUTs can still be used in extreme unfortunate cases. We show first results indicating that this new logic block combined to some LUTs in hybrid FPGAs can reduce delay up to 22-32% and area by some 16% on average. Yet, we explored only a few design points and we think that these results could still be improved by a more systematic exploration.

Routing resources in modern FPGAs use 50% of the silicon real estate and are significant contributors to critical path delay and power consumption; the situation gets worse with each successive process generation, as transistors scale more effectively than wires. To cope with these challenges, FPGA architects have divided wires into local and global categories and introduced fast dedicated carry chains between adjacent logic cells, which reduce routing resource usage for certain arithmetic circuits (primarily adders and subtractors).

To bridge the gap between FPGAs and ASICs for arithmetic dominated circuits, one key step is to improve multipliers on FPGAs. This is a key feature that FPGA vendors have tried to improve in recent years by embedding ASIC like multipliers in the DSP blocks. However, due to the limited number of DSP blocks in an FPGA, their fixed location and bit-width limitation, efficient soft logic implementation of multipliers is fundamental. This is the reason that FPGA vendors have enhanced the logic blocks architecture to improve certain arithmetic circuits such as adder tree, which is the basic part of a parallel multiplier. This paper has two main contributions: (1) The performance gap between embedded and soft multipliers is measured and the design space is explored and (2) the current performance gap is reduced by employing a number of target specific mapping and arithmetic transformation techniques. For this purpose, a multiplier generator tool is developed and two conventional multiplication techniques are implemented in this tool. We compare our multipliers with the ones that are generated by Altera core generator tool considering a wide range of bit-widths. Therefore, this paper can be used as a reference for the digital circuit designers to choose the right way of implementing multipliers on FPGAs based on their design constraints.

Compressor trees are a class of circuits that generalizes multioperand addition and the partial product reduction trees of parallel multipliers using carry-save arithmetic. Compressor trees naturally occur in many DSP applications, such as FIR filters, and, in the more general case, their use can be maximized through the application of high-level transformations to arithmetically intensive data flow graphs. Due to the presence of carry-chains, it has long been thought that trees of 2- or 3-input carry-propagate adders are more efficient than compressor trees for FPGA synthesis; however, this is not the case. This article presents a heuristic for FPGA synthesis of compressor trees that outperforms adder trees and exploits carry-chains when possible. The experimental results show that, on average, the use of compressor trees can reduce critical path delay by 33% and 45% respectively, compared to adder trees synthesized on the Xilinx Virtex-5 and Altera Stratix III FPGAs.

Integrating DSP blocks into FPGAs is an effective approach to close the existing gap between FPGAs and ASICs. A much wider range of applications could benefit from DSP blocks if they were more versatile than those currently found in commercial devices. In this paper we propose a novel DSP block which resembles commercially available ones and yet additionally supports a wide variety of multiplier bit widths as well as multi-input addition with negligible overhead. The novel DSP block uses much more efficiently the limited available input/output bandwidth. Experimental results show that on average the area overhead of the novel features added to a base design is a mere 3% with practically no delay penalty. Moreover, for multi-input addition, which is not supported in current DSP blocks, the proposed DSP block is more than 50% faster on average compared to FPGA soft logic.

A new method to synthesize clusters of floating-point addition operations on FPGAs is presented. Similar to Altera's floating-point data path compiler, it performs normalization once, at the output of the cluster operation. All significands in the clustered operation are denormalized in parallel with respect to the largest exponent: a fixed-point compressor tree then sums the aligned significands, followed by normalization and rounding. Compared to Altera's floating-point datapath compiler, our method reduces the critical path delay by as much as 20%, and area by as much as 29% on Altera Stratix III FPGAs.

The selective use of carry-save arithmetic, where appropriate, can accelerate a variety of arithmetic-dominated circuits. Carry-save arithmetic occurs naturally in a variety of DSP applications, and further opportunities to exploit it can be exposed through systematic data flow transformations that can be applied by a hardware compiler. Field-programmable gate arrays (FPGAs), however, are not particularly well suited to carry-save arithmetic. To address this concern, we introduce the ¿field programmable counter array¿ (FPCA), an accelerator for carry-save arithmetic intended for integration into an FPGA as an alternative to DSP blocks. In addition to multiplication and multiply accumulation, the FPCA can accelerate more general carry-save operations, such as multi-input addition (e.g., add k > 2 integers) and multipliers that have been fused with other adders. Our experiments show that the FPCA accelerates a wider variety of applications than DSP blocks and improves performance, area utilization, and energy consumption compared with soft FPGA logic.

This poster proposes the use of 3D integration technology to enable low-overhead reconfigurable computing. In our scheme, a 64 Megabyte DRAM array is stacked on top of an FPGA using face-to-face bonding, and caches up to 289 future configurations which can be quickly loaded onto the FPGA. Past DRAMs have been designed for off-chip communication, a bottleneck that 3D stacking eliminates; hence, the DRAM array is redesigned. To reconfigure the FPGA, a configuration is read from the DRAM into a latch array while the FPGA executes; then, the configuration is loaded from the latch array into the FPGA in 5 cycles (60ns). The minimum latency between reconfigurations, 8.42s, is dominated by the time to load data from the DRAM into the latch array. The benefits, area cost, and performance of the proposed system are evaluated on three previously published FPGA implementations of multimedia applications: MP3 and MPEG-4 decoders, and JPEG compression, and are evaluated under three scenarios: No Dynamic ReConfiguration (NDRC), Off-chip Dynamic ReConfiguration (ORDC), and 3D Configuration Caching (3DCC). Our experiments demonstrate that 3D configuration caching works best when used in conjunction with FPGA-based accelerators, rather than pure FPGA-based systems; in these systems, the reconfiguration latency can easily be hidden behind software execution on the processor controlling the accelerator. This significantly reduces the amount of silicon area that must be dedicated to the accelerator, while imposing virtually no performance penalty compared to significantly larger accelerators that do not require reconfiguration.

This paper advocates the use of 3D integration technology to stack a DRAM on top of an FPGA. The DRAM will store future FPGA contexts. A configuration is read from the DRAM into a latch array on the DRAM layer while the FPGA executes; the new configuration is loaded from the latch array into the FPGA in 60 ns (5 cycles). The latency between reconfigurations, 8.42 mus, is dominated by the time to read data from the DRAM into the latch array. We estimate that the DRAM can cache 289 FPGA contexts.

Fast carry chains featuring dedicated adder circuitry is a distinctive feature of modern FPGAs. The carry chains bypass the general routing network and are embedded in the logic blocks of FPGAs for fast addition. Conventional intuition is that such carry chains can be used only for implementing carry-propagate addition; state-of-the-art FPGA synthesizers can only exploit the carry chains for these specific circuits. This paper demonstrates that the carry chains can be used to build compressor trees, i.e., multi-input addition circuits used for parallel accumulation and partial product reduction for parallel multipliers implemented in FPGA logic. The key to our technique is to program the lookup tables (LUTs) in the logic blocks to stop the propagation of carry bits along the carry chain at appropriate points. This approach improves the area of compressor trees significantly compared to previous methods that synthesized compressor trees solely on LUTs, without compromising the performance gain over trees built from ternary carry-propagate adders.

We propose a new DSP block for use in modern high-performance FPGAs. Current DSP blocks contain fixed-bitwidth multipliers that can be combined efficiently to form larger multipliers. Our approach is similar, but includes a bypass layer following the partial product generator that exposes the compressor tree used for partial product reduction directly to the user. As a consequence, the proposed DSP block can accelerate multi-input addition operations in addition to multiplication. To increase the flexibility of the device, the partial product reduction tree used within our DSP block uses a fixed-function compression logic along with a field programmable compressor tree (FPCT), the latter of which is user-configurable to meet the needs of the application at hand. Multi-input addition operations can be mapped directly onto the FPCT without compromising any of the other functionality of the DSP block.

Multi-input addition occurs in a variety of arithmetically intensive signal processing applications. The DSP blocks embedded in high-performance FPGAs perform fixed bitwidth parallel multiplication and Multiply-ACcumulate (MAC) operations. In theory, the compressor trees contained within the multipliers could implement multi-input addition; however, they are not exposed to the programmer. To improve FPGA performance for these applications, this article introduces the Field Programmable Compressor Tree (FPCT) as an alternative to the DSP blocks. By providing just a compressor tree, the FPCT can perform multi-input addition along with parallel multiplication and MAC in conjunction with a small amount of FPGA general logic. Furthermore, the user can configure the FPCT to precisely match the bitwidths of the operands being summed. Although an FPCT cannot beat the performance of a well-designed ASIC compressor tree of fixed bitwidth, for example, 9×9 and 18×18-bit multipliers/MACs in DSP blocks, its configurable bitwidth and ability to perform multi-input addition is ideal for reconfigurable devices that are used across a variety of applications.

To improve FPGA performance for arithmetic circuits that are dominated by multi-input addition operations, an FPGA logic block is proposed that can be configured as a 6:2 or 7:2 compressor. Compressors have been used successfully in the past to realize parallel multipliers in VLSI technology; however, the peculiar structure of FPGA logic blocks, coupled with the high cost of the routing network relative to ASIC technology, renders compressors ineffective when mapped onto the general logic of an FPGA. On the other hand, current FPGA logic cells have already been enhanced with carry chains to improve arithmetic functionality, for example, to realize fast ternary carry-propagate addition. The contribution of this article is a new FPGA logic cell that is specialized to help realize efficient compressor trees on FPGAs. The new FPGA logic cell has two variants that can respectively be configured as a 6:2 or a 7:2 compressor using additional carry chains that, coupled with lookup tables, provide the necessary functionality. Experiments show that the use of these modified logic cells significantly reduces the delay of compressor trees synthesized on FPGAs compared to state-of-the-art synthesis techniques, with a moderate increase in area and power consumption.

FPGA performance is currently lacking for arithmetic circuits. Large sums of k > 2 integer values is a computationally intensive operation in applications such as digital signal and video processing. In ASIC design, compressor trees, such as Wallace and Dadda trees, are used for parallel accumulation; however, the LUT structure and fast carry-chains employed by modern FPGAs favor trees of carry-propagate adders (CPAs), which are a poor choice for ASIC design. This paper presents the first method to successfully synthesize compressor trees on LUT-based FPGAs. In particular, we have found that generalized parallel counters (GPCs) map quite well to LUTs on FPGAs; a heuristic, presented within, constructs a compressor tree from a library of GPCs that can efficiently be implemented on the target FPGA. Compared to the ternary adder trees produced by commercial synthesis tools, our heuristic reduces the combinational delay by 27.5%, on average, within a tolerable average area increase of 5.7%.

Multi-input addition is an important operation for many DSP and video processing applications. On FPGAs, multi-input addition has traditionally been implemented using trees of carry-propagate adders. This approach has been used because the traditional lookup table (LUT) structure of FPGAs is not amenable to compressor trees, which are used to implement multi-input addition and parallel multiplication in ASIC technology. In prior work, we developed a greedy heuristic method to map compressor trees onto the general logic of an FPGA using a component called generalized parallel counter (GPC). Although this technique reduced the combinational delay of our circuits, when synthesized onto Altera Stratix-II FPGAs, by 27% on average; however, the area was increased by an average 11%. To further reduce the delay and limit the increase in area, we have developed a new solution to the mapping problem based on integer linear programming. This new approach reduced the delay of the compressor tree by 32% on average and reduced the area by 3% compared to an adder tree.

The Field Programmable Counter Array (FPCA) was introduced to improve FPGA performance for arithmetic circuits. An FPCA is a reconfigurable IP core that can be integrated into an FPGA. To exploit the FPCA, a circuit is transformed by merging disparate addition and multiplication operations into large multi-input addition operations, which are synthesized as compressor trees on the FPCA; the remaining portion of the circuit is synthesized on the FPGA. This paper presents a series of architectural improvements to the FPCA that reduce routing delay, increase flexibility and component utilization, and simplify the integration process. Using an FPGA containing six FPCAs, we observed average and maximum speedups of 1.60x and 2.40x on a set of arithmetic benchmarks

To improve FPGA performance for arithmetic circuits, this paper proposes a new architecture for FPGA logic cells that includes a 6:2 compressor. The new cell features additional fast carry-chains that concatenate adjacent compressors and can be routed locally without the global routing network. Unlike previous carry-chains for binary and ternary addition, the carry chain used by the new cell only spans 2 logic blocks, which significantly improves the delay of multi-input addition operations mapped onto the FPGA. The delay and area overhead that arises from augmenting a traditional FPGA logic cell with the new compressor structure is minimal. Using this new cell, we observed an average speedup in combinational delay of 1.41 x compared to adder trees synthesized using ternary adders.

FPGAs offer flexibility and cost-effectiveness that ASICs cannot match; however, their performance is quite poor in comparison, especially for arithmetic dominated circuits. To address this issue, this paper introduces a novel reconfigurable lattice built from counters rather than look-up tables that can effectively accelerate the arithmetic portions of a circuit. We intend to integrate this novel lattice onto the same die as an FPGA.

This paper presents a very fast and low-power address bus encoder which is less dependent on address bus width. Its encoding scheme is the same as TO-XOR encoding method but its encoder and decoder architectures are much faster. Both the analytical analysis and the simulation results show that the delay of proposed architecture is about one third of delay of optimized TO-XOR encoder/decoder