Research And Implementation Of 0/1 Knapsack Problem Based On OpenCL Parallel Genetic Algorithm

With the coming of multi-core era, the current parallel computing system usually includes multi-core CPU, GPU and other processor. The integration of CPU and GPU has become the development trend of the processor. How to make full use of the parallel computing capability in current muiti-core heterogeneous systems has become a research hotspot. The emergence of OpenCL computing technology has provided technical support for utilization of heterogeneous computing resources. To use OpenCL for parallel improvement with the traditional serial algorithm will be possible to obtain great acceleration.Knapsack problem has wide application prospect in actual life, and the 0/1 knapsack problem is a kind of basic knapsack problem, while other knapsack problem can usually be converted into 0/1 knapsack problem. Genetic algorithm (GA) is an intelligent optimization algorithm, which has advantages of simple, practical and good robustness, and it has shown great advantage in solving knapsack problem. The natural parallel model of genetic algorithm is very consistent with the OpenCL parallel technology, but the traditional genetic algorithm for solving knapsack problem is based on the individual serial computation through one by one. So it can’t take advantage of the individual independent in parallel genetic algorithm. Then, this paper proposed a research subject of improved genetic algorithm by using OpenCL parallel technology to solving knapsack problem.This paper mainly focused on the 0/1 knapsack problem based on genetic algorithm. According to the characteristic of the individual independence based on GA, a parallel segmentation method was presented by using OpenCL for 0/1 knapsack problem. Moreover, the local memory was employed to partial optimize the statistical operation. By comparing the experiments in serial and parallel algorithms, the results show that the parallel algorithm is operative, and the execution time increases linearly according to the increment scale to be solved. Moreover, by comparing the execution time of CPU and GPU under different individuals and iterations, the merit and defect of CPU and GPU for the method were analyzed.