Performance Tuning of Scientific Applications
David H Bailey, Lawrence Berkeley National Lab, USA (speaker)
DHB’s website:
http://crd.lbl.gov/~dhbailey!

1Why performance is important· Highly-parallel scientific computing is widely used in science and technology:
§§
§
§
§
§

Climate modeling – exploring scenarios for global warming.
Materials science – photovoltaics, batteries and nanoelectronics.
Astrophysics – supernova explosions, cosmology, data processing.
Physics – tests of standard model and alternatives.
Biology – model biochemical processes, develop new drugs.
Combustion – test designs for greater efficiency and less pollution.

· However, achieved performance is often poor – typically only 1-5% of peak.
Common reasons include:§§§Limited parallel concurrency in key loops, resulting in poor load balance.
Suboptimal structure of loops and blocks.
Subtle interference effects in data communication channels.

· Low performance is unacceptable, not only because of the high purchasecost of state-of-the-art systems, but also because of the increasing cost ofproviding electrical power for these systems.
2The Performance Engineering
Research Institute (PERI)· Performing research in theory, techniques and application of performancetuning for scientific computing.
· Funded by U.S. Dept. of Energy, Office of Science (SciDAC program).
· Participating members:§§§
§§§

University of Southern Cal. (lead)
Lawrence Berkeley Natl. Lab. (asst. lead)
Argonne National Lab.
Oak Ridge National Lab.
Lawrence Livermore National Lab. Rice University
University of California, San Diego University of Maryland
University of North Carolina/RENCI University of Tennessee, Knoxville
University of Utah· Principal research thrusts:§§§Performance modeling and analysis.
Automatic performance tuning.
Application analysis.

3

PERI performance modeling· Semi-automated performance modeling methodology:
§
§
§

Performance trace runs obtain profiles of applications.
Performance probes obtain profiles of computer systems.
A “convolution” approach combines application and system profiles toproduce quantitative predictions of performance.

· Uses:§§Permits scientists to understand the bottlenecks in their codes and future
potential for parallel scalability.
Permits computing facility managers to plan future requirements and improve
the selection process of large systems.

· Recent advances include:§§§§

Techniques to significantly reduce the volume of trace data required.
Techniques to extrapolate models to larger future systems.
Extensions of modeling methods to encompass energy consumption.
Applications to both DOD and DOE computational workloads.

Credit: Allan Snavely, UCSD
4

Performance modeling at LBNL· Erich Strohmaier’s ApexMAP: A simple modeling framework based on dataset
size, spatial locality and temporal locality.
· Samuel Williams’ “roofline” model: Compares achieved performance to a“roofline” graph of peak data streaming bandwidth and peak flop/s capacity.
Opteron 2356
(Barcelona)128

1
performance roofline(Y-coordinate is64performance)

peak performance (73.6 Gflop/s)

GFlop/s

32

2
processor-bandwidth
roofline(slope is bandwidth)16

48

Kernel #3

4

Kernel #22
11each kernel’s
performance
bound

3

Kernel #1

/8

1/
4

1/2

1
2
4
Arithmetic Intensity
5816

each kernel’srange inarithmetic
intensity

PERI automatic performance tuning· Background: We have found that most computational scientists are
reluctant to learn and use performance tools in day-to-day research work.
· Solution: Extend semi-automatic performance tuning techniques, such as
those developed for specialized libraries like FFTW (FFTs) and ATLAS(dense matrix computation), to the more general area of large-scalescientific computing.

6

The PERI autotuning framework

HPC Toolkit (Rice)"
ROSE (LLNL)"
CHiLL (USC/ISI and Utah)"
ROSE (LLNL)"
Orio (Argonne)"

OSKI (LBNL)"{Active Harmony (UMD)"
GCO (UTK)"

PerfTrack (LBNL, SDSC, RENCI)"

7

Applications of PERI research· PERI research tools and expertise have been applied to numerous
scientific application codes, in many cases with notable results.
· Even modest performance improvements in widely-used, high-profile
codes can save hundreds of thousands of dollars in computer time.
Examples:· S3D (Sandia code to model turbulence):
§
§
§
§

Improved exp routine (later supplanted by improved exp from Cray).
Improved set of compiler settings.
Achieved 12.7% overall performance improvement.
S3D runs consume 6,000,000 CPU-hours of computer time per year, so
762,000 CPU-hours are potentially saved each year.

· PFLOTRAN (LANL code to subsurface reactive flows):§§§

Two key PETSc routines (17% of run time) and a third routine (7% of runtime) were each accelerated by more than 2X using autotuning.
40X speedup in initialization phase, and 4X improvement in I/O stage.
Overall 5X speedup on runs with 90,000 or more cores.
8SMG2000· SMG2000: A semicoarsening multigrid solver code, used for various
applications including modeling of groundwater diffusion.
· PERI researchers integrated several tools, then developed a “smart”
search technique to find an optimal tuning strategy among 581 million
different choices.
· Achieved 2.37X performance improvement on one key kernel.
· Achieved 27% overall performance improvement.

9Autotuning the central SMG2000 kernel
Outlined code (from ROSE outliner)"for (si = 0; si < stencil_size; si++) "for (kk = 0; kk < hypre__mz; kk++) "for (jj = 0; jj < hypre__my; jj++) "for (ii = 0; ii < hypre__mx; ii++) "rp[((ri+ii)+(jj*hypre__sy3))+(kk*hypre__sz3)] -= "((Ap_0[((ii+(jj*hypre__sy1))+ (kk*hypre__sz1))+"(((A->data_indices)[i])[si])])* "(xp_0[((ii+(jj*hypre__sy2))+(kk*hypre__sz2))+(( *dxp_s)[si])])); "CHiLL transformation recipe "permute([2,3,1,4])"tile(0,4,TI)"
tile(0,3,TJ)"
tile(0,3,TK) "unroll(0,6,US) "unroll(0,7,UI)""
Credit: Mary Hall, Utah"

Constraints on search"
0 ≤ TI , TJ, TK ≤ 122 "0 ≤ UI ≤ 16 "0 ≤ US ≤ 10 "compilers ∈ {gcc, icc} ""Search space: "1223x16x10x2 = 581,071,360 points"
10Search for optimal tuning parameters
for SMG kernel
Parallel heuristic search (using Active Harmony) evaluates 490 total points andconverges in 20 steps.

Selected parameters:
TI=122,TJ=106,TK=56,UI=8,US=3,Comp=gcc

Performance gain on residual computation:
2.37X
Performance gain on full application:
27.23% improvement

Credit: Mary Hall, Utah

1111

Autotuning the triangular solve kernelof the Nek5000 turbulence code
Compiler

Original

Active Harmony

ExhaustiveTimeTime(u1,u2)

SpeedupTime(u1,u2)

Speeduppathscale

0.58

0.32

(3,11)

1.81

0.30(3,15)

1.93

gnu

0.71

0.47

(5,13)

1.51

0.46(5,7)

1.54

pgi

0.90

0.53

(5,3)

1.70

0.53

(5,3)

1.70

cray

1.13

0.70

(15,5)

1.61

0.69(15,15)

1.63

Credit: Jeff Hollingsworth, Maryland
12Autotuning LBMHD and GTC(LBNL work)· LBMHD (left): Implements a lattice Boltzmann method for magnetohydrodynamic
plasma turbulence simulation.
· GTC (right): A gyrokinetic toroidal code for plasma turbulence modeling.
threading of stream()threading of collision()
auto-tuned (ISA-specific)
auto-tuned (portable C)
reference

2.00

GFlop/s per Core

1.75
1.50
1.25
1.00
0.75
0.50
0.25

IntrepidFranklin

16GB

4GB

1GB4GB

1GB

1GB0.00

HopperCredit: Samuel Williams, LBNL
1335

Performance per Node relative to BGP

2.25

Optimized
Reference

30
1.35x

25
20

1.77x
15

1.02x

10
5
1.22x
0
BGP XE6Intel Fermi
Intrepid Hopper Cluster Cluster

LS3DF(LBNL work)· LS3DF: “linearly scaling 3-dimensional fragment” method.
· Developed at LBNL by Lin-Wang Wang and several collaborators.
· Used for for electronic structure calculations – numerous applications inmaterials science and nanoscience.
· Employs a novel divide-and-conquer scheme including a new approachfor patching the fragments together.
· Achieves nearly linear scaling in computational cost versus size ofproblem, compared with n3 scaling in many other comparable codes.
· Potential for nearly linear scaling in performance versus number of cores.
Challenge:· Initial implementation of LS3DF had disappointingly low performance andparallel scalability.

14

2-D domain patching scheme in LS3DF"

Interior area"(i,j,k)Buffer area"

Fragment (2x1)

Artificial surface
passivation"}

Total = ΣF {FFFF

Boundary effects are (nearly) cancelled out between the fragments:

System = ∑ {F222 + F211 + F121 + F112 − F221 − F212 − F122 − F111 }i , j ,kCredit: Lin-Wang Wang, LBNL
15

LBNL’s performance analysis of LS3DF
LBNL researchers (funded through PERI) applied performance monitoring
tools to analyze run-time performance of LS3DF. Key issues uncovered:· Limited concurrency in a key step, resulting in a significant load
imbalance between processors.
§Solution: Modify code for two-dimensional parallelism.

· Costly file I/O operations were used for data communication betweenprocessors.
§Solution: Replace all file I/O operations with MPI send-receive operations.

16

Resulting performance of tuned LS3DF· 135 Tflops/s on 36,864 cores of theCray XT4 Franklin system at LBNL.
§

40% efficiency on 36,864 cores.

· 224 Tflops/s on 163,840 processors of
the BlueGene/P Intrepid system at
Argonne Natl. Lab.
§

40% efficiency on 163,840 cores.

· 442 Tflops/s on 147,456 processors ofthe Cray XT5 Jaguar system at Oak
Ridge Natl. Lab.
§

33% efficiency on 147,456 cores.

The authors of the LS3DF paper wereawarded the 2008 ACM Gordon Bell
Prize in a special category for “algorithminnovation.”17

Near-linear parallel scaling for up to163,840 cores and up to 442 Tflop/s
LS3DF
500
450
400

TFlop/s.

350

JaguarIntrepidFranklin

300
250
200
150
100
500
0

20,00040,00060,00080,000 100,000 120,000 140,000 160,000 180,000
Cores18

Solar cell application of tuned LS3DF· Single-band material
theoretical photovoltaic
efficiency is limited to 30%.
· With an intermediate state,
the photovoltaic efficiency
may increase to 60%.
· Proposed material: ZnTe:O.
§ Is there really a gap?
§ Is there sufficientoscillator strength?
· LS3DF calculation used for3500 atom 3% O alloy [onehour on 17,000 cores ofFranklin system].
· Result: There is a gap, and O
induced states are highlylocalized.

Highest O induced state

ZnTe bottom of cond. band state
19Credit: Lin-Wang Wang, LBNL

For additional details:
Performance Tuning of Scientific Applications
Editors: Bailey (LBNL), Lucas (USC/ISI), Williams (LBNL);
numerous individual authors of various chapters.
Publisher: CRC Computational Science, Jan 2011.
Contents:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.

Introduction
Parallel computer architecture
Software interfaces to hardware counters
Measurement and analysis of parallel program performance using TAU
and HPCToolkit.
Trace-base tools
Large-scale numerical simulations on high-end computational platforms
Performance modeling: the convolution approach
Analytic modeling for memory access patterns based on Apex-MAP
The roofline model
End-to-end auto-tuning with active harmony
Languages and compilers for auto-tuning
Empirical performance tuning of dense linear algebra software
Auto-tuning memory-intensive kernels for multicore
Flexible tools supporting a scalable first-principles MD code
The community climate system model
Tuning an electronic structure code20