No offical talks are held by GPU Computing group in October but we highly recommend this upcoming seminar.
Landscape Evolution Modelling (LEM) is used to predict how landscapes evolve over the millennia due to weathering and erosion. LEM’s normally operate on a regular grid of cells each representing the height of a point within a landscape. The process can be broken up into the following stages applied to each cell: determination of the flow direction of water out of that cell, summation of the volume of water flowing through the cell and computation of the erosion / deposition in the cell. This process is repeated at regular intervals – either an annual time-step (due to computation complexity) or once for each major storm-event – for periods of around one million years.
Within each year/rainstorm there is great potential for speedup when executing on a GPGPU – flow direction for most cells can be performed independently, flow accumulation can easily be performed in parallel. However, due to certain ‘real world’ landscape features this potential can easily be lost. Landscape features such as plateaus – where all cells in a region have the same height – or sinks – (sets of) cells which have no lower neighbour, meaning water cannot escape – prevent optimal speedup being achieved. Likewise, computing the volume of water passing through a cell is inherently sequential – the sum of water through a cell at the end of a river depends on knowing the volume of water passing through all points upstream.
CUDA algorithms have been developed for computing the LEM processes: Flow direction can be computed independently for each cell; A parallel breadth-first algorithm can be used for routing water over a plateau to an outlet cell; A parallel technique for ‘filling’ sinks (making them into lakes) which performs much of its work through parallel pointer jumping is used. Flow accumulation can be performed using a developed ‘correct’ algorithm where each cell which has no incorrect flows entering it can be computed and marked correct. The process of erosion / deposition can then be performed in a similar manner to flow accumulation with the eroded material being passed around.
In this talk we will present parallel techniques for overcoming these problems, demonstrating between two and three orders of magnitude speedup over the best-in- class LEM software for landscapes between 0.1 and 56 million cells – far larger than the traditional 5 thousand cell simulations which have previously been performed. This has led to a need for a re-evaluation of the models used within the LEM community. Errors in LEM simulation results, which have been used over the last 30+ years, have been attributed to the very small simulation sizes. However, with our 46+ million cell simulations – a realistic scale – we are now able to determine that these errors are not due to scale but rather due to the equations themselves.
We will present our approach moving forwards to overcome these limitations and present initial results of this work.