SPbLA: The Library of GPGPU-Powered Sparse Boolean Linear Algebra Operations: The Library of GPGPU-Powered Sparse Boolean Linear Algebra Operations

Egor Orachev, Maria Karpenko, Artem Khoroshev, Semyon Grigorev

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Abstract

Sparse matrices are widely applicable in data analysis while the theory of matrix processing is well-established. There are a wide range of algorithms for basic operations such as matrix-matrix and matrix-vector multiplication, factorization, etc. To facilitate data analysis, GraphBLAS API provides a set of building blocks and allows for reducing algorithms to sparse linear algebra operations. While GPGPU utilization for high-performance linear algebra is common, the high complexity of GPGPU programming makes the implementation of GraphBLAS API on GPGPU challenging. In this work, we present a GPGPU library of sparse operations for an important case - Boolean algebra. The library is based on modern algorithms for sparse matrix processing. We provide a Python wrapper for the library to simplify its use in applied solutions. Our evaluation shows that operations specialized for Boolean matrices can be up to 5 times faster and consume up to 4 times less memory than generic, not the Boolean optimized, operations from modern libraries. We hope that our results help to move the development of a GPGPU version of GraphBLAS API forward.

Translated title of the contributionSPbLA: библиотека операций разреженной булевой линейной булевой линейной алгебры для вычислений на GPU
Original languageEnglish
Title of host publication2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 - In conjunction with IEEE IPDPS 2021
Place of PublicationLos Alamitos, CA, USA
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages272-275
Number of pages4
ISBN (Electronic)978-1-6654-3577-2
DOIs
StatePublished - 1 Jun 2021
Event35th IEEE International Parallel and Distributed Processing Symposium (IPDPS): Workshop on Graphs, Architectures, Programming, and Learning - Virtual Conference, Portland, United States
Duration: 17 Jun 202121 Jun 2021
Conference number: 35
https://www.ipdps.org/ipdps2021/index.html

Publication series

Name2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2021 - In conjunction with IEEE IPDPS 2021

Conference

Conference35th IEEE International Parallel and Distributed Processing Symposium (IPDPS)
Abbreviated titleIPDPS
Country/TerritoryUnited States
CityPortland
Period17/06/2121/06/21
Internet address

Scopus subject areas

  • Computer Science(all)
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Keywords

  • distributed processing
  • data analysis
  • memory management
  • programming
  • libraries
  • sparse matrices
  • sparse boolean matrix
  • boolean semiring
  • sparse linear algebra
  • GPGPU

Fingerprint

Dive into the research topics of 'SPbLA: The Library of GPGPU-Powered Sparse Boolean Linear Algebra Operations: The Library of GPGPU-Powered Sparse Boolean Linear Algebra Operations'. Together they form a unique fingerprint.

Cite this