Heuristics for the Design of Large Multipliers for FPGAs

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.