Efficient Large Integer Multiplication with Arm SVE Instructions

@inproceedings{10.1145/3578178.3578193,
author = {Edamatsu, Takuya and Takahashi, Daisuke},
title = {Efficient Large Integer Multiplication with Arm SVE Instructions},
year = {2023},
isbn = {9781450398053},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3578178.3578193},
doi = {10.1145/3578178.3578193},
abstract = {In this study, we implement large integer multiplication with the Arm Scalable Vector Extension (SVE) instructions. SVE is a single instruction, multiple data (SIMD) instruction set for the Arm AArch64 architecture. We use a reduced-radix representation technique because SIMD instructions do not retain the carry that occurs when partial products are added in large integer multiplication computations. Furthermore, we develop and implement a multiplication algorithm based on the Basecase method, which allows the application of ordinary multiplication instructions to special integers in reduced-radix representation. To evaluate performance, we compare our multiplication implementation on an A64FX processor with the GNU Multiple Precision Arithmetic Library (GMP). We show that processing with SVE was faster than GMP for multiplication with operands larger than 2,048 bits. The performance gain was up to 36\%. These results suggest that SVE instructions have the potential to be faster than scalar instructions for large integer multiplication, especially for large operands.},
booktitle = {Proceedings of the International Conference on High Performance Computing in Asia-Pacific Region},
pages = {9–17},
numpages = {9},
keywords = {Arm, SIMD, SVE, integer multiplication, large integer arithmetic},
location = {, Singapore, Singapore, },
series = {HPCAsia '23}
}