Adjusting thread parallelism dynamically to accelerate dynamic programming with irregular workload distribution on GPGPUs

Chao Chin Wu, Jenn Yang Ke, Syun Sheng Jhan, Heshan Lin

研究成果: Article

8 引文 斯高帕斯(Scopus)

摘要

Dynamic Programming (DP) is an important and popular method for solving a wide variety of discrete optimization problems such as scheduling, string-editing, packaging, and inventory management. DP breaks problems into simpler subproblems and combines their solutions into solutions to original ones. This paper focuses on one type of dynamic programming called Nonserial Polyadic Dynamic Programming (NPDP). To run NPDP applications efficiently on an emerging General-Purpose Graphic Processing Unit (GPGPU), the authors have to exploit more parallelism to fully utilize the computing power of the hundreds of processing units in it. However, the parallelism degree varies significantly in different phases of the NPDP applications. To address the problem, the authors propose a method that can adjust the thread-level parallelism to provide a sufficient and steadier parallelism degree for different phases. If a phase has insufficient parallelism, the authors split threads into subthreads. On the other hand, the authors can limit the total number of threads in a phase by merging threads. The authors also examine the difference between the conventional problem of finding the minimum on a GPU and the NPDP-featured problem of finding the minimums of many independent sets on a GPU. Finally, the authors examine how to design an appropriate data structure to apply the memory coalescing optimization technique. The experimental results demonstrate our method can obtain the best speedup of 13.40 over the algorithm published previously.

原文English
頁(從 - 到)1-20
頁數20
期刊International Journal of Grid and High Performance Computing
6
發行號1
DOIs
出版狀態Published - 2014 一月 1

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications

指紋 深入研究「Adjusting thread parallelism dynamically to accelerate dynamic programming with irregular workload distribution on GPGPUs」主題。共同形成了獨特的指紋。

  • 引用此