There is a recent trend in artificial intelligence (AI) inference towards lower precision data formats down to 8 bits and less. As multiplication is the most complex operation in typical inference tasks, there is a large demand for efficient small multipliers. The large DSP blocks have limitations implementing many small multipliers efficiently. Hence, this work proposes a solution for better logic-based multipliers that is especially beneficial for small multipliers. Our work is based on the multiplier tiling method in which a multiplier is designed out of several sub-multiplier tiles. The key observation we made is that these sub-multipliers do not necessarily have to perform a complete (rectangular) N×K multiplication and more efficient submultipliers are possible that are incomplete (non-rectangular). This proposal first seeks to identify efficient incomplete irregular sub-multipliers and then demonstrates improvements over state-of-the-art designs. It is shown that optimal solutions can be found using integer linear programming (ILP), which are evaluated in FPGA synthesis experiments.

The major challenge when designing multipliers for FPGAs is to address several tradeoffs: On the one hand at the performance level and on the other hand at the resource level utilizing DSP blocks or lookup tables (LUTs). With DSPs being a relatively limited resource, the problem of under- or over-utilization of DSPs has previously been addressed by the concept of multiplier tiling, by assembling multipliers from DSPs and small supplemental LUT multipliers. But there had always been an efficiency gap between tiling-based multipliers and radix-4 Booth-Arrays. While the monolithic Booth-Array was shown to be considerably more efficient in terms of L UT- resources on many modern FPGA-architectures, it typically possess a significantly higher critically path delay (or latency when pipeline d) compared to multipliers designed by tiling. This work proposes and analyzes the use of smaller Booth-Arrays as sub-multipliers that are integrated into existing tiling-based methods, such that better tradeoff points between area and delay can be reached while utilizing a user-specified number of DSP blocks. It is shown by synthesis experiments, that the critical path delay compared to large Booth-Arrays can be reduced, while achieving significant reductions in LUT-resources compared to previous tiling.

The design of a multiplier typically consists of three steps: (1) partial product generation, (2) compressor tree design and (3) the selection of the final adder. Conventionally, these three steps are performed consecutively. However, when targeting FPGAs, there are many possibilities in all three design steps that heavily influence each other. This proposal presents for the first time a holistic optimization, combining all three optimization steps yielding a minimum amount of look-up-tables (LUTs) while it can also guarantee the minimal number of (pipeline) stages. An ILP-formulation for the determination of a combined, globally optimal solution for the multiplier tiling, compressor tree generation and final adder selection is proposed. With globally optimal we mean that the best solution is found for a given set of sub-multipliers for partial product generation, compressors and final adder.This allows to improve the quality and evaluate the limitations of existing heuristic 3-step approaches. It is shown experimentally for the example of Xilinx FPGAs, that globally optimal solutions can be obtained for multiplier sizes of practical relevance, leading to significant LUT reductions. Additional packing density experiments show that a significantly larger number of multiplier instances can be mapped to the same device.

Squaring is an essential operation in computer arithmetic that can be considered as a special case of multiplication where several simplifications can be applied to reduce the complexity of the resulting circuit. However, the design of a squarer is not straightforward for modern FPGAs that provide embedded DSP blocks and look-up-tables (LUTs). This work proposes a flexible method to design resource optimal squarers, i.e., a squarer that uses a minimum number of LUTs for a user-defined number of DSP blocks. The method uses an integer linear programming (ILP) formulation based on a generalization of multiplier tiling. It is shown that the proposed squarer design method significantly improves the LUT utilization for a given number of DSPs over previous methods, while maintaining a similar critical path delay and latency.

This proposal presents the resource optimal design of truncated multipliers targeting field programmable gate arrays (FPGAs). In contrast to application specific integrated circuits (ASICs), the design for FPGAs has some distinct design challenges due to many possibilities of computing the partial products using logic-based or DSP-based sub-multipliers. To tackle this, we extend a previously proposed tiling methodology which translates the multiplier design into a geometrical problem: the target multiplier is represented by a board that has to be covered by tiles representing the sub-multipliers. The tiling with the least resources can be found with integer linear programming (ILP). Our extension considers the error of possibly unoccupied positions of the board and determines the tiling with the least resources that respects the maximal allowed error bound. This error bound is chosen such that a faithfully rounded truncated multiplier is obtained. Compared to previous designs that use a fixed number of guard bits or optimize at the level of the dot diagrams, this allows a much better use of sub-multipliers resulting in significant area savings without sacrificing the timing.

This proposal presents a scalable methodology for the design of large multipliers by using tiling. Thereby, a multiplier of a given arbitrary size is partitioned into smaller DSP blocks or logic-based multipliers. This can be represented by tiling an area (defined by the size of the large multiplier) by using tiles of different shapes (defined by the small multipliers), each assigned with individual costs. Resource optimal solutions for this problem have been proposed for small multipliers by using integer linear programming (ILP) solvers, but the computational effort to solve the tiling problem for multipliers beyond 64x64 exceeds solving times of several days on current computers. Many applications like from cryptography require much larger multipliers. In addition, none of the previous methods exploit resource reductions from the well known Karatsuba scheme. Hence, it is first shown how the Karatsuba scheme can be included in the tiling optimization by considering it as a specific tile. Next, two fast and scalable tiling heuristics are presented to obtain good solutions in a reasonable time. Similar to previous work, the first heuristic is based on a greedy search. Based on that, the second heuristic improves these results by applying the idea of the beam search meta-heuristic. Both heuristics are capable to include the Karatsuba scheme, scale well to large multipliers and show significant improvements compared to state-of-the-art heuristics.