Bottleneck in Message Scheduling

From HPCBugBase

[edit] Fault Description

In the programming with explicit message passing, inappropriate message scheduling can cause performance bottleneck.

The following pseudo-code demonstrates a problem found in MPI programs with a nearest-neighbor communication pattern. (The variable rank denotes the rank of the process and size denotes the number of processes.)

if (rank != 0) {
    MPI_Ssend ( ..., rank-1, ...);
    MPI_Recv ( ..., rank-1, ...);
}
if (rank != (size-1)) {
    MPI_Recv ( ..., rank+1, ...);
    MPI_Ssend ( ..., rank+1, ...);
}

In this code, each process exchanges a message with its neighbors. The boundaries at process 0 and (size-1) don't wrap around in this case. For example, process 0 communicates with 1, 1 with 0 and 2, 2 with 1 and 3, etc.

The defect is unnecessary interdependency between messages. In fact, only one process pair can send/recv a message at one time in this code, and they are forced to take place strictly in this order.

• rank 1 send - rank 0 recv
• rank 0 send - rank 1 recv
• rank 2 send - rank 1 recv
• rank 1 send - rank 2 recv
• rank 3 send - rank 2 recv
• rank 2 send - rank 3 recv
• ...

As a result, the communication requires O(time) time, where a "correct" solution takes O(1).

Note that in the above example, synchronous send (MPI_Ssend) was used to make the point clear. if the standard send (MPI_Send) is used, we argue that the code has the same defect, but the same type of performance problem may or may not actually occur depending on the message size and the library implementation. The argument is analogous to the one presented in the Potential Deadlock, although the example here doesn't cause a deadlock.

[edit] Statistics (Frequency)

[edit] Other Findings and Contexts