Abstract
System performance plays an important role in the era of big data. As such, the multiplication algorithm and hardware have evolved to improve system performance which can support a fast big data analysis engine. Several variations on conventional Booth multiplication algorithm have improved performance. However, we have observed that the existing multiplication algorithms repeating addition and shift operations conduct unnecessary iteration due to leading zeros in binary numbers. We have found that we can reduce the number of iterations by clearing unnecessary leading zeros in the multiplier. Thus, we propose two approaches to clear unnecessary leading Os: (1) pre-front-based: pre-clearing leading zeros with the front-based multiplication algorithm and (2) post-booth: post-clearing leading zeros with the rear-based multiplication algorithm using Booth algorithm. We evaluate performance with the data extracted from sparse matrices in UF Matrix Collection. Our algorithms outperform conventional multiplication algorithms by using a minimum number of necessary binary digits in the multiplier. The algorithms can be applied directly below the level of multiplication instructions with a minimal change to deal with big data ingestion.