Parallel non-divergent flow accumulation for trillion cell digital elevation models on desktops or clusters. (June 2017)

• Record Type: Journal Article
• Authors: Barnes, Richard
• Is Part Of: Environmental modelling & software. Volume 92(2017)
• Page Start: 202
• Page End: 212
• Publication Date: 2017-06
• Subjects: Parallel computing -- Hydrology -- Geographic information system (GIS) -- Upslope area -- Contributing area; Environmental monitoring -- Computer programs -- Periodicals; Ecology -- Computer simulation -- Periodicals; Digital computer simulation -- Periodicals; Computer software -- Periodicals; Environmental Monitoring -- Periodicals; Computer Simulation -- Periodicals; Environnement -- Surveillance -- Logiciels -- Périodiques; Écologie -- Simulation, Méthodes de -- Périodiques; Simulation par ordinateur -- Périodiques; Logiciels -- Périodiques; Computer software; Digital computer simulation; Ecology -- Computer simulation; Environmental monitoring -- Computer programs; Periodicals; Electronic journals; 363.70015118
• DOI: 10.1016/j.envsoft.2017.02.022
• Languages: English
• ISSNs: 1364-8152

Abstract

Abstract: Continent-scale datasets challenge hydrological algorithms for processing digital elevation models. Flow accumulation is an important input for many such algorithms; here, I parallelize its calculation. The new algorithm works on one or many cores, or multiple machines, and can take advantage of large memories or cope with small ones. Unlike previous parallel algorithms, the new algorithm guarantees a fixed number of memory access and communication events per raster cell. In testing, the new algorithm ran faster and used fewer resources than previous algorithms, exhibiting ∼ 30 % strong and weak scaling efficiencies up to 48 cores and linear scaling across datasets ranging over three orders of magnitude. The largest dataset tested had two trillion ( 2 · 10 12 ) cells. With 48 cores, processing required 24 min wall-time (14.5 compute-hours). 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 on Github. Highlights: I present a parallelized flow accumulation algorithm for large DEMs. The algorithm guarantees fixed numbers of memory and communication events. The algorithm runs in serial on a standard desktop or in parallel on a supercomputer. The algorithm performs tests three orders of magnitude larger than any previous work. Well-commented source code and an automated test suite are available on Github.