International Journal of Computer Applications |
Foundation of Computer Science (FCS), NY, USA |
Volume 69 - Number 3 |
Year of Publication: 2013 |
Authors: Mohsin Altaf Wani, S. M. K Quadri |
10.5120/11822-7518 |
Mohsin Altaf Wani, S. M. K Quadri . Accelerated Dynamic Programming on GPU: A Study of Speed Up and Programming Approach. International Journal of Computer Applications. 69, 3 ( May 2013), 18-21. DOI=10.5120/11822-7518
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(n3)-time complexity algorithm and a work space of size O(n2). The main contribution of this paper is to present a parallel implementation of this O(n3)-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.