Load balancing methods and parallel dynamic programming algorithm using dominance technique applied to the 0-1 knapsack problem

被引：22

作者：

El Baz, D ^{[1
]}

Elkihel, M ^{[1
]}

机构：

[1] CNRS, LAAS, F-31077 Toulouse 4, France

来源：

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING | 2005年 / 65卷 / 01期

关键词：

parallel computing; load balancing; 0-1 knapsack problem; dynamic programming; dominance technique;

D O I：

10.1016/j.jpdc.2004.10.004

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The parallelization on a supercomputer of a one list dynamic programming algorithm using dominance technique and processor cooperation for the 0-1 knapsack problem is presented. Such a technique generates irregular data structure, moreover the number of undominated states is unforeseeable. Original and efficient load balancing strategies are proposed. Finally, computational results obtained with an Origin 3800 supercomputer are displayed and analyzed. To the best of our knowledge, this is the first time for which computational experiments on a supercomputer are presented for a parallel dynamic programming algorithm using dominance technique. (C) 2004 Elsevier Inc. All rights reserved.

引用

页码：74 / 84

页数：11

共 27 条

[1] MERGING AND SORTING APPLIED TO ZERO-ONE KNAPSACK PROBLEM [J].