Research On The GPU Parallel Algorithm Of The Knapsack Problem Based On Divide And Conquer

The0-1knapsack problem is a kind of typical portfolio optimization NP-hardproblem. Many domestic and foreign researchers have been concentrated in theextending and deepening the study of the problem, and have not found a solvingalgorithm in linear time so far, but it has important application value in the practicalapplication field, so the domestic and overseas scholars have been emphasized how toreduce computation cost of solving the problem.In recent years, with the mature of the parallel processing technology, solving0-1knapsack problem by the traditional serial algorithm has been gradually turning tothe parallel algorithm of research, and has become a hot issue in this field. There aretwo kinds of methods of solving it: dynamic programming method and divide andconquer algorithm. A lot of scholars have got many results by dynamic programming,but they got less by the latter.Based on the thorough study of CUDA parallel computing model and the parallelalgorithm based on partition strategies, the paper analyzed the two list serialalgorithm of solving0-1knapsack problems, and put forward parallel algorithm oftwo list based on the CPU+GPU heterogeneous programming model for solvingknapsack problem, and analyzed the two list algorithm and the generation of thesubset of the algorithm, a block for the most value and parallel cut pieces algorithm ofparallel search algorithm and the son of the basic ideas and algorithm design process.And in each designing process of the son of the parallel algorithm, the parallel tasksare distributes into respective programming in GPU to realize such calculating. In theonly consideration of the backpack items scale the optimal cost factors of theperformance of the algorithm theory analysis and comparison, the algorithm avoidedGPU memory access conflict completely.Finally, this paper, based on the CPU+GPU heterogeneous programming modelfor0-1knapsack problem two list parallel algorithm experimental programming,conducted and tested the experiments repeatedly. And it compared the running timedifferences of the two list serial algorithms, based on the traditional CPUprogramming model,and the two list parallel algorithms, based on OpenMP modeland the CPU+GPU heterogeneous programming model. It also analyzed theperformance of parallel algorithm. The experimental results showed the feasibility of reducing time in two table algorithm based on GPU parallel programming model, andit also showed a better acceleration.