Adjusting Thread Parallelism Dynamically to Accelerate Dynamic Programming with Irregular Workload Distribution on GPGPUs
International Journal of Grid and High Performance Computing · 2014
DOI: 10.4018/ijghpc.2014010101 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Journal of Grid and High Performance Computing, 2014. Verfasst von Chao-Chin Wu und 3 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 28 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
APA
Wu, C., Ke, J., Lin, H., & Jhan, S. (2014). Adjusting Thread Parallelism Dynamically to Accelerate Dynamic Programming with Irregular Workload Distribution on GPGPUs. International Journal of Grid and High Performance Computing. https://doi.org/10.4018/ijghpc.2014010101
Vancouver
Wu C, Ke J, Lin H, Jhan S. Adjusting Thread Parallelism Dynamically to Accelerate Dynamic Programming with Irregular Workload Distribution on GPGPUs. International Journal of Grid and High Performance Computing. 2014. doi:10.4018/ijghpc.2014010101
BibTeX
@article{Wu2014,
author = {Wu, Chao-Chin and Ke, Jenn-Yang and Lin, Heshan and Jhan, Syun-Sheng},
title = {Adjusting Thread Parallelism Dynamically to Accelerate Dynamic Programming with Irregular Workload Distribution on GPGPUs},
journal = {International Journal of Grid and High Performance Computing},
year = {2014},
doi = {10.4018/ijghpc.2014010101}
}
EUVIMED