Increasing Parallelism in Forward-backward Distributed Algorithm for Finding Strongly Connected Components of Directed Graphs
DOI:
https://doi.org/10.26636/jtit.2024.3.1693Keywords:
distributed computation, graph algorithms, strongly connected componentsAbstract
The paper proposes a modification of the existing distributed forward-backward algorithm for finding strongly connected components in directed graphs. The modification aims at improving the parallelism of the algorithm by increasing the branching factor while dividing the workload. Instead of randomly picking the pivot vertex, a heuristic technique is used which allows more sub-tasks to be generated, on average, for the subsequent step of the algorithm. The work describes suitable algorithm modifications and presents empirical results, proving suitability of the approach in question.
Downloads
References
B. Sandeep and A. Ferreira, "Complexity of Connected Components in Evolving Graphs and the Computation of Multicast Trees in Dynamic Networks", Second International Conference, ADHOC-NOW2003, Montreal, Canada, 2003.
View in Google Scholar
S. Raghavan, "Twinless Strongly Connected Components", in: Perspectives in Operations Research, pp. 285-304, 2006. DOI: https://doi.org/10.1007/978-0-387-39934-8_17
View in Google Scholar
W. McLendon III, B. Hendrickson, S.J. Plimpton, and L. Rauchwerger, "Finding Strongly Connected Components in Distributed Graphs", Journal of Parallel and Distributed Computing, vol. 65, no. 8, pp. 901-910, 2005. DOI: https://doi.org/10.1016/j.jpdc.2005.03.007
View in Google Scholar
H. Garavel, R. Mateescu, and I.M. Smarandache, "Parallel State Space Construction for Model-checking", Proc. of the 8th International SPIN Workshop on Model Checking of Software (SPIN’01), vol. 2057, pp. 200-216, 2001.
View in Google Scholar
D. Ryzko, "Reasoning in Multi-agent Systems with Random Knowledge Distribution", in: Advances in Databases and Information Systems, pp. 310-317, 2012. DOI: https://doi.org/10.1007/978-3-642-33074-2_23
View in Google Scholar
P. Cholewinski, "Reasoning with Stratified Default Theories", Proc. of Third International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’95), pp. 273-286, 1995. DOI: https://doi.org/10.1007/3-540-59487-6_20
View in Google Scholar
V. Batagelj, "Efficient Algorithms for Citation Network Analysis", ArXiv, 2003.
View in Google Scholar
Y. Kajikawa et al., "Creating an Academic Landscape of Sustainability Science: An Analysis of the Citation Network", Sustainability Science, vol. 2, pp. 221-231, 2007. DOI: https://doi.org/10.1007/s11625-007-0027-8
View in Google Scholar
H. Yang et al., "Strongly Connected Components Based Efficient PPR Algorithms", Jisuanji Xuebao/Chinese Journal of Computers, vol. 40, pp. 584-600, 2017.
View in Google Scholar
N.P. Hummon and P. Doreian, "Computational Methods for Social Network Analysis", Social Networks, vol. 12, no. 4, pp. 273-288, 1990. DOI: https://doi.org/10.1016/0378-8733(90)90011-W
View in Google Scholar
R. Tarjan, "Depth First Search and Linear Graph Algorithms", SIAM Journal on Computing, vol. 1, no. 2, pp. 146-160, 1972. DOI: https://doi.org/10.1137/0201010
View in Google Scholar
H.N. Gabow, "Path-based Depth First Search Strong and Biconnected Components", Information Processing Letters, vol. 74, no. 3-4, pp. 107-114, 2000. DOI: https://doi.org/10.1016/S0020-0190(00)00051-X
View in Google Scholar
E. Renault, A. Duret-Lutz, F. Kordon, and D. Poitrenaud, "Parallel Explicit Model Checking for Generalized Buchi Automata", in: Tools and Algorithms for the Construction and Analysis of Systems, pp. 613-627, 2015. DOI: https://doi.org/10.1007/978-3-662-46681-0_56
View in Google Scholar
H. Gazit and G.L. Miller, "An Improved Parallel Algorithm that Computes the BFS Numbering of a Directed Graph", Information Processing Letters, vol. 28, no. 2, pp. 61-65, 1988. DOI: https://doi.org/10.1016/0020-0190(88)90164-0
View in Google Scholar
R. Cole and U. Vishkin, "Faster Optimal Parallel Prefix Sums and List Ranking", Information and Computation, vol. 81, no. 3, pp. 334-352, 1989. DOI: https://doi.org/10.1016/0890-5401(89)90036-9
View in Google Scholar
J. Barnat, J. Chaloupka, and J. van de Pol, "Improved Distributed Algorithms for SCC Decomposition", Electronic Notes in Theoretical Computer Science, vol. 198, no. 1, pp. 63-77, 2008. DOI: https://doi.org/10.1016/j.entcs.2008.02.001
View in Google Scholar
W. Schudy, "Randomized Algorithms for Graph Problems", 2007.
View in Google Scholar
W. Schudy, "Finding Strongly Connected Components in Parallel Using O(log2n) Reachability Queries", Proceedings of the Twentieth Annual Symposium on Parallelism in Algorithms and Architectures, pp. 146-151, 2008.
View in Google Scholar
J. Jaiganesh and M. Burtscher, "A High-performance Connected Components Implementation for GPUs", Proceedings of the 27th International Symposium on High-Performance Parallel and Distributed Computing, pp. 92-104, 2018. DOI: https://doi.org/10.1145/3208040.3208041
View in Google Scholar
T. Ben-Nun, M. Sutton, S. Pai, and K. Pingali, "Groute: An Asynchronous Multi-GPU Programming Model for Irregular Computations", Proceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 235-248, 2017. DOI: https://doi.org/10.1145/3018743.3018756
View in Google Scholar
L. Fleischer, B. Hendrickson, and A. Pinar, "On Identifying Strongly Connected Components in Parallel", Proceedings of Parallel and Distributed Processing Symposium, pp. 505-511, 2000. DOI: https://doi.org/10.1007/3-540-45591-4_68
View in Google Scholar
S. Hong, N.C. Rodia, and K. Olukotun, "On Fast Parallel Detection of Strongly Connected Components (SCC) in Small-world Graphs", Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, 2013. DOI: https://doi.org/10.1145/2503210.2503246
View in Google Scholar
J. Barnat and P. Moravec, "Parallel Algorithms for Finding SCCs in Implicitly Given Graphs", in: Formal Methods: Applications and Technology, pp. 316-330, 2007. DOI: https://doi.org/10.1007/978-3-540-70952-7_22
View in Google Scholar
Y. Ji, H. Liu, and H.H. Huang, "iSpan: Parallel Identification of Strongly Connected Components with Spanning Trees", SC18: International Conference for High Performance Computing, Networking, Storage and Analysis, Dallas, USA, 2022.
View in Google Scholar
D. Niewenhuis and A.L. Varbanescu, "Efficient Trimming for Strongly Connected Components Calculation", Proceedings of the 19th ACM International Conference on Computing Frontiers, pp. 131-140, 2022. DOI: https://doi.org/10.1145/3528416.3530247
View in Google Scholar
J. Barnat, J. Chaloupka, and J. van de Pol, "Distributed Algorithms for SCC Decomposition", Journal of Logic and Computation, vol. 21, no. 1, pp. 23-44, 2011. DOI: https://doi.org/10.1093/logcom/exp003
View in Google Scholar
S. Orzan, "On Distributed Verification and Verified Distribution", Ph.D. thesis, Free University of Amsterdam, 2004 (https://research.vu.nl/en/publications/on-distributed-verification-and-verified-distribution).
View in Google Scholar
P. Erdos and A. Renyi, "On Random Graphs I", Publicationes Mathematicae Debrecen, vol. 6, pp. 290-297, 1959 DOI: https://doi.org/10.5486/PMD.1959.6.3-4.12
View in Google Scholar
T. Tobita and H. Kasahara, "A Standard Task Graph Set for Fair Evaluation of Multiprocessor Scheduling Algorithms", Journal of Scheduling, vol. 5, no. 5, pp. 379-394, 2002. DOI: https://doi.org/10.1002/jos.116
View in Google Scholar
R.P. Dick, D.L. Rhodes, and W. Wolf, "TGFF: Task Graphs for Free", Proceedings of the 6th International Workshop on Hardware/Software Codesign, pp. 97-101, 1998. DOI: https://doi.org/10.1145/278241.278309
View in Google Scholar
P. Winkler, "Random Orders", Order, vol. 1, pp. 317-331, 1985. DOI: https://doi.org/10.1007/BF00582738
View in Google Scholar
Downloads
Published
Issue
Section
License
Copyright (c) 2024 Dominik Ryżko
This work is licensed under a Creative Commons Attribution 4.0 International License.
