# Presentation: 739017

## The Next Revolution in Programming: multi-core and petascale

**The Next Revolution in Programming: multi-core and petascale**

**Presented to ASC 2007 PI Meeting**
**Los Vegas, NV – February 21, 2007**
**Dr. Mark K. Seager**
**Lawrence Livermore National Laboratory**

- UCRL-PRES-228298
- This work was performed under the auspices of the U.S. Department of Energy by the University of California, Lawrence Livermore National Laboratory under Contract No. W-7405-Eng-48.

## Legal Disclaimer

- This work was performed under the auspices of the U.S. Department of Energy by University of California Lawrence Livermore National Laboratory under contract No. W-7405-Eng-48.

- DISCLAIMER
- This document was prepared as an account of work sponsored by an agency of the United States Government.  Neither the United States Government nor the University of California nor any of their employees, makes any warranty, express or implied, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness of any information, apparatus, product, or process disclosed, or represents that its use would not infringe privately owned rights.  Reference herein to any specific commercial products, process, or service by trade name, trademark, manufacturer, or otherwise, does not necessarily constitute or imply its endorsement, recommendation, or favoring by the United States Government or the University of California.  The views and opinions of authors expressed herein do not necessarily state or reflect those of the United States Government or the University of California, and shall not be used for advertising or product endorsement purposes.

- ASC 2007 PI Meeting

- Feb 21, 2007

## Outline

- The Problem
- Extreme scalability required for delivered petaFLOP/s in 2011
- Multi-physics codes have multiple distinctly different algorithms requiring flexible scaling approach
- The Solution
- Divide and conquer
- MPI at the highest level
- Highly flexible SMP programming model underneath
- Close collaboration between ASC applications developer and IBM compiler research and development

- ASC 2007 PI Meeting

- Feb 21, 2007

## A: The world’s fastest supercomputer, with up to8 processors, 512MB RAM, 2.3 GFLOPS (peak).

**A:**** The world’s fastest supercomputer, with up to****8 processors, 512MB RAM, 2.3 GFLOPS (peak).**

**Q:**** What is a 1989 Cray Y-MP? (Or half my laptop...)**

**From Herb Sutter <hsutter@microsoft.com>**

- ASC 2007 PI Meeting

- Feb 21, 2007

## The Problem

- Moore’s law is holding, but ramifications are changing
- Transistors on an ASIC still doubling every 18 months at constant cost
- Parasitic power now dominating over active power.  Both increase as frequency2  frequency slowly increasing with each generation
- Performance improvements are now coming from exponential increase in the number of cores on a processor (ASIC).
- This is an industry trend
- Huge investment at Intel, Micro$oft and IBM to figuring out how to make SMP style programming accessible to the mass market

- ASC 2007 PI Meeting

- Feb 21, 2007

## Historically: Boost single-stream performance via more complex chips, first via one big feature, then via lots of smaller features.
Now: Deliver more cores per chip.
The free lunch is over for today’s sequential apps and many concurrent apps (expect some regressions). We need killer apps with lots of latent parallelism.
A generational advance >OO is necessary to get above the “threads+locks” programming model.

- Historically: Boost single-stream performance via more complex chips, first via one big feature, then via lots of smaller features.
- Now: Deliver more cores per chip.
- The free lunch is over for today’s sequential apps _and_ many concurrent apps (expect some regressions). We need killer apps with lots of latent parallelism.
- A generational advance >OO is necessary to get above the “threads+locks” programming model.

- Each year we get faster more processors

**Montecito**

**Intel CPU Trends** (sources: Intel, Wikipedia, K. Olukotun)

**Pentium**

**386**

**Moore’s****Law**

**From Herb Sutter <hsutter@microsoft.com>**

- ASC 2007 PI Meeting

- Feb 21, 2007

**Notes:**
(Montecito 1.7Bt ÷ P55C 4.5Mt = ~100 x86s + 16 MB L3$)

## Recent announcements on mainstream multi-core architectures indicate high levels of processor parallelism

**Sun CoolThreadsTM Processor has 8 cores * 4 threads = 32 way parallelism and is now shipping**

**Four threads with round robin scheduling to hide memory latency sounds like Cray MTA**

**Intel’s recent announcement at IDF of 80 core processor took everyone by surprise!**

- ASC 2007 PI Meeting

- Feb 21, 2007

## How many cores are you coding for?

**From Herb Sutter <hsutter@microsoft.com>**

**Microprocessor parallelism will increase ****exponentially**** in the next decade**

**You**
**Are**
**Here!**

**How**
**Do We**
**Get to**
**Here?**

- ASC 2007 PI Meeting

- Feb 21, 2007

## Computing Revolutions Over Time

|  | Intro | Adopted in Mainstream |
| --- | --- | --- |
| Timesharing | 1961 (CTSS) | 1978 (BSD Unix) |
| GUIs | 1973 (Xerox Alto) | ~1984-1989 (Mac)
~1990-1995 (Win 3.x) |
| Objects | 1967 (Simula) | ~1993-98 (C++, Java) |
| Garbage Collection | 1958 (Lisp) | ~1995-2000 (Java) |
| Generic Types | 1967 (Strachey) | ~198x (USDOD, Ada)
~1995-2000 (C++) |
| Internet | 1967+ (ARPAnet) | ~1995-2000 |
| Distributed Memory | 1990 | TBD |
| Concurrency | 1964 (CDC 6600) | 2007-12 (est) |

**After  Herb Sutter <hsutter@microsoft.com>**

- ASC 2007 PI Meeting

- Feb 21, 2007

## What will the concurrency revolution look like?

**From Herb Sutter <hsutter@microsoft.com>**

- ASC 2007 PI Meeting

- Feb 21, 2007

## How much parallelism will be required to sustain petaFLOP/s in 2011?

- Hypothetical low power machines will feature 1.6M to 6.6M way parallelism
- 32-64 cores per processor and up to 2-4 threads per core
- Assume 1 socket nodes and 25.6K nodes
- Hypothetical Intel terascale chip petascale system yields 1.5M way parallelism
- 80 cores per processor
- Assume 4 socket nodes and 4,608 nodes (32 SU of 144 nodes with IBA)
- Holey cow, this is about 12-48x BlueGene/L!

- ASC 2007 PI Meeting

- Feb 21, 2007

## Multicore processors have non-intuitive impact on other machine characteristics

- Memory is the most critical machine characteristic
- ASC applications require >1GiB/MPI task
- If we map MPI tasks directly to cores
- 64GiB/node on Low Power  1.6PiB of memory and that is 4x too expensive, if we could build and power it
- This drives us to think in terms of fewer MPI tasks/node
- 320GiB/node on Intel  1.5PiB of memory is also a problem

- †From Seager Dec 1997 platforms talk

- ASC 2007 PI Meeting

- Feb 21, 2007

## Multicore processors drive huge network requirements

- With multiple MPI tasks/node, short message messaging rate becomes as important as bandwidth and latency
- ASC applications require >2 mMsgs/s/MPI task
- If we map MPI tasks directly to cores, then we require
- Low power system requires 64 MPI tasks/node  128 mM/s.
- 12.5 clocks/message
- This may be achievable, but is very high risk.
- Intel requires 80 MPI tasks/socket and 4 socket nodes  >640 mM/s
- 5 clocks/message
- This is not achievable
- This drives us to think in terms of fewer MPI tasks/node

- ASC 2007 PI Meeting

- Feb 21, 2007

## Divide and conquer also drives one to consider SMP parallelism within MPI tasks

- Divide and conquer technique was hugely successful on solving both HW+SW problems on BG/L
- CN:ION ratio of 64:1 solved OS and file systems problem
- RAS system built up from fan-in network

| System | Cores | Nodes | MPI/node | SMP/MPI | Total MPI | Ratio:BGL |
| --- | --- | --- | --- | --- | --- | --- |
| BGL | 2 | 65,536 | 2 | 1 | 131,072 | 1.000 |
| BGL | 2 | 65,536 | 1 | 1-2 | 65,536 | 0.500 |
| BGP(1⁄2) | 4 | 36,864 | 4 | 1 | 147,456 | 1.125 |
| LowPower | 64 | 25,600 | 64 | 1 | 1,638,400 | 12.500 |
| LowPower | 64 | 25,600 | 4 | 16 | 102,400 | 0.781 |
| LowPower | 64 | 25,600 | 1 | 64 | 25,600 | 0.195 |
| IntelTS | 80 | 4,608 | 320 | 1 | 1,474,560 | 11.250 |
| IntelTS | 80 | 4,608 | 40 | 8 | 184,320 | 1.406 |
| IntelTS | 80 | 4,608 | 4 | 80 | 18,432 | 0.078 |

- ASC 2007 PI Meeting

- Feb 21, 2007

## The “Livermore Model” developed in 1990 made sense of the “killer-micro” revolution

- Livermore Model system perspective for distributed memory machines
- Interactive and batch usage
- Debugging and visualization
- Mix of job sizes
- Capability runs at a significant portion of platform
- Capacity runs at a small fraction of platform
- Mix of runtimes
- Short run-time for setup
- Many months of science run
- Many users
- Require progress on jobs
- Hard allocations for user groups

- ASC 2007 PI Meeting

- Feb 21, 2007

## The Livermore Model also leveraged desktop to teraFLOP/s development by providing identical programming model across platforms

- Local

- Local

- MPI Comms

**OpenMP**

**OpenMP**

**OpenMP**

**Idea**: Provide a consistent programming model for multiple platform generations and across multiple vendors!
**Idea**: Incrementally increase functionality over time!

- Local

- ASC 2007 PI Meeting

- Feb 21, 2007

## By capturing the essence of the killer-micro revolution we have created a new era of programming model stability

**White**

**Blue**

**IBM ID**

**Meiko**
** ****CS-2**

**Big Crays**

**CDC 7600**

- By the end of Purple in 2009, the Livermore model (clustered SMPs with incrementally improving functionality) will provide more than three-quarters the programming model longevity of Vector era.

- 20 year vector era

- 15 year cluster era

- ASC 2007 PI Meeting

- Feb 21, 2007

**Notes:**
Strategy started with the Meiko after learning that SMP would not scale to teraFLOP/s without the use of MPI in applications.
Pushed single SMP to 128 CPU with BBN TC2000 Butterfly in MPCI project lead by Eugene Brooks.

## What SMP style parallelism has been tried in the past?

- OpenMP describes fork/join loop level parallelism
- Overheads of all implementations are large
- Serial regions limit effectiveness due to Amdahl’s law, even at small scale
- Work between loops is serial and sometimes non-trivial
- Critical sections within loops for updating global variables
- Works well on some packages, but not all packages are amenable to this style of parallelism
- GAS models (UPC, Global Arrays, HPF) not applicable because they assume top level parallelism
- Compiler generated automagic parallelism has not been successful
- Largely due to very conservative assumptions to assure program correctness
- HPF adapted for regular datasets (uniform grids) and large overheads lead to its demise

- ASC 2007 PI Meeting

- Feb 21, 2007

## New approach to multi-core parallelism

- Industry looking seriously at several novel techniques
- Transactional Memory for atomic updates
- Speculative execution and scout threads for prefetching
- Some hardware cores will have support for transactional memory and speculative execution
- TM allows eliminates many sever problems with locks
- Allows compilers to aggressively pursue speculation with hardware catching dependencies and discarding speculation work as needed for correct program execution
- SE is dynamic and adaptive
- Two SE research tools were able to find more than 32 way parallelism with 92% efficiency (ignoring overheads) in UMT2000
- This analysis was on the worst case: Angles=1 (no OpenMP loop) and Energy Groups = 1 (minimum work)

- ASC 2007 PI Meeting

- Feb 21, 2007

## We should leverage the huge investment in concurrency being made by Micro$oft/Linux/Intel ecosystem

**From Herb Sutter <hsutter@microsoft.com>**

- ASC 2007 PI Meeting

- Feb 21, 2007

## Summary

- We have described a new approach to the frightening challenge of petascale applications scaling
- Driven by exponential increase in cores/processor
- Driven on some platforms by practical memory limits
- Driven on some platforms by practical interconnect limits
- Key strategy elements
- Divide and conquer trades the number of MPI tasks and the SMP parallelism/MPI task required with multiplicative effect
- Use research contract to focus partnership on research and development for ASC applications driven TM/SE technology insertion
- The right answer is always the obvious one, after you find it!

- ASC 2007 PI Meeting

- Feb 21, 2007