Using inter-block synchronization to improve the knapsack problem on GPUs

Xue Sun, Chao-Chin Wu, Liang-Rui Chen, Jian You Lin

Research output: Contribution to journalArticle

Abstract

This article describes how as one of the hot parallel processors, the general-purpose graphics processing unit (GPU) has been widely adopted to accelerate various time-consuming algorithms. Dynamic programming (DP) optimization is a popular method to solve a particular class of complex problems. This article focuses on serial-monadic DP problems onto NVIDIA GPUs. As 0/1 knapsack is one of the most representational problems in this category and it often arises in many other fields of applications. The previous work proposed the compression method to reduce the amount of data transferred, but data in shared memory cannot be reused. This article demonstrates how to apply a more condensed data structure and the inter-block synchronization to efficiently map the serialmonadic DP onto GPUs. Computational experiments reveal that the best performance improvement of the approach is about 100% comparing with the previous work.

Original languageEnglish
Pages (from-to)83-98
Number of pages16
JournalInternational Journal of Grid and High Performance Computing
Volume10
Issue number4
DOIs
Publication statusPublished - 2018 Oct 1

Fingerprint

Dynamic programming
Synchronization
Data structures
Data storage equipment
Graphics processing unit
Experiments

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications

Cite this

@article{a3b1c87c6f3049f7b0f831ee4f070bb5,
title = "Using inter-block synchronization to improve the knapsack problem on GPUs",
abstract = "This article describes how as one of the hot parallel processors, the general-purpose graphics processing unit (GPU) has been widely adopted to accelerate various time-consuming algorithms. Dynamic programming (DP) optimization is a popular method to solve a particular class of complex problems. This article focuses on serial-monadic DP problems onto NVIDIA GPUs. As 0/1 knapsack is one of the most representational problems in this category and it often arises in many other fields of applications. The previous work proposed the compression method to reduce the amount of data transferred, but data in shared memory cannot be reused. This article demonstrates how to apply a more condensed data structure and the inter-block synchronization to efficiently map the serialmonadic DP onto GPUs. Computational experiments reveal that the best performance improvement of the approach is about 100{\%} comparing with the previous work.",
author = "Xue Sun and Chao-Chin Wu and Liang-Rui Chen and Lin, {Jian You}",
year = "2018",
month = "10",
day = "1",
doi = "10.4018/IJGHPC.2018100105",
language = "English",
volume = "10",
pages = "83--98",
journal = "International Journal of Grid and High Performance Computing",
issn = "1938-0259",
publisher = "IGI Global Publishing",
number = "4",

}

Using inter-block synchronization to improve the knapsack problem on GPUs. / Sun, Xue; Wu, Chao-Chin; Chen, Liang-Rui; Lin, Jian You.

In: International Journal of Grid and High Performance Computing, Vol. 10, No. 4, 01.10.2018, p. 83-98.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Using inter-block synchronization to improve the knapsack problem on GPUs

AU - Sun, Xue

AU - Wu, Chao-Chin

AU - Chen, Liang-Rui

AU - Lin, Jian You

PY - 2018/10/1

Y1 - 2018/10/1

N2 - This article describes how as one of the hot parallel processors, the general-purpose graphics processing unit (GPU) has been widely adopted to accelerate various time-consuming algorithms. Dynamic programming (DP) optimization is a popular method to solve a particular class of complex problems. This article focuses on serial-monadic DP problems onto NVIDIA GPUs. As 0/1 knapsack is one of the most representational problems in this category and it often arises in many other fields of applications. The previous work proposed the compression method to reduce the amount of data transferred, but data in shared memory cannot be reused. This article demonstrates how to apply a more condensed data structure and the inter-block synchronization to efficiently map the serialmonadic DP onto GPUs. Computational experiments reveal that the best performance improvement of the approach is about 100% comparing with the previous work.

AB - This article describes how as one of the hot parallel processors, the general-purpose graphics processing unit (GPU) has been widely adopted to accelerate various time-consuming algorithms. Dynamic programming (DP) optimization is a popular method to solve a particular class of complex problems. This article focuses on serial-monadic DP problems onto NVIDIA GPUs. As 0/1 knapsack is one of the most representational problems in this category and it often arises in many other fields of applications. The previous work proposed the compression method to reduce the amount of data transferred, but data in shared memory cannot be reused. This article demonstrates how to apply a more condensed data structure and the inter-block synchronization to efficiently map the serialmonadic DP onto GPUs. Computational experiments reveal that the best performance improvement of the approach is about 100% comparing with the previous work.

UR - http://www.scopus.com/inward/record.url?scp=85050724382&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85050724382&partnerID=8YFLogxK

U2 - 10.4018/IJGHPC.2018100105

DO - 10.4018/IJGHPC.2018100105

M3 - Article

AN - SCOPUS:85050724382

VL - 10

SP - 83

EP - 98

JO - International Journal of Grid and High Performance Computing

JF - International Journal of Grid and High Performance Computing

SN - 1938-0259

IS - 4

ER -