spbla

spbla is a linear Boolean algebra library primitives and operations for work with sparse matrices written for CPU, Cuda and OpenCL platforms. The primary goal of the library is implementation, testing and profiling algorithms for solving formal-language-constrained problems, such as context-free and regular path queries with various semantics for graph databases. The library provides C-compatible API, written in the GraphBLAS style. The library is shipped with python package pyspbla - wrapper for spbla library C API. This package exports library features and primitives in high-level format with automated resources management and fancy syntax sugar.

• PyPI package: https://pypi.org/project/pyspbla/
• Tutorial: https://github.com/JetBrains-Research/spbla/blob/main/docs/tutorial.md
• Extended example: https://github.com/JetBrains-Research/spbla/blob/main/docs/extended_example.md
• Getting started: https://github.com/JetBrains-Research/spbla/blob/main/docs/getting_started.md
• Contributing guide: https://github.com/JetBrains-Research/spbla/blob/master/CONTRIBUTING.md
• Python Reference: https://jetbrains-research.github.io/spbla/pydocs/pyspbla
• C API Reference: https://jetbrains-research.github.io/spbla/cdocs/
• Package source code: https://github.com/JetBrains-Research/spbla/tree/main/python/pyspbla

Features summary

• Python package for every-day tasks
• C API for performance-critical computations
• Cuda backend for computations
• OpenCL backend for computations
• Cpu (fallback) backend for computations
• Matrix creation (empty, from data, with random data)
• Matrix-matrix operations (multiplication, element-wise addition, kronecker product)
• Matrix operations (equality, transpose, reduce to vector, extract sub-matrix)
• Matrix data extraction (as lists, as list of pairs)
• Matrix syntax sugar (pretty string printing, slicing, iterating through non-zero values)
• IO (import/export matrix from/to .mtx file format)
• GraphViz (export single matrix or set of matrices as a graph with custom color and label settings)
• Debug (matrix string debug markers, logging)

Platforms

• Linux based OS (tested on Ubuntu 20.04)

Installation

Get the latest package version from PyPI package index:

shell $ python3 -m pip install pyspbla

Simple example

Create sparse matrices, compute matrix-matrix product and print the result to the output:

```python import pyspbla as sp

a = sp.Matrix.empty(shape=(2, 3)) a[0, 0] = True a[1, 2] = True

b = sp.Matrix.empty(shape=(3, 4)) b[0, 1] = True b[0, 2] = True b[1, 3] = True b[2, 1] = True

print(a, b, a.mxm(b), sep="\n") ```

Performance

Sparse Boolean matrix-matrix multiplication evaluation results are listed bellow. Machine configuration: PC with Ubuntu 20.04, Intel Core i7-6700 3.40GHz CPU, DDR4 64Gb RAM, GeForce GTX 1070 GPU with 8Gb VRAM.

The matrix data is selected from the SuiteSparse Matrix Collection link.

| Matrix name | # Rows | Nnz M | Nnz/row | Max Nnz/row | Nnz M^2 | |:---------------------------|-----------:|----------:|--------:|------------:|------------:| | SNAP/amazon0312 | 400,727 | 3,200,440 | 7.9 | 10 | 14,390,544 | | LAW/amazon-2008 | 735,323 | 5,158,388 | 7.0 | 10 | 25,366,745 | | SNAP/web-Google | 916,428 | 5,105,039 | 5.5 | 456 | 29,710,164 | | SNAP/roadNet-PA | 1,090,920 | 3,083,796 | 2.8 | 9 | 7,238,920 | | SNAP/roadNet-TX | 1,393,383 | 3,843,320 | 2.7 | 12 | 8,903,897 | | SNAP/roadNet-CA | 1,971,281 | 5,533,214 | 2.8 | 12 | 12,908,450 | | DIMACS10/netherlands_osm | 2,216,688 | 4,882,476 | 2.2 | 7 | 8,755,758 |

Detailed comparison is available in the full paper text at link .

Directory structure

spbla ├── .github - GitHub Actions CI setup ├── docs - documents, text files and various helpful stuff ├── scripts - short utility programs ├── spbla - library core source code │ ├── include - library public C API │ ├── sources - source-code for implementation │ │ ├── core - library core and state management │ │ ├── io - logging and i/o stuff │ │ ├── utils - auxilary class shared among modules │ │ ├── backend - common interfaces │ │ ├── cuda - cuda backend │ │ ├── opencl - opencl backend │ │ └── sequential - fallback cpu backend │ ├── utils - testing utilities │ └── tests - gtest-based unit-tests collection ├── python - pyspbla related sources │ ├── pyspbla - spbla library wrapper for python (similar to pygraphblas) │ ├── tests - regression tests for python wrapper │ └── data - generate data for pyspbla regression tests ├── deps - project dependencies │ ├── clbool - OpenCL based matrix operations for dcsr, csr and coo matrices │ ├── cub - cuda utility, required for nsparse │ ├── gtest - google test framework for unit testing │ └── nsparse - SpGEMM implementation for csr matrices (with unified memory, configurable) └── CMakeLists.txt - library cmake config, add this as sub-directory to your project

Contributing

If you want to contribute to this project, follow our short and simple open-source contributors guide. Also have a look at code of conduct.

Contributors

• Egor Orachyov (Github: EgorOrachyov)
• Maria Karpenko (Github: mkarpenkospb)
• Pavel Alimov (Github : Krekep)
• Semyon Grigorev (Github: gsvgit)

Citation

ignorelang @online{spbla, author = {Orachyov, Egor and Karpenko, Maria and Alimov, Pavel and Grigorev, Semyon}, title = {spbla: sparse Boolean linear algebra for CPU, Cuda and OpenCL computations}, year = 2021, url = {https://github.com/JetBrains-Research/spbla}, note = {Version 1.0.0} }

License

This project is licensed under MIT License. License text can be found in the license file.

Acknowledgments

This is a research project of the Programming Languages and Tools Laboratory at JetBrains-Research. Laboratory website link.