The Split-And-Merge Method in General Purpose Computation on GPUs

The Split-And-Merge Method in General Purpose Computation on GPUs

Code related to the paper The split-and-merge method in general purpose computation on GPUs by F. Argüello, D.B. Heras, M. Bóo, and J. Lamas-Rodríguez, published in Parallel Computing, Volume 38, Issues 6-7, June-July 2012, Pages 277-288.
DOI: 10.1016/j.parco.2012.03.003


The split-and-merge method is an algorithm design paradigm sometimes used in the field of parallel computing. It is applied to multilevel algorithms such as the wavelet transforms and some tridiagonal system solvers. In this paper we present the application of the method in the context of general purpose computation on GPUs. The split-and-merge method allows us to efficiently use the CUDA parallel programming model, where a multithreaded program is partitioned into blocks of threads that execute independently from each other. Thus we can solve the data dependency problem at the block boundaries and efficiently take advantage of the memory hierarchy of the GPU. The results obtained show a significant acceleration compared with the direct implementation of the algorithms on the GPU.



This code is licensed under a GNU General Public License v3.0