FastFlow: GPU Acceleration of Flow and Depression Routing for Landscape Simulation

Input : Terrain nodes $\backslash mathcal\{T\}$ with depressions; non-outflow local minima $\backslash mathcal\{L\}$
Output: Updated terrain graph with rerouted depressions

1 for $i\; \backslash leftarrow\; 1$ to $\backslash log\_2(|\backslash mathcal\{L\}|)$ do
2   Construct basins $\backslash mathcal\{D\}$ and annotate the cells (Algorithm 2)
3   Find min edges, saddles and outlets (Algorithm 3)
4   Reroute recipients (Algorithm 4)
5 end

Each iteration, in turn, requires $\backslash log\_2(n)$ sub-iterations, where $n$ is the number of cells, yielding an $\backslash mathcal\{O\}(\backslash log(L)\; \backslash log(n))$ algorithm.

Implementation. As with flow routing, we prevent read-after-write hazards while minimizing the extent of copying. For basin identification, we store the basin-id only for the local minima and not for all cells, and we use the updated recipients at the end of Algorithm 2 as a per-cell pointer to the downstream local minima, which we interrogate to obtain the basin-id. This change relaxes the need for any copy during basin identification, as read-after-write no longer prevents the correct convergence of the algorithm. Furthermore, we observe that this operation is required only for the first iteration. In subsequent iterations, we need only update the pointers to reflect the new connections out of the local minima, yielding an overall complexity of $\backslash mathcal\{O\}(\backslash log(n)\; +\; \backslash log^2(L))$.

Another RAW hazard can occur in the depression carving variant for re-routing flow paths. To prevent this, we use a localized ping-pong strategy (similar to the one presented in Section 4), which is simplified by using the tag variable as a condition for copying.