Efficient Scan Operator Methods on a GPU - Diéguez, Adrián P.; Amor, Margarita; Doallo, Ramón (Anais do International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD); 2014: Anais do XXVI International Symposium on Computer Architecture and High Performance Computing, 2014)
Current GPUs (Graphics Processing Units) offer high computational power at relatively low cost, nonetheless, this enhanced performance often comes at the expenses of flexibility and code complexity. Efficient GPU programming requires detailed knowledge on certain hardware aspects. The scan operator is an important building block for a wide range of algorithms. In this paper, we present a number of parallel scan methods based on the traditional cyclic reduction tridiagonal solver and the Ladner-Fischer parallel prefix adder. Futhermore, we analyze a set of new features introduced in the Kepler Nvidia architecture such as read-only data cache and shuffle instructions. Our methods provide an excellent performance in many cases, up to 48% improvement over the CUDA Data Parallel Primitives (CUDPP) library.