Abstract
Graph abstractions have gained prominence for serving as tools to understand and tackle difficult problems in the fields of Engineering and Technological Sciences. They have been extensively used for applications involving large-scale networks. One of the well-known algorithms for graph traversal is Breadth-First Search algorithm. This paper employs a Parallel Breadth-First search to obtain an optimized solution quicker using a multi-set data structure called ‘BAG’ instead of a FIFO queue. This paper tries to optimize graph traversal on multi-core systems using Cilk++ by an implementation of a Parallelized Breadth-First Search Algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Graph 500 Committee, Graph 500 Benchmark Suite, http://www.graph500.org/. Retrieved 22 Nov 2014
E.T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms (MIT Press Inc, Cambridge, 1990)
C. Leiserson, T. Schardl, A work-efficient parallel breadth-first search algorithm (or how to cope with the non-determinism of reducers), in Proceedings of the 22nd Annual Symposium on Parallelism in Algorithms and Architectures (SPAA’10), 2010, pp. 301–314
S. Pai, M.A. Hassaan, K. Pingali, An operational performance model of breadth-first search, in Proceedings of the 1st International Workshop on Architecture for Graph Processing, Vancouver, CA, June 2017 (AGP’17)
R. Berrendorf, M. Makulla, Level synchronous parallel breadth-first search algorithm for multicore and multiprocessor systems, in Proceedings of Sixth International Conference on Future Computing Technologies and Applications (Future computing 2014), 2014, pp. 26–31
D.A. Bader, K. Madduri, Designing multithreaded algorithms for breadth-first search and st-connectivity on the Cray MTA-2, in Proceedings of 35th International Conference on Parallel Processing (ICPP 2006), 2006, pp. 523–530
Y. Yasui, K. Fujusawa, K. Goto, NUMA-optimized parallel breadth-first search on multicore single-node system, in Proceedings of IEEE International Conference on Big Data, 2013, pp. 394–402
R.E. Korf, P. Schultze, Large-scale parallel breadth-first search, in AAAI, 2005, pp. 1380–1385
Supertech Research Group, MIT/LCS. Cilk 5.4.6 Reference Manual, (1998). http://supertech.csail.mit.edu/cilk/
J. Shun, G.E. Blelloch, Ligra: a lightweight graph processing framework for shared memory, in Proceedings of Principles and Practices of Parallel Processing. IEEE, 2013, pp. 135–146
S. Hong, T. Oguntebi, K. Olukotun, Efficient parallel graph exploration on multi-core CPU and GPU, in Proceeding of the 2011 IEEE International Conference on Parallel Architectures and Compilation Techniques (PACT, 2011), pp. 78–88
J.J. Tithi, Avoiding locks instructions in shared-memory parallel BFS using optimistic parallelization, in 2013, IEEE, International Symposium on Parallel and Distributed Processing Workshops and Phd Forum (2013)
Intel® Cilk™ Plus Language Extension Specification—CilkPlus, https://www.cilkplus.org/sites/default/files/open_specifications/Intel_Cilk_plus_lang_spec_1.2.htm
D.A. Bader, K. Madduri, SNAP, small-world network analysis and partitioning: an open-source parallel graph framework for the exploration of large-scale networks, in 22nd IEEE International Symposium on Parallel and Distributed Processing, 2008, pp. 1–12
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Eedi, H., Rasheed, M.A. (2019). Implementation of Multithreaded BFS Using Bag Data Structure. In: Wang, J., Reddy, G., Prasad, V., Reddy, V. (eds) Soft Computing and Signal Processing . Advances in Intelligent Systems and Computing, vol 900. Springer, Singapore. https://doi.org/10.1007/978-981-13-3600-3_37
Download citation
DOI: https://doi.org/10.1007/978-981-13-3600-3_37
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-13-3599-0
Online ISBN: 978-981-13-3600-3
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)