Current parallel BFS algorithms are known to have reduced time complexity. However, such cases do not take into account synchronization costs which increase exponentially with the core count. Such synchronization costs stem from communication costs due to data movement between cores, and coherence traffic if using a cache coherent multicore. What is the best parallel BFS algorithm available in this case?
Hi,
This is the most recent article on parallel BFS algorithm : Conference Paper Level-Synchronous BFS Algorithm Implemented in Java Using PCJ Library
Best regards!
In my opinion, the best parallel model that fits well your description and reduces the communication and synchronization costs is the high level parallel model.
in a such model, several instances of the BFS algorithm explore simultaneously several parts of the search tree. Thus, a low synchronization and communication costs since each part can be explored independently from the others.
To reduce the complexity, you can also change the exploration from Breadth-First to Best-First.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms