World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

CHALLENGES IN PARALLEL GRAPH PROCESSING

    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

    • C. Amzaet al., IEEE Computer 29(2), 18 (1996). Crossref, ISIGoogle Scholar
    • W.   Anderson et al. , 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 et al. , Graph software development and performance on the MTA-2 and Eldorado , Cray User's Group ( 2006 ) . Google Scholar
    • L. Dagum and R. Menon, IEEE Computational Science and Engineering 5(1), 46 (1998), DOI: 10.1109/99.660313. CrossrefGoogle 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. Feoet al., Eldorado, Proc. 2nd Conf. Computing Frontiers (2005) pp. 28–34. Google Scholar
    • E. Gabrielet al., 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 et al. , MPI — The Complete Reference: Volume 2, the MPI-2 Extensions ( MIT Press , 1998 ) . CrossrefGoogle Scholar
    • J.   JáJá , An introduction to parallel algorithms ( Addison Wesley Longman Publishing Co., Inc. , Redwood City, CA, USA , 1992 ) . Google Scholar
    • K.   Madduri et al. , 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 et al. , DRS: A simple to write yet difficult to execute benchmark , Proc. IEEE Intl. Symp. Workload Characterizations ( 2006 ) . Google Scholar
    • R. C. Murphy and P. M. Kogge, 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 et al. , Analyzing the scalability of Eldorado , Proc. Cray User's Group ( 2006 ) . Google Scholar
    • L. G. Valiant, Communications of the ACM 33(8), 103 (1990), DOI: 10.1145/79173.79181. Crossref, ISIGoogle Scholar
    • A. Yooet al., 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