A Topological Approach to Partitioning Flow Networks for Parallel Simulation
Publication: Journal of Computing in Civil Engineering
Volume 36, Issue 4
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.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
All data, models, or code that support the findings of this study are available from the corresponding author upon reasonable request.
Acknowledgments
This paper was developed under Cooperative Agreement No. 83595001 awarded by the EPA to The University of Texas at Austin. It has not been formally reviewed by the EPA. The views expressed in this document are solely those of the authors and do not necessarily reflect those of the EPA. The EPA does not endorse any products or commercial services mentioned in this publication. Maps throughout this article were created using ArcGIS software by Esri. ArcGIS and ArcMap are the intellectual property of Esri and are used herein under license. Copyright © Esri. All rights reserved. For more information about Esri software, please visit www.esri.com.
References
Ahmed, A., N. Shervashidze, S. Narayanamurthy, V. Josifovski, and A. J. Smola. 2013. “Distributed large-scale natural graph factorization.” In Proc., 22nd Int. Conf. on World Wide Web (WWW’13), 37–48. New York: Association for Computing Machinery Press.
Ariffin, W. N. M., and S. Salleh. 2016. “The partitioning technique of directed cyclic graph for task assignment problem.” AIP Conf. Proc. 1750 (1): 020010. https://doi.org/10.1063/1.4954523.
Aydin, K., M. Bateni, and V. Mirrokni. 2016. “Distributed balanced partitioning via linear embedding.” In Proc., 9th ACM Int. Conf. on Web Search and Data Mining (WSDM ’16), 387–396. New York: ACM Press.
Barabasi, A.-L., and R. Albert. 1999. “Emergence of scaling in random networks.” Science 286 (5439): 509–512. https://doi.org/10.1126/science.286.5439.509.
Bichot, C.-E., and P. Siarry. 2011. Graph partitioning. London: International Society for Technology in Education.
Bourse, F., M. Lelarge, and M. Vojnovic. 2014. “Balanced graph edge partition.” In Proc., 20th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining—KDD ’14, 1456–1465. New York: Association for Computing Machinery Press.
Burger, G., R. Sitzenfrei, M. Kleidorfer, and W. Rauch. 2014. “Parallel flow routing in SWMM 5.” Environ. Modell. Software 53 (Mar): 27–34. https://doi.org/10.1016/j.envsoft.2013.11.002.
David, C. H., D. R. Maidment, G.-Y. Niu, Z.-L. Yang, F. Habets, and V. Eijkhout. 2011. “River network routing on the NHDPlus dataset.” J. Hydrometeorol. 12 (5): 913–934. https://doi.org/10.1175/2011JHM1345.1.
Dean, J., and S. Ghemawat. 2008. “MapReduce: Simplified data processing on large clusters.” Commun. ACM 51 (1): 107. https://doi.org/10.1145/1327452.1327492.
Duan, H.-F., B. Pan, M. Wang, L. Chen, F. Zheng, and Y. Zhang. 2020. “State-of-the-art review on the transient flow modeling and utilization for urban water supply system (UWSS) management.” J. Water Supply Res. Technol. AQUA 69 (8): 858–893. https://doi.org/10.2166/aqua.2020.048.
Ginting, B. M., and R.-P. Mundani. 2019. “Parallel flood simulations for wet–dry problems using dynamic load balancing concept.” J. Comput. Civ. Eng. 33 (3): 04019013. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000823.
Gleich, D. F. 2014. “PageRank beyond the Web.” Preprint, submitted July 18, 2014. https://arxiv.org/abs/1407.5107.
Gonzalez, J. E., Y. Low, H. Gu, D. Bickson, and C. Guestrin. 2012. “PowerGraph: Distributed graph-parallel computation on natural graphs.” In Proc., 10th USENIX Symp. on Operating Systems Design and Implementation (OSDI 12), 17–30. Berkeley, CA: USENIX Association.
Gupta, A. 1997. “Fast and effective algorithms for graph partitioning and sparse-matrix ordering.pdf.” IBM J. Res. Dev. 41 (1–2): 171–183. https://doi.org/10.1147/rd.411.0171.
Heidari, S., Y. Simmhan, R. N. Calheiros, and R. Buyya. 2018. “Scalable graph processing frameworks: A taxonomy and open challenges.” ACM Comput. Surv. 51 (3): 1–53. https://doi.org/10.1145/3199523.
Hendrickson, B., and T. G. Kolda. 2000. “Graph partitioning models for parallel computing.” Parallel Comput. 26 (12): 1519–1534. https://doi.org/10.1016/S0167-8191(00)00048-X.
Hendrickson, B., and R. Leland. 1995. “The Chaco user‘s guide. Version 2.0.” Accessed April 12, 2021. http://www.osti.gov/servlets/purl/10106339-MvWY47/native/.
Hodges, B. R., and F. Liu. 2020. “Timescale interpolation and no-neighbour discretization for a 1D finite-volume Saint-Venant solver.” J. Hydraul. Res. 58 (5): 738–754. https://doi.org/10.1080/00221686.2019.1671510.
Ji, Y., and N. Geroliminis. 2012. “On the spatial partitioning of urban transportation networks.” Transp. Res. Part B Methodol. 46 (10): 1639–1656. https://doi.org/10.1016/j.trb.2012.08.005.
Johnson, P., D. Nguyen, and M. Ng. 2016. “Large-scale network partitioning for decentralized traffic management and other transportation applications.” J. Intell. Transp. Syst. 20 (5): 461–473. https://doi.org/10.1080/15472450.2016.1151792.
Karypis, G. 2013. A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. Minneapolis: Univ. of Minnesota.
Karypis, G., and V. Kumar. 1998. “A fast and high quality multilevel scheme for partitioning irregular graphs.” SIAM J. Sci. Comput. 20 (1): 359–392. https://doi.org/10.1137/S1064827595287997.
Li, L., R. Geda, A. B. Hayes, Y. Chen, P. Chaudhari, E. Z. Zhang, and M. Szegedy. 2017. “A simple yet effective balanced edge partition model for parallel computing.” Proc. ACM Meas. Anal. Comput. Syst. 1 (1): 1–21. https://doi.org/10.1145/3084451.
Li, Y., W. Cai, Y. Li, and X. Du. 2020. “Key node ranking in complex networks: A novel entropy and mutual information-based approach.” Entropy 22 (1): 52. https://doi.org/10.3390/e22010052.
Liu, F., and B. R. Hodges. 2014. “Applying microprocessor analysis methods to river network modelling.” Environ. Modell. Software 52 (Feb): 234–252. https://doi.org/10.1016/j.envsoft.2013.09.013.
Meyerhenke, H., P. Sanders, and C. Schulz. 2014. “Parallel graph partitioning for complex networks.” Preprint, submitted April 18, 2014. https://arxiv.org/abs/1404.4797.
Mokashi, V., and D. B. Kulkarni. 2018. “A review: Scalable parallel graph partitioning for complex networks.” In Proc., 2018 2nd Int. Conf. on Intelligent Computing and Control Systems, 1869–1871. New York: IEEE.
Riaño-Briceño, G. 2020. “Distributed parallel computing for pressurized-flow dynamic simulations.” Accessed February 18, 2021. https://gerardoriano.xyz/scipy2020.html.
Riaño-Briceño, G., L. Sela, and B. R. Hodges. 2022. “Distributed and vectorized method of characteristics for fast transient simulations in water distribution systems.” Comput.-Aided Civ. Infrastruct. Eng. 37 (2): 163–184. https://doi.org/10.1111/mice.12709.
Rossman, L. A. 2000. EPANET 2 users manual, 200. Washington, DC: USEPA.
Sadler, J. M., J. L. Goodall, M. Behl, M. M. Morsy, T. B. Culver, and B. D. Bowes. 2019. “Leveraging open source software and parallel computing for model predictive control of urban drainage systems using EPA-SWMM5.” Environ. Model. Softw. 120: 104484. https://doi.org/10.1016/j.envsoft.2019.07.009.
Sanders, P., and C. Schulz. 2013. “KaHIP v2.1—Karlsruhe high quality partitioning—User guide.” Preprint, submitted November 7, 2013. https://arxiv.org/abs/1311.1714.
Schäuble, H., O. Marinoni, and M. Hinderer. 2008. “A GIS-based method to calculate flow accumulation by considering dams and their specific operation time.” Comput. Geosci. 34 (6): 635–646. https://doi.org/10.1016/j.cageo.2007.05.023.
Schlag, S., C. Schulz, D. Seemaier, and D. Strash. 2018. “Scalable edge partitioning.” Preprint, submitted August 20, 2018. https://arxiv.org/abs/1808.06411.
Schloegel, K., G. Karypis, and V. Kumar. 2000. “Graph partitioning for high performance scientific simulations.” In CRPC parallel computing handbook, 40. New York: Association for Computing Machinery.
Shi, J., and J. Malik. 2000. “Normalized cuts and image segmentation.” IEEE Trans. Pattern Anal. Mach. Intell. 22 (8): 888–905. https://doi.org/10.1109/34.868688.
Simon, H. D., and S.-H. Teng. 1997. “How good is recursive bisection.” SIAM J. Sci. Comput. 18 (5): 1436–1445. https://doi.org/10.1137/S1064827593255135.
Tarboton, D. G. 1997. “A new method for the determination of flow directions and upslope areas in grid digital elevation models.” Water Resour. Res. 33 (2): 309–319. https://doi.org/10.1029/96WR03137.
Tien, I., and A. Der Kiureghian. 2014. “Compression algorithm for Bayesian network modeling of binary systems.” In Safety, reliability, risk and life-cycle performance of structures and infrastructures, edited by G. Deodatis, B. Ellingwood, and D. Frangopol, 3075–3081. Boca Raton, FL: CRC Press.
Tiernan, E. D. 2021. BIPquick code and supporting data. Austin, TX: Univ. of Texas at Austin. https://doi.org/10.18738/T8/LRZBLS.
USGS. 2020. “National hydrography dataset.” Accessed January 20, 2021. https://www.usgs.gov/core-science-systems/ngp/national-hydrography.
Xie, C., W.-J. Li, and Z. Zhang. 2015. “S-PowerGraph: Streaming graph partitioning for natural graphs by vertex-cut.” Preprint, submitted November 9, 2015. https://arxiv.org/abs/1511.02586.
Yahia, C. N., V. Pandey, and S. D. Boyles. 2018. “Network partitioning algorithms for solving the traffic assignment problem using a decomposition approach.” Transp. Res. Rec. 2672 (48): 116–126. https://doi.org/10.1177/0361198118799039.
Yong, J., and Z. Zhigang. 2011. “The project schedule management model based on the program evaluation and review technique and Bayesian networks.” In Proc., 2011 IEEE Int. Conf. on Automation and Logistics, 379–383. New York: IEEE.
Yu, C.-W., F. Liu, and B. R. Hodges. 2017. “Consistent initial conditions for the Saint-Venant equations in river network modeling.” Hydrol. Earth Syst. Sci. 21 (9): 4959–4972. https://doi.org/10.5194/hess-21-4959-2017.
Zhang, L.-M., X.-H. Deng, J.-P. Yu, and X.-S. Wu. 2011. “Degree and connectivity of the Internet’s scale-free topology.” Chin. Phys. B 20 (4): 048902. https://doi.org/10.1088/1674-1056/20/4/048902.
Information & Authors
Information
Published In
Journal of Computing in Civil Engineering
Volume 36 • Issue 4 • July 2022
Copyright
© 2022 American Society of Civil Engineers.
History
Received: Jul 13, 2021
Accepted: Dec 22, 2021
Published online: Mar 29, 2022
Published in print: Jul 1, 2022
Discussion open until: Aug 29, 2022
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.
Cited by
- Gerardo Riaño-Briceño, Ben R. Hodges, Lina Sela, PTSNet: A Parallel Transient Simulator for Water Transport Networks based on vectorization and distributed computing, Environmental Modelling & Software, 10.1016/j.envsoft.2022.105554, 158, (105554), (2022).
- Kezhen Rong, Minglei Fu, Yangyang Huang, Ming Zhang, Lejin Zheng, Jianfeng Zheng, Miklas Scholz, Zaher Mundher Yaseen, Graph attention neural network for water network partitioning, Applied Water Science, 10.1007/s13201-022-01791-4, 13, 1, (2022).