Abstract
Breadth-first search (BFS) is an important graph analysis kernel. The Graph500 benchmark measures a computer’s BFS performance using the traversed edges per second (TEPS) ratio. Our previous nonuniform memory access (NUMA)-optimized BFS reduced memory accesses to remote RAM on a NUMA architecture system; its performance was 11 GTEPS (giga TEPS) on a 4-way Intel Xeon E5-4640 system. Herein, we investigated the computational complexity of the bottom-up, a major bottleneck in NUMA-optimized BFS. We clarify the relationship between vertex out-degree and bottom-up performance. In November 2013, our new implementation achieved a Graph500 benchmark performance of 37.66 GTEPS (fastest for a single node) on an SGI Altix UV1000 (one-rack) and 31.65 GTEPS (fastest for a single server) on a 4-way Intel Xeon E5-4650 system. Furthermore, we achieved the highest Green Graph500 performance of 153.17 MTEPS/W (mega TEPS per watt) on an Xperia-A SO-04E with a Qualcomm Snapdragon S4 Pro APQ8064.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM 19(2), 248–264 (1972)
Cormen, T., Leiserson, C., Rivest, R.: Introduction to Algorithms. MIT Press, Cambridge (1990)
Brandes, U.: A Faster Algorithm for Betweenness Centrality. J. Math. Sociol. 25(2), 163–177 (2001)
Frasca, M., Madduri, K., Raghavan, P.: NUMA-Aware Graph Mining Techniques for Performance and Energy Efficiency. In: Proc. ACM/IEEE Int. Conf. High Performance Computing, Networking, Storage and Analysis (SC 2012), pp. 1–11. IEEE Computer Society (2012)
Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99, 7821–7826 (2002)
Yasui, Y., Fujisawa, K., Goto, K., Kamiyama, N., Takamatsu, M.: NETAL: High-performance Implementation of Network Analysis Library Considering Computer Memory Hierarchy. J. Oper. Res. Soc. Japan 54(4), 259–280 (2011)
Fujisawa, K., Endo, T., Yasui, Y., Sato, H., Matsuzawa, N., Matsuoka, S., Waki, H.: Petascale General Solver for Semidefinite Programming Problems with Over Two Million Constraints. In: Proc. IEEE Int. Symp. Parallel and Distributed Processing (IPDPS 2014). IEEE Computer Society (2014)
Murphy, R.C., Wheeler, K.B., Barrett, B.W., Ang, J.A.: Introducing the Graph500. In: Cray User Group 2010 Proceedings (2010)
Hoefler, T.: GreenGraph500 Submission Rules, http://green.graph500.org/greengraph500rules.pdf
Leskovec, J., Chakrabarti, D., Kleinberg, J., Faloutsos, C., Ghahramani, Z.: Kronecker Graphs: An Approach to Modeling Networks. J. Mach. Learning Res. 11, 985–1042 (2010)
Chakrabarti, D., Zhan, Y., Faloutsos, C.: R-MAT: A Recursive Model for Graph Mining. In: Proc. 4th SIAM Int. Conf. Data Mining, pp. 442–446. SIAM (2004)
Bader, D.A., Madduri, K.: Designing Multithreaded Algorithms for Breadth-First Search and st-connectivity on the Cray MTA-2. In: Proc. 2006 Int. Conf. Parallel Processing (ICPP 2006), pp. 523–530. IEEE Computer Society (2006)
Agarwal, V., Petrini, F., Pasetto, D., Bader, D.A.: Scalable Graph Exploration on Multicore Processors. In: Proc. ACM/IEEE Int. Conf. High Performance Computing, Networking, Storage and Analysis (SC 2010), pp. 1–11. IEEE Computer Society (2010)
Beamer, S., Asanović, K., Patterson, D.A.: Searching for a Parent Instead of Fighting Over Children: A Fast Breadth-first Search Implementation for Graph500. EECS Department, University of California, UCB/EECS-2011-117, Berkeley, CA (2011)
Beamer, S., Asanović, K., Patterson, D.A.: Direction-optimizing Breadth-first Search. In: Proc. ACM/IEEE Int. Conf. High Performance Computing, Networking, Storage and Analysis (SC 2012), p. 12. IEEE Computer Society (2012)
Yasui, Y., Fujisawa, K., Goto, K.: NUMA-optimized Parallel Breadth-first Search on Multicore Single-node System. In: Proc. IEEE Int. Conf. BigData 2013. IEEE Computer Society (2013)
Yoo, A., Chow, E., Henderson, K., McLendon, W., Hendrickson, B., Catalyurek, U.: A Scalable Distributed Parallel Breadth-first Search Algorithm on BlueGene/L. In: Proc. ACM/IEEE Conf. Supercomputing (SC 2005), p. 25. IEEE Computer Society (2005)
Buluç, A., Madduri, K.: Parallel Breadth-first Search on Distributed Memory Systems. In: Proc. ACM/IEEE Int. Conf. High Performance Computing, Networking, Storage and Analysis (SC11), p. 65. ACM (2011)
Petrini, F., Checconi, F., Willcock, J., Lumsdaine, A., Choudhury, A.R., Sabharval, Y.: Breaking the Speed and Scalability Barriers for Graph Exploration on Distributed-memory Machines. In: Proc. ACM/IEEE Int. Conf. High Performance Computing, Networking, Storage and Analysis (SC 2012), p. 13. IEEE Computer Society (2012)
Ueno, K., Suzumura, T.: Highly Scalable Graph Search for the Graph500 Benchmark. In: Proc. 21st Int. ACM Symp. High-Performance Parallel and Distributed Computing (HPDC 2012), pp. 149–160. ACM (2012)
Ueno, K., Suzumura, T.: Parallel Distributed Breadth First Search on GPU. In: Proc. IEEE Int. Conf. High Performance Computing (HiPC 2013). IEEE Computer Society (2013)
McAuley, J., Leskovec, J.: Image Labeling on a Network: Using Social-Network Metadata for Image Classification. In: Fitzgibbon, A., Lazebnik, S., Perona, P., Sato, Y., Schmid, C. (eds.) ECCV 2012, Part IV. LNCS, vol. 7575, pp. 828–841. Springer, Heidelberg (2012)
Leskovec, J., Huttenlocher, D., Kleinberg, J.: Signed Networks in Social Media. In: CHI (2010)
Leskovec, J., Huttenlocher, D., Kleinberg, J.: Predicting Positive and Negative Links in Online Social Networks. In: WWW (2010)
The 9th DIMACS Implementation Challenge, http://www.dis.uniroma1.it/~challenge9/
Backstrom, L., Huttenlocher, D., Kleinberg, J., Lan, X.: Group Formation in Large Social Networks: Membership, Growth, and Evolution. In: KDD (2006)
Leskovec, J., Lang, K., Dasgupta, A., Mahoney, M.: Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters. Internet Mathematics 6(1), 29–123 (2009)
Kwak, H., Lee, C., Park, H., Moon, S.: What is Twitter, a Social Network or a News Media? In: Proceedings of the 19th International Conference on World Wide Web (WWW 2010), pp. 591–600 (2010)
Yang, J., Leskovec, J.: Defining and Evaluating Network Communities based on Ground-truth. In: ICDM (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Yasui, Y., Fujisawa, K., Sato, Y. (2014). Fast and Energy-efficient Breadth-First Search on a Single NUMA System. In: Kunkel, J.M., Ludwig, T., Meuer, H.W. (eds) Supercomputing. ISC 2014. Lecture Notes in Computer Science, vol 8488. Springer, Cham. https://doi.org/10.1007/978-3-319-07518-1_23
Download citation
DOI: https://doi.org/10.1007/978-3-319-07518-1_23
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07517-4
Online ISBN: 978-3-319-07518-1
eBook Packages: Computer ScienceComputer Science (R0)