Research On GPU Parallel Algorithm For Knapsack Problem Based On Partitioning Strategy

With the development of multi-core technology and the maturity of GPUtechnology, many researchers have begun to use GPU to speed up some operation inthe database, and the new generation of GPU in a computer system’s role becomesuniversal coprocessor CPU (GPGPU), the coprocessor has much more powerful thanthe CPU parallel computation ability. Because of its unique characteristics of GPUarchitecture, is now widely applied to general-purpose computing, to deal with densedata and parallel data computing, problem solving combinatorial optimization of largeor difficult.Firstly, Based on in-depth study of CUDA parallel computing model and paralleldivide-and-conquer idea, serial two-list algorithm is presented to solve the0-1knapsack problem, and propose two algorithms of parallel computing model forsolving0-1knapsack problem based on CUDA parallel, only consider backpack itemsthis factor scale cost optimum conditions under the analysis and comparison ofperformance on the theory of algorithms, the algorithm can avoid the memory accessconflict.Secondly, the programming experiment for parallel table algorithm for0-1knapsack problem of parallel programming model based on CUDA architecture, andthe experiment was repeated testing, which compares the traditional serial two-listalgorithm based on CPU programming model and CPU+GPU programming modelbased on the difference of heterogeneous and two-list algorithm running time, and theperformance of the parallel algorithm the analysis. The experimental results show thatthe parallel table algorithm based on GPU programming model to reduce the run timeof feasibility, and the program showed better speedup.By research on the parallel algorithm and the GPU platform, the databaseconnection between parallel algorithm implementation and Optimization on GPUplatform. Given the multi-core processor and computer cluster similarity in some part,we make a comparison of the success in the computer in the algorithm, the CMDalgorithm is transplanted to GPU platform. And compared to the GPU, itsperformance and other classical algorithms, and discuss the accelerating ability ofdatabase operations GPU.