Abstract
Single-source shortest path (SSSP) is a well-known graph computation that has been studied for more than half a century. It is one of the most common graph analytical analyses in many research areas such as networks, communication, transportation, electronics, and so on. In this chapter, we propose scalable SSSP algorithms for distributed memory systems. Our algorithms are based on a ∆-step** algorithm with the use of a two-dimensional (2D) graph layout as an underlying graph data structure to reduce communication overhead and improve load balancing. The detailed evaluation of the algorithms on various large-scale, real-world graphs is also included. Our experiments show that the algorithm with the 2D graph layout delivers up to three times the performance (in TEPS), and uses only one-fifth of the communication time of the algorithm with a one-dimensional layout.
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
Dijkstra, E. W. (1959). A note on two problems in connection with graphs. Numerische Mathematik, 1(1), 269–271.
Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16, 87–90.
Ford, L. A. (1956). Network flow theory. Tech. Rep. Report P-923. Santa Monica, CA: The Rand Corporation.
Gregor, D., & Lumsdaine, A. (2005). The Parallel BGL: A generic library for distributed graph computations. Parallel Object-Oriented Scientific Computing, 2, 1–18.
Low, Y., Bickson, D., Gonzalez, J., Guestrin, C., Kyrola, A., & Hellerstein, J. M. (2012). Distributed GraphLab: A framework for machine learning and data mining in the cloud. Proceedings of the VLDB Endowment, 5(8), 716–727.
Gonzalez, J. E., Low, Y., Gu, H., Bickson, D., & Guestrin, C. (2012). PowerGraph: Distributed graph-parallel computation on natural graphs. In: OSDI (Vol. 12, p. 2).
Galois. Retrieved July 15, 2018, from http://iss.ices.utexas.edu/?p=projects/galois.
Dayarathna, M., Houngkaew, C., & Suzumura, T. (2012). Introducing ScaleGraph: An X10 library for billion scale graph analytics. In Proceedings of the 2012 ACM SIGPLAN X10 Workshop (p. 6). New York: ACM.
White, T. (2012). Hadoop: The definitive guide. Newton, MA: O’Reilly Media.
Chen, R., Ding, X., Wang, P., Chen, H., Zang, B., & Guan, H. (2014). Computation and communication efficient graph processing with distributed immutable view. In Proceedings of the 23rd International Symposium on High-Performance Parallel and Distributed Computing (pp. 215–226). New York: ACM.
**n, R. S., Gonzalez, J. E., Franklin, M. J., & Stoica, I. (2013). Graphx: A resilient distributed graph system on Spark. In First International Workshop on Graph Data Management Experiences and Systems (p. 2). New York: ACM.
Khayyat, Z., Awara, K., Alonazi, A., Jamjoom, H., Williams, D., & Kalnis, P. (2013). Mizan: A system for dynamic load balancing in large-scale graph processing. In Proceedings of the 8th ACM European Conference on Computer Systems (pp. 169–182). New York: ACM.
Davidson, A. A., Baxter, S., Garland, M., & Owens, J. D. (2014). Work-efficient parallel GPU methods for single-source shortest paths. In International Parallel and Distributed Processing Symposium (Vol. 28).
Wang, Y., Davidson, A., Pan, Y., Wu, Y., Riffel, A., & Owens, J. D. (2015). Gunrock: A high-performance graph processing library on the GPU. In Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (pp. 265–266.. PPoPP 2015).
Zhong, J., & He, B. (2014). Medusa: Simplified graph processing on GPUs. IEEE Transactions on Parallel and Distributed Systems, 25(6), 1543–1552.
Madduri, K., Bader, D. A., Berry, J. W., & Crobak, J. R. (2007). An experimental study of a parallel shortest path algorithm for solving large-scale graph instances. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX) (pp. 23–35). Society for Industrial and Applied Mathematics.
Prabhakaran, V., Wu, M., Weng, X., McSherry, F., Zhou, L., & Haridasan, M. (2012). Managing large graphs on multi-cores with graph awareness. In Proceedings of USENIX Annual Technical Conference (ATC).
Shun, J., & Blelloch, G. E. (2013). Ligra: A lightweight graph processing framework for shared memory. In: Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (pp. 135–146). PPoPP’13.
Chakaravarthy, V. T., Checconi, F., Petrini, F., & Sabharwal, Y. (2014). Scalable single source shortest path algorithms for massively parallel systems. In Proceedings of IEEE 28th International Parallel and Distributed Processing Symposium (pp. 889–901).
Dial, R. B. (1969). Algorithm 360: Shortest-path forest with topological ordering. Communications of the ACM, 12(11), 632–633.
Meyer, U., & Sanders, P. (2003). ∆-step**: A parallelizable shortest path algorithm. Journal of Algorithms, 49(1), 114–152.
Buluç, A., & Madduri, K. (2011). Parallel breadth-first search on distributed memory systems. In: Proceedings of High Performance Computing, Networking, Storage and Analysis (SC).
Panitanarak, T., & Madduri, K. (2014). Performance analysis of single-source shortest path algorithms on distributed-memory systems. In SIAM Workshop on Combinatorial Scientific Computing (CSC) (p. 60). Citeseer.
Beamer, S., Asanović, K., & Patterson, D. (2013). Direction-optimizing breadth-first search. Scientific Programming, 21(3–4), 137–148.
StarCluster. Retrieved July 15, 2018, from http://star.mit.edu/cluster/.
Amazon Web Services. Amazon elastic compute cloud. Retrieved July 15, 2018, from http://aws.amazon.com/ec2/.
The Graph 500. Retrieved July 15, 2018, from http://www.graph500.org.
The University of Florida Sparse Matrix Collection. Retrieved July 15, 2018, from https://www.cise.ufl.edu/research/sparse/matrices/.
SNAP: Stanford Network Analysis Project. Retrieved July 15, 2018, from https://snap.stanford.edu/data/.
Acknowledgments
The author would like to thank Dr. Kamesh Madduri, an associate professor at Pennsylvania State University, USA, for the inspiration and kind support.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Panitanarak, T. (2020). Distributed Single-Source Shortest Path Algorithms with Two-Dimensional Graph Layout. In: Berry, M., Mohamed, A., Yap, B. (eds) Supervised and Unsupervised Learning for Data Science . Unsupervised and Semi-Supervised Learning. Springer, Cham. https://doi.org/10.1007/978-3-030-22475-2_3
Download citation
DOI: https://doi.org/10.1007/978-3-030-22475-2_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-22474-5
Online ISBN: 978-3-030-22475-2
eBook Packages: EngineeringEngineering (R0)