The chapter authors (Albert-Jan N. Yzelman, Dirk Roose, and Karl Meerbergen) note that, “Current hardware trends lead to an increasing width of vector units as well as to decreasing effective bandwidth-per-core. For sparse computations these two trends conflict.” For this reason they designed a usable and efficient data structure for vectorized sparse computations on multi-core architectures with vector processing capabilities – like Intel Xeon Phi. This data structures helps with the difficulties in achieving a high performance for sparse matrix–vector (SpMV) multiplications caused by a low flop-to-byte ratio and inefficient cache use. Results are presented for sparse matrix multiplication and transpose.
The final vectorized BICRS data structure that separates the relative encoding of pq −1 nonzeroes in each block from the BICRS encoding of each of the leading nonzeroes of all blocks
- These two encodings are then combined in the final vectorized data structure.
- The figure illustrates 2×2 blocking on an 4×4 matrix with 10 nonzeroes ordered according to a Hilbert curve.
- This results in 4 blocks, containing 6 explicit zeroes.
Illustration of the final vectorized BICRS data structure. (Courtesy Morgan Kaufmann)
The following show performance improvements for sparse matrix multiplication for Intel Xeon Phi and Xeon using optimizations discussed in this chapter. The baseline is OpenMP CRS, successively augmented with:
- Partial data distribution
- sparse blocking with Hilbert ordering
- Vectorized BICRS data structure.
Courtesy Morgan Kaufmann
Courtesy Morgan Kaufmann
The following show performance optimizations for sparse matrix transpose for Intel Xeon Phi and Xeon. The performance of each possible blocking size (1×4, 2×2, and 4×1) is compared against results obtained using onvectorized BICRS (1×1).
Courtesy Morgan Kaufmann
Courtesy Morgan Kaufmann
Chapter Authors
Albert-Jan N. Yzelman
Albert-Jan is a postdoctoral researcher at the department of Computer Science, KU Leuven, Belgium. He works within the ExaScience Life Lab on sparse matrix computations, high performance computing, and general parallel programming
Dirk Roose
Dirk is a professor at the department of Computer Science, KU Leuven, Belgium. His research focuses on numerical methods for computational science and engineering and on algorithms for parallel scientific computing.
Karl Meerbergen
Karl is a professor at the department of Computer Science, KU Leuven, Belgium. His research focuses on large scale numerical linear algebra.
Click to see the overview article “Teaching The World About Intel Xeon Phi” that contains a list of TechEnablement links about why each chapter is considered a “Parallelism Pearl” plus information about James Reinders and Jim Jeffers, the editors of High Performance Parallelism Pearls.
Leave a Reply