# Presentation: 937425

## Tuning Sparse Matrix Vector Multiplication for multi-core SMPs(details in paper at SC07)

- 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 auto-tuned 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 auto-tuned serial kernel (OSKI)
- Show Cell delivers good performance and efficiency, while Niagara2 delivers good performance and productivity

## 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(2 implementations)

**Cache+Pthreads SpMV**
**implementation**

**Local Store SpMV**
**Implementation**

## Multicore SMP Systems(cache)

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

**4MB**

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

**4MB**

**Notes:**
Aggregate cache

## Multicore SMP Systems(peak flops)

**75 Gflop/s**
**(TLP + ILP + SIMD)**

**17 Gflop/s**
**(TLP + ILP)**

**29 Gflop/s**
**(TLP + ILP + SIMD)**

**11 Gflop/s**
**(TLP)**

**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

- Performance across suite
- Also, 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
- x86 core delivers > 10x performance of Niagara2 thread

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

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

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

**Pthread Implementation****for Cache-Based Machines**

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

## Naïve Parallel Performance

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

- Simple row parallelization
- Pthreads (didn’t have to be)
- 1P Niagara2 > 2x5x 2P x86 machines

**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**

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

**8x cores = 1.9x performance**

**4x cores = 1.5x performance**

**64x threads = 41x performance**

- Simple row parallelization
- Pthreads (didn’t have to be)
- 1P Niagara2 > 2x5x 2P x86 machines

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

## Naïve Parallel Performance

**Naïve Parallel Performance**

- 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**

- Simple row parallelization
- Pthreads (didn’t have to be)
- 1P Niagara2 > 2x5x 2P x86 machines

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

## Case for Auto-tuning

- How do we deliver good performance across all these architectures, across all matrices without exhaustively optimizing every combination
- Auto-tuning (in general)
- Write a Perl script that generates all possible optimizations
- Heuristically, or exhaustively searches the optimizations
- Existing SpMV solution: OSKI (developed at UCB)
- This work:
- Tuning geared toward 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 

## Performance(+NUMA & SW Prefetching)

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

- NUMA aware allocation
- Tag prefetches with the appropriate temporal locality
- Tune for the optimal distance

**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)

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

- Very significant on some
- missed the boat on others

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

## Performance(+cache & TLB blocking)

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

- Cache blocking geared towards sparse accesses

**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) 
Useful on the most challenging matrices (3x on LP on Opteron)

## Performance(more DIMMs,firmware fix ...)

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

## Performance(more DIMMs,firmware fix ...)

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

- 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,firmware fix ...)

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

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

**3 essential optimizations:**
**  ****Parallelize, Prefetch, Compress**

**4 essential optimizations:**
**  ****Parallelize, NUMA, Prefetch, Compress**

**2 essential optimizations:**
**  ****Parallelize, Compress**

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

## Comments
Performance

- Performance

**Cell Implementation**

## Cell Implementation

**No vanilla C implementation (aside from the PPE)**
- In some cases, what were optional optimizations on cache based machines, are requirements for correctness on Cell
- Even SIMDized double precision is extremely weak
- Scalar double precision is unbearable
- Minimum register blocking is 2x1 (SIMDizable)
**Can increase memory traffic by 66%**
- Optional Cache blocking is now required 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
- Branchless implementation
- Despite the following performance numbers, Cell was still handicapped by double precision

## Performance(all)

**Performance****(all)**

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

- IBM Cell Broadband Engine

## Hardware Efficiency

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

**Hardware Efficiency**

- IBM Cell Broadband Engine

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

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

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

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

## Productivity

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

**Productivity**

- IBM Cell Broadband Engine

**3 essential optimizations:**
**  ****Parallelize, Prefetch, Compress**

**4 essential optimizations:**
**  ****Parallelize, NUMA, Prefetch, Compress**

**2 essential optimizations:**
**  ****Parallelize, Compress**

**5 essential optimizations:**
**  ****Parallelize, NUMA, DMA, Compress, Cache(LS) Block**

## Parallel Efficiency

**Parallel Efficiency**

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

- IBM Cell Broadband Engine

## Parallel Efficiency(breakdown)

**Parallel Efficiency****(breakdown)**

- Intel Clovertown

- AMD Opteron

- Sun Niagara2

- IBM Cell Broadband Engine

- multicore

- multicore

- multicore

- multicore

- multisocket

- multisocket

- multisocket

- MT

## 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
- = good autotuned shared memory MPI implementation

- Intel Clovertown

- AMD Opteron

## Summary

## Median Performance & Efficiency

**Median Performance & Efficiency**

- 1P Niagara2 was consistently better than 2P x86 machines (more potential bandwidth)
- Cell delivered by far the best performance (better utilization)

- Used digital power meter to measure sustained system power
- FBDIMM is power hungry (12W/DIMM)
- Clovertown(330W)
- Niagara2 (350W) power

## Summary

**Paradoxically**, the most complex/advanced architectures required the most tuning, and delivered the lowest performance.
- Niagara2 delivered both very good performance and productivity
- Cell delivered very good performance and efficiency
- 90% of memory bandwidth (most get ~50%)
- High power efficiency
- Easily understood performance
- Extra traffic = lower performance (future work can address this)
**Our multicore specific autotuned implementation significantly outperformed an autotuned MPI implementation**
- It exploited:
- Matrix compression geared towards multicore, rather than single
- NUMA
- Prefetching

## Acknowledgments

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

## Questions?

## Backup Slides

## 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)

## 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**

## 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)

## 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, ...