Dynamic Programming on Multicore processor

Abstract

The strong need for increased computational performance in science and engineering has led to the use of heterogeneous computing, with GPUs, acting as coprocessors to the CPUs for arithmetic intensive data-parallel workloads. CUDA - Compute Uni- ed Device Architecture is a new industry standard for task-parallel and data-parallel heterogeneous computing on NVIDIA GPUs. Basic goal of CUDA is to help program- mers focus on the task of parallelization of the algorithms rather than spending time on their implementation. Key to performance on this platform is using massive mul- tithreading to utilize the large number of cores and hide global memory latency. The main objective of the thesis is to obtain the performance gain in execution speed for the dynamic algorithms which generally are complex and takes a very long time for execution and compare results on di erent gpu processors and CPU and have a com- parative study of algorithms. It will require running the CUDA C code in sequential and parallel on GPU consisting of hundreds of core or even more. Also the algo- rithms C code may require removing dependencies. Hence obtaining all the statistics of various algorithms and achieve performance gain in execution.The contributions of this thesis include a programming language approach to providing transforma- tion abstraction and composition, a unifying framework for general and GPU speci c transformations, and demonstration of the framework on standard benchmarks that show it capable of matching or outperforming hand-tuned GPU kernels. This thesis work is mainly concentrated on the computational part of the source code and its op- timization. Report contains study of the NVIDIA GeForce GPU architecture, CUDA SDK tool kit, Dynamic Algorithms and di fferent methods to get performance benefit, implementation of intermediate tool to find out functions and their dependencies from the source code and the implementation of the complete algorithm, testing and Obtaining statistics for the same.