On GPU Implementation for Multi-Precision Integer Division
This work addresses the lack of efficient GPU division for medium-sized integers, which is a niche problem for high-performance computing applications.
The paper presents a GPU implementation of multi-precision integer division for precisions from 2^15 to 2^18, achieving near-optimal performance relative to a cost model based on multiplications.
This paper presents the issues arising in implementing a fast integer division algorithm on general purpose GPUs. The algorithm uses a Newton iteration based on the shifted inverse operation, keeping all arithmetic in the integer domain and relying on data-parallel operators. The principal contribution is an efficient GPU/CUDA implementation for integer precisions from $2^{15}$ to $2^{18}$ -- sizes not supported by \cgbn{} division. We propose algorithmic refinements, define a cost model in terms of multiplications, build on prefix sums and previous work on multi-precision multiplication, and present an evaluation showing near-optimal performance relative to the model for the target precision.