[PDC - Center for Parallel Computers, KTH]

Discussion:
Derived Datatypes

This is the in-depth discussion layer of a two-part module. For an explanation of the layers and how to navigate within and between them, return to the top page of this module.

Table of Contents

  1. Goals and Prerequisites
  2. Why Would I Use Derived Datatypes?
    2.1 Basic MPI Datatypes
    2.2 Motivation
  3. What Are Derived Datatypes?
    3.1 General Datatypes and Typemaps
    3.2 Extent of a Datatype
  4. How and When Do I Use Derived Datatypes?
    4.1 When to Use
    4.2 How to Use
    4.3 Matching Rules
  5. Key Points

References | Lab Exercises | Quiz | Evaluation

[Table of Contents] [Section 1] [Section 2] [Section 3] [Section 4] [Section 5] [Less Detail]

1. Goals and Prerequisites

The goal of this material is to introduce you to the concept of MPI derived datatypes. After completing this material, you should know what derived datatypes are, and why, how, and when to use them. By trying the C or FORTRAN exercises, you will also gain hands-on experience. Check out the references included at the end of this material to learn even more about derived datatypes.

Constructing derived datatypes is mainly a case of going through each of the arguments to the routine you want to use and putting in the appropriate values. People often enter into the study of derived datatypes thinking they are very complicated, but after trying them, find them fairly straightforward.

As a prerequisite for this material, you should be familiar with the material in the Basics of MPI Programming, and have knowledge of MPI's basic data types.

WARNING

MPI-2 introduces several new functions for use in constructing derived datatypes. They are not described in this module. The descriptions in this module conform to MPI-1. Code that uses these functions should work in any MPI implementation that conforms to either version of the standard because backward compatibility is required. However, MPI-2 deprecates use of the functions that have been replaced, so anyone who is writing code that will be used only with implementations of the MPI-2 standard should use the new functions.

[Table of Contents] [Section 1] [Section 2] [Section 3] [Section 4] [Section 5] [Less Detail]

2. Why Would I Use Derived Datatypes?

2.1 Basic MPI Datatypes

Review, for a moment, MPI's basic datatypes, shown below:

Given these datatypes and a count, you can handle messages of contiguous data of the same type.

2.2 Motivation

What if you want to specify:

A few possible solutions suggest themselves:

Generally, however, these solutions are slow, clumsy, and wasteful of memory. Using MPI_BYTE or MPI_PACKED might also result in a program that isn't portable to a heterogeneous system of machines.

The idea of MPI derived datatypes is to provide a portable and efficient way of communicating non-contiguous or mixed types in a message. MPI derived datatypes provide a simpler, cleaner, more elegant and efficient way to handle this type of data, which is common. While you can get along without derived datatypes, you couldn't do so easily.

[ Caution: some implementations of MPI derived datatypes are not as efficient as they should be, particularly in terms of I/O wait times. Once you have your code running correctly, you may want to convert a few of the derived datatypes in your code's hotspots to MPI_BYTE or MPI_PACKED. Compare the timings of your converted code to that of your code using all MPI derived datatypes, and choose the one that gives you optimal performance. ]

[Table of Contents] [Section 1] [Section 2] [Section 3] [Section 4] [Section 5] [Less Detail]

3. What Are Derived Datatypes?

Derived datatypes are datatypes that are built from the basic MPI datatypes. To better understand what is needed to construct such a datatype, you need to understand the general concept of an MPI datatype, and something called a typemap.

3.1 General Datatypes and Typemaps

Formally, the MPI Standard defines a general datatype as an object that specifies two things:

An easy way to represent such an object is as a sequence of pairs of basic datatypes and displacements. MPI calls this sequence a typemap.

Typemap = {(type0, disp0), (type1, disp1), ..., (typeN, dispN)}

These displacements are relative to the buffer that the datatype is describing. For example, MPI_INT is a predefined handle to a datatype with typemap {(int,0)} with one entry of type int at zero displacement. The other basic datatypes are defined similarly. Seen in this way, derived datatypes are general datatypes with more than one (type, disp) pair.

3.2 Extent of a Datatype

The above is sufficient to answer the questions "what are derived datatypes?" From time to time, however, you may need to know a little bit more to use more complex derived datatypes successfully. In particular, it is useful to understand the concept of the extent of a derived datatype. For that, we need some more definitions.

lb(Typemap) = min(disp0, disp1, ..., dispN)

ub(Typemap) = max(disp0 + sizeof(type0), disp1 + sizeof(type1), ..., dispN + sizeof(typeN))

extent(Typemap) = ub(Typemap) - lb(Typemap) + pad

lb stands for lower bound. You can think of it as the location of the first byte described by the datatype. ub stands for the upper bound. It is the location of the last byte described by the datatype. sizeof is the size of the basic datatype in bytes. (Note: this is for basic datatypes.) extent is the difference between these two, possibly increased by pad to meet alignment requirements. Some languages, like FORTRAN and C, require that their datatypes be aligned a particular way in memory. Commonly, they require the address of a variable (in bytes) to be a multiple of its length (in bytes). MPI uses pad to take this into account, so the extent of a datatype is the span from the first byte to the last byte occupied by entries in this datatype, rounded up to satisfy alignment requirements. For all the basic datatypes, like MPI_DOUBLE, MPI_INTEGER, this is simply the number of bytes in them.

Consider an example for a derived datatype. Suppose extent(double) = 8, extent(int) = 4, and that a machine requires doubles to be aligned on 8-byte boundaries. If a derived datatype has typemap = {(int,0) (double,4)}, it follows that lb = min(0,4) = 0 and ub = max(0+4,4+8) = 12. However, since double must be aligned on 8-byte boundaries, the extent of this derived datatype is 16, not 12. MPI calls exist for you to get the lb, ub, and extent. Thus, you don't need to worry about how a particular machine or language aligns data in memory.

Here is the syntax for the extent routine:

where

[Table of Contents] [Section 1] [Section 2] [Section 3] [Section 4] [Section 5] [Less Detail]

4. How and When Do I Use Derived Datatypes?

4.1 When to Use

When you want to create a datatype in C or FORTRAN, you do so by declaring the datatype before executing any statements. Your declarations are read by the compiler which sets up storage for your datatype. In contrast, MPI derived datatypes are created at run-time through calls to MPI library routines. Since MPI derived datatypes are often used to send or receive C or FORTRAN datatypes, in the typical scenario, you first declare your C or FORTRAN datatypes. Later, in the execution part of your program between calls to MPI_INIT and MPI_FINALIZE, you create and use your MPI derived datatypes.

4.2 How to Use

Before you can use a derived datatype, you must create it. Here are the steps you take:

  1. Construct the datatype.
  2. Allocate the datatype.
  3. Use the datatype.
  4. Deallocate the datatype.
You must construct and allocate a datatype before using it. On the other hand, once you have it constructed and allocated, you are not required to use or deallocate it.

Let's to through these steps in more detail:

4.2.1 Construct the datatype

As we said above, derived datatypes are datatypes that are built from the basic MPI datatypes. Typemaps are a completely general way of doing this, but they are not very convenient if we have a large number of entries. Fortunately, MPI provides a number of routines to create common datatypes from the basic datatypes without needing to construct a typemap. New datatype definitions are build up from existing datatypes (either derived or basic) using a call, or a recursive series of calls, to the routines described below:

Contiguous:

Calls to MPI_TYPE_CONTIGUOUS produce a new datatype by replicating the existing datatype into contiguous locations.

where

Vector:

Calls to MPI_TYPE_VECTOR, like those to MPI_TYPE_CONTIGUOUS, produce a new datatype by replicating the existing one; however, MPI_TYPE_VECTOR allows for gaps in the displacement. Such gaps are multiples of the extent of the existing datatype.

where

Example:

[IMAGE]

This illustrates a call with count = 2, blocklength = 3, and stride = 5

Try this:

Using paper and pencil, illustrate the call:

MPI_TYPE_VECTOR(2, 4, 4, OLDTYPE, NEWTYPE, MPIERROR)

What does this say about the call to MPI_TYPE_CONTIGUOUS?

Caution

This datatype constructor and the ones described below can be used with allocatable objects (C or F90) provided the entire object is allocated at once. The stride in actual memory between pieces that were allocated at different times cannot be predicted. Thus, to allocate a C matrix for which MPI_TYPE_VECTOR could be used to define a datatype that represents a submatrix, one would allocate an object whose size is the number of rows times the number of columns times the size of a matrix element. An array of pointers to the rows can be set up afterward.

Hvector:

This is like MPI_TYPE_VECTOR, except the displacement is specified in bytes. The C and FORTRAN routines, MPI_Type_hvector and MPI_TYPE_HVECTOR, respectively, are identical to those for MPI_TYPE_VECTOR given above, except that stride is in bytes.

Indexed:

Calls to MPI_TYPE_INDEXED replicates the existing datatype into a sequence of blocks where each block is a concatenation of the existing datatype. Each block can contain a different number of copies and have a different displacement; however, all block displacements are multiples of the existing datatype's extent.

where Hindexed:

This is like MPI_TYPE_INDEXED, except the displacement is specified in bytes. The C and FORTRAN routines, MPI_Type_hindexed and MPI_TYPE_HINDEXED, respectively, are identical to those for MPI_TYPE_INDEXED given above, except that array_of_displacements is in bytes.

Struct:

When you call MPI_TYPE_STRUCT, you can gather a mix of different datatypes scattered at many locations in memory into one datatype that can be used for sending messages. This is the most general datatype and the only one that allows more than one datatype as input. Note that if the input arguments are basic MPI datatypes, the input is just a typemap.

where

If the storage relationships among the elements is determined by the compiler (C struct, F90 sequence derived type, or FORTRAN common block), the byte values for the array_of_displacements can be calculated by the programmer. However, if the elements are independently declared variables or members of an F90 nonsequence derived type, the MPI_ADDRESS function must be used to determine the absolute address of each element for use in the array_of_displacements. When using datatypes containing absolute addresses in the array_of_displacements, the buffer address must be specified as MPI_BOTTOM.

Example:

[IMAGE]

This illustrates a call with:

count = 2
array_of_blocklengths[0] = 1
array_of_types[0] = MPI_INT
array_of_blocklengths[1] = 3
array_of_types[1] = MPI_DOUBLE

Caution

Derived datatypes defined using absolute displacements should NOT contain variables that aren't static (e.g., they are on the data stack) unless the datatype is defined and used within a single call to the subroutine where the variables are declared. The reason for this is that unless the context is identical, the stack pointer will have a different value upon reentry into the subroutine and the absolute addresses determined earlier will be invalid. At CTC, FORTRAN variables are not static unless the user specifies the STATIC attribute in the source file or the -qsave option at compile time.

Try this:

Using paper and pencil, illustrate the call MPI_TYPE_STRUCT where:

count = 2,
array_of_blocklengths[0] = 1,
array_of_types[0] = the newtype illustrated above,
array_of_blocklengths[1] = 2, and
array_of_types[1] = MPI_INT.

4.2.2 Allocate the datatype

A constructed datatype must be committed to the system before it can be used in a communication. The constructed datatype is committed with a call to MPI_TYPE_COMMIT. (There is no need to commit basic datatypes; they are pre-committed.) It can then be used in any number of communications. The form of MPI_TYPE_COMMIT is:

4.2.3 Use the datatype

Derived datatypes can be used in all send and receive operations. You simply use the handle to the derived datatype as an argument in a send or receive operation instead of a basic datatype argument. Here is a sample C code segment: 

MPI_Type_vector(count, blocklength, stride, oldtype, &newtype);
MPI_Type_commit (&newtype);
MPI_Send(buffer, 1, newtype, dest, tag, comm);

What happens if you are using a derived datatype and the count in MPI_SEND is greater than one? Happily, it's just as you would expect: MPI_SEND acts as if it were passed a new datatype that is count concatenations of datatype.

4.2.4 Deallocate the datatype

Finally, there is a complementary routine to MPI_TYPE_COMMIT, namely, MPI_TYPE_FREE, which marks a datatype for deallocation. The form of MPI_TYPE_FREE is:

Any datatypes derived from a freed datatype are unaffected when it is freed, as are any communications that are using the freed datatype at the time of the freeing. datatype is both an input and output argument. It is returned as MPI_DATATYPE_NULL.

4.3 Matching Rules

[Table of Contents] [Section 1] [Section 2] [Section 3] [Section 4] [Section 5] [Less Detail]

5. Key Points

[Table of Contents] [Section 1] [Section 2] [Section 3] [Section 4] [Section 5] [Less Detail]

References

General

Specific

[FAQ] Frequently Asked Questions

[Example] A sampling of programs available on the Web that illustrate commands covered in this module.

[Quiz] Take a multiple-choice quiz on this material, and submit it for grading.

[Evaluation] Please complete this short evaluation form. Thank you!

[Table of Contents] [Section 1] [Section 2] [Section 3] [Section 4] [Section 5] [Less Detail]

[Copyright Statement] [Feedback]