Premium
An efficient solution to the subset‐sum problem on GPU
Author(s) -
Curtis V. V.,
Sanches C. A. A.
Publication year - 2016
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.3636
Subject(s) - parallel computing , cuda , graphics processing unit , computer science , graphics , combinatorics , parallel algorithm , algorithm , mathematics , computer graphics (images)
Summary We present an algorithm to solve the subset‐sum problem (SSP) of capacity c and n items with weights w i ,1≤ i ≤ n , spending O ( n ( m − w min )/ p ) time and O ( n + m − w min ) space in the Concurrent Read/Concurrent Write (CRCW) PRAM model with 1≤ p ≤ m − w min processors, where w min is the lowest weight and m = min c , ∑ i = 1 nw i − c , improving both upper‐bounds . Thus, when n ≤ c , it is possible to solve the SSP in O ( n ) time in parallel environments with low memory. We also show OpenMP and CUDA implementations of this algorithm and, on Graphics Processing Unit, we obtained better performance than the best sequential and parallel algorithms known so far. Copyright © 2015 John Wiley & Sons, Ltd.