SHF:Small: Solving the Problem of Scalable Multi-Precision Matrix Arithmetic on GPUs

University Of Massachusetts Amherst, Amherst MA

Investigators

Abstract

Computers directly support arithmetic that is typically limited to 64 bits (about 19 decimal digits) of precision. Applications that need more precision must implement arithmetic through computationally expensive software. Beyond about 256 bits of precision, such calculations become quite costly. The RSA encryption algorithm, for example, can require arithmetic with up to 4096 bits of precision. Applications in areas such as experimental mathematics and number theory can require millions of bits of precision. One multiplication with 10 million bits of precision can take a tenth of a second to compute on a modern processor, which means that matrix arithmetic using such large values can take days to weeks to execute. In previous work the investigators have shown that it is possible to obtain a factor of 20 improvement in performance by utilizing the parallel processing capabilities of a commodity graphics processing unit (GPU) in place of the traditional CPU. However, programming a GPU to achieve this level of performance is quite difficult, and the resulting code requires considerable hand-tuning to move it to new generations of GPU and gain the advantage of their performance, which is scaling up at a rate that exceeds CPU performance scaling. This project is working to develop a framework that automatically generates and tunes multi-precision arithmetic libraries to execute on successive generations of GPUs. The libraries include both scalar and basic matrix arithmetic routines. They support scaling in precision as well as matrix size. The problem is challenging because different parallel algorithms must be automatically selected for different levels of precision, which must be balanced with the exploitation of the alternate dimension of parallelism inherent in matrix arithmetic. In addition, the work seeks to employ distributed parallelism across a cluster of computers enhanced with GPUs, so that the libraries can be used on a new generation of GPU-based supercomputers that is beginning to be deployed at national laboratories. The work is significant because it enables easier exploitation of low-cost commodity graphics processors to achieve more than an order of magnitude increase in performance for multi-precision scalar and matrix arithmetic. One important application is enhancing performance of RSA encryption to support longer, more secure keys, at greater data rates, so that it becomes feasible to encrypt greater volumes of internet traffic. Another important use is experimental mathematics, where computationally expensive functions (e.g., integrals, infinite series) are computed at high precision and compared to other functions and high precision constants to help identify more efficient closed-form solutions. Results from experimental mathematics have found applications in particle physics, chaos theory, and calculation of fundamental constants. The resulting software framework offers a significant performance enhancement for multi-precision arithmetic to systems that range from individual researcher workstations to large supercomputers.