Skip to main content
padlock icon - secure page this page is secure

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

Buy Article:

$106.34 + tax (Refund Policy)

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
No Metrics

Keywords: CUDA; Dynamic Programming; MCM; Multicore; OpenMP

Document Type: Research Article

Affiliations: 1: Department of Computer Science and Engineering, Ramdeobaba College of Engineering and Management, Nagpur, Maharashtra, 440013, India 2: 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
  • Access Key
  • Free content
  • Partial Free content
  • New content
  • Open access content
  • Partial Open access content
  • Subscribed content
  • Partial Subscribed content
  • Free trial content
Cookie Policy
X
Cookie Policy
Ingenta Connect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more