Parallel Priority-Flood Depression Filling For Trillion Cell Digital Elevation Models On Desktops Or Clusters
Author:
- Richard BarnesRBRichard Barnes
Preprint
Abstract
Algorithms for extracting hydrologic features and properties from digital elevation models (DEMs) are challenged by large datasets, which often cannot fit within a computer's RAM. Depression filling is an important preconditioning step to many of these algorithms. Here, I present a new, linearly-scaling algorithm which parallelizes the Priority-Flood depression-filling algorithm by subdividing a DEM into tiles. Using a single-producer, multi-consumer design, the new algorithm works equally well on one core, multiple cores, or multiple machines and can take advantage of large memories or cope with small ones. Unlike previous algorithms, the new algorithm guarantees a fixed number of memory access and communication events per subdivision of the DEM. In comparison testing, this results in the new algorithm running generally faster while using fewer resources than previous algorithms. For moderately sized tiles, the algorithm exhibits ~60% strong and weak scaling efficiencies up to 48 cores, and linear time scaling across datasets ranging over three orders of magnitude. The largest dataset on which I run the algorithm has 2 trillion (2*10^12) cells. With 48 cores, processing required 4.8 hours wall-time (9.3 compute-days). This test is three orders of magnitude larger than any previously performed in the literature. Complete, well-commented source code and correctness tests are available for download from a repository.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- An efficient variant of the Priority-Flood algorithm for filling depressions in raster digital elevation modelsComputers & Geosciences, 2016
- A virtual tile approach to raster-based calculations of large digital elevation models in a shared-memory systemComputers & Geosciences, 2015
- Efficient hybrid breaching-filling sink removal methods for flow path enforcement in digital elevation modelsHydrological Processes, 2015
- Priority-flood: An optimal depression-filling and watershed-labeling algorithm for digital elevation modelsComputers & Geosciences, 2014
- An efficient assignment of drainage direction over flat surfaces in raster digital elevation modelsComputers & Geosciences, 2014
- Extraction of hydrological proximity measures from DEMs using parallel processingEnvironmental Modelling & Software, 2011
- Revisiting priority queues for image analysisPattern Recognition, 2010
- A physically-based method for removing pits in digital elevation modelsAdvances in Water Resources, 2007
- Removal of artifact depressions from digital elevation models: towards a minimum impact approachHydrological Processes, 2005
- The treatment of flat areas and depressions in automated drainage analysis of raster digital elevation modelsHydrological Processes, 1998