Optimizing dynamic programming on graphics processing units via adaptive thread-level parallelism

Chao Chin Wu, Jenn Yang Ke, Heshan Lin, Wu Chun Feng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Citations (Scopus)

Abstract

Dynamic programming (DP) is an important computational method for solving a wide variety of discrete optimization problems such as scheduling, string editing, packaging, and inventory management. In general, DP is classified into four categories based on the characteristics of the optimization equation. Because applications that are classified in the same category of DP have similar program behavior, the research community has sought to propose general solutions for parallelizing each category of DP. However, most existing studies focus on running DP on CPU-based parallel systems rather than on accelerating DP algorithms on the graphics processing unit (GPU). This paper presents the GPU acceleration of an important category of DP problems called nonserial polyadic dynamic programming (NPDP). In NPDP applications, the degree of parallelism varies significantly in different stages of computation, making it difficult to fully utilize the compute power of hundreds of processing cores in a GPU. To address this challenge, we propose a methodology that can adaptively adjust the thread-level parallelism in mapping a NPDP problem onto the GPU, thus providing sufficient and steady degrees of parallelism across different compute stages. We realize our approach in a real-world NPDP application - the optimal matrix parenthesization problem. Experimental results demonstrate our method can achieve a speedup of 13.40 over the previously published GPU algorithm.

Original languageEnglish
Title of host publicationProceedings - 2011 17th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2011
Pages96-103
Number of pages8
DOIs
Publication statusPublished - 2011 Dec 1
Event2011 17th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2011 - Tainan, Taiwan
Duration: 2011 Dec 72011 Dec 9

Publication series

NameProceedings of the International Conference on Parallel and Distributed Systems - ICPADS
ISSN (Print)1521-9097

Other

Other2011 17th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2011
CountryTaiwan
CityTainan
Period11-12-0711-12-09

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Cite this

Wu, C. C., Ke, J. Y., Lin, H., & Feng, W. C. (2011). Optimizing dynamic programming on graphics processing units via adaptive thread-level parallelism. In Proceedings - 2011 17th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2011 (pp. 96-103). [6121265] (Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS). https://doi.org/10.1109/ICPADS.2011.92