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.
View in Google Scholar
DOI: https://doi.org/10.1007/978-0-387-39934-8_17
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.
View in Google Scholar
DOI: https://doi.org/10.1016/j.jpdc.2005.03.007
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.
View in Google Scholar
DOI: https://doi.org/10.1007/978-3-642-33074-2_23
P. Cholewinski, "Reasoning with Stratified Default Theories", Proc. of Third International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’95), pp. 273-286, 1995.
View in Google Scholar
DOI: https://doi.org/10.1007/3-540-59487-6_20
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.
View in Google Scholar
DOI: https://doi.org/10.1007/s11625-007-0027-8
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.
View in Google Scholar
DOI: https://doi.org/10.1016/0378-8733(90)90011-W
R. Tarjan, "Depth First Search and Linear Graph Algorithms", SIAM Journal on Computing, vol. 1, no. 2, pp. 146-160, 1972.
View in Google Scholar
DOI: https://doi.org/10.1137/0201010
H.N. Gabow, "Path-based Depth First Search Strong and Biconnected Components", Information Processing Letters, vol. 74, no. 3-4, pp. 107-114, 2000.
View in Google Scholar
DOI: https://doi.org/10.1016/S0020-0190(00)00051-X
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.
View in Google Scholar
DOI: https://doi.org/10.1007/978-3-662-46681-0_56
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.
View in Google Scholar
DOI: https://doi.org/10.1016/0020-0190(88)90164-0
R. Cole and U. Vishkin, "Faster Optimal Parallel Prefix Sums and List Ranking", Information and Computation, vol. 81, no. 3, pp. 334-352, 1989.
View in Google Scholar
DOI: https://doi.org/10.1016/0890-5401(89)90036-9
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.
View in Google Scholar
DOI: https://doi.org/10.1016/j.entcs.2008.02.001
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.
View in Google Scholar
DOI: https://doi.org/10.1145/3208040.3208041
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.
View in Google Scholar
DOI: https://doi.org/10.1145/3018743.3018756
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.
View in Google Scholar
DOI: https://doi.org/10.1007/3-540-45591-4_68
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.
View in Google Scholar
DOI: https://doi.org/10.1145/2503210.2503246
J. Barnat and P. Moravec, "Parallel Algorithms for Finding SCCs in Implicitly Given Graphs", in: Formal Methods: Applications and Technology, pp. 316-330, 2007.
View in Google Scholar
DOI: https://doi.org/10.1007/978-3-540-70952-7_22
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.
View in Google Scholar
DOI: https://doi.org/10.1145/3528416.3530247
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.
View in Google Scholar
DOI: https://doi.org/10.1093/logcom/exp003
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
View in Google Scholar
DOI: https://doi.org/10.5486/PMD.1959.6.3-4.12
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.
View in Google Scholar
DOI: https://doi.org/10.1002/jos.116
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.
View in Google Scholar
DOI: https://doi.org/10.1145/278241.278309
P. Winkler, "Random Orders", Order, vol. 1, pp. 317-331, 1985.
View in Google Scholar
DOI: https://doi.org/10.1007/BF00582738
Downloads
Published
Issue
Section
License
Copyright (c) 2024 Dominik Ryżko
This work is licensed under a Creative Commons Attribution 4.0 International License.
