Scan

The scan operation is similar to the reduce operation (accumulating the elements of a collection into a single result). The difference from reduce is that in scan, the last process in the communicator holds the final result. In essence, scan is the reverse of reduce. Additionally, each process has a partially accumulated result, meaning process 0 has the value P0, process 1 has the value P0 + P1, process 2 has the value P0 + P1 + P2, and so on.

Example:

l = [1, 2, 3, 4, 5, 6]
op = +
result = 1 + 2 + 3 + 4 + 5 + 6 = 21

Pași:
[1, 2, 3, 4, 5, 6]
[1, 3, 3, 4, 5, 6]
[1, 3, 6, 4, 5, 6]
[1, 3, 6, 10, 5, 6]
[1, 3, 6, 10, 15, 6]
[1, 3, 6, 10, 15, 21] -> the result is 21

Here are attached slides that provide detailed explanations of the steps involved in implementing the scan operation: slides

Pseudocode:

for (step = 1; step < nr_processes; step *= 2)
	if (rank + step < nr_processes)
		send to process with rank [rank + step]
        if (rank - pas >= 0)
                receive from process with rank [rank - step]
                add