EUVIMEDEUVIMED entdecken
Crossref

Hypergraph Partitioning for Sparse Matrix-Matrix Multiplication

Grey Ballard, Alex Druinsky, Nicholas Knight, Oded Schwartz

ACM Transactions on Parallel Computing · 26.12.2016 · 3 (3) · 1-34

DOI: 10.1145/3015144 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Parallel Computing, online erschienen am 26.12.2016. Verfasst von Grey Ballard und 3 weiteren Autor:innen. Die Arbeit wurde bisher 40-mal zitiert (Crossref) und nennt 44 Literaturangaben. Gefördert von: HUJI Cyber Security Research Center in conjunction with the Israel National Cyber Bureau in the Prime Minister's Office, Sandia National Laboratories Truman Fellowship, United States-Israel Binational Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We propose a fine-grained hypergraph model for sparse matrix-matrix multiplication (SpGEMM), a key computational kernel in scientific computing and data analysis whose performance is often communication bound. This model correctly describes both the interprocessor communication volume along a critical path in a parallel computation and also the volume of data moving through the memory hierarchy in a sequential computation. We show that identifying a communication-optimal algorithm for particular input matrices is equivalent to solving a hypergraph partitioning problem. Our approach is nonzero structure dependent, meaning that we seek the best algorithm for the given input matrices. In addition to our three-dimensional fine-grained model, we also propose coarse-grained one-dimensional and two-dimensional models that correspond to simpler SpGEMM algorithms. We explore the relations between our models theoretically, and we study their performance experimentally in the context of three applications that use SpGEMM as a key computation. For each application, we find that at least one coarse-grained model is as communication efficient as the fine-grained model. We also observe that different applications have affinities for different algorithms. Our results demonstrate that hypergraphs are an accurate model for reasoning about the communication costs of SpGEMM as well as a practical tool for exploring the SpGEMM algorithm design space.

Förderung

  • HUJI Cyber Security Research Center in conjunction with the Israel National Cyber Bureau in the Prime Minister's Office
  • Sandia National Laboratories Truman Fellowship
  • United States-Israel Binational Science Foundation
  • National Security Science and Engineering
  • Intel Collaborative Research Institute for Computational Intelligence
  • Operator of Sandia National Laboratories
  • Ministry of Science and Technology, Israel
  • Einstein Foundation and the Minerva Foundation

Zitieren

APA

Ballard, G., Druinsky, A., Knight, N., & Schwartz, O. (2016). Hypergraph Partitioning for Sparse Matrix-Matrix Multiplication. ACM Transactions on Parallel Computing, 3(3), 1-34. https://doi.org/10.1145/3015144

Vancouver

Ballard G, Druinsky A, Knight N, Schwartz O. Hypergraph Partitioning for Sparse Matrix-Matrix Multiplication. ACM Transactions on Parallel Computing. 2016;3(3):1-34. doi:10.1145/3015144

BibTeX
@article{Ballard2016,
  author = {Ballard, Grey and Druinsky, Alex and Knight, Nicholas and Schwartz, Oded},
  title = {Hypergraph Partitioning for Sparse Matrix-Matrix Multiplication},
  journal = {ACM Transactions on Parallel Computing},
  year = {2016},
  volume = {3},
  number = {3},
  pages = {1--34},
  doi = {10.1145/3015144}
}
Kostenlos starten →