Performance tuning and sparse traversal technique for a cell-based fetch length algorithm on a GPU

摘要

For determining distances (fetch lengths) from points to polygons in a two-dimensional Euclidean plane,rncell-based algorithms provide a simple and effective solution. They divide the input area into a grid of cellsrnthat cover the area. The objects are stored into the appropriate cells, and the resulting structure is used forrnsolving the problem. When the input objects are distributed unevenly or the cell size is small, most of therncells may be empty. The representation is then called sparse. In the method proposed in this work, each cellrncontains information about its distance to the nonempty cells. It is then possible to skip over several emptyrncells at a time without memory accesses. A cell-based fetch length algorithm is implemented on a graphicsrnprocessing unit (GPU). Because control flow divergence reduces its performance, several methods to reducernthe divergence are studied. While many of the explicit attempts turn out to be unsuccessful, sorting of therninput data and sparse traversal are observed to greatly improve performance: compared with the initial GPUrnimplementation, up to 45-fold speedup is reached. The speed improvement is greatest when the map is veryrnsparse and the points are given in a random order.