GPU Based Non-Serial Polyadic Dynamic Programming Template

Abstract

Abstract

Non-serial polyadic dynamic programming algorithms are used to solve combinatorial optimization problems like optimal polygon triangulation, optimal matrix multiplication and RNA secondary structure prediction using Zuker algorithm. They have irregular data access patterns and are complicated dynamic programming algorithms. Each computation is dependent on multiple entries computed earlier in the process. We provide a GPU based algorithm template that is optimized for non-serial polyadic dynamic programming algorithms. This template requires only sequential specification of a particular problem for execution on a GPU. Our algorithm template provides users the performance of massively parallel processors without having to develop the parallel algorithms entirely from scratch. Our implementation using CUDA provides up to 50 times better performance in certain test cases. 

Keywords: Non-Serial Polyadic Dynamic Programming (NPDP), CUDA, GPU, skeleton

Cite this Article

Mohsin Altaf Wani, Manzoor Ahmad. GPU Based Non-Serial Polyadic Dynamic Programming Template. Recent Trends in Parallel Computing. 2017; 4(3): 29–39p.