More Web Proxy on the site http://driver.im/

Article

A Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L

Authors:

Keith Henderson,

William McLendon,

Bruce Hendrickson,

Umit CatalyurekAuthors Info & Claims

SC '05: Proceedings of the 2005 ACM/IEEE conference on Supercomputing

Page 25

https://doi.org/10.1109/SC.2005.4

Published: 12 November 2005 Publication History

Abstract

Many emerging large-scale data science applications require searching large graphs distributed across multiple memories and processors. This paper presents a distributed breadth- first search (BFS) scheme that scales for random graphs with up to three billion vertices and 30 billion edges. Scalability was tested on IBM BlueGene/L with 32,768 nodes at the Lawrence Livermore National Laboratory. Scalability was obtained through a series of optimizations, in particular, those that ensure scalable use of memory. We use 2D (edge) partitioning of the graph instead of conventional 1D (vertex) partitioning to reduce communication overhead. For Poisson random graphs, we show that the expected size of the messages is scalable for both 2D and 1D partitionings. Finally, we have developed efficient collective communication functions for the 3D torus architecture of BlueGene/L that also take advantage of the structure in the problem. The performance and characteristics of the algorithm are measured and reported.

References

[1]

{1} Blue Gene/L. http://cmg-rr.llnl.gov/asci/platforms/bluegenel.

[2]

{2} B. Bollobás. The diameter of random graphs. Trans. American Mathematical Society, 267: 41- 52, 1981.

[3]

{3} U. V. Çatalyürek and C. Aykanat. A hypergraph-partitioning approach for coarse-grain decomposition. In ACM/IEEE SC2001, Denver, CO, November 2001.

Digital Library

[4]

{4} M. Chein and M.-L. Mugnier. Conceptual graphs: Fundamental notions. Revue d'intelligence artificielle, 6(4): 365-406, 1992.

[5]

{5} A. Clauset, M. E. J. Newman, and C. Moore. Finding community structure in very large networks. Phys. Rev. E, 70(6): 066111, Dec. 2004.

[6]

{6} A. Crauser, K. Mehlhorn, U. Meyer, and P. Sanders. A parallelization of Dijkstra's shortest path algorithm. Lecture Notes in Computer Science, 1450: 722-731, 1998.

Digital Library

[7]

{7} J. Duch and A. Arenas. Community detection in complex networks using extremal optimization. arXiv.cond-mat/0501368, Jan. 2005.

[8]

{8} C. Faloutsos, K. McCurley, and A. Tomkins. Fast discovery of connection subgraphs. In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 118-127, Seattle, WA, USA, 2004. ACM Press.

Digital Library

[9]

{9} G. Fox, M. Johnson, S. Otto, J. Salmon, and D. Walker. Solving Problems on Concurrent Processors. Prentice-Hall, Inc., 1988.

Digital Library

[10]

{10} A. Y. Grama and V. Kumar. A survey of parallel search algorithms for discrete optimization problems, 1993.

[11]

{11} Y. Han, V. Y. Pan, and J. H. Reif. Efficient parallel algorithms for computing all pair shortest paths in directed graphs. In ACM Symposium on Parallel Algorithms and Architectures, pages 353-362, 1992.

Digital Library

[12]

{12} B. Hendrickson, R. Leland, and S. Plimpton. An efficient parallel algorithm for partitioning irregular graphs. Int. Journal of High Speed Computing, 7(1): 73-88, 1995.

[13]

{13} P. N. Klein and S. Subramanian. A randomized parallel algorithm for single-source shortest paths. J. Algorithms, 25(2): 205-220, 1997.

Digital Library

[14]

{14} R. Levinson. Towards domain-independent machine intelligence. In G. Mineau, B. Moulin, and J. Sowa, editors, Proc. 1st Int. Conf. on Conceptual Structures, volume 699, pages 254-273, Quebec City, Canada, 1993. Springer-Verlag, Berlin.

Digital Library

[15]

{15} J. G. Lewis, D. G. Payne, and R. A. van de Geijn. Matrix-vector multiplication and conjugate gradient algorithms on distributed memory computers. In Proceedings of the Scalable High Performance Computing Conference, pages 542-550, 1994.

[16]

{16} J. G. Lewis and R. A. van de Geijn. Distributed memory matrix-vector multiplication and conjugate gradient algorithms. In Proceedings of Supercomputing'93, pages 484-492, Portland, OR, November 1993.

Digital Library

[17]

{17} K. Macherey, F. Och, and H. Ney. Natural language understanding using statistical machine translation, 2001.

[18]

{18} Multiprogrammatic Capability Cluster (MCR). http://www.llnl.gov/linux/mcr.

[19]

{19} M. E. J. Newman. From the cover: The structure of scientific collaboration networks. Proceedings of the National Academy of Sciences, 98: 404-409, 2001.

[20]

{20} M. E. J. Newman. Detecting community structure in networks. European Physical Journal B, 38: 321-330, May 2004.

[21]

{21} M. E. J. Newman. Fast algorithm for detecting community structure in networks. Phys. Rev. E, 69(6): 066133, June 2004.

[22]

{22} M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Phys. Rev. E, 69(2): 026113, Feb. 2004.

[23]

{23} I. Pohl. Bi-directional search. Machine Intelligence, 6: 127-140, 1971. eds. Meltzer and Michie, Edinburgh University Press.

[24]

{24} Y.-J. Suh and K. G. Shin. All-to-all personalized communication in multidimensional torus and mesh networks. IEEE Trans. on Parallel and Distributed Systems, 12: 38-59, 2001.

Digital Library

Cited By

Neff RZarch MMinutoli MHalappanavar MTumeo AKalyanaraman ABecchi M(2024)FuseIM: Fusing Probabilistic Traversals for Influence Maximization on Exascale SystemsProceedings of the 38th ACM International Conference on Supercomputing10.1145/3650200.3656621(38-49)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3650200.3656621
Gan XWu GQiu SXiong FSi JFang JDong DGong CLi TWang ZLee IChabbi MSteuwer M(2024)GraphCube: Interconnection Hierarchy-aware Graph ProcessingProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638498(160-174)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638498
Cao HWang YWang HLin HMa ZYin WChen WLee JAgrawal KSpear M(2022)Scaling graph traversal to 281 trillion edges with 40 million coresProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508403(234-245)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508403
Show More Cited By

Index Terms

Recommendations

Parallel breadth-first search on distributed memory systems
SC '11: Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis

Data-intensive, graph-based computations are pervasive in several scientific applications, and are known to to be quite challenging to implement on distributed memory systems. In this work, we explore the design space of parallel algorithms for Breadth-...
Massively parallel breadth first search using a tree-structured memory model
PMAM '12: Proceedings of the 2012 International Workshop on Programming Models and Applications for Multicores and Manycores

Analysis of massive graphs has emerged as an important area for massively parallel computation. In this paper, it is shown how the Fresh Breeze trees-of-chunks memory model may be used to perform breadth-first search of large undirected graphs. Overall, ...
A work-efficient parallel breadth-first search algorithm (or how to cope with the nondeterminism of reducers)
SPAA '10: Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures

We have developed a multithreaded implementation of breadth-first search (BFS) of a sparse graph using the Cilk++ extensions to C++. Our PBFS program on a single processor runs as quickly as a standar. C++ breadth-first search implementation. PBFS ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SC '05: Proceedings of the 2005 ACM/IEEE conference on Supercomputing

November 2005

829 pages

ISBN:1595930612

General Chair:
William Kramer

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS: Computer Society

Publisher

IEEE Computer Society

United States

Publication History

Published: 12 November 2005

Check for updates

Qualifiers

Article

Conference

SC '05

Sponsor:

SIGARCH
IEEE-CS

SC '05: International Conference for High Performance Computing, Networking, Storage and Analysis

November 12 - 18, 2005

Acceptance Rates

SC '05 Paper Acceptance Rate 62 of 260 submissions, 24%;

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

76
Total Citations
View Citations
840
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)2

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Neff RZarch MMinutoli MHalappanavar MTumeo AKalyanaraman ABecchi M(2024)FuseIM: Fusing Probabilistic Traversals for Influence Maximization on Exascale SystemsProceedings of the 38th ACM International Conference on Supercomputing10.1145/3650200.3656621(38-49)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3650200.3656621
Gan XWu GQiu SXiong FSi JFang JDong DGong CLi TWang ZLee IChabbi MSteuwer M(2024)GraphCube: Interconnection Hierarchy-aware Graph ProcessingProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638498(160-174)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638498
Cao HWang YWang HLin HMa ZYin WChen WLee JAgrawal KSpear M(2022)Scaling graph traversal to 281 trillion edges with 40 million coresProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508403(234-245)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508403
Nakao MMurai HSato M(2020)Parallelization of All-Pairs-Shortest-Path Algorithms in Unweighted GraphProceedings of the International Conference on High Performance Computing in Asia-Pacific Region10.1145/3368474.3368478(63-72)Online publication date: 15-Jan-2020
https://dl.acm.org/doi/10.1145/3368474.3368478
Chen RShi JChen YZang BGuan HChen H(2019)PowerLyraACM Transactions on Parallel Computing10.1145/32989895:3(1-39)Online publication date: 22-Jan-2019
https://dl.acm.org/doi/10.1145/3298989
Chatarasi PSarkar V(2018)A Preliminary Study of Compiler Transformations for Graph Applications on the Emu SystemProceedings of the Workshop on Memory Centric High Performance Computing10.1145/3286475.3286481(37-44)Online publication date: 11-Nov-2018
https://dl.acm.org/doi/10.1145/3286475.3286481
Li MLu XSubramoni HPanda D(2018)Multi-Threading and Lock-Free MPI RMA Based Graph Processing on KNL and POWER ArchitecturesProceedings of the 25th European MPI Users' Group Meeting10.1145/3236367.3236371(1-10)Online publication date: 23-Sep-2018
https://dl.acm.org/doi/10.1145/3236367.3236371
Bondu JMishra ALaxmi VGaur MShekhawat RGaur MElci AVaidya JMakarevich OPoet ROrgun MDhaka VBohra MSingh VBabenko LSheykhkanloo NRahnama B(2017)Flooding in secure wireless sensor networksProceedings of the 10th International Conference on Security of Information and Networks10.1145/3136825.3136867(151-156)Online publication date: 13-Oct-2017
https://dl.acm.org/doi/10.1145/3136825.3136867
Imamura SYasui YInoue KOno TSasaki HFujisawa KSuzumura TGarcia-Gasulla DDayarathna MShun J(2016)Power-efficient breadth-first search with DRAM row buffer locality-aware address mappingProceedings of the First International Workshop on High Performance Graph Data Management and Processing10.5555/3018830.3018833(17-24)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.5555/3018830.3018833
Kumar PHuang HWest J(2016)G-storeProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.5555/3014904.3014999(1-12)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.5555/3014904.3014999
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents