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

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

研究成果: Conference contribution

15 引文 斯高帕斯(Scopus)

摘要

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.

原文English
主出版物標題Proceedings - 2011 17th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2011
頁面96-103
頁數8
DOIs
出版狀態Published - 2011 十二月 1
事件2011 17th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2011 - Tainan, Taiwan
持續時間: 2011 十二月 72011 十二月 9

出版系列

名字Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS
ISSN(列印)1521-9097

Other

Other2011 17th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2011
國家Taiwan
城市Tainan
期間11-12-0711-12-09

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

指紋 深入研究「Optimizing dynamic programming on graphics processing units via adaptive thread-level parallelism」主題。共同形成了獨特的指紋。

引用此