I Simposio de Postgrado 2023. Ingeniería, ciencias e innovación

I SIMPOSIO 2023 AN EVALUATION OF GPU FILTERS FOR ACCELERATING THE CONVEX HULL ABSTRACT This work focuses on improving the performance of computing the convex hull, a crucial structure in computational geometry with applications in computer graphics, robotics, and data mining. Despite existing advances in algorithms for this task, there is a need to achieve even faster solutions, especially for handling more significant problems or real-time processing. The research presents an experimental evaluation of Graphic processing unit (GPU) filters designed to parallel reduce the computational cost of finding the convex hull. The proposed techniques involve a preprocessing step that filters points within an eight-vertex polygon, resulting in a reduced set of candidate points. The process to utilize parallel computation and the Manhattan distance metric to identify the vertices of the polygon and perform the point filtering. Several different approaches for the filtering stage are studied, ranging from custom CUDA kernels to established libraries likeThrust and CUB. To assess the performance of the GPU filtering algorithm, the study tests four types of point distributions: normal distribution (favorable case), uniform distribution (favorable case), circumference distribution (the worst case), and a distribution where points are randomly shifted from the circumference (intermediate case). Overall, this work contributes to enhancing the efficiency of computing the convex hull through the utilization of GPU filters. The significant performance gains observed in various scenarios highlight the potential impact of this. The GPU filtering algorithm demonstrates remarkable speed improvements, achieving up to 17.5xfasterruntimecomparedtoasequentialCPUimplementation. Moreover, the entire convex hull computation can be up to 160x faster than the fastest implementation provided by the CGAL library (the fastest implementation in the state-of-the-art) for a uniformdistribution and 23x faster for a normal distribution. 1 DCC, Universidad de Chile. 2 Departamento de Informática, Universidad Austral de Chile. *Email: rocarras@dcc.uchile.cl Roberto Carrasco 1* , Héctor Ferrada 2 , Cristóbal A. Navarro 2 Nancy Hitschfeld 1