IEEE Geoscience and Remote Sensing Magazine - September 2016 - 66

Speedup

These formulae show that the achieved speedup can vary
considerably with small numbers of MC iterations, but, as
the number of iterations increases, the fluctuations in the
individual MC iterations average out.
Another commonly used quantity is the efficiency E Np ,
which, in our case, is defined as

Ideal
Measured

10 T10
10
E Np = p S Np =
.
p Tp

A value close to one means that the scaling is efficient,
whereas a value closer to zero indicates inefficient scaling.
The standard deviation for the efficiency is given simply by

1
10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40
Number of GPUs
FIGURE 6. The speedup as a function of the number of GPUs for

the analysis of the whole of Finland, calculated from the benchmark calculations with 50 MC iterations. The error bars show the
standard deviation for the derived speedup values for the analyses
with 49 MC iterations.
The speedup for an analysis with N MC iterations is calculated from the ideal execution times using
S Np =

N
T10
T 10
=
.
Tp
T Np

(3)

The ideal case is S Np = p/10 , because we use ten GPUs as our
reference case here. The fluctuations in the individual MC
iteration times will induce variations in the speedup that is
achieved as well. We can estimate this variation by applying
the general formula for error propagation [29] to S Np , which
gives the standard deviation
2
2
2S Np
2S Np
N
N
N dT p n
N dT 10 n + d
2T p
2T 10
2
T10
d T10 2
1
d
n +d
=
2 d Tp n .
Tp
Tp
N

dS Np =

tAbLe 2. the tImING resULts OF the CpU ImpLemeNtAtION
OF the DrAINAGe DeLINeAtION ALGOrIthm, ObtAINeD
FrOm COmpUtING teN mC IterAtIONs UsING p threADs
AND pArtItIONs.
1

Partitioning

1×2

2×5

2 × 12

2 × 24

total time (s)

59,506

34,380

8,973

4,582

2,427

5,904.9

3,399.6

867.4

423.4

225.8

d Tp (s)

Tp (s)

49.9

42.0

13.5

6.8

1.7

S 9p

1.74

6.81

13.95

26.2
0.10

9
p

0.01

0.05

0.09

E 9p

0.87

0.68

0.58

0.54

dE 9p

0.01

The case p = 48 was computed using two nodes; other cases were computed in a single
node. The average values are calculated from the last nine MC iterations.

(5)

(4)

10
dE Np = p dS Np .

(6)

We excluded the first MC iteration and calculated the average MC iteration time from the subsequent 49 iterations of
the benchmark calculations because, in the first MC iteration, the algorithms need to perform some initialization.
The average MC iteration times, their standard deviations,
and the derived speedup and efficiency are reported in
Table 1, with the derived speedup results shown in Figure 6.
The scaling of the program is very close to ideal. One
source of variation is that the amount of imbalance in the
workload varies slightly with the number of GPUs used.
For comparison, we performed ten MC iterations using
the CPU version of the program, first in a fully serial mode
and then parallelized over two, ten, 24, and 48 threads. The
timing results are shown in Table 2. Again, the first MC iteration was excluded from the calculation of the average
values. The values are calculated using (3)-(6) but with
p = 1 as the reference case. The CPU implementation has
not been optimized to the same extent as its multi-GPU
counterpart, and it is possible that adjusting the parameters
more carefully, such as the N limit shown in Figure 3, could
improve the scaling.
A direct comparison of the average MC iteration times
indicates that the multi-GPU program using, e.g., ten
GPUs is +100 times faster than the serial CPU version. In
[17], the single GPU program was found to be roughly ten
times faster than the serial CPU program. Therefore, the
comparison of the multi-GPU program using ten GPUs
is expected to be two orders of magnitude faster than the
fully serial CPU version, and our measurements fit into
this expectation well.
The early benchmarkings of our multi-GPU program
are reported in [18]. At that stage, the scalability for multiple computing nodes was not ideal. In the current work,
we have shown good, nearly linear scalability. Based on the
benchmarking results, we can estimate that, when using
ten GPUs, uncertainty-aware computation of a drainage
basin delineation (based on 1,000 MC iterations) would
take +12.6 h for the whole of Finland. With 40 GPUs, the
computing time is less than 3.3 h.
According to CSC's pricing for academia and the public
sector [30], the GPU cost is €0.30/h. The cost for the job
ieee Geoscience and remote sensinG maGazine

september 2016

Table of Contents for the Digital Edition of IEEE Geoscience and Remote Sensing Magazine - September 2016