Efficient arithmetic computation decomposition using embedded blocks

Arithmetic computation decomposition is a strategy that can be used to solve large and complicated computing problems. To obtain an efficient solution, the operands of the computations are decomposed and processed. Then, partial results are reassembled by exploiting a set of smaller and simpler computing blocks. These computing blocks are assumed to be highly optimized, and already built in Field Programmable Gate Arrays (FPGAs). This feature makes it possible to implement large size arithmetic operations in FPGAs with performances closer to those of the traditional Application Specific Integrated Circuits (ASICs).;Key words: large size arithmetic computation, high performance multipliers, decomposition, embedded multipliers, addition tree optimization, sign extension, multigranular, FPGA mapping. -;To improve the efficiency in terms of performance and resource usage for FPGA-based designs, this work develops efficient design methodologies and systematic approaches for the implementation of computing functions with large size operands based on decomposition strategies, using small-size embedded blocks in FPGAs. The design philosophy is demonstrated through the realization of large size multipliers and their derivatives. Innovative architectures of these multipliers and sets of optimized design rules are derived to aid in the realizations. Fixed size and multigranular embedded blocks are considered in these designs. The additions of partial products are performed in multi-levels using high performance two operand adders. Higher order compressors are also employed with optimized mapping techniques based on the architectures of the segmented multipliers. These approaches have been implemented and tested targeting primarily Xilinx' and Altera's FPGAs with the aid of the Xilinx' ISE and Altera's Quartus II tools. Significant improvements over that of the traditional techniques have been achieved in increasing the performance and reducing the area usage. The proposed approaches for the designs of large size unsigned and signed multipliers are further applied to implement other related more complex arithmetic operations. The implementation results have demonstrated that the approaches presented in this thesis ensure the efficiency in solving the problems of large size computing operations.