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.
No Reference information available - sign in for access.
No Citation information available - sign in for access.
No Supplementary Data.
No Article Media
Document Type: Research Article
Department of Computer Science and Engineering, Ramdeobaba College of Engineering and Management, Nagpur, Maharashtra, 440013, India
Department of Computer Science and Engineering, Visvesvaraya National Institute of Technology, Nagpur, Maharashtra, 440013, India
Publication date: April 1, 2017
More about this publication?
ADVANCED SCIENCE LETTERS is an international peer-reviewed journal with a very wide-ranging coverage, consolidates research activities in all areas of (1) Physical Sciences, (2) Biological Sciences, (3) Mathematical Sciences, (4) Engineering, (5) Computer and Information Sciences, and (6) Geosciences to publish original short communications, full research papers and timely brief (mini) reviews with authors photo and biography encompassing the basic and applied research and current developments in educational aspects of these scientific areas.
- Editorial Board
- Information for Authors
- Subscribe to this Title
- Ingenta Connect is not responsible for the content or availability of external websites