Direction-Optimized Parallel BFS in PIM
Date:
Poster | Lightning Talk | More Information about CRNCH 2022
Our project is Direction-Optimized Parallel BFS in PIM. Our motivation comes from that when the frontier is large, there exists an opportunity to perform the breadth-first search more efficiently by searching in the reverse direction. Based on this motivation, we implemented the top-down and bottom-up parallel BFS in PIM using the distributed model /and made several optimization of partitioning methods, MPI messages and so on. We evaluated this BFS on social network graphs. The result shows that /both top-down and bottom-up BFS have a high speedup /and the ideal hybrid one’s speedup can be up to 1.5 or even more compared to top-down. But our work is still ongoing. We aim to further optimize this algorithm by avoiding all-to-all communication, and also aim to extend this algorithm to process dynamic graphs.