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

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

研究成果: Article同行評審

1 引文 斯高帕斯(Scopus)

摘要

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.

原文English
頁(從 - 到)83-98
頁數16
期刊International Journal of Grid and High Performance Computing
10
發行號4
DOIs
出版狀態Published - 2018 十月 1

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications

指紋 深入研究「Using inter-block synchronization to improve the knapsack problem on GPUs」主題。共同形成了獨特的指紋。

引用此