GPU implementation of a parallel two-list algorithm for the subset-sum problem

摘要

The subset-sum problem is a well-known non-deterministic polynomial-time complete (NP-complete)rndecision problem. This paper proposes a novel and efficient implementation of a parallel two-list algorithmrnfor solving the problem on a graphics processing unit (GPU) using Compute Unified Device Architecturern(CUDA). The algorithm is composed of a generation stage, a pruning stage, and a search stage. It isrnnot easy to effectively implement the three stages of the algorithm on a GPU. Ways to achieve betterrnperformance, reasonable task distribution between CPU and GPU, effective GPU memory management,rnand CPU–GPU communication cost minimization are discussed. The generation stage of the algorithmrnadopts a typical recursive divide-and-conquer strategy. Because recursion cannot be well supported by currentrnGPUs with compute capability less than 3.5, a new vector-based iterative implementation mechanismrnis designed to replace the explicit recursion. Furthermore, to optimize the performance of the GPU implementation,rnthis paper improves the three stages of the algorithm. The experimental results show that the GPUrnimplementation has much better performance than the CPU implementation and can achieve high speeduprnon different GPU cards. The experimental results also illustrate that the improved algorithm can bringrnsignificant performance benefits for the GPU implementation.