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 (FMIS / DIPS)
Krzysztof Kaczmarski,,
- Department of Information Processing Systems
, Paweł Rzążewski (FMIS / DIPS)
Paweł Rzążewski,,
- Department of Information Processing Systems
, Albert Wolant (FMIS)
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, GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND, 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
Score sourceconferenceIndex
ScoreMinisterial score = 15.0, 10-01-2020, BookChapterSeriesAndMatConfByConferenceseries
Ministerial score (2013-2016) = 15.0, 10-01-2020, BookChapterSeriesAndMatConfByConferenceseries
Publication indicators Scopus Citations = 1; WoS Citations = 1
Citation count*
Share Share

Get link to the record

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