检索结果-内蒙古大学图书馆

A novel cooperative accelerated parallel two-list algorithm for solving the subset-sum problem on a hybrid CPU-GPU cluster

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2016年第0期97卷 112-123页

作者： Wan, Lanjun Li, Kenli Li, Keqin Hunan Univ Coll Comp Sci & Elect Engn Changsha 410082 Hunan Peoples R China Natl Supercomp Ctr Changsha Changsha 410082 Hunan Peoples R China SUNY Coll New Paltz Dept Comp Sci New Paltz NY 12561 USA

Many parallel algorithms have recently been developed to accelerate solving the subset-sum problem on a heterogeneous CPU-GPU system. However, within each compute node, only one CPU core is used to control one GPU and all the remaining CPU cores are in idle state, which leads to a large number of CPU cores being wasted. In this paper, based on a cost-optimal parallel two-list algorithm, we propose a novel heterogeneous cooperative computing approach to solve the subset-sum problem on a hybrid CPU-GPU cluster, which can make full use of all available computational resources of a cluster. The unbalanced workload distribution and the huge communication overhead are two main obstacles for the heterogeneous cooperative computing. In order to assign the most suitable workload to each compute node and reasonably partition it between CPU and GPU within each node, and minimize the inter-node and intra-node communication costs, we design a communication-avoiding workload distribution scheme suitable for the parallel two-list algorithm. According to this scheme, we provide an efficient heterogeneous cooperative implementation of the algorithm. A series of experiments are conducted on a hybrid CPU-GPU cluster, where each node has two 6-core CPUs and one GPU. The results show that the heterogeneous cooperative computing significantly outperforms the CPU-only or GPU-only computing. (C) 2016 Elsevier Inc. All rights reserved.

关键词： Heterogeneous cooperative computing Hybrid CPU-GPU cluster Hybrid programming model Subset-sum problem two-list algorithm Workload distribution

来源：评论

学校读者我要写书评

暂无评论

Efficient Parallelization of a two-list algorithm for the Subset-Sum Problem on a Hybrid CPU/GPU Cluster 6

Efficient Parallelization of a Two-List Algorithm for the Su...

引用

6th International Symposium on Parallel Architectures, algorithms, and Programming (PAAP)

作者： Kang, Letian Wan, Lanjun Li, Kenli Hunan Univ Coll Informat Sci & Engn Changsha 410082 Hunan Peoples R China

ISBN: (纸本)9781479938445

Recently, hybrid CPU/GPU cluster has been widely used to deal with compute-intensive problems, such as the subset-sum problem. The two-list algorithm is a well known approach to solve the problem. However, a hybrid MPI-CUDA dual-level parallelization of the algorithm on the cluster is not straightforward. The key challenge is how to allocate the most suitable workload to each node to achieve good load balancing between nodes and minimize the communication overhead. Therefore, this paper proposes an effective workload distribution scheme which aims to reasonably assign workload to each node. According to this scheme, an efficient MPI-CUDA parallel implementation of a two-list algorithm is presented. A series of experiments are conducted to compare the performance of the hybrid MPI-CUDA implementation with that of the best sequential CPU implementation, the single-node CPU-only implementation, the single-node GPU-only implementation, and the hybrid MPI-OpenMP implementation with same cluster configuration. The results show that the proposed hybrid MPI-CUDA implementation not only offers significant performance benefits but also has excellent scalability.

关键词： MPI-CUDA implementation hybrid CPU/GPU cluster two-list algorithm subset-sum problem knapsack problem

来源：评论

学校读者我要写书评

暂无评论

Observations on optimal parallelizations of two-list algorithm

引用

PARALLEL COMPUTING 2010年第1期36卷 65-67页

作者： Alonso Sanches, Carlos Alberto Soma, Nei Yoshihiro Yanasse, Horacio Hideki CTA ITA IEC Inst Tecnol Aeronaut BR-12228900 Sao Jose Dos Campos SP Brazil INPE LAC Inst Nacl Pesquisas Espaciais BR-12227010 Sao Jose Dos Campos SP Brazil

For more than three decades, the very well known and famous two-list Horowitz and Sahni algorithm [3] remains the serial upper-bound for the 0-1 Knapsack problem with n items (KP01) in a time bounded by O(2(n/2)). Recently, Chedid [2] Suggested an optimal parallelization for that algorithm to a KP01 variation - the subset-sum problem - in a PRAM CREW with p = 2(n/8) processors. It is presented here that, in addition to be incomplete, the Chedid result is a particular case given by Sanches et al. [6]. (c) 2009 Elsevier B.V. All rights reserved.

关键词： Knapsack problem Subset-sum problem Parallel algorithm two-list algorithm

来源：评论

学校读者我要写书评

暂无评论

An optimal parallelization of the two-list algorithm of cost O(2^n/2)

引用

PARALLEL COMPUTING 2008年第1期34卷 63-65页

作者： Chedid, Fouad B. Univ Notre Dame Dept Comp Sci Zouk Mikael Zouk Mosbeh Lebanon

In 1994, Chang et al. [Parallel Computing 20 (1994)] claimed a parallelization of the two-list algorithm of cost O(2(5n/8)) based on a shared memory CREW SIMD PRAM model of computation. In 1997, Lou and Chang [Parallel Computing 22 (1997)] proposed a novel search phase for the two-list algorithm which when combined with Chang et al.'s generation phase gives an optimal parallelization of the two-list algorithm. In 2002, Sanches et al. [Parallel Computing 28 (2002)] proved that the results about Chang et al.'s generation phase are incorrect invalidating both Chang et al's and Lou and Chang's results. In this paper, we describe a new generation phase for the two-list algorithm which when combined with the search phase of Lou and Chang reclaims an optimal parallelization of the two-list algorithm of cost O(2(n/2)) (c) 2007 Elsevier B.V. All rights reserved.

关键词： Knapsack problem two-list algorithm parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：