Accelerated Dynamic Programming on GPU: A Study of Speed Up and Programming Approach

Mohsin Altaf Wani, S.M.K Quadri
Research Scholar computer science, Mewar University, Chittorgarh, Rajasthan
International Journal of Computer Applications, Volume 69, No.3, 2013


   title={Accelerated Dynamic Programming on GPU: A Study of Speed Up and Programming Approach},

   author={Wani, Mohsin Altaf and Quadri, S.M.K},



Download Download (PDF)   View View   Source Source   



GPUs (Graphics processing units) can be used for general purpose parallel computation. Developers can develop parallel programs running on GPUs using different computing architectures like CUDA or OpenCL. The Optimal Matrix Chain Multiplication problem is an optimization problem to find the optimal order for multiplying a chain of matrices. The optimal order of multiplication depends only on the dimensions of the matrices. It is known that this problem can be solved by dynamic programming technique using O(n^3)-time complexity algorithm and a work space of size O(n^2). The main contribution of this paper is to present a parallel implementation of this O(n^3)-time algorithm on a GPU and to assess the amount of programming effort required to develop this parallel implementation when compared to a similar sequential implementation.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: