# Presentation: 190570

## Principles of Parallel Computing,Uniprocessor Optimizations and Matrix Multiplication 

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

- CS267 Lecure 2

## Outline

- Principles of Parallel Computing
- Parallelism in Modern Processors
- Memory Hierarchies
- Matrix Multiply Cache Optimizations
- Bag of Tricks

- CS267 Lecure 2

## Principles of Parallel Computing

- Speedup, efficiency, and Amdahl’s Law
- Finding and exploiting granularity
- Preserving data locality
- Load balancing
- Coordination and synchronization
- Performance modeling
- All of these things make parallel programming more difficult than sequential programming.

- CS267 Lecure 2

## Speedup

- The *speedup* of a parallel application is
- Speedup(p) = Time(1)/Time(p),
- Where Time(1) = execution time for a single processor and Time(p) = execution time using p parallel processors
- If S(p) = p we have *perfect speedup (or linear speedup)*
- We will rarely have perfect speedup.
- Understanding why there is no parallel speedup will help finding ways improving the applications performance on parallel computers

- CS267 Lecure 2

## Speedup (cont.)

- Speedup compares an application with itself on one and on p processors
- It is more realistic to compare
- The execution time of the best serial application on a single processor
- versus
- The execution time of best parallel algorithm on p processors
- Question: can we find “superlinear” speedup, that is
- 				S > 1   ?
- The efficiency of an application is defined as
- 				E(p) = S(p)/p
- E(p) <= 1; for perfect speedup E(p) = 1

- CS267 Lecure 2

## Perfect Speedup (Efficiency = 1)

- Is rarely ever achievable, because
- Lack of perfect parallelism in the application or algorithm
- Lack of perfect load balancing
- Cost of communication
- Cost of contention for resources
- Synchronization time

- CS267 Lecure 2

## Finding Enough Parallelism

- Suppose only part of an application seems parallel
- Amdahl’s law
- Let s be the fraction of work done serially, so                                (1-s) is fraction done in parallel
- P = number of processors.

- Speedup(p) = T(1)/T(p)
- T(p) = (1-s)*T(1)/p +s*T(1)
- Speedup(p) = p/(1 + (p-1)*s)

- Even if the parallel part speeds up perfectly, we may be limited by the sequential portion of code.

- CS267 Lecure 2

## Amdahl’s Law (for 1024 processors)

- Does this mean parallel computing is a hopeless enterprise?

**Source: Gustafson, Montry, Benner**

- CS267 Lecure 2

## Scaled Speedup

- See: Gustafson, Montry, Benner, “Development of Parallel Methods for a 1024 Processor Hypercube”, SIAM J. Sci. Stat. Comp. 9, No. 4, 1988, pp.609.

- CS267 Lecure 2

## Scaled Speedup (background)

- CS267 Lecure 2

##  Limits of Scaling – an example of  a current debate

- Test run on global climate model reported on the Earth Simulator sustained performance of about 28 TFLOPS on 640 nodes. The model was an atmospheric global climate model (T1279L96) developed originally by CCSR/NEIS and tuned by ESS.
- This corresponds to scaling down to a 10 km^2 grid
- Many physical modeling assumptions from a 200 km^2 grid don’t hold any longer
- The climate modeling community is debating the significance of these results

- CS267 Lecure 2

## Little’s Law

- Principle (Little's Law): the relationship of a production system in steady state is:
-           Inventory = Throughput × Flow Time
- For parallel computing, this means:
- 	        Concurrency = bandwidth  x latency
- Example: 1000 processor system, 1 GHz clock, 100 ns memory latency, 100 words of memory in data paths between CPU and memory.
- Main memory bandwidth is:
-       ~ 1000 x 100 words x 109/s = 1014 words/sec.
- To achieve full performance, an application needs:
-       ~ 10-7 x 1014 = 107 way concurrency

- CS267 Lecure 2

## Overhead of Parallelism

- Given enough parallel work, this is the most significant barrier to getting desired speedup.
- Parallelism overheads include:
- cost of starting a thread or process
- cost of communicating shared data
- cost of synchronizing
- extra (redundant) computation
- Each of these can be in the range of milliseconds         (= millions of flops) on some systems
- Tradeoff: Algorithm needs sufficiently large units of work to run fast in parallel (i.e. large granularity), but not so large that there is not enough parallel work.

- CS267 Lecure 2

## Locality and Parallelism

- Large memories are slow, fast memories are small.
- Storage hierarchies are large and fast _on average._
- Parallel processors, collectively, have large, fast memories -- the slow accesses to “remote” data we call “communication”.
- Algorithm should do most work on local data.

- Proc

- Cache

- L2 Cache

- L3 Cache

- Memory

- Conventional
- Storage
- Hierarchy

- Proc

- Cache

- L2 Cache

- L3 Cache

- Memory

- Proc

- Cache

- L2 Cache

- L3 Cache

- Memory

- potential
- interconnects

- CS267 Lecure 2

## Load Imbalance

- Load imbalance is the time that some processors in the system are idle due to
- insufficient parallelism (during that phase).
- unequal size tasks.
- Examples of the latter
- adapting to “interesting parts of a domain”.
- tree-structured computations.
- fundamentally unstructured problems.
- Algorithm needs to balance load
- but techniques the balance load often reduce locality

- CS267 Lecure 2

## Parallel Programming for Performance is Challenging

-  Speedup(P) = Time(1) / Time(P)
- Applications have “learning curves”

- Amber (chemical modeling)

- CS267 Lecure 2

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

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

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

## Outline

- Principles of Parallel Computing
- Parallelism in Modern Processors
- Memory Hierarchies
- Matrix Multiply Cache Optimizations
- Bag of Tricks

- CS267 Lecure 2

## Idealized Uniprocessor Model

- Processor names bytes, words, etc. in its address space
- These represent integers, floats, pointers, arrays, etc.
- Exist in the program stack, static region, or heap
- Operations include
- Read and write (given an address/pointer)
- Arithmetic and other logical operations
- Order specified by program
- Read returns the most recently written data
- Compiler and architecture translate high level expressions into “obvious” lower level instructions
- Hardware executes instructions in order specified by compiler
- Cost
- Each operations has roughly the same cost
- 	(read, write, add, multiply, etc.)

- CS267 Lecure 2

## Uniprocessors in the Real World

- Real processors have
- registers and caches
- small amounts of fast memory
- store values of recently used or nearby data
- different memory ops can have very different costs
- parallelism
- multiple “functional units” that can run in parallel
- different orders, instruction mixes have different costs
- pipelining
- a form of parallelism, like an assembly line in a factory
- Why is this your problem?
- In theory, compilers understand all of this and can optimize your program; in practice they don’t.

- CS267 Lecure 2

## What is Pipelining? 

- <footer>

- 08/29/2002

**What is Pipelining? **

- In this example:
- Sequential execution takes    4 * 90min = 6 hours
- Pipelined execution takes 30+4*40+20 = 3.3 hours
- Pipelining helps throughput, but not latency
- Pipeline rate limited by slowest pipeline stage
- Potential speedup = Number pipe stages
- Time to “fill” pipeline and time to “drain” it reduces speedup

**6 PM**

**7**

**8**

**9**

*T*
*a*
*s*
*k*
*O*
*r*
*d*
*e*
*r*

*Time*

- Dave Patterson’s Laundry example: 4 people doing laundry
- 	wash (30 min) + dry (40 min) + fold (20 min)

## Example: 5 Steps of MIPS DatapathFigure 3.4, Page 134 , CA:AQA 2e by Patterson and Hennessy

**Memory**
**Access**

**Write**
**Back**

**Instruction**
**Fetch**

**Instr. Decode**
**Reg. Fetch**

**Execute**
**Addr. Calc**

- Memory

- Reg File

- MUX

- MUX

- Data
- Memory

- MUX

**Sign**
**Extend**

- Zero?

- Next SEQ PC

- Next SEQ PC

- RD

- RD

- RD

- WB Data

**  ****Pipelining is also used within arithmetic units**
** ****a fp multiply may have latency 10 cycles, but throughput of 1/cycle**

- Next PC

- RS1

- RS2

- Imm

- MUX

- CS267 Lecure 2

## Limits to Instruction Level Parallelism (ILP)

- <footer>

- 08/29/2002

**Limits to Instruction Level Parallelism (ILP)**

- Limits to pipelining: Hazards prevent next instruction from executing during its designated clock cycle
- _Structural hazards_: HW cannot support this combination of instructions (single person to fold and put clothes away)
- _Data hazards_: Instruction depends on result of prior instruction still in the pipeline (missing sock)
- _Control hazards_: Caused by delay between the fetching of instructions and decisions about changes in control flow (branches and jumps).
- The hardware and compiler will try to reduce these:
- Reordering instructions, multiple issue, dynamic branch prediction, speculative execution...
- You can also enable parallelism by careful coding

## Dependences (Data Hazards) Limit Parallelism

- A dependence or data hazard is one of the following:
- true of flow dependence:
- a writes a location that b later reads
- (read-after write or RAW hazard)
- anti-dependence
- a reads a location that b later writes
- (write-after-read or WAR hazard)
- output dependence
- a writes a location that b later writes
- (write-after-write or WAW hazard)

| true | anti | output |
| --- | --- | --- |
| a = |    = a | a = 
a =  |
|    = a | a =  |  |

- CS267 Lecure 2

## Outline

- Parallelism in Modern Processors
- Memory Hierarchies
- Matrix Multiply Cache Optimizations
- Bag of Tricks

- CS267 Lecure 2

## Memory Hierarchy

- Most programs have a high degree of locality in their accesses
- spatial locality: accessing things nearby previous accesses
- temporal locality: reusing an item that was previously accessed
- Memory hierarchy tries to exploit locality

- on-chip cache

- registers

- datapath

- control

- processor

- Second level cache (SRAM)

- Main memory
- (DRAM)

- Secondary storage (Disk)

- Tertiary storage
- (Disk/Tape)

- Speed (ns):    1               10                 100           10 ms              10 sec
- Size (bytes): 100s           KB                 MB              GB                   TB

- CS267 Lecure 2

## Processor-DRAM Gap (latency)

- μProc
- 60%/yr.

- DRAM
- 7%/yr.

**1**

**10**

**100**

**1000**

**1980**

**1981**

**1983**

**1984**

**1985**

**1986**

**1987**

**1988**

**1989**

**1990**

**1991**

**1992**

**1993**

**1994**

**1995**

**1996**

**1997**

**1998**

**1999**

**2000**

- DRAM

- CPU

**1982**

**Processor-Memory**
**Performance Gap:****(grows 50% / year)**

**Performance**

**Time**

- “Moore’s Law”

- Memory hierarchies are getting deeper
- Processors get faster more quickly than memory

- CS267 Lecure 2

**Notes:**

Y-axis is performance
X-axis is time
Latency
Cliché: 
Not e that x86 didn’t have cache on chip until 1989

## Cache Basics

- X000       X001
- X010       X011
- X100       X101
- X110       X111

- Cache hit: in-cache memory access—cheap
- Cache miss: non-cached memory access—expensive
- Consider a tiny cache (for illustration only)

- Cache line length: # of bytes loaded together in one entry
- Associativity
- direct-mapped: only one address (line) in a given range in cache
*n*-way: 2 or more lines with different addresses exist

- CS267 Lecure 2

## Experimental Study of Memory

- Microbenchmark for memory system performance

-  time the following program for each size(A) and stride s
-   (repeat to obtain confidence and mitigate timer resolution)
-           for array A of size from 4KB to 8MB by 2x
-              for stride s from 8 Bytes (1 word) to size(A)/2 by 2x
- 	          for i from 0 to size by s
-                            load A[i] from memory (8 Bytes)

- CS267 Lecure 2

## Memory Hierarchy on a Sun Ultra-IIi

**Memory Hierarchy on a Sun Ultra-IIi**

- L2: 2 MB, 36 ns
- (12 cycles)

- L1: 16K, 6 ns
- (2 cycle)

- Mem: 396 ns
- (132 cycles)

- Sun Ultra-IIi, 333 MHz

- L2: 64 byte line

- 8 K pages

- See www.cs.berkeley.edu/~yelick/arvindk/t3d-isca95.ps for details

- L1: 16 byte line

**Array size**

- CS267 Lecure 2

## Memory Hierarchy on a Pentium III

- L1: 32 byte line ?

- L2: 512 KB
- 60 ns

- L1: 64K
- 5 ns, 4-way?

- Katmai processor on Millennium, 550 MHz

**Array size**

- CS267 Lecure 2

## Lessons

- Actual performance of a simple program can be a complicated function of the architecture
- Slight changes in the architecture or program change the performance significantly
- To write fast programs, need to consider architecture
- We would like simple models to help us design efficient algorithms
- Is this possible?
- We will illustrate with a common technique for improving cache performance, called blocking or tiling
- Idea: used divide-and-conquer to define a problem that fits in register/L1-cache/L2-cache

- CS267 Lecure 2