| Improved Parallel Three-List Algorithm for the Knapsack Problem without Memory Conflicts |
| |
| 作者姓名： | 潘军 李肯立 李庆华 |
| |
| 作者单位： | School of Computer Science and Technology, Huazhong Unit~.rsity of Science and Technology, Wuhan 430074, China |
| |
| 基金项目： | The National Natural Science Foundation of China （ No. 60273075）, and the National High Technique Development Program （ No. 863-306 ZD-11-01-06） |
| |
| 摘 要： | Based on the two-list algorithm and the parallel three-list algorithm, an improved parallel three-list algorithm for knapsack problem is proposed, in which the method of divide and conquer, and parallel merging without memory conflicts are adopted. To find a solution for the n-element knapsack problem, the proposed algorithm needs O（2^3n/8） time when O（2^3n/8） shared memory units and O（2^n/4） processors are available. The comparisons between the proposed algorithm and 10 existing algorithms show that the improved parallel three-fist algorithm is the first exclusive-read exclusive-write （EREW） parallel algorithm that can solve the knapsack instances in less than O（2^n/2） time when the available hardware resource is smaller than O（2^n/2） , and hence is an improved result over the past researches.
|
| 关 键 词： | 平行算法 存储器 计算机 信息冲突 |
| 文章编号： | 1005-2429（2006）01-0007-08 |
| 收稿时间： | 2005-04-24 |
Improved Parallel Three-List Algorithm for the Knapsack Problem without Memory Conflicts |
| |
| Pan Jun,Li Kenli,Li Qinghua.Improved Parallel Three-List Algorithm for the Knapsack Problem without Memory Conflicts[J].Journal of Southwest Jiaotong University,2006,14(1):7-14. |
| |
| Authors: | Pan Jun Li Kenli Li Qinghua |
| |
| Abstract: | Based on the two-list algorithm and the parallel three-list algorithm, an improved parallel three-list algorithm for knapsack problem is proposed, in which the method of divide and conquer, and parallel merging without memory conflicts are adopted. To find a solution for the n-element knapsack problem, the proposed algorithm needs O(2 3n/8) time when O(2 3n/8) shared memory units and O(2 n/4) processors are available. The comparisons between the proposed algorithm and 10 existing algorithms show that the improved parallel three-list algorithm is the first exclusive-read exclusive-write (EREW) parallel algorithm that can solve the knapsack instances in less than O(2 n/2) time when the available hardware resource is smaller than O(2 n/2), and hence is an improved result over the past researches. |
| |
| Keywords: | Knapsack problem NP-Hard Parallel algorithm Memory conflicts Hardware-time tradeoff |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
