TL;DR
This paper introduces BRMerge, a novel accumulation method for Sparse General Matrix Multiplication (SpGEMM) on multi-core CPUs. By optimizing memory access patterns, BRMerge significantly speeds up SpGEMM computations, outperforming existing state-of-the-art libraries by up to 1.42x on average.
What Problem Does This Paper Address?
Sparse General Matrix Multiplication (SpGEMM) is a fundamental operation in many scientific and engineering applications, such as solving linear systems and graph analysis. However, SpGEMM is notoriously memory-bound, meaning its performance is heavily dictated by how efficiently it can access and process data from memory. Existing SpGEMM methods often struggle with the vast and irregular memory accesses required, leading to suboptimal performance due to inefficient cache utilization and high translation lookaside buffer (TLB) misses. This paper aims to tackle these memory access inefficiencies to accelerate SpGEMM on modern multi-core CPU architectures.
Methods
The core contribution of this paper is the BRMerge accumulation method. This method is designed to optimize memory access patterns during the accumulation phase of SpGEMM, which is where intermediate results from multiplying rows of matrix A with matrix B are combined into a final result row.
BRMerge operates in two phases:
- Multiplying Phase: This phase generates intermediate lists by multiplying rows of matrix A with corresponding rows of matrix B. These intermediate lists are stored contiguously in memory using a "ping-pong buffer" technique.
- Accumulating Phase: This is where BRMerge truly innovates. It employs a binary-row-merging algorithm to combine these intermediate lists. Instead of complex heap-based or hash-based merging, BRMerge merges lists two by two in a tree-like hierarchy. This approach leverages:
- Streaming Access Patterns: Data is accessed and processed sequentially, maximizing memory bandwidth utilization and taking advantage of hardware pre-fetching.
- Minimized TLB Cache Misses: By processing intermediate lists contiguously, the need to repeatedly access different memory pages for the same intermediate data is reduced, thus lowering TLB misses.
- Reasonably High L1/L2 Cache Hit Rates: The localized processing of intermediate lists and the reduction in data size after each merge step contribute to better cache performance.
Based on BRMerge, the authors propose two SpGEMM libraries: BRMerge-Upper and BRMerge-Precise, which differ in their memory allocation strategies (upper-bound vs. precise allocation).
Datasets
The authors evaluated their proposed methods using 26 commonly used sparse matrices from the SuiteSparse Matrix Collection. These matrices vary in size and compression ratio, providing a comprehensive testbed for performance evaluation. No new benchmarks were introduced.
Key Insights and Ideas
- The bottleneck is memory, not just computation: The paper strongly emphasizes that for SpGEMM, memory access efficiency is paramount, often more so than raw computational power.
- Binary merging is surprisingly effective: A simple binary merging strategy, when applied to intermediate SpGEMM lists, can achieve superior memory access patterns compared to more complex heap or hash-based methods.
- Contiguous access is king: The BRMerge method's success hinges on its ability to maintain streaming, contiguous memory access patterns, which modern CPUs are highly optimized for.
- TLB misses are a significant performance killer: The paper highlights how inefficient memory access patterns can lead to frequent TLB misses, severely degrading performance, and BRMerge's design actively mitigates this.
Key Results
- The proposed BRMerge-Precise library achieved an average performance speedup of 1.42x over the state-of-the-art best-performing SpGEMM library (Hash-SpGEMM) on an Intel Xeon Platinum 8163 CPU.
- On an Intel Xeon Gold 6254 CPU, BRMerge-Precise achieved an average speedup of 1.39x over Hash-SpGEMM.
- BRMerge-Upper also significantly outperformed existing libraries like Heap-SpGEMM, especially on matrices with higher compression ratios.
- The paper demonstrates that BRMerge-based libraries consistently outperform other libraries across a wide range of benchmarks, showcasing the effectiveness of the proposed accumulation method.
Limitations and Future Work
- MKL-SpGEMM Performance: The paper notes that for matrices with high compression ratios, the Intel MKL-SpGEMM library sometimes outperformed BRMerge-Precise. However, the authors could not fully explain this difference due to the unavailability of MKL-SpGEMM's detailed implementation.
- Future Work: While not explicitly detailed, the success of BRMerge on multi-core CPUs suggests potential for further optimization and exploration on other architectures (e.g., GPUs, accelerators) or for different types of sparse matrix operations. The paper also mentions that the load balancing strategy used is the same as previous work, implying potential for further improvements in load balancing.
Summary updated