# Presentation: 769145

## CS267Applications of Parallel ComputersLecture 1:  Introduction

- Horst D. Simon
- hdsimon@lbl.gov
- http://www.nersc.gov/~simon

- CS267 Lecture 1: Intro

## Outline

- Introduction
- Large important problems require powerful computers
- Why powerful computers must be parallel processors
- Principles of parallel computing performance
- Structure of the course

- CS267 Lecture 1: Intro

## Why we need powerful computers

- CS267 Lecture 1: Intro

##  Simulation: The Third Pillar of Science 

- Traditional scientific and engineering paradigm:
- Do theory or paper design.
- Perform experiments or build system.
- Limitations:
- Too difficult -- build large wind tunnels.
- Too expensive -- build a throw-away passenger jet.
- Too slow -- wait for climate or galactic evolution.
- Too dangerous -- weapons, drug design, climate experimentation.
- Computational science paradigm:
- Use high performance computer systems to simulate the phenomenon
- Base on known physical laws and efficient numerical methods.

- CS267 Lecture 1: Intro

## Some Particularly Challenging Computations

- Science
- Global climate modeling
- Astrophysical modeling
- Biology: genomics; protein folding; drug design
- Computational Chemistry
- Computational Material Sciences and Nanosciences
- Engineering
- Crash simulation
- Semiconductor design
- Earthquake and structural modeling
- Computational fluid dynamics
- Combustion
- Business
- Financial and economic modeling
- Transaction processing, web services and search engines
- Defense
- Nuclear weapons -- test by simulations
- Cryptography

- CS267 Lecture 1: Intro

## Units of Measure in HPC

- High Performance Computing (HPC) units are:
- Flop/s: floating point operations
- Bytes: size of data
- Typical sizes are millions, billions, trillions...
- Mega	Mflop/s = 106 flop/sec	Mbyte = 106 byte
-  						(also 220 = 1048576)
- Giga	Gflop/s = 109 flop/sec	Gbyte = 109 byte
-  						(also 230 = 1073741824)
- Tera	Tflop/s = 1012 flop/sec	Tbyte = 1012 byte
-  						(also 240 = 10995211627776)
- Peta	Pflop/s = 1015 flop/sec	Pbyte = 1015 byte
-  						(also 250 = 1125899906842624)
- Exa		Eflop/s = 1018 flop/sec	Ebyte = 1018 byte

- CS267 Lecture 1: Intro

**Notes:**
Add definition of flop, where are current machines (size speed)

## Economic Impact of HPC

- Airlines:
- System-wide logistics optimization systems on parallel systems.
- Savings: approx. $100 million per airline per year.
- Automotive design:
- Major automotive companies use large systems (500+ CPUs) for:
- CAD-CAM, crash testing, structural integrity and aerodynamics.
- One company has 500+ CPU parallel system.
- Savings: approx. $1 billion per company per year.
- Semiconductor industry:
- Semiconductor firms use large systems (500+ CPUs) for
- device electronics simulation and logic validation
- Savings: approx. $1 billion per company per year.
- Securities industry:
- Savings: approx. $15 billion per year for U.S. home mortgages.

- CS267 Lecture 1: Intro

## Global Climate Modeling Problem

- Problem is to compute:
- f(latitude, longitude, elevation, time) 
-                     temperature, pressure, humidity, wind velocity
-  Approach:
- Discretize the domain, e.g., a measurement point every 10 km
- Devise an algorithm to predict weather at time t+1 given t

- Uses:
- Predict major events, e.g., El Nino
- Use in setting air emissions standards

- Source: http://www.epm.ornl.gov/chammp/chammp.html

- CS267 Lecture 1: Intro

## Global Climate Modeling Computation

- One piece is modeling the fluid flow in the atmosphere
- Solve Navier-Stokes problem
- Roughly 100 Flops per grid point with 1 minute timestep
- Computational requirements:
- To match real-time, need 5x 1011 flops in 60 seconds = 8 Gflop/s
- Weather prediction (7 days in 24 hours)  56 Gflop/s
- Climate prediction (50 years in 30 days)  4.8 Tflop/s
- To use in policy negotiations (50 years in 12 hours)  288 Tflop/s
- To double the grid resolution, computation is at least 8x
- State of the art models require integration of atmosphere, ocean, sea-ice, land models, plus possibly carbon cycle, geochemistry and more
- Current models are coarser than this

- CS267 Lecture 1: Intro

## High Resolution Climate Modeling on NERSC-3 – P. Duffy, et al., LLNL

***High Resolution Climate Modeling on NERSC-3 – P. Duffy, et al., LLNL***

- CS267 Lecture 1: Intro

## Comp. Science : A 1000 year climate simulation

*Warren Washington and Jerry Meehl, National Center for Atmospheric Research; Bert Semtner, Naval Postgraduate School; John Weatherly, U.S. Army Cold Regions Research and Engineering Lab Laboratory et al.*

-  A 1000-year simulation demonstrates the ability of the new Community Climate System Model (CCSM2) to produce a long-term, stable representation of the earth’s climate.
- 760,000 processor hours used
**http://www.nersc.gov/aboutnersc/pubs/bigsplash.pdf**

- CS267 Lecture 1: Intro

## Comp. Science: High Resolution Global Coupled Ocean/Sea Ice Model

*Mathew E. Maltrud, Los Alamos National Laboratory; Julie L. McClean, Naval Postgraduate School.*
-      The objective of this project is to couple a high-resolution ocean general circulation model with a high-resolution dynamic-thermodynamic sea ice model in a global context.

- Currently, such simulations are typically performed with a horizontal grid resolution of about 1 degree. This project is running a global ocean circulation model with horizontal resolution of approximately 1/10th degree.
- Allows resolution of geographical features critical for climate studies such as Canadian Archipelago
**http://www.nersc.gov/aboutnersc/pubs/bigsplash.pdf**

- CS267 Lecture 1: Intro

## Parallel Computing in Web Search

- Functional parallelism: crawling, indexing, sorting
- Parallelism between queries: multiple users
- Finding information amidst junk
- Preprocessing of the web data set to help find information
- General themes of sifting through large, unstructured data sets:
- when to put white socks on sale
- what advertisements should you receive
- finding medical problems in a community

- CS267 Lecture 1: Intro

## Document Retrieval Computation 

**Document Retrieval Computation **

- Approach:
- Store the documents in a large (sparse) matrix
- Use Latent Semantic Indexing (LSI), or related algorithms to “partition”
- Needs large sparse matrix-vector multiply

- # keywords
- ~100K

- # documents  ~= 10 M

- 24      65         18

- Matrix is compressed
- “Random” memory access
- Scatter/gather vs. cache miss per 2Flops

- Ten million documents in typical matrix.
- Web storage increasing 2x every 5 months.
- Similar ideas may apply to image retrieval.

- x

- CS267 Lecture 1: Intro

## Transaction Processing

- Parallelism is natural in relational operators: select, join, etc.
- Many difficult issues: data partitioning, locking, threading.

- (mar. 15, 1996)

- CS267 Lecture 1: Intro

## Why powerful computers are parallel

- CS267 Lecture 1: Intro

## Technology Trends: Microprocessor Capacity

**2X transistors/Chip Every 1.5 years**
**Called “**_**Moore’s Law**_**”**
** **

**Moore’s Law**

**Microprocessors have become smaller, denser, and more powerful.**

**Gordon Moore (co-founder of Intel) predicted in 1965 that the transistor density of semiconductor chips would double roughly every 18 months. **

- Slide source: Jack Dongarra

- CS267 Lecture 1: Intro

## Impact of Device Shrinkage

- What happens when the feature size shrinks by a factor of x ?
- Clock rate goes up by x
- actually less than x, because of power consumption
- Transistors per unit area goes up by x2
- Die size also tends to increase
- typically another factor of ~x
- Raw computing power of the chip goes up by ~ x4 !
- of which x3 is devoted either to parallelism or locality

- CS267 Lecture 1: Intro

## Microprocessor Transistors

- CS267 Lecture 1: Intro

## Microprocessor Clock Rate

- CS267 Lecture 1: Intro

## Empirical Trends: Microprocessor Performance

- CS267 Lecture 1: Intro

## SIA Projections for Microprocessors

**SIA Projections for Microprocessors**

***Compute power ~1/(Feature Size)******3***

**0.01**

**0.1**

**1**

**10**

**100**

**1000**

**1995**

**1998**

**2001**

**2004**

**2007**

**2010**

**Year of Introduction**

**Feature Size **

**(microns) & Million **

**Transistors per chip**

***Feature Size***

***(microns)***

***Transistors per***

***chip x 10**(-6)***

- based on F.S.Preston, 1997

- CS267 Lecture 1: Intro

## But there are limiting forces: Increased cost and difficulty of manufacturing

**Moore’s 2****nd**** law (Rock’s law)**

- Demo of 0.06 micron CMOS

- CS267 Lecture 1: Intro

## How fast can a serial computer be?

- Consider the 1 Tflop/s sequential machine:
- Data must travel some distance, r, to get from memory to CPU.
- Go get 1 data element per cycle, this means 1012 times per second at the speed of light, c = 3x108 m/s.  Thus r < c/1012 = 0.3 mm.
- Now put 1 Tbyte of storage in a 0.3 mm x 0.3 mm area:
- Each word occupies about 3 square Angstroms, or the size of a small atom.

- r = 0.3 mm

- 1 Tflop/s, 1 Tbyte sequential machine

- CS267 Lecture 1: Intro

## Microprocessor Transistors and Parallelism

**Microprocessor Transistors and Parallelism**

- Bit-Level
- Parallelism

- Instruction-Level
- Parallelism

- Thread-Level
- Parallelism?

- CS267 Lecture 1: Intro

## “Automatic” Parallelism in Modern Machines

- Bit level parallelism: within floating point operations, etc.
- Instruction level parallelism (ILP): multiple instructions execute per clock cycle.
- Memory system parallelism: overlap of memory operations with computation.
- OS parallelism: multiple jobs run in parallel on commodity SMPs.
- There are limitations to all of these!
- Thus to achieve high performance, the programmer needs to identify, schedule and coordinate parallel tasks and data.

- CS267 Lecture 1: Intro

## The Opportunity: Dramatic Advances in ComputingTerascale Today, Petascale Tomorrow

**0.1**

**1**

**10**

**100**

**1,000**

**1998**

**2000**

**2002**

**Peak Teraflops**

**2004**

**1996**

**2006**

**Increased Use of Parallelism**

**Microprocessor Advances**

**MICROPROCESSORS**
- 2x increase in microprocessor speeds every 18-24 months
- (“Moore’s Law”)
**PARALLELISM**
- More and more processors being used on single problem
**INNOVATIVE DESIGNS**
- Processors-in-Memory
- HTMT

**IBM “Blue Gene”**
**Innovative Designs**

- CS267 Lecture 1: Intro

## Technology Trends in Parallel Computers

- CS267 Lecture 1: Intro

## Microprocessors have made desktop computing in 2000 what supercomputing was in 1990.
Massive Parallelism has changed the “high end” completely.
Today clusters of Symmetric Multiprocessors are the standard supercomputer architecture.

**Massive Parallelism has changed the “high end” completely.**
**Today clusters of Symmetric Multiprocessors are the standard supercomputer architecture.**

***Nevertheless, the microprocessor revolution will continue with little attenuation for ~10 years.****** ***

- CS267 Lecture 1: Intro

## A Parallel Computer Today: NERSC-3 Vital Statistics

- 5 Teraflop/s Peak Performance – 3.05 Teraflop/s with Linpack
- 208 nodes, 16 CPUs per node at 1.5 Gflop/s per CPU
- “Worst case” Sustained System Performance measure .358 Tflop/s (7.2%)
- “Best Case” Gordon Bell submission 2.46 on 134 nodes (77%)
- 4.5 TB of main memory
- 140 nodes with 16 GB each, 64 nodes with 32 GBs, and 4 nodes with 64 GBs.
- 40 TB total disk space
- 20 TB formatted shared, global, parallel, file space; 15 TB local disk for system usage
- Unique 512 way Double/Single switch configuration

- CS267 Lecture 1: Intro

## TOP500 – June 2002  (see www.top500.org)

- CS267 Lecture 1: Intro

## TOP500 - Performance

- CS267 Lecture 1: Intro

## Manufacturers

**Manufacturers**

- CS267 Lecture 1: Intro

## Manufacturers

**Manufacturers**

- CS267 Lecture 1: Intro

## Processor Type

- CS267 Lecture 1: Intro

## Chip Technology

- CS267 Lecture 1: Intro

## Architectures

- CS267 Lecture 1: Intro

## NOW - Cluster

- CS267 Lecture 1: Intro

## Why do we have only commodity components?

- CS267 Lecture 1: Intro

## Dead Supercomputer Society

- ACRI
- Alliant
- American Supercomputer
- Ametek
- Applied Dynamics
- Astronautics
- BBN
- CDC
- Convex
- Cray Computer
- Cray Research
- Culler-Harris
- Culler Scientific
- Cydrome
- Dana/Ardent/Stellar/Stardent
- Denelcor
- Elexsi
- ETA Systems
- Evans and Sutherland Computer
- Floating Point Systems
- Galaxy YH-1

- Goodyear Aerospace MPP
- Gould NPL
- Guiltech
- Intel Scientific Computers
- International Parallel Machines
- Kendall Square Research
- Key Computer Laboratories
- MasPar
- Meiko
- Multiflow
- Myrias
- Numerix
- Prisma
- Thinking Machines
- Saxpy
- Scientific Computer Systems (SCS)
- Soviet Supercomputers
- Supertek
- Supercomputer Systems
- Suprenum
- Vitesse Electronics

- CS267 Lecture 1: Intro

## Warm Up Homework Assignment

- CS267 Lecture 1: Intro

## The Parallel Computing Challenge: improving real performance of scientific applications

**The Parallel Computing Challenge: ****improving real performance of scientific applications**

**0.1**

**1**

**10**

**100**

**1,000**

**2000**

**2004**

**Teraflops**

**1996**

**Peak Performance is skyrocketing**
- In 1990’s, peak performance increased 100x; in 2000’s, it will increase 1000x
**But ...**
- Efficiency declined from 40-50% on the vector supercomputers of 1990s to as little as 5-10% on parallel supercomputers of today
**Close the gap through ...**
- Mathematical methods and algorithms that achieve high performance on a single processor and scale to thousands of processors
- More efficient programming models for massively parallel supercomputers
- Parallel Tools

**Performance**
**Gap**

**Peak Performance**

**Real Performance**

- CS267 Lecture 1: Intro

## Performance Levels

- Peak advertised performance (PAP)
- You can’t possibly compute faster than this speed
- LINPACK (TPP)
- The “hello world” program for parallel computing
- Gordon Bell Prize winning applications performance
- The right application/algorithm/platform combination plus years of work
- Average sustained applications performance
- What one reasonable can expect for standard applications
- When reporting performance results, these levels are often confused, even in reviewed publications

- CS267 Lecture 1: Intro

## Performance Levels (for example on NERSC-3)

- Peak advertised performance (PAP): 5 Tflop/s
- LINPACK (TPP): 3.05 Tflop/s
- Gordon Bell Prize winning applications performance : 2.46 Tflop/s
- Material Science application at SC01
- Average sustained applications performance: ~0.4 Tflop/s
- Less than 10% peak!

- CS267 Lecture 1: Intro

## First Assignment

- See home page for details.
- Find an application of parallel computing and build a web page describing it.
- Choose something from your research area.
- Or from the web or elsewhere.
- Create a web page describing the application.
- Describe the application and provide a reference (or link)
- Describe the platform where this application was run
- Find peak and LINPACK performance for the platform and its rank on the TOP500 list
- Find performance of your selected application
- What ratio of sustained to peak performance is reported?
- Evaluate project: How did the application scale? What were the major difficulties in obtaining good performance? What tools and algorithms were used?
- Send us (Horst and David) the link and add the webpage to your portfolio
- Due next week, Thursday (9/5).

- CS267 Lecture 1: Intro

## Course Organization

- CS267 Lecture 1: Intro

## Schedule of Topics

- Introduction
- Parallel Programming Models and Machines
- Shared Memory and Multithreading
- Distributed Memory and Message Passing
- Data parallelism
- Sources of Parallelism in Simulation
- Tools
- Languages (UPC)
- Performance Tools
- Visualization
- Environments
- Algorithms
- Dense Linear Algebra
- Partial Differential Equations (PDEs)
- Particle methods
- Load balancing, synchronization techniques
- Sparse matrices
- Applications: biology, climate, combustion, astrophysics
- Project Reports

- CS267 Lecture 1: Intro

## Reading Materials

- Some on-line texts:
- Demmel’s notes from CS267 Spring 1999, which are similar to 2000 and 2001.  However, they contain links to html notes from 1996.
- _[http://www.cs.berkeley.edu/~demmel/cs267_Spr99/](http://www.cs.berkeley.edu/~demmel/cs267_Spr99/)_
- Yelick’s notes from Fall 2001
- _[http://www.cs.berkeley.edu/~dbindel/cs267ta/](http://www.cs.berkeley.edu/~dbindel/cs267ta/)_
- Ian Foster’s book, “Designing and Building Parallel Programming”.
- _[http://www-unix.mcs.anl.gov/dbpp/](http://www-unix.mcs.anl.gov/dbpp/)_
- Recommended text:
- “Sourcebook for Parallel Computing”, by Dongarra, Foster, Fox, ..
- Available in bookstores in November 2002; now available as a reader or on CD;
- Potentially Useful
- “Performance Optimization of Numerically Intensive Codes” by Stefan Goedecker and Adolfy Hoisie
- This is a practical guide to optimization, mostly for those of you who have never done any optimization

- CS267 Lecture 1: Intro

## Other Topics or Interest

- Field Trips
- NERSC Visualization lab, Thursday, October 3 confirmed
- Silicon Valley/Computer History Museum, Tuesday, November 26 ?
- Projects
- MATLAB anyone? There is a parallel MATLAB available on seaborg
- Student Volunteer at SC2002 in Baltimore, November 16 – 22, 2002
- _[http://hpc.ncsa.uiuc.edu:8080/sc2002/svol_registration.html](http://hpc.ncsa.uiuc.edu:8080/sc2002/svol_registration.html)_ for the student volunteer program
- _[http://www.sc2002.org](http://www.sc2002.org/)_ for the conference
- Also of interest:
- ACTS Parallel Tools Workshop for Students in Berkeley, Sept. 4 – 7, 2002 see _[http://acts.nersc.gov/workshop](http://acts.nersc.gov/workshop)_ ; send e-mail to Osni Marques at _[oamarques@lbl.gov](mailto:oamarques@lbl.gov)_ to register; about five spots available for CS267

- CS267 Lecture 1: Intro

## Requirements

- Fill out on-line account request for Millennium machine.
- See course web page for pointer
- Fill out request for NERSC account
- Form available in class
- Fill out survey
- e-mail to David if you missed this lecture
- Build a portfolio
- Every week or two students will report explorations, ideas, proposed work, and work to the TA via an organized webpage, document or notebook.
- There will be about four programming assignments geared towards hands-on experience, interdisciplinary teams.
- There will be a Final Project
- Teams of 2-3, interdisciplinary is best.
- Interesting applications or advance of systems.
- Presentation (poster session)
- Conference quality paper

- CS267 Lecture 1: Intro

## What you should get out of the course

- In depth understanding of:
- When is parallel computing useful?
- Understanding of parallel computing hardware options.
- Overview of programming models (software) and tools.
- Some important parallel applications and the algorithms
- Performance analysis and tuning

- CS267 Lecture 1: Intro

## Administrative Information

- Instructors:
- Horst D. Simon, 329 Soda, _[hdsimon@lbl.gov](mailto:hdsimon@lbl.gov)_, (510) 486-7377
- TA: David Garmire, 566 Soda, _[strive@eecs.berkeley.](mailto:strive@eecs.berkeley.edu)__[edu](mailto:strive@eecs.berkeley.edu)_, (510) 643 6763
- Accounts – fill out online registration for Millenium; fill out form for NERSC accounts on seaborg
- Class survey – fill out today
- Lecture notes are based on previous semester notes:
- Jim Demmel, David Culler, David Bailey, Bob Lucas, Kathy Yelick and myself
- Reader based on “Sourcebook for Parallel Computing”; hardcopy or CD option
- Discussion section: Wed. 1:30 – 2:30 in 405 Soda; not every week
- Most class material and lecture notes are at:
- http://www.cs.berkeley.edu/~strive/cs267

- CS267 Lecture 1: Intro