A Generalized Strategy for Parallelization of Non-Serial Polyadic Dynamic Programming on Multicore and Manycore

Dynamic programming is a computational methodology used for various combinatorial and optimization problems. We mainly emphasize on the parallelization aspects of non-serial polyadic dynamic programming (NPDP) algorithm, Matrix chain multiplication (MCM) on multicore and manycore. Due to non-uniformity in the dependence and heterogeneity of load at different phases, parallelization of NPDP problem and related issues are targeted on multicore and manycore. We realize the parallelization of MCM algorithm on Intel Xeon CPU E5-2698 using OpenMP and on QuadroK6000 GPU using Compute Unified Device Architecture (CUDA). By realizing the parallelization of MCM on multicore using OpenMP with different scheduling techniques, we reach to the conclusion that static scheduling is not suitable for NPDP problems. We implement parallel MCM on manycore GPU with same block-size for each phase and draw the conclusion that when the number of streaming multiprocessors on the GPU is not completely utilized, performance degradation occurs in the course of parallelization. In the direction of effective utilizations of GPU hardware resources, we propose a parallelization technique for NPDP problems on GPU that adaptively adjusts the block-size for different phases so as to utilize more number of streaming multiprocessors in each phase. This technique achieves approximately 14% speedup as compared to fixed block-size approach for a sufficiently large input. We also propose a generalized approach for effective scheduling of subproblems of NPDP problems on multicore and manycore in the direction of effective utilization of hardware and software resources.