Julian Shun
Guy E. Blelloch
ABSTRACT
There has been significant recent interest in parallel frameworks for processing graphs due to their applicability in studying social networks, the Web graph, networks in biology, and unstructured meshes in scientific simulation. Due to the desire to process large graphs, these systems have emphasized the ability to run on distributed memory machines. Today, however, a single multicore server can support more than a terabyte of memory, which can fit graphs with tens or even hundreds of billions of edges. Furthermore, for graph algorithms, shared-memory multicores are generally significantly more efficient on a per core, per dollar, and per joule basis than distributed memory systems, and shared-memory algorithms tend to be simpler than their distributed counterparts.
In this paper, we present a lightweight graph processing framework that is specific for shared-memory parallel/multicore machines, which makes graph traversal algorithms easy to write. The framework has two very simple routines, one for mapping over edges and one for mapping over vertices. Our routines can be applied to any subset of the vertices, which makes the framework useful for many graph traversal algorithms that operate on subsets of the vertices. Based on recent ideas used in a very fast algorithm for breadth-first search (BFS), our routines automatically adapt to the density of vertex sets. We implement several algorithms in this framework, including BFS, graph radii estimation, graph connectivity, betweenness centrality, PageRank and single-source shortest paths. Our algorithms expressed using this framework are very simple and concise, and perform almost as well as highly optimized code. Furthermore, they get good speedups on a 40-core machine and are significantly more efficient than previously reported results using graph frameworks on machines with many more cores.
- V. Agarwal, F. Petrini, D. Pasetto, and D. A. Bader. Scalable graph exploration on multicore processors. In SC, 2010. Google Scholar
Digital Library
- D. A. Bader, S. Kintali, K. Madduri, and M. Mihail. Approximating betweenness centrality. In WAW, 2007. Google ScholarDigital Library
- S. Beamer, K. Asanović, and D. Patterson. Searching for a parent instead of fighting over children: A fast breadth-first search implementation for graph500. Technical Report UCB/EECS-2011-117, EECS Department, University of California, Berkeley, 2011.Google Scholar
- S. Beamer, K. Asanović, and D. Patterson. Direction-optimizing breadth-first search. In SC, 2012. Google ScholarDigital Library
- J. Berry, B. Hendrickson, S. Kahan, and P. Konecny. Software and algorithms for graph queries on multithreaded architectures. In In IPDPS, 2007.Google ScholarCross Ref
- U. Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25, 2001.Google Scholar
- S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. In WWW, 1998. Google ScholarDigital Library
- A. Buluç and J. R. Gilbert. The Combinatorial BLAS: Design, implementation, and applications. The International Journal of High Performance Computing Applications, 2011. Google ScholarDigital Library
- D. Chakrabarti, Y. Zhan, and C. Faloutsos. R-MAT: A recursive model for graph mining. In SDM, 2004.Google ScholarCross Ref
- E. Cohen. Size-estimation framework with applications to transitive closure and reachability. J. Comput. Syst. Sci., 55, December 1997. Google ScholarDigital Library
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms (3. ed.). MIT Press, 2009. Google ScholarDigital Library
- J.-A. Ferrez, K. Fukuda, and T. Liebling. Parallel computation of the diameter of a graph. In HPCSA, 1998.Google ScholarCross Ref
- L. Freeman. A set of measures of centrality based upon betweenness. Sociometry, 1977.Google ScholarCross Ref
- R. Geisberger, P. Sanders, and D. Schultes. Better approximation of betweenness centrality. In ALENEX, 2008.Google ScholarDigital Library
- J. R. Gilbert, S. Reinhardt, and V. B. Shah. A unified framework for numerical and combinatorial computing. Computing in Sciences and Engineering, 10(2), Mar/Apr 2008. Google ScholarDigital Library
- Giraph. "http://giraph.apache.org", 2012.Google Scholar
- J. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin. Power-Graph: Distributed graph-parallel computation on natural graphs. In OSDI, 2012. Google ScholarDigital Library
- Graph500. "http://www.graph500.org", 2012.Google Scholar
- D. Gregor and A. Lumsdaine. The Parallel BGL: A generic library for distributed graph computations. In POOSC, 2005.Google Scholar
- S. Hong, T. Oguntebi, and K. Olukotun. Efficient parallel graph exploration on multi-core CPU and GPU. In PACT, 2011. Google ScholarDigital Library
- S. Hong, H. Chafi, E. Sedlar, and K. Olukotun. Green-Marl: a DSL for easy and efficient graph analysis. In ASPLOS, 2012. Google ScholarDigital Library
- J. Jaja. Introduction to Parallel Algorithms. Addison-Wesley Professional, 1992. Google ScholarDigital Library
- U. Kang, C. E. Tsourakakis, A. P. Appel, C. Faloutsos, and J. Leskovec. Hadi: Mining radii of large graphs. In TKDD, 2011. Google ScholarDigital Library
- U. Kang, C. E. Tsourakakis, and C. Faloutsos. PEGASUS: mining peta-scale graphs. Knowl. Inf. Syst., 27(2), 2011. Google ScholarDigital Library
- H. Kwak, C. Lee, H. Park, and S. Moon. What is Twitter, a social network or a news media? In WWW, 2010. Google ScholarDigital Library
- A. Kyrola, G. Blelloch, and C. Guestrin. GraphChi: Large-scale graph computation on just a PC. In OSDI, 2012. Google ScholarDigital Library
- C. E. Leiserson. The Cilk++ concurrency platform. J. Supercomputing, 51(3), 2010. Springer. Google ScholarDigital Library
- C. E. Leiserson and T. B. Schardl. A work-efficient parallel breadthfirst search algorithm (or how to cope with the nondeterminism of reducers). In SPAA, 2010. Google ScholarDigital Library
- Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein. GraphLab: A new parallel framework for machine learning. In Conference on Uncertainty in Artificial Intelligence, 2010.Google Scholar
- Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein. Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud. PVLDB, 2012. Google ScholarDigital Library
- A. Lugowski, D. Alber, A. Buluç, J. Gilbert, S. Reinhardt, Y. Teng, and A. Waranis. A flexible open-source toolbox for scalable complex graph analysis. In SDM, 2012.Google ScholarCross Ref
- K. Madduri, D. A. Bader, J. W. Berry, and J. R. Crobak. An experimental study of a parallel shortest path algorithm for solving largescale graph instances. In ALENEX, 2007.Google Scholar
- C. Magnien, M. Latapy, and M. Habib. Fast computation of empirically tight bounds for the diameter of massive graphs. J. Exp. Algorithmics, 13, February 2009. Google ScholarDigital Library
- G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In SIGMOD, 2010. Google ScholarDigital Library
- D. Merrill, M. Garland, and A. Grimshaw. Scalable GPU graph traversal. In PPoPP, 2012. Google ScholarDigital Library
- U. Meyer and P. Sanders. ?-stepping: a parallelizable shortest path algorithm. J. Algorithms, 49(1), 2003. Google ScholarDigital Library
- C. R. Palmer, P. B. Gibbons, and C. Faloutsos. ANF: a fast and scalable tool for data mining in massive graphs. In ACM SIGKDD, 2002. Google ScholarDigital Library
- K. Pingali, D. Nguyen, M. Kulkarni, M. Burtscher, M. A. Hassaan, R. Kaleem, T.-H. Lee, A. Lenharth, R. Manevich, M. Mendez-Lojo, D. Prountzos, and X. Sui. The tao of parallelism in algorithms. In PLDI, 2011. Google ScholarDigital Library
- V. Prabhakaran, M.Wu, X.Weng, F. McSherry, L. Zhou, and M. Haridasan. Managing large graphs on multi-cores with graph awareness. In USENIX ATC, 2012. Google ScholarDigital Library
- S. Salihoglu and J.Widom. GPS: A graph processing system. Technical Report InfoLab 1039, Stanford University, 2012.Google Scholar
- J. Shun, G. E. Blelloch, J. T. Fineman, P. B. Gibbons, A. Kyrola, H. V. Simhadri, and K. Tangwongsan. Brief announcement: the Problem Based Benchmark Suite. In SPAA, 2012. Google ScholarDigital Library
- Yahoo! Altavista web page hyperlink connectivity graph, 2012. "http://webscope.sandbox.yahoo.com/catalog.php?datatype=g".Google Scholar
Index Terms
- Ligra: a lightweight graph processing framework for shared memory
Recommendations
Ligra: a lightweight graph processing framework for shared memory
PPoPP '13There has been significant recent interest in parallel frameworks for processing graphs due to their applicability in studying social networks, the Web graph, networks in biology, and unstructured meshes in scientific simulation. Due to the desire to ...
Julienne: A Framework for Parallel Graph Algorithms using Work-efficient Bucketing
SPAA '17: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and ArchitecturesExisting graph-processing frameworks let users develop efficient implementations for many graph problems, but none of them support efficiently bucketing vertices, which is needed for bucketing-based graph algorithms such as \Delta-stepping and ...
L(2,1)-labeling of dually chordal graphs and strongly orderable graphs
An L(2,1)-labeling of a graph G=(V,E) is a function f:V(G)->{0,1,2,...} such that |f(u)-f(v)|>=2 whenever uv@__ __E(G) and |f(u)-f(v)|>=1 whenever u and v are at distance two apart. The span of an L(2,1)-labeling f of G, denoted as SP"2(f,G), is the ...
Comments