Introduction
Sparse Matrix-Matrix Multiplication (SpGEMM) is a fundamental kernel in numerous computational fields, including graph analytics (e.g., Markov clustering) and scientific computing (e.g., Algebraic Multigrid solvers). Despite its importance, SpGEMM remains one of the most challenging operations to optimize on modern many-core architectures like Intel’s Knights Landing (KNL). This paper presents a suite of optimizations designed to mitigate architecture-specific bottlenecks, focusing on memory management, thread scheduling, and SIMD-accelerated data structures.
Challenges in SpGEMM
Optimizing SpGEMM is difficult due to three primary factors:
- Irregular Memory Access: The sparsity pattern of the input matrices necessitates indirect addressing, leading to poor cache locality and frequent misses.
- Dynamic Output Size: The number of non-zero elements in the product matrix is generally unknown a priori, complicating efficient memory allocation.
- Hardware Underutilization: Modern processors rely on high parallelism and wide SIMD lanes. The irregular nature of sparse data often fails to saturate these resources, particularly on many-core systems like KNL.
Optimization Strategies
Parallel Memory Management
A significant finding of this work is that standard memory management becomes a major bottleneck on high-core-count systems. Specifically, single-threaded deallocation of large memory blocks can incur substantial overhead, stalling the entire computation. To address this, the authors implemented a parallel memory management scheme where each thread manages its own private memory pool for accumulators.
As shown in the figure above, the time required for memory operations increases dramatically for single-threaded approaches as the allocation size grows. The parallelized approach maintains low overhead across all tested sizes, which is critical for the large-scale matrices typical of SpGEMM workloads.
Light-weight Load Balancing
Standard OpenMP scheduling strategies (static, dynamic, guided) often fail to balance the irregular workload of SpGEMM effectively. The authors introduced a two-phase "balanced" scheduling approach. First, the number of floating-point operations (FLOPs) per row is calculated to estimate the computational weight. Then, a prefix sum and binary search are used to distribute rows such that each thread handles a nearly equal number of FLOPs.
The performance results demonstrate that the "balanced parallel" strategy consistently achieves higher throughput (MFLOPS) compared to standard schedules, particularly as the problem scale increases.
HashVector SpGEMM
To better utilize SIMD capabilities, the authors developed "HashVector," a novel hash-table-based accumulator. By leveraging AVX-512 vector instructions, HashVector can probe multiple hash entries simultaneously. This reduces the instruction count for hash collisions and probing, which are common bottlenecks in traditional hash-based SpGEMM implementations.
Performance Evaluation
The optimized algorithms were evaluated against industry standards, including Intel MKL and Kokkos-Kernels, using the SuiteSparse Matrix Collection and synthetic R-MAT matrices. Key findings include:
- Sorting Overhead: Avoiding the final sort of non-zero elements in each row provides a 1.5x to 1.7x speedup, which is beneficial for applications that do not require sorted output.
- MCDRAM Utilization: While KNL's high-bandwidth memory (MCDRAM) is beneficial, its impact is most pronounced for matrices with higher density where contiguous access patterns are more frequent.
- Algorithm Selection: The authors suggest a decision matrix based on the matrix's compression ratio. Hash-based methods are preferred for high compression ratios, while heap-based methods excel for very sparse matrices requiring sorted output.
Conclusion
By addressing the specific constraints of many-core architectures, this work demonstrates that significant performance gains are possible for SpGEMM. The combination of parallel memory management, load-balanced scheduling, and SIMD-accelerated accumulators allows the proposed methods to consistently outperform general-purpose libraries across a wide range of real-world datasets.
Summary updated