Parallel Computing in Geography - GeoComputation - page 54

modelling could place geography and the social sciences firmly in the supercomputing arena. He
argued that knowledge and the ability to model human systems, such as cities, are of vital impor-
tance since the majority of the world's population lives in cities, and urbanisation, particularly in
developing countries, continues at a rapid rate. Moreover, human influences on climate remained
poorly understood or modelled, and Openshaw saw that the increasing size and speed of the new
supercomputers in the mid-1990s, combined with the ever larger amounts of data being produced
by the spatial data revolution, would allow geography and the social sciences to start to model
these phenomena. It was also recognised by Ding and Densham (1996) that parallel computing
would allow geographers to gain a better understanding of geographical phenomena by being able
to better model spatial relationships. Moreover, parallel implementations of models are more in
line with complex geographical phenomena, which are characterised by multiple simultaneous
events, than the more traditional sequential modelling approach (Openshaw and Turton 2000). A
wake-up call is offered by Armstrong (2000), who makes the important point that geographers
must actively contribute to research on parallel computing in order to solve geographical problems
or they will find other disciplines moving into the spatial arena and reinventing many spatial con-
cepts and methods.
Early research in parallel computing in geography showed that it had practical applications in
transportation and land-use modelling (Harris 1985; Xiong and Marble 1996), spatial data han-
dling and analysis (Sandhu and Marble 1988), least cost path calculations (Smith et al. 1989), earth
observation (Mineter and Dowers 1999; Aloisio and Cafaro 2003) and in speeding up other GIS
operations such as polygon overlay, line shading and line simplification (Wang 1993; Mower 1996;
Roche and Gittings 1996). Parallel implementations of spatial interpolation algorithms, in particu-
lar, are an area that has seen a great deal of activity both in the past (Armstrong and Marciano
1993, 1994, 1995, 1996, 1997; Wang and Armstrong 2003) and more recently (Srinivasan et al.
2010; Guan et al. 2011; Henneboehl et al. 2011; Pesquer et al. 2011). Similarly, digital terrain anal-
ysis is another area of active research interest with respect to parallel computing, for example, the
early work by Peucker and Douglas (1975). More recently, Do et al. (2010) implemented a parallel
algorithm to delineate catchments from a digital elevation model (DEM) using OpenMPI and C++
on an eight-node machine, achieving near linear speed-up, particularly for larger DEMs. Parallel
computing has also been used in the calculation of other hydrological parameters from a DEM, for
example, the calculation of flow accumulation, that is, how much water accumulates in each grid
cell based on neighbouring flows of water in a catchment, and other hydrological proximity mea-
sures (Tesfa et al. 2011). For example, Wallis et al. (2009) developed a set of parallel algorithms
for flow direction and accumulation using MPI (message passing interface). Testing the parallel
implementations against the serial one not only resulted in considerable speed-up but also revealed
that larger DEMs can be processed that would not be possible through the serial algorithm alone.
GPU was used in the parallel implementation of flow accumulation by Qin and Zhan (2012), while
Yao et al. (2012) applied a sweeping algorithm to flow accumulation calculations that could be
run in parallel. These applications, however, are for the most part still data parallelism . There is
no real re-engineering of a fresh or novel solution that demands parallel thinking and complex
parallel programming!
Progress continues to be made in the field of GIS, but this is largely in experimental systems
with few if any of the vendors of GIS systems showing any interest in developing parallel systems
commercially. However, ESRI's ArcGIS server can now execute some large geoprocessing jobs in
a parallel manner (ESRI 2009), and parallel databases are being developed for the business market
which have obvious benefits to the GIS community. In general, it is the database operations that
make a GIS slow; with the development of graphics coprocessors, visualising even very large data
sets is no longer a problem. However, carrying out large and complex queries of the database can
still be very slow and is inherently parallel. More recently, geography has linked parallel comput-
ing architectures to the development of GIS algorithms and toolkits using HPC, for example; see
Clematis et al. (2003) as well as distributed approaches (Hawick et al. 2003).