Premium
A distributed approach for calculating inundation height based on Dijkstra's algorithm
Author(s) -
Grady C. J.,
Li Xingong
Publication year - 2018
Publication title -
transactions in gis
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.721
H-Index - 63
eISSN - 1467-9671
pISSN - 1361-1682
DOI - 10.1111/tgis.12453
Subject(s) - dijkstra's algorithm , scalability , computer science , parallel computing , memory footprint , computation , supercomputer , implementation , computational science , multi core processor , algorithm , graph , scaling , path (computing) , shortest path problem , theoretical computer science , mathematics , programming language , operating system , geometry
This research proposed a parallelized approach to scaling up the calculation of inundation height, the minimum sea‐level rise required to inundate a cell on a digital elevation model, which is based on Dijkstra's algorithm for shortest‐path calculations on a graph. Our approach is based on the concepts of spatial decomposition, calculate‐and‐correct, and a master/worker parallelization paradigm. The approach was tested using the U.S. Coastal Relief Model (CRM) dataset from the National Geophysical Data Center on a multicore desktop computer and various supercomputing resources through the U.S. Extreme Science and Engineering Discovery Environment (XSEDE) program. Our parallel implementation not only enables computations that were larger than previously possible, but also significantly outperforms serial implementations with respect to running time and memory footprint as the number of processing cores increases. The efficiency of the scalability seemed to be tied to tile size and flattened out at a certain number of workers.