CHALLENGES IN PARALLEL GRAPH PROCESSING
Abstract
Graph algorithms are becoming increasingly important for solving many problems in scientific computing, data mining and other domains. As these problems grow in scale, parallel computing resources are required to meet their computational and memory requirements. Unfortunately, the algorithms, software, and hardware that have worked well for developing mainstream parallel scientific applications are not necessarily effective for large-scale graph problems. In this paper we present the inter-relationships between graph problems, software, and parallel hardware in the current state of the art and discuss how those issues present inherent challenges in solving large-scale graph problems. The range of these challenges suggests a research agenda for the development of scalable high-performance software for graph problems.
References
- IEEE Computer 29(2), 18 (1996). Crossref, ISI, Google Scholar
-
W. Anderson , Early experiences with scientific programs on the Cray MTA-2 , Proc. SC'03 ( 2003 ) . Google Scholar -
D. Bader and K. Madduri , Designing multithreaded algorithms for breadth-first search and st-connectivity on the Cray MTA-2 , Proc. 35th Int'l Conf. on Parallel Processing (ICPP) ( IEEE Computer Society , 2006 ) . Google Scholar -
J. W. Berry , Graph software development and performance on the MTA-2 and Eldorado , Cray User's Group ( 2006 ) . Google Scholar - IEEE Computational Science and Engineering 5(1), 46 (1998), DOI: 10.1109/99.660313. Crossref, Google Scholar
- T. A. El-Ghazawi, W. W. Carlson, and J. M. Draper. UPC Language Specification, 1.1 edition, May 2003. http://www.gwu.edu/~upc/downloads/-upc_specs_1.1p2prel.pdf . Google Scholar
J. Feo , Eldorado, Proc. 2nd Conf. Computing Frontiers (2005) pp. 28–34. Google ScholarE. Gabriel , Open MPI: Goals, concept, and design of a next generation MPI implementation, Proceedings, 11th European PVM/MPI Users' Group Meeting (2004) pp. 97–104. Google Scholar- D. Gregor, N. Edmonds, B. Barrett, and A. Lumsdaine. The Parallel Boost Graph Library, http://www.osl.iu.edu/research/pbgl, 2005 . Google Scholar
-
D. Gregor and A. Lumsdaine , The Parallel BGL: A generic library for distributed graph computations , Parallel Object-Oriented Scientific Computing (POOSC) ( 2005 ) . Google Scholar -
W. Gropp , MPI — The Complete Reference: Volume 2, the MPI-2 Extensions ( MIT Press , 1998 ) . Crossref, Google Scholar -
J. JáJá , An introduction to parallel algorithms ( Addison Wesley Longman Publishing Co., Inc. , Redwood City, CA, USA , 1992 ) . Google Scholar -
K. Madduri , Parallel shortest path algorithms for solving large-scale instances , 9th DIMACS Implementation Challenge: Shortest Paths ( 2006 ) . Google Scholar - , MPI: A Message Passing Interface, Proc. of Supercomputing '93 (IEEE Computer Society Press, 1993) pp. 878–883. Google Scholar
U. Meyer and P. Sanders , Delta-stepping: A parallel single source shortest path algorithm, ESA '98: Proceedings of the 6th Annual European Symposium on Algorithms (Springer-Verlag, 1998) pp. 393–404. Google Scholar-
R. C. Murphy , DRS: A simple to write yet difficult to execute benchmark , Proc. IEEE Intl. Symp. Workload Characterizations ( 2006 ) . Google Scholar - IEEE Trans. Computers (2007). Google Scholar
- , System Application Program Interface (API) [C Language]. Information technology—Portable Operating System Interface (POSIX) ( IEEE Press , Piscataway, NJ , 1990 ) . Google Scholar
-
K. Underwood , Analyzing the scalability of Eldorado , Proc. Cray User's Group ( 2006 ) . Google Scholar - Communications of the ACM 33(8), 103 (1990), DOI: 10.1145/79173.79181. Crossref, ISI, Google Scholar
A. Yoo , A scalable distributed parallel breadth-first search algorithm on BlueGene/L, SC '05: Proceedings of the 2005 ACM/IEEE conference on Supercomputing (IEEE Computer Society, 2005) p. 25. Google Scholar


