# Presentation: 045935

## Hybrid OpenMP and MPI  Programming and Tuning

- Yun (Helen) He and Chris Ding
- Lawrence Berkeley National Laboratory

- NUG2004

- 06/24/2004

## Outline

**Introduction**
- Why Hybrid
- Compile, Link, and Run
- Parallelization Strategies
- Simple Example: Ax=b
- MPI_init_thread Choices
- Debug and Tune
**Examples**
- Multi-dimensional Array Transpose
- Community Atmosphere Model
- MM5 Regional Climate Model
- Some Other Benchmarks
**Conclusions**

- NUG2004

- 06/24/2004

## MPI vs. OpenMP

**Pure MPI Pro:**
- Portable to distributed and shared memory machines.
- Scales beyond one node
- No data placement problem
**Pure MPI Con:**
- Difficult to develop and debug
- High latency, low bandwidth
- Explicit communication
- Large granularity
- Difficult load balancing** **
**	**

**Pure OpenMP Pro:**
- Easy to implement parallelism
- Low latency, high bandwidth
- Implicit Communication
- Coarse and fine granularity
- Dynamic load balancing
**Pure OpenMP Con:**
- Only on shared memory machines
- Scale within one node
- Possible data placement problem
- No specific thread order

- NUG2004

- 06/24/2004

## Why Hybrid

- Hybrid MPI/OpenMP paradigm is the software trend for clusters of SMP architectures.
- Elegant in concept and architecture: using MPI across nodes and OpenMP within nodes. Good usage of shared memory system resource (memory, latency, and bandwidth).
- Avoids the extra communication overhead with MPI within node.
- OpenMP adds fine granularity (larger message sizes) and allows increased and/or dynamic load balancing.
- Some problems have two-level parallelism naturally.
- Some problems could only use restricted number of MPI tasks.
- Could have better scalability than both pure MPI and pure OpenMP.
**My code speeds up by a factor of**** 4.44****.**

- NUG2004

- 06/24/2004

## Why Mixed OpenMP/MPI Code is Sometimes Slower?

- OpenMP has less scalability due to implicit parallelism while **MPI allows multi-dimensional blocking**.
- All threads are idle except one while MPI communication.
- Need overlap comp and comm for better performance.
- Critical Section for shared variables.
- Thread creation overhead
- Cache coherence, data placement.
- Natural one level parallelism problems.
- Pure OpenMP code performs worse than pure MPI within node.
- Lack of optimized OpenMP compilers/libraries.
**Positive and Negative experiences:**
- Positive: CAM, MM5, ...
- Negative: NAS, CG, PS,  ...

- NUG2004

- 06/24/2004

## A Pseudo Hybrid Code

-  **Program hybrid**
-  call MPI_INIT (ierr)
-  call MPI_COMM_RANK (...)
-  call MPI_COMM_SIZE (...)
-   ...  some computation and MPI communication
-   call OMP_SET_NUM_THREADS(4)
-  !$OMP PARALLEL DO PRIVATE(i)
-  !$OMP&                    SHARED(n)
-     do i=1,n
-         ... computation
-     enddo
-   !$OMP END PARALLEL DO
-   ...  some computation and MPI communication
-  call MPI_FINALIZE (ierr)
-  **end**

- NUG2004

- 06/24/2004

## Compile, link, and Run

- % mpxlf90_r –qsmp=omp -o hybrid –O3 hybrid.f90
- % setenv XLSMPOPTS parthds=4
-     (or % setenv OMP_NUM_THREADS 4)
- % poe hybrid –nodes 2 –tasks_per_node 4
- Loadleveler Script: (% llsubmit job.hybrid)
-        #@ shell = /usr/bin/csh
-        #@ output = $(jobid).$(stepid).out
-        #@ error = $(jobid).$(stepid).err
-        #@ class = debug
-        #@ node = 2
-        #@ tasks_per_node = 4
-        #@ network.MPI = csss,not_shared,us
-        #@ wall_clock_limit = 00:02:00
-        #@ notification = complete
-        #@ job_type = parallel
-        #@ environment = COPY_ALL
-        #@ queue
-        hybrid
-        exit

- NUG2004

- 06/24/2004

## Other Environment Variables

- MP_WAIT_MODE: Tasks wait mode, could be poll, yield, or sleep. Default value is poll for US and sleep for IP.
- MP_POLLING_INTERVAL: the polling interval.
- By default, a thread in OpenMP application goes to sleep after finish its work.
- By putting thread in a busy-waiting instead of sleep could reduce overhead in thread reactivation.
- SPINLOOPTIME:  time spent in busy wait before yield
- YIELDLOOPTIME: time spent in spin-yield cycle before fall asleep.

- NUG2004

- 06/24/2004

## Loop-based vs. SPMD

-   Loop-based:
-   !$OMP PARALLEL DO PRIVATE(i)
-   !$OMP&             SHARED(a,b,n)
-     do i=1,n
-         a(i)=a(i)+b(i)
-     enddo
-   !$OMP END PARALLEL DO

-   SPMD:
-   !$OMP PARALLEL DO PRIVATE(start, end, i)
-   !$OMP&                   SHARED(a,b)
-      num_thrds = omp_get_num_threads()
-     thrd_id = omp_get_thread_num()
-     start = n* thrd_id/num_thrds + 1
-     end = n*(thrd_num+1)/num_thrds
-     do i = start, end
-         a(i)=a(i)+b(i)
-     enddo
-   !$OMP END PARALLEL DO

**SPMD code normally gives better performance than loop-based code,** but more difficult to implement:
-   Less thread synchronization.
-   Less cache misses.
-   More compiler optimizations.

- NUG2004

- 06/24/2004

## Hybrid Parallelization Strategies

- From sequential code, decompose with MPI first, then add OpenMP.
- From OpenMP code, treat as serial code.
- From MPI code, add OpenMP.
- Simplest and least error-prone way is to use MPI outside parallel region, and allow only master thread to communicate between MPI tasks.
- Could use MPI inside parallel region with thread-safe MPI.

- NUG2004

- 06/24/2004

## A Simple Example: Ax=b

-  c = 0.0
-  do j = 1, n_loc
-  !$OMP DO PARALLEL
-  !$OMP SHARED(a,b), PRIVATE(i)
-  !$OMP REDUCTION(+:c)
-  do i = 1, nrows
-    c(i) = c(i) + a(i,j)*b(i)
-  enddo
-  enddo
-  call MPI_REDUCE_SCATTER(c)

**=**

-  OMP does not support vector reduction
-  Wrong answer since c is shared!

- process

-    thread

- NUG2004

- 06/24/2004

## Correct Implementations

-  IBM SMP:
-  c = 0.0
-  !$SMP PARALLEL REDUCTION(+:c)
-  c = 0.0
-  do j = 1, n_loc
-  !$SMP DO PRIVATE(i)
-  do i = 1, nrows
-    c(i) = c(i) + a(i,j)*b(i)
-  enddo
-  !$SMP END DO NOWAIT
-  enddo
-  !$SMP END PARALLEL
-  call MPI_REDUCE_SCATTER(c)

-  OPENMP:
-  c = 0.0
-  !$OMP PARALLEL SHARED(c), PRIVATE(c_loc)
-  c_loc = 0.0
-  do j = 1, n_loc
-  !$OMP DO PRIVATE(i)
-  do i = 1, nrows
-    c_loc(i) = c_loc(i) + a(i,j)*b(i)
-  enddo
-  !$OMP END DO NOWAIT
-  enddo
-  !$OMP CRITICAL
-   c = c + c_loc
-  !$OMP END CRITICAL
-  !$OMP END PARALLEL
-  call MPI_REDUCE_SCATTER(c)

- NUG2004

- 06/24/2004

## MPI_INIT_Thread Choices

- MPI_INIT_THREAD* *(required, provided, ierr)
- IN: required, desired level of thread support (integer).
- OUT: provided, provided level of thread support (integer).
- Returned provided maybe less than required.
- Thread support levels:
- MPI_THREAD_SINGLE: Only one thread will execute.
- MPI_THREAD_FUNNELED: Process may be multi-threaded, but only main thread will make MPI calls (all MPI calls are ’’funneled'' to main thread).  Default value for SP.
- MPI_THREAD_SERIALIZED: Process may be multi-threaded, multiple threads may make MPI calls, but only one at a time: MPI calls are not made concurrently from two distinct threads (all MPI calls are ’’serialized'').
- MPI_THREAD_MULTIPLE: Multiple threads may call MPI, with no restrictions.

- NUG2004

- 06/24/2004

## MPI Calls Inside OMP MASTER

- MPI_THREAD_FUNNELED is required.
- OMP_BARRIER is needed since there is no synchronization with OMP_MASTER.
- It implies all other threads are sleeping!

- !$OMP BARRIER
- !$OMP MASTER
-      **call MPI_xxx(...)**
- !$OMP END MASTER
- !$OMP BARRIER

- NUG2004

- 06/24/2004

## MPI Calls Inside OMP SINGLE

- MPI_THREAD_SERIALIZED is required.
- OMP_BARRIER is needed since OMP_SINGLE only guarantees synchronization at the end.
- It also implies all other threads are sleeping!

- !$OMP BARRIER
- !$OMP SINGLE
-      **call MPI_xxx(...)**
- !$OMP END SINGLE

- NUG2004

- 06/24/2004

## THREAD FUNNELED/SERIALIZED vs. Pure MPI

- FUNNELED/SERIALIZED:
- All other threads are sleeping while single thread communicating.
- Only one thread communicating maybe not able to saturate the inter-node bandwidth.
- Pure MPI:
- Every CPU communicating may over saturate the inter-node bandwidth.
- Overlap communication with computation!

- NUG2004

- 06/24/2004

## Overlap COMM and COMP

- Need at least MPI_THREAD_FUNNELED.
- While master or single thread is making MPI calls, other threads are computing!
- Must be able to separate codes that can run before or after halo info is received.  Very hard!

-  !$OMP PARALLEL
-      if (my_thread_rank < 1) then
-          **call MPI_xxx(...)**
-      else
-          **do some computation**
-      endif
-  !$OMP END PARALLEL

- NUG2004

- 06/24/2004

## Scheduling for OpenMP

**Static**: Loops are divided into #*thrds* partitions, each containing *ceiling(#iters/#thrds)* iterations.
**Affinity**: Loops are divided into *n_thrds* partitions, each containing *ceiling(#iters/#thrds)* iterations.  Then each partition is subdivided into chunks containing *ceiling(#left_iters_in_partion/2)* iterations.
**Guided**: Loops are divided into progressively smaller chunks until the chunk size is 1.  The first chunk contains *ceiling(#iters/#thrds)* iterations. Subsequent chunk contains *ceiling(#left_iters/#thrds)* iterations.
**Dynamic, n**: Loops are divided into chunks containing *n* iterations.  We choose different chunk sizes.

- NUG2004

- 06/24/2004

## Debug and Tune Hybrid Codes

- Debug and Tune MPI code and OpenMP code separately.
- Use Guideview or Assureview to tune OpenMP code.
- Use Vampir to tune MPI code.
- Decide which loop to parallelize. Better to parallelize outer loop.  Decide whether Loop permutation, fusion or exchange is needed.
- Choose between loop-based or SPMD.
- Use different OpenMP task scheduling options.
- Experiment with different combinations of MPI tasks and number of threads per MPI task. Less MPI tasks may not saturate inter-node bandwidth.
- Adjust environment variables.
- Aggressively investigate different thread initialization options and the possibility of overlapping communication with computation.

- NUG2004

- 06/24/2004

## KAP OpenMP Compiler - Guide

- A high-performance OpenMP compiler for Fortran, C and C++.
- Also supports the full debugging and performance analysis of OpenMP and hybrid MPI/OpenMP programs *via* Guideview.

*%  guidef90  **<driver options> -WG,<guide options> *
*     **<filename> <xlf compiler options> *
*%  guideview <statfile> *

- NUG2004

- 06/24/2004

## KAP OpenMP Debugging Tools - Assure

- A programming tool to validate the correctness of an OpenMP program.

*%  assuref90 -WApname=pg –o a.exe a.f -O3 *
*%  a.exe *
*%  assureview pg*

*%  mpassuref90 <driver options> -WA,<assure options> *
*     **<filename> <xlf compiler options>*
*%  setenv KDD_OUTPUT=project.%H.%I*
*%  poe ./a.out –procs 2 –nodes 4*
*%  assureview assure.prj project.{hostname}.{process-id}.kdd *

-   Could also be used to validate **the ****OpenMP section   ****     in a hybrid MPI/OpenMP**** code.**** **

- NUG2004

- 06/24/2004

## Other Debugging, Performance Monitoring and Tuning Tools 

- HPM Toolkit: IBM hardware performance monitor for C/C++, Fortran77/90, HPF.
- TAU: C/C++, Fortran, Java performance tool.
- Totalview: Graphic parallel debugger for C/C++, F90.
- Vampir: MPI performance tool.
- Xprofiler: Graphic profiling tool.

- NUG2004

- 06/24/2004

## Story 1: Distributed Multi-Dimensional Array Transpose With Vacancy Tracking Method

-            *A(3,2) **** A(2,3)*
- Tracking cycle: 1 – 3 – 4 – 2 - 1

- Cycles are closed, non-overlapping.

*             **A(2,3,4)** ****A(3,4,2),* tracking cycles:
-        1 - 4 - 16 - 18 - 3 - 12 - 2 - 8 - 9 - 13 - 6 - 1
-        5 - 20 - 11 - 21 - 15 - 14 - 10 - 17 - 22 - 19 - 7 – 5

- NUG2004

- 06/24/2004

## Multi-Threaded Parallelism

-    Key: Independence of tracking cycles.
- !$OMP PARALLEL DO DEFAULT (PRIVATE)
- !$OMP&         SHARED (N_cycles, info_table, Array)      (C.2)
- !$OMP&         SCHEDULE (AFFINITY)
-       do k = 1, N_cycles
-          an inner loop of memory exchange for each cycle using info_table
-       enddo
- !$OMP END PARALLEL DO

- NUG2004

- 06/24/2004

## Scheduling for OpenMPwithin one Node 

- 64x512x128:   *N_cycles* = 4114,   *cycle_lengths* = 16 16x1024x256: *N_cycles* = 29140, *cycle_lengths*= 9, 3
- Schedule “affinity” is the best for large number of cycles and regular short cycles.

- 8x1000x500: *N_cycles* = 132, *cycle_lengths* = 8890, 1778, 70, 14, 5 32x100x25:   *N_cycles* = 42,   *cycle_lengths* = 168, 24, 21, 8, 3.
- Schedule “dynamic,1” is the best for small number of cycles with large irregular cycle lengths.

- NUG2004

- 06/24/2004

## Pure MPI and Pure OpenMP within One Node

- OpenMP *vs.* MPI (16 CPUs)
- 64x512x128:  2.76 times faster
- 16x1024x256:1.99 times faster

- NUG2004

- 06/24/2004

## Pure MPI and Hybrid MPI/OpenMP Across Nodes

- With 128 CPUs, n_thrds=4 hybrid MPI/OpenMP performs faster than n_thrds=16 hybrid by a factor of 1.59, and faster than pure MPI by a factor of 4.44.

- NUG2004

- 06/24/2004

## Story 2: Community Atmosphere Model (CAM) Performance on SPPat Worley, ORNL

- T42L26 grid size:
- 128(lon)*64(lat)
- *26 (vertical)

- NUG2004

- 06/24/2004

## CAM Observation

- CAM has two computational phases: dynamics and physics. Dynamics need much more interprocessor communication than physics.
- Original parallelization with pure MPI is limited to 1-D domain decomposition; the number of maximum CPUs used is limited to the number of latitude grids.

- NUG2004

- 06/24/2004

## CAM New Concept: Chunks

|  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
|  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |

- Longitude

- Latitude

- NUG2004

- 06/24/2004

## What Have Been Done to Improve CAM?

- The incorporation of chunks (column based data structures) allows dynamic load balancing and the usage of hybrid MPI/OpenMP method:
- Chunking in physics provides extra granularity.  It allows an increase in the number of processors used.
- Multiple chunks are assigned to each MPI processor, OpenMP threads loop over each local chunk.  Dynamic load balancing is adopted.
- The optimal chunk size depends on the machine architecture, 16-32 for SP.
- Overall Performance increases from 7 models years per simulation day with pure MPI to 36 model years with hybrid MPI/OpenMP (allow more CPUs), load balanced, updated dynamical core and community land model (CLM).
-      (11 years with pure MPI vs. 14 years with MPI/OpenMP both with 64 CPUs and load-balanced)

- NUG2004

- 06/24/2004

## Story 3: MM5 Regional Weather Prediction Model

- MM5  is approximately 50,000 lines of Fortran 77 with Cray extensions. It runs in pure shared-memory, pure distributed memory and mixed shared/distributed-memory mode.
- The code is parallelized by FLIC, a translator for same-source parallel implementation of regular grid applications.
- The different method of parallelization is implemented easily by including appropriate compiler commands and options to the existing configure.user build mechanism.

- NUG2004

- 06/24/2004

## MM5 Performance on 332 MHz SMP

| Method | Communication (sec) | Total (sec) |
| --- | --- | --- |
| 64 MPI tasks | 494 | 1755 |
| 16 MPI tasks with 4 threads/task | 281 | 1505 |

- 85% total reduction is in communication.
- threading also speeds up computation.

- Data from: http://www.chp.usherb.ca/doc/pdf/sp3/Atelier_IBM_CACPUS_oct2000/hybrid_programming_MPIOpenMP.PDF

- NUG2004

- 06/24/2004

## Story 4: Some Benchmark Results

-       Performance depends on:
- benchmark features
- Communication/computation patterns
- Problem size
- Hardware features
- Number of nodes
- Relative performance of CPU, memory, and communication system (latency, bandwidth)

- Data from: http://www.eecg.toronto.edu/~de/Pa-06.pdf

- NUG2004

- 06/24/2004

## Conclusions

- Pure OpenMP performs better than pure MPI within node is a necessity to have hybrid code better than pure MPI across node.
- Whether the hybrid code performs better than MPI code depends on whether the communication advantage outcomes the thread overhead, etc. or not.
- There are more positive experiences of developing hybrid MPI/OpenMP parallel paradigms now. It’s encouraging to adopt hybrid paradigm in your own application.

- NUG2004

- 06/24/2004

## The End

- Thank you very much!

- NUG2004

- 06/24/2004