Abstract
We introduce a new parallel algorithm for approximate breadth-first ordering of an unweighted graph by using bounded asynchrony to parametrically control both the performance and error of the algorithm. This work is based on the \(k\)-level asynchronous (KLA) paradigm that trades expensive global synchronizations in the level-synchronous model for local synchronizations in the asynchronous model, which may result in redundant work. Instead of correcting errors introduced by asynchrony and redoing work as in KLA, in this work we control the amount of work that is redone and thus the amount of error allowed, leading to higher performance at the expense of a loss of precision. Results of an implementation of this algorithm are presented on up to 32,768 cores, showing 2.27x improvement over the exact KLA algorithm and 3.8x improvement over the level-synchronous version with minimal error on several graph inputs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
The graph 500 list (2011). http://www.graph500.org
Stanford large network dataset collection (2013). http://snap.stanford.edu/data/index.html
Avery, C.: Giraph: large-scale graph processing infrastructure on hadoop. In: Hadoop Summit (2011)
Baswana, S., Kavitha, T.: Faster algorithms for all-pairs approximate shortest paths in undirected graphs. SIAM J. Comput. 39(7), 2865–2896 (2010)
Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in expected O(n2) time. ACM Trans. Algorithms 2(4), 557–577 (2006)
Beamer, S., Asanović, K., Patterson, D.: Direction-optimizing breadth-first search. In: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, SC 2012, pp. 12:1–12:10. IEEE Computer Society Press, Los Alamitos (2012)
Becchetti, L., Boldi, P., Castillo, C., Gionis, A.: Efficient algorithms for large-scale local triangle counting. ACM Trans. Knowl. Discov. Data 4(3), 13:1–13:28 (2010)
Buluç, A., Beamer, S., Madduri, K., Asanović, K., Patterson, D.: Distributed-memory breadth-first search on massive graphs. In: Bader, D. (ed.) Parallel Graph Algorithms. CRC Press (2015)
Buluç, A., Madduri, K.: Parallel breadth-first search on distributed memory systems. In: Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2011, pp. 65:1–65:12. ACM, New York (2011)
Buss, A.A., Harshvardhan, Papadopoulos, I., Pearce, O., Smith, T.G., Tanase, G., Thomas, N., Xu, X., Bianco, M., Amato, N.M., Rauchwerger, L.: STAPL: standard template adaptive parallel library. In: Proceedings of SYSTOR 2010: The 3rd Annual Haifa Experimental Systems Conference, Haifa, Israel, 24–26 May 2010, pp. 1–10. ACM, New York (2010)
Ceccarello, M., Pietracaprina, A., Pucci, G., Upfal, E.: Space and time efficient parallel graph decomposition, clustering, and diameter approximation. In: Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, pp. 182–191. ACM, New York (2015)
Gregor, D., Lumsdaine, A.: The parallel BGL: a generic library for distributed graph computations. In: Parallel Object-Oriented Scientific Computing (POOSC), July 2005
Gubichev, A., Bedathur, S., Seufert, S., Weikum, G.: Fast and accurate estimation of shortest paths in large graphs. In: Proceedings of the 19th ACM International Conference on Information and Knowledge Management, CIKM 2010, pp. 499–508. ACM, New York (2010)
Harshvardhan, Fidel, A., Amato, N.M., Rauchwerger, L.: The STAPL parallel graph library. In: Kasahara, H., Kimura, K. (eds.) LCPC 2012. LNCS, vol. 7760, pp. 46–60. Springer, Berlin Heidelberg (2012)
Harshvardhan, Fidel, A., Amato, N.M., Rauchwerger, L.: KLA: a new algorithmic paradigm for parallel graph computations. In: Proceedings of the International Conference on Parallel Architecture and Compilation Techniques (PACT), PACT 2014, pp. 27–38. ACM, New York (2014). Conference Best Paper Award
Harshvardhan, Fidel, A., Amato, N.M., Rauchwerger, L.: An algorithmic approach to communication reduction in parallel graph algorithms. In: Proceedings of the International Conference Parallel Architecture and Compilation Techniques (PACT), PACT 2015, pp. 201–212. IEEE, San Francisco (2015). Finalist for Conference Best Paper Award
Hong, S., Chafi, H., Sedlar, E., Olukotun, K.: Green-Marl: a DSL for easy and efficient graph analysis. In: Proceedings of the Seventeenth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2012, pp. 349–362. ACM, New York (2012)
Klein, P.N., Subramanian, S.: A randomized parallel algorithm for single-source shortest paths. J. Algorithms 25(2), 205–220 (1997)
Low, Y., Bickson, D., Gonzalez, J., Guestrin, C., Kyrola, A., Hellerstein, J.M.: Distributed graphlab: a framework for machine learning and data mining in the cloud. Proc. VLDB Endow. 5(8), 716–727 (2012)
Malewicz, G., Austern, M.H., Bik, A.J., Dehnert, J.C., Horn, I., Leiser, N., Czajkowski, G.: Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 International Conference on Management of Data, SIGMOD 2010, pp. 135–146. ACM, New York (2010)
Méndez-Lojo, M., Nguyen, D., Prountzos, D., Sui, X., Hassaan, M.A., Kulkarni, M., Burtscher, M., Pingali, K.: Structure-driven optimizations for amorphous data-parallel programs. In: Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2010, pp. 3–14. ACM, New York (2010)
Nanongkai, D.: Distributed approximation algorithms for weighted shortest paths. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC 2014, pp. 565–573. ACM, New York (2014)
Nelson, J., Holt, B., Myers, B., Briggs, P., Kahan, S., Ceze, L., Oskin, M.: Grappa: a latency-tolerant runtime for large-scale irregular application. In: WRSC 2014, April 2014
Nguyen, D., Lenharth, A., Pingali, K.: A lightweight infrastructure for graph analytics. In: Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP 2013, pp. 456–471. ACM, New York (2013)
Palmer, C.R., Gibbons, P.B., Faloutsos, C.: ANF: afast and scalable tool for data mining in massive graphs. In: Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2002, pp. 81–90. ACM, New York (2002)
Pearce, R.A., Gokhale, M., Amato, N.M.: Multithreaded asynchronous graph traversal for in-memory and semi-external memory. In: Conference on High Performance Computing Networking, Storage and Analysis, SC 2010, New Orleans, LA, USA, 13–19 November 2010, pp. 1–11 (2010)
Qi, Z., Xiao, Y., Shao, B., Wang, H.: Toward a distance oracle for billion-node graphs. Proc. VLDB Endow. 7(1), 61–72 (2013)
Qiao, M., Cheng, H., Chang, L., Yu, J.X.: Approximate shortest distance computing: a query-dependent local landmark scheme. IEEE Trans. Knowl. Data Eng. 26(1), 55–68 (2014)
Shang, Z., Yu, J.X.: Auto-approximation of graph computing. Proc. VLDB Endow. 7(14), 1833–1844 (2014)
Sommer, C.: Shortest-path queries in static networks. ACM Comput. Surv. 46(4), 45:1–45:31 (2014)
Tanase, G., Buss, A.A., Fidel, A., Harshvardhan, Papadopoulos, I., Pearce, O., Smith, T.G., Thomas, N., Xu, X., Mourad, N., Vu, J., Bianco, M., Amato, N.M., Rauchwerger, L.: The STAPL parallel container framework. In: Proceedings of the 16th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 2011, San Antonio, TX, USA, 12–16 February 2011, pp. 235–246 (2011)
Thorup, M., Zwick, U.: Approximate distance oracles. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, STOC 2001, pp. 183–192. ACM, New York (2001)
Ullman, J., Yannakakis, M.: High-probability parallel transitive closure algorithms. In: Proceedings of the Second Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1990, pp. 200–209. ACM, New York (1990)
Valiant, L.: Bridging model for parallel computation. Comm. ACM 33(8), 103–111 (1990)
Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. In: Nature, pp. 440–442 (1998)
Acknowledgments
We would like to thank Daniel Latypov for help with aspects of the proof. We would also like to thank our anonymous reviewers.
This research supported in part by NSF awards CNS-0551685, CCF 0702765, CCF-0833199, CCF-1439145, CCF-1423111, CCF-0830753, IIS-0916053, IIS-0917266, EFRI-1240483, RI-1217991, by NIH NCI R25 CA090301-11, and by DOE awards DE-AC02-06CH11357, DE-NA0002376, B575363. This research used resources of the National Energy Research Scientific Computing Center, which is supported by the Office of Science of the U.S. Department of Energy under Contract No. DE-AC02-05CH11231.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Fidel, A., Sabido, F.C., Riedel, C., Amato, N.M., Rauchwerger, L. (2017). Fast Approximate Distance Queries in Unweighted Graphs Using Bounded Asynchrony. In: Ding, C., Criswell, J., Wu, P. (eds) Languages and Compilers for Parallel Computing. LCPC 2016. Lecture Notes in Computer Science(), vol 10136. Springer, Cham. https://doi.org/10.1007/978-3-319-52709-3_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-52709-3_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-52708-6
Online ISBN: 978-3-319-52709-3
eBook Packages: Computer ScienceComputer Science (R0)