Article

Managing large graphs on multi-cores with graph awareness

Authors:

Vijayan Prabhakaran,

Frank McSherry,

Maya HaridasanAuthors Info & Claims

USENIX ATC'12: Proceedings of the 2012 USENIX conference on Annual Technical Conference

Page 4

Published: 13 June 2012 Publication History

Abstract

Grace is a graph-aware, in-memory, transactional graph management system, specifically built for real-time queries and fast iterative computations. It is designed to run on large multi-cores, taking advantage of the inherent parallelism to improve its performance. Grace contains a number of graph-specific and multi-core-specific optimizations including graph partitioning, careful in-memory vertex ordering, updates batching, and load-balancing. It supports queries, searches, iterative computations, and transactional updates. Grace scales to large graphs (e.g., a Hotmail graph with 320 million vertices) and performs up to two orders of magnitude faster than commercial key-value stores and graph databases.

References

[1]

BerkeleyDB. http://www.oracle.com/ technetwork/database/berkeleydb/ overview/index.html.

[2]

Clueweb09. http://lemurproject.org/ clueweb09/.

[3]

CodeAnalyst. http://developer.amd.com/ tools/codeanalyst/Pages/default.aspx.

[4]

Hadoop. http://hadoop.apache.org/.

[5]

METIS. http://glaros.dtc.umn.edu/ gkhome/metis/metis/overview.

[6]

Neo4j. http://neo4j.org.

[7]

VTune. http://software.intel.com/en-us/ articles/intel-vtune-amplifier-xe/.

[8]

V. Agarwal, F. Petrini, D. Pasetto, and D. A. Bader. Scalable graph exploration on multicore processors. In Proceedings of the 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis, SC '10, pages 1-11, Washington, DC, USA, 2010. IEEE Computer Society.

[9]

K. Bharat, A. Broder, M. Henzinger, P. Kumar, and S. Venkatasubramanian. The connectivity server: fast access to linkage information on the Web. In Proceedings of the 7th international conference on World Wide Web 7, pages 469-477, 1998.

[10]

S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Computer Networks, 30(1-7): 107-117, 1998.

[11]

G. Cong and K. Makarychev. Optimizing large-scale graph analysis on a multi-threaded, multi-core platform. In IPDPS, pages 688-697, 2011.

[12]

J. Dean and S. Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. In OSDI'04, pages 137-150, 2004.

[13]

A. A. Diwan, S. Rane, S. Seshadri, and S. Sudarshan. Clustering techniques for minimizing external path length. In VLDB'96, September 3-6, Mumbai (Bombay), India, pages 342-353, 1996.

[14]

D. Gregor and A. Lumsdaine. Lifting sequential graph algorithms for distributed-memory parallel computation. In OOPSLA'05, pages 423-437, New York, NY, USA, 2005. ACM.

[15]

D. Gregor and A. Lumsdaine. The parallel bgl: A generic library for distributed graph computations. In In Parallel Object-Oriented Scientific Computing (POOSC'05), 2005.

[16]

S. Hong, T. Oguntebi, and K. Olukotun. Efficient parallel graph exploration on multi-core cpu and gpu. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques, PACT'11, pages 78-88, 2011.

[17]

Imranul Hoque and Indranil Gupta. Social Network-Aware Disk Management. Technical report, University of Illinois at Urbana-Champaign, 2010-12-03.

[18]

G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput., 20:359-392, December 1998.

[19]

G. Karypis, V. Kumar, and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 48:96-129, 1998.

[20]

Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. Hellerstein. GraphLab: A new parallel framework for machine learning. In Conference on Uncertainty in Artificial Intelligence, 2010.

[21]

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'10, pages 135-146, New York, NY, USA, 2010. ACM.

[22]

Y. Mao, E. Kohler, and R. T. Morris. Cache craftiness for fast multicore key-value storage. In EuroSys'12, Bern, Switzerland, pages 183-196, 2012.

[23]

F. McSherry, R. Isaacs, M. Isard, and D. G. Murray. Naiad: The animating spirit of rivers and streams. Poster Session of Symposium on Operating Systems Principles (SOSP'11), 2011.

[24]

A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee. Measurement and analysis of online social networks. In Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, IMC '07, pages 29-42, New York, NY, USA, 2007. ACM.

[25]

M. Najork. The scalable hyperlink store. In Proceedings of the 20th ACM conference on Hypertext and Hypermedia, pages 89-98, 2009.

[26]

J. Nelson, B. Myers, A. H. Hunter, P. Briggs, L. Ceze, C. Ebeling, D. Grossman, S. Kahan, and M. Oskin. Crunching large graphs with commodity processors. In Proceedings of the 3rd USENIX conference on Hot topic in parallelism, HotPar'11, pages 10-10, Berkeley, CA, USA, 2011. USENIX Association.

[27]

J. M. Pujol, V. Erramilli, G. Siganos, X. Yang, N. Laoutaris, P. Chhabra, and P. Rodriguez. The Little Engine(s) That Could: Scaling Online Social Networks. In SIGCOMM'10, New Delhi, India, Aug. 2010.

[28]

C. Ranger, R. Raghuraman, A. Penmetsa, G. Bradski, and C. Kozyrakis. Evaluating mapreduce for multi-core and multiprocessor systems. In HPCA'07, pages 13-24. IEEE Computer Society, 2007.

[29]

D. A. Spielman and S.-H. Teng. Spectral partitioning works: Planar graphs and finite element meshes. In FOCS, pages 96-105, 1996.

[30]

L. G. Valiant. A bridging model for parallel computation. Commun. ACM, 33:103-111, August 1990.

[31]

G. Weikum and G. Vossen. Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery. Morgan Kaufmann, 2009.

[32]

Y. Yu, M. Isard, D. Fetterly, M. Budiu, U. Erlingsson, P. K. Gunda, and J. Currey. DryadLINQ: A System for General-Purpose Distributed Data-Parallel Computing Using a High-Level Language. In OSDI'08, San Diego, California, pages 1-14, 2008.

Cited By

Zheng RPai SLee J(2021)Efficient execution of graph algorithms on CPU with SIMD extensionsProceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO51591.2021.9370326(262-276)Online publication date: 27-Feb-2021
https://dl.acm.org/doi/10.1109/CGO51591.2021.9370326
Brahmakshatriya AZhang YHong CKamil SShun JAmarasinghe SLee J(2021)Compiling graph applications for GPUs with graphitProceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO51591.2021.9370321(248-261)Online publication date: 27-Feb-2021
https://dl.acm.org/doi/10.1109/CGO51591.2021.9370321
Ma LYang ZMiao YXue JWu MZhou LDai YDan TDahlia M(2019)NeugraphProceedings of the 2019 USENIX Conference on Usenix Annual Technical Conference10.5555/3358807.3358845(443-457)Online publication date: 10-Jul-2019
https://dl.acm.org/doi/10.5555/3358807.3358845
Show More Cited By

Managing large graphs on multi-cores with graph awareness

Recommendations

Large Induced Forests in Graphs

In this article, we prove three theorems. The first is that every connected graph of order n and size m has an induced forest of order at least 8n-2m-2/9 with equality if and only if such a graph is obtained from a tree by expanding every vertex to a ...
Building large k-cores from sparse graphs
Abstract
A k-core of a graph G is the maximal induced subgraph in which every vertex has degree at least k. In the Edge k -Core optimization problem, we are given a graph G and integers k, b and p. The task is to ...
Connectivity of k-extendable graphs with large k
Discrete mathematics and theoretical computer science (DMTCS)

Let G be a simple connected graph on 2n vertices with perfect matching. For a given positive integer k (0 ≤ k ≤ n - 1), G is k-extendable if any matching of size k in G is contained in a perfect matching of G. It is proved that if G is a k-extendable ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

USENIX ATC'12: Proceedings of the 2012 USENIX conference on Annual Technical Conference

June 2012

41 pages

Publisher

USENIX Association

United States

Publication History

Published: 13 June 2012

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

41
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zheng RPai SLee J(2021)Efficient execution of graph algorithms on CPU with SIMD extensionsProceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO51591.2021.9370326(262-276)Online publication date: 27-Feb-2021
https://dl.acm.org/doi/10.1109/CGO51591.2021.9370326
Brahmakshatriya AZhang YHong CKamil SShun JAmarasinghe SLee J(2021)Compiling graph applications for GPUs with graphitProceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO51591.2021.9370321(248-261)Online publication date: 27-Feb-2021
https://dl.acm.org/doi/10.1109/CGO51591.2021.9370321
Ma LYang ZMiao YXue JWu MZhou LDai YDan TDahlia M(2019)NeugraphProceedings of the 2019 USENIX Conference on Usenix Annual Technical Conference10.5555/3358807.3358845(443-457)Online publication date: 10-Jul-2019
https://dl.acm.org/doi/10.5555/3358807.3358845
Liu HHuang HDan TDahlia M(2019)SIMD-XProceedings of the 2019 USENIX Conference on Usenix Annual Technical Conference10.5555/3358807.3358843(411-427)Online publication date: 10-Jul-2019
https://dl.acm.org/doi/10.5555/3358807.3358843
Dhulipala LBlelloch GShun JMcKinley KFisher K(2019)Low-latency graph streaming using compressed purely-functional treesProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314598(918-934)Online publication date: 8-Jun-2019
https://dl.acm.org/doi/10.1145/3314221.3314598
Abbas ZKalavri VCarbone PVlassov V(2018)Streaming graph partitioningProceedings of the VLDB Endowment10.14778/3236187.323620811:11(1590-1603)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.14778/3236187.3236208
Zhang YYang MBaghdadi RKamil SShun JAmarasinghe S(2018)GraphIt: a high-performance graph DSLProceedings of the ACM on Programming Languages10.1145/32764912:OOPSLA(1-30)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276491
Grossman SLitz HKozyrakis C(2018)Making pull-based graph processing performantACM SIGPLAN Notices10.1145/3200691.317850653:1(246-260)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3200691.3178506
Grossman SLitz HKozyrakis CKrall AGross T(2018)Making pull-based graph processing performantProceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3178487.3178506(246-260)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3178487.3178506
Davoudian AChen LLiu M(2018)A Survey on NoSQL StoresACM Computing Surveys10.1145/315866151:2(1-43)Online publication date: 17-Apr-2018
https://dl.acm.org/doi/10.1145/3158661
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents