bit-packing and compression of data structures in scientific computing

Question

I recently came across this paper, which describes a scheme for saving memory in representing sparse matrices. A 32-bit integer can store numbers up to ~4 billion. But when you solve a PDE you've gone parallel and partitioned the problem long before the number of unknowns is anywhere close to 4 billion. Their idea is to reorder the matrix for small bandwidth. Rather than store the indices j of all non-zero columns in a given row i, they store the offset j - i, which tends to be small in magnitude by virtue of the reordering. The offsets can then be stored using fewer bits than a 32-bit integer would. There's more arithmetic to do when iterating over the non-zero entries of the matrix, but the savings in fewer cache misses more than make up for it. In this paper they were looking specifically at using 16-bit indices in a hierarchical matrix format, but ultimately it's a similar idea. There's also the library zfp, which is more for compressing floating-point data.

Since "flops are free" now and the bottleneck is memory access, these kinds of tricks seem really promising for making better use of CPU cache.

I've scoured most of the cited/citing works of these two papers. I'm looking for any other references on the effectiveness of bit-packing, for sparse matrix-vector multiplication and for any other problems in computational science. For example, I imagine you could design much more efficient data structures for graphs or for unstructured meshes using this idea.

Answer 1

Reducing Memory for Sparse Matrices

One method (that they mention in the first paper you linked, but is worth emphasizing) is the Block Compressed Sparse Row (BCSR) storage format. If your problem creates dense $n \times n$ blocks (common in e.g. FEM with multiple DoFs per node), you modify the typical CSR (CSC) storage scheme to store only a single column (row) index for the block. This reduces the storage requirement of the index vector by a factor of $n^2$. If you're storing $3\times 3$ blocks, this reduces the memory required for the index vector by ~90%, which is far more than you'll save using any sort of bit-packing tricks.

A fuller description of the format can be found here: http://www.netlib.org/utk/people/JackDongarra/etemplates/node375.html

In addition, storing dense blocks in the sparse matrix allows you to vectorize the matrix-vector multiplication with SSE or AVX instructions, but you probably won't see a huge speedup here because, as you noted, you'll still be memory-bound.

If your problem doesn't produce a structure that is as perfect for BCSR as FEM, then you can still use the technique without incurring the memory overhead of unaligned blocks. This paper shows an implementation that does not require that the blocks start on a multiple of $n$ column (and also explains what I meant by memory overhead of unaligned blocks).

https://bebop.cs.berkeley.edu/pubs/vuduc2005-ubcsr-split.pdf

Of course, there is nothing preventing you from playing the bit-packing games with a re-ordered BCSR matrix to further reduce the memory requirement, but you should probably pick the low-hanging fruit first.

Bit-packing in general

If you're specifically interested in applications of bit packing, this is done aggressively in the LLVM project. One of its (clever?) ideas is to use what they call a PointerIntPair, which stores a pointer and a small integer together in the space of a single pointer. The idea here is to take advantage of the fact that (on linux x64 systems), pointers returned by malloc are 16-byte aligned, which gives you 4 bits at the bottom to do something with. They do all sorts of crazy things using this idea, building up complex data structures that live in the space of a single pointer. Here's an interesting conference talk given a few years ago by one of the LLVM optimizer guys. He starts talking about this at 22:00. Fair warning, though: this was at a C++ conference, so there is a large amount of unabashedly-complicated C++ involved.

https://www.youtube.com/watch?v=vElZc6zSIXM&t=22m&ab_channel=CppCon