The next question: where is the data?
In Module 3, every process could calculate its own terms from an index. We shared a single number with MPI_Bcast and combined partial answers with MPI_Reduce. What if the input is an array already held by process 0? Each process needs its own part before it can work.
Today we will divide an array into blocks with MPI_Scatter, work on each block, and collect the pieces with MPI_Gather. This follows the book’s discussion of data distributions and vector addition in §§3.4.6–3.4.8. We will use small arrays so we can inspect every value while we learn what the MPI calls do.
The complete programs are mpi_square_blocks.c and mpi_vector_add.c. We can write them together or download them after class.
Blocks instead of taking turns
The twelve integers 1 through 12 start on process 0. With three processes, give each process four neighboring values:
| Rank | Values it receives | Values after squaring |
|---|---|---|
| 0 | 1, 2, 3, 4 | 1, 4, 9, 16 |
| 1 | 5, 6, 7, 8 | 25, 36, 49, 64 |
| 2 | 9, 10, 11, 12 | 81, 100, 121, 144 |
This is a block distribution. Compare it with the cyclic distribution from our sum and trapezoid examples, where rank 0 took indices 0, 3, 6, 9 and the other ranks took turns.
Before coding: With four processes, which three values would rank 2 receive? What would each process get with just one process?
Scatter one array
Start mpi_square_blocks.c with the usual MPI initialization and rank/size calls. We will use n = 12 and local_n = n / comm_sz. For this first version, n must divide evenly among the processes. The complete code checks this before scattering.
Process 0 fills numbers with 1 through 12. Then every process calls:
MPI_Scatter(numbers, local_n, MPI_INT,
local_numbers, local_n, MPI_INT,
0, MPI_COMM_WORLD);Read it as: “From rank 0’s numbers, send local_n integers to each process; put my block into my local_numbers.” The first block goes to rank 0, the next to rank 1, and so on. Rank 0 participates and receives its own block.
numbers is meaningful only on rank 0. The other processes still pass an array in that position, but MPI ignores it there. Every process gets values in its own local_numbers array. These are copies, not shared memory.
The count is the number sent to each process, not the total array length. With 12 values and four processes, local_n is 3. If rank 2 changes its local copy, rank 0’s original numbers array does not change.
For a four-process run, the root provides 12 elements in total, while each process receives 3. In the call above, both count arguments are 3 because those arguments describe one process’s block.
Work locally, then gather
Each process squares just the values it received:
for (int i = 0; i < local_n; i++) {
local_squares[i] = local_numbers[i] * local_numbers[i];
}Notice the local index starts at 0 on every process. On rank 2 in a four-process run, local_numbers[0] is 7, not 1. The array belongs to that process.
To bring the pieces back to rank 0, every process calls:
MPI_Gather(local_squares, local_n, MPI_INT,
squares, local_n, MPI_INT,
0, MPI_COMM_WORLD);The first count says each process sends local_n integers. The second says the root receives that many from each process. Rank 0 places the blocks in rank order in squares. Only rank 0 has a meaningful complete squares array after the call.
Complete program
#include <stdio.h>
#include <mpi.h>
int main(void) {
int my_rank, comm_sz;
MPI_Init(NULL, NULL);
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
MPI_Comm_size(MPI_COMM_WORLD, &comm_sz);
const int n = 12;
if (n % comm_sz != 0) {
if (my_rank == 0) {
printf("Use 1, 2, 3, 4, 6, or 12 processes.\n");
}
MPI_Finalize();
return 1;
}
int local_n = n / comm_sz;
int numbers[12];
int squares[12];
int local_numbers[12];
int local_squares[12];
if (my_rank == 0) {
for (int i = 0; i < n; i++) {
numbers[i] = i + 1;
}
}
MPI_Scatter(numbers, local_n, MPI_INT,
local_numbers, local_n, MPI_INT,
0, MPI_COMM_WORLD);
for (int i = 0; i < local_n; i++) {
local_squares[i] = local_numbers[i] * local_numbers[i];
}
MPI_Gather(local_squares, local_n, MPI_INT,
squares, local_n, MPI_INT,
0, MPI_COMM_WORLD);
if (my_rank == 0) {
printf("Squares:");
for (int i = 0; i < n; i++) {
printf(" %d", squares[i]);
}
printf("\n");
}
MPI_Finalize();
return 0;
}Compile and try one, three, and four processes:
mpicc -g -Wall -o mpi_square_blocks mpi_square_blocks.c
mpirun -n 1 ./mpi_square_blocks
mpirun -n 3 ./mpi_square_blocks
mpirun -n 4 ./mpi_square_blocksEvery run should print:
Squares: 1 4 9 16 25 36 49 64 81 100 121 144The gathered order is stable because MPI_Gather places rank 0’s block first, rank 1’s block next, and so on. This does not tell us which rank finished computing first.
Try it: Change the local loop so it doubles each number instead. Predict the entire output before compiling. Then restore squaring for the next example.
Follow the book: add two vectors
Vector addition applies the same operation to pairs of array elements. If \(x=[1,2,3]\) and \(y=[10,20,30]\), then \(x+y=[11,22,33]\).
Process 0 starts with both complete arrays. We scatter each input using the same block size. Every process adds its matching local elements. Finally, we gather the local results into z on process 0:
rank 0: full x, full y
│ │
▼ ▼
scatter scatter
│ │
each rank: local_x + local_y → local_z
│
▼
gather into z on rank 0Complete mpi_vector_add.c
#include <stdio.h>
#include <mpi.h>
int main(void) {
int my_rank, comm_sz;
MPI_Init(NULL, NULL);
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
MPI_Comm_size(MPI_COMM_WORLD, &comm_sz);
const int n = 12;
if (n % comm_sz != 0) {
if (my_rank == 0) {
printf("Use 1, 2, 3, 4, 6, or 12 processes.\n");
}
MPI_Finalize();
return 1;
}
int local_n = n / comm_sz;
int x[12], y[12], z[12];
int local_x[12], local_y[12], local_z[12];
if (my_rank == 0) {
for (int i = 0; i < n; i++) {
x[i] = i + 1;
y[i] = 10 * (i + 1);
}
}
MPI_Scatter(x, local_n, MPI_INT,
local_x, local_n, MPI_INT,
0, MPI_COMM_WORLD);
MPI_Scatter(y, local_n, MPI_INT,
local_y, local_n, MPI_INT,
0, MPI_COMM_WORLD);
for (int i = 0; i < local_n; i++) {
local_z[i] = local_x[i] + local_y[i];
}
MPI_Gather(local_z, local_n, MPI_INT,
z, local_n, MPI_INT,
0, MPI_COMM_WORLD);
if (my_rank == 0) {
printf("x + y:");
for (int i = 0; i < n; i++) {
printf(" %d", z[i]);
}
printf("\n");
}
MPI_Finalize();
return 0;
}mpicc -g -Wall -o mpi_vector_add mpi_vector_add.c
mpirun -n 4 ./mpi_vector_addExpected output:
x + y: 11 22 33 44 55 66 77 88 99 110 121 132Why is there no MPI_Reduce? We need all twelve separate answers, in order. A sum reduction would combine them into one number and lose those individual values.
What if twelve does not divide evenly?
Try the four-process example on paper with five processes. Twelve divided by five leaves a remainder. The equal-block calls above cannot assign all twelve values while giving every rank the same local_n.
Our programs detect this and print a short message rather than silently dropping values. Try:
mpirun -n 5 ./mpi_vector_addAll processes take the same exit path after the check. An invalid configuration does not mean that MPI cannot handle uneven data. Later we can use MPI_Scatterv and MPI_Gatherv to specify different block sizes. For today, use 1, 2, 3, 4, 6, or 12 processes.
Questions to discuss
- How are a block distribution and a cyclic distribution different for twelve values on three processes?
- Why must rank 0 call
MPI_Scattereven though it already has the entire input array? - After scattering, can rank 1 read
numbers[5]from rank 0? Which array should it read instead? - Why does the count in
MPI_Gatherequallocal_n, rather thann? - Why do we gather the vector result instead of reducing it?
- What happens to the amount of communication if we make the input arrays much larger?
If we have time
- Change
mpi_vector_add.csoy[i] = 100 - i. Predict the first and last values ofzbefore running it. - Print a rank’s
local_xvalues immediately after the first scatter. Output lines from different ranks may arrive in any order; the gathered vector still has a defined order. - Compare
MPI_Gatherwith theMPI_Allgatherdiscussed next in the book. Which processes would receive the complete array with each call?
The arrays here are deliberately tiny. They make ownership and data movement visible; they are not a useful speed benchmark. Once we understand the pattern, we can allocate larger arrays and ask whether the work saved outweighs the cost of moving them.