• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Performance Tuning and Sparse Traversal Technique for a Cell-Based Fetch Length Algorithm on a GPU

Mika Murtojärvi, Olli Nevalainen, Ville Leppänen, Performance Tuning and Sparse Traversal Technique for a Cell-Based Fetch Length Algorithm on a GPU. Concurrency and Computation: Practice and Experience 27(17), 5114–5133, 2015.

Abstract:

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

BibTeX entry:

@ARTICLE{jMuNeLe15a,
  title = {Performance Tuning and Sparse Traversal Technique for a Cell-Based Fetch Length Algorithm on a GPU},
  author = {Murtojärvi, Mika and Nevalainen, Olli and Leppänen, Ville},
  journal = {Concurrency and Computation: Practice and Experience},
  volume = {27},
  number = {17},
  publisher = {Wiley},
  pages = {5114–5133},
  year = {2015},
  ISSN = {1532-0626},
}

Belongs to TUCS Research Unit(s): Algorithmics and Computational Intelligence Group (ACI), Software Development Laboratory (SwDev)

Publication Forum rating of this publication: level 1

Edit publication