Title :
Parallel implementation of the modified subset sum problem in CUDA
Author :
Ristovski, Zlatko ; Mishkovski, Igor ; Gramatikov, Sasho ; Filiposka, Sonja
Author_Institution :
Fac. of Comput. Sci. & Eng., Univ. Ss Cyril & Methodius, Skopje, Macedonia
Abstract :
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.
Keywords :
graphics processing units; mathematics computing; optimisation; parallel architectures; set theory; CPU; CUDA; GPU; NP-complete modified subset sum algorithm; central processing; compute unified device architecture; computing paradigm shift; coprocessing; graphics processing units; parallel computing architecture; Central Processing Unit; Computer architecture; Graphics processing units; Instruction sets; Peer-to-peer computing; Programming; Vectors; CUDA; GPGPU; Modified subset sum algorithm; Parallel Speedup;
Conference_Titel :
Telecommunications Forum Telfor (TELFOR), 2014 22nd
Conference_Location :
Belgrade
Print_ISBN :
978-1-4799-6190-0
DOI :
10.1109/TELFOR.2014.7034556