Computing:
The Third Mode of Scientific Discovery
David H Bailey
Lawrence Berkeley National Laboratory
http://crd.lbl.gov/~dhbailey1Laplace: Father of Modern ScientificComputing?
Computer simulations can be seen as the modern realization of a centuriesold dream known as the “clockwork universe.” This was stated mostclearly by Pierre Simon Laplace in 1773:
 An intelligence knowing all the forces acting in nature at a given instant, as well as
the momentary positions of all things in the universe, would be able tocomprehend in one single formula the motions of the largest bodies as well as ofthe lightest atoms in the world, provided that its intellect were sufficiently powerful
to subject all data to analysis; to it nothing would be uncertain, the future as wellas the past would be present to its eyes.

We now know that this dream, taken to its logical extreme, is unrealistic: Chaos theory teaches us that even simple physical systems exhibit chaos: slightchanges to the present state are exponentially magnified.
 Quantum theory teaches us that it is fundamentally impossible to know bothpositions and velocities at any instant to arbitrarily high accuracy.

But many physical systems are amenable to computer simulation, and evenchaotic systems can be studied computationally.

2Computing:
The Third Mode of Scientific Discovery

Experiment

TheoryComputing3

Progress of Scientific Supercomputers:
Data from the Top500 List

4

A Multi-Disciplinary Symphony of 21stCentury Science and Engineering










Basic physical laws.
Mathematical formulations of these laws.
Numerical algorithms to solve the mathematics.
Computational techniques to implement algorithms.
Grid generation.
Multidimensional optimization techniques to explore parameter variations.
Parallel computing methods.
Scientific visualization.
Performance monitoring and analysis.
Computer system software.
Computer system hardware.

5Basic Physical Laws
Many scientific computations are based on
Newton’s laws, e.g.: force = mass x accel,and gravity= G M1 M2 / R2.
Many large computations are merely repeated 200
applications of these laws on a grid.
Example: Suppose initial velocity = 100 m/s in a 45
!200
deg direction (i.e. 70.71 m/s horiz and70.71 m/s vert), and is subject to gravity.
!400
 Then after 0.1 sec, horiz vel = 70.71 m/s,vert vel = 70.71 – 0.1x9.8 = 69.73 m/s, andobject will have risen 0.1x70.71 = 7.071 m.
 Repeated applications of this calculation
yields the curve at right. Even moreaccurate results can be had with a smaller
time interval, e.g. 0.01 sec or 0.001 sec.
 This is just for one point-sized object.
Large calculations do this for many objects.
6200

400

600

800

1000

1200

1400

Mathematical Formulationsof Physical Laws
 All basic laws of physics can be encapsulated into mathematicalequations. For example, Maxwell’s equations governing light andelectromagnetic radiation can be written as:

∇·E
∇×E
∇·B
∇×B

=4πρ
1 ∂B= −c ∂t
= 04π
1 ∂E
=J+cc ∂t7

Numerical Algorithms
 Advanced numerical algorithms are used to solve the underlying
mathematical formulations of physical laws.
 These algorithms dramatically lower the amount of computation normallyrequired – modern scientific computing could not be done without them.
 Examples:


Dense linear algebra.
Sparse linear algebra.
Spectral methods (i.e., fast Fourier transforms).
N-body methods.
Structured grid methods for partial differential equations.
Unstructured grid methods for partial differential equations.
Distribute-reduce schemes.
Sorting, searching.
Optimization, maximization, minimization.
Many others.
8Computational Techniques
Because of the realities of modern computer architectures, efficient
implementations of basic algorithms require considerable sophistication:
 Data locality is now very important:The “hierarchical” design of processors (Level I cache, Level II cache, Level
III cache, main memory, disk memory) means that considerable attention
must be given to arranging computations for good performance.
It is often more efficient to recompute a value, rather than store it to memory
and later fetch it.

 Changing computer designs means that computer programs that once
were efficient now must be revised.


Floating-point multiply operations once were much more expensive than add/subtract operations, so codes were changed to exploit this. Now there is nodifference.
Computation (add, subtract, multiply, divide, compare) was once much more
expensive than fetching and storing data to memory. Now the opposite istrue.

9

Grid Generation
 In many computational simulations, a key aspect of the computer
implementation is the construction of a grid of points or polygons thatencompass the physical object under study.
 Techniques for generating efficient and effective grids are an active fieldof research.

10

Optimization Techniques After a computational simulation program has been successfully
developed, say to simulate the operation of a jet engine, then researchers
run many instances of this simulation with variations of the input
parameters, in an attempt to find an optimal configuration.
 Advanced optimization techniques permit these searches to be done
significantly more efficiently than by exhaustive search.
 The resulting discipline of multidimensional optimization now is an
essential part of high-performance computing.
 On some large HPC systems, almost all jobs perform multidimensionaloptimization.

11

Parallel Computing Parallel computing (using multiple processors for a single computation)
until recently was the exclusive province of large government laboratories.
 Now, even consumer personal computers have more two, four, eight ormore “cores,” and it is essential to take advantage of these cores to fully
utilize the power of the system.
 Scientists who do not convert their programs to utilize parallel computerswill soon be left behind.
 Parallel computing requires considerable sophistication. Constructs must
be inserted into computer programs to control:






Data layout.
Broadcast of data from the control node to other nodes.
Synchronization between nodes.
Communication between nodes.
Collection of data from all nodes back to a single node.
Parallel input and output of data to external disk drives.

12Amdahl’s Law
A simple principle first enunciated by Gene Amdahl in the 1960s places limits
on speedup from parallel processing: If some fraction P of a computation is amenable to parallelization withspeedup S, then the maximum possible speedup of the entire calculation
is no more than 1 / ((1-P) + P/S).
For instance, if 99.9% of a computation can be effectively run in parallel on
10,000 processors, and the rest must be done serially, then the maximum
speedup is only 909 (out of 10,000).
So far scientists working on large-scale computers have been able to keep
Amdahl’s Law at bay – mostly because the problems they wish to solve
are always at the limit of available computer systems.
But how long will our luck hold out?
 In some arenas, such as climate modeling, computer programs are
already pressing the limits of available concurrency.

13

Scientific Visualization
 With the enormous volumes of data now involved in a large scientificsimulation, it is no longer possible for a scientist to examine bits of data
one by one.
 Instead, sophisticated scientific visualization software must be employed.
 Finding better ways to generate displays, and finding newer approaches
to visualization, are active areas of research.

14

Performance Monitoringand Analysis
 Scientists are often disappointed in the performance (computationalspeed) of their programs – often only a few percent of the peak theoretical
performance is achieved.
 Numerous sophisticated software tools are now available to help
scientists better understand the performance of their programs onadvanced computer architectures.
 The development of automatic performance tuning tools for scientificcomputer programs is an active area of research.

15

System Software
Underlying all of scientific computing is an enormous body of system
software, without which scientific computing would not be possible: Operating system – Linux is the most widely used, although BSD Unix
and IBM’s AIX Unix are also used.
 Compilers – before any program is executed, it must be “compiled”, i.e.,translated to machine instructions.
 Modern compilers employ enormously sophisticated schemes to generate
the most efficient possible machine code.
 Support for parallel computing.
 Support for large-scale data storage.
 Support for networking.

16Computer Hardware
A large-scale scientific computer is much more than just a collection of chips– the large-scale system architecture is also important.
 Until about 2000, vector supercomputers were the most common platform
for large-scale scientific computing.
 Now most scientific computing is done on large clusters of units, each ofwhich is often an off-the-shelf personal computer system.
 The interprocessor network is very important – without a very high-speed
network, many scientific computations would be mired in network
congestion.

17

Moore’s Law: 44 Years of Sustained
Exponential Growth in Computer PowerIn 1965 Gordon Moore (cofounder of Intel with Andy
Grove and Robert Noyce ofGrinnell College) predictedthat the transistor density ofsemiconductor chips would
double every 12-18 months.
After 44 years, no end is yet insight!

2X transistors/chip every 1.5 years
Called “Moore’s Law”
18

LBNL’s National Energy Research
Scientific Computing Center (NERSC) NERSC serves a large population of users:~3000 users, ~400 projects, ~500 codes Allocations managed by the Department of Energy:
 10% INCITE awards:
 Open to all of science, not just DOE-funded projects.
 Large allocations, extra service.
 70% Production (ERCAP) awards:
 From 10,000 CPU-hours to 5,000,000 CPU-hours.
 10% each NERSC and DOE reserve for special needs.

19

NERSC 2009 Configuration
Current flagship computer system:• Cray XT4• 9,740 nodes; 19,480 cores• 78 Tbyte main memory• 355 Tflops/s theoretical peak• ~25 Tflops/s sustained on realscientific work
Newly announced upgrade (3Q 2010):• Cray XT-5, 6400 nodes, 153,600 cores• 1.9+ GHz AMD Opteron chips• 1.17 Pflop/s peak performance• Expect 100 Tflop/s sustained• 217 TB DDR3 memory total• Gemini Interconnect• 2 PByte disk, 80 GByte/s bandwidth• Liquid cooled
20

Validating Climate Models
 “20th Century Reanalysis” using an Ensemble Kalman filter to fill in
missing climate data since; can be used for validation of models.
 Principal investigator: G. Compo, Univ. of Boulder.
•Science Results:– Reproduced 1922
Knickerbocker storm anddust storms of 1930s.
– Building maps every 6hours 1982-2008.
• Scaling Results:– Scales to 2400 cores.
– Switched to higher
resolution algorithm withFranklin access.
Granted 1,000,000 CPUhours in 2009.

Sea level pressures with color showing uncertainty(a&b); precipitation (c); temperature (d). Dots indicate
measurements locations (a).

21Global Cloud System Resolving Models
Surface Altitude (feet)

200km
Typical resolu5on ofIPCC AR4 models

25km
Upper limit of climate
models with cloudparameteriza5ons
221km
Cloud system resolving
modelsare a transforma5onal
changeClimate Modeling with CCSM
 Climate Change Simulations with CCSM: Moderate and High
Resolution Studies.
 Principal investigator: Warren Washington, NCAR.
•Science Results:– 2000-2100 simulation onpreserving polar bear
habitat by reducing nonCO2 emissions.
– Separating human andnatural forcings inclimate change.
– Sulfate and carbon
sulfate impact isolated.
Granted 12,000,000 CPUhours in 2009.
Typical runs utilize
5000-6000 cores.
23

Material Modeling for Geoscience Calculation: Simulation of seismic waves through silicates, which make up
80% of the Earth’s mantle; important for understanding structures in oil welldrilling, carbon sequestration, earthquakes, etc.
 PI: John Wilkins, Ohio State University

Science Result:– Seismic analysis shows jumps in wave velocity due to structuralchanges in silicates under pressureFirst use of Quantum
Monte Carlo (QMC)
for computing elastic
constants.
Typical runs utilize
8,000 cores.

24

Low-Swirl Combustion Burner
Simulation
 Low-swirl burners were invented in 1991 atLBNL.
 They are now being developed for near-zeroemission gas turbines (2007 R&D 100 Award).
 They dramatically reduce pollutants by using
special “lean premixed” fuels in power
generation and transportation.
 Combustion with these fuels can be highly
unstable, making robust systems hard todesign.

25

Low-Swirl Burner Simulation
 Computation: Numerical simulation of a lean premixed hydrogen
flame in a laboratory-scale low-swirl burner (LMC code). Uses a low
Mach number formulation, adaptive mesh refinement (AMR) anddetailed chemistry and transport.
 PI: John Bell, LBNL
Science Result:• Simulations capture cellular structure of leanhydrogen flames and provide a quantitative
characterization of enhanced local burningstructure.
• LMC dramatically reduces time and memory.
• Scales to 4K cores, typically run at 2K• Used 9,600,000 CPU-hours in 2008; allocated5,500,000 CPU-hours in 2009.
J B Bell, R K Cheng, M S Day, V E Beckner and M J Lijewski, Journal of Physics: Conference Series
125 (2008) 012027.
26

Nanoscience Calculations and Scalable
Algorithms• Calculation: Linear Scaling 3D Fragment (LS3DF). Density Functional
Theory (DFT) calculation numerically equivalent to more common
algorithm, but scales with O(n) in number of atoms rather than O(n3).
• Principal investigator: L.W. Wang, LBNL.
Science Results• Calculation of 3500 atom XnTe alloy
used to predict efficiency of a newsolar cell material.
• Ran on 17,000 cores.
• Took 1 hour vs months for previousO(n3) algorithm.
• Good efficiency (40% of peak).
• Won ACM Gordon Bell Prize at SC08.

27

ZnTeO Alloy Calculations
Using LS3DF• Run on Franklin (XT4) at NERSC led to the ACM Gordon Bell Award.
• Subsequent runs on Intrepid (BG/P) at Argonne and later Jaguar (XT5) at ORNL.
LS3DF

450

XT5: 442 Tflops

400• NCCS Jaguar• 36,864 cores• 33% of peak.

350

TFlop/s

Performance [ Tflop/s]

500Jaguar
IntrepidFranklin

300

BG/P: 224 Tflops• ALCF Intrepid• 163,840 cores• 40% of peak

250
200

XT4: 139 TFlops

150• NERSC Franklin• 147,146 cores• 40% of peak

100
500050,000

100,000

NumberCoresof cores
28

150,000

200,000NERSC User George Smootwins 2006 Nobel Prize in Physics

COBE Experiment showedanisotropy of CMB

Cosmic Microwave
Background Radiation(CMB): an image of theuniverse at 400,000 years.

29

Cosmic Microwave Data Analysis
Experiment

DateSize

Bell Labs

1965

1

COBE

1989

109

BOOMERanG

2000

109

WMAP

2001

1010

 CMB data sets have to be analyzed asPlanck20081011a whole: Complex data correlations.
 No simple “divide and conquer”
scheme will work.

PolarBear

2010

1012

CMBpol>2020

1014

 CMB data sets are very large:

 Very low signal/noise per sample.
 Higher resolution observations offainter signals with more detectors
at more frequencies.

30Cosmic Microwave Background
Computations
Calculation: Planck full focal plane 1 year simulation of CMB (T & P),
detector noise & foregrounds.
 74 detectors at 9 frequencies.
 750 billion observations.
 54,000 files, 3 TB data.
 Principal investigator: J. Borrill, LBNL.

Science Result:• 9 “routine” 1-frequency maps.
• Unprecedented 9-frequency map withentire simulated Planck data set.

Scaling Results:• 9-frequence problem ran for < 1 hour on
16K cores.
31

Evolution Of CMB Satellite Maps

32

Type 1a Supernovae Simulation

Three phases of the gravitationally confined detonation mechanism. The
images show the flame surface and the star at 0.5 s, 1.0 s, and 1.7 s.

 Simulations by D. Lamb et al, U. Chicago done at NERSC andLLNL.
 Show that gravitationally confined detonation may trigger theexplosion of Type 1a supernovae.

33Quantum Effects of Photosynthesis

Sunlight absorbed bybacteriochlorophyll (green)
within the FMO protein (gray)generates a wavelike motionof excitation energy.
Quantum mechanicalproperties can be mapped
through the use of twodimensional electronic
spectroscopy.
(Image courtesy of G. Engel)Spectrum modeling and quantum dynamics simulations: Oscillations correlate with the quantum coherence in thesystem.
 Energy transfer pathways shown inside network ofphotosynthetic pigment-protein complexes.
34Chemistry: Better Fuel Cell Design

 Polymer electrolyte membrane (PEM) fuel cell requires right amountof hydration for optimal power output.
 Simulations of ionized Nafion varying levels of hydration (λ=3.5 and
λ=16) reveal different properties 3 Phys. Chem. B papers by R. Devanathan, et al (PNNL).

35

Molecular Dynameomics
 V. Daggett, U Washington,
2,000,000 CPU-hours.
 Understand protein folding
pathways by ‘unfolding’ proteinsat high temperature.
 Computed unfolding of 151 mostcommon fold structures atdifferent temperatures.
 Multiple runs of MD calculationfor each fold/temperature pair.

The first 156 protein targets

36Exploring Nanoelectronics with Theory:
Single Molecule Electrical Junctions
Electron flow

H2
PdPdShown at left is a single hydrogen molecule (in white) bridging
palladium point contacts. At right, a density plot of the dominanttransmitting electronic state reveals a significant reflection of charge
at the left Pd contact, leading to a high resistance, consistent withrecent experiments. (Red is high electronic density in the plot, blueis low.)

37

Steven Louie,
Marvin Cohen,
UC Berkeley
Jeff Neaton, LBNL
Molecular Foundry

Discovering and Verifying New
Mathematical Formulas by Computer
One surprising new application of high-performance computing is thediscovery of previously unknown mathematical identities, via a combinationof high-precision calculations (typically 100-1000 digits), combined withinteger relation algorithms to identify the calculated constants. Examples:∞!

k=1π=

π2

=1k 2 − x2=

L−7 (2) =' 1' 1' 1000)

"
#∞!
1421
1−−−k16
8k + 1 8k + 4 8k + 5 8k + 6n=0"#∞
1! 114421672549−−−+864k (6k + 1)2(6k + 2)2
(6k + 3)2
(6k + 4)2
(6k + 5)2
k=0
∞
k−1!
& " 1 − 4 x2 /m2 #1
3$2k%
2k k (1 − x2 /k 2 ) m=1 1 − x2 /m2
k=1(√ ((' π/2(24( tan t + 7 (√√ ( dtlog (( tan t − 7 (7 7 π/3
dr1 dr2 dr3 ds1 ds2 ds3(r1 − s1)2 + (r2 − s2)2 + (r3 − s3)2√√√√ +1 *=6 + 6 2 − 12 3 − 10π + 30 log(1 + 2) + 30 log(2 + 3)
1538

Summary
 Scientific computing has vastly expanded in sophistication and powerover the past 40 years, and is now widely regarded as a third mode ofscientific discovery, after theory and experiment.
 Modern scientific computing is a multidisciplinary “symphony” involving
scientists and engineers from many fields.
 The power of the leading-edge systems has closely followed Moore’s
Law in an exponentially upward path, and no end is yet in sight.
Major challenges:• In order to utilize future systems efficiently, computer programs mustpossess and exhibit enormous parallelism (1010-way or more).
• Exotic architectures (e.g., hybrid systems employing game processors)
will present difficult programming and software challenges.
• Daunting electric power requirements projected for future systems will
require innovation in hardware, software and applications.

39