# Presentation: 606906

## The Roofline Model:A pedagogical tool for program analysis and optimization

**ParLab Summer Retreat**
- Samuel Williams, David Patterson
*samw@cs.berkeley.edu*

## Motivation

- Performance and scalability of multicore architectures can be extremely non-intuitive to novice programmers
- Success of the multicore paradigm should be premised on augmenting the abilities of the world’s programmers

## Goals & Audience

- Focused on:
**	****	****rates and efficiencies (Gflop/s, % of peak)**,
- Goals for Roofline:
- Provide everyone with a graphical aid that provides:
**	****	****realistic expectations of performance and productivity**
- Show inherent hardware limitations for a given kernel
- Show potential benefit and priority of optimizations
- Who’s not the audience for the Roofline:
- Not for those interested in fine tuning (+5%)
- Not for those challenged by parallel kernel correctness

## Principal Components of Performance

## Components

- There are three principal components to performance:
**Computation**
**Communication**
**Locality**
- Each architecture has a different balance between these
- Each kernel has a different balance between these
- Performance is a question of how well an kernel’s characteristics map to an architecture’s characteristics

## Computation

- For us, floating point performance (**Gflop/s**) is the metric of interest (typically double precision)
- Peak in-core performance can only be attained if:
- fully exploit ILP, DLP, FMA, etc...
- non-FP instructions don’t sap instruction bandwidth
- threads don’t diverge (GPUs)
- transcendental/non pipelined instructions are used sparingly
- branch mispredictions are rare
- To exploit a form of in-core parallelism, it must be:
- Inherent in the algorithm
- Expressed in the high level implementation
- Explicit in the generated code

## Communication

- For us, DRAM bandwidth (**GB/s**) is the metric of interest
- Peak bandwidth can only be attained if certain optimizations are employed:
- Few unit stride streams
- NUMA allocation and usage
- SW Prefetching
- Memory Coalescing (GPU)

## Locality

- Computation is free, Communication is expensive.
- Maximize locality to minimize communication
**There is a lower limit to communication: compulsory traffic**
- Hardware changes can help minimize communication
- Larger cache capacities minimize capacity misses
- Higher cache associativities minimize conflict misses
- Non-allocating caches minimize compulsory traffic
- Software optimization can also help minimize communication
- Padding avoids conflict misses
- Blocking avoids capacity misses
- Non-allocating stores minimize compulsory traffic

## Roofline Model

## Integrating Components...

- Goal: integrate in-core performance, memory bandwidth, and locality into a single readily understandable performance figure
- Also, must graphically show the penalty associated with not including certain software optimizations
- Roofline model will be unique to each architecture
- Coordinates of a kernel are ~unique to each architecture

## What relates GB/s to GFlop/s ?

- Through dimensional analysis, its clear that **Flops:Bytes** is the parameter that allows us to convert bandwidth (GB/s) to performance (GFlop/s)
- This is a well known quantity: **Arithmetic Intensity** (discussed later)
- When we measure total bytes, we incorporate all cache behavior (the 3C’s) and Locality

## Basic Roofline

- Performance is upper bounded by both the peak flop rate, and the product of streaming bandwidth and the flop:byte ratio

**Gflop/s = min **

**Peak Gflop/s**

**Stream BW * actual flop:byte ratio**

## notes

*Bandwidth #’s collected via micro benchmarks*
*Computation #’s derived from optimization manuals (pencil and paper)*
*Assume complete overlap of either communication or computation*

## Roofline model for Opteron(adding ceilings)

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- AMD Opteron 2356
- (Barcelona)

- Peak roofline performance
- based on manual for
- 	**single precision peak**
- and a hand tuned stream read for bandwidth

- 1

- peak SP

- peak stream bandwidth

**Log scale !**

**Log scale !**

## Roofline model for Opteron(adding ceilings)

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- AMD Opteron 2356
- (Barcelona)

- Peak roofline performance
- based on manual for
- 	**single precision peak**
- and a hand tuned stream read for bandwidth

- 1

- peak SP

- peak stream bandwidth

## Roofline model for Opteron(adding ceilings)

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- AMD Opteron 2356
- (Barcelona)

- Opterons have separate multipliers and adders
- ‘functional unit parallelism’
- This is a ceiling beneth the roofline

- 1

- peak SP

- mul / add imbalance

- peak stream bandwidth

## Roofline model for Opteron(adding ceilings)

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- AMD Opteron 2356
- (Barcelona)

- In single precision, SIMD is 4x32b.
- If only the _ss versions are used, performance is 1/4

- 1

- peak SP

- mul / add imbalance

- peak stream bandwidth

- w/out SIMD

## Roofline model for Opteron(adding ceilings)

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- AMD Opteron 2356
- (Barcelona)

- If 4 independent instructions are kept in the pipeline, performance will fall

- 1

- peak SP

- mul / add imbalance

- w/out ILP

- peak stream bandwidth

- w/out SIMD

## Roofline model for Opteron(adding ceilings)

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- AMD Opteron 2356
- (Barcelona)

- If SW prefetching is not used, performance will degrade
- These act as ceilings below the bandwidth roofline

- 1

- peak SP

- mul / add imbalance

- w/out ILP

- peak stream bandwidth

- w/out SW prefetching

- w/out SIMD

## Roofline model for Opteron(adding ceilings)

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- AMD Opteron 2356
- (Barcelona)

- Without NUMA optimizations, the memory controllers on the second socket can’t be used.

- 1

- peak SP

- mul / add imbalance

- w/out ILP

- peak stream bandwidth

- w/out SW prefetching

- w/out NUMA optimizations

- w/out SIMD

## Roofline model for Opteron(adding ceilings)

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- AMD Opteron 2356
- (Barcelona)

- Bandwidth is much lower without unit stride streams

- 1

- peak SP

- mul / add imbalance

- w/out ILP

- peak stream bandwidth

- w/out SW prefetching

- w/out NUMA optimizations

- w/out SIMD

- w/out unit stride streams

## Roofline model for Opteron(adding ceilings)

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- AMD Opteron 2356
- (Barcelona)

- Its difficult for any architecture to reach the raw DRAM bandwidth

- 1

- peak SP

- mul / add imbalance

- w/out ILP

- peak stream bandwidth

- w/out SW prefetching

- w/out NUMA optimizations

- w/out SIMD

- w/out unit stride streams

- raw DRAM bandwidth

## Roofline model for Opteron(adding ceilings)

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- Partitions the regions of expected performance into three optimization regions:
- Compute only
- Memory only
- Compute+Memory

- 1

- peak SP

- AMD Opteron 2356
- (Barcelona)

- mul / add imbalance

- w/out ILP

- peak stream bandwidth

- w/out SW prefetching

- w/out NUMA optimizations

- w/out SIMD

- w/out unit stride streams

## Uniqueness

- There is no single ordering or roofline model
- The order of ceilings is generally (bottom up):
- What is inherent in algorithm
- What a compiler is likely to provide
- What a programmer could provide
- What can never be exploited for this kernel
- For example,
- FMA or mul/add balance is inherent in many linear algebra routines and should be placed at the bottom.
- However, many stencils are dominated by adds, and thus the multipliers and FMA go underutilized.

## Arithmetic Intensity in HPC

**Arithmetic Intensity (AI) ~ Total Flops / Total DRAM Bytes**
- Some HPC kernels have an arithmetic intensity that’s constant, but on others it scales with with problem size (increasing temporal locality)
- Actual arithmetic intensity is capped by cache/local store capacity

## Accurately Determining the true Flop:DRAM Byte ratio

- Remember the 3C’s of caches
- Calculating the Flop:DRAM byte ratio is:
**Compulsory misses**: straightforward
**Capacity misses**: pencil and paper (maybe performance counters)
**Conflict misses**: must use performance counters
- Flop:actual DRAM Byte ratio < Flop:compulsory DRAM Byte ratio
- One might place a range on the arithmetic intensity ratio
- Thus performance is limited to an area between the ceilings and between the upper (compulsory) and lower bounds on arithmetic intensity

## Roofline model for Opteron(powerpoint doodle)

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- Final Roofline

- 1

- peak SP

- AMD Opteron 2356
- (Barcelona)

- mul / add imbalance

- w/out ILP

- peak stream bandwidth

- w/out SW prefetching

- w/out NUMA optimizations

- w/out SIMD

## Roofline model for Opteron(powerpoint doodle)

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- Some arbitrary kernel has a flop:compulsory byte ratio of 4
- Overlaid on the roofline
- Defines upper bound on range of expected performance
- Also shows which optimizations are likely

- 1

- peak SP

- AMD Opteron 2356
- (Barcelona)

- mul / add imbalance

- w/out ILP

- peak stream bandwidth

- w/out SW prefetching

- w/out NUMA optimizations

- w/out SIMD

-  compulsory misses

## Roofline model for Opteron(powerpoint doodle)

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- Capacity misses reduce the actual flop:byte ratio
- Also reduces attainable performance
**AI is unique to each combination of kernel and architecture**

- 1

- peak SP

- AMD Opteron 2356
- (Barcelona)

- mul / add imbalance

- w/out ILP

- peak stream bandwidth

- w/out SW prefetching

- w/out NUMA optimizations

- w/out SIMD

-  compulsory misses

- capacity

## Roofline model for Opteron(powerpoint doodle)

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- Conflict misses may destroy performance
**AI is unique to each combination of kernel and architecture**

- 1

- peak SP

- AMD Opteron 2356
- (Barcelona)

- mul / add imbalance

- w/out ILP

- peak stream bandwidth

- w/out SW prefetching

- w/out NUMA optimizations

- w/out SIMD

-  compulsory misses

- capacity

- conflict

## Roofline model for Opteron(powerpoint doodle)

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- Conflict misses may destroy performance

- 1

- peak SP

- AMD Opteron 2356
- (Barcelona)

- mul / add imbalance

- w/out ILP

- peak stream bandwidth

- w/out SW prefetching

- w/out NUMA optimizations

- w/out SIMD

-  compulsory misses

- capacity

- conflict

**Doubling cache capacity doesn’t double the arithmetic intensity!**

## Three Categories of Software Optimization

## Maximizing Attained in-core Performance

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- Software optimizations such as explicit SIMDization can punch through the horizontal ceilings (what can be expected from a compiler)
- Other examples include loop unrolling, reordering, and long running loops

- 1

- peak SP

- AMD Opteron 2356
- (Barcelona)

- mul / add imbalance

- w/out ILP

- peak stream bandwidth

- w/out SW prefetching

- w/out NUMA optimizations

- w/out SIMD

-  compulsory misses

- capacity

- conflict

## Maximizing AttainedMemory Bandwidth

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- Compilers won’t give great out-of-the box bandwidth
- Punch through bandwidth ceilings:
- Maximize MLP
- long unit stride accesses
- NUMA aware allocation and parallelization
- SW prefetching

- 1

- peak SP

- AMD Opteron 2356
- (Barcelona)

- mul / add imbalance

- w/out ILP

- peak stream bandwidth

- w/out SW prefetching

- w/out NUMA optimizations

- w/out SIMD

-  compulsory misses

- capacity

- conflict

## Minimizing Memory Traffic

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- Use performance counters to measure flop:byte ratio (AI)
- Out-of-the-box code may have an AI ratio much less than the compulsory ratio
- Be cognizant of cache capacities, associativities, and threads sharing it
- Pad structures to avoid conflict misses
- Use cache blocking to avoid capacity misses
**These optimizations can be imperative**

- 1

- peak SP

- AMD Opteron 2356
- (Barcelona)

- mul / add imbalance

- w/out ILP

- peak stream bandwidth

- w/out SW prefetching

- w/out NUMA optimizations

- w/out SIMD

- capacity

- conflict

-  compulsory misses

## Effective Roofline (before)

-  compulsory misses

**Effective Roofline (before)**

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- Before optimization, traffic, and limited bandwidth optimization limits performance to a very narrow window

- 1

- peak SP

- AMD Opteron 2356
- (Barcelona)

- mul / add imbalance

- w/out ILP

- peak stream bandwidth

- w/out SW prefetching

- w/out NUMA optimizations

- w/out SIMD

- capacity

- conflict

## Effective Roofline (after)

- 2

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- After optimization, ideally, performance is significantly better

- 1

- peak SP

- AMD Opteron 2356
- (Barcelona)

- mul / add imbalance

- w/out ILP

- peak stream bandwidth

- w/out SW prefetching

- w/out NUMA optimizations

- w/out SIMD

- capacity

- conflict

-  compulsory misses

## Applicable to Other Architectural Paradigms ?

## Four Architectures

- Sun Victoria Falls

- AMD Barcelona

- NVIDIA G80

- IBM Cell Blade

## Four Architectures

- Sun Victoria Falls

- AMD Barcelona

- NVIDIA G80

- IBM Cell Blade

- One Thread / Core

- Multithreaded Cores

## Four Architectures

- Sun Victoria Falls

- AMD Barcelona

- NVIDIA G80

- IBM Cell Blade

- Cache-based

- Local Store-based

## 32b Rooflines for the Four(in-core parallelism)

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s (32b)

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s (32b)

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s (32b)

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- Sun Victoria Falls

- AMD Barcelona

- NVIDIA G80

- Single Precision Roofline models for the SMPs used in this work.
- Based on micro-benchmarks, experience, and manuals
- Ceilings =
- 		in-core parallelism
**Can the compiler find all this parallelism ?**
- NOTE:
- log-log scale
- Assumes perfect SPMD

- 4

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s (32b)

- 8

- 16

- 32

- 64

- 128

- 256

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- IBM Cell Blade

- 4

- 8

- 16

- 32

- 64

- 128

- 256

- 4

- 8

- 16

- 32

- 64

- 128

- 256

- 4

- 8

- 16

- 32

- 64

- 128

- 256

- 512

- 512

- 512

- 512

- peak SP

- mul / add imbalance

- w/out SIMD

- w/out ILP

- peak SP

- peak SP

- w/out FMA

- w/out SIMD

- w/out ILP

- peak SP

- w/out FMA

- w/out memory coalescing

- w/out NUMA

- w/out SW prefetch

- w/out NUMA

- w/out SW prefetch

- w/out NUMA

- w/out DMA concurrency

**Notes:**
Look for each architecture’s Achilles’ Heel

## 32b Rooflines for the Four(diverged threads)

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s (32b)

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s (32b)

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s (32b)

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- Sun Victoria Falls

- AMD Barcelona

- NVIDIA G80

- G80 dynamically finds DLP (shared instruction fetch)
**SIMT**
- If threads of a warp diverge from SIMD execution, performance is limited by instruction issue bandwidth
- Ceilings on G80 =
- 	number of unique PCs when threads diverge

- 4

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s (32b)

- 8

- 16

- 32

- 64

- 128

- 256

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- IBM Cell Blade

- 4

- 8

- 16

- 32

- 64

- 128

- 256

- 4

- 8

- 16

- 32

- 64

- 128

- 256

- 4

- 8

- 16

- 32

- 64

- 128

- 256

- 512

- 512

- 512

- 512

- peak SP

- mul / add imbalance

- w/out SIMD

- w/out ILP

- peak SP

- peak SP

- w/out FMA

- w/out SIMD

- w/out ILP

- w/out NUMA

- w/out SW prefetch

- w/out NUMA

- w/out SW prefetch

- w/out NUMA

- w/out DMA concurrency

- peak SP

- 4 PCs

- w/out memory coalescing

- 8 PCs

- 16 PCs

- 32 PCs

## 32b Rooflines for the Four(FP fraction of dynamic instructions)

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s (32b)

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s (32b)

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s (32b)

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- Sun Victoria Falls

- AMD Barcelona

- NVIDIA G80

- Some kernels have large numbers of non FP instructions
- Saps instruction issue bandwidth
- Ceilings = FP fraction of dynamic instruction mix
- NOTE:
- Assumes perfect in-core parallelism

- 4

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s (32b)

- 8

- 16

- 32

- 64

- 128

- 256

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- IBM Cell Blade

- 4

- 8

- 16

- 32

- 64

- 128

- 256

- 4

- 8

- 16

- 32

- 64

- 128

- 256

- 4

- 8

- 16

- 32

- 64

- 128

- 256

- 512

- 512

- 512

- 512

- w/out SW prefetch

- w/out SW prefetch

- peak SP

- w/out NUMA

- FP = 25%

- FP = 12%

- FP = 6%

- peak SP

- w/out NUMA

- w/out DMA concurrency

- FP = 25%

- FP = 12%

- FP = 6%

- peak SP

- w/out NUMA

- FP = 25%

- FP = 12%

- peak SP

- w/out memory coalescing

- FP = 50%

- FP = 25%

- FP = 12%

- FP = 6%

## 32b Rooflines for the Four(ridge point)

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s (32b)

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s (32b)

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s (32b)

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- Sun Victoria Falls

- AMD Barcelona

- NVIDIA G80

- Some architectures have drastically different
- 	ridge points
- VF may be compute bound on many kernels
- Clovertown has 1/3 the BW of Barcelona = ridge point to the right

- 4

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s (32b)

- 8

- 16

- 32

- 64

- 128

- 256

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- IBM Cell Blade

- 4

- 8

- 16

- 32

- 64

- 128

- 256

- 4

- 8

- 16

- 32

- 64

- 128

- 256

- 4

- 8

- 16

- 32

- 64

- 128

- 256

- 512

- 512

- 512

- 512

- w/out SW prefetch

- w/out SW prefetch

- peak SP

- w/out NUMA

- FP = 25%

- FP = 12%

- FP = 6%

- peak SP

- w/out NUMA

- w/out DMA concurrency

- FP = 25%

- FP = 12%

- FP = 6%

- peak SP

- w/out NUMA

- FP = 25%

- FP = 12%

- peak SP

- w/out memory coalescing

- FP = 50%

- FP = 25%

- FP = 12%

- FP = 6%

## Using Roofline when Auto-tuningHPC Kernels

## Multicore SMPs Used

- AMD Opteron 2356 (Barcelona)

- Intel Xeon E5345 (Clovertown)

- IBM QS20 Cell Blade

- Sun T2+ T5140 (Victoria Falls)

## Sparse Matrix-Vector Multiplication (SpMV)

- Samuel Williams, Leonid Oliker, Richard Vuduc, John Shalf, Katherine Yelick, James Demmel, "Optimization of Sparse Matrix-Vector Multiplication on Emerging Multicore Platforms", Supercomputing (SC), 2007.

## 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 arithmetic intensity  (often <0.166 flops/byte)**
**	****= likely memory bound**

## Roofline model for SpMV

- Double precision roofline models
- FMA is inherent in SpMV (place at bottom)

**No naïve Cell**
**implementation**

## Roofline model for SpMV

- Two unit stride streams
- Inherent FMA
- No ILP
- No DLP
- FP is 12-25%
- Naïve compulsory flop:byte < 0.166

**No naïve Cell**
**implementation**

## Roofline model for SpMV(out-of-the-box parallel)

- Two unit stride streams
- Inherent FMA
- No ILP
- No DLP
- FP is 12-25%
- Naïve compulsory flop:byte < 0.166
- For simplicity: dense matrix in sparse format

**No naïve Cell**
**implementation**

## Roofline model for SpMV(NUMA & SW prefetch)

- compulsory flop:byte ~ 0.166
- utilize all memory channels

**No naïve Cell**
**implementation**

## Roofline model for SpMV(matrix compression)

- Inherent FMA
- Register blocking improves ILP, DLP, flop:byte ratio, and FP% of instructions

## Lattice-Boltzmann Magneto-Hydrodynamics (LBMHD)

- Samuel Williams, Jonathan Carter, Leonid Oliker, John Shalf, Katherine Yelick, "Lattice Boltzmann Simulation Optimization on Leading Multicore Platforms", International Parallel & Distributed Processing Symposium (IPDPS), 2008.
**Best Paper, Application Track**

## LBMHD

- Plasma turbulence simulation via Lattice Boltzmann Method
- Two distributions:
- momentum distribution (27 scalar components)
- magnetic distribution (15 vector components)
- Three macroscopic quantities:
- Density
- Momentum (vector)
- Magnetic Field (vector)
- Must read 73 doubles, and update 79 doubles per point in space
- Requires about 1300 floating point operations per point in space
- Just over 1.0 flops/byte (ideal)

## Roofline model for LBMHD

- Huge datasets
- NUMA allocation/access
- Little ILP
- No DLP
- Far more adds than multiplies (imbalance)
**Essentially random access to memory**
- Flop:byte ratio ~0.7
- High conflict misses

**No naïve Cell**
**implementation**

## Roofline model for LBMHD(out-of-the-box code)

- Huge datasets
- NUMA allocation/access
- Little ILP
- No DLP
- Far more adds than multiplies (imbalance)
**Essentially random access to memory**
- Flop:byte ratio ~0.7
- High conflict misses
- Peak VF performance with 64 threads (our of 128) - high conflict misses

**No naïve Cell**
**implementation**

## Roofline model for LBMHD(Padding, Vectorization, Unrolling, Reordering)

- Vectorize the code to eliminate TLB capacity misses
- Ensures unit stride access (bottom bandwidth ceiling)
- Tune for optimal VL
- Clovertown pinned to lower BW ceiling

**No naïve Cell**
**implementation**

## Roofline model for LBMHD(SIMDization + cache bypass)

- Make SIMDization explicit
- Technically, this swaps ILP and SIMD ceilings
- Use cache bypass instruction: ***movntpd***
- Increases flop:byte ratio to ~1.0 on x86/Cell

## The Heat Equation Stencil 

- Kaushik Datta, Mark Murphy, Vasily Volkov, Samuel Williams, Jonathan Carter, Leonid Oliker, David Patterson, John Shalf, Katherine Yelick, “Stencil Computation Optimization and Autotuning on State-of-the-Art Multicore Architecture”, submitted to Supercomputing (SC), 2008.

## The Heat Equation Stencil

- PDE grid

- +Y

- +Z

- +X

- stencil for heat equation PDE

- y+1

- y-1

- x-1

- z-1

- z+1

- x+1

- x,y,z

- Explicit Heat equation on a regular grid
- Jacobi
- One double per point in space
- 7-point nearest neighbor stencil
- Must:
- read every point from DRAM
- perform 8 flops (linear combination)
- write every point back to DRAM
- Just over 0.5 flops/byte (ideal)
- Cache locality is important

## Roofline model for Stencil(out-of-the-box code)

- Large datasets
- 2 unit stride streams
- No NUMA
- Little ILP
- No DLP
- Far more adds than multiplies (imbalance)
- Ideal flop:byte ratio 1/3
- High locality requirements
- Capacity and conflict misses will severely impair flop:byte ratio

**No naïve Cell**
**implementation**

## Roofline model for Stencil(out-of-the-box code)

- Large datasets
- 2 unit stride streams
- No NUMA
- Little ILP
- No DLP
- Far more adds than multiplies (imbalance)
- Ideal flop:byte ratio 1/3
- High locality requirements
- Capacity and conflict misses will severely impair flop:byte ratio

**No naïve Cell**
**implementation**

## Roofline model for Stencil(NUMA, cache blocking, unrolling, prefetch, ...)

- Cache blocking helps ensure flop:byte ratio is as close as possible to 1/3
- Clovertown has huge caches but is pinned to lower BW ceiling
- Cache management is essential when capacity/thread is low

**No naïve Cell**
**implementation**

## Roofline model for Stencil(SIMDization + cache bypass)

- Make SIMDization explicit
- Technically, this swaps ILP and SIMD ceilings
- Use cache bypass instruction: ***movntpd***
- Increases flop:byte ratio to ~0.5 on x86/Cell

## Refining the Roofline

## Other performance metrics

- There is no reason either floating point (Gflop/s) must be the performance metric
- Could also use:
- Graphics (Pixels, Vertices, Textures)
- Crypto
- Integer
- Bitwise
- etc...

## For our kernels, DRAM bandwidth is the key communication component.
For other kernels, other bandwidths might be more appropriate
L2 bandwidth (e.g. DGEMM)
PCIe bandwidth (offload to GPU)
Network bandwidth
The example below shows zero overhead double buffered transfers to/from a GPU over PCIe x16
How bad is a SP stencil ?
What about SGEMM ?
No overlap / high overhead tends
	to smooth performance
Performance is half at ridge point

- For other kernels, other bandwidths might be more appropriate
- L2 bandwidth (e.g. DGEMM)
- PCIe bandwidth (offload to GPU)
- Network bandwidth
- The example below shows zero overhead double buffered transfers to/from a GPU over PCIe x16
- How bad is a SP stencil ?
- What about SGEMM ?
- No overlap / high overhead tends
- 	to smooth performance
- Performance is half at ridge point

**Other bandwidths**

- 1

- flop:PCIe byte ratio

- attainable Gflop/s (32b)

- 2

- 4

- 8

- 16

- 32

- 64

- 128

- NVIDIA G80

- 4

- 8

- 16

- 32

- 64

- 128

- 256

- 512

- peak SP

- FP = 50%

- FP = 25%

- FP = 12%

- FP = 6%

- full duplex

- half duplex

## Mix and match

- In general, you can mix and match as the kernel/architecture requires:
- e.g. all posibilities is the cross product of performance metrics with bandwidths
**	****{Gflop/s, GIPS, crypto, ...} ******** {L2, DRAM, PCIe, Network}  **

## Conclusions

- The Roofline Model provides an intuitive graph for kernel analysis and optimization
- Easily extendable to other architectural paradigms
- Easily extendable to other communication or computation metrics

## Questions ?

## BACKUP SLIDES

## Trends

- ILP is decreasing (shorter pipelines, multithreading)
- SIMD is becoming wider
- Bandwidth isn’t keeping up with #cores
- Application flop:byte is decreasing
- Cache/Local Store management is becoming critical

- 1.6%

- 1/8

- flop:DRAM byte ratio

- % of peak Gflop/s

- 3.1%

- 6.4%

- 12.5%

- 25.0%

- 50.0%

- 100%

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- 1

- peak SP

- mul / add imbalance

- w/out SIMD

- peak stream bandwidth

- w/out memory optimizations

- w/out ILP

## Trends

- ILP is decreasing (shorter pipelines, multithreading)
- SIMD is becoming wider
- Bandwidth isn’t keeping up with #cores
- Application flop:byte is decreasing
- Cache/Local Store management is becoming critical

- 1.6%

- 1/8

- flop:DRAM byte ratio

- % of peak Gflop/s

- 3.1%

- 6.4%

- 12.5%

- 25.0%

- 50.0%

- 100%

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- 1

- peak SP

- mul / add imbalance

- w/out SIMD

- peak stream bandwidth

- w/out memory optimizations

- w/out ILP

## Trends

- ILP is decreasing (shorter pipelines, multithreading)
- SIMD is becoming wider
- Bandwidth isn’t keeping up with #cores
- Application flop:byte is decreasing
- Cache/Local Store management is becoming critical

- 1.6%

- 1/8

- flop:DRAM byte ratio

- % of peak Gflop/s

- 3.1%

- 6.4%

- 12.5%

- 25.0%

- 50.0%

- 100%

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- 1

- peak SP

- mul / add imbalance

- w/out SIMD

- peak stream bandwidth

- w/out memory optimizations

- w/out ILP

## Trends

- ILP is decreasing (shorter pipelines, multithreading)
- SIMD is becoming wider
- Bandwidth isn’t keeping up with #cores
- Application flop:byte is decreasing
- Cache/Local Store management is becoming critical

- 1.6%

- 1/8

- flop:DRAM byte ratio

- % of peak Gflop/s

- 3.1%

- 6.4%

- 12.5%

- 25.0%

- 50.0%

- 100%

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- 1

- peak SP

- mul / add imbalance

- w/out SIMD

- peak stream bandwidth

- w/out memory optimizations

- w/out ILP

## Trends

- ILP is decreasing (shorter pipelines, multithreading)
- SIMD is becoming wider
- Bandwidth isn’t keeping up with #cores
- Application flop:byte is decreasing
- Cache/Local Store management is becoming critical

- 1.6%

- 1/8

- flop:DRAM byte ratio

- % of peak Gflop/s

- 3.1%

- 6.4%

- 12.5%

- 25.0%

- 50.0%

- 100%

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- 1

- peak SP

- mul / add imbalance

- w/out SIMD

- peak stream bandwidth

- w/out memory optimizations

- w/out ILP

## Alternate View (Barcelona)

- 2

- 1/2

- attainable GB/s

- attainable Gflop/s (32b)

- 4

- 8

- 16

- 32

- 64

- 128

- 1

- 2

- 4

- 8

- 16

- 32

- 64

- Same formalism can be plotted on different axis
- Difficult to plot AI

- 1

- peak SP

- mul / add imbalance

- w/out ILP

- peak stream bandwidth

- w/out SW prefetching

- w/out NUMA optimizations

- w/out SIMD

- w/out unit stride streams

## No Overlap

- What if computation or communication isn’t totally overlapped
- At ridgepoint 50% of the time is spent in each, so performance is cut in half
- In effect, the curves are smoothed
- Common for bulk synchonous MPI communication, atypical for DRAM access on modern architectures

## Roofline model for Opteron(non-overlapped)

**Roofline model for Opteron****(non-overlapped)**

- AMD Opteron (rev.F)

- Not typical of multi-thread/core architectures
- Not typical of architectures with ooo or HW prefetchers
- More common in network accesses

- 0.5

- 1.0

- 1/8

- flop:DRAM byte ratio

- attainable Gflop/s

- 2.0

- 4.0

- 8.0

- 16.0

- 32.0

- 64.0

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 16

- peak DP

- mul / add imbalance

- w/out
- ILP or SIMD

- peak stream bandwidth

- w/out SW prefetching

- w/out NUMA optimizations

## Auto-tuned Performance(+Cell/SPE version)

- Wrote a double precision Cell/SPE version
- DMA, local store blocked, NUMA aware, etc...
- Only 2x1 and larger BCOO
- Only the SpMV-proper routine changed
- About 12x faster (median) than using the PPEs alone.

- +More DIMMs(opteron),
- +FW fix, array padding(N2), etc...

- +Cache/TLB Blocking

- +Compression

- +SW Prefetching

- +NUMA/Affinity

- Naïve Pthreads

- Naïve

## Auto-tuned Performance(Local Store Implementation)

- First attempt at cell implementation.
- VL, unrolling, reordering fixed
- No NUMA
- Exploits DMA and double buffering to load vectors
- Straight to SIMD intrinsics.
- Despite the relative performance, Cell’s DP implementation severely impairs performance

****collision() only *

- +SIMDization

- +SW Prefetching

- +Unrolling

- +Vectorization

- +Padding

- Naïve+NUMA

**Notes:**
Note the performance difference between architectures

## Where do GPUs fit in?

- GPUs discover data level parallelism from thread level parallelism at runtime