Massively Parallel Construction of the Cell Graph

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

Abstract

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
Pages559-569
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.
DOIDOI:10.1007/978-3-319-32149-3_52
URL http://link.springer.com/chapter/10.1007%2F978-3-319-32149-3_52
Languageen angielski
Score (nominal)15
Score sourceconferenceIndex
ScoreMinisterial score = 15.0, 08-11-2019, BookChapterSeriesAndMatConfByConferenceseries
Ministerial score (2013-2016) = 15.0, 08-11-2019, BookChapterSeriesAndMatConfByConferenceseries
Publication indicators Scopus Citations = 1; WoS Citations = 1
Citation count*
Cite
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.
Back
Confirmation
Are you sure?