Parallel flow accumulation algorithms for graphical processing units with application to RUSLE model. (April 2016)

• Record Type: Journal Article
• Authors: Sten, Johan; Lilja, Harri; Hyväluoma, Jari; Westerholm, Jan; Aspnäs, Mats
• Is Part Of: Computers & geosciences. Volume 89(2016)
• Page Start: 88
• Page End: 95
• Publication Date: 2016-04
• Subjects: Algorithms -- DEM -- GPGPU -- Hydrology -- Parallel -- RUSLE; Environmental policy -- Periodicals; 550.5
• DOI: 10.1016/j.cageo.2016.01.006
• Languages: English
• ISSNs: 0098-3004

Abstract

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. Highlights: We present two new parallel algorithms for flow accumulation calculations on DEMs. The new algorithms are based on dependency transfer and topological sort. We demonstrate the benefit(s) of the topological sort on GPU. We benchmark our GPU implementation against industry standard ArcGIS and Saga. Speed-ups up to 100x can be achieved on GPUs.