GPU Based Non-Serial Polyadic Dynamic Programming Template

Mohsin Altaf Wani; Dr. Manzoor Ahmad

doi:10.37591/rtpc.v4i3.1284

Abstract

AbstractNon-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, skeletonCite this ArticleMohsin Altaf Wani, Manzoor Ahmad. GPU Based Non-Serial Polyadic Dynamic Programming Template. Recent Trends in Parallel Computing. 2017; 4(3): 29–39p.