基于采样和MIMD结构的背包问题并行算法

Research on the Parallel Algorithm for the Knapsack Problem Based on Sampling and MIMD

背包问题属于著名的NP完全问题,在信息密码学和数论研究中有着极其重要的应用。在深入分析背包问题现有并行算法的基础上,本文提出了一种基于采样和MIMD结构的背包问题并行求解算法,并给出了算法性能的理论分析和在IBM P690超级计算机上的实验结果。实验结果表明,当背包实例的维数n≥40时,本算法的并行效率可达60%以上。因此,本并行算法具有较好的可扩展性,能应用于各种MIMD结构的并行机上有效地求解背包问题。

The knapsack problem is a famous NP-complete problem. It is very important in the research on cryptosystems and number theory. Based on the proposed parallel algorithms for the knapsack problem, a new parallel algorithm by sampling for solving the knapsack problem based on MIMD supercomputers is proposed in the paper. Then the performance is theoretically analyzed. Next the experimental results of the knapsack instances randomly generated are given on the IBM P690 supercomputer. The experimental results show the parallel efficiency can exceed 60% when solving the larger scale knapsack instances（n≥40）. Thus it is proved that the proposed parallel algorithm is scalable and effective on MIMD parallel supercomputers.