Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Parallel Flow Accumulation Alg...

Parallel Flow Accumulation Algorithms for Graphical Processing Units with Application to RUSLE Mode

Johan Sten, Harri Lilja, Jari Hyväluoma, Jan Westerholm, Mats Aspnäs, Parallel Flow Accumulation Algorithms for Graphical Processing Units with Application to RUSLE Mode. Computers & Geosciences 89, 88–95, 2016.

http://dx.doi.org/10.1016/j.cageo.2016.01.006

Abstract:

Digital elevation models (DEMs) are widely used in the modeling of surface hydrology, which typically includes the determination of flow directions and flow accumulation. The use of high-resolution DEMs increases the accuracy of flow accumulation computation, but as a drawback, the computational time may become excessively long if large areas are analyzed. In this paper we investigate the use of graphical processing units (GPUs) for efficient flow accumulation calculations. We present two new parallel flow accumulation algorithms based on dependency transfer and topological sorting and compare them to previously published flow transfer and indegree-based algorithms. We benchmark the GPU implementations against industry standards, ArcGIS and SAGA. With the flow-transfer D8 flow routing model and binary input data, a speed up of 19 is achieved compared to ArcGIS and 15 compared to SAGA. We show that on GPUs the topological sort-based flow accumulation algorithm leads on average to a speedup by a factor of 7 over the flow-transfer algorithm. Thus a total speed up of the order of 100 is achieved. We test the algorithms by applying them to the Revised Universal Soil Loss Equation (RUSLE) erosion model. For this purpose we present parallel versions of the slope, LS factor and RUSLE algorithms and show that the RUSLE erosion results for an area of 12 km x 24 km containing 72 million cells can be calculated in less than a second. Since flow accumulation is needed in many hydrological models, the developed algorithms may find use in many other applications than RUSLE modeling. The algorithm based on topological sorting is particularly promising for dynamic hydrological models where flow accumulations are repeatedly computed over an unchanged DEM.

BibTeX entry:

@ARTICLE{aconv27849,
  title = {Parallel Flow Accumulation Algorithms for Graphical Processing Units with Application to RUSLE Mode},
  author = {Sten, Johan and Lilja, Harri and Hyväluoma, Jari and Westerholm, Jan and Aspnäs, Mats},
  journal = {Computers & Geosciences},
  volume = {89},
  publisher = {Elsevier},
  pages = {88–95},
  year = {2016},
  keywords = {Algorithms; DEM; GPGPU; Hydrology; Parallel; RUSLE},
  ISSN = {1873-7803},
}

Belongs to TUCS Research Unit(s): Software Engineering Laboratory (SE Lab)

Edit publication