More Web Proxy on the site http://driver.im/

research-article

Free access

Parallel graph analytics

Authors:

Andrew Lenharth,

Keshav PingaliAuthors Info & Claims

Communications of the ACM, Volume 59, Issue 5

Pages 78 - 87

https://doi.org/10.1145/2901919

Published: 26 April 2016 Publication History

All formats PDF

Abstract

Data-centric abstractions and execution strategies are needed to exploit parallelism in large-scale graph analytics.

Supplementary Material

p78-lenharth.pdf (516capingalisourcematerial.pdf)

Supplemental text.

Download
50.10 KB

References

[1]

Azad, A., Buluc, A., and Gilbert, J.R. Parallel triangle counting and enumeration using matrix algebra. In Proceedings of the 29^th International Parallel & Distributed Processing Symposium Workshop (Hyderabad, India, May 25--29). IEEE International, 2015, 804--811.

Digital Library

[2]

Bader, D.A. and Madduri, K. Designing multithreaded algorithms for breadth-first search and st-connectivity on the Cray MTA-2. In Proceedings of the 2006 International Conference on Parallel Processing (Columbus, OH, Aug. 14-18). IEEE Computer Society Press, 2006, 523--530.

Digital Library

[3]

Bertsekas, D.P. and Tsitsiklis, J.N. Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, Inc., Upper Saddle River, NJ, 1989.

Digital Library

[4]

Buluç, A. and Gilbert, J.R. The combinatorial BLAS: Design, implementation, and applications. International Journal of High Performance Computing Applications 25, 4 (Nov. 2011), 496--509.

Digital Library

[5]

Cormen, T., Leiserson, C., Rivest, R., and Stein, C., Eds. Introduction to Algorithms. MIT Press, Cambridge, MA, 2001.

Digital Library

[6]

Delling, D., Goldberg, A.V., Nowatzyk, A., and Werneck, R.F. Phast: Hardware-accelerated shortest path trees. In Proceedings of the 25^th International Parallel and Distributed Processing Symposium (Anchorage, AK, May 16--20). IEEE Computer Society Press, 2011, 921--931.

Digital Library

[7]

Fernholz, D. and Ramachandran, V. The diameter of sparse random graphs. Random Structures & Algorithms 31, 4 (Dec. 2007), 482--516.

Digital Library

[8]

Giraph; http://giraph.apache.org/

[9]

Gonzalez, J.E., Low, Y., Gu, H., Bickson, D., and Guestrin, C. PowerGraph: Distributed graph-parallel computation on natural graphs. In Proceedings of the USENIX Conference on Operating Systems Design and Implementation (Hollywood, CA, Oct. 8--10). USENIX Association, Berkeley, CA, 2012, 17--30.

Digital Library

[10]

Harish, P. and Narayanan, P.J. Accelerating large graph algorithms on the GPU using CUDA. In Proceedings of the 14^th International Conference on High Performance Computing (Goa, India, Dec. 19--22). Springer-Verlag, Berlin, Heidelberg, 2007, 197--208.

Digital Library

[11]

Herlihy, M. and Shavit, N. The Art of Multiprocessor Programming. Morgan-Kaufmann, San Francisco, CA, 2012.

Digital Library

[12]

Hong, S., Chaf, H., Sedlar, E., and Olukotun, K. Green-Marl: A DSL for easy and efficient graph analysis. In Proceedings of the 17^th International Conference on Architectural Support for Programming Languages and Operating Systems (London, U.K., Mar. 3--7). ACM Press, New York, 2012, 349--362.

Digital Library

[13]

JaJa, J. An Introduction to Parallel Algorithms. Addison-Wesley, Reading, MA, 1992.

Digital Library

[14]

Karp, R.M. and Ramachandran, V. A Survey of Parallel Algorithms for Shared-Memory Machines, Technical Report UCB/CSD-88-408. EECS Department, University of California, Berkeley, Mar. 1988; http://www.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-408.pdf

[15]

Khorasani, K., Vora, K., Gupta, R., and Bhuyan, L.N. Cusha: Vertex-centric graph processing on GPUs. In Proceedings of the 23^rd International Symposium on High-performance Parallel and Distributed Computing (Vancouver, Canada, June 23--27). ACM Press, New York, 2014, 239--252.

Digital Library

[16]

Kim, J. and Batten, C. Accelerating irregular algorithms on GPGPUs using fine-grain hardware worklists. In Proceedings of the 47^th Annual IEEE/ACM International Symposium on Microarchitecture (Cambridge, U.K., Dec. 13--17). IEEE Computer Society Press, 2014, 75--87.

Digital Library

[17]

Kulkarni, M., Burtscher, M., Casçaval, C., and Pingali, K. Lonestar: A suite of parallel irregular programs. In Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software (Boston, MA, Apr. 26--28). IEEE Computer Society Press, 2009; http://iss.ices.utexas.edu/?p=projects/galois/lonestar

[18]

Kulkarni, M., Nguyen, D., Prountzos, D., Sui, X., and Pingali, K. Exploiting the commutativity lattice. In Proceedings of the 32^nd ACM SIGPLAN Conference on Programming Language Design and Implementation (San Jose, CA, June 4--8). ACM Press, New York, 2011, 542--555.

Digital Library

[19]

Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tompkins, A., and Upfal, E. The Web as a graph. In Proceedings of the 19^th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (Dallas, TX, May 15--17). ACM Press, New York, 2000, 1--10.

Digital Library

[20]

Low, Y., Gonzalez, J., Kyrola, A., Bickson, D., Guestrin, C., and Hellerstein, J.M. GraphLab: A new parallel framework for machine learning. In Proceedings of the 26^th Conference on Uncertainty in Artificial Intelligence (Catalina Island, CA, July 8--11). Association for Uncertainty in Artificial Intelligence, 2010.

[21]

Lu, L. The diameter of random massive graphs. In Proceedings of the 12^th Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, Jan. 9--11). Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001, 912--921.

Digital Library

[22]

Madduri, K., Feo, J., Cong, G., and Bader, D.A. Design of multithreaded algorithms for combinatorial problems. Chapter 31 in Handbook of Parallel Computing: Models, Algorithms and Applications, S. Rajasekaran and J. Reif, Eds. Chapman and Hall/CRC, Boca Raton, FL, 2007.

[23]

Malewicz, G., Austern, M.H., Bik, A.J., Dehnert, J.C., Horn, I., Leiser, N., and Czajkowski, G. Pregel: A system for large-scale graph processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data (Indianapolis, IN, June 6--11). ACM Press, New York, 2010, 135--146.

Digital Library

[24]

Merrill, D., Garland, M., and Grimshaw, A. Scalable GPU graph traversal. SIGPLAN Notices 47, 8 (Feb. 2012), 117--128.

Digital Library

[25]

Meyer, U. and Sanders, P. Delta-stepping: A parallel single-source shortest-path algorithm. In Proceedings of the Sixth Annual European Symposium on Algorithms (Venice, Italy, Aug. 24--26). Springer-Verlag, London, U.K., 1998, 393--404.

Digital Library

[26]

Nasre, R., Burtscher, M., and Pingali, K. Morph algorithms on GPUs. In Proceedings of the 18^th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Shenzhen, China, Feb. 23--27). ACM Press, New York, 2013, 147--156.

Digital Library

[27]

Nguyen, D., Lenharth, A., and K. Pingali. A lightweight infrastructure for graph analytics. In Proceedings of the 24^th ACM Symposium on Operating Systems Principles (Farmington, PA, Nov. 3--6). ACM Press, New York, 2013, 456--471.

Digital Library

[28]

Nguyen, D., Lenharth, A., and Pingali, K. Deterministic Galois: On-demand, portable and parameterless. In Proceedings of the 19^th International Conference on Architectural Support for Programming Languages and Operating Systems (Salt Lake City, UT, Mar. 1--5). ACM Press, New York, 2014, 499--512.

Digital Library

[29]

Pingali, K., Nguyen, D., Kulkarni, M., Burtscher, M., Hassaan, M.A., Kaleem, R., Lee, T.-H., Lenharth, A., Manevich, R., Méndez-Lojo, M., Prountzos, D., and Sui, X. The Tao of parallelism in algorithms. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (San Jose, CA, June 4--8). ACM Press, New York, 2011, 12--25.

Digital Library

[30]

Prountzos, D., Manevich, R., and Pingali, K. Synthesizing parallel graph programs via automated planning. In Proceedings of the 36^th Annual SIGPLAN Conference on Programming Language Design and Implementation (Portland, OR, June 13--17). ACM Press, New York, 2015, 533--544.

Digital Library

[31]

Rauchwerger, L. and Padua, D.A. The LRPD test: Speculative runtime parallelization of loops with privatization and reduction parallelization. IEEE Transactions on Parallel Distributed Systems 10, 2 (Feb. 1999), 160--180.

Digital Library

[32]

Satish, N., Sundaram, N., Patwary, M.M.A., Seo, J., Park, J., Hassaan, M.A., Sengupta, S., Yin, Z., and Dubey, P. Navigating the maze of graph analytics frameworks using massive graph datasets. In Proceedings of the ACM SIGMOD International Conference on Management of Data (Snowbird, UT, June 22--27). ACM Press, New York, 2014, 979--990.

Digital Library

[33]

Shun, J. and Blelloch, G.E. Ligra: A lightweight graph-processing framework for shared memory. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Shenzhen, China, Feb. 23--27). ACM Press, New York, 2013, 135--146.

Digital Library

[34]

Shun, J., Blelloch, G.E., Fineman, J.T., Gibbons, P.B., Kyrola, A., Simhadri, H.V., and Tangwongsan, K. Brief announcement: The problem-based benchmark suite. In Proceedings of the 24^th Annual ACM Symposium on Parallelism in Algorithms and Architectures (Pittsburgh, PA, June 25--27). ACM Press, New York, 2012, 68--70.

Digital Library

[35]

Siek, J., Lee, L.-Q., and Lumsdaine, A. The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley, Reading, MA, 2001.

[36]

Ugander, J., Karrer, B., Backstrom, L., and Marlow, C. The Anatomy of the Facebook Social Graph. Technical Report, 2011; http://arxiv.org/abs/1111.4503

[37]

Valiant, L.G. A bridging model for parallel computation. Commun. ACM 33, 8 (Aug. 1990), 103--111.

Digital Library

[38]

Xin, R.S., Gonzalez, J.E., Franklin, M.J., and Stoica, I. GraphX: A resilient distributed graph system on Spark. In Proceedings of the First International Workshop on Graph Data Management Experiences and Systems (New York, June 22--27). ACM Press, New York, 2013.

Digital Library

Cited By

Lee HDathathri RPingali KTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Kimbap: A Node-Property Map System for Distributed Graph AnalyticsProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3620665.3640421(566-581)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620665.3640421
Choudhury DBarik RRajam AKalyanaraman APande P(2022)Software/Hardware Co-design of 3D NoC-based GPU Architectures for Accelerated Graph ComputationsACM Transactions on Design Automation of Electronic Systems10.1145/351435427:6(1-22)Online publication date: 27-Jun-2022
https://dl.acm.org/doi/10.1145/3514354
Ma XZhao TGuo QLi XZhang C(2022)Fuzzy hypergraph network for recommending top-K profitable stocksInformation Sciences: an International Journal10.1016/j.ins.2022.09.010613:C(239-255)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.ins.2022.09.010
Show More Cited By

Index Terms

Parallel graph analytics

Recommendations

Big Graph Analytics Systems
SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data

In recent years we have witnessed a surging interest in developing Big Graph processing systems. To date, tens of Big Graph systems have been proposed. This tutorial provides a timely and comprehensive review of existing Big Graph systems, and ...
Parallel graph partitioning on multicore architectures
LCPC'10: Proceedings of the 23rd international conference on Languages and compilers for parallel computing

Graph partitioning is a common and frequent preprocessing step in many high-performance parallel applications on distributed-and shared-memory architectures. It is used to distribute graphs across memory and to improve spatial locality. There are ...
Systems for Big Graph Analytics

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 59, Issue 5

May 2016

121 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/2930840

Editor:
Moshe Y. Vardi
Association for Computing Machinery, New York, NY

Issue’s Table of Contents

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 ACM 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: 26 April 2016

Published in CACM Volume 59, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Popular
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
8,596
Total Downloads

Downloads (Last 12 months)245
Downloads (Last 6 weeks)16

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lee HDathathri RPingali KTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Kimbap: A Node-Property Map System for Distributed Graph AnalyticsProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3620665.3640421(566-581)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620665.3640421
Choudhury DBarik RRajam AKalyanaraman APande P(2022)Software/Hardware Co-design of 3D NoC-based GPU Architectures for Accelerated Graph ComputationsACM Transactions on Design Automation of Electronic Systems10.1145/351435427:6(1-22)Online publication date: 27-Jun-2022
https://dl.acm.org/doi/10.1145/3514354
Ma XZhao TGuo QLi XZhang C(2022)Fuzzy hypergraph network for recommending top-K profitable stocksInformation Sciences: an International Journal10.1016/j.ins.2022.09.010613:C(239-255)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.ins.2022.09.010
Kılıç BÖzturan CSen A(2022)Parallel analysis of Ethereum blockchain transaction data using cluster computingCluster Computing10.1007/s10586-021-03511-025:3(1885-1898)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1007/s10586-021-03511-0
Liu LWei SZhu JDeng CLiu LWei SZhu JDeng C(2022)Current Application FieldsSoftware Defined Chips10.1007/978-981-19-7636-0_4(167-277)Online publication date: 15-Nov-2022
https://doi.org/10.1007/978-981-19-7636-0_4
Ghosh STallent NMinutoli MHalappanavar MPeri RKalyanaraman Ade Supinski BHall MGamblin T(2021)Single-node partitioned-memory for huge graph analyticsProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3458817.3476156(1-14)Online publication date: 14-Nov-2021
https://dl.acm.org/doi/10.1145/3458817.3476156
Kaushik APekhimenko GPatel H(2021)GretchACM Transactions on Architecture and Code Optimization10.1145/343980318:2(1-25)Online publication date: 9-Feb-2021
https://dl.acm.org/doi/10.1145/3439803
Ataei SHua WYang YManohar RLu YHe JMaleki SPingali K(2021)An Open-Source EDA Flow for Asynchronous LogicIEEE Design & Test10.1109/MDAT.2021.305133438:2(27-37)Online publication date: Apr-2021
https://doi.org/10.1109/MDAT.2021.3051334
Dadu VLiu SNowatzki TMartínez JDuato JJohn L(2021)PolyGraphProceedings of the 48th Annual International Symposium on Computer Architecture10.1109/ISCA52012.2021.00053(595-608)Online publication date: 14-Jun-2021
https://dl.acm.org/doi/10.1109/ISCA52012.2021.00053
Sun WLi ZYin SWei SLiu LMartínez JDuato JJohn L(2021)ABC-DIMMProceedings of the 48th Annual International Symposium on Computer Architecture10.1109/ISCA52012.2021.00027(237-250)Online publication date: 14-Jun-2021
https://dl.acm.org/doi/10.1109/ISCA52012.2021.00027
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Digital Edition

View this article in digital edition.

Digital Edition

Magazine Site

View this article on the magazine site (external)

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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents