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 language | English |
|---|---|
| Pages (from-to) | 83-98 |
| Number of pages | 16 |
| Journal | International Journal of Grid and High Performance Computing |
| Volume | 10 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - 2018 Oct 1 |
Fingerprint
All Science Journal Classification (ASJC) codes
- Computer Networks and Communications
Cite this
}
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 journal › Article
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 -