IEEE Robotics & Automation Magazine - June 2013 - 40

GPU-Mapping
Robotic Map Building with Graphical Multiprocessors

By Diego Rodriguez-Losada, Pablo San Segundo,
Miguel Hernando, Paloma de la Puente,
and Alberto Valero-Gomez

T

his article provides a
broad perspective of the
potential applicability of
graphical processing units
(GPUs) computing power
in robotics, specifically in the well-known problem
of two-dimensional (2-D) robotic mapping. There are three
possible ways of exploiting these massively parallel devices: 1)
parallelizing existing algorithms, 2) integrating already
existing parallelized general purpose software, and 3) use of
its high-computational capabilities in the inception of new
algorithms. This article presents examples for all three
options: parallelizing a popular implementation of the gridmapping algorithm, using a GPU open-source linear sparse
system solver to address the problem of linear least squares
graph minimization, and developing a novel method that can
be efficiently parallelized and executed in a GPU for handling
overlapping grid maps in a mapping with local maps
algorithm. Large speedups are shown in the experiments,
highlighting the importance of this technology in robotic
software development in the near future, as is already the case
in many other areas.
Graphical Processing Units
Although microprocessor manufacturing technology is
continuously improving, it is reaching the point at which its
physical limitations are becoming a major concern. Memory speed and power have imposed walls for increasing
processing performance by scaling the clock frequency.
Over the last few years, Moore's law and performance
improvements have been maintained mainly because of
multicore processors (multiprocessors). In the multiprocessors, several central processing unit (CPU) cores are
packaged into a single chip that takes advantage of
their proximity, for example, when accessing the cache

memory. Some well-known examples are Intel Dual-Core
and Quad systems, the Sony Cell (eight-core) processor
inside the PlayStation3, and the PowerPC Xenon (threecore) processor in Microsoft's Xbox 360.
Together with the multiprocessors, new programming
models have emerged to manage and exploit the available
parallelism of those systems. Single processors can implicitly
implement in hardware some degree of parallelization pipelining instructions, but when dealing with the multiprocessor architectures parallelization must be explicitly
implemented by the programmer. Message passing interface
is the de facto standard for high-performance distributed
computing, whereas OpenMP is probably the most extended
solution for multiprocessing in shared memory systems,
such as multicore CPUs.
Manufacturers of GPUs are also continuously improving
their systems, leading to multicore GPUs, where each core
also contains many arithmetic and logical units specialized in
parallel processing of graphics such as texture rendering, visibility computation, image processing, and so on. In addition,
the large market for graphics cards with ubiquitous threedimensional (3-D) graphics (games, computer-aided design,
multimedia, etc.), has lowered the cost of very powerful
devices that can fit into a class known as
commodity hardware. Major GPU manufacturers have recently released tools
and programming models that allow
programmers to access such computing power: the ATI (now part
of AMD) development platform
is called ATI Stream, and the
NVIDIA development

Digital Object Identifier 10.1109/MRA.2012.2220503
Date of publication: 2 May 2013

40

* IEEE ROBOTICS & AUTOMATION MAGAZINE *

JUNE 2013

1070-9932/13/$31.00©2013IEEE
Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - June 2013
