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

As a reminder, flow routing involves computing the discharge $q\_c$ for a cell $c$ resulting from the accumulation of precipitation $p$ over a stream tree. This tree is implicitly defined by the relationship between a cell $c$ and its downstream recipient $r\_c$. We can also travel upstream by defining a donor of $c$ as a node $d$, such that $r\_d\; =\; c$. We write the set of up to 4 donors of $c$ as $\backslash mathcal\{D\}\_c$. In practice, we store the donors in an $n\; \backslash times\; 4$ matrix, with an accompanying list of the number of donors per cell. This matrix is derived by parsing the cells in parallel. Each cell increases the donor count of its recipient $r$ with atomic operations and adds its position to the donors of $r$.

Water flows downstream from donor cells to recipients, and therefore the flow routing problem consists of accumulating all of the upstream precipitation:

$$q\_c\; =\; p\_c\; +\; \backslash sum\_\{d\; \backslash in\; \backslash mathcal\{D\}(c)\}\; q\_d.\; \backslash quad\; (1)$$

Note that this is a recursive definition so that the discharge at a cell is the sum of the precipitation falling on the cell and the discharge from all donor cells.