Tuesday , April 20 2021

Accelerating Multiple Flow Accumulation Algorithm Using MPI on a Cluster of Computers

University of Nis, Faculty of Electronic Engineering, Aleksandra Medvedeva 14, 18000 Nis, Serbia
natalija.stojanovic@elfak.ni.ac.rs (*Corresponding author), dragan.stojanovic@elfak.ni.ac.rs

Abstract: The goal of the watershed analysis is to delineate a watershed, the area of land that collects all of the water which falls in it to the common outlet, such as a river or a drainage basin. This analysis is based on data-intensive geospatial operations over large-scale Digital Elevation Model (DEM) raster data, and requires implementation of high-performance parallel methods and technologies. In this paper, the parallelization of the sequential watershed analysis algorithm using MPI (Message Passing Interface) distributed processing library is presented. The MFD-md algorithm has been implemented and evaluated as the modification of the original Multiple Flow Direction (MFD) algorithm. Distributed MPI solutions that implement two different approaches have been developed with the aim of minimizing the cost of MPI process communication by overlapping it with the MPI process execution. These approaches have been evaluated concerning execution time, while varying the size of input DEM data and the number of compute nodes in the cluster. The experimental evaluation shows the improvements in the performance of the parallel MPI watershed analysis solutions related to the sequential solution and promotes proposed MPI solutions for accelerating the flow accumulation step of watershed analysis.

Keywords: Big data processing, Watershed analysis, MPI, High-performance computing.


Natalija STOJANOVIC, Dragan STOJANOVIC, Accelerating Multiple Flow Accumulation Algorithm Using MPI on a Cluster of Computers, Studies in Informatics and Control, ISSN 1220-1766, vol. 29(3), pp. 307-316, 2020.