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

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications

Cite this