A parallel Breadth-First Search using shared memory level-synchronization

Research Article
Open access

A parallel Breadth-First Search using shared memory level-synchronization

Kaiwen Zheng 1*
  • 1 University of Toronto    
  • *corresponding author helloworld.zheng@mail.utoronto.ca
Published on 7 February 2024 | https://doi.org/10.54254/2755-2721/36/20230442
ACE Vol.36
ISSN (Print): 2755-273X
ISSN (Online): 2755-2721
ISBN (Print): 978-1-83558-297-8
ISBN (Online): 978-1-83558-298-5

Abstract

Breadth-first search (BFS) stands as a cornerstone in graph exploration techniques, enabling systematic traversal of a provided graph. As the digital era continues to burgeon, there has been a marked upswing in the need to process vast graph-based data sets. To harness the power of such data effectively, it becomes imperative to use computational tools efficiently. Parallelizing BFS emerges as a pivotal strategy in this regard, leveraging the expansive capabilities of multiprocessor systems to maximize efficiency. This manuscript introduces a level-synchronous parallel BFS that is predicated on the shared-memory model. Recognizing the potential pitfalls of such an approach, especially regarding overhead induced by implicit barriers and critical sections, meticulous optimization techniques are infused into the model. These strategies are not mere afterthoughts; they are woven into the fabric of the design, ensuring smooth operations even when scaled. To validate the efficacy of this model, a rigorous assessment is carried out using the Graph500 benchmark. This offers insights into the performance scale of the parallel BFS algorithm, especially focusing on its speedup in relation to the number of operational threads. Concluding this exploration, the paper delineates prospective avenues for refining and further enhancing the proposed parallel implementation, aiming for even greater efficiencies in future endeavors.

Keywords:

Breadth-first search (BFS) stands as a cornerstone in graph exploration techniques, enabling systematic traversal of a provided graph. As the digital era continues to burgeon, there has been a marked upswing in the need to process vast graph-based data sets. To harness the power of such data effectively, it becomes imperative to use computational tools efficiently. Parallelizing BFS emerges as a pivotal strategy in this regard, leveraging the expansive capabilities of multiprocessor systems to maximize efficiency. This manuscript introduces a level-synchronous parallel BFS that is predicated on the shared-memory model. Recognizing the potential pitfalls of such an approach, especially regarding overhead induced by implicit barriers and critical sections, meticulous optimization techniques are infused into the model. These strategies are not mere afterthoughts; they are woven into the fabric of the design, ensuring smooth operations even when scaled. To validate the efficacy of this model, a rigorous assessment is carried out using the Graph500 benchmark. This offers insights into the performance scale of the parallel BFS algorithm, especially focusing on its speedup in relation to the number of operational threads. Concluding this exploration, the paper delineates prospective avenues for refining and further enhancing the proposed parallel implementation, aiming for even greater efficiencies in future endeavors.

Zheng,K. (2024). A parallel Breadth-First Search using shared memory level-synchronization. Applied and Computational Engineering,36,180-184.
Export citation

References

[1]. Harel R, Mosseri I, Levin H, et al. Source-to-source parallelization compilers for scientific shared-memory multi-core and accelerated multiprocessing: analysis, pitfalls, enhancement and potential[J]. International Journal of Parallel Programming, 2020, 48: 1-31.

[2]. Kadosh T, Schneider N, Hasabnis N, et al. Advising OpenMP Parallelization via a Graph-Based Approach with Transformers[J]. arXiv preprint arXiv:2305.11999, 2023.

[3]. Perciano T, Heinemann C, Camp D, et al. Shared-memory parallel probabilistic graphical modeling optimization: Comparison of threads, openmp, and data-parallel primitives[C]//High Performance Computing: 35th International Conference, ISC High Performance 2020, Frankfurt/Main, Germany, June 22–25, 2020, Proceedings 35. Springer International Publishing, 2020: 127-145.

[4]. Harel R, Pinter Y, Oren G. Learning to parallelize in a shared-memory environment with transformers[C]//Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming. 2023: 450-452.

[5]. Kadosh T, Hasabnis N, Mattson T, et al. Quantifying OpenMP: Statistical Insights into Usage and Adoption[J]. arXiv preprint arXiv:2308.08002, 2023.

[6]. Cho H. Memory-efficient flow accumulation using a look-around approach and its OpenMP parallelization[J]. Environmental Modelling & Software, 2023, 167: 105771.

[7]. Datta D, Gordon M S. A massively parallel implementation of the CCSD (T) method using the resolution-of-the-identity approximation and a hybrid distributed/shared memory parallelization model[J]. Journal of Chemical Theory and Computation, 2021, 17(8): 4799-4822.

[8]. Harel R, Pinter Y, Oren G. POSTER: Learning to Parallelize in a Shared-Memory Environment with Transformers[J]. 2023.

[9]. Velarde A. Parallelization of Array Method with Hybrid Programming: OpenMP and MPI[J]. Applied Sciences, 2022, 12(15): 7706.

[10]. Gambhir G, Mandal J K. Shared memory implementation and scalability analysis of recursive positional substitution based on prime-non prime encryption technique[C]//Computational Intelligence, Communications, and Business Analytics: Second International Conference, CICBA 2018, Kalyani, India, July 27–28, 2018, Revised Selected Papers, Part II 2. Springer Singapore, 2019: 441-449.

Cite this article

Zheng,K. (2024). A parallel Breadth-First Search using shared memory level-synchronization. Applied and Computational Engineering,36,180-184.

Data availability

The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.

Disclaimer/Publisher's Note

The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

About volume

Volume title: Proceedings of the 2023 International Conference on Machine Learning and Automation

ISBN：978-1-83558-297-8(Print) / 978-1-83558-298-5(Online)
Editor：Mustafa İSTANBULLU
Conference website: https://2023.confmla.org/
Conference date: 18 October 2023
Series: Applied and Computational Engineering
Volume number: Vol.36
ISSN：2755-2721(Print) / 2755-273X(Online)

© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license. Authors who publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See Open access policy for details).

References

[1]. Harel R, Mosseri I, Levin H, et al. Source-to-source parallelization compilers for scientific shared-memory multi-core and accelerated multiprocessing: analysis, pitfalls, enhancement and potential[J]. International Journal of Parallel Programming, 2020, 48: 1-31.

[2]. Kadosh T, Schneider N, Hasabnis N, et al. Advising OpenMP Parallelization via a Graph-Based Approach with Transformers[J]. arXiv preprint arXiv:2305.11999, 2023.

[3]. Perciano T, Heinemann C, Camp D, et al. Shared-memory parallel probabilistic graphical modeling optimization: Comparison of threads, openmp, and data-parallel primitives[C]//High Performance Computing: 35th International Conference, ISC High Performance 2020, Frankfurt/Main, Germany, June 22–25, 2020, Proceedings 35. Springer International Publishing, 2020: 127-145.

[4]. Harel R, Pinter Y, Oren G. Learning to parallelize in a shared-memory environment with transformers[C]//Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming. 2023: 450-452.

[5]. Kadosh T, Hasabnis N, Mattson T, et al. Quantifying OpenMP: Statistical Insights into Usage and Adoption[J]. arXiv preprint arXiv:2308.08002, 2023.

[6]. Cho H. Memory-efficient flow accumulation using a look-around approach and its OpenMP parallelization[J]. Environmental Modelling & Software, 2023, 167: 105771.

[7]. Datta D, Gordon M S. A massively parallel implementation of the CCSD (T) method using the resolution-of-the-identity approximation and a hybrid distributed/shared memory parallelization model[J]. Journal of Chemical Theory and Computation, 2021, 17(8): 4799-4822.

[8]. Harel R, Pinter Y, Oren G. POSTER: Learning to Parallelize in a Shared-Memory Environment with Transformers[J]. 2023.

[9]. Velarde A. Parallelization of Array Method with Hybrid Programming: OpenMP and MPI[J]. Applied Sciences, 2022, 12(15): 7706.

[10]. Gambhir G, Mandal J K. Shared memory implementation and scalability analysis of recursive positional substitution based on prime-non prime encryption technique[C]//Computational Intelligence, Communications, and Business Analytics: Second International Conference, CICBA 2018, Kalyani, India, July 27–28, 2018, Revised Selected Papers, Part II 2. Springer Singapore, 2019: 441-449.

For authors
Guide for authors Policies for authors Aims and scope Subscription Open access policy
For editors
Policies for editors Editorial board
For reviewers
Policies for reviewers Privacy policy

Cookies are used by this site.
Copyright © 2024 EWA Publishing, its licensors, and contributors. All rights reserved, including text and data mining, AI training, and similar technologies.