BIPquick: a tool for enhancing parallelizability of the new SWMM engine

Eddie Tiernan


Central to the objectives of the National Center for Infrastructure Modeling and Management (NCIMM) is producing a SWMM Engine that is more readily able to handle city-scale SWMM models through parallel processing of the system’s hydraulics. Parallelizing a large SWMM network of nodes and links introduces some additional challenges. One such challenge is of intelligent partitioning; that is, how to divide the system into subnetworks to be solved on parallel processors. The constraints of intelligent partitioning are two-fold. The first is finding a set of subnetworks such that the points of connection between subnetworks are minimized, thereby limiting the amount of time spent message passing. Ensuring the work allotted to each processor is balanced constitutes the other constraint. Finding the solution to this two-function optimization problem has garnered significant attention in the field of graph theory, but remains classified as an NP-complete problem.

The BIPquick algorithm, presented here, approximates the optimal partition set for a given SWMM network. Inspired by the flow accumulation calculation commonly used for GIS stream delineation, BIPquick uses cumulative upstream weight as a proxy for computational complexity, thereby eliminating the requirement for an a priori estimate of the system’s hydraulics, solely relying instead on the system’s topology. BIPquick can be shown to reduce the points of partition interconnection compared to FORTRAN CoArray’s default partitioning of the Guadalupe – San Antonio River Basin.

Permanent link: