Tracing MPI Communication Patterns

1. The MPI Execution Model: SPMD

MPI programs typically follow the Single Program, Multiple Data (SPMD) model. This means you write one C++ source file, compile it once, and then use a special launcher like mpirun to start multiple copies of your program simultaneously. Each running copy is a separate process.

While all processes run the same code, they are not identical. Each process has a unique ID, called its rank, from 0 to N-1, where N is the total number of processes. A process uses its rank to determine its specific role and what data it should work on.

The fundamental MPI functions for this are:

• MPI_Init(): Initializes the MPI environment. Must be called at the beginning.
• MPI_Comm_size(): Gets the total number of processes (N).
• MPI_Comm_rank(): Gets the current process's unique rank (from 0 to N-1).
• MPI_Finalize(): Cleans up the MPI environment. Must be called at the end.

Let's start with a foundational video that covers these core concepts.

As you saw, the key to tracing MPI code is to think from the perspective of a single process, identified by its rank, executing the same block of code as all other processes.

2. Point-to-Point Communication and Deadlock

Processes exchange data using point-to-point communication. The most basic pairing is a blocking MPI_Send and MPI_Recv.

• MPI_Send: Sends data from a buffer in the current process to a specified destination process.
• MPI_Recv: Waits to receive data from a specified source process and stores it in a buffer.

These operations are blocking.

• MPI_Recv will wait until the message arrives.
• MPI_Send will often wait until the corresponding MPI_Recv has been posted by the destination process. This ensures the data has been safely received before the sending process continues (and potentially modifies its send buffer).

This blocking behavior is the source of a classic parallel programming problem: deadlock. If two processes are both waiting for each other to do something, they will wait forever.

Consider two processes, Rank 0 and Rank 1, wanting to exchange data.

Deadlocking Code:

// Executed by both Rank 0 and Rank 1
int my_rank, other_rank;
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
other_rank = 1 - my_rank;

// Both processes try to send first.
MPI_Send(/* ... */, other_rank, /* ... */); // Rank 0 sends to 1, Rank 1 sends to 0
MPI_Recv(/* ... */, other_rank, /* ... */); // Both now wait for a message that will never be sent

In this scenario, Rank 0 is blocked on MPI_Send, waiting for Rank 1 to post a receive. But Rank 1 is also blocked on its own MPI_Send, waiting for Rank 0 to post a receive. They are stuck in a deadly embrace.

Correct Code:
The solution is to break the symmetry. One process sends first, while the other receives first.

int my_rank;
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);

if (my_rank == 0) {
    MPI_Send(/* to Rank 1 */);
    MPI_Recv(/* from Rank 1 */);
} else { // my_rank == 1
    MPI_Recv(/* from Rank 0 */);
    MPI_Send(/* to Rank 0 */);
}

Now, the communication is ordered. Rank 0 sends, Rank 1 receives it, then Rank 1 sends, and finally Rank 0 receives that. No deadlock.

Let's trace a slightly more complex example: a "round-robin" or ring communication pattern.

Tracing a Ring Communication

Imagine 4 processes arranged in a logical ring: 0 -> 1 -> 2 -> 3 -> 0. Each process p will send a value to process (p+1)%4. To avoid deadlock, we can't have everyone send at once. A common strategy is to have even-ranked processes send first while odd-ranked processes receive, and then they swap roles.

Let's trace the state with 4 processes (nprocs=4), where each process p wants to send the value p*10 to its right neighbor (p+1)%4.

Code Logic:

// Simplified logic
int my_rank = /* ... */;
int my_val = my_rank * 10;
int received_val;
int next_rank = (my_rank + 1) % nprocs;
int prev_rank = (my_rank - 1 + nprocs) % nprocs;

if (my_rank % 2 == 0) { // Even ranks
    MPI_Send(&my_val, 1, MPI_INT, next_rank, 0, MPI_COMM_WORLD);
    MPI_Recv(&received_val, 1, MPI_INT, prev_rank, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
} else { // Odd ranks
    MPI_Recv(&received_val, 1, MPI_INT, prev_rank, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
    MPI_Send(&my_val, 1, MPI_INT, next_rank, 0, MPI_COMM_WORLD);
}

Trace:

1. Initial State:

   • Rank 0: my_val = 0, next = 1, prev = 3
   • Rank 1: my_val = 10, next = 2, prev = 0
   • Rank 2: my_val = 20, next = 3, prev = 1
   • Rank 3: my_val = 30, next = 0, prev = 2

2. Phase 1: Even ranks send, Odd ranks receive.

   • Rank 0 (even): Executes MPI_Send of value 0 to Rank 1.
   • Rank 2 (even): Executes MPI_Send of value 20 to Rank 3.
   • Rank 1 (odd): Executes MPI_Recv from Rank 0. It receives 0. Its received_val becomes 0.
   • Rank 3 (odd): Executes MPI_Recv from Rank 2. It receives 20. Its received_val becomes 20.
   • At the end of this phase, the sends and receives are complete.

3. Phase 2: Even ranks receive, Odd ranks send.

   • Rank 1 (odd): Now executes MPI_Send of its my_val (10) to Rank 2.
   • Rank 3 (odd): Now executes MPI_Send of its my_val (30) to Rank 0.
   • Rank 0 (even): Now executes MPI_Recv from Rank 3. It receives 30. Its received_val becomes 30.
   • Rank 2 (even): Now executes MPI_Recv from Rank 1. It receives 10. Its received_val becomes 10.

4. Final State:

   • Rank 0: my_val = 0, received_val = 30
   • Rank 1: my_val = 10, received_val = 0
   • Rank 2: my_val = 20, received_val = 10
   • Rank 3: my_val = 30, received_val = 20

Each process has successfully received the value from its predecessor in the ring without causing a deadlock.

3. Collective Communication

While point-to-point communication is flexible, many parallel algorithms use standard communication patterns that involve all processes. MPI provides a rich set of collective operations for these patterns. They are not only convenient but also highly optimized.

A key rule for collectives is that all processes in the communicator must call the same collective function.

Let's trace the execution of a program that uses collectives to perform a parallel sum reduction. This is a very common pattern: an array of numbers is distributed among processes, each process sums its local portion, and then the local sums are combined to get a global total.

Tracing a Sum Reduction

Let's trace the logic from the video with a concrete example. Assume we have 4 processes and Rank 0 starts with an array of 8 integers: data = [10, 20, 30, 40, 50, 60, 70, 80]. The chunk_size will be 8 / 4 = 2.

1. MPI_Scatter: Rank 0 "scatters" the data array. Each process receives a unique chunk of size 2 into its recv_buffer.

• Initial State:
  • Rank 0 data: [10, 20, 30, 40, 50, 60, 70, 80]
• State after MPI_Scatter:
  • Rank 0 recv_buffer: [10, 20]
  • Rank 1 recv_buffer: [30, 40]
  • Rank 2 recv_buffer: [50, 60]
  • Rank 3 recv_buffer: [70, 80]

2. Local Computation: Each process computes the sum of its recv_buffer and stores it in a local_result variable.

• State after local computation:
  • Rank 0 local_result: 10 + 20 = 30
  • Rank 1 local_result: 30 + 40 = 70
  • Rank 2 local_result: 50 + 60 = 110
  • Rank 3 local_result: 70 + 80 = 150

3. MPI_Reduce: All processes provide their local_result. MPI combines them using the MPI_SUM operation and places the final answer into the global_result variable on the root process (Rank 0).

• State after MPI_Reduce:
  • Rank 0 global_result: 30 + 70 + 110 + 150 = 360
  • Rank 1, 2, 3 global_result: Unchanged/uninitialized. Only the root process receives the final result.

If the goal were to have all processes know the final sum, we would use MPI_Allreduce.

Conclusion

Today we explored the distributed-memory paradigm of MPI. Unlike OpenMP where threads implicitly share data, MPI processes operate in isolation and must explicitly communicate. Tracing MPI code requires you to adopt the mindset of a single process, keeping track of its rank, its local data, and the messages it sends and receives.

Key Takeaways:

• SPMD Model: MPI programs consist of multiple independent processes running the same code, distinguished by their unique rank.
• Point-to-Point Communication: Blocking MPI_Send and MPI_Recv are the fundamental building blocks. Tracing them requires careful attention to the order of operations to identify potential deadlocks.
• Collective Communication: Operations like MPI_Bcast, MPI_Scatter, MPI_Gather, and MPI_Reduce orchestrate communication among all processes. Tracing them involves understanding how they distribute, collect, and compute on data across the entire system.
• Tracing Strategy: For any MPI program, the core task is to track the state of variables within each process, step-by-step, as messages are exchanged.

In our next lesson, we will explore our third and final major parallel architecture: the GPU. You will learn to trace the execution of simple CUDA kernels, tracking values in global and shared memory, which introduces yet another distinct and powerful model of parallel computation.