A sample implementation for parallelizing Divide-and-Conquer algorithms on the GPU

Gang Mei; Jiayin Zhang; Nengxiong Xu; Kunyang Zhao

doi:10.1016/j.heliyon.2018.e00512

A sample implementation for parallelizing Divide-and-Conquer algorithms on the GPU

Heliyon. 2018 Jan 18;4(1):e00512. doi: 10.1016/j.heliyon.2018.e00512. eCollection 2018 Jan.

Authors

Gang Mei^{1

2}, Jiayin Zhang¹, Nengxiong Xu¹, Kunyang Zhao¹

Affiliations

¹ School of Engineering and Technology, China University of Geosciences, Beijing 100083, China.
² Institute of Earth and Environmental Science, University of Freiburg, Albertstr. 23B 79104, Freiburg im Breisgau, Germany.

Abstract

The strategy of Divide-and-Conquer (D&C) is one of the frequently used programming patterns to design efficient algorithms in computer science, which has been parallelized on shared memory systems and distributed memory systems. Tzeng and Owens specifically developed a generic paradigm for parallelizing D&C algorithms on modern Graphics Processing Units (GPUs). In this paper, by following the generic paradigm proposed by Tzeng and Owens, we provide a new and publicly available GPU implementation of the famous D&C algorithm, QuickHull, to give a sample and guide for parallelizing D&C algorithms on the GPU. The experimental results demonstrate the practicality of our sample GPU implementation. Our research objective in this paper is to present a sample GPU implementation of a classical D&C algorithm to help interested readers to develop their own efficient GPU implementations with fewer efforts.

Keywords: Computer science.