| 基于采样和MIMD结构的背包问题并行算法 |
| |
| 引用本文： | 刘晓玲,李肯立,郑光勇. 基于采样和MIMD结构的背包问题并行算法[J]. 计算机工程与科学, 2006, 28(9): 100-102 |
| |
| 作者姓名： | 刘晓玲 李肯立 郑光勇 |
| |
| 作者单位： | 湖南大学计算机与通信学院,湖南,长沙,410082;湖南大学计算机与通信学院,湖南,长沙,410082;湖南大学计算机与通信学院,湖南,长沙,410082 |
| |
| 基金项目： | 国家自然科学基金;教育部科学技术研究重点项目;国家科技基础条件平台建设计划 |
| |
| 摘 要： | 背包问题属于著名的NP完全问题，在信息密码学和数论研究中有着极其重要的应用。在深入分析背包问题现有并行算法的基础上，本文提出了一种基于采样和MIMD结构的背包问题并行求解算法，并给出了算法性能的理论分析和在IBMP690超级计算机上的实验结果。实验结果表明，当背包实例的维数n≥40时，本算法的并行效率可达60％以上。因此，本并行算法具有较好的可扩展性，能应用于各种MIMD结构的并行机上有效地求解背包问题。
|
| 关 键 词： | 背包问题 并行算法 采样 MIMD 二表算法 |
| 文章编号： | 1007-130X(2006)09-0100-03 |
| 修稿时间： | 2005-09-02 |
Research on the Parallel Algorithm for the Knapsack Problem Based on Sampling and MIMD |
| |
| LIU Xiao-ling,LI Ken-li,ZHENG Guang-yong. Research on the Parallel Algorithm for the Knapsack Problem Based on Sampling and MIMD[J]. Computer Engineering & Science, 2006, 28(9): 100-102 |
| |
| Authors: | LIU Xiao-ling LI Ken-li ZHENG Guang-yong |
| |
| Abstract: | 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 p arallel algorithms for the knapsack problem, a new parallel algorithm by sampling for solving the knapsack problem based on MIMD supercomputers is propo sed 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. |
| |
| Keywords: | MIMD |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与科学》浏览原始摘要信息 |
|
点击此处可从《计算机工程与科学》下载免费的PDF全文 |
