Fast Two Dimensional Convex Hull on the GPU
Center for Security, Theory, and Algorithmic Research, International Institute of Information Technology, Hyderabad, India
IEEE Workshops of International Conference on Advanced Information Networking and Applications (WAINA), 2011
@inproceedings{srungarapu2011fast,
title={Fast Two Dimensional Convex Hull on the GPU},
author={Srungarapu, S. and Reddy, D.P. and Kothapalli, K. and Narayanan, PJ},
booktitle={Advanced Information Networking and Applications (WAINA), 2011 IEEE Workshops of International Conference on},
pages={7–12},
organization={IEEE},
year={2011}
}
General purpose programming on the graphics processing units(GPGPU) has received a lot of attention in the parallel computing community as it promises to offer a large computational power at a very low price. GPGPU is best suited for regular data parallel algorithms. They are not directly amenable for algorithms which have irregular data access patterns such as convex hull, list ranking etc. In this paper, we present a GPU-optimized implementation for finding the convex hull of a two dimensional point set. Our implementation tries to minimize the impact of irregular data access patterns. Our implementation can find the convex hull of 10 million random points in less than 0.2 seconds and achieves a speedup of up to 14 over the standard sequential CPU implementation. We also discuss some of the practical issues relating to the implementation of convex hull algorithms on massively multi-threaded architectures like that of the GPU.
May 20, 2011 by hgpu
