Introduction
Sparse Matrix-Matrix Multiplication (SpGEMM) is a fundamental building block for big data analytics, graph theory, and scientific simulations. Unlike dense matrix multiplication, the sparsity pattern and the number of non-zero elements in the output of SpGEMM are not known beforehand. This characteristic makes memory management and parallelization particularly challenging on modern multi-core and many-core architectures.
This paper, originally published in Parallel Computing (2019), explores deep optimizations for SpGEMM, specifically targeting the Intel Xeon Phi (Knights Landing) architecture. The authors identify critical bottlenecks in existing libraries and propose high-performance algorithms to overcome them.
Challenges in SpGEMM
The authors highlight several key issues that limit the performance of traditional SpGEMM implementations:
- Thread Scheduling Overhead: Standard OpenMP dynamic scheduling is often too "heavy" for the fine-grained tasks in row-wise SpGEMM.
- Memory Management Bottlenecks: Frequent allocation and deallocation of temporary memory by a master thread create significant serial bottlenecks.
- The "Sortedness" Requirement: Many libraries force output rows to be sorted by column index, adding overhead that is not always required by subsequent computational steps.
Optimization Strategies
The research focuses on optimizing two primary approaches based on Gustavson’s row-wise algorithm: hash-table based and heap-based SpGEMM.
Memory and Scheduling Optimizations
To address memory bottlenecks, the authors shifted from master-thread memory management to thread-private allocation using the Intel TBB scalable_malloc. This change drastically reduces the overhead associated with frequent memory operations by avoiding the serial bottlenecks of a single master allocator.
Additionally, the team implemented FLOP-based load balancing. Instead of assigning an equal number of rows to each thread, they distribute work based on the required floating-point operations (FLOPs) per row, ensuring a more balanced computational load across the many-core processor.
HashVector: A SIMD-Optimized Accumulator
A novel contribution of this work is the "HashVector," which utilizes AVX-512 SIMD instructions to probe multiple hash table entries simultaneously. This approach effectively reduces the performance impact of hash collisions, particularly for matrices with uniform distributions, by leveraging the wide vector registers of the KNL architecture.
Experimental Evaluation
The performance was evaluated using a diverse set of matrices, including the SuiteSparse Matrix Collection, synthetic R-MAT matrices (Erdős-Rényi and Graph500), and real-world protein similarity networks.
The "Compression Ratio" Recipe
The authors discovered that the "Compression Ratio" (FLOPs divided by the number of non-zeros in the output) is the most effective predictor of performance. They propose a selection recipe:
- High Compression Ratio (>2): Hash-based algorithms are preferred as they benefit from high locality in the hash table.
- Low Compression Ratio (≤2): Heap-based algorithms are often more efficient as the hashing overhead is not justified.
Results and Impact
The optimized implementations consistently outperformed state-of-the-art libraries like Intel MKL and Kokkos-Kernels. Key findings include:
- Sortedness Speedup: Allowing unsorted output provides a 1.6x to 1.7x speedup on average, revealing a hidden cost in standard libraries.
- MCDRAM Limitations: The Xeon Phi's High-Bandwidth Memory (MCDRAM) provides limited benefit for very sparse matrices due to irregular, fine-grained memory access patterns that fail to saturate the bandwidth.
- Real-World Application: Integrating these optimizations into the HipMCL protein clustering tool resulted in a 10x speedup for the SpGEMM kernel and a 2.6x overall speedup for the entire application pipeline.
Conclusion
This work provides a comprehensive framework for optimizing SpGEMM on many-core processors. While the current optimizations are tuned for Intel architectures, the underlying principles of load balancing, thread-private memory, and SIMD-accelerated hashing offer a roadmap for performance tuning on other high-performance computing platforms. Future research will explore adaptive "poly-algorithms" that can switch strategies mid-computation based on real-time sparsity observations.
Summary updated