Making MPICH Thread Safe

From Mpich
Jump to: navigation, search

Thread Safety

In a multi-threaded MPI program, care must be taken to ensure that updates and accesses to data structures shared between threads in the same process. This applies to both the use of multiple threads within the MPI implementation, e.g. to support background processing of messages, and to user-threads that make MPI calls (the MPI_THREAD_MULTIPLE case).

The classical approach to thread-safety is to establish critical sections around the parts of the code that must be executed atomically. This is often done using locks, but other approaches are possible. In some cases, it is possible to use careful coding or special processor instructions to ensure that an update is atomic (for example, an atomic increment or compare-and-swap). A major consideration is what granularity of critical section (or of locks, which are more general) to use.

In the implementation of MPICH, two different approaches are used for mediating the access to shared structures.

  1. Critical sections. These are used to guard shared data structures and system calls, such as queue updates and reads and writes to sockets.
  2. Atomic update and access. These are used for simple operations that can be implemented with processor-atomic operations. This is usually applied to reference count updates that only require an integer update.
  3. Memory consistency. There are some issues that need to be considered, particularly when narrowing the scope of the critical sections.

In addition, there are two special cases that need to be handled efficiently.

  1. One-time Initialization
  2. The Progress Engine

Finally, in order to provide a common set of routines for basic thread operations, there are a number of common thread routines.

To simplify the source code, macros are used for both atomic updates and critical sections. When MPICH is configured for single-threaded operation (both MPI_THREAD_SERIALIZED or lower and only one thread used by the MPICH implementation itself), these macros turn into the appropriate single threaded code. Specifically, in the single-threaded case, the atomic update and reference operations use non-atomic (and less expensive) versions and the critical section macros turn into no-ops.

Critical Sections

This document is obsolete. While there is much good stuff in this document, the MPICH code base makes use of a variation on the macros and definitions in this document. In particular, all critical sections are now marked with macros that take the name of the critical section and a reference to the object as arguments, permitting a single set of macros to implement different granularity of thread safety. This version describes the code used in release 1.0.7, but not the version in the thread branch. That branch will soon be merged into the main version.

The new form of the macros uses these names to delimit critical sections

MPIU_THREAD_CS_ENTER(name,context)
Enter a critical section called name for a particular context (e.g., communicator)
MPIU_THREAD_CS_EXIT(name,contest)
Exit the named critical section.

These are sufficient for most uses that require atomic access or update. There are two other major needs: lightweight atomic updates, such as reference counters, and sharing of a resource. For lightweight atomic updates, there are the atomic operations and the reference-count update macros. For resources, the following is a proposed design.

MPIU_THREAD_RESOURCE_ENTER(csname,resourcename)
Gain exclusive access to a resource associated with a critical section names csname. Release the critical section.
MPIU_THREAD_RESOURCE_EXIT(csname,resourcename)
Release the resource, re-entering the critical section
MPIU_THREAD_RESOURCE_POKE(csname,resourcename)
Provides a hook to poke or wakeup the thread that has acquired the resource. For example, in the current MPICH sock implementation, there is an FD that is local to the process; each of the threads, by writing a byte to this fd, cause the thread that is doing a poll on the fds to wake up. By abstracting this concept, parts of the implementation that may need to cause the thread holding the resource to wake up can do so, allowing that thread to use blocking operations.


Please edit this file and bring it up-to-date (rather than creating a new version).


Old text begins here.

There are two obvious approaches to thread safety in MPICH: (1) the single, global critical section and (2) finer grain (object- or module-based) access. Because we want to experiment with and understand the different approaches, we propose to use the following sets of macros to describe thread-synchronization points within MPICH:

  1. A single critical section. This is often the first approach used in a thread-safe application, and has the advantage of simplicity. The disadvantage is that, as a coarse-grain approach, threads that are in fact using distinct data structures may be waiting on the global critical section when they don't need to. For this approach, there are two major macros:
    MPIU_THREAD_SINGLE_CS_ENTER(msg)
    Enter the single critical section
    MPIU_THREAD_SINGLE_CS_EXIT(msg)
    Exit the single critical section
    The msg argument is a string (it may be empty) that may be used when debugging.
    This is one special case that needs to be considered which is the handling of the creation of error codes. MPICH provides instance-specific error codes; these require use of a shared data structure. Rather than force all code to be within a critical section in case an error is discovered, even code that otherwise would not need a critical section, such as code that only references data such as MPI_Comm_rank, the error code routines have their own thread-safe support. This will be discussed later.
  2. Per module and/or per object critical sections (and atomic update operations). This is a more complex approach but it can offer greater performance by avoiding unnecessary critical sections and by allowing separate threads to run concurrently when possible. For this approach, there are two sets of macros:
    MPIU_THREAD_<class>_CS_ENTER[(obj)]
    Enter the critical section for the class. Depending on the class, this may be a per-class or per object within the class operation. In the latter case, the object is passed to the macro.
    MPIU_THREAD_<class>_CS_EXIT[(obj])
    Exit the critical section for the class or the object within the class.

The classes still need to be defined, but they may include:

  • COLL (collective)
  • COMM (communication, including progress)
  • MEM (memory and object allocation/deallocation)
  • LIST (reference or update to a list of objects)

See Analysis of Thread Safety Needs of MPI Routines for one set of possible classes.

One special object pointer is &MPIR_Process; this provides a "master lock" that can be used when there is no relevant object.

When one of these two approaches is chosen, the macros for the other are defined as empty. This allows us to annotate the source code with detailed information about the needed thread synchronization without requiring separate source code versions or complex ifdefs.

In addition to these two macros to enter and exit the critical section, additional macros are needed to aid in declarations and initialization:

MPIU_THREAD_SINGLE_CS_DECL
Provide the declarations needed for the single critical section. This should be placed where it is globally accessible (e.g., within the MPIR_Process structure).
MPIU_THREAD_SINGLE_CS_INITIALIZE
Initialize the single critical section. This should appear in the MPI_Init/MPI_Init_thread routines.
MPIU_THREAD_SINGLE_CS_FINALIZE
Finalize the single critical section. This should appear in the MPI_Finalize routine.
MPIU_THREAD_SINGLE_CS_ASSERT_WITHIN(msg)
This is a special version of an assert that can be used to check that the critical section is indeed held.

For the finer-grain approach, these are the macros:

MPIU_THREAD_<class>_CS_DECL
Provide the declarations needed. This should either be within the object declaration (when the granularity is per object) or in the MPIR_Process structure (when the granularity is per class).
MPIU_THREAD_<class>_CS_INITIALIZE[(obj)]
Initialize the critical section.
MPIU_THREAD_<class>_CS_ASSERT_WITHIN[(obj)]
This is a special version of an assert that can be used to check that the critical section is indeed held.

One possible problem with threaded code that uses more than on critical section is deadlock caused when two or more threads both need to acquire two or more critical sections, and each acquire a critical section needed by the other, causing them to wait for the other to release the critical section. This is called a deadly embrace.

The following is a possible way to help debug these cases. For example, each critical section could increment a "critical section" counter (in thread-private storage); if this value exceeds one, then an error can be raised. A more sophisticated approach could define a "priority"; a low priority critical section may not be held when attempting to acquire a higher priority critical section. These checks would be enabled when testing and debugging but during performance runs. This does not change the API described in this note; it only changes the implementation.

There are two other major classes of operations that must be handled in a thread safe way: initialization and reference count updates. In addition, there is code that is needed only when thread-support is included.

One-time Initialization

Some routines need to be initialized the first time they are executed. Initializations are often controlled by a flag that is cleared once the initialization is completed. In a single-threaded case, the code is often simply

static int initNeeded = 1;
...
if (initNeeded) {
   code to initialize
   initNeeded = 0;
}

In the multi-threaded case, it is possible that two threads will enter the if (initNeeded) at nearly the same time. We could avoid this by putting the test on initNeeded within a critical section, but then every entry into this routine will need to acquire and release the critical section, a potentially costly operation. A very simple approach is to use two tests, with the second inside a critical section:

static volatile int initNeeded = 1;
...
if (initNeeded) {
    MPIU_THREAD_SINGLE_CS_ENTER("");
    if (initNeeded == 1) {
       code to initialize
       MemoryBarrier;
       initNeeded = 0;
    }
    MPIU_THREAD_SINGLE_CS_EXIT("");
}

However, the full generality of a critical section is not needed, so in some cases, an approach that uses two test variables is used, with the first (fast) test checking the initNeeded flag and a second test or an atomic fetch and increment on the flag. For example,

    static volatile int initNeeded = 1;
    static volatile int initLock = 0;
    ...
    if (initNeeded) {
        MemoryBarrier;
        AtomicFetchandIncrement(initLock);
        if (initLock == 0) {
           code to initialize
           MemoryBarrier;
           initNeeded = 0;
        }
        else {
             /* Spin, waiting for other thread to init */
             while (initNeeded) ;
        }
    }

Note that several MemoryBarriers are needed, and that some mechanism (here an atomic fetch-and-increment) is needed to make sure only one thread performs the initialization. The positive feature of this is that once the initialization is performed, no costly thread locks or atomic memory operations are required. Because it can be tricky to get the thread-safe features (such as the memory barriers correct) and because the single-threaded case does not require anything this complex, there are special macros for this case:

   MPIU_THREADSAFE_INIT_DECL(var);
   ...
   MPIU_THREADSAFE_INIT_STMT(var,code to initialize)

if the code to initialize is simple (no commas) or the following for more complex initialization code:

   MPIU_THREADSAFE_INIT_DECL(var);
   ...
   if (var) {
       MPIU_THREADSAFE_INIT_BLOCK_BEGIN(var);
       code to initialize
       MPIU_THREADSAFE_INIT_CLEAR(var);
       MPIU_THREADSAFE_INIT_BLOCK_END(var);
   }

The MPIU_THREADSAFE_INIT_CLEAR is important; it ensures that the necessary memory barrier can be issued before clearing the variable that controls the initialization check.

To understand these macros, the following table shows how each may be implemented in the context of the example above:

MPIU_THREADSAFE_INIT_DECL(var); static volatile int var=1;
if (var) { if (var) {
MPIU_THREADSAFE_INIT_BLOCK_BEGIN(var); MPIU_THREAD_SINGLE_CS_ENTER("");
code to initialize code to initialize
MPIU_THREADSAFE_INIT_CLEAR(var); var=0;
MPIU_THREADSAVE_INIT_BLOCK_END(var); MPIU_THREAD_SINGLE_CS_EXIT("");
} }

An example where this is needed is in the default version of MPID_Wtick, where the value of the clock tick is determined on the first call to the routine.

Atomic Reference and Update

In some cases, a simple atomic reference or update is needed. There are three cases:

  1. Reference is outside of all critical sections
  2. Reference is within the single critical section case, but outside of the finer grain critical sections.
  3. Reference is within both the coarse-grain and fine-grain critical sections.

Different implementation are needed for each of these cases.

However, before we further pursue this approach, we will determine whether there is a real need for it, based on our experiences with the two approaches to critical sections in the code. If it turns out that all (or even most) of the atomic references and updates are already within a critical section, we won't need to use this approach. Note that one place where we can use this is in the creation on instance-specific error codes.

Fortunately, the first case is rare and can in fact be defined away by requiring that all such updates be moved within the single critical section. Thus, we need only distinguish between the cases where we are within the single critical section but outside of the particular object or module's critical section and where we are within the critical section.

The following macros should be used to update the reference count for an MPIU object (e.g., an MPI communicator or group) in the second case: within the single critical section but outside of the object's critical section:

MPIU_Object_set_ref( MPIU_Object * )
MPIU_Object_add_ref( MPIU_Object * )
MPIU_Object_release_ref( MPIU_Object *, int *inuse )

Normally, the MPIU_Object_add_ref is used to increase the reference count and MPIU_Object_release_ref is used to decrease the reference count and in addition sets the flag inuse to true if the reference count is positive. MPIU_Object_set_ref is use to initialize the reference counter. For the third case, we could simply reference the object directly, since we would be sure that the reference was within the critical section. However, to emphasize the need for an atomic update, we define a similar set of macros:

MPIU_Object_In_<class>_set_ref( MPIU_Object * )
MPIU_Object_In_<class>_add_ref( MPIU_Object * )
MPIU_Object_In_<class>_release_ref( MPIU_Object *, int *inuse )

These make it easy to track changes to the object's reference counts by changing the definitions of these macros.

Handling Thread-Only Code

In some cases, there is code that is used only when thread support is enabled. We define two cases. For the general case, we define a simple name on which we can test:

#ifdef MPICH_IS_THREADED
   MPIU_THREAD_CHECK_BEGIN
...
   MPIU_THREAD_CHECK_END
#endif

The two lines, MPIU_THREAD_CHECK_BEGIN and MPIU_THREAD_CHECK_END, are used in executable code only (not in a declaration) to provide a hook to allow runtime checks on whether the MPICH implementation is multi-threaded. This will allow us to support running with a lower level of thread safety (e.g., MPI_THREAD_FUNELLED) than the library supports, and thus allow us to perform experiments on the overhead of adding thread-safety support.

For simple blocks of code, we can avoid the use of the ifdef by using a macro that is defined to give its argument only if MPICH_IS_THREADED is defined:

MPIU_ISTHREADED(statement);

In most of MPICH, only at the thread level of MPI_THREAD_MULTIPLE is thread-related code needed, and thus MPICH_IS_THREADED is only defined for MPI_THREAD_MULTIPLE. There are exactly two places where special thread code is needed for MPI_THREAD_SERIALIZED; these are in MPI_Is_thread_main and in MPI_Init_thread. In these cases, the test that should be used is

#if MPICH_THREAD_LEVEL >= MPI_THREAD_SERIALIZED
   ...
#endif

Memory Consistency

When one thread updates two or more memory locations, neither the underlying programming language (except for some very recent, thread-aware languages) nor the processor hardware guarantees that all other threads will see the updates in the same order. Even in a cache-coherent system, variables that are not defined as volatile in C may be stored in register and if the code uses the value in register instead of loading from memory, changes to that variable may by another thread will not be seen.

Implementations of critical sections take care of everything except the volatile issue by ensuring that all memory operations have completed; for example, it may issue a memory fence instruction on processors that re-order memory loads and stores to force all pending memory updates to complete. When writing code that avoids using critical sections, you should consider whether volatile or a memory fence or some similar operation may be needed. The current macros described here do not include a memory fence because, at least at the level of the single critical section code, we're not convinced one is needed. In other words, where such a fence may be needed, there is already a critical section that ensures the memory consistency. Note that the atomic update operations may need a memory fence within their implementation.

The Progress Engine

The progress engine is responsible for advancing communication. There are two natural approaches for implementing a thread-safe progress engine:

  1. A separate thread is responsible for running the progress engine. Typically, other (i.e., user) threads enqueue requests to this thread.
  2. Any thread may invoke the progress engine; there is no separate thread that runs the progress engine.

A key requirement on the progress engine in both of these cases is that the thread running the progress engine must not block all threads when it makes a blocking system call. This means that it must release any critical sections it may hold before calling the blocking system call, and it must reacquire the critical sections when the blocking system call returns.

To handle this case, the progress engine provides a special API made up of a set of routines that are used to invoke the progress engine. These apply either to the single critical section or to the finer-grain communication class critical section.

MPID_Progress_start(state)
Enter a state where only the calling thread will modify communication objects (e.g., request completion flags will not change)
MPID_Progress_wait(state)
Wait for any event handled by the progress engine. This allows the calling thread to block rather than spin-wait.
MPID_Progress_test()
A nonblocking version of MPID_Progress_wait
MPID_Progress_end(state)
Exit the state begun with MPID_Progress_start
MPID_Progress_poke()
Give the progress engine an opportunity to run without invoking MPID_Progress_start.

Here is a sample of how the Progress routine API is used to implement MPI_Wait:

MPI_Wait( ... )
{
    while (request->busy) {
        MPID_Progress_start( state );   // Notes that we are about to
                                        // check ready flags.  No busy 
                                        // flags will be cleared
        if (request->busy) {
            MPID_Progress_wait( state );
        }
        else {
            MPID_Progress_end();
        }
    }
}

Note: this is drawn from the old MPICH design document and may not reflect the current implementation.

The progress routines MPID_Progress_start and MPID_Progress) end calls are analogous to the critical section enter and exit macros described above. The MPID_Progress_wait is a special call that allows the progress engine to release the progress critical section, permitting a different thread to complete a progress call. This call only returns when the progress engine has detected some progress.

Internally to the implementation of the progress engine, additional routines are needed to manage the coordination between different threads that call the progress engine.

In the single-threaded case, the progress start and end calls may be macros that expand into empty statements (thus avoiding the cost of a function call).

Note: The interface to the progress engine may change to reduce the latency of common cases, for example, by saying "wait until this request or array of requests is complete".

Error Codes

When MPICH is configured to produce instance-specific error messages (this is the default), the messages are stored in a ring of message buffers. The index into this ring is computed with an atomic fetch and increment operation (mod the ring size). To avoid any possibility of conflict with thread locks in other parts of the code, the error code and message routines use their own thread-safe macros, even if the rest of the MPICH code is using a single critical section.

In order to make the code as robust as possible, the error code and message routines attempt to use an atomic fetch and increment operation if one is available for the processor. If not, a standard thread mutex (lock) is used; this lock is separate from any lock used in any other part of the code. Note that since this code is not performance critical but must be robust, the design here aims for simplicity over performance.

Rationales

This section contains a discussion of the rationales for some of the choices.

Why a single ifdef test for thread support?

In order to ensure that the source code remains consistent, it is important to establish some clear coding guidelines. For example, we want to avoid something like the following:

#ifdef thread_level > MPI_THREAD_SINGLE && MPICH_IMPLS_THREADS
...
#endif 
... many lines of code
#ifdef thread_level > MPI_THREAD_SINGLE
...
#endif 

where the second ifdef is missing the second test.

Why not include the if in the one-time initialization macros?

An alternate design for the one-time initialization macros could simply use

MPIU_THREADSAFE_INIT_BLOCK_ENTER(needsInit);
   ... perform initialization action
MPIU_THREADSAFE_INIT_BLOCK_END(needsInit);

but this requires familiarity with these macros when browsing the code. By keeping the initial if check, the condition under which the code is active is clear, even if this requires the use of an additional MPIU_THREADSAFE_INIT_CLEAR macro.

Common Thread API

In order to simplify the MPICH code, there is an "MPICH" API for thread utilities.

MPID_Thread_tls_get
Access thread-private storage ()
MPID_Thread_tls_set
Set a value in thread-private storage ()
MPE_Thread_self
Return the id of the thread
MPE_Thread_same
Compare two thread ids and indicate whether the threads are the same. This allows the thread-id to be an arbitrary value.
MPE_Thread_yield
Allow this thread to be de-scheduled.
MPE_Thread_mutex_create
Create a thread mutex
MPE_Thread_mutex_lock
Lock a thread mutex
MPE_Thread_mutex_unlock
Unlock a thread mutex
MPE_Thread_mutex_destroy
Destroy a thread mutex
MPE_Thread_tls_get
Access thread-private storage. tls stands for "thread local storage" ()
MPE_Thread_tls_set
Set a value in thread-private storage ()

Why are there two sets of definitions for the reference count macros?

If the operation is not within a critical section, it will be implemented either with a memory-atomic processor instruction or by acquiring and releasing a thread lock. Both of these are more expensive than the simple C code (e.g., an atomic memory increment of the variable a is more expensive than a simple a++;).