IEEE Geoscience and Remote Sensing Magazine - September 2016 - 60

processes communicate using a message-passing interface
(MPI) via the host central processing units (CPUs). The implementation can utilize any number of nodes, with one or
many GPUs per node. The performance and scalability of
the program have been tested with a 10-m DEM covering
390,905 km2, i.e., the entire area of Finland. Performing
the drainage basin delineation for the DEM with different
numbers of GPUs shows a nearly linear strong scalability.
UNCERTAINTY-AWARE GEOSPATIAL ANALYSIS
In uncertainty-aware geospatial analysis, we compute not
only the solution to a given problem but also the estimates
of the uncertainty of the solution [1]-[4]. Determining the
reliability of the analysis is important because, in many
cases, decisions are made based on the result of an analysis that may have a significant economic impact or affect
human lives. For example, issuing storm warnings would
allow individuals to prepare for approaching storms in
time, but, if the predictions are unreliable, the false alerts
render the warnings useless. When choosing a location for
the long-term storage of nuclear waste, one wants to make
sure that the location that the model predicts to be stable is
not simply a random artifact that moves or disappears with
the slightest change in input data. Knowing the reliability
of the borders of the drainage basins [5], [6] will help to
ensure that proper action is taken, e.g., in the case of accidents where toxic material spills onto the ground. In general, knowledge of the uncertainty of the result of an analysis indicates whether the result can be trusted or whether
more accurate data are needed or another analysis method
is required.
Although the foundation for uncertainty-aware geospatial analysis is rather well established [1], [4], it has received
relatively little practical usage. This is partly due to the fact
that the analysis of uncertainty is computationally very demanding, because the implementations use MC simulations
in which the underlying analysis is repeated typically 1,000
times, if not more [1]. It is evident that carrying out uncertainty-aware geospatial analysis with large data sets covering
geographically extensive areas pushes the computation facilities to their limits.
Large computing clusters are common nowadays, but
programs and algorithms must be developed for parallel
execution to harness the available resources efficiently.
Unfortunately, the traditional software packages commonly used in the application field of geographic information systems (GIS) do not benefit from powerful
computing clusters as well as they could [7]-[10]. For
example, in the Geographic Resources Analysis Support
System (GRASS) GIS package, only some of the functionality supports parallelism [11]. In this article, we describe
our design and implementation of an uncertainty-aware
drainage basin delineation program that uses multiple
GPUs to speed up the calculations and permit efficient
processing of large DEMs that do not fit into the RAM of
a regular workstation.
60

Some work has been reported wherein GPUs have been
used to speed up some common analyses [12]-[18]; however, they are typically limited to one GPU. This work is a continuation of the work reported in [18], where preliminary
benchmark calculations of a drainage delineation program
using multiple GPUs were presented. We have identified
and analyzed the main bottlenecks of the implementation
and developed the algorithms further.
In the following sections, we describe the principles on
which the program is based to achieve good performance
and scalability. For benchmarking, we use a country-wide
DEM covering 390,905 km2, which is the area of Finland,
in 10-m resolution [19]. To our knowledge, this is the first
time that uncertainty-aware geospatial analysis has been
carried out for areas covering an entire country. In addition, this was done in a single run.
Based on the benchmarking, we demonstrate that the
cost to compute uncertainty-aware drainage basin delineations for country-wide data sets has been reduced to a
rather low level. We argue that we have reached a situation
in which cost alone is not a sufficient reason to neglect the
computation and presentation of uncertainty maps. These
statements are based on and apply to the drainage basin
delineation task. As discussed at the end of the article, our
implementation could be used as a framework for other
similar uncertainty-aware geospatial analysis tasks.
In our study, the motivation for fast, scalable computing
solutions is based on the need to produce uncertainty maps
and on the underlying MC simulation, which is a computationally intensive task. The need for fast, scalable programs
for geospatial analysis is, however, much more generic,
i.e., high-resolution data are available in such volumes,
velocities, and varieties that they deserve to be called big
geospatial data. Efficient use of these data fundamentally
depends on quick, on-demand computations, i.e., the ability to produce timely inputs for environmental decisionmaking processes. At the same time, multi-GPU computing
clusters are increasingly being used for scientific and technical computing. In this respect, the presented work can
serve as a high-performance geocomputing demonstration
on the efficient use of computing resources.
DRAINAGE BASIN DELINEATION ALGORITHM
We begin by describing the process of uncertainty-aware
basin delineation, and then we outline the parallelization
of the task to multiple GPUs.
A BASIC DRAINAGE BASIN DELINEATION ALGORITHM
A drainage basin delineation algorithm is presented in [17],
[18], [20], and [21]. In short, a basic algorithm that does
not take the uncertainty of the DEM into account reads the
DEM and the stream data as the input and provides the borders of the drainage basins as the output. The principal idea
is to determine the stream to which the surficial flow leads
from each cell. The basic algorithm consists of the following parts that are executed sequentially:
ieee Geoscience and remote sensinG maGazine

september 2016

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