# Presentation: 606880

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

- Samuel Williams1,2, David Patterson1,
- Leonid Oliker1,2, John Shalf2, Katherine Yelick1,2
- 1University of California, Berkeley
- 2Lawrence Berkeley National Laboratory
*samw@cs.berkeley.edu*

**Notes:**
Developed not only to easily explain differences in performance among architectures, but also requisite optimizations

## Outline

- Motivation, Goals, Audience, etc...
- Survey of multicore architectures
- Description of the Roofline model
- Introduction to Auto-tuning
- Application of the roofline to auto-tuned kernels
- Example #1 - SpMV
- Example #2 - LBMHD
- Conclusions

## Motivation

- Multicore guarantees neither good scalability
- 	nor good (attained) performance
- Performance and scalability can be extremely non-intuitive even to computer scientists
- Success of the multicore paradigm seems to be premised upon their programmability
- To that end, one must understand the limits to both scalability and efficiency.
- 		- How can we empower programmers?

**Notes:**
.... How can we aide them ?

## Primary Focus

- Throughput-oriented kernels (rather than time)
- Our performance metrics are:
**	****Gflop/s **and** % of peak **(efficiency)
*	**for purposes of this talk, I will focus on memory-intensive *
*	**64b floating-point SPMD kernels.*
- Not focused on algorithmic innovation or
- 	computational complexity

## Goals & Audience

- Goals for Roofline:
- Provide everyone (especially undergrads) 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 (+10%)
- Not for those challenged by parallel kernel correctness

## Multicore SMPsof Interest

*(used throughout the rest of the talk)*

## Multicore SMPs Used

- AMD Opteron 2356 (Barcelona)

- Intel Xeon E5345 (Clovertown)

- IBM QS20 Cell Blade

- Sun T2+ T5140 (Victoria Falls)

**Notes:**
NOTE: SMP, NUMA?, Snoop Filter?

## Multicore SMPs Used

- AMD Opteron 2356 (Barcelona)

- Intel Xeon E5345 (Clovertown)

- IBM QS20 Cell Blade

- Sun T2+ T5140 (Victoria Falls)

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

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

## Multicore SMPs Used

- AMD Opteron 2356 (Barcelona)

- Intel Xeon E5345 (Clovertown)

- IBM QS20 Cell Blade

- Sun T2+ T5140 (Victoria Falls)

**multithreaded cores**

## Multicore SMPs Used(peak double precision flops)

- AMD Opteron 2356 (Barcelona)

- Intel Xeon E5345 (Clovertown)

- IBM QS20 Cell Blade

- Sun T2+ T5140 (Victoria Falls)

**75 GFlop/s**

**74 Gflop/s**

**29* GFlop/s**

**19 GFlop/s**

- *SPEs only

## Multicore SMPs Used(total DRAM bandwidth)

- AMD Opteron 2356 (Barcelona)

- Intel Xeon E5345 (Clovertown)

- IBM QS20 Cell Blade

- Sun T2+ T5140 (Victoria Falls)

**21 GB/s (read)**
**10 GB/s (write)**

**21 GB/s**

**51* GB/s**

**42 GB/s (read)**
**21 GB/s (write)**

- *SPEs only

## Roofline models for multicore SMPs

*(for memory-intensive double precision floating-point kernels)*

## Arithmetic Intensity in HPC

**True Arithmetic Intensity (AI) ~ Total Flops / Total DRAM Bytes**
- constant with respect to problem size for many problems of interest
- ultimately limited by compulsory traffic
- diminished by conflict or capacity misses.

**A r i t h m e t i c  I n t e n s i t y**

- O( N )

- O( log(N) )

- O( 1 )

- SpMV, BLAS1,2

- Stencils (PDEs)

- Lattice Methods

- FFTs

- Dense Linear Algebra
- (BLAS3)

- Particle Methods

## Naïve Roofline Model

- Based on **Bound and Bottleneck analysis**1
- Performance is upper bounded by both the peak flop rate,
- 	and the product of streaming bandwidth and the flop:byte ratio
- (well understood in the performance oriented communities)
*	**	**	**	**	**where AI is the actual arithmetic intensity*
- Assumptions:
- Bandwidth is independent on arithmetic intensity
- Bandwidth is independent of optimization or access pattern
- Computation is independent of optimization
- Complete overlap of either communication or computation
*1**D. Lazowska, J. Zahorjan, G. Graham, K. Sevcik, *
*“**Quantitative System Performance”*

## Roofline Model

- 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

- 1

**Log scale !**

**Log scale !**

## Naïve Roofline Model

- Unrealistically optimistic model
- Hand optimized Stream BW benchmark

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- peak DP

- peak DP

- peak DP

- 8

- peak DP

- IBM QS20
- Cell Blade

- Sun T2+ T5140
- (Victoria Falls)

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- hand optimized Stream BW

- hand optimized Stream BW

- hand optimized Stream BW

- hand optimized Stream BW

## Naïve Roofline Model

- Unrealistically optimistic model
- Hand optimized Stream BW benchmark

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- peak DP

- peak DP

- peak DP

- 8

- peak DP

- IBM QS20
- Cell Blade

- Sun T2+ T5140
- (Victoria Falls)

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- hand optimized Stream BW

- hand optimized Stream BW

- hand optimized Stream BW

- hand optimized Stream BW

**This level of performance**
**is only attainable with**
**extensive optimizations**

## Naïve Roofline Model

- Unrealistically optimistic model
- Hand optimized Stream BW benchmark

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- peak DP

- peak DP

- peak DP

- 8

- peak DP

- IBM QS20
- Cell Blade

- Sun T2+ T5140
- (Victoria Falls)

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- hand optimized Stream BW

- hand optimized Stream BW

- hand optimized Stream BW

- hand optimized Stream BW

**How sensitive is each**
**architecture to**
**removing those optimizations ?**

## Better Roofline

- Collect **StreamBW****j**** **with progressively fewer optimizations
- Estimate **InCoreGFlops****i**** **with progressively fewer optimizations
- 					*is the attainable performance with: *
*	**	**	**	**	**memory optimizations**1...i**	**- and -*
*	**	**	**	**	**in-core optimizations**1..j** **	*
- These denote a series of **ceilings** below the roofline
- Assumptions:
- Bandwidth is independent on arithmetic intensity
- Complete overlap of either communication or computation

**Notes:**
Performance is a combination of in-core and bandwidth optimizations

## Roofline models(dram bandwidth)

- What happens as bandwidth optimizations are stripped out ?
- Form a series of bandwidth ceilings below the roofline
- Small problems fit in the snoop filter in Clovertown’s MCH
- most architectures see NUMA and prefetch variations

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- peak DP

- peak DP

- peak DP

- 8

- peak DP

- IBM QS20
- Cell Blade

- Sun T2+ T5140
- (Victoria Falls)

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- hand optimized Stream BW

- hand optimized Stream BW

- hand optimized Stream BW

- hand optimized Stream BW

**Notes:**
DEFINE CEILINGS !!

## Roofline models(dram bandwidth)

- What happens as bandwidth optimizations are stripped out ?
- Form a series of bandwidth ceilings below the roofline
- Small problems fit in the snoop filter in Clovertown’s MCH
- most architectures see NUMA and prefetch variations

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- peak DP

- peak DP

- peak DP

- 8

- peak DP

- IBM QS20
- Cell Blade

- Sun T2+ T5140
- (Victoria Falls)

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- dataset fits in snoop filter

- hand optimized Stream BW

- hand optimized Stream BW

- hand optimized Stream BW

- hand optimized Stream BW

## Roofline models(dram bandwidth)

- What happens as bandwidth optimizations are stripped out ?
- Form a series of bandwidth ceilings below the roofline
- Small problems fit in the snoop filter in Clovertown’s MCH
- most architectures see NUMA and prefetch variations

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- peak DP

- 8

- Sun T2+ T5140
- (Victoria Falls)

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- dataset fits in snoop filter

- peak DP

- peak DP

- w/out SW prefetch

- w/out SW prefetch

- hand optimized Stream BW

- hand optimized Stream BW

- hand optimized Stream BW

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- peak DP

- IBM QS20
- Cell Blade

- hand optimized Stream BW

## Roofline models(dram bandwidth)

- What happens as bandwidth optimizations are stripped out ?
- Form a series of bandwidth ceilings below the roofline
- Small problems fit in the snoop filter in Clovertown’s MCH
- most architectures see NUMA and prefetch variations

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- peak DP

- 8

- IBM QS20
- Cell Blade

- Sun T2+ T5140
- (Victoria Falls)

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- dataset fits in snoop filter

- peak DP

- peak DP

- peak DP

- w/out SW prefetch

- w/out SW prefetch

- unaligned DMA

- hand optimized Stream BW

- hand optimized Stream BW

- hand optimized Stream BW

- hand optimized Stream BW

## Roofline models(dram bandwidth)

- What happens as bandwidth optimizations are stripped out ?
- Form a series of bandwidth ceilings below the roofline
- Small problems fit in the snoop filter in Clovertown’s MCH
- most architectures see NUMA and prefetch variations

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- peak DP

- peak DP

- peak DP

- 8

- peak DP

- w/out SW prefetch

- w/out NUMA

- IBM QS20
- Cell Blade

- Sun T2+ T5140
- (Victoria Falls)

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- w/out SW prefetch

- w/out NUMA

- dataset fits in snoop filter

- unaligned DMA

- w/out NUMA

- hand optimized Stream BW

- hand optimized Stream BW

- hand optimized Stream BW

- hand optimized Stream BW

## Roofline models(dram bandwidth)

- What happens as bandwidth optimizations are stripped out ?
- Form a series of bandwidth ceilings below the roofline
- Small problems fit in the snoop filter in Clovertown’s MCH
- most architectures see NUMA and prefetch variations

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- peak DP

- peak DP

- peak DP

- 8

- peak DP

- w/out SW prefetch

- w/out NUMA

- IBM QS20
- Cell Blade

- Sun T2+ T5140
- (Victoria Falls)

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- w/out SW prefetch

- w/out NUMA

- dataset fits in snoop filter

- unaligned DMA

- w/out NUMA

- hand optimized Stream BW

- hand optimized Stream BW

- hand optimized Stream BW

- hand optimized Stream BW

- w/out unit stride

- w/out unit stride

- w/out unitr stride

**Notes:**
What if we don’t have unit-stride accesses ?

## In-core Performance

- Define a similar set of ceilings for in-core performance
- In-core performance can be limited by (among other things):
- Not satisfying all forms of **in-core parallelism**:
- Instruction-level parallelism (multi-issue, pipeline, ...)
- Data-level parallelism (SIMD)
- Functional unit parallelism (adders + multipliers + ...)
- Non-FP instructions can consume **instruction issue bandwidth**
- As the FP fraction decrease, how sensitive is attainable performance?
- One or the other is usually more difficult to satisfy on a given architecture/kernel
- 		=** Architecture’s Achilles’ Heel**

## Roofline models(in-core performance = in-core parallelism?)

- Covering the breadth of in-core parallelism is the preeminent challenge on most architectures
- Form a series of parallelism ceilings below the roofline
- On Niagara machines, instruction latencies are easily hidden with 8-way multithreading

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- peak DP

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- w/out SW prefetch

- w/out NUMA

- w/out SIMD

- w/out ILP

- mul/add imbalance

- dataset fits in snoop filter

- w/out FMA

- peak DP

- w/out SIMD

- w/out ILP

- w/out NUMA

- unaligned DMA

- 8

- peak DP

- w/out SW prefetch

- w/out NUMA

- IBM QS20
- Cell Blade

- Sun T2+ T5140
- (Victoria Falls)

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

## Roofline models(in-core performance = instruction mix?)

- All machines have a limited instruction issue bandwidth.
- non-FP instructions sap instruction issue bandwidth needed by FP instructions
- As the FP fraction of the dynamic instruction mix decreases, so might performance.
- On Cell, double precision instructions stall subsequent issues for 7 cycles.

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 25% FP

- peak DP

- 12% FP

- w/out SW prefetch

- w/out NUMA

- IBM QS20
- Cell Blade

- Sun T2+ T5140
- (Victoria Falls)

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- peak DP

- dataset fits in snoop filter

- 12% FP

- 25% FP

- peak DP

- w/out SW prefetch

- w/out NUMA

- 12% FP

- 25% FP

- peak DP

- w/out NUMA

- unaligned DMA

- 12%

## Roofline models(Achilles' Heel)

- Its clear that in-core parallelism is more important on the superscalars
- Instruction mix is more important on Niagara2
- Each architecture has its own **Achilles’ Heel** when it comes to in-core performance

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- peak DP

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- w/out SW prefetch

- w/out NUMA

- w/out SIMD

- w/out ILP

- mul/add imbalance

- dataset fits in snoop filter

- w/out FMA

- peak DP

- w/out SIMD

- w/out ILP

- w/out NUMA

- unaligned DMA

- IBM QS20
- Cell Blade

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 25% FP

- peak DP

- 12% FP

- w/out SW prefetch

- w/out NUMA

- Sun T2+ T5140
- (Victoria Falls)

## Roofline models(ceilings constrain performance)

- The ceilings act to constrain performance to a much smaller region

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- peak DP

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- w/out SW prefetch

- w/out NUMA

- w/out SIMD

- w/out ILP

- mul/add imbalance

- dataset fits in snoop filter

- w/out FMA

- peak DP

- w/out SIMD

- w/out ILP

- w/out NUMA

- unaligned DMA

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 25% FP

- peak DP

- 12% FP

- w/out SW prefetch

- w/out NUMA

- 1/16

- 1/16

- IBM QS20
- Cell Blade

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- Sun T2+ T5140
- (Victoria Falls)

**Notes:**
Ceilings constrain performance

## Roofline models(ceilings constrain performance)

- The ceilings act to constrain performance to a much smaller region

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- peak DP

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- w/out SW prefetch

- w/out NUMA

- w/out SIMD

- w/out ILP

- mul/add imbalance

- dataset fits in snoop filter

- w/out FMA

- peak DP

- w/out SIMD

- w/out ILP

- w/out NUMA

- unaligned DMA

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 25% FP

- peak DP

- 12% FP

- w/out SW prefetch

- w/out NUMA

- 1/16

- 1/16

- IBM QS20
- Cell Blade

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- Sun T2+ T5140
- (Victoria Falls)

**Notes:**
Ceilings constrain performance

## Roofline models(thickness)

- The ceilings act to constrain performance to a much smaller region

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- peak DP

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- w/out SW prefetch

- w/out NUMA

- w/out SIMD

- w/out ILP

- mul/add imbalance

- dataset fits in snoop filter

- w/out FMA

- peak DP

- w/out SIMD

- w/out ILP

- w/out NUMA

- unaligned DMA

- IBM QS20
- Cell Blade

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 25% FP

- peak DP

- 12% FP

- w/out SW prefetch

- w/out NUMA

- Sun T2+ T5140
- (Victoria Falls)

**Thickness of the roofline is**
**indicative of requisite**
**compiler or SW complexity**

**Notes:**
If I were to give you a roofline model and arithmetic intensity, could you predict performance ?

## Three Categories of Software Optimization

## Optimization Categorization

**Maximizing**
**In-core Performance**

**Minimizing**
**Memory Traffic**

**Maximizing**
**Memory Bandwidth**

**Exploit in-core parallelism**
**   ****(ILP, DLP, etc...)**
**Good (enough)**
**   ****floating-point balance**

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

- Compilers may not have as much knowledge as the programmer
- Express more in-core parallelism and amortize non-FP instructions
- Software optimizations:
- Explicit SIMDization
- Loop unrolling
- Unroll and jam
- Reordering
- Predication
**Punch through ceilings**

- 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
- Optimizations:
- long unit stride accesses
- NUMA aware allocation and parallelization
- SW prefetching
- Maximize MLP
**Punch through bandwidth ceilings**

- 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 Total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
- Optimizations:
- Array padding: conflict
- Cache blocking: capacity
- Cache bypass: compulsory
**Push arithmetic intensity to the compulsory limit**

- 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 miss limit

## Optimization Categorization

**Maximizing**
**In-core Performance**

**Minimizing**
**Memory Traffic**

**Maximizing**
**Memory Bandwidth**

**Exploit in-core parallelism**
**   ****(ILP, DLP, etc...)**
**Good (enough)**
**   ****floating-point balance**

**Each optimization has**
**a large parameter space**
**What are the optimal parameters?**

**Notes:**
Note the difference between ‘optimization’ and ‘parameter’

## Introduction toAuto-tuning

## Out-of-the-box Code

- Out-of-the-box code has (unintentional) assumptions on:
- cache sizes (>10MB)
- functional unit latencies(~1 cycle)
- etc...
- These assumptions may result in poor performance when they exceed the machine characteristics

## What is auto-tuning?

- Goal: provide** performance portability **across the existing breadth and evolution of microprocessors
- At the expense of a one time up front productivity cost that’s amortized by the number of machines its used on
- Auto-tuning does not invent new optimizations
**Auto-tuning automates the exploration of the optimization and parameter space**
- Two components:
- parameterized code generator (we wrote ours in Perl)
- Auto-tuning exploration benchmark
- 	(combination of heuristics and exhaustive search)
- Can be extended with ISA specific optimizations (e.g. DMA, SIMD)

## Distinguishing theRoofline and Auto-tuning

- Roofline specifies what's deficient, but not how to fix it.
- Auto-tuning attempts to fix it by searching the parameter space for the existing body of optimization work

## Application of the Roofline Model to sample Kernels

*Does the roofline model provide insight into the limitations of architecture, implementation, and algorithm? *

## notes

- Things to watch for:
- do performance graphs alone provide insight into the limitations of kernel or architecture ?
- does the roofline show the ultimate performance limitations of
- 	kernel and architecture ?
- does the roofline show which optimizations will be necessary ?

**Notes:**
Kernel details aren’t key to this talk.

## Example #1: Auto-tuning 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

- What’s a Sparse Matrix ?
- Most entries are 0.0
- Performance advantage in only storing/operating on the nonzeros
- Requires significant meta data to reconstruct the matrix structure
- What’s SpMV ?
- Evaluate y=Ax
- A is a sparse matrix, x & y are dense vectors
- Challenges
**Very low arithmetic intensity  (often <0.166 flops/byte)**
- Difficult to exploit ILP(bad for superscalar),
- Difficult to exploit DLP(bad for SIMD)

## The Dataset (matrices)

- Unlike dense BLAS, performance is dictated by sparsity
- Suite of 14 matrices
- All bigger than the caches of our SMPs
- We’ll also include a median performance number

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

## SpMV Performance(simple parallelization)

- Out-of-the box SpMV performance on a suite of 14 matrices
**Scalability isn’t great**
**Is this performance good?**

- Naïve Pthreads

- Naïve

**Notes:**
Looking at this, 
Could an undergrad tell me why scalability is poor?
Could an undergrad tell me how much further improvement is possible? 

## Auto-tuned SpMV Performance(architecture specific optimizations)

- Fully auto-tuned SpMV performance across the suite of matrices
- Included SPE/local store optimized version
- Why do some optimizations work better on some architectures?
**Performance is better,**
**	****but is performance good?**

- +Cache/LS/TLB Blocking

- +Matrix Compression

- +SW Prefetching

- +NUMA/Affinity

- Naïve Pthreads

- Naïve

## Auto-tuned SpMV Performance(architecture specific optimizations)

- Fully auto-tuned SpMV performance across the suite of matrices
- Included SPE/local store optimized version
- Why do some optimizations work better on some architectures?
**Performance is better,**
**	****but is performance good?**

- +Cache/LS/TLB Blocking

- +Matrix Compression

- +SW Prefetching

- +NUMA/Affinity

- Naïve Pthreads

- Naïve

**Auto-tuning resulted**
** ****in **_**better**_** performance,**
** ****but did it result in **
_**good**_** performance?**

## Roofline model for SpMV

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

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- w/out SIMD

- peak DP

- w/out ILP

- w/out FMA

- w/out NUMA

- unaligned DMA

- 25% FP

- peak DP

- 12% FP

- w/out SW prefetch

- w/out NUMA

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- w/out SW prefetch

- w/out NUMA

- IBM QS20
- Cell Blade

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- Sun T2+ T5140
- (Victoria Falls)

- dataset dataset fits in snoop filter

## Roofline model for SpMV(overlay arithmetic intensity)

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

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- w/out SIMD

- peak DP

- w/out ILP

- w/out FMA

- w/out NUMA

- unaligned DMA

- 25% FP

- peak DP

- 12% FP

- w/out SW prefetch

- w/out NUMA

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- w/out SW prefetch

- w/out NUMA

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

- IBM QS20
- Cell Blade

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- Sun T2+ T5140
- (Victoria Falls)

- dataset dataset fits in snoop filter

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

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- w/out SIMD

- peak DP

- w/out ILP

- w/out FMA

- w/out NUMA

- unaligned DMA

- 25% FP

- peak DP

- 12% FP

- w/out SW prefetch

- w/out NUMA

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- w/out SW prefetch

- w/out NUMA

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

- IBM QS20
- Cell Blade

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- Sun T2+ T5140
- (Victoria Falls)

- dataset dataset fits in snoop filter

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

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

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- w/out SIMD

- peak DP

- w/out ILP

- w/out FMA

- w/out NUMA

- unaligned DMA

- 25% FP

- peak DP

- 12% FP

- w/out SW prefetch

- w/out NUMA

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- w/out SW prefetch

- w/out NUMA

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

- IBM QS20
- Cell Blade

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- Sun T2+ T5140
- (Victoria Falls)

- dataset dataset fits in snoop filter

## Roofline model for SpMV(matrix compression)

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

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- w/out SIMD

- peak DP

- w/out ILP

- w/out FMA

- w/out NUMA

- unaligned DMA

- 25% FP

- peak DP

- 12% FP

- w/out SW prefetch

- w/out NUMA

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- dataset dataset fits in snoop filter

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- w/out SW prefetch

- w/out NUMA

- IBM QS20
- Cell Blade

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- Sun T2+ T5140
- (Victoria Falls)

## Roofline model for SpMV(matrix compression)

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

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- w/out SIMD

- peak DP

- w/out ILP

- w/out FMA

- w/out NUMA

- unaligned DMA

- 25% FP

- peak DP

- 12% FP

- w/out SW prefetch

- w/out NUMA

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- dataset fits in snoop filter

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- w/out SW prefetch

- w/out NUMA

- IBM QS20
- Cell Blade

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- Sun T2+ T5140
- (Victoria Falls)

**All machines are on the**
**bandwidth roofline !**

## Example #2: Auto-tuning 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

**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)
- Arithmetic Intensity:
- Must read 73 doubles, and update 79 doubles per lattice update (1216 bytes)
- Requires about 1300 floating point operations per lattice update
**Just over 1.0 flops/byte (ideal)**
- Out-of-the-box,
- 	no unit stride memory
- 	access patterns

## Initial LBMHD Performance

- Generally, scalability looks good
**but is performance good?**

****collision() only *

- Naïve+NUMA

**Notes:**
PPE performance is abysmal

## Auto-tuned LBMHD Performance(architecture specific optimizations)

- Auto-tuning avoids cache conflict and TLB capacity misses
- Additionally, it exploits SIMD where the compiler doesn’t
- Include a SPE/Local Store optimized version

****collision() only *

- +Explicit SIMDization

- +SW Prefetching

- +Unrolling

- +Vectorization

- +Padding

- Naïve+NUMA

- +small pages

## Roofline model for LBMHD

- Far more adds than multiplies (imbalance)
- Huge data sets

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 25% FP

- peak DP

- 12% FP

- w/out SW prefetch

- w/out NUMA

- w/out FMA

- peak DP

- w/out ILP

- w/out SIMD

- w/out NUMA

- unaligned DMA

- peak DP

- mul/add imbalance

- dataset fits in snoop filter

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- w/out SW prefetch

- w/out NUMA

- IBM QS20
- Cell Blade

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- Sun T2+ T5140
- (Victoria Falls)

- w/out SIMD

- w/out ILP

## Roofline model for LBMHD(overlay arithmetic intensity)

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

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 25% FP

- peak DP

- 12% FP

- w/out SW prefetch

- w/out NUMA

- w/out FMA

- peak DP

- w/out ILP

- w/out SIMD

- w/out NUMA

- unaligned DMA

- peak DP

- mul/add imbalance

- dataset fits in snoop filter

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- w/out SW prefetch

- w/out NUMA

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

- IBM QS20
- Cell Blade

- Opteron 2356
- (Barcelona)

- Intel Xeon E5345
- (Clovertown)

- Sun T2+ T5140
- (Victoria Falls)

- w/out SIMD

- w/out ILP

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

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

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 25% FP

- peak DP

- 12% FP

- w/out SW prefetch

- w/out NUMA

- w/out FMA

- peak DP

- w/out ILP

- w/out SIMD

- w/out NUMA

- unaligned DMA

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- w/out SW prefetch

- w/out NUMA

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

- IBM QS20
- Cell Blade

- Opteron 2356
- (Barcelona)

- Sun T2+ T5140
- (Victoria Falls)

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- peak DP

- mul/add imbalance

- dataset fits in snoop filter

- Intel Xeon E5345
- (Clovertown)

- w/out SIMD

- w/out ILP

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

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 25% FP

- peak DP

- 12% FP

- w/out SW prefetch

- w/out NUMA

- w/out FMA

- peak DP

- w/out ILP

- w/out SIMD

- w/out NUMA

- unaligned DMA

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- w/out SW prefetch

- w/out NUMA

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

- IBM QS20
- Cell Blade

- Opteron 2356
- (Barcelona)

- Sun T2+ T5140
- (Victoria Falls)

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- peak DP

- mul/add imbalance

- dataset fits in snoop filter

- Intel Xeon E5345
- (Clovertown)

- w/out SIMD

- w/out ILP

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

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 25% FP

- peak DP

- 12% FP

- w/out SW prefetch

- w/out NUMA

- w/out FMA

- peak DP

- w/out ILP

- w/out SIMD

- w/out NUMA

- unaligned DMA

- peak DP

- w/out ILP

- w/out SIMD

- mul/add imbalance

- w/out SW prefetch

- w/out NUMA

- IBM QS20
- Cell Blade

- Opteron 2356
- (Barcelona)

- Sun T2+ T5140
- (Victoria Falls)

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- peak DP

- mul/add imbalance

- dataset fits in snoop filter

- Intel Xeon E5345
- (Clovertown)

- w/out ILP

- w/out SIMD

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

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- 25% FP

- peak DP

- 12% FP

- w/out SW prefetch

- w/out NUMA

- w/out FMA

- peak DP

- w/out ILP

- w/out SIMD

- w/out NUMA

- unaligned DMA

- peak DP

- w/out SIMD

- w/out ILP

- mul/add imbalance

- w/out SW prefetch

- w/out NUMA

- IBM QS20
- Cell Blade

- Opteron 2356
- (Barcelona)

- Sun T2+ T5140
- (Victoria Falls)

- 1

- 2

- 1/16

- flop:DRAM byte ratio

- attainable Gflop/s

- 4

- 8

- 16

- 32

- 64

- 128

- 1/8

- 1/4

- 1/2

- 1

- 2

- 4

- 8

- peak DP

- mul/add imbalance

- dataset fits in snoop filter

- Intel Xeon E5345
- (Clovertown)

- w/out SIMD

- w/out ILP

**3 out of 4 machines**
**hit the Roofline**

## Conclusions

## Summary

- The Roofline model is a visually intuitive figure for kernel analysis and optimization
- We believe undergraduates will find it useful in assessing performance and scalability limitations
- It is easily extended to other architectural paradigms
- We believe it is easily extendable to other metrics:
- performance (sort, graphics, crypto...)
- bandwidth (L2, PCIe, ...)
- We believe that a performance counters could be used to generate a **runtime-specific** roofline that would greatly aide the optimization

## Suggestion...

- As architectures are presented over the next two days, we invite you to create a roofline model for each.
- Estimate the ceilings.
- Then contemplate performance and productivity among them

## Acknowledgements

- Research supported by:
- Microsoft and Intel funding (Award #20080469)
- DOE Office of Science under contract number DE-AC02-05CH11231
- NSF contract CNS-0325873
- Sun Microsystems - Niagara2 / Victoria Falls machines
- AMD - access to Quad-core Opteron (barcelona) access
- Forschungszentrum Jülich - access to QS20 Cell blades
- IBM - virtual loaner program to QS20 Cell blades

## Questions ?

- 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.
- 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**
- 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*”, Supercomputing (SC) (to appear), 2008.