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 Model

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

Abstract:

Digital elevation models (DEMs) are widely used in modeling of surface hydrology, which typically includes determination of flow directions and flow accumulation. The use of high-resolution DEMs increases the accuracy of flow accumulation results but as a drawback the computational effort may become intolerable if large areas are analyzed. In this paper we investigate the use of graphical processing units (GPUs) in efficient flow accumulation calculation. We present two new parallel flow accumulation algorithms based on dependency transfer and topological sort and compare them to previously published flow transfer and indegree-based algorithms. We benchmarked the GPU implementation against industry standard ArcGIS 10.2.1. With the flow-transfer D8 flow routing model and binary input data, a speed up of 19 was achieved compared to ArcGIS. We show that on GPUs the topological sort-based flow accumulation algorithm leads on average to a speed-up by a factor of 7 over the flow-transfer algorithm. Thus a speed up of the order of 100 was achieved. We test the algorithms by applying them to 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 accumulation is repeatedly computed over an unchanged DEM.

BibTeX entry:

@ARTICLE{jJoHaJaJaMa16a,
  title = {Parallel Flow Accumulation Algorithms for Graphical Processing Units with Application to RUSLE Model},
  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},
}

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

Edit publication