TY - GEN

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

AU - Orachev, Egor

AU - Karpenko, Maria

AU - Khoroshev, Artem

AU - Grigorev, Semyon

N1 - Conference code: 35

PY - 2021/6/1

Y1 - 2021/6/1

N2 - 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.

AB - 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.

KW - распределенная обработка

KW - анализ данных

KW - управление памятью

KW - программирование

KW - библиотеки

KW - разреженные матрицы

KW - distributed processing

KW - data analysis

KW - memory management

KW - programming

KW - libraries

KW - sparse matrices

KW - sparse boolean matrix

KW - boolean semiring

KW - sparse linear algebra

KW - GPGPU

UR - https://www.mendeley.com/catalogue/243d569a-2495-395e-ab6c-4f3097eb8974/

UR - https://www.mendeley.com/catalogue/243d569a-2495-395e-ab6c-4f3097eb8974/

U2 - 10.1109/ipdpsw52791.2021.00049

DO - 10.1109/ipdpsw52791.2021.00049

M3 - статья в сборнике материалов конференции

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

SP - 272

EP - 275

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

PB - Institute of Electrical and Electronics Engineers Inc.

CY - Los Alamitos, CA, USA

Y2 - 17 June 2021 through 21 June 2021

ER -