A scalable high-performance topographic flow direction algorithm for hydrological information analysis

Kornelijus Survila, Ahmet Artu Yildirim, Ting Li, Yan Y. Liu, David G. Tarboton, Shaowen Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Hydrological information analyses based on Digital Eleva-tion Models (DEM) provide hydrological properties derived from high-resolution topographic data represented as an el-evation grid. Flow direction is one of the most computa-tionally intensive functions in the current implementation of TauDEM, a broadly used high-performance hydrological analysis software in hydrology community. Hydrologic flow direction defines a flow field on the DEM that directs flow from each grid cell to one or more of its neighbors. This is a local computation for the majority of grid cells, but becomes a global calculation for the geomorphologically motivated procedure in TauDEM to route flow across flat regions. As the resolution of DEM becomes higher, the computational bottleneck of this function hinders the use of these DEM data in large-scale studies. This paper presents an efficient parallel flow direction algorithm that identifies spatial fea-tures (e.g., flats) and reduces the number of sequential and parallel iterations needed to compute their geomorphologi-cally motivated flow direction. Numerical experiments show that our algorithm outperformed the existing parallel D8 algorithm in TauDEM by two orders of magnitude. The new parallel algorithm exhibited desirable scalability on Stam-pede and ROGER supercomputers.

Original languageEnglish (US)
Title of host publicationProceedings of XSEDE 2016
Subtitle of host publicationDiversity, Big Data, and Science at Scale
PublisherAssociation for Computing Machinery
ISBN (Electronic)9781450347556
DOIs
StatePublished - Jul 17 2016
EventConference on Diversity, Big Data, and Science at Scale, XSEDE 2016 - Miami, United States
Duration: Jul 17 2016Jul 21 2016

Publication series

NameACM International Conference Proceeding Series
Volume17-21-July-2016

Other

OtherConference on Diversity, Big Data, and Science at Scale, XSEDE 2016
CountryUnited States
CityMiami
Period7/17/167/21/16

Fingerprint

Information analysis
Parallel algorithms
Parallel flow
Supercomputers
Hydrology
Scalability
Flow fields
Experiments

Keywords

  • D8 flow algorithm
  • High-performance computing
  • Parallel flow direction assignment
  • Tau-DEM

ASJC Scopus subject areas

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

Cite this

Survila, K., Yildirim, A. A., Li, T., Liu, Y. Y., Tarboton, D. G., & Wang, S. (2016). A scalable high-performance topographic flow direction algorithm for hydrological information analysis. In Proceedings of XSEDE 2016: Diversity, Big Data, and Science at Scale [a11] (ACM International Conference Proceeding Series; Vol. 17-21-July-2016). Association for Computing Machinery. https://doi.org/10.1145/2949550.2949571

A scalable high-performance topographic flow direction algorithm for hydrological information analysis. / Survila, Kornelijus; Yildirim, Ahmet Artu; Li, Ting; Liu, Yan Y.; Tarboton, David G.; Wang, Shaowen.

Proceedings of XSEDE 2016: Diversity, Big Data, and Science at Scale. Association for Computing Machinery, 2016. a11 (ACM International Conference Proceeding Series; Vol. 17-21-July-2016).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Survila, K, Yildirim, AA, Li, T, Liu, YY, Tarboton, DG & Wang, S 2016, A scalable high-performance topographic flow direction algorithm for hydrological information analysis. in Proceedings of XSEDE 2016: Diversity, Big Data, and Science at Scale., a11, ACM International Conference Proceeding Series, vol. 17-21-July-2016, Association for Computing Machinery, Conference on Diversity, Big Data, and Science at Scale, XSEDE 2016, Miami, United States, 7/17/16. https://doi.org/10.1145/2949550.2949571
Survila K, Yildirim AA, Li T, Liu YY, Tarboton DG, Wang S. A scalable high-performance topographic flow direction algorithm for hydrological information analysis. In Proceedings of XSEDE 2016: Diversity, Big Data, and Science at Scale. Association for Computing Machinery. 2016. a11. (ACM International Conference Proceeding Series). https://doi.org/10.1145/2949550.2949571
Survila, Kornelijus ; Yildirim, Ahmet Artu ; Li, Ting ; Liu, Yan Y. ; Tarboton, David G. ; Wang, Shaowen. / A scalable high-performance topographic flow direction algorithm for hydrological information analysis. Proceedings of XSEDE 2016: Diversity, Big Data, and Science at Scale. Association for Computing Machinery, 2016. (ACM International Conference Proceeding Series).
@inproceedings{cf4471235759440faf0502427f2de02c,
title = "A scalable high-performance topographic flow direction algorithm for hydrological information analysis",
abstract = "Hydrological information analyses based on Digital Eleva-tion Models (DEM) provide hydrological properties derived from high-resolution topographic data represented as an el-evation grid. Flow direction is one of the most computa-tionally intensive functions in the current implementation of TauDEM, a broadly used high-performance hydrological analysis software in hydrology community. Hydrologic flow direction defines a flow field on the DEM that directs flow from each grid cell to one or more of its neighbors. This is a local computation for the majority of grid cells, but becomes a global calculation for the geomorphologically motivated procedure in TauDEM to route flow across flat regions. As the resolution of DEM becomes higher, the computational bottleneck of this function hinders the use of these DEM data in large-scale studies. This paper presents an efficient parallel flow direction algorithm that identifies spatial fea-tures (e.g., flats) and reduces the number of sequential and parallel iterations needed to compute their geomorphologi-cally motivated flow direction. Numerical experiments show that our algorithm outperformed the existing parallel D8 algorithm in TauDEM by two orders of magnitude. The new parallel algorithm exhibited desirable scalability on Stam-pede and ROGER supercomputers.",
keywords = "D8 flow algorithm, High-performance computing, Parallel flow direction assignment, Tau-DEM",
author = "Kornelijus Survila and Yildirim, {Ahmet Artu} and Ting Li and Liu, {Yan Y.} and Tarboton, {David G.} and Shaowen Wang",
year = "2016",
month = "7",
day = "17",
doi = "10.1145/2949550.2949571",
language = "English (US)",
series = "ACM International Conference Proceeding Series",
publisher = "Association for Computing Machinery",
booktitle = "Proceedings of XSEDE 2016",

}

TY - GEN

T1 - A scalable high-performance topographic flow direction algorithm for hydrological information analysis

AU - Survila, Kornelijus

AU - Yildirim, Ahmet Artu

AU - Li, Ting

AU - Liu, Yan Y.

AU - Tarboton, David G.

AU - Wang, Shaowen

PY - 2016/7/17

Y1 - 2016/7/17

N2 - Hydrological information analyses based on Digital Eleva-tion Models (DEM) provide hydrological properties derived from high-resolution topographic data represented as an el-evation grid. Flow direction is one of the most computa-tionally intensive functions in the current implementation of TauDEM, a broadly used high-performance hydrological analysis software in hydrology community. Hydrologic flow direction defines a flow field on the DEM that directs flow from each grid cell to one or more of its neighbors. This is a local computation for the majority of grid cells, but becomes a global calculation for the geomorphologically motivated procedure in TauDEM to route flow across flat regions. As the resolution of DEM becomes higher, the computational bottleneck of this function hinders the use of these DEM data in large-scale studies. This paper presents an efficient parallel flow direction algorithm that identifies spatial fea-tures (e.g., flats) and reduces the number of sequential and parallel iterations needed to compute their geomorphologi-cally motivated flow direction. Numerical experiments show that our algorithm outperformed the existing parallel D8 algorithm in TauDEM by two orders of magnitude. The new parallel algorithm exhibited desirable scalability on Stam-pede and ROGER supercomputers.

AB - Hydrological information analyses based on Digital Eleva-tion Models (DEM) provide hydrological properties derived from high-resolution topographic data represented as an el-evation grid. Flow direction is one of the most computa-tionally intensive functions in the current implementation of TauDEM, a broadly used high-performance hydrological analysis software in hydrology community. Hydrologic flow direction defines a flow field on the DEM that directs flow from each grid cell to one or more of its neighbors. This is a local computation for the majority of grid cells, but becomes a global calculation for the geomorphologically motivated procedure in TauDEM to route flow across flat regions. As the resolution of DEM becomes higher, the computational bottleneck of this function hinders the use of these DEM data in large-scale studies. This paper presents an efficient parallel flow direction algorithm that identifies spatial fea-tures (e.g., flats) and reduces the number of sequential and parallel iterations needed to compute their geomorphologi-cally motivated flow direction. Numerical experiments show that our algorithm outperformed the existing parallel D8 algorithm in TauDEM by two orders of magnitude. The new parallel algorithm exhibited desirable scalability on Stam-pede and ROGER supercomputers.

KW - D8 flow algorithm

KW - High-performance computing

KW - Parallel flow direction assignment

KW - Tau-DEM

UR - http://www.scopus.com/inward/record.url?scp=84989208926&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84989208926&partnerID=8YFLogxK

U2 - 10.1145/2949550.2949571

DO - 10.1145/2949550.2949571

M3 - Conference contribution

AN - SCOPUS:84989208926

T3 - ACM International Conference Proceeding Series

BT - Proceedings of XSEDE 2016

PB - Association for Computing Machinery

ER -