# Presentation: 045942

## MPI and OpenMP Paradigms on Cluster of SMP Architectures: the Vacancy Tracking Algorithm for Multi-Dimensional Array Transposition

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

- Yun (Helen) He, SC2002

- 11/19/2002

##                           Outline

- Introduction
- Background
- 2-array transpose method
- In-place vacancy tracking method
- Performance on single CPU
- Parallelization of Vacancy Tracking Method
- Pure OpenMP
- Pure MPI
- Hybrid MPI/OpenMP
- Performance
- Scheduling for pure OpenMP
- Pure MPI and pure OpenMP within one node
- Pure MPI and Hybrid MPI/OpenMP across nodes
- Conclusions

- Yun (Helen) He, SC2002

- 11/19/2002

##                      Background

- Mixed MPI/openMP is software trend for SMP architectures
- Elegant in concept and architecture
- Negative experiences: NAS, CG, PS,  indicate pure MPI outperforms mixed MPI/openMP
- Array transpose on distributed memory architectures equals the remapping of problem subdomains
- Used in many scientific and engineering applications
- Climate model: longitude local <=> height local

- Yun (Helen) He, SC2002

- 11/19/2002

## Two-Array Transpose Method

- Reshuffle Phase
*B[k**1**,k**3**,k**2**]**** A[k**1**,k**2**,k**3**]*
- Use auxiliary array *B*
- Copy Back Phase
*A**** B*
**Combine Effect**
*A’[k**1**,k**3**,k**2**]**** A[k**1**,k**2**,k**3**]*

- Yun (Helen) He, SC2002

- 11/19/2002

##   Vacancy Tracking Method

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

*         **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
**   ****Cycles are closed, non-overlapping.**

- Yun (Helen) He, SC2002

- 11/19/2002

##       Algorithm to Generate Tracking Cycles

- ! For 2D array *A*, viewed as *A(N1,N2)* at input and as *A(N2,N1)* at output.
- ! Starting with (i1,i2), find vacancy tracking cycle
-         ioffset_start = index_to_offset (N1,N2,i1,i2)
-         ioffset_next = -1
-         tmp = A (ioffset_start)
-         ioffset = ioffset_start
-         do while ( ioffset_next .NOT_EQUAL. ioffset_start)             (C.1)
-                call offset_to_index (ioffset,N2,N1,j1,j2)          ! N1,N2 exchanged
-                ioffset_next = index_to_offset (N1,N2,j2,j1)     ! j1,j2 exchanged
-                if (ioffset .NOT_EQUAL. ioffset_next) then
-                     A (ioffset) = A (ioffset_next)
-                     ioffset = ioffset_next
-                end if
-         end_do_while
-         A (ioffset_next) = tmp

- Yun (Helen) He, SC2002

- 11/19/2002

##     In-Place vs. Two-Array

- Yun (Helen) He, SC2002

- 11/19/2002

##      Memory Access Volume and Pattern

- Eliminates auxiliary array and copy-back phase, reduces memory access in half.
- Has less memory access due to length-1 cycles not touched.
- Has more irregular memory access pattern than traditional method, but gap becomes smaller when size of move is larger than cache-line size.
- Same as 2-array method: inefficient memory access due to large stride.

- Yun (Helen) He, SC2002

- 11/19/2002

##                           Outline

- Introduction
- Background
- 2-array transpose method
- In-place vacancy tracking method
- Performance on single CPU
- Parallelization of Vacancy Tracking Method
- Pure OpenMP
- Pure MPI
- Hybrid MPI/OpenMP
- Performance
- Scheduling for pure OpenMP
- Pure MPI and pure OpenMP within one node
- Pure MPI and Hybrid MPI/OpenMP across nodes
- Conclusions

- Yun (Helen) He, SC2002

- 11/19/2002

##    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

- Yun (Helen) He, SC2002

- 11/19/2002

##                Pure MPI

***A(N******1******,N******2******,N******3******)***** ******** *****A(N******1******,N******3******,N******2******)***** on *****P***** processors:**

- (G1) Do a local transpose on the local array
-             *A(N**1**,N**2**,N**3**/P)  ** A(N**1**,N**3**/P,N**2**).*
- (G2) Do a global all-to-all exchange of data blocks,
-         each of size N1(N3/P)(N2/P).
- (G3) Do a local transpose on the local array
-               *A(N**1**,N**3**/P,N**2**),* viewed as *A(N**1**N**3**/P,N**2**/P,P)*
-          *A(N**1**N**3**/P,P,N**2**/P),* viewed as *A(N**1**,N**3**,N**2**/P).*

- Yun (Helen) He, SC2002

- 11/19/2002

##          Global all-to-all Exchange

-  ! All processors simultaneously do the following:
-     do q = 1, P - 1
-        send a message to destination processor destID
-        receive a message from source processor srcID
-     end do
-  ! where destID = srcID = (myID XOR q)

- Yun (Helen) He, SC2002

- 11/19/2002

##       Total Transpose Time (Pure MPI)

-  Use “latency+ message-size / bandwidth” model
-  TP = 2MN1N2N3/P + 2L(P-1) + [2N1N3N2 /BP][(P-1)/P]
-  where P --- total number of CPUs
-             M --- average memory access time per element
-             L --- communication latency
-             B --- communication bandwidth

- Yun (Helen) He, SC2002

- 11/19/2002

##  Total Transpose Time (Hybrid MPI/OpenMP)

- Parallelize local transposes (G1) and (G3) with OpenMP
-      N_CPU = N_MPI * N_threads
-     T = 2MN1N2N3/NCPU + 2L(NMPI-1)
-            + [2N1N3N2/BNMPI][(NMPI-1)/NMPI]
-  where NCPU --- total number of CPUs
-             NMPI --- number of MPI tasks

- Yun (Helen) He, SC2002

- 11/19/2002

##                           Outline

- Introduction
- Background
- 2-array transpose method
- In-place vacancy tracking method
- Performance on single CPU
- Parallelization of Vacancy Tracking Method
- Pure OpenMP
- Pure MPI
- Hybrid MPI/OpenMP
- Performance
- Scheduling for pure OpenMP
- Pure MPI and pure OpenMP within one node
- Pure MPI and Hybrid MPI/OpenMP across nodes
- Conclusions

- Yun (Helen) He, SC2002

- 11/19/2002

## 	   Scheduling for OpenMP

**Static**: Loops are divided into *n_thrds* partitions, each containing *ceiling(n_iters/n_thrds)* iterations.
**Affinity**: Loops are divided into *n_thrds* partitions, each containing *ceiling(n_iters/n_thrds)* iterations.  Then each partition is subdivided into chunks containing *ceiling(n_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(n_iter/n_thrds)* iterations. Subsequent chunk contains *ceiling(n_left_iters /n_thrds)* iterations.
**Dynamic, n**: Loops are divided into chunks containing *n* iterations.  We choose different chunk sizes.

- Yun (Helen) He, SC2002

- 11/19/2002

## Scheduling for OpenMP within one Node 

- 64x512x128:   N_cycles = 4114,   cycle_lengths = 16 16x1024x256: N_cycles = 29140, cycle_lengths= 9, 3

- Yun (Helen) He, SC2002

- 11/19/2002

## Scheduling for OpenMP within one Node (cont’d) 

- 8x1000x500: N_cycles = 132, cycle_lengths = 8890, 1778, 70, 14, 5
- 32x100x25:   N_cycles = 42,   cycle_lengths = 168, 24, 21, 8, 3.

- Yun (Helen) He, SC2002

- 11/19/2002

## Pure MPI and Pure OpenMP Within One Node

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

- Yun (Helen) He, SC2002

- 11/19/2002

## 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.

- Yun (Helen) He, SC2002

- 11/19/2002

##                        Conclusions

- In-place vacancy tracking method outperforms 2-array method.  It could be explained by the elimination of copy back and memory access volume and pattern.
- Independency and non-overlapping of tracking cycles allow multi-threaded parallelization.
- SMP schedule *affinity* optimizes performances for larger number of cycles and small cycle lengths. Schedule *dynamic* for smaller number of cycles and larger or uneven cycle lengths.
- The algorithm could be parallelized using pure MPI with the combination of local vacancy tracking and global exchanging.

- Yun (Helen) He, SC2002

- 11/19/2002

##        Conclusions (cont’d)

- Pure OpenMP performs more than twice faster than pure MPI within one node.  It makes sense to develop a hybrid MPI/OpenMP algorithm.
- Hybrid approach parallelizes the local transposes with OpenMP, and MPI is still used for global exchange across nodes.
- Given the total number of CPUs, the number of MPI tasks and OpenMP threads need to be carefully chosen for optimal performance. In our test runs, a factor of 4 speedup is gained compared to pure MPI.
- This paper gives a positive experience of developing hybrid MPI/OpenMP parallel paradigms.

- Yun (Helen) He, SC2002

- 11/19/2002