Source-linked AI summary
Performance Evaluation of Sparse Matrix Multiplication Kernels on Intel Xeon Phi
Erik Saule, Kamer Kaya, Umit V. Catalyurek
TL;DR
The paper asks how Intel Xeon Phi performs on important sparse kernels whose irregular accesses make efficient execution difficult. It evaluates SpMV and SpMM through architectural microbenchmarks and experiments across sparse matrices, finding latency-bound behavior and promising performance relative to tested CPUs and GPUs.
Problem
SpMV and SpMM are important scientific-computing kernels, but their sparse, irregular access patterns make their performance on the new Xeon Phi coprocessor an open question.
Method
The paper analyzes Xeon Phi architecture and microbenchmarks, then evaluates SpMV and SpMM using sparse matrices and compares results with Intel Xeon processors and NVIDIA Tesla GPUs.
Results
Xeon Phi’s sparse kernels are latency bound, yet their performance is promising and superior to the tested cutting-edge processors and accelerators, especially for SpMM.
Takeaways & Limitations
Wide registers and vectorization capabilities make Xeon Phi a promising platform for scientific computing and sparse matrix kernels within the evaluated scope.
Takeaways & Limitations
Register blocking with dense block storage is not very promising for SpMV, and its benefits may remain limited for very sparse matrices because input-vector accesses still induce latency.
Abstract
from arXiv · showhide
Intel Xeon Phi is a recently released high-performance coprocessor which features 61 cores each supporting 4 hardware threads with 512-bit wide SIMD registers achieving a peak theoretical performance of 1Tflop/s in double precision. Many scientific applications involve operations on large sparse matrices such as linear solvers, eigensolver, and graph mining algorithms. The core of most of these applications involves the multiplication of a large, sparse matrix with a dense vector (SpMV). In this paper, we investigate the performance of the Xeon Phi coprocessor for SpMV. We first provide a comprehensive introduction to this new architecture and analyze its peak performance with a number of micro benchmarks. Although the design of a Xeon Phi core is not much different than those of the cores in modern processors, its large number of cores and hyperthreading capability allow many application to saturate the available memory bandwidth, which is not the case for many cutting-edge processors. Yet, our performance studies show that it is the memory latency not the bandwidth which creates a bottleneck for SpMV on this architecture. Finally, our experiments show that Xeon Phi's sparse kernel performance is very promising and even better than that of cutting-edge general purpose processors and GPUs.
1 Introduction
The paper examines SpMV and related sparse kernels on Intel Xeon Phi, a many-core coprocessor whose irregular sparse workloads pose a distinct performance question. Across experiments and comparisons, it finds promising sparse-kernel performance while identifying memory latency and matrix structure as central factors.
- SpMV and SpMM are computational cores of large-scale scientific applications involving linear systems, eigenvalues, and linear programs.
- Intel Xeon Phi combines many cores, hardware threading, and wide vector registers in a coprocessor architecture of interest for high-performance computing.
- The paper provides the first analysis of Xeon Phi performance on SpMV and SpMM, addressing sparse kernels beyond prior studies of dense, regular data.
- Experiments use 22 UFL Sparse Matrix Collection matrices and compare Xeon Phi with two Intel Xeon processors and two NVIDIA Tesla GPUs.
- Xeon Phi’s sparse performance is promising, while memory latency rather than bandwidth limits SpMV and performance depends strongly on sparsity and nonzero alignment.
2 The Intel Xeon Phi Coprocessor
The Xeon Phi architecture combines many threaded cores, large SIMD capability, and substantial memory infrastructure. Microbenchmarks show that read and write behavior varies by instruction mix, vectorization, thread count, and the ability to hide memory latency.
- Architecture: The pre-release Xeon Phi card has 61 cores at 1.05GHz, eight memory controllers, and 352GB/s aggregate controller bandwidth.
- Architecture: Each core supports four hardware contexts and uses separate instruction pipelines to overlap latency across threads.
- Architecture: Each core has 32×512-bit SIMD registers supporting eight double-precision or 16 single-precision values per vector and up to eight double-precision operations per cycle.
- Read-bandwidth benchmarks: 12GB/s is reached for char summation with 61 cores and 2 threads per core, where performance is instruction bound and follows the No Pairing limit.
- Read-bandwidth benchmarks: 60.0GB/s is reached for scalar int summation with 4 threads per core, while vectorized full-cacheline summation reaches 171GB/s with 61 cores and 4 threads per core.
- Read-bandwidth benchmarks: 183GB/s is reached with prefetching, 61 cores, and 2 threads per core, but performance plateaus as core count increases.
3 Sparse Multiplication Kernels
The paper defines SpMV and SpMM through their sparse matrix access patterns and describes compressed row storage as the baseline representation. Their low computation-to-data ratio and irregular accesses make efficient execution difficult.
- SpMV and SpMM: SpMV computes y ← Ax for a sparse matrix A and dense vectors x and y, accessing each nonzero once for a multiplication and addition.
- SpMV and SpMM: SpMM generalizes the operation to dense matrices X and Y, requiring k reads and k read-and-writes per accessed nonzero.
- Access patterns: SpMV has irregular memory access and little computation per nonzero, causing most operations to suffer from bandwidth limitation.
- Compressed row storage: Compressed row storage uses column ids, row pointers, and values arranged in row-major order for a sparse matrix with τ nonzeros.
- Compressed row storage: The paper uses CRS as a baseline because the best sparse storage format usually depends on the matrix pattern and kernel.
- Parallel execution: In parallel CRS execution, rows can be assigned independently to threads, with each output entry computed from its row’s nonzeros.
4 SpMV on Intel Xeon Phi
SpMV performance on Xeon Phi depends strongly on matrix structure and vectorization: useful cacheline density improves vectorized execution, while most instances remain memory-latency bound. Matrix reordering and dense register blocking provide inconsistent or limited benefits.
- Evaluation setup: 22 matrices from the UFL Sparse Matrix Collection were evaluated using CRS storage, double-precision values, and 32-bit indices.The dataset also includes one 2048 × 2048 five-point stencil mesh.
- Baseline performance: OpenMP SpMV performance ranges from 1 to 13GFlop/s with -O1, while -O3 reaches 22GFlop/s on nd24k and exceeds 15GFlop/s on five matrices.The best configurations typically use 61 cores with 3 threads per core or 60 cores with 4 threads per core.
- Vectorization and locality: Vectorization improves performance most when useful cacheline density is high, because vgatherd benefits from nonzeros packed within fewer input-vector cachelines.Useful cacheline density averages each row’s nonzero count divided by the number of input-vector cacheline elements accessed by that row.
- Bandwidth considerations: Most SpMV instances are limited by memory latency rather than bandwidth, although five instances show little difference between three and four threads per core and three exceed 100GB/s application bandwidth.The five instances are crankseg 2, pdbHYS, webbase-1M, nd24k, and torso1.
- Effect of matrix ordering: Reverse Cuthill-McKee reordering improves F1 by almost 6GFlop/s, but eight matrices degrade and six experience increased input-vector transfers.The results indicate that row and column ordering can make matrices less friendly to Xeon Phi when vector access worsens.
- Effect of register blocking: Dense register blocking does not improve average performance; the best 8 × 1 scheme helps eight instances, never by more than 25%, while large blocks waste memory at low density.Register blocking saves memory only when at least 70% of block values are nonzeros, a condition not met by the tested 8 × 8 blocks.
5 SpMM on Intel Xeon Phi
SpMM raises the flop-to-byte ratio by multiplying a sparse matrix by multiple dense vectors, allowing Xeon Phi to exploit its wide SIMD registers. Manual vectorization and NRNGO writes substantially improve performance, reaching 128GFlop/s on pwtk.
- SpMM multiplies a sparse matrix by multiple dense vectors, increasing the flop-to-byte ratio beyond SpMV’s limit of at most 30GFlop/s.This can benefit graph-based recommendation systems and eigensolvers that reuse the same sparse matrix across vectors.
- The Xeon Phi implementation stores each row of X contiguously and provides generic, manually vectorized, and NRNGO-write variants.The manually vectorized variant processes eight doubles per SIMD register and uses fused multiply-add while retaining temporary values in registers.
- With k = 16, manual vectorization doubles performance in many instances, exceeding 60GFlop/s in 11 instances.
- NRNGO writes provide significant improvements, with performance peaking at 128GFlop/s on pwtk.
- Only one instance surpasses 60GB/s application bandwidth, while transferring X to multiple cores increases the accounted data-movement overhead.Finite cache size has little impact, but the presence of 61 separate caches can matter for some applications.
6 Against other architectures
The study compares Xeon Phi with two GPUs and two CPU systems on sparse matrix multiplication. Xeon Phi leads frequently on both SpMV and SpMM, with especially strong results for SpMM.
- The comparison uses NVIDIA Tesla C2050 and K20 GPUs alongside dual Intel Xeon Westmere and Sandy Bridge systems.The GPU results use CuSparse, while the CPU and Xeon Phi implementations are otherwise matched except for instruction-set-specific SpMM optimizations.
- For SpMV, Xeon Phi achieves the highest performance on 12 of 22 instances and is the only architecture exceeding 15GFlop/s.It exceeds 15GFlop/s on 7 instances; K20 leads on 9 instances and performs better than C2050 on 18.
- For SpMM, Xeon Phi achieves the best performance on 14 instances, compared with 5 for the CPUs and 3 for the GPUs.
- Xeon Phi is the only architecture achieving more than 100GFlop/s in the SpMM comparison.
7 Conclusion and Future Work
The paper reports absolute Xeon Phi performance results for SpMV and SpMM and finds the investigated kernels latency bound. It concludes that Xeon Phi performs strongly, especially for SpMM, while future optimization must address locality and data partitioning.
- The study analyzes Xeon Phi performance on SpMV and SpMM and reports, to the authors’ knowledge, the first absolute performance results for the coprocessor.
- The investigated sparse matrix kernels are latency bound, while the relatively small 512kB L2 cache per core is not identified as a problem.
- With 61 cores, Xeon Phi makes existing optimization approaches variably useful and increases the importance of storage schemes, intra-core locality, and data partitioning.Large inputs transferred to multiple caches can negatively affect performance.
- Xeon Phi’s SpMV and especially SpMM performance is reported as superior to the tested cutting-edge processors and accelerators, attributed to wide registers and vectorization capabilities.