# Presentation: 517675

## Slide 1

## What is Wrong with MPI for PetaFlops Computing?

**Kathy Yelick**
- _[http://www.](http://www.cs.berkeley.edu/~yelick)__[cs](http://www.cs.berkeley.edu/~yelick)__[.](http://www.cs.berkeley.edu/~yelick)__[berkeley](http://www.cs.berkeley.edu/~yelick)__[.](http://www.cs.berkeley.edu/~yelick)__[edu](http://www.cs.berkeley.edu/~yelick)__[/~](http://www.cs.berkeley.edu/~yelick)__[yelick](http://www.cs.berkeley.edu/~yelick)_
**U.C. Berkeley and LBNL**

## Will MPI predominance persist?

**Why has MPI been the dominant model?**
- Ubiquity/portability of code
- Control over performance
- There was a community of MP programmers before MPI
- Designed to support higher level libraries
**Even if the research community develops great ideas, do users ever change?**
- Added expressive power (F/C  C++)
- Significant performance advantage (vector+threads  MPI)
- “Managers” force change due to productivity advantage
- Infusion of “new” programmers with different training

## Are Alternatives Probable?

**Global Address Space Languages Offer an alternative: UPC, CAF, Titanium**
**Key ideas:**
- Affinity between data and thread/process
- Separate implementation issues (shared/distributed memory) from programming model
- On any machine, locality is useful
- Remote data structures can be read/written directly
- Your distributed tree/graph/hashtable/array are not just a figment of the programmers imaginations

## Global Address Space Languages

**Static parallelism (like MPI) in all 3 languages**

- Object heaps
- are shared

**Global address space**

**x: 1**
**y: 2**

- Program stacks
- are private

**l: **

**l: **

**l: **

**g: **

**g: **

**g: **

**x: 5**
**y: 6**

**x: 7**
**y: 8**

- p0

- p1

- pn

**Globally shared address space is partitioned **
**References (pointers) are either local or global (meaning possibly remote)**
**Distributed arrays and pointer-based structures**

## What’s Wrong with MPI?

**Not bad for regular applications**
- Bulk-synchronous code with balanced load
**What about fine-grained programs?**
- Pack/unpack
**What about fine-grained asynchronous programs?**
- Pack/unpack, prepost, check-for-done

## Bulk-synchronous MG on Quadrics AlphaServer

***Bulk-synchronous MG on Quadrics AlphaServer***

- Elan-based layer soundly beat apps on MPI-based layer - better performance, better scaling
- GM layer also beat MPI
- The only difference in the Berkeley lines is the network API!
- Source: Bonachea and Duell

**Notes:**
Two bulk-synchronous apps - CG dominated by bulk (56K) puts, MG by bulk (100KB) gets and some small (8b) puts
Difference is mostly due to the cost of providing the one-sided illusion on MPI 1.1 - two copy messaging
Native layer can use zero-copy RDMA w/ no rendezvous

## MPI One-Sided

**Remote Memory Access (RMA) added in MPI 2.0**
- Provides a one-sided communications interface
- MPI_Put, MPI_Get, MPI_Accumulate
- All RMA takes place on an abstract window
- Passive target is truly one-sided: no target cooperation
**Window creation is a collective operation**
**Concurrency limits on accessing windows**
- Window may not be concurrently accessed by
- Remote RMA and local load/stores
- Even for non-overlapping regions
**The bulk-synchronous (compute/communicate) model is still imposed**

**Notes:**
Provide only a brief overview
Seems like a natural fit for GAS languages - not so

## Can Architectures Help Programming Pain?

**The vicious cycle:**

- All high end programs
-  written in MPI

- All machine support
- only MPI well

**The losers:**** **
**the scientists who are not paid enough to program in MPI**

**the customers who bought hardware and threw away the performance**

## 8-byte ‘put’ Latencies with Software Overheads

**Notes:**
Zero receive overhead for some: significant if 2-way communication
MPI cost: not just higher latency, but also less potential for hiding latency

## The Vicious Cycle Plays Out

- Software put overhead for 8-byte messages over time.
- Not improving much over time (even in absolute terms)

## How Large Should Messages Be?

- No free lunch: Large messages on irregular problems leads to memory copies

## How Should Compilers Promote Petaflops Programming?

**Virtualize the memory system**
- Global address space languages do this
**Virtualize the processor space**
- Some object-oriented parallel languages do this
- Data parallel languages do this
- Challenges:
- Don’t want to lose programmers’ locality
- Mapping N things to P processor for N >> P can be hard
**Caveat:**
- Don’t take giant steps
- Learned from Prolog/HPF/Sisal

## How Should Compilers Promote Petaflops Programming?

**Plenty of parallelism for pesky pervasive  processors: let the programmer express it**
- Global address space languages of today are not enough
- Want to expose all the parallelism
- Not just loop/shared-memory/threads
- May need levels of affinity?
**Look for lots of locality for latency-laden world**
- Hierarchical models of locality
- Need not be a rigid association that far away is inaccessible
**Get out of the way:**
- Don’t throw away the architecture’s performance!

## End of Slides

## S2S for Novel Architectures

**Very preliminary (1 week of work), most have = perf**
**Problems are due to multidimensional arrays (Matmul); can be improved**

**49x**

## Serial Performance (Pure Java)

- Note the Ti/Java numbers use Java arrays, not Titanium arrays
- Ti -nobc is with bounds-checking disabled

## Parallel Performance and Scalability

**Poisson solver using “Method of Local Corrections”**
**Communication < 5%; Scaled speedup nearly ideal (flat)**
**               **IBM SP at SDSC                            Cray T3E at NERSC

**Notes:**
Explain scaled speedup – scale problem size with num procs
Problem (work) itself doesn't always scale exactly linearly

## Performance Tuning by Compiler

- Advantage of compiled languages (Berkeley UPC compiler)

- Scaled version of GUPS

## Programmability

**Heart simulation developed in ~1 year**
- Extended to support 2D structures for Cochlea model in ~1 month
**Preliminary code length measures**
- Simple torus model
- Serial torus code is 17045 lines long (2/3 comments)
- Parallel Titanium torus version is 3057 lines long.
- Full heart model
- Shared memory Fortran heart code is 8187 lines long
- Parallel Titanium version is 4249 lines long.
- Need to be analyzed more carefully, but not a significant overhead for distributed memory parallelism

## Robustness

**Robustness is the primary motivation for language “safety” in Java**
- Type-safe, array bounds checked, auto memory management
- Study on C++ vs. Java from Phipps at Spirus:
- C++ has 2-3x more bugs per line than Java
- Java had 30-200% more lines of code per minute
**Extended in Titanium**
- Checked synchronization avoids barrier deadlocks
- More abstract array indexing, retains bounds checking
**No attempt at quantify for Titanium yet**
- Would like to measure speed of error detection (compile time, runtime exceptions, etc.)

## Portability

**Heart code and other applications run anywhere Titanium runs**
- Runs on serial or shared memory machines with native C compiler
- Including my laptop!
- Very important for programmer productivity
- For distributed memory, requires communication layer
- Alpha/Quadrics, IBM SP, Cray T3E, PC/Myrinet, anything with MPI
- Global Address Space Networking layer (GASNet)
- With C compiler, get Titanium and LBNL/UPC compilers
**FFTW used in heart code: strategy for performance and portability**

## Performance and Portability Approach

**Use machines, not humans for architecture-specific tuning**
- Code generation + search-based selection
- Can adapt to cache size, # registers, network buffering
- Used in
- Signal processing: FFTW, SPIRAL, UHFFT
- Dense linear algebra: Atlas, PHiPAC
- Sparse linear algebra: Sparsity
- Rectangular grid-based computations: Titanium compiler
- Global communication: Atlas-derivative

## Summary

**Titanium designed for performance and programmability**
- Some compromises (regions, local/global refs)
**Retains robustness (safety) of Java**
- Also a big help in learning, avoiding certain kinds of bugs
**Tunability and performance transparency**
- Aggressive automatic optimizations can make this worse
**Advertising (all open source):**
- Titanium compiler: _[http://titanium.](http://titanium.cs.berkeley.edu/)__[cs](http://titanium.cs.berkeley.edu/)__[.](http://titanium.cs.berkeley.edu/)__[berkeley](http://titanium.cs.berkeley.edu/)__[.](http://titanium.cs.berkeley.edu/)__[edu](http://titanium.cs.berkeley.edu/)_
- Berkeley UPC compiler: _[http://](http://upc.nersc.gov/)__[upc](http://upc.nersc.gov/)__[.](http://upc.nersc.gov/)__[nersc](http://upc.nersc.gov/)__[.](http://upc.nersc.gov/)__[gov](http://upc.nersc.gov/)_
- Automatic tuning: _[http://www.](http://www.cs.berkeley.edu/~richie/bebop)__[cs](http://www.cs.berkeley.edu/~richie/bebop)__[.](http://www.cs.berkeley.edu/~richie/bebop)__[berkeley](http://www.cs.berkeley.edu/~richie/bebop)__[.](http://www.cs.berkeley.edu/~richie/bebop)__[edu](http://www.cs.berkeley.edu/~richie/bebop)__[/~](http://www.cs.berkeley.edu/~richie/bebop)__[richie](http://www.cs.berkeley.edu/~richie/bebop)__[/bebop](http://www.cs.berkeley.edu/~richie/bebop)_