Foundations for multi-thread parallel computation in stormwater network models

Multi-threading computers that can simultaneously compute across 10, 20, or even 100 simultaneous processes are readily available to today's engineers and researchers. It seems likely that multi-processor thread counts will continue to increase over the next decade. Unfortunately, common numerical algorithms for network solutions of the open-channel Saint-Venant equations and surcharged-pipe incompressible flow equations have proved difficult to effectively parallelize across a large number of threads. Amdahl's law for existing codes typically limits the speed-up through multi-threading to about 10x or 20x, no matter how many threads are available. As the network solver is typically most time-consuming part of a stormwater model, the present state-of-the-art needs a dramatic change to take advantage of the next generation of computers. To run high-resolution models of large urban areas we need computational schemes that are designed from the ground up for effective slicing-and-dicing into 1000s of thread without being limited by serial computations in the algorithm. We present a new approach that we call a "no-neighbor" method that is designed for effective multi-thread computing. The underlying idea is that the computational stencil for finite-volume cells in a 1D time-marching algorithm must be inherently local, i.e. without multi-cell neighbor stencils, without inversion of a matrix, and without an implicit iterative algorithm. This idea naturally limits us to explicit schemes (e.g. RK4) with small time steps and has consequences for the allowable discretization schemes (e.g. common upwinding cannot be used). We demonstrate that such schemes can be stable for the 1D Saint-Venant equations in subcritical, supercritical, and trans critical flows.