Evaluating Parallel Breadth-First Search Algorithms for Multiprocessor Systems
- Breadth-First Search is a graph traversal technique used in many applications as a building block, e.g., to systematically explore a search space or to determine single source shortest paths in unweighted graphs. For modern multicore processors and as application graphs get larger, well-performing parallel algorithms are favorable. In this paper, we systematically evaluate an important class of parallel algorithms for this problem and discuss programming optimization techniques for their implementation on parallel systems with shared memory. We concentrate our discussion on level-synchronous algorithms for larger multicore and multiprocessor systems. In our results, we show that for small core counts many of these algorithms show rather similar performance behavior. But, for large core counts and large graphs, there are considerable differences in performance and scalability influenced by several factors, including graph topology. This paper gives advice, which algorithm should be used under which circumstances.
Document Type: | Article |
---|---|
Language: | English |
Author: | Matthias Makulla, Rudolf Berrendorf |
Parent Title (English): | Soft (International Journal on Advances in Software) |
Volume: | 7 |
Issue: | 3&4 |
First Page: | 740 |
Last Page: | 751 |
ISSN: | 1942-2628 |
URL: | https://www.thinkmind.org/index.php?view=article&articleid=soft_v7_n34_2014_24 |
Publisher: | ThinkMind |
Date of first publication: | 2014/12/30 |
Keyword: | BFS; NUMA; data locality; memory bandwidth; parallel breadth-first search |
Departments, institutes and facilities: | Fachbereich Informatik |
Dewey Decimal Classification (DDC): | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
Entry in this database: | 2016/04/22 |