2016/08/31 by Richard Barnes
Computer Science · Environmental Science · Mathematics · #Algorithm #Artificial intelligence #Code (set theory) #Computer science #Correctness #Digital elevation model #Flood Risk Assessment and Management #Flow (mathematics) #Geology #Geometry #Hydrological Forecasting Using AI #Hydrology and Watershed Management Studies #Mathematics #Parallel computing #Programming language #Ranging #Raster graphics #Remote sensing #Scale (ratio) #Scaling #Set (abstract data type) #Telecommunications #cs.DC #cs.DS
paper · pdf · doi:10.1016/j.envsoft.2017.02.022
published as 2017. Environmental Modelling & Software 92, 202-212 · 23 pages (double-spaced), 4 figures, 2 tables. arXiv admin note: substantial text overlap with arXiv:1606.06204
openalex created_date 2016/09/16 · arxiv created 2017/02/04 · openalex publication_date 2017/04/26 · arxiv updated 2018/01/31 · openalex updated_date 2026/08/06
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*1012) cells. With 48 cores, processing required 24 minutes 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.