Parallel implementation of the modified subset sum problem in CUDA
Zlatko Ristovski, Igor Mishkovski, Sasho Gramatikov, Sonja Filiposka · 2014
In the recent years, computing is shifting from “central processing” on the CPU to “co-processing” on the CPU and GPU. This computing paradigm shift is due to the development of CUDA (Compute Unified Device Architecture) parallel computing architecture. CUDA is a programming model for parallel computing in Graphics Processing Units (GPUs). In this work, we have implemented parallel solution of the NP-complete modified subset sum algorithm using CUDA. With our implementation, for a certain problem size, we have obtained speedup of 20 times, compared to the CPU version.