摘要
背包问题属于著名的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.
出处
《计算机工程与科学》
CSCD
2006年第9期100-102,共3页
Computer Engineering & Science
基金
国家自然科学基金资助项目(60273075)
教育部重点项目(105128)
中国网上教育平台工程(计高技[2000]2034)
关键词
背包问题
并行算法
采样
MIMD
二表算法
knapsack problem
parallel algorithm
sampling
MIMD
two-list algorithm
