# Presentation: 937426

## Tuning Sparse Matrix Vector Multiplication for multi-core SMPs

- Samuel Williams1,2, Richard Vuduc3, Leonid Oliker1,2,
- John Shalf2, Katherine Yelick1,2, James Demmel1,2
- 	1University of California Berkeley	2Lawrence Berkeley National Laboratory	3Georgia Institute of Technology
*samw@cs.berkeley.edu*

## Overview

- Multicore is the de facto performance solution for the next decade
- Examined Sparse Matrix Vector Multiplication (SpMV) kernel
- Important HPC kernel
- Memory intensive
- Challenging for multicore
- Present two autotuned threaded implementations:
- Pthread, cache-based implementation
- Cell local store-based implementation
- Benchmarked performance across 4 diverse multicore architectures
- Intel Xeon (Clovertown)
- AMD Opteron
- Sun Niagara2
- IBM Cell Broadband Engine
- Compare with leading MPI implementation(PETSc) with an autotuned serial kernel (OSKI)

## Sparse Matrix Vector Multiplication

- Sparse Matrix
- Most entries are 0.0
- Performance advantage in only
- 	storing/operating on the nonzeros
- Requires significant meta data
- Evaluate y=Ax
- A is a sparse matrix
- x & y are dense vectors
- Challenges
- Difficult to exploit ILP(bad for superscalar),
- Difficult to exploit DLP(bad for SIMD)
- Irregular memory access to source vector
- Difficult to load balance
**Very low computational intensity  (often >6 bytes/flop)**

- A

- x

- y

## Dataset (Matrices)
Multicore SMPs

- Multicore SMPs

**Test Suite**

## Matrices Used

- Pruned original SPARSITY suite down to 14
- none should fit in cache
- Subdivided them into 4 categories
- Rank ranges from 2K to 1M

- Dense

- Protein

- FEM /
- Spheres

- FEM /
- Cantilever

- Wind
- Tunnel

- FEM /
- Harbor

- QCD

- FEM /
- Ship

- Economics

- Epidemiology

- FEM /
- Accelerator

- Circuit

- webbase

- LP

- 2K x 2K Dense matrix
- stored in sparse format

- Well Structured
- (sorted by nonzeros/row)

- Poorly Structured
- hodgepodge

- Extreme Aspect Ratio
- (linear programming)

**Notes:**
I’ll keep this order throughout the paper

## Multicore SMP Systems

**Notes:**
Note, 3 are dual socket SMPs, + the single N2
Note, N2 is 8 threads/core

## Multicore SMP Systems(memory hierarchy)

**Conventional Cache-based**
**Memory Hierarchy**

**Disjoint Local Store**
**Memory Hierarchy**

## Multicore SMP Systems(cache)

**16MB**
**(vectors fit)**

**4MB**

**4MB**
**(local store)**

**4MB**

**Notes:**
Aggregate cache

## Multicore SMP Systems(peak flops)

**75 Gflop/s**
**(w/SIMD)**

**17 Gflop/s**

**29 Gflop/s**
**(w/SIMD)**

**11 Gflop/s**

**Notes:**
If we were to judge performance
Difficult to exploit SIMD on SPMV(Cell / Clovertown)

## Multicore SMP Systems(peak read bandwidth)

**21 GB/s**

**21 GB/s**

**51 GB/s**

**43 GB/s**

**Notes:**
Low Arithmetic intensity

## Multicore SMP Systems(NUMA)

**Uniform Memory Access**

**Non-Uniform Memory Access**

## Naïve Implementation

- For cache-based machines
- Included a median performance number

**Notes:**
Vanilla c
Cache based
Median number

## vanilla C Performance

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

- Vanilla C implementation
- Matrix stored in CSR (compressed sparse row)
- Explored compiler options - only the best is presented here

**Notes:**
x86 core = 10x Niagara2 thread
Will this carry thru MC/MT?

## Optimized for multicore/threading
Variety of shared memory programming models
   are acceptable(not just Pthreads)
More colors = more optimizations = more work 

- Variety of shared memory programming models
-    are acceptable(not just Pthreads)
- More colors = more optimizations = more work

**Pthread Implementation**

**Notes:**
More colors = more optimzations = more work = less productivity

## Parallelization

- Matrix partitioned by rows and balanced by the number of nonzeros
- SPMD like approach
- A barrier() is called before and after the SpMV kernel
- Each sub matrix stored separately in CSR
- Load balancing can be challenging
- # of threads explored in powers of 2 (in paper)

## Naïve Parallel Performance

- Naïve Pthreads

- Naïve Single Thread

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

**Notes:**
Note stacked format!!! (not a breakdown, 2 configurations plotted on top each other)
Poor scaling on x86

## Naïve Parallel Performance

**Naïve Parallel Performance**

- Naïve Pthreads

- Naïve Single Thread

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

**8x cores = 1.9x performance**

**4x cores = 1.5x performance**

**64x threads = 41x performance**

**Notes:**
8 cores didn’t even give us 2x

## Naïve Parallel Performance

**Naïve Parallel Performance**

- Naïve Pthreads

- Naïve Single Thread

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

**1.4% of peak flops**
**29% of bandwidth**

**4% of peak flops**
**20% of bandwidth**

**25% of peak flops**
**39% of bandwidth**

**Notes:**
Just to show we’re not already memory bound...

## Case for Autotuning

- How do we deliver good performance across all these architectures, across all matrices without exhaustively optimizing every combination
- Autotuning
- Write a Perl script that generates all possible optimizations
- Heuristically, or exhaustively search the optimizations
- Existing SpMV solution: OSKI (developed at UCB)
- This work:
- Optimizations geared for multi-core/-threading
- generates SSE/SIMD intrinsics, prefetching, loop transformations, alternate data structures, etc...
- “prototype for parallel OSKI”

**Notes:**
OSKI, developed by Rich Vuduc WHILE in the BeBop group @ berkeley 

## Exploiting NUMA, Affinity

- Bandwidth on the Opteron(and Cell) can vary substantially based on placement of data
- Bind each sub matrix and the thread to process it together
- Explored libnuma, Linux, and Solaris routines
- Adjacent blocks bound to adjacent cores

- Opteron

- DDR2 DRAM

- Opteron

- DDR2 DRAM

- Opteron

- DDR2 DRAM

- Opteron

- DDR2 DRAM

- Opteron

- DDR2 DRAM

- Opteron

- DDR2 DRAM

**Single Thread**

**Multiple Threads,**
**One memory controller**

**Multiple Threads,**
**Both memory controllers**

## Performance (+NUMA)

- +NUMA/Affinity

- Naïve Pthreads

- Naïve Single Thread

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

## Performance (+SW Prefetching)

- +Software Prefetching

- +NUMA/Affinity

- Naïve Pthreads

- Naïve Single Thread

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

**Notes:**
Tuned for the optimal prefetch distance

## Matrix Compression

**Matrix Compression**

- For memory bound kernels, minimizing memory
- 	traffic should maximize performance
- Compress the meta data
- Exploit structure to eliminate meta data
**Heuristic**: select the compression that
- 	minimizes the matrix size:
- power of 2 register blocking
- CSR/COO format
- 16b/32b indices
- etc...
**Side effect**: matrix may be minimized to the point where it fits entirely in cache

**Notes:**
Impass if memory bound...
Compress redundant meta data

## Performance (+matrix compression)

- +Matrix Compression

- +Software Prefetching

- +NUMA/Affinity

- Naïve Pthreads

- Naïve Single Thread

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

**Notes:**
A couple of compression techniques can improve performance on many matrices

## Cache and TLB Blocking

- Accesses to the matrix and destination vector are streaming
- But, access to the source vector can be random
- Reorganize matrix (and thus access pattern) to maximize reuse.
- Applies equally to TLB blocking (caching PTEs)
**Heuristic**: block destination, then keep adding
- 	more columns as long as the number of
- 	source vector cache lines(or pages) touched
- 	is less than the cache(or TLB).  Apply all
- 	previous optimizations individually to each
- 	cache block.
**Search**:  neither, cache, cache&TLB
- Better locality at the expense of confusing
- 	the hardware prefetchers.

- A

- x

- y

**Notes:**
Some matrices are so large and poorly structured that caches can’t capture temporal and spatial locality
Different than conventional cache blocking (maximizes utilization)

## Performance (+cache blocking)

- +Cache/TLB Blocking

- +Matrix Compression

- +Software Prefetching

- +NUMA/Affinity

- Naïve Pthreads

- Naïve Single Thread

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

**Notes:**
Useful on the most challenging matrices (3x on LP on Opteron)

## Banks, Ranks, and DIMMs

- In this SPMD approach, as the number of threads increases, so to does the number of concurrent streams to memory.
- Most memory controllers have finite capability to reorder the requests.  (DMA can avoid or minimize this)
- Addressing/Bank conflicts become increasingly likely
- Add more DIMMs, configuration of ranks can help
- Clovertown system was already fully populated

**Notes:**
As a rather expensive solution, ...

## Performance (more DIMMs, ...)

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

## Performance (more DIMMs, ...)

**Performance (more DIMMs, ...)**

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

**4% of peak flops**
**52% of bandwidth**

**20% of peak flops**
**66% of bandwidth**

**52% of peak flops**
**54% of bandwidth**

**Notes:**
Done with optimizations for cache based machines

## Performance (more DIMMs, ...)

**Performance (more DIMMs, ...)**

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

**3 essential optimizations**

**4 essential optimizations**

**2 essential optimizations**

**Notes:**
Note how much work was required !!!

## Comments
Performance

- Performance

**Cell Implementation**

## Cell Implementation

**No vanilla C implementation (aside from the PPE)**
- Even SIMDized double precision is extremely weak
- Scalar double precision is unbearable
- Minimum register blocking is 2x1 (SIMDizable)
**Can increase memory traffic by 66%**
- Cache blocking optimization is transformed into local store blocking
**Spatial and temporal locality is captured by software when the matrix is optimized**
- In essence, the high bits of column indices are grouped into DMA lists
- No branch prediction
- Replace branches with conditional operations
- In some cases, what were optional optimizations on cache based machines, are requirements for correctness on Cell
- Despite the performance, Cell is still handicapped by double precision

## Performance

**Performance**

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

- IBM Cell Broadband Engine

## Performance

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

**Performance**

- IBM Cell Broadband Engine

**39% of peak flops**
**89% of bandwidth**

## Multicore MPI Implementation

- This is the default approach to programming multicore

## Multicore MPI Implementation

- Used PETSc with shared memory MPICH
- Used OSKI (developed @ UCB) to optimize each thread
- = Highly optimized MPI

- Intel Clovertown

- AMD Opteron

## Summary

## Median Performance & Efficiency

**Median Performance & Efficiency**

- Used digital power meter to measure sustained system power
- FBDIMM drives up Clovertown and Niagara2 power
- Right: sustained MFlop/s / sustained Watts
- Default approach(MPI) achieves very low performance and efficiency

## Summary

**Paradoxically**, the most complex/advanced architectures required the most tuning, and delivered the lowest performance.
- Most machines achieved less than 50-60% of DRAM bandwidth
- Niagara2 delivered both very good performance and productivity
- Cell delivered very good performance and efficiency
- 90% of memory bandwidth
- High power efficiency
- Easily understood performance
- Extra traffic = lower performance (future work can address this)
**multicore specific autotuned implementation significantly outperformed a state of the art MPI implementation**
- Matrix compression geared towards multicore
- NUMA
- Prefetching

## Acknowledgments

- UC Berkeley
- RADLab Cluster (Opterons)
- PSI cluster(Clovertowns)
- Sun Microsystems
- Niagara2
- Forschungszentrum Jülich
- Cell blade cluster

## Questions?