8/16/2012

Algorithms and Software in
the Post-Petascale Era
William Gropp
www.cs.illinois.edu/~wgropp

Extrapolation is Risky• 1989 – T – 23 years
 Intel introduces 486DX
 Eugene Brooks writes “Attack of the Killer

Micros”
 4 years before TOP500
 Top systems at about 2 GF Peak• 1999 – T – 13 years
 NVIDIA introduces its GPU (GeForce 256)
• Programming GPUs still a challenge 13 years later Top system – ASCI Red, 9632 cores, 3.2 TF

Peak (about 3 GPUs in 2012)
 MPI is 7 years old21

8/16/2012

HPC Today• High(est)-End systems
 1 PF (1015 Ops/s) achieved on a few “peak friendly”

applications

 Much worry about scalability, how we’re going to get to an

ExaFLOPS Systems are all oversubscribed• DOE INCITE awarded almost 900M processor hours in 2009;
1600M-1700M hours in 2010-2012; (big jump planned in 2013
– over 5B hours)• NSF PRAC awards for Blue Waters similarly competitive• Widespread use of clusters, many with accelerators;
cloud computing services
 These are transforming the low and midrange• Laptops (far) more powerful than the supercomputers I
used as a graduate student
3

HPC in 2011
• Sustained PF systems
 Kei Computer (Fujitsu) at RIKEN, Kobe, Japan (2011)
 “Sequoia” Blue Gene/Q at LLNL NSF Track 1 “Blue Waters” at Illinois
 Undoubtedly others (China, … )• Still programmed with MPI and MPI+other (e.g.,
MPI+OpenMP or MPI+OpenCL/CUDA or MPI+OpenACC)
 But in many cases using toolkits, libraries, and otherapproaches• And not so bad – applications will be able to run when thesystem is turned on Replacing MPI will require some compromise – e.g.,domain specific (higher-level but less general)• Lots of evidence that fully automatic solutions won’t work42

8/16/2012

End of an Era• IN THE LONG TERM (~2017 THROUGH 2024)“While power consumption is an urgent
challenge, its leakage or static component will
become a major industry crisis in the longterm, threatening the survival of CMOS
technology itself, just as bipolar technology
was threatened and eventually disposed of
decades ago.” [ITRS 2009]• Unlike the situation at the end of the bipolarera, no technology is waiting in the wings.

5

The Post-Moore Era• Scaling is ending Voltage scaling ended in 2004 (leakage current)
 Feature scaling will end in 202x (not enough atoms)
 Scaling rate will slow down in the next few years
 Continued scaling in the next decade will need asequence of (small) miracles (new materials, newstructures, new manufacturing technologies)☛Compute Efficiency becomes a paramountconcern
 More computations per joule More computations per transistor

63

8/16/2012

HPC in 2018-2020
2020-2023• Exascale systems are likely to have

 Extreme power constraints, leading to• Clock Rates similar to today’s systems• A wide-diversity of simple computing elements (simple for
hardware but complex for software)• Memory per core and per FLOP will be much smaller• Moving data anywhere will be expensive (time and power)
 Faults that will need to be detected and managed• Some detection may be the job of the programmer, as
hardware detection takes power Extreme scalability and performance irregularity• Performance will require enormous concurrency• Performance is likely to be variable Simple, static decompositions will not scale A need for latency tolerant algorithms andprogramming• Memory, processors will be 100s to 10000s of cycles
away. Waiting for operations to complete will cripple
performance
7

Algorithms and Applications
Will Change• Applications need to become more
dynamic, more integrated• System software must work withapplication:
 Code complexity (Autotuning) Dynamic resources (no simple PGAS) Latency hiding (Nonblocking algorithms,

interfaces (including futures)) Resource sharing (more performance
information, performance asserts, runtime
coordination)
84

8/16/2012

How Do We Make Effective
Use of These Systems?
• Better use of our existing systems
 Blue Waters will provide a sustained PF, but thattypically requires ~10PF peak

• Improve node performance
 Make the compiler better Give better code to the compiler Get realistic with algorithms/data structures• Improve parallel performance/scalability• Improve productivity of applications
 Better tools and interoperable languages, not a (single)

new programming language• Improve algorithms
 Optimize for the real issues – data movement, power,

resilience, …

9Make the Compiler Better• It remains the case that mostcompilers cannot compete withhand-tuned or autotuned code on
simple code Just look at dense matrix-matrix

multiplication or matrix transpose Try it yourself!
• Matrix multiply on my laptop:• N=100 (in cache): 1818 MF (1.1ms)• N=1000 (not): 335 MF (6s)105

8/16/2012

How Good are Compilers at
Vectorizing Codes?
Vectorizable

Not Vectorizable

Auto Vectorized
GCC
4 1

ICC
3
3

IBM

Intel

XLC

1
34

28

7 18 5627

Vectorizable but none of thecompilers auto vectorized

21

S. Maleki, Y. Gao, T. Wong, M. Garzarán, and D. Padua. An Evaluation of Vectorizing
Compilers. PACT 2011.
11

Media Bench II Applications
Appl

XLC

ICC

GCC

XLC

Automatic

ICC

GCC

ManualJPEG Enc

-

1.33

-

1.39

2.13

1.57

JEPG Dec

-

-

-

-

1.14

1.13

H263 Enc

-

-

-

1.25

2.28

2.06

H263 Dec

-

-

-

1.31

1.45

-

MPEG2 Enc

-

-

-

1.06

1.96

2.43

MPEG2 Dec

-

-

1.15

1.37

1.45

1.55

MPEG4 Enc

-

-

-

1.44

1.81

1.74

MPEG4 Dec

-

-

-

1.12

-

1.18

Table shows whole program speedups measured
against unvectorized application
S. Maleki, Y. Gao, T. Wong, M. Garzarán, and D. Padua. An Evaluation of Vectorizing Compilers. PACT 2011.
126

8/16/2012

How Do We Change This?
•

Test compiler against “equivalent” code (e.g., best hand-tuned or
autotuned code that performs the same computation, under someinterpretation or “same”)•As part of the Blue Waters project, Padua, Garzaran, Maleki aredeveloping a test suite that evaluates how the compiler does withsuch equivalent code








•

In a perfect world, the compiler would provide the same, excellent
performance for all equivalent versions

Working with vendors to improve the compiler
Identify necessary transformations
Identify opportunities for better interaction with the programmer tofacilitate manual intervention.
Main focus has been on code generation for vector extensions
Result is a compiler whose realized performance is less sensitive to different
expression of code and therefore closer to that of the best hand-tuned
code.
Just by improving automatic vectorization, loop speedups of more than 5
have been observed on the Power 7.

But this is a long-term projectWhat can we do in the meantime?
13

Give “Better” Code to theCompiler• Augmenting current programming
models and languages to exploit
advanced techniques for
performance optimization (i.e.,
autotuning)• Not a new idea, and some tools
already do this.
• But how can these approaches
become part of the mainstream
development?
14

7

8/16/2012

How Can Autotuning Tools Fit
Into Application Development?
• In the short run, just need effective
mechanisms to replace user code with
tuned code Manual extraction of code, specification of

specific collections of code transformations• But this produces at least two versionsof the code (tuned (for a particulararchitecture and problem choice) anduntuned). And there are other issues.
• What does an application want (what isthe Dream)?
15

Application Needs Include• Code must be portable• Code must be persistent• Code must permit (and encourage)
experimentation• Code must be maintainable• Code must be correct• Code must be faster16

8

8/16/2012

Implications of These
Requirements• Portable - augment existing language. Either use
pragmas/comments or extremely portable precompiler Best if the tool that performs all of these steps looks like just likethe compiler, for integration with build process• Persistent Keep original and transformed code around: Golden Copy

• Maintainable Let user work with original code and ensure changes automatically

update tuned code

• Correct
 Do whatever the application developer needs to believe that the

tuned code is correct• In the end, this will require running some comparison tests• Faster Must be able to interchange tuning tools - pick the best tool foreach part of the code No captive interfaces
 Extensibility - a clean way to add new tools, transformations,

properties, …

17Application-Relevant
Abstractions• Language for interfacing with autotuning must convey
concepts that are meaningful to the application
programmer• Wrong: unroll by 5
 Though could be ok for performance expert, and somecompilers already provide pragmas for specifictransformations• Right (maybe): Performance precious, typical loop countbetween 100 and 10000, even, not power of 2
• Middle ground: Apply unroll, align, SIMD
transformations and tune
• We need work at developing higher-level, performanceoriented languages or language extensions
 This would be the “good” future
 Early steps include TCE, Orio, Spiral, …

18

9

8/16/2012

Better Algorithms and Data
Structures• Autotuning only offers the best
performance with the given data
structure and algorithm That’s a big constraint• Processors include hardware to address
performance challenges
 “Vector” function units Memory latency hiding/prefetch
 Atomic update features for shared memory
 Etc.
19

Sparse Matrix-Vector Multiply

Performance Ratio

Barriers to faster code
• “Standard” formats
SCSRsuch as CSR do not 2.00
2
SCSR1.80
meet requirements
4
VSCSR
1.60
-2
for prefetch or
VSCSR
-4
1.40
vectorization
1.20• Modest changes to 1.00
data structure
0.80
enable both
vectorization,
prefetch, for 20Prefetch results in Optimizing Sparse Data
Structures for Matrix Vector Multiply
80% improvement
http://hpc.sagepub.com/content/25/1/115
on P7
20

10

8/16/2012

What Does This Mean For
You?
• It is time to rethink data structures andalgorithms to match the realities of memoryarchitecture We have results for x86 where the benefit is smaller

but still significant
 Better match of algorithms to prefetch hardware isnecessary to overcome memory performance
barriers• Similar issues come up with heterogeneous
processing elements (someone needs todesign for memory motion and concurrent andnonblocking data motion)
21

Is It Communication Avoiding Or
Minimum Solution Time?
• Example: non minimum collective
algorithms• Work of Paul Sack; see “Faster
topology-aware collective
algorithms through non-minimalcommunication”, PPoPP 2012
• Lesson: minimum communicationneed not be optimal
2211

8/16/2012

Allgather
1

2

3

4

Input
Output23

Problem: Recursive-doubling• No congestion model: T=(lgP)α + n(P-1)β• Congestion on torus: T≈(lgP)α + (5/24)nP4/3β• Congestion on Clos network: T≈(lgP)α + (nP/μ)β• Solution approach: move smallest
amounts of data the longest distance2412

8/16/2012

Allgather: recursive halving

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

25

Allgather: recursive halving

ac

bd

ac

bd

eg

fh

eg

fh

ik

jl

ik

jl

mo

np

mo

np

26

13

8/16/2012

Allgather: recursive halving

acik

bdjl

acik

bdjl

egmo

fhnp

egmo

fhnp

acik

bdjl

acik

bdjl

egmo

fhnp

egmo

fhnp

27

Allgather: recursive halving

acikbdjl

acikbdjl

acikbdjl

acikbdjl

egmofhnp

egmofhnp

egmofhnp

egmofhnp

acikbdjl

acikbdjl

acikbdjl

acikbdjl

egmofhnp

egmofhnp

egmofhnp

egmofhnp28

14

8/16/2012

Allgather: recursive halving

acikbdjl
egmofhnp

acikbdjl
egmofhnp

acikbdjl
egmofhnp

acikbdjl
egmofhnp

acikbdjl
egmofhnp

acikbdjl
egmofhnp

acikbdjl
egmofhnp

acikbdjl
egmofhnp

acikbdjl
egmofhnp

acikbdjl
egmofhnp

acikbdjl
egmofhnp

acikbdjl
egmofhnp

acikbdjl
egmofhnp

acikbdjl
egmofhnp

acikbdjl
egmofhnp

acikbdjl
egmofhnp

T=(lg P)α + (7/6)nPβ
29

New Problem: Data
Misordered• Solution: shuffle input data Could shuffle at end (redundant

work; all processes shuffle) Could use non-contiguous datamoves
 Shuffle data on network…

30

15

8/16/2012

Solution: Input shuffle

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

31

Solution: Input shuffle

a

e

b

f

i

m

j

n

c

g

d

h

k

o

l

p

32

16

8/16/2012

Solution: Input shuffle

a

e

b

f

i

m

j

n

c

g

d

h

k

o

l

p

33

Solution: Input shuffle

ab

ef

ab

ef

ij

mn

ij

mn

cd

gh

cd

gh

kl

op

kl

op

34

17

8/16/2012

Solution: Input shuffle

abcdefghabcdefghabcdefghabcdefgh

ijklmnop

ijklmnop

ijklmnop

ijklmnop

abcdefghabcdefghabcdefghabcdefgh

ijklmnop

ijklmnop

ijklmnop

ijklmnop

T=(1+lgP) α + (7/6)nPβ
T≈(lgP)α35 + (7/6)nPβ

Evaluation:
Intrepid BlueGene/P at ANL• 40k-node system
 Each is 4 x 850 MHz PowerPC 450• 512+ nodes is 3d torus; fewer is
3d mesh• xlc -O4
• 375 MB/s delivered per link
 7% penalty using all 6 links both

ways

36

18

8/16/2012

Allgather performance

37

Notes on Allgather• Bucket algorithm (not describedhere) exploits multiple
communication engines on BG• Analysis shows performance near
optimal• Alternative to reorder data step isin memory move; analysis shows
similar performance andmeasurements show reorder step
faster on tested systems
38

19

8/16/2012

Performance on a Node
• Nodes are SMPs
 You have this problem on anything(even laptops)• Tuning issues include the usual Getting good performance out of thecompiler (often means adapting to
the memory hierarchy)• New (SMP) issues include Sharing the SMP with other processes
 Sharing the memory system
39

New (?) Wrinkle – Avoiding
Jitter• Jitter here means the variation in timemeasured when running identicalcomputations
 Caused by other computations, e.g., an OSinterrupt to handle a network event or
runtime library servicing a communication
or I/O request• This problem is in some ways lessserious on HPC platform, as the OS andruntime services are tuned to minimize
impact However, cannot be eliminated entirely
40

20

8/16/2012

Sharing an SMP• Having many cores available
makes everyone think thatthey can use them to solve
other problems (“no one
would use all of them all of
the time”)• However, compute-boundscientific calculations areoften written as if all computeresources are owned by theapplication• Such static scheduling leads
to performance loss
• Pure dynamic scheduling adds
overhead, but is better• Careful mixed strategies areeven better• Thanks to Vivek Kale
41

Happy Medium Scheduling
Static scheduling

Static + 10% dynamic scheduling

100% dynamic scheduling

Performance irregularities introduce loadimbalance.
Pure dynamic has significant overhead; purestatic too much imbalance.
Solution: combined static and dynamicscheduling
Communication Avoiding LU factorization(CALU) algorithm, S. Donfack, L .Grigori, V.
Kale, WG, IPDPS ‘12

time

Scary Consequence: Static
data decompositions will notwork at scale.
Corollary: programming
models with static task
models will not work at scale42

21

8/16/2012

Synchronization and OS Noise• “Characterizing the Influence ofSystem Noise on Large-Scale
Applications by Simulation,”
Torsten Hoefler, Timo Schneider,
Andrew Lumsdaine
 Best Paper, SC10

• Next 3 slides based on this talk…

43

A Noisy Example –Dissemination Barrier• Process 4 is delayed
 Noise propagates “wildly” (of course

deterministic)44

22

8/16/2012

Single Collective Operations
and Noise
Legend:deterministic

3rdquartilemedian
2ndquartileoutliers

outliers• 1 Byte, Dissemination, regular noise,1000 Hz, 100 μs
45

The problem isblocking operations• Simple, data-parallel algorithms easy toreason about but inefficient True for decades, but ignored (memory)• One solution: fully asynchronous
methods
 Very attractive, yet efficiency is low andthere are good reasons for that
 Blocking can be due to fully collective (e.g.,
Allreduce) or neighbor communications(halo exchange) Can we save methods that involve global,
synchronizing operations?
46

23

8/16/2012

Saving Allreduce• One common suggestion is to avoid using
Allreduce
 But algorithms with dot products are among the bestknown Can sometimes aggregate the data to reduce thenumber of separate Allreduce operations
 But better is to reduce the impact of thesynchronization by hiding the Allreduce behind otheroperations (in MPI, using MPI_Iallreduce)• We can adapt CG to nonblocking Allreducewith some added floating point (but perhaps
little time cost)

47

The Conjugate Gradient
Algorithm• While (not converged)
niters += 1;s= A * p;t
= p' *s;alpha = gmma / t;x
= x + alpha * p;r
= r - alpha * s;
if rnorm2 < tol2 ; break ; endz= M * r;gmmaNew = r' * z;beta = gmmaNew / gmma;
gmma = gmmaNew;p= z + beta * p;
end
48

24

8/16/2012

The Conjugate Gradient
Algorithm• While (not converged)
niters += 1;s= A * p;t
= p' *s;alpha = gmma / t;x
= x + alpha * p;r
= r - alpha * s;
if rnorm2 < tol2 ; break ; endz= M * r;gmmaNew = r' * z;beta = gmmaNew / gmma;
gmma = gmmaNew;p= z + beta * p;
end49

CG Reconsidered• By reordering operations, nonblocking
dot products (MPI_Iallreduce in MPI-3)
can be overlapped with other operations• Trades extra local work for overlapped
communication
 On a pure floating point basis, thenonblocking version requires 2 more
DAXPY operations
 A closer analysis shows that some
operations can be merged• More work does not imply more time
50

25

8/16/2012

What’s Different at Peta/Exascale• Performance Focus

 Only a little – basically, the resource is expensive, so a

premium placed on making good use of resource Quite a bit – node is more complex, has more featuresthat must be exploited• Scalability

 Solutions that work at 100-1000 way often inefficient at

100,000-way Some algorithms scale well
• Explicit time marching in 3D
 Some don’t• Direct implicit methods
 Some scale well for a while• FFTs (communication volume in Alltoall) Load balance, latency are critical issues• Fault Tolerance becoming important Now: Reduce time spent in checkpoints
 Soon: Lightweight recovery from transient errors
51

Preparing for the Next
Generation of HPC Systems• Better use of existing resources Performance-oriented programming Dynamic management of resources at all levels
 Embrace hybrid programming models (you havealready if you use SSE/VSX/OpenMP/…)• Focus on results Adapt to available network bandwidth and latency
 Exploit I/O capability (available space grew fasterthan processor performance!)• Prepare for the future Fault tolerance
 Hybrid processor architectures
 Latency tolerant algorithms
 Data-driven systems

52

26

8/16/2012

Recommended Reading• Bit reversal on uniprocessors (Alan Karp, SIAM
Review, 1996)• Achieving high sustained performance in an
unstructured mesh CFD application (W. K.
Anderson, W. D. Gropp, D. K. Kaushik, D. E.
Keyes, B. F. Smith, Proceedings ofSupercomputing, 1999)• Experimental Analysis of Algorithms(Catherine McGeoch, Notices of the American
Mathematical Society, March 2001)• Reflections on the Memory Wall (Sally McKee,
ACM Conference on Computing Frontiers,
2004)
53

Thanks• Torsten Hoefler• Abhinav Bhatele

 Performance modeling lead,Blue Waters; MPI datatype

Process/node mapping• Elena Caraba• David Padua, Maria
Garzaran, Saeed Maleki Nonblocking Allreduce in CG• Van Bui

 Compiler vectorization

 Performance model-based• Dahai Guo

evaluation of programming
models Streamed format exploiting• Funding provided by:prefetch, vectorization, GPU• Vivek Kale

 Blue Waters project (State of

Illinois and the University of
Illinois) Department of Energy, Officeof Science National Science Foundation

 SMP work partitioning• Hormozd Gahvari
 AMG application modeling• Marc Snir and William
Kramer Performance model

advocates

54

27