Reducing the computational cost of an iterative method for sediment yield minimization by afforestation

Afforestation of certain areas of a river catchment can reduce the outflow of sediment from that catchment. We developed algorithms and software, called CAMF, to minimize the sediment outflow, based on a) a model for local sediment production, b) some parameters such as retention capacity and saturation threshold, c) a raster geo-database containing elevation data and land use. The software can also be adapted to model the effect of other actions than afforestation. We implemented both Single Flow Direction (SFD) and Multiple Flow Direction (MFD) methods to simulate flow transport. We analyze the differences between the two approaches. With the use of MFD methods the spatial interaction increases. As a consequence, the flow simulation with CAMF-MFD, executed in each iteration of the minimization procedure, has a substantially higher computational cost. The total execution time of CAMF can be prohibitively expensive for large geo-databases, since in each iteration only the cell(s) with the maximum sediment outflow reduction are selected.

In each iteration of the minimization procedure, a sediment flow simulation is performed for each candidate cell. Since these simulations are independent of each other, we parallelized CAMF for multi-core processors using Open Multi-Processing (OpenMP) directives. Each thread executes the simulations for a subset of the candidate cells. To distribute the simulations over threads, dynamic scheduling is used to handle the imbalance due to the varying execution time of the simulations for each candidate cell. We also adapted the algorithm in two ways to accelerate the execution. First, in each iteration several cells, that produce nearly the same sediment yield reduction at the outlet, are selected. A threshold T determines the number of selected cells. Second, a complete ranking of all cells, with respect to their potential for sediment yield reduction by afforestation, is only computed every K iterations, while in intermediate iterations only N cells are ranked, namely those at the top of the previous complete ranking. The values for T, K and N substantially reduce the computational cost, while the solution quality is typically only slightly lower.

We evaluated the performance of the accelerated variant for minimizing sediment outflow by afforestation using a raster geo-database of the Tabacay catchment (Ecuador), with a cell size of 30m × 30m. From a total of 73 471 non-null cells, 27 246 are candidate cells for afforestation.

A high speedup is obtained for up to 28 cores (≈22), leading to a substantial reduction of the execution time. The accelerated variant produces nearly the same yield reduction at the outlet and selects almost the same cells than the original CAMF-MFD. The difference between the set of cells selected by both algorithms is measured by the relative spatial coincidence RSC. Results show that in all considered cases RSC > 99%.