Welcome to the InfoSci Platform
Reference Hub10
Adjusting Thread Parallelism Dynamically to Accelerate Dynamic Programming with Irregular Workload Distribution on GPGPUs

Adjusting Thread Parallelism Dynamically to Accelerate Dynamic Programming with Irregular Workload Distribution on GPGPUs

Chao-Chin Wu, Jenn-Yang Ke, Heshan Lin, Syun-Sheng Jhan
Copyright: © 2014 |Volume: 6 |Issue: 1 |Pages: 20
ISSN: 1938-0259|EISSN: 1938-0267|EISBN13: 9781466654433|DOI: 10.4018/ijghpc.2014010101
Cite Article Cite Article

MLA

Wu, Chao-Chin, et al. "Adjusting Thread Parallelism Dynamically to Accelerate Dynamic Programming with Irregular Workload Distribution on GPGPUs." IJGHPC vol.6, no.1 2014: pp.1-20. http://doi.org/10.4018/ijghpc.2014010101

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 (IJGHPC), 6(1), 1-20. http://doi.org/10.4018/ijghpc.2014010101

Chicago

Wu, Chao-Chin, et al. "Adjusting Thread Parallelism Dynamically to Accelerate Dynamic Programming with Irregular Workload Distribution on GPGPUs," International Journal of Grid and High Performance Computing (IJGHPC) 6, no.1: 1-20. http://doi.org/10.4018/ijghpc.2014010101

Export Reference

Mendeley
Favorite Full-Issue Download

Abstract

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.

Request Access

You do not own this content. Please login to recommend this title to your institution's librarian or purchase it from the IGI Global bookstore.