Ivan's wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
# Prefix reductions (MPI)
A prefix reduction (scan) turns an array of N values into N partial results, where each output element is the reduction of all input elements up to that index. The sequential exclusive prefix sum:

```c
int offsets[N];
offsets[0] = 0;
for (int i = 1; i < N; i++)
    offsets[i] = offsets[i-1] + counts[i-1];
```

In a distributed program, each process holds one value and needs its write offset into a global array — the sum of counts for all preceding processes. `MPI_Exscan` computes exactly that: each process receives the reduction of all values from ranks strictly less than its own, so rank 0 receives no meaningful value. `MPI_Scan` is the inclusive variant: each process receives the result including its own.

```c
int local_count = count_my_elements();
int offset = 0;
MPI_Exscan(&local_count, &offset, 1, MPI_INT, MPI_SUM, MPI_COMM_WORLD);
// rank 0: offset stays 0; all others: offset = sum of counts for ranks < me
// now write local_count elements starting at position offset in the global array
```

The operator must be associative but need not be commutative, since the ordering is defined by rank. Both have non-blocking variants `MPI_Iscan` and `MPI_Iexscan` in MPI-3.