The DOI matches its Crossref record; 20 of the 20 references it cites were found in a registry or an index.
Efficient Parallel Graph Exploration on Multi-Core CPU and GPU
Abstract
Graphs are a fundamental data representation that has been used extensively in various domains. In graph-based applications, a systematic exploration of the graph such as a breadth-first search (BFS) often serves as a key component in the processing of their massive data sets. In this paper, we present a new method for implementing the parallel BFS algorithm on multi-core CPUs which exploits a fundamental property of randomly shaped real-world graph instances. By utilizing memory bandwidth more efficiently, our method shows improved performance over the current state-of-the-art implementation and increases its advantage as the size of the graph increases. We then propose a hybrid method which, for each level of the BFS algorithm, dynamically chooses the best implementation from: a sequential execution, two different methods of multicore execution, and a GPU execution. Such a hybrid approach provides the best performance for each graph size while avoiding poor worst-case performance on high-diameter graphs. Finally, we study the effects of the underlying architecture on BFS performance by comparing multiple CPU and GPU systems, a high-end GPU system performed as well as a quad-socket high-end CPU system.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Collective dynamics of ‘small-world’ networks
Watts, D. J., & Strogatz, S. H. (1998) · Nature · doi:10.1038/30918 · Cited by 43,060
Adhi Harmoko, S., M.Komp, Jacquard, J. M., Zuse, K., & Eniac (2005) · Cited by 18,035
Finding and evaluating community structure in networks
Newman, M. E. J., & Girvan, M. (2004) · Physical Review E · doi:10.1103/physreve.69.026113 · Cited by 13,931
A faster algorithm for betweenness centrality*
Brandes, U. (2001) · The Journal of Mathematical Sociology · doi:10.1080/0022250x.2001.9990249 · Cited by 4,936
Pregel: a system for large-scale graph processing
Malewicz, G., Austern, M. H., Bik, A. J. C., Dehnert, J. C., Horn, I., Leiser, N., & Czajkowski, G. (2010) · Proceedings of the 2010 ACM SIGMOD International Conference on Management of data · doi:10.1145/1807167.1807184 · Cited by 3,515
O’Regan, G. (2023) · Texts in Computer Science · doi:10.1007/978-3-031-26212-8_4 · Cited by 1,614
R-MAT: A Recursive Model for Graph Mining
Chakrabarti, D., Zhan, Y., & Faloutsos, C. (2004) · Proceedings of the 2004 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972740.43 · Cited by 1,255
Nickolls, J., & Dally, W. J. (2010) · IEEE Micro · doi:10.1109/mm.2010.41 · Cited by 980
(1998) · Choice Reviews Online · doi:10.5860/choice.35-6287 · Cited by 904
Accelerating Large Graph Algorithms on the GPU Using CUDA
Harish, P., & Narayanan, P. J. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-77220-0_21 · Cited by 734
Tong, A. H. Y., Drees, B., Nardelli, G., Bader, G. D., Brannetti, B., Castagnoli, L., Evangelista, M., Ferracuti, S., Nelson, B., Paoluzi, S., et al. (2002) · Science · doi:10.1126/science.1064987 · Cited by 700
Debunking the 100X GPU vs. CPU myth: an evaluation of throughput computing on CPU and GPU
Lee, V. W., Kim, C., Chhugani, J., Deisher, M., Kim, D., Nguyen, A. D., Satish, N., Smelyanskiy, M., Chennupaty, S., Hammarlund, P., et al. (2010) · Proceedings of the 37th annual international symposium on Computer architecture · doi:10.1145/1815961.1816021 · Cited by 640
CHALLENGES IN PARALLEL GRAPH PROCESSING
LUMSDAINE, A., GREGOR, D., HENDRICKSON, B., & BERRY, J. (2007) · Parallel Processing Letters · doi:10.1142/s0129626407002843 · Cited by 469
Accelerating CUDA graph algorithms at maximum warp
Hong, S., Kim, S. K., Oguntebi, T., & Olukotun, K. (2011) · Proceedings of the 16th ACM symposium on Principles and practice of parallel programming · doi:10.1145/1941553.1941590 · Cited by 339
Self-citationA Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L
Yoo, A., Chow, E., Henderson, K., McLendon, W., Hendrickson, B., & Catalyurek, U. (2005) · ACM/IEEE SC 2005 Conference (SC'05) · doi:10.1109/sc.2005.4 · Cited by 261
Global A-Optimal Robot Exploration in SLAM
Sim, R., & Roy, N. (2006) · Proceedings of the 2005 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.2005.1570193 · Cited by 238
Scalable Graph Exploration on Multicore Processors
Agarwal, V., Petrini, F., Pasetto, D., & Bader, D. A. (2010) · 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis · doi:10.1109/sc.2010.46 · Cited by 223
Designing Multithreaded Algorithms for Breadth-First Search and st-connectivity on the Cray MTA-2
Bader, D. A., & Madduri, K. (2006) · 2006 International Conference on Parallel Processing (ICPP'06) · doi:10.1109/icpp.2006.34 · Cited by 216
Design and Implementation of the HPCS Graph Analysis Benchmark on Symmetric Multiprocessors
Bader, D. A., & Madduri, K. (2005) · Lecture notes in computer science · doi:10.1007/11602569_48 · Cited by 151
Bader, D. A., & Madduri, K. (2008) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2008.4536261 · Cited by 122
Cited by
Ligra: a lightweight graph processing framework for shared memory
Shun, J., & Blelloch, G. E. (2013) · Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming · doi:10.1145/2442516.2442530 · Cited by 798
A scalable processing-in-memory accelerator for parallel graph processing
Ahn, J., Hong, S., Yoo, S., Mutlu, O., & Choi, K. (2015) · Proceedings of the 42nd Annual International Symposium on Computer Architecture · doi:10.1145/2749469.2750386 · Cited by 767
Self-citationX-Stream: edge-centric graph processing using streaming partitions
Roy, A., Mihailovic, I., & Zwaenepoel, W. (2013) · Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles · doi:10.1145/2517349.2522740 · Cited by 673
A Survey of CPU-GPU Heterogeneous Computing Techniques
Mittal, S., & Vetter, J. S. (2015) · ACM Computing Surveys · doi:10.1145/2788396 · Cited by 568
Direction-optimizing Breadth-First Search
Beamer, S., Asanovic, K., & Patterson, D. (2012) · 2012 International Conference for High Performance Computing, Networking, Storage and Analysis · doi:10.1109/sc.2012.50 · Cited by 325
Metadata
- Authors
- Hong, S., Oguntebi, T., & Olukotun, K.
- Venue
- 2011 International Conference on Parallel Architectures and Compilation Techniques
- Publisher
- IEEE
- Published
- 2011-10
- Pages
- 78-88
- OpenAlex
- W2055497547
- Cited by
- 269
- References
- 20
- FWCI
- 22.72
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.