# Presentation: 217426

## Improving the Performance of MPI Datatypes

- William Gropp, Ewing Lusk, and Debbie SwiderMathematics and Computer ScienceArgonne National Laboratoryhttp://www.mcs.anl.gov/~gropp

## The Unfulfilled Promise of MPI Datatypes

- Datatypes offer a way to minimize memory motion
- An MPI implementation can move data directly from source to destination
- (Datatypese also describe data for heterogeneous environments)
- In practice, performance is disappointing:
**Slow**: *significantly* slower than when the user packs and unpacks data to contiguous memory
**Surprising**: Different ways of expressing the same pattern may have wildly different performance

## Datatypes for Matrices

- Using MPI_Type_vector, a separate datatype is required for each row:MPI_Type_vector(m,1,lda,            basetype,&newtype)
- Using MPI_Type_struct with MPI_UB, a only a single datatype is needed:MPI_Type_struct(2,{1,1},    {0,lda*sizeof(old)},    {oldtype,MPI_UB},&newtype)
- MPI-2 MPI_Type_create_resized is official replacement for MPI_UB

- Matrix in Fortran (column) major order:

- m

- Sending pivot rows to other processes

## Performance of MPI Datatypes

- Performance of MPI_Type_Vector
- 1000 doubles with stride 24
- Performance in MB/sec

- Equivalent Type_Struct

- MPICH *is* Vendor MPI

## Datatype Abstractions

- Standard Unix abstraction is “block of contiguous bytes” (e.g., readv, writev)
- MPI specifies datatypes recursively as
- count of (type,offset)where offset may be relative or absolute
- MPICH uses a simplified form of this for MPI_Type_vector (and so outperforms vendor MPIs)
- More general form would provide superior performance for most user-defined datatypes
- MPI implementations can improve

## Some Ground Rules

- System (or at least communicator) has same data representation
- All basic datatypes can be replaced with (contiguous copies of) MPI_BYTE
- Detailed datatype info (required by MPI-2) may be stored separately
- Only the “pack” direction will be discussed

## A Taxonomy of Datatypes

- All MPI datatypes have
- count
- either offset or displacement to the next element
- fixed or variable length for each element
- A rule for setting the *extent* (used to determine the placement of the next instance)

## Considering the Extent Separately

- Both cases move the same data
- Only the final extent is different

- Extent of MPI_Type_vector

- Extent of (contiguous,n of) MPI_Type_create_resizedor types with MPI_UB

## Strided

- For (I=0; I<n; I++) {    memcpy(dest,src,len);    dest += len;    src   += stride;}

## Fixed Indexed

- For (I=0; I<n; I++) {    memcpy(dest,base+offset[I],len);    dest += len;}

## Variable Indexed

- For (I=0; I<n; I++) {    memcpy(dest,base+offset[I],len[I]);    dest += len[I];}

## Summary of Datatypes

- Fixed length block with offset relative to the previous element
- Strided
- Fixed length block with absolute offset
- Fixed length indexed
- Variable length block with absolute offset
- Variable length indexed
- In each case, replace “memcpy” with “pack datatype” when base type is not contiguous

## Representing MPI Datatypes

- Strided
- Vector and hvector; resized contiguous; contiguous of resized
- Extent rule is different in the cases
- Fixed length indexed
- Create_indexed_block (MPI-2 but common usage); some Index, hindex, and struct.
- Variable length indexed
- Struct, index, hindex

## Datatypes as Trees

- R copies of Vec, each with n Type1
- Q copies of Struct, each with m Type2 and k Type3
- P copies of Type4

## Datatypes as Trees

- Rn + q(m+k) + p uses of basic datatypes
- That’s a lot of jumping around in the code

- Struct

- Vec

- Struct

- Type4

- Type2

- Type1

- Type3

- n

- m

- k

- p

- q

- r

## Datatypes as Trees

- R + q + p uses of basic loops
- Classic loop merging technique to improve performance

- Struct

- Vec

- Struct

- Type4

- Type2

- Type1

- Type3

- n

- m

- k

- p

- q

- r

- Basic loop leaves

## Implementation Issues

- Block moves use data-aligned loops for small count, memcpy for large count
- Need for partial traversal (e.g., for packetization) requires explicit handling of recursion with stack
- Stack overflow test done at type creation time
- Quick detection of leaf important
- Internal datatype layout needs to be compatible with stack operations

## Results

- MPICH results pack data into a separate buffer, mimicking user code
- Results are preliminary
- Some optimizations not taken
- MPICH still needs single copy of data
- Packetization issues not included
- Simple vector types already handled by MPICH

## Resized Datatype

- Doubles with a stride of 16 using Type_struct with MPI_UB.
- Difference in user time due to faster SGI contiguous send/receive

## Sending a Face of a Cube

- 2 faces can be sent using single vector (with blocklen)
- Third face requires hvector of vector

- nx

- ny

- nz

- MPI_Type_vector(my,1,nx,             oldtype,&t1);MPI_Type_hvector(mz,1,    nx*ny*sizeof(old),t1,    &new)

- MPI_Type_vector( mz,mx,nx*ny,old,&new)

- MPI_Type_vector(my,mx,nx,old,&new)

## Speeding the Processing of Types of Types

- Hvec invokes Vec mz times:for (I=0;I<mz;I++) {    push(vec);    process_datatype;    pop;}
- Move stack operations out of loop:push(vec);for (I=0;I<mz;I++) {    process_datatype;}pop;
- This is a general approach

- Hvec

- Vec

- Double

- mz

- my

- Really strided

- Data from stack top

- Data from stack top-1

## 2-D Face of 3-D 

- 200x200x200 cube, 100x100 y-z face

- 200x200x200 cube, 198x198 y-z face

## Conclusions

- All MPI Datatypes can be represented as one of 3 loops, plus contiguous
- More optimizations yet to be tried
- Still not better than user packing to contiguous buffer
- MPICH datatype overhead can be reduced
- But much closer:
- Users can now choose between letting MPI manage data motion and squeezing more performance out