research-article

General-purpose join algorithms for large graph triangle listing on heterogeneous systems

Authors:

Sudhakar YalamanchiliAuthors Info & Claims

GPGPU '16: Proceedings of the 9th Annual Workshop on General Purpose Processing using Graphics Processing Unit

Pages 12 - 21

https://doi.org/10.1145/2884045.2884054

Published: 12 March 2016 Publication History

Abstract

We investigate applying general-purpose join algorithms to the triangle listing problem on heterogeneous systems that feature a multi-core CPU and multiple GPUs. In particular, we consider an out-of-core context where graph data are available on secondary storage such as a solid-state disk (SSD) and may not fit in the CPU main memory or GPU device memory. We focus on Leapfrog Triejoin (LFTJ), a recently proposed, worst-case optimal algorithm and present "boxing": a novel yet conceptually simple approach for partitioning and feeding out-of-core input data to LFTJ. The "boxing" algorithm integrates well with a GPU-Optimized LFTJ algorithm for triangle listing. We achieve significant performance gains on a heterogeneous system comprised of GPUs and CPU by utilizing the massive-parallel computation capability of GPUs. Our experimental evaluations on real-world and synthetic data sets (some of which containing more than 1.2 billion edges) show that out-of-core LFTJ is competitive with specialized graph algorithms for triangle listing. By using one or two GPUs, we achieve additional speedups on the same graphs.

References

[1]

A. Atserias, M. Grohe, and D. Marx. Size bounds and query plans for relational joins. In FOCS'08, pages 739--748. IEEE, 2008.

Digital Library

[2]

S. Baxter. Modern gpu. http://nvlabs.github.io/moderngpu/, 2013.

[3]

D. Chakrabarti, Y. Zhan, and C. Faloutsos. R-MAT: A recursive model for graph mining. In SDM, volume 4, pages 442--446. SIAM, 2004.

[4]

S. Chu and J. Cheng. Triangle listing in massive networks and its applications. In SIGKDD, pages 672--680. ACM, 2011.

Digital Library

[5]

R. Dementiev. Algorithm engineering for large data sets. PhD thesis, Saarland University, 2006.

[6]

G. Diamos, H. Wu, J. Wang, A. Lele, and S. Yalamanchili. Relational algorithms for multi-bulk-synchronous processors. PPoPP '13, pages 301--302, 2013.

Digital Library

[7]

X. Hu, Y. Tao, and C.-W. Chung. Massive graph triangulation. In SIGMOD, pages 325--336. ACM, 2013.

Digital Library

[8]

M. A. Khamis, H. Q. Ngo, C. Ré, and A. Rudra. A resolution-based framework for joins: Worst-case and beyond. CoRR, abs/1404.0703, 2014.

[9]

H. Kwak, C. Lee, H. Park, and S. Moon. What is Twitter, a social network or a news media? In WWW '10, pages 591--600, New York, NY, USA, 2010. ACM.

Digital Library

[10]

Y. Low, D. Bickson, J. Gonzalez, C. Guestrin, A. Kyrola, and J. M. Hellerstein. Distributed graphlab: A framework for machine learning and data mining in the cloud. Proc. VLDB Endow., 5(8):716--727, Apr. 2012.

Digital Library

[11]

B. Menegola. An external memory algorithm for listing triangles. Technical report, Universidade Federal do Rio Grande do Sul, 2010.

[12]

A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee. Measurement and Analysis of Online Social Networks. In IMC'07, San Diego, CA, October 2007.

Digital Library

[13]

H. Q. Ngo, D. T. Nguyen, C. Ré, and A. Rudra. Beyond worst-case analysis for joins with minesweeper. CoRR, abs/1302.0914, 2014.

Digital Library

[14]

H. Q. Ngo, E. Porat, C. Ré, and A. Rudra. Worst-case optimal join algorithms:{extended abstract}. In PODS, pages 37--48. ACM, 2012.

Digital Library

[15]

R. Pagh and F. Silvestri. The input/output complexity of triangle enumeration. In PODS'14, pages 224--233, 2014.

Digital Library

[16]

G. Palla, I. Derényi, I. Farkas, and T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043):814--818, 2005.

[17]

J. W. Raymond, E. J. Gardiner, and P. Willett. Rascal: Calculation of graph similarity using maximum common edge subgraphs. The Computer Journal, 45(6):631--644, 2002.

[18]

N. Rhodes, P. Willett, A. Calvet, J. B. Dunbar, and C. Humblet. Clip: similarity searching of 3d databases using clique detection. Journal of chemical information and computer sciences, 43(2):443--448, 2003.

[19]

T. Schank. Algorithmic aspects of triangle-based network analysis. Phd in computer science, University Karlsruhe, 2007.

[20]

J. Seo, J. Park, J. Shin, and M. S. Lam. Distributed socialite: a datalog-based language for large-scale graph analysis. Proceedings of the VLDB Endowment, 6(14):1906--1917, 2013.

Digital Library

[21]

T. L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In ICDT, pages 96--106, 2014.

[22]

H. Wu, G. Diamos, T. Sheard, M. Aref, S. Baxter, M. Garland, and S. Yalamanchili. Red fox: An execution environment for relational query processing on gpus. CGO '14, pages 44:44--44:54, 2014.

Digital Library

[23]

H. Wu, G. Diamos, J. Wang, S. Cadambi, S. Yalamanchili, and S. Chakradhar. Optimizing data warehousing applications for gpus using kernel fusion/fission. In PLC, IPDPSW '12, pages 2433--2442, 2012.

Digital Library

[24]

H. Wu, D. Zinn, M. Aref, and S. Yalamanchili. Multipredicate join algorithms for accelerating relational graph processing on GPUs. ADMS 2014, September 2014.

[25]

J. Yang and J. Leskovec. Defining and evaluating network communities based on ground-truth. CoRR, abs/1205.6233, 2012.

Digital Library

[26]

D. Zinn. General-purpose join algorithms for listing triangles in large graphs. CoRR, abs/1501.06689, 2015.

Cited By

DOVIER AFORMISANO AGUPTA GHERMENEGILDO MPONTELLI EROCHA R(2022)Parallel Logic Programming: A SequelTheory and Practice of Logic Programming10.1017/S147106842200005922:6(905-973)Online publication date: 28-Mar-2022
https://doi.org/10.1017/S1471068422000059
Lai ZSun XLuo QXie X(2021)Accelerating multi-way joins on the GPUThe VLDB Journal10.1007/s00778-021-00708-y31:3(529-553)Online publication date: 2-Nov-2021
https://doi.org/10.1007/s00778-021-00708-y
Kumar SGilray T(2020)Load-Balancing Parallel Relational AlgebraHigh Performance Computing10.1007/978-3-030-50743-5_15(288-308)Online publication date: 15-Jun-2020
https://doi.org/10.1007/978-3-030-50743-5_15
Show More Cited By

Index Terms

General-purpose join algorithms for large graph triangle listing on heterogeneous systems
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Parallel and distributed DBMSs
        Relational parallel and distributed DBMSs
2. Theory of computation
  1. Design and analysis of algorithms
    1. Parallel algorithms
      1. Massively parallel algorithms
  2. Theory and algorithms for application domains
    1. Database theory
      1. Data structures and algorithms for data management

Recommendations

A performance study of general-purpose applications on graphics processors using CUDA

Graphics processors (GPUs) provide a vast number of simple, data-parallel, deeply multithreaded cores and high memory bandwidths. GPU architectures are becoming increasingly programmable, offering the potential for dramatic speedups for a variety of ...
Accelerating CUDA graph algorithms at maximum warp
PPoPP '11

Graphs are powerful data representations favored in many computational domains. Modern GPUs have recently shown promising results in accelerating computationally challenging graph problems but their performance suffered heavily when the graph structure ...
Accelerating CUDA graph algorithms at maximum warp
PPoPP '11: Proceedings of the 16th ACM symposium on Principles and practice of parallel programming

Graphs are powerful data representations favored in many computational domains. Modern GPUs have recently shown promising results in accelerating computationally challenging graph problems but their performance suffered heavily when the graph structure ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

GPGPU '16: Proceedings of the 9th Annual Workshop on General Purpose Processing using Graphics Processing Unit

March 2016

107 pages

ISBN:9781450341950

DOI:10.1145/2884045

Conference Chairs:
David Kaeli,
John Cavazos

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 March 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation (NSF)

Conference

PPoPP '16

PPoPP '16: 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

March 12, 2016

Barcelona, Spain

Acceptance Rates

GPGPU '16 Paper Acceptance Rate 9 of 23 submissions, 39%;

Overall Acceptance Rate 57 of 129 submissions, 44%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
217
Total Downloads

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

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

DOVIER AFORMISANO AGUPTA GHERMENEGILDO MPONTELLI EROCHA R(2022)Parallel Logic Programming: A SequelTheory and Practice of Logic Programming10.1017/S147106842200005922:6(905-973)Online publication date: 28-Mar-2022
https://doi.org/10.1017/S1471068422000059
Lai ZSun XLuo QXie X(2021)Accelerating multi-way joins on the GPUThe VLDB Journal10.1007/s00778-021-00708-y31:3(529-553)Online publication date: 2-Nov-2021
https://doi.org/10.1007/s00778-021-00708-y
Kumar SGilray T(2020)Load-Balancing Parallel Relational AlgebraHigh Performance Computing10.1007/978-3-030-50743-5_15(288-308)Online publication date: 15-Jun-2020
https://doi.org/10.1007/978-3-030-50743-5_15
Gilray TKumar S(2019)Distributed Relational Algebra at Scale2019 IEEE 26th International Conference on High Performance Computing, Data, and Analytics (HiPC)10.1109/HiPC.2019.00014(12-22)Online publication date: Dec-2019
https://doi.org/10.1109/HiPC.2019.00014

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents