Skip to content

A Julia interface (wrapper) to the Compressed Sparse Blocks (CSB) library.

License

Notifications You must be signed in to change notification settings

fcdimitr/CompressedSparseBlocks.jl

Repository files navigation

Julia Interface to Matrix-Vector Multiplications in CSB Format

Documentation Build Status Contributing Extras
CI

We provide a Julia interface (a wrapper) to the Compressed Sparse Blocks (CSB) library. The library is written in C/C++, available at https://people.eecs.berkeley.edu/~aydin/csb/html/index.html. The library supports fast computation of large sparse matrix-vector products, $Ax$ and $A^{\rm T}x$ operations specifically, with sparse matrix $A$ in the format of compressed sparse blocks (CSB), on shared-memory computer systems. The CSB format was introduced by A. Buluç, J. Fineman, M. Frigo, J. Gilbert, and C. Leiserson [1].

The CSB format and library have the following advantages: (1) The matrix-vector operations in CSB format often outpace the conventional general-purposes sparse formats, namely, CSC and CSR [2]. (2) The multiplication with the transposed matrix $A^{\rm T}$ does not suffer from longer latency than that with $A$. The symmetric performance eliminates the need for an additional copy in a different layout for $A^{\rm T}$ (as with CSR or CSC) for reducing the speed gap at the cost of double memory consumption. (3) The library is integrated with Cilk [3]. The latter offers optimal run-time scheduling (in theory and in practice) on parallel computers with shared memory.

This Julia interface is intended to extend and ease the use of CSB to broader applications. This interface supports up to $32$ multiple vectors to be applied with the same matrix $A$.

Benchmarks

Fig.1 - Comparison in wall-clock execution time between CSB (direct and transpose) and MKLSparse (CSC transpose only). The parallel execution times are with 4 threads on an Intel Core i5-4288U @2.6GHz CPU. The average degree is the average number of nonzeros per row/column.

Installation

The package can be added using the Julia package manager. From the Julia REPL, type ] to enter the Pkg REPL mode and execute the following command

pkg> add CompressedSparseBlocks

⚠️ CompressedSparseBlocks is currently not working on Windows and native M1 Macs: Either use WSL2 on Windows or use the package via Rosetta 2 on the M-processor Macs (that means by using the x86 and not the arm64 julia).

Documentation

  • STABLEmost recently tagged version of the documentation.
  • LATESTin-development version of the documentation.

Contributing and Questions

Contributions are very welcome, as are feature requests and suggestions. Please open an issue if you encounter any problems.

References

[1] A. Buluç, J. T. Fineman, M. Frigo, J. R. Gilbert, and C. E. Leiserson, “Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks,” in Proceedings of the 21st Annual Symposium on Parallelism in Algorithms and Architectures, 2009, pp. 233–244. doi: 10.1145/1583991.1584053.

[2] S. C. Eisenstat, M. C. Gursky, M. H. Schultz, A. H. Sherman, “Yale Sparse Matrix Package,” Technical Report, 1977.

[3] M. Frigo, C. E. Leiserson, and K. H. Randall, “The implementation of the Cilk-5 multithreaded language,” ACM SIGPLAN Notices, vol. 33, no. 5, pp. 212–223, 1998, doi: 10.1145/277652.277725.

Contributors of the Julia interface

Design and development:
Dimitris Floros1, Nikos Pitsianis1,2, Xiaobai Sun2

1 Department of Electrical and Computer Engineering, Aristotle University of Thessaloniki, Thessaloniki 54124, Greece
2 Department of Computer Science, Duke University, Durham, NC 27708, USA