  Computing the product of two sparse matrices (SpGEMM) is a fundamental
operation in various combinatorial and graph algorithms as well as various
bioinformatics and data analytics applications for computing inner-product
similarities. For an important class of algorithms, only a subset of the output
entries are needed, and the resulting operation is known as Masked SpGEMM since
a subset of the output entries is considered to be "masked out". Existing
algorithms for Masked SpGEMM usually do not consider mask as part of
multiplication and either first compute a regular SpGEMM followed by masking,
or perform a sparse inner product only for output elements that are not masked
out. In this work, we investigate various novel algorithms and data structures
for this rather challenging and important computation, and provide guidelines
on how to design a fast Masked-SpGEMM for shared-memory architectures. Our
evaluations show that factors such as matrix and mask density, mask structure
and cache behavior play a vital role in attaining high performance for Masked
SpGEMM. We evaluate our algorithms on a large number of matrices using several
real-world benchmarks and show that our algorithms in most cases significantly
outperform the state of the art for Masked SpGEMM implementations.
