Massively Parallel Construction of the Cell Graph

Krzysztof Kaczmarski , Paweł Rzążewski , Albert Wolant


Motion planning is an important and well-studied field of robotics. A typical approach to finding a route is to construct a cell graph representing a scene and then to find a path in such a graph. In this paper we present and analyze parallel algorithms for constructing the cell graph on a SIMD-like GPU processor. Additionally, we present a new implementation of the dictionary data type on a GPU device. In the contrary to hash tables, which are common in GPU algorithms, it uses a radix search tree in which all values are kept in leaves. With such a structure we can effectively perform dictionary operations on a set of long vectors over a limited alphabet.
Author Krzysztof Kaczmarski ZSPI
Krzysztof Kaczmarski,,
- Department of Information Processing Systems
, Paweł Rzążewski ZSPI
Paweł Rzążewski,,
- Department of Information Processing Systems
, Albert Wolant WMiNI
Albert Wolant,,
- Faculty of Mathematics and Information Science
Publication size in sheets0.5
Book Wyrzykowski Roman, Deelman Ewa, Dongarra Jack , Karczewski Konrad , Kitowski Jacek, Wiatr Kazimierz (eds.): PARALLEL PROCESSING AND APPLIED MATHEMATICS, PPAM 2015, PT I, Lecture Notes In Computer Science, vol. 9573, 2016, SPRINGER INT PUBLISHING AG, ISBN 978-3-319-32149-3, [978-3-319-32148-6]
Keywords in EnglishCell graph, Motion planning, GPGPU, CUDA
Abstract in PolishW pracy przedstawiono nowe równoległe algorytmy konstruujące graf sąsiedztwa komórek w przestrzeni w przeszkodami. Algorytmy zostały zaprojektowane dla modelu obliczeniowego GP GPU.
Languageen angielski
Score (nominal)15
ScoreMinisterial score = 15.0, 27-06-2017, BookChapterSeriesAndMatConf
Ministerial score (2013-2016) = 15.0, 27-06-2017, BookChapterSeriesAndMatConf
Citation count*0
Share Share

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.