[MPI] MPI Scan explained

[2024 Summer GeekPie HPC Lecture Notes] Catalog of Notes

• Week 1 Notes
  • Singularity
• Week 2
  • Week 2 Notes
  • MPI Prefix Sum
  • Week 2 HW
    • MPI Matrix Multiplication
    • MPI Scan
• Week 3
  • Notes
    • Profiling
    • Optimization
  • HW
    • CA1 Project 4
    • CUDA Transpose Optimization

定义 Definition

MPI_SCAN(sendbuf, recvbuf, count, datatype, op, comm)
 IN   sendbuf    发送消息缓冲区的起始地址(可变)
 OUT  recvbuf    接收消息缓冲区的起始地址(可变)
 IN   count      输入缓冲区中元素的个数(整型)
 IN   datatype   输入缓冲区中元素的类型(句柄)
 IN   op         操作(句柄)
 IN   comm       通信子(句柄)

int MPI_Scan(void* sendbuf, void* recvbuf, int count,
             MPI_Datatype datatype, MPI_Op op, MPI_Comm comm)

MPI_SCAN(SENDBUF, RECVBUF, COUNT, DATATYPE, OP, COMM, IERROR)
    <type> SENDBUF(*), RECVBUF(*)
    INTEGER COUNT, DATATYPE, OP, COMM, IERROR

MPI_SCAN常用于对分布于组中的数据作前置归约操作.此操作将序列号为0,... ,i(包括i)的进程发送缓冲区的值的归约结果存入序列号为i 的进程的接收消息缓冲区中,这种操作支持的类型、语义以及对发送及接收缓冲区的限制和MPI_REDUCE相同.

MPI_Scan is used to perform an inclusive prefix reduction on data distributed across the calling processes. The operation returns, in the recvbuf of the process with rank i, the reduction (calculated according to the function op) of the values in the sendbufs of processes with ranks 0, …, i (inclusive). The type of operations supported, their semantics, and the constraints on send and receive buffers are as for MPI_Reduce.

人话解释 Explanation

MPI_Scan 指的是，对 每个rank为r的进程，假设sendbuf(r)[i]指的是第 r 个进程的sendbuf[i]，recvbuf(r)[i]类似定义。

对于 i=0...count-1，会有recvbuf(r)[i] = prefix<j=0...r, op>sendbuf(j)[i]，也就是根据进程的 rank，将 sendbuf(0), sendbuf(1) … sendbuf(r) 从前到后以 op 作为算符进行**“前缀和”（前缀op）操作**。

数组形式转化成地址：recvbuf(r)[i] 的地址就是 sizeof(datatype) * i + addr(recvbuf(r))；在 C/CPP 中，recvbuf(r) + i

需要注意的是：

1. 这是对进程组而不是数组本身/序列本身的前缀和
2. op（算符）可能不是交换性的(not commutative)。
3. 这个函数不需要指定收发进程，因为这涉及了所有的进程。
4. sendbuf 可以随进程不同而内容/变量不同；recvbuf也是。

举个例子 Example

对于 rank 为 r 而言sendbuf = [rank, 2*rank, 3*rank]，也就是说，对 rank 是 2 的进程，sendbuf(2) = [2, 4, 6]；对 rank 是 3 的进程，sendbuf(3) = [3, 6, 9]。

我们设定 count 是 3，也就是整个数组的长度。假设有 4 个进程，recvbuf数组的长度也是3，并且初始化为了全 0.

这样调用 MPI_Scan(sendbuf, recvbuf, 3, int, MPI_SUM, MPI_COMM_WORLD) 之后，进程的sendbuf分别是

[0, 0, 0]

[1, 2, 3]

[2, 4, 6]

[3, 6, 9]

随着前缀操作（这里是和），recvbuf 会是：

[0, 0, 0]
	|
	v
[1, 2, 3]
	|
	v
[1+2, 2+4, 3+6]
	|
	v
[1+2+3, 2+4+6, 3+6+9]

我们设定 count 是 2，这样sendbuf(r)[2] 也就是 3*r 这个元素会在操作的时候被忽略掉。

[0, 0, 0]
	|
	v
[1, 2, 0]
	|
	v
[1+2, 2+4, 0]
	|
	v
[1+2+3, 2+4+6, 0]