GPU Implementations for Midsize Integer Addition and Multiplication

Overview

• This paper explores using a high-level functional language for efficient GPU-based arithmetic on "midsize" integers, up to around a quarter million bits.
• The goal is to understand if it's possible to support effective nested-parallel programs with a small, flexible codebase.
• The researchers present GPU implementations for integer addition and multiplication that leverage temporal reuse from scratchpad memories.
• They find that their solutions are simpler than related work, which often uses complex tiling strategies or computations in the domain of real numbers.
• The researchers evaluate performance against the state-of-the-art CGBN library and find their CUDA prototype outperforms CGBN for integer sizes above 32K bits.

Plain English Explanation

In this paper, the researchers explore using a high-level programming language called a "functional language" to perform arithmetic operations on large integers, up to around a quarter million bits, on graphics processing units (GPUs). The main goal is to see if they can create efficient programs that can take advantage of the parallel processing power of GPUs, while keeping the underlying code simple and flexible.

The researchers focus on implementing two key operations: addition and multiplication of these large integers. They find ways to organize the work so that the GPU's high-speed temporary memory, called "scratchpad memory," is used effectively, which boosts performance. Compared to previous work, the researchers' solutions are much simpler, avoiding complex strategies that may be "overkill" for this problem.

The researchers test their GPU-based implementations against a state-of-the-art library called CGBN, which is optimized for large integer arithmetic. They find that their approach outperforms CGBN for integers larger than 32,000 bits, while providing comparable performance for smaller sizes. Interestingly, they also discover that a particular multiplication technique called FFT multiplication starts to outperform the more traditional multiplication approach as the integer sizes get larger, as long as the integers still fit in the GPU's memory.

Finally, the researchers examine the strengths and weaknesses of the high-level functional language they used, called Futhark, for efficiently supporting these types of computational tasks. They identify that a new compiler feature to better manage excess parallelism could significantly improve the performance.

Technical Explanation

The researchers present GPU-based implementations for addition and multiplication of "midsize" integers, which they define as up to around a quarter million bits. Their goal is to understand whether it is possible to support efficient nested-parallel programs using a small, flexible codebase.

For integer addition, the researchers recognize that this can be implemented efficiently on GPUs using a well-known technique called "scan," which allows the computation to be parallelized effectively. Previous work has shown the potential for scan-based addition on GPUs.

For integer multiplication, the researchers employ a simple work-partitioning strategy that provides good temporal locality, allowing the GPU's scratchpad memory to be used effectively. This is in contrast to related work that uses complex tiling strategies, which the researchers feel may be "too big a hammer for the job."

The researchers also explore FFT-based multiplication, where they efficiently map the computation to the domain of integral fields by finding "good" prime numbers that enable near-full utilization of machine words. This avoids the potential issues with working in the domain of real numbers, which could degrade the numerical precision.

The researchers evaluate the performance of their CUDA-based prototype implementations against the state-of-the-art CGBN library, developed by NvidiaLab. They find that their approach outperforms CGBN for integer sizes above 32K bits, while offering comparable performance for smaller sizes. Importantly, they also report that the FFT-based multiplication outperforms the classical multiplication approach on the larger integer sizes that still fit within a single CUDA block.

Critical Analysis

The researchers have presented a thoughtful and novel approach to achieving efficient GPU-based arithmetic on "midsize" integers using a high-level functional language. Their key contributions lie in the simplicity of their solutions, which avoid the complex tiling strategies employed in related work, as well as their use of the integral field domain for FFT-based multiplication.

One potential limitation of the research is the focus on integers that fit within a single CUDA block. While this is a reasonable constraint for "midsize" integers, it may not fully address the challenges of working with truly large integers that exceed the memory capacity of a single GPU. Exploring techniques for scaling the computations across multiple GPU blocks or even multiple GPUs could be an area for further research.

Additionally, the researchers acknowledge that the high-level functional language they used, Futhark, could benefit from a compiler pass to more efficiently manage excess parallelism. This suggests that the performance of their approach may be somewhat constrained by the capabilities of the language and compiler, rather than solely by the underlying algorithmic and architectural choices.

It would also be interesting to see how the researchers' techniques compare to other state-of-the-art libraries or approaches beyond just CGBN, as well as how the performance scales with the number of GPU cores or other hardware parameters.

Overall, the researchers have presented a valuable contribution to the field of GPU-accelerated arithmetic on large integers, and their work serves as a solid foundation for further exploration and optimization in this domain.

Conclusion

This paper explores the use of a high-level functional language for efficient GPU-based arithmetic on "midsize" integers, up to around a quarter million bits. The researchers present simple yet effective implementations for integer addition and multiplication that leverage the GPU's scratchpad memory to achieve good performance.

The key findings are that the researchers' CUDA-based prototype outperforms the state-of-the-art CGBN library for integer sizes above 32K bits, and that FFT-based multiplication can outperform the classical approach for the larger integer sizes that still fit within a single CUDA block.

While the focus on integers that fit within a single CUDA block is a reasonable constraint, exploring techniques for scaling the computations across multiple GPU blocks or even multiple GPUs could be an area for future research. Additionally, the researchers identify opportunities to improve the performance of their approach through compiler-level optimizations.

Overall, this work contributes valuable insights and techniques for leveraging the parallel processing power of GPUs for large-integer arithmetic, which has important applications in fields such as cryptography, scientific computing, and data analysis.