Bulk Execution of the Dynamic Programming for the Optimal Polygon Triangulation on the GPU

摘要

The optimal polygon triangulation problem for a convex polygon is an optimization problem to find a triangulation with minimum total weight. It is known that this problem can be solved using the dynamic programming technique in O(n~3) time. The main contribution of this paper is to present an efficient parallel implementation of this O(n~3)-time algorithm for a lot of instances on the GPU (Graphics Processing Unit). In our proposed GPU implementation, we focused on the computation for a lot of instances and considered programming issues of the GPU architecture such as coalesced access of the global memory, warp divergence. The experimental result shows that our GPU implementation on NVIDIA TITAN X attains a speed-up factor of up to 50.6 over the sequential CPU implementation on Intel Core i7-6700K.