Bullseye Hash: An Efficient Hash-Table for Sparse Tensor Contraction

Abstract

Sparse tensor contraction (SpTC) is a critical operation in high-performance applications. However, the high dimensionality and inherent sparsity of tensors make the performance improvement of SpTC a fundamentally challenging problem. In this paper, we propose Bullseye Hash, a novel hash table designed to efficiently support SpTC computations. Bullseye Hash features a fast hash function with guaranteed collision-free operations. We analyze the special characteristics of SpTC and optimize hash operations tailored to its computation pattern across various data objects. Additionally, we provide guidance on configuring data object representations based on their specific characteristics, considering both algorithmic complexity and cache efficiency. Experimental results on 22 SpTCs show that our method achieves up to a 10.4 × speedup (with an average of 3.1 ×) and reduces the memory footprint by up to 77% (with an average of 43%) compared to the state-of-the-art. To the best of our knowledge, this work is the first effort in designing hash-table methods specifically for SpTC, paving the way for further optimization using hash-based techniques in sparse computations.