# Presentation: 153125

## Scientific Libraries: MPI + Manycore issues and plans

- Greg Henry
- Intel® MKL Architect

## Agenda

- 1 Minute Tour of Intel Math Kernel Library (MKL)
- Threading and MPI Usage in MKL
- Some Examples

## Goals for Intel MKL

-  Performance
- Outstanding Performance on Intel processors
- Intel Core® 2, Pentium® 4, Xeon®, Intel Itanium® processors, ...
- [We] Do not add software without performance
- Parity with best software on Intel compatible architectures
-  Parallelism
- SIMD (Instruction level)
- Multi-core processors (Open MP)
- Distributed memory clusters (MPI)
- Add it everywhere it makes sense
-  Ease of use
- Compiler independence
- Intel, MSFT*, GCC*, PGI*
- F95 interfaces to BLAS, LAPACK
- CBLAS
- FFTW interface to Intel MKL FFTs

## Why is Intel MKL faster?

- Optimization done for maximum speed.
- Resource limited optimization – exhaust one or more resources of the full system features:
-  CPU:  Register use, FP units.
-  Cache: Keep data in cache as long as possible; deal with cache
-      interleaving.
-  TLBs: Maximally use data on each page.
-  Memory bandwidth: Minimally access memory.
-  Many-core: Use all the processor cores available using threading.
-  Cluster: Efficiently use all the nodes available.

**Notes:**
MKL Optimizations.

The basic concept here is that different routines stress different parts of the system. Vector operations place great demand on the memory system and, if the data are not in cache, the performance will be limited by the memory bandwidth. For this case, Intel MKL would try to achieve the same memory bandwidth for the vector function that is achieved on that processor on the STREAM benchmark. 

The major optimization techniques used throughout the library include:
• Loop unrolling to minimize loop management costs
• Blocking of data to improve data reuse opportunities
• Copying to reduce chances of data eviction from cache
• Data prefetching to help hide memory latency
• Multiple simultaneous operations (for example, dot products in dgemm) to eliminate stalls
due to arithmetic unit pipelines
• Use of hardware features such as the SIMD arithmetic units, where appropriate

## Intel® Math Kernel Library Contents

**BLAS and Sparse BLAS**
- Basic vector-vector/matrix-vector/matrix-matrix computation routines.
**LAPACK (Linear algebra package)**
- Solvers and eigensolvers. Many hundreds of routines total!
**ScaLAPACK**
- computational, driver and auxiliary routines for distributed-memory architectures via MPI/BLACS
**DFTs (General FFTs)**
- Mixed radix, multi-dimensional transforms
- Multi threaded
**Cluster FFT**
- For distributed-memory architectures via MPI/BLACS

**Notes:**
Intel® Math Kernel Library Contents

This and next slide are to give an overview of what MKL contents.  Later slide will talk more detail on each of these modules.

## Intel® Math Kernel Library Contents

**Sparse Solvers (PARDISO, DSS and and ISS)**
- For symmetric, structurally symmetric or non-symmetric, positive definite, indefinite or Hermitian sparse linear system of equations
- OOC version for huge problem sizes
**VML (Vector Math Library)**
- Set of vectorized transcendental functions, most of libm functions, but faster
**VSL (Vector Statistical Library)**
- Set of vectorized random number generators
**PDEs (Partial Differential Equations)**
- Trigonometric transform and Poisson solvers.
**Optimization Solvers**
- Solvers for nonlinear least square problems with/without boundary condition
**GMP**
- arbitrary precision arithmetic operations on integer numbers

**Notes:**
Support functions for memory management, thread control etc.

## Intel® Math Kernel Library Contents

- Data types supported:
- Single precision Real and Complex
- Double precision Real and Complex
- *A few domains, such as Sparse Solvers only have some data type support in MKL 10.0
- Support Functions/Examples
- We aim to run well on Intel/AMD
- C/C++, Fortran and now a few Java examples
- Well documented

## The MKL Team

- Around 40 code developers
- Doesn’t count: answering user questions/issues, documentation, installation

## At present, Multi-core is done via OpenMP Threading

-  MKL supports OpenMP 2.5 (from Compilers) and beyond
-  We have special threading environment variables
- MKL_DYNAMIC
- MKL_NUM_THREADS
- MKL_DOMAIN_NUM_THREADS
- (routine equivalents always have precedence)
- MKL_DYNAMIC:
- True (Default): MKL can change the number of requested threads for performance reasons
- False: MKL will try not to change the number of requested threads
- MKL_NUM_THREADS
- Set to a different number than OMP_NUM_THREADS
- MKL_DOMAIN_NUM_THREADS
- Different domains in MKL can use different threading values

## Intel® MKL Threading

- There are numerous opportunities for threading:
- Level 3 BLAS ( O(n3) )
- LAPACK* ( O(n3) )
- FFTs ( O(n log(n) )
- VML, VSL ? depends on processor and function

- Not threaded on some routines due to:
-     Limited resource is memory bandwidth.
-     NUMA may change this for future MKL

- Threaded using OpenMP*
- With support for GCC* and Microsoft* OpenMP*

- ScaLAPACK and Cluster FFT are SMP Parallel
- All Intel® MKL is thread-safe

**Notes:**
Threading

Thread safe: say DDOT called from 2 different threads; it will not confuse induction variables.
All local vars kept on stack.
Also, be careful with data statements; for example, do not put induction vars in data statement designed in
We are experimenting threading for large BLAS 1 for Nehalem architecture, since the additional memory controllers might increase the Bandwidth. 

## MKL Threading Decisions

-  We try to use the OpenMP library’s suggested number of threads
- Often a large value on a multi-core machine
- If the requested number of threads is greater than the number of physical cores, and MKL_DYNAMIC is TRUE (default), we will scale down to the number of physical cores
- May have with SMT-on
- If the user is running MPI, and we cannot detect that it is being used in a thread-safe mode, we will scale down to 1 thread
- If the user is a parallel region, and MKL_DYNAMIC is TRUE (default), we will scale down to 1 thread.

## MPI

- First Used with ScaLAPACK
- Creation of the “Extended BLACS”
- 		Ported to: SGI MPI, HP MPI, Intel MPI, OpenMPI, MPICH1, MPICH 2
- 		Demonstrates we don’t focus on latency, or more than about 30 MPI calls
- Distributed Memory FFT
- Many MPI-issues are handled inside the library (not for users)

## MPI-Only Issues for Us

- MPI ignores Shared Cache
- We’ve been experimenting with Hybrid OpenMP/MPI
- Hybrid ScaLAPACK/MP LINPACK

## Intel® MKL: ScaLAPACK

- LAPACK for distributed memory architectures
- Uses MPI, BLACS, BLAS, and LAPACK
- Uses 2D block cyclic data distribution for dense matrix computations which helps
- Better work balance between available processors
- Use BLAS level 3 for optimized local computations
- Optimization Opportunities:
- Recursive Blocking (Inner Algorithmic Blocking)
- Outer Algorithmic Blocking (Beyond Physical-Only Blocking found in the NETLIB source)
- Threading
- MPI Tunings (via Extended BLACS)
- Algorithmic Enhancements

## Fast Fourier Transform Performance  

- Threading Optimizations
- Intel MKL FFTs are extensively threaded to take advantage of multiprocessors

**Intel® Xeon® Processor****  **
- Intel MKL single thread performance is often greater than FFTW* 2 and 4 thread performance
- Intel MKL can deliver >100% gain

**Intel® Itanium® 2 Processor**
- Outstanding scaling performance for 2, 4, and 8 threads
- Intel MKL can deliver significant performance benefits over FFTW*

**BLAS/LAPACK****  ****ScaLAPACK ****Sparse Solver****FFTs****VML****VSL**

## Intel® MKL: Cluster FFT

- FFT for SMP systems/clusters
- Works with MPI using “Extended BLACS”
- 1, 2, 3 and multidimensional
- Requires basic MPI programming skills
- Same interface as the DFT from standard MKL

- Intel may make changes to specification, product descriptions, and plans at any time, without notice.
-  Performance tests and ratings are measured using specific computer systems and/or components and reflect the approximate performance of Intel products as measured by those tests.  Any difference in system hardware or software design or configuration may affect actual performance.  Buyers should consult other sources of information to evaluate the performance of systems or components they are considering purchasing.  For more information on performance tests and on the performance of Intel products, reference www.intel.com/software/products or call (U.S.) 1-800-628-8686 or 1-916-356-3104

**Notes:**
BLACS  - Message passing library for linear algebra

Chart shows Cluster FFT performance comparison between Intel MKL CFFT Vs Open source FFTW and FFTE

## More on Threading in LAPACK

-  LAPACK Originally Threaded based on the BLAS
-  MKL has been threading LAPACK at an iteration level (in the previous releases)
-  Current Research points to threading at an algorithm-level
- DAG techniques
- PLASMA (You heard from Jack)
- FLAME
- MKL is already doing these techniques in MKL 10.0.3

- Backup
- But we may want to glance at a more recent Cholesky

## Direct acyclic graph

## Graph flow optimizations

- Minimization of critical path
- Factorize ahead. QR factorization is preferably performed by the thread which performed the last panel update.
- Task with lower stage number has always higher priority that task with larger stage
- Maximization of task performance:
- Free thread chooses a task for panel previously been processed by this thread (for better cache usage).
- Thread gets a block of neighboring panels for execution of  tasks.  Other threads have possibility to steal uncompleted  tasks in the bundle, if they have nothing to do.

## Factorize ahead

- y y y y y y y y y
- 0 y y y y y y y y
- 0 0 y y y y y y y
- 0 0 0 z z y y y y
- 0 0 0 0 z y y y y

- 2

- y y y x x x x x x
- 0 y y x x x x x x
- 0 0 y x x x x x x
- 0 0 0 x x x x x x
- 0 0 0 x x x x x x

- 1

- y y y y y y y y y
- 0 y y y y y y y y
- 0 0 y y y y y y y
- 0 0 0 z z z z z z
- 0 0 0 0 z z z z z

- 2

- Non parallel part

- The next QR
- is always
- hidden

## Performance results for  QR factorization

## Performance results for Cholesky factorization

## D&C SEP Results versus other methods (relative)