Tumbling Down the GraphBLAS Rabbit Hole with SHMEM | SpringerLink
Skip to main content
Springer Nature Link
Log in

Tumbling Down the GraphBLAS Rabbit Hole with SHMEM

  • Conference paper
  • First Online:
OpenSHMEM and Related Technologies. OpenSHMEM in the Era of Extreme Heterogeneity (OpenSHMEM 2018)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 11283))

Included in the following conference series:

Abstract

In this paper we present shgraph, a SHMEM implementation of the GraphBLAS standard, which enables the user to redefine complex graph algorithms in terms of simple linear algebra primitives. GraphBLAS offers many nice features such as type abstractions, the ability to perform generalized matrix/vector operations over a semiring, and executing graph operations out-of-order (non-blocking mode).

shgraph seeks to efficiently manage and process billion-edge or greater sparse graphs on an HPC system. We walk through sample GraphBLAS code and discuss the shgraph development process. In particular, we explain how SHMEM was used and where it was necessary to tweak the GraphBLAS specification to be compatible with a distributed system. Additionally, we analyze some preliminary performance results, map out next steps, and suggest potential applications.

Supported by the US Department of Defense.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Buluç, A., Mattson, T., McMillan, S., Moreira, J., Yang, C.: The GraphBLAS C API specification. https://people.eecs.berkeley.edu/~aydin/GraphBLAS_API_C.pdf. Accessed 6 July 2018

  2. Buluç, A., Mattson, T., McMillan, S., Moreira, J., Yang, C.: Design of the GraphBLAS API for C. In: 2017 IEEE International Parallel and Distributed Processing Symposium Workshops, pp. 643–652. IEEE, Orlando (2017)

    Google Scholar 

  3. Kepner, J.: GraphBLAS Mathematics - Provisional Release 1.0 -. https://www.mit.edu/~kepner/GraphBLAS/GraphBLAS-Math-release.pdf. Accessed 6 July 2018

  4. Buluç, A., Gilbert, J.R., Shah, V.B.: Implementing sparse matrices for graph algorithms. SIAM J. Sci. Comput. 22, 287–314 (2011)

    MathSciNet  MATH  Google Scholar 

  5. Dunbar, R.I.M.: Neocortex size as a constraint on group size in primates. J. Hum. Evol. 22(6), 469–493 (1992)

    Article  Google Scholar 

  6. Lawson, C.L., Hanson, R.J., Kincaid, D.R., Krough, F.T.: Basic linear algebra subprograms for FORTRAN usage. ACM Trans. Math. Softw. 5(2), 308–323 (1979)

    Article  Google Scholar 

  7. Duff, I., Heroux, M., Pozo, R.: An overview of the sparse basic linear algebra subprograms: the new standard from the BLAS technical forum. ACM Trans. Math. Softw. 28(2), 239–267 (2002)

    Article  MathSciNet  Google Scholar 

  8. OpenSHMEM application programming interface. http://www.openshmem.org/site/sites/default/site_files/OpenSHMEM-1.3.pdf. Accessed 6 July 2018

  9. Gilbert, J.R., Reinhardt, S., Shah, V.B.: Distributed sparse matrices for very high level languages. Adv. Comput. 72, 225–252 (2008)

    Article  Google Scholar 

  10. Buluç, A., Gilbert, J.R.: Challenges and advances in parallel sparse matrix-matrix multiplication. In: 2008 37th International Conference on Parallel Processing, pp. 503–510. IEEE, Portland (2008)

    Google Scholar 

  11. Buluç, A., Gilbert, J.R.: On the representation and multiplication of hyperspace matrices. In: 2008 IEEE International Symposium on Parallel and Distributed Processing, IEEE, Miami (2008)

    Google Scholar 

  12. Lidl, R., Mullen, G.L.: When does a polynomial over a finite field permute the elements of that field? Am. Math. Mon. 25(3), 243–246 (1998)

    Article  Google Scholar 

  13. Buluç, A., Gilbert, J.R.: Parallel sparse matrix-matrix multiplication and indexing: implementation and experiments. SIAM J. Sci. Comput. 32(4), 170–191 (2011)

    Article  MathSciNet  Google Scholar 

  14. Gilbert, J.R., Moler, C., Schreiber, R.: Sparse matrices in MATLAB: design and implementation. SIAM J. Matrix Anal. Appl. 13(1), 333–356 (1992)

    Article  MathSciNet  Google Scholar 

  15. Gustavson, F.G.: Finding the block lower triangular form of a matrix. In: Bunch, J.R., Rose, D.J. (eds.) Sparse Matrix Computations, pp. 275–289. Academic Press (1976)

    Google Scholar 

  16. Buluç, A., Gilbert, J.R.: The combinatorial BLAS: design, implementation, and applications. Int. J. High Perform. Comput. Appl. 25(4), 496–509 (2011)

    Article  Google Scholar 

  17. Satish, N., et al.: Navigating the maze of graph analytics frameworks using massive graph datasets. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, pp. 1–12. Snowbird (2014)

    Google Scholar 

  18. Murphy, R., Bader, D., Snir, M.: Unveiling the first graph 500 list. In: International Conference for High Performance Computing, Networking, Storage and Analysis, New Orleans (2010)

    Google Scholar 

  19. Graph500. https://graph500.org/. Accessed 6 July 2018

  20. Chakrabarti, D., Zhan, Y., Faloutsos, C.: R-MAT: a recursive model for graph mining. In: Proceedings of the SIAM Conference on Data Mining, Lake Buena Vista (2014)

    Google Scholar 

Download references

Acknowledgments

We thank the three anonymous reviewers from the OpenSHMEM Workshop, whose helpful and incisive advice produced a much better paper.

Author information

Authors and Affiliations

  1. US Department of Defense, 9800 Savage Road, Ft. George G. Meade, MD, 20755, USA

    Curtis Hughey

Authors
  1. Curtis Hughey
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Curtis Hughey .

Editor information

Editors and Affiliations

  1. Oak Ridge National Laboratory, Oak Ridge, TN, USA

    Swaroop Pophale

  2. Oak Ridge National Laboratory, Oak Ridge, TN, USA

    Neena Imam

  3. Oak Ridge National Laboratory, Oak Ridge, TN, USA

    Ferrol Aderholdt

  4. Oak Ridge National Laboratory, Oak Ridge, TN, USA

    Manjunath Gorentla Venkata

Rights and permissions

Reprints and permissions

Copyright information

© 2019 This is a U.S. government work and its text is not subject to copyright protection in the United States; however, its text may be subject to foreign copyright protection

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Hughey, C. (2019). Tumbling Down the GraphBLAS Rabbit Hole with SHMEM. In: Pophale, S., Imam, N., Aderholdt, F., Gorentla Venkata, M. (eds) OpenSHMEM and Related Technologies. OpenSHMEM in the Era of Extreme Heterogeneity. OpenSHMEM 2018. Lecture Notes in Computer Science(), vol 11283. Springer, Cham. https://doi.org/10.1007/978-3-030-04918-8_8

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-04918-8_8

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-04917-1

  • Online ISBN: 978-3-030-04918-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation