# Presentation: 688255

## Scalable Algorithms for 1M Cores: What Might and Might Not Work, And WhyMichael A. HerouxSandia National Laboratories

- Sandia is a multiprogram laboratory operated by Sandia Corporation, a Lockheed Martin Company,for the United States Department of Energy under contract DE-AC04-94AL85000.

## Advanced Modeling and Simulation Capabilities:Stability, Uncertainty and Optimization

- Promise: 10-1000 times increase in parallelism (or more).
- Pre-requisite: High-fidelity “forward” solve:
- Computing families of solutions to similar problems.
- Differences in results must be meaningful.

- SPDEs:

- Transient
- Optimization:

-     - Size of a single forward problem

- Lower Block
- Bi-diagonal

- Block
- Tri-diagonal

*t**0*

*t**0*

*t**n*

*t**n*

## Advanced Capabilities: Readiness and Importance

| Modeling Area | Sufficient Fidelity? | Other concerns | Advanced capabilities priority |
| --- | --- | --- | --- |
| Seismic
S. Collis, C. Ober | Yes. | None as big. | Top. |
| Shock & Multiphysics
(Alegra)
A. Robinson, C. Ober | Yes, but some concerns. | Constitutive models, material responses maturity. | Secondary now.  Non-intrusive most attractive. |
| Multiphysics
(Charon)

J. Shadid | Reacting flow w/ simple transport, device w/ drift diffusion, ... | Higher fidelity, more accurate multiphysics. | Emerging, not top. |
| Solid mechanics

K. Pierson | Yes, but... | Better contact. Better timestepping.  Failure modeling. | Not high for now. |

## Advanced Capabilities:Other issues

- Non-intrusive algorithms (e.g., Dakota):
- Task level parallel:
- A true peta/exa scale problem?
- Needs a cluster of 1000 tera/peta scale nodes.
- Embedded/intrusive algorithms (e.g., Trilinos):
- Cost of code refactoring:
- Non-linear application becomes “subroutine”.
- Disruptive, pervasive design changes.
- Forward problem fidelity:
- Not uniformly available.
- Smoothness issues.
- Material responses.

## Advanced Capabilities:Derived Requirements

- Large-scale problem presents collections of related subproblems with forward problem sizes.
- Linear Solvers:
- Krylov methods for multiple RHS, related systems.
- Preconditioners:
- Preconditioners for related systems.
- Data structures/communication:
- Substantial graph data reuse.

## Programming Model Issues for Algorithms on Scalable Multicore Systems

## Core Configurations: Factoring 1M Cores

- Traditional MPI-only+traditional threading

- MPI+light-weight threads

- MPI+?? (vectorization/streaming?)

## Node Classification

- Homogeneous multicore:
- SMP on a chip.
- NUMA nodes.
- Varying memory architectures.
- Heterogeneous multicore:
- Serial/Controller processor(s).
- Team of identical, simpler compute processors.
- Varying memory architectures.

## Why Homogeneous vs. Heterogeneous?

- Homogeneous:
- Out-of-the-box: Can attempt single-level MPI-only.
- m nodes, n cores per node: p = m*n
- mpirun -np p ...
- Heterogeneous:
- Must think of compute cores as “co-processors”.
- mpirun -np m ...
- Something else on the node.
- Future:
- Boundary may get fuzzy.
- Heterogenous techniques can work well on homogeneous nodes.

## About MPI

- MPI will be the primary inter-node programming model.
- Very few people program in MPI: Abstractions.
- Right ingredients:
- Portable, ubiquitous.
- Forced alignment of work/data ownership and transfer.
- Matches architectures:
- Interconnects of best commercial node parts.
- New languages:
- Big fan of Co-Array Fortran (Have been for 15 years: F--).
- Chapel looks good.
- But tough uphill climb.
- Real question: How do we program the node?

## Programming Models for Scalable Homogeneous Multicore(beyond single-level MPI-only)

## Threading under MPI

- Default approach: Successful in many applications.
- Concerns:
- Opaqueness of work/data pair assignment.
- Lack of granularity control.
- Collisions: Multiple thread models.
- Performance issue, not correctness.
- Bright spot: Intel Thread Building Blocks (TBB).
- Iterator (C++ language feature) model.
- Opaque or transparent: User choice.

## MPI Under MPI

- Scalable multicores:
- Two different MPI architectures.
- Machines within a machine.
- Exploited in single-level MPI:
- Short-circuited messages.
- Reduce network B/W.
- Missing some potential.
- Nested algorithms.
- Already possible.
- Real attraction: No new node programming model.
- Can even implement shared memory algorithms (with some enhancements to MPI).

| “Ping-pong” test | Latency
(microsec) | Bandwidth
(MB/sec) |
| --- | --- | --- |
| Intra-node machine | 0.71 | 1082 |
| Inter-node machine | 47.5 | 114 |

## MPI-Only + MPI/Threading: Ax=b

- App
- Rank 0

- App
- Rank 1

- App
- Rank 2

- App
- Rank 3

- Lib
- Rank 0

- Lib
- Rank 1

- Lib
- Rank 2

- Lib
- Rank 3

- Mem
- Rank 0

- Mem
- Rank 1

- Mem
- Rank 2

- Mem
- Rank 3

- Multicore: “PNAS” Layout

- Lib
- Rank 0
- Thread 0   Thread 1   Thread 2  Thread 3

- App passes matrix and vector values to library data
- classes

- All ranks store *A, x, b* data in memory visible to rank 0

- Library solves *Ax=b* using shared memory algorithms
- on the node.

## Heterogeneous Multicore Issues

## Excited about multimedia processors

- Inclusion of native double precision.
- Large consumer market.
- Qualitative performance improvement over standard microprocessors...
- If your computation matches the architecture.
- Many of our computations do match well.
- But a long road ahead...

## APIs for Heterogeneous Nodes(A Mess)

| Processor | API |
| --- | --- |
| NVIDIA | CUDA |
| AMD/ATI | Brook+ |
| STI Cell | ALF |
| Intel Larrabee | Ct |
| Most/All? | Sequoia |
| Most | RapidMind (Proprietary) |
| Apple/All | OpenCL |

- Commonality: Fine-grain functional programming.
- Our Response: A Library Node Abstraction Layer

## Epetra Communication Classes

- Epetra_Comm is a pure virtual class:
- Has no executable code: Interfaces only.
- Encapsulates behavior and attributes of the parallel machine.
- Defines interfaces for basic services such as:
- Collective communications.
- Gather/scatter capabilities.
- Allows multiple parallel machine implementations.
- Implementation details of parallel machine confined to Comm classes.
- In particular, rest of Epetra (and rest of Trilinos) has no dependence on any particular API, e.g. MPI.

## Comm Methods

- _[CreateDistributor](file://Heroux00/u0/mheroux/Trilinos/doc/epetra/html/class_Epetra_Comm.html#a16)_() const=0 [pure virtual]
- _[CreateDirectory](file://Heroux00/u0/mheroux/Trilinos/doc/epetra/html/class_Epetra_Comm.html#a16)_(const Epetra_BlockMap & map) const=0 [pure virtual]
- _[Barrier](file://Heroux00/u0/mheroux/Trilinos/doc/epetra/html/class_Epetra_Comm.html#a1)_() const=0 [pure virtual]
- _[Broadcast](file://Heroux00/u0/mheroux/Trilinos/doc/epetra/html/class_Epetra_Comm.html#a2)_(double *MyVals, int Count, int Root) const=0 [pure virtual]
- _[Broadcast](file://Heroux00/u0/mheroux/Trilinos/doc/epetra/html/class_Epetra_Comm.html#a3)_(int *MyVals, int Count, int Root) const=0 [pure virtual]
- _[GatherAll](file://Heroux00/u0/mheroux/Trilinos/doc/epetra/html/class_Epetra_Comm.html#a4)_(double *MyVals, double *AllVals, int Count) const=0 [pure virtual]
- _[GatherAll](file://Heroux00/u0/mheroux/Trilinos/doc/epetra/html/class_Epetra_Comm.html#a5)_(int *MyVals, int *AllVals, int Count) const=0 [pure virtual]
**MaxAll**(double *PartialMaxs, double *GlobalMaxs, int Count) const=0 [pure virtual]
**MaxAll**(int *PartialMaxs, int *GlobalMaxs, int Count) const=0 [pure virtual]
**MinAll**(double *PartialMins, double *GlobalMins, int Count) const=0 [pure virtual]
**MinAll**(int *PartialMins, int *GlobalMins, int Count) const=0 [pure virtual]
**MyPID**() const=0 [pure virtual]
**NumProc**() const=0 [pure virtual]
**Print**(ostream &os) const=0 [pure virtual]
**ScanSum**(double *MyVals, double *ScanSums, int Count) const=0 [pure virtual]
**ScanSum**(int *MyVals, int *ScanSums, int Count) const=0 [pure virtual]
**SumAll**(double *PartialSums, double *GlobalSums, int Count) const=0 [pure virtual]
**SumAll**(int *PartialSums, int *GlobalSums, int Count) const=0 [pure virtual]
**~Epetra_Comm**() [inline, virtual]

## Comm Implementations

- Three implementations of Epetra_Comm:
- Epetra_SerialComm:
- Allows easy simultaneous support of serial and parallel version of user code.
- Epetra_MpiComm:
- OO wrapping of C MPI interface.
- Epetra_MpiSmpComm:
- Allows definition/use of shared memory multiprocessor nodes.

## Abstract Node Class

- Trilinos/Kokkos: Trilinos compute node package.
- Abstraction definition in progress: Will look a lot like TBB.
- Composition needed:
- Node with quadcore and GPU.
- Kokkos::TbbNode uses Kokkos::SerialNode.
- Trilinos/Tpetra:
- Tpetra::Comm constructor takes Kokkos::Node object.

- Kokkos::Node

- Kokkos::SerialNode

- Kokkos::CudaNode

- Kokkos::TbbNode

- ...

## Going Forward: Changing the Atomic Unit

- Now: 	Single-level MPI-only OK for many apps.
- Future: 	Hiding network heterogeneity beneath single MPI level too hard.
- Philosophical approach: 	Node becomes the new atomic unit.
- Key Requirement: 	Portable standard node API.
- Hard work:	Changes are ubiquitous (unlike MPI).

## Library Efforts for Multicore

## A Few HPCCG Multicore Results

- Float useful:
**Mixed precision algorithms.**
- Memory system performance even more important:
**Saturation means loss of core use.**
- Memory placement a concern:
**Shared memory allows remote placement.**
- NiagaraT2 threads hide latency:
**Easiest node to program.**

**Notes:**
The dashed red line is the Barcelona performance for a large subdomain, prior to memory placement fix.  The problem was that memory for a core on socket 0 was placed on socket 1 because I/O buffers were  competing.  This is an example of the problems we have with current runtime environments.

- Niagara results show that simple oversubscribing of cores with multiple threads (there are 8 HW threads per core) can allow us to continue getting excellent speed ups.  This is a easy way to hide latency for unstructured computations.

## Library Preparations for New Node Architectures (Decision Made Years Ago)

- We knew node architectures would change...
- Abstract Parallel Machine Interface: Comm Class.
- Abstract Linear Algebra Objects:
- Operator  class: Action of operator only, no knowledge of how.
- RowMatrix class: Serve up a row of coefficients on demand.
- Pure abstract layer: No unnecessary constraints at all.
- Model Evaluator:
- Highly flexible API for linear/non-linear solver services.
- Templated scalar and integer types:
- Compile-time resolution float, double, quad,... int, long long,...
- Mixed precision algorithms.

## Library Effort in Response toNode Architecture Trends

- Block Krylov Methods (Belos & Anasazi):
- Natural for UQ, QMU, Sensitivity Analysis...
- Superior Node and Network complexity.
- Specialized sparse matrix data structures:
- Sparse diagonal, sparse-dense, composite, leverage OSKI.
- Templated Kernel Libraries (Tpetra & Tifpack):
- Choice of float vs double made when object created.
- High-performance multiprecision algorithms.
- Shared memory node-only algorithms:
- Triangular solves, multi-level preconditioner smoothers.
- Kokkos Node class
- Intel TBB support, compatible with OpenMP, Pthreads, ...
- Clients of Kokkos::TbbNode can access static, ready-to-work thread pool.
- Code above the basic kernel level is unaware of threads.
- MPI-only+MPI/PNAS
- Application runs MPI-only (8 flat MPI processes on dual quad-core)
- Solver runs:
- MPI-only when interfacing with app using partitioned nodal address space (PNAS).
- 2 MPI processes, 4 threads each when solving problem.

## C++ Templates

**Standard method prototype for apply matrix-vector multiply:**
- template<typename OT, typename ST>
- CisMatrix::apply(Vector<OT, ST> const& x, Vector<OT, ST>& y)

**Mixed precision method prototype (DP vectors, SP matrix):**
- template<typename OT, typename ST>
- CisMatrix::apply(Vector<OT, ScalarTraits<ST>::dp()>  const& x,
- 		Vector<OT, ScalarTraits<ST>::dp()> & y)

**Sample usage:**
- Tpetra::Vector<int, double> x, y;
- Tpetra::CisMatrix<int, float> A;
- A.apply(x, y);  // Single precision matrix applied to double precision vectors

## C++ Templates

- Compile time polymorphism.
- True generic programming.
- No runtime performance hit.
- Huge compile-time performance hit:
- But this is OK: Good use of multicore :)
- Can be reduced for common data types.
- Example was for float/double but works for:
- complex<float>/complex<double>.
- Arbitrary precision.

## Summary

**Advanced Capabilities: **
- Demand tremendous computing capabilities.
- Require continued advances in fidelity of forward solves.
- Place new requirements on lower level (e.g., linear solver) capabilities.
**Multimedia processors:**
- seem to have right mix for next qualitative performance improvement.
- Very difficult to program.
**Possible scenario for some apps/libs**:
- Heterogeneous API superior on homogeneous nodes.
- Go directly from single-level MPI-only to MPI+heterogenous node?
**A common, standard API for multicore:** Most critical need.
**Libraries:** Already on path to address many issues presented here.

## Extra Slides

## Homogeneous Multicore Issues

## Single Core Performance: Still improving for some codes

- HPCCG microapp.
- Clock speeds stable: ~ 2GHz.
- FP-friendly computations stalled.
- Memory-intensive computations still improving.

| Year | Processor | Clock (GHz) | Cores per socket | MFLOPS/sec |
| --- | --- | --- | --- | --- |
| 2003
 | AMD Athlon | 1.9 | 1 | 178 |
| 2004 | AMD Opteron | 1.6 | 1 | 282 |
| 2005 | Intel Pentium M | 2.1 | 1 | 310 |
| 2006 | AMD Opteron | 2.2 | 2 | 359 |
| 2007 | Intel Woodcrest | 1.9 | 4 | 401 |
| 2007 | AMD Opteron | 2.1 | 4 | 476 |
| 2007 | Intel Core Duo | 2.3 | 2 | 508 |

## MPI-Only(Intel Clovertown)

- The incumbent: Always present.
- Sometimes sufficient.

## Programming Model Translation(courtesy H.C. Edwards)

- Been here before:
- 12-15 years ago: SMP nodes.
- MPI vs. MPI/OpenMP/Pthreads.
- Lesson learned:
- Nothing magic about programming model.
- For SMP model to matter: *Algorithms must exploit shared memory.*

## Epetra Benchmark Tests

- Focused on core Epetra kernels:
- Sparse MV, MM.
- Dot products, norms, daxpy’s.
- spMM:
- Better performance.
- Better core utilization.

## Epetra Kernels on Niagara2

|  | Speedup 60 vs 1 |
| --- | --- |
| SpMV | 36.0 |
| SpMM2 | 31.0 |
| SpMM4 | 22.3 |
| Norm2 | 28.7 |
| Dot | 14.9 |
| Update | 26.1 |

## Tramonto Clovertown Results

**Tramonto Clovertown Results**

- Super-linear speedup
- (Setup phase)

- Sub-linear speedup
- (Solve phase)

- Setup (The application code itself): Excellent MPI-only.
- Solve (libraries): Much poorer. Inherent in algorithms.

## Tramonto Niagara2 Results

- Super-linear/linear speedup
- (Setup phase)

- Linear/sublinear speedup
- (Solve phase)

## Observations (So Far) for MPI Applications

- MPI-only is a legitimate approach and the default.
- Multicore will change how we program the node, eventually.
- Opinions on time frame vary greatly.
- Uncomfortable defending MPI but: Bold predictions of MPI-only demise so far have proved false.
- Simple programming model translation is ineffective.
- Runtime environment is fragile: process/memory placement.
- Memory-system-intensive code problematic: Ineffective core use.
- Multithreading helps us: performance and simpler code.
- Data placement: Huge performance impact, abstraction a challenge.

## Shared Memory Algorithms