• shareshare
  • link
  • cite
  • add
auto_awesome_motion View all 4 versions
Publication . Preprint . Article . Conference object . 2011

Distributed Parallel D8 Up-Slope Area Calculation in Digital Elevation Models

Barnes, Richard; Lehman, Clarence; Mulla, David;
Open Access
This paper presents a parallel algorithm for calculating the eight-directional (D8) up-slope contributing area in digital elevation models (DEMs). In contrast with previous algorithms, which have potentially unbounded inter-node communications, the algorithm presented here realizes strict bounds on the number of inter-node communications. Those bounds in turn allow D8 attributes to be processed for arbitrarily large DEMs on hardware ranging from average desktops to supercomputers. The algorithm can use the OpenMP and MPI parallel computing models, either in combination or separately. It partitions the DEM between slave nodes, calculates an internal up-slope area by replacing information from other slaves with variables representing unknown quantities, passes the results on to a master node which combines all the slaves' data, and passes information back to each slave, which then computes its final result. In this way each slave's DEM partition is treated as a simple unit in the DEM as a whole and only two communications take place per node.
6 pages, 2 figures, 8 algorithms

Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science - Data Structures and Algorithms, D8, upslope area, digital elevation model, DEM, parallel computing, algorithm, flow accumulation, Distributed, Parallel, and Cluster Computing (cs.DC), Data Structures and Algorithms (cs.DS), FOS: Computer and information sciences

[1] Jurgen Garbrecht and Lawrence W Martz. The assignment of drainage direction over flat surfaces in raster digital elevation models. Journal of Hydrology, 193:204-213, June 1997. ISSN 00221694. doi: 10.1016/S0022-1694(96)03138-1. URL http://linkinghub.

[2] D.M. Mark. Modelling in Geomorphological Systems, chapter Network models in geomorphology, pages 73-97. John Wiley & Sons, 1988.

[3] John O'Callaghan and David Mark. The extraction of drainage networks from digital elevation data. Computer Vision, Graphics, and Image Processing, 28(3):323-344, December 1984. ISSN 0734189X. doi: 10.1016/S0734-189X(84)80011-0. URL http://linkinghub.

[4] David G Tarboton. A New Method For Determining Flow Directions And Upslope Areas In Grid Digital Elevation Models. Water Resources Research, 33(2):309-319, 1997.

[5] Chase Wallis, Dan Watson, David Tarboton, and Robert Wallace. Parallel Flow-Direction and Contributing Area Calculation for Hydrology Analysis in Digital Elevation Models. In International Conference on Parallel and Distributed Processing Techniques and Applications, pages 1-5, Las Vegas, Nevada, USA, 2009.

1: procedure FINALISEINTERNALk(S; c) Require: F; D; Q; A 2: if c was not specified then 3: ATOMIC(c front of Q) 4: if c was not set then 5: return 6: end if 7: S AreaD(c) 8: end if 9: 10: 11: 12: 13: