A Topological Approach to Partitioning Flow Networks for Parallel Simulation

Abstract

System partitioning for effective simulation of civil infrastructure flow networks on parallel processors is a nontrivial problem. Arbitrary partitioning focused only on balancing processor workload can lead to a large interprocessor communication burden that limits parallel speedup. Thus, there is a need for intelligent partitioning algorithms that balance the estimated computational load while minimizing the number of connections between partitions. Graph theory provides widely used partitioning methods, but these are applicable to networks with power-law connectivity and where the computational workload is proportional to the number of system nodes—conditions that do not hold for finite-volume solution of water drainage networks (e.g., river systems, stormwater drainage systems). This paper presents the novel BIPquick algorithm, which is shown to be an effective approach to identifying network partitions with reduced connectivity for systems that are directed acyclic graphs (DAGs) and have a physical limit on the number of connections per network node. Novel developments include (1) a node-cut approach that allows a partitioning workload function to be exactly balanced in systems where the computational work is proportional to the link length between nodes, (2) a finite-pass approach to partitioning that ensures a partitioning solution in a known time, and (3) a new connectivity scaling metric that allows simple evaluation and comparison of different partitioning results. The BIPquick model is tested on a large river network with up to 10,000 partitions.