An Efficient and Parallelism-Scalable Large Integer Multiplier Architecture Using Least-Positive Form and Winograd Fast Algorithm

In this brief, an improved and efficient Winograd-based Large Integer Multiplication using least-positive form named WLIM is proposed, which can reduce 28.61% to 33.33% of the number of multiplications compared to least-positive form direct multiplication. By exploiting the cyclic parallelism of the improved algorithm, an Efficient and Parallelism-Scalable Large Integer Multiplier architecture named EPSM is proposed, which has two levels of adjustable parallelism. EPSM is implemented on Xilinx Virtex-7 VC709 Board, Zynq UltraScale+ XZCU19EG Device, and Alveo U250 Card, by using Vivado. Compared with the related works, EPSM can achieve a performance improvement of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$1.29\times \sim ~20.99\times $ </tex-math></inline-formula>. In terms of area efficiency, EPSM can achieve <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$3.54\times \sim ~41.41\times $ </tex-math></inline-formula> area-time product (ATP) improvements.