Caching a single dense vector

Generally, the most expensive part of sparse matrix multiplication is the random accesses of the accompanying dense vector. For example, when computing a dense-sparse dot product, we need to access the value of the dense vector at the index of each structural non-zero in the sparse vector. Each access might require a fetch from main memory if the position of the structural non-zero falls in a new cache line.

To avoid this, we process a block of \(B\) sparse vectors for each dense vector. For example, we might load a block of sparse LHS rows and compute the dot product for each sparse row with a single dense RHS column. This keeps the single dense vector in cache so that it can be quickly re-used for multiple sparse vectors. We assume that each sparse vector in the block contains structural non-zeros at positions that lie within a cache line of the previous sparse vectors; and that the cache hierarchy is large enough to hold the entire dense vector, or at least the parts corresponding to all of the structural non-zeros. Larger values of \(B\) improve speed at the cost of increased main memory usage as tatami needs to realize all sparse vectors into memory.

Caching multiple dense vectors

If the dense vectors are small, we might consider loading a block of \(C\) dense vectors into cache at once. For each sparse vector, we iterate over the dense vectors in this block to perform the relevant multiplication operations. We then repeat this with a new sparse vector but re-using the same block of dense vectors.

The idea is that the dense block is small enough that all of its vectors can be completely cached for quick re-use. The cache is also assumed to be large enough to store the sparse vector's contents for re-use across multiple dense vectors. By caching both the dense and sparse vectors, this strategy is more effective than just caching one dense vector. However, this is only applicable when the extent of the relevant dimension is small.

Other blocking schemes

In rare cases, some sparse algorithms have blocking schemes that do not fall into the above two categories. This is mostly related to easier transposition. For examples, see:

• multiply_dense_row_with_sparse_row_matrix_to_column_output()
• multiply_sparse_row_with_dense_row_matrix_to_column_output()

Further comments

Both \(B\) and \(C\) should be positive. If either is equal to 1, no blocking will be performed.