IEEE Robotics & Automation Magazine - December 2016 - 169

× 10-4
TPE on CPU
TPE on GPU

Time per Edge (ms)

7
6
5
4
3
2
1
0

6
8
10 12
Number of Edges

Figure 4. The TPE evolution of the errors computing block (FB2).

on the GPU continues to decrease till the last step. At the last
step, on both FB2 and FB3, the GPU-based TPE is approximately five times smaller than the CPU-based TPE. Note here
that the TPEs of FB7 and FB8 blocks have approximately the
same behavior evolution.
Schur Complement
Basically, as a matrix-matrix multiplication, the Schur
complement is quadratic time. The proposed algorithm to
compute the Schur complement is linear time. It essentially depends on the number of edges resulting from the
graph reduction. Nevertheless, the robot poses neighborhood affects the processing time as well. The smaller the
neighborhood, the faster is the execution. Indeed, the
neighborhood determines the number of the serial loop
iterations, which may slow down the execution (lines 13
through 17 in Algorithm 4).
Figure 6 presents the TPE evolution of the Schur complement. If we do not take into account data transfer time from
the GPU to the CPU, the CPU gives the best TPE at the
beginning. As the number of edges increases and because of
the limited number of threads on the CPU, the TPE on the
GPU starts to slightly overcome the TPE on the CPU. This
gain also depends on how large the robot poses neighborhood is. The smaller the neighborhood, the higher is the gain
over the CPU. Each robot pose, at the end of the trajectory, is
linked to at most three landmarks. This explains the relative
gain at the end. Note also that executing FB4 on the GPU may
be slowed down by the high number of global memory
accesses to fetch and store data. Nevertheless, the graph
reduction generates many more edges than the initial graph
has. Transferring these edges (nonzero blocks of H pp ), to be
used by FB5 on the CPU, is a limiting factor of executing FB4
on the GPU. Indeed, the time transfer quickly becomes prohibitive with respect to the functional block overall run time.
In this experiment, at the last step we have to transfer 51,574
nonzero blocks (3.54 Mb). Figure 6 shows that taking into
account data transfer time increases the TPE more when
computing FB4 on the GPU.

TPE on CPU
TPE on GPU

3
2.5
2
1.5
1
0.5

18
× 103

6
8
10 12
Number of Edges

18
× 103

Figure 5. The TPE evolution of the construction block (FB3).

1.6

× 10-3
TPE on CPU
TPE on GPU
TPE on GPU + Transfer Time
TPE on CPU/GPU + Transfer Time

1.4
Time per Edge (ms)

× 10-3

3.5
Time per Edge (ms)

1.2
1
0.8
0.6
0.4
0.2
0

20
30
40
Number of Edges

60
× 103

Figure 6. The TPE evolution of the Schur complement block (FB4).

Discussion and Algorithm-Architecture Mapping
Based on the evaluations and the analysis described earlier,
the GPU gives more performances compared to the CPU for
the blocks FB2, FB3, FB7, and FB8. Nevertheless, the CPU is
more suitable to implement the Schur complement (FB4) due
to data transfer time. It should be noted that the average processing time of FB1, in these experiments, is about 0.8 ms on
the GPU and 0.2 ms on the CPU. However, FB1 should be
implemented on the GPU as FB3 to avoid data transfer from
the GPU to the CPU.
Now that the CPU is more able to compute FB4, we still
have to transfer the matrix H to the CPU. This device-to-host
transfer is not so prohibitive as the first one, because we only
transfer nonzero blocks. Furthermore, to enhance the TPE
more and minimize transferring data back to the GPU, we
split FB4 into three subblocks. The first one computes the H ll
inverse on the GPU, the second one computes the new information vector Bp on the GPU as well. The last one computes
the new information matrix H pp on the CPU after receiving
the information matrix H . Using this cooperative model
CPU-GPU, we obtain the best TPE as shown in Figure 6.
Indeed, even if we consider data transfer time, the CPU-GPU
DECEMBER 2016

IEEE ROBOTICS & AUTOMATION MAGAZINE

169

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - December 2016