• search hit 5 of 62
Back to Result List

Level-Synchronous Parallel Breadth-First Search Algorithms For Multicore and Multiprocessor Systems

  • Breadth-First Search (BFS) is a graph traversal technique used in many applications as a building block, e.g.,~to systematically explore a search space. For modern multicore processors and as application graphs get larger, well-performing parallel algorithms are favourable. In this paper, we systematically evaluate an important class of parallel BFS algorithms and discuss programming optimization techniques for their implementation. 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 behaviour. But, for large core counts and large graphs, there are considerable differences in performance and scalability influenced by several factors. This paper gives advice, which algorithm should be used under which circumstances.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Availability
Document Type:Conference Object
Author:Rudolf Berrendorf, Mathias Makulla
Parent Title (English):Nygard, Tamir (Eds.): Future Computing 2014, The Sixth International Conference on Future Computational Technologies and Applications. Venice, Italy, May 25-29, 2014
First Page:26
Last Page:31
Date of first publication:2014/05/25
Award:Best Paper Award
Tag: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:2015/04/02