Divide and Conquer Skeleton on GPU

Parallelism is a suitable approach for speeding up themassive computations of applications, but parallel programmingis difficult yet. Algorithmic skeleton is a parallel programmingmodel that provides a high level of abstraction forprogrammers. This approach uses the pre-defined componentsto facilitate easier parallel programming. Divide and conquer(DC) is an appropriate parallel pattern for implementation as askeleton. The solution of the original problem is obtained bydividing it into smaller sub-problems and solving them inparallel. Today, graphics processor unit (GPU) is an attractivecomputational processor for doing tasks in parallel, because ithas a large number of process units. In this paper, divide andconquer skeleton on GPU has been proposed and namedDC_GPU. DC_GPU is a divide and conquer skeleton that isimplemented on GPU that using a consistent programminginterface in C++ for easier parallel programming. Performanceof this skeleton has been evaluated by mergesort and sobel edgedetection. The results show that obtained speedup at thisskeleton is more than 2 on GPU.

Keywords:

Algorithmic Skeleton , Divide and ConquerSkeleton , Graphics Processor Unit (GPU) , ProgrammingInterface in C++ , Mergesort , Sobel Edge Detection