实验一：奇偶排序（odd_even_sort）¶

负责助教：黄书鸿 huangsh19@mails.tsinghua.edu.cn

通过实现奇偶排序帮助熟悉 MPI。在保证正确性的前提下，我们鼓励通过探索不同的并行化策略以优化程序性能。

背景介绍¶

本题的基本要求为使用 MPI 实现奇偶排序算法，并且 MPI 进程 只能向其相邻进程发送消息。

奇偶排序是一种比较排序，它由两个主要阶段组成： 偶数阶段 和 奇数阶段 。在 偶数阶段 中，比较所有相邻元素的(偶数，奇数)索引对，如果存在顺序错误，则将交换元素。类似地，对 奇数阶段 中的 (奇数, 偶数) 索引对重复相同的过程。奇偶排序算法的工作原理是将这两个阶段交替进行，直到每个阶段都不交换元素为止。

为了更好地理解该算法，下面逐步说明了奇偶排序的执行流程：（在以下示例中，我们按升序排序）

【偶数阶段】 满足 (偶数，奇数) 索引的相邻元素组成元素对。

Index    0   1   2   3   4   5   6   7
Value   (6   1) (4   8) (2   5) (9   3)

【偶数阶段】 如果元素对中存在顺序错误，则交换两个元素。

Index    0   1   2   3   4   5   6   7
Value   (1   6) (4   8) (2   5) (3   9)

【奇数阶段】 满足 (奇数，偶数) 索引相邻元素被组成元素对。

Index    0   1   2   3   4   5   6   7
Value    1  (6   4) (8   2) (5   3)  9

【奇数阶段】 如果元素对中存在顺序错误，则交换两个元素。

Index    0   1   2   3   4   5   6   7
Value    1  (4   6) (2   8) (3   5)  9

交替运行 偶数阶段 和 奇数阶段，直到两个阶段都 没有元素交换。

接下来，提供一种并行化的奇偶排序思路：（在以下示例中，我们按升序排序）

进程内排序。

Process     0         1         2         3          4           5          6           7
Value   |6 8 3 5| |9 4 1 7| |8 2 1 7| |3 5 2 9| |8 11 4 29| |34 1 4 56| |5 7 6 11| |10 9 5 2| （排序前）
Value   |3 5 6 8| |1 4 7 9| |1 2 7 8| |2 3 5 9| |4 8 11 29| |1 4 34 56| |5 6 7 11| |2 5 9 10| （排序后）

【偶数阶段】 满足 (偶数，奇数) 索引的相邻进程组成进程对。

Process      0         1           2         3            4           5            6          7
Value   (|3 5 6 8| |1 4 7 9|) (|1 2 7 8| |2 3 5 9|) (|4 8 11 29| |1 4 34 56|) (|5 6 7 11| |2 5 9 10|)

【偶数阶段】 如果偶数进程的最大值大于奇数进程的最小值，则合并、排序两个进程的序列并重新分配至进程中（元素交换）。

Process     0           1          2         3           4           5             6          7
Value   (|1 3 4 5   6 7 8 9|) (|1 2 2 3   5 7 8 9|) (|1 4 4 8   11 29 34 56|) (|2 5 5 6   7 9 10 11|) （合并排序）
Value   (|1 3 4 5| |6 7 8 9|) (|1 2 2 3| |5 7 8 9|) (|1 4 4 8| |11 29 34 56|) (|2 5 5 6| |7 9 10 11|) （重新分配）

【奇数阶段】 满足 (奇数，偶数) 索引的相邻进程组成进程对。

Process     0          1         2           3         4             5           6           7
Value   |1 3 4 5| (|6 7 8 9| |1 2 2 3|) (|5 7 8 9| |1 4 4 8|) (|11 29 34 56| |2 5 5 6|) |7 9 10 11|

【奇数阶段】 如果奇数进程的最大值大于偶数进程的最小值，则合并、排序两个进程的序列并重新分配至进程中（元素交换）。

Process     0          1         2           3         4           5           6             7
Value   |1 3 4 5| (|1 2 2 3   6 7 8 9|) (|1 4 4 5   7 8 8 9|) (|2 5 5 6   11 29 34 56|) |7 9 10 11| （合并排序）
Value   |1 3 4 5| (|1 2 2 3| |6 7 8 9|) (|1 4 4 5| |7 8 8 9|) (|2 5 5 6| |11 29 34 56|) |7 9 10 11| （重新分配）

交替运行 偶数阶段 和 奇数阶段，直到两个阶段都 没有元素交换。

实验步骤¶

首先将实验文件 拷贝到自己的目录 ，并进入 PA1 目录：

$ cp -R /home/course/hpc/assignments/2024/PA1 ~/
$ cd ~/PA1/

具体任务¶

填写 odd_even_sort.cpp 文件中的 sort 函数，在该函数内实现并行化的奇偶排序算法（具体请见背景介绍），并注意：

使用升序排序；
每个进程 只允许向相邻进程发送消息。

框架介绍¶

框架首先读入输入文件中的序列，每个进程分别读入序列的一部分，并传递给 sort 函数。
框架将在排序之后进行检验，只有所有进程都输出 pass 才表示排序后序列通过检验，存在错误顺序的将输出 failed 。4 进程运行时正确输出如下（顺序未必一致）：
```
...
Rank 0: pass
Rank 2: pass
Rank 1: pass
Rank 3: pass
...
```
框架对 sort 函数进行计时，并作为性能评判依据。计时前均会进行进程间同步。计时输出跟随在正确性检验之后，格式如下：
```
...
Execution time of function sort is 3330.42 ms.
...
```

运行流程¶

加载环境：spack load openmpi。
编译各个文件： make -j4（可以调整 Makefile 中的 CFLAGS 控制编译选项）。
generate.cpp 编译得到的 generate 可生成乱序序列作为输入：
```
$ ./generate <number_of_elements> <file>
```
其中两个参数的含义分别是：
- number_of_elements : 生成的乱序序列的元素个数 $n\ (0 \le n \le 2147483647)$ ；
- file : 存储乱序序列的输出文件名。
具体运行命令，例如：
```
$ mkdir data
$ ./generate 256 ./256.dat
```
运行 odd_even_sort 对输入文件中的乱序序列进行排序：
```
$ srun -n <nprocs> ./odd_even_sort <number_of_elements> <input_file>
```
其中三个参数的含义分别是：
- nprocs : 运行的进程数；
- number_of_elements : 输入乱序序列的元素个数 $n\ (0 \le n \le 2147483647)$ ；
- input_file : 输入文件名，其中包含 $n$ 个待排序的 32 位浮点数（二进制格式）。此处可直接使用 generate 的输出文件，请参考输入文件 ./data/100.dat。
具体运行命令，例如：
```
$ srun -n 4 ./odd_even_sort 256 ./256.dat
```

测试数据¶

除了同学自己生成的数据外，助教在 /home/course/hpc/assignments/2024/data/public/PA1 下也提供了一些数据可供同学测试，文件名即为数据数量（如 100.dat 表示 $n = 100$ ）。在提供的代码框架中，已经将此数据目录链接到了 PA1/data 目录中。由于数据文件较大，禁止将数据拷贝到自己的目录下，运行时直接向程序传入 data/xxx.dat 即可。同学对此目录没有写入权限，如果需要生成文件测试，请使用其他目录。

优化策略¶

可以尝试将计算时间和通信时间尽可能地重叠。例如合并相邻进程序列的计算和下一轮迭代的通信之间存在重叠机会。可以通过点对点异步通信实现。
可以尝试将进程与核绑定，运行性能会更稳定（具体可阅读集群使用手册的 SLURM 使用部分）。
如果不确定自己的优化方法或实现是否符合规则，请与助教进行讨论。

注意事项¶

你的修改应该仅限于 odd_even_sort.cpp 文件。即使修改了其他文件（如用于调试等目的），也要确保在 不进行这些修改 的情况下，程序能够正确编译运行。助教将替换所有其他文件为下发的版本后进行评测，以确保评分的正确性和公平性。
下发的 odd_even_sort.cpp 中的 sort 函数为空，需在填写 sort 函数后，编译运行 odd_even_sort 后才能正确工作。

实验评测¶

测试用例
- 最终用于正确性与性能测试的测试数据不完全由 generate 生成，将是固定的 10 组数据（不公开），并满足题目的输入要求。
正确性（ $60 \%$ ）
- 在作业截止日期之后进行正确性检查，每个测试用例 6 分。你将获得所有通过的测试用例的分数。
- 助教可能使用符合要求的 任意进程数 来运行你的程序，因此请确保你的实现是正确的。

性能（ $30 \%$ ）

每组测试用例的性能分为 3 分。对于每组测试用例，只有当你获得了正确性分数后，才能得到性能分。
性能测试只针对 sort 函数，即仅对 sort 函数计时。
由于不同实现在不同情况下的性能表现可能不同，此部分最终的运行方式由同学确定， 至多可以使用 2 机 56 进程 。请同学自行修改 run.sh 脚本中的运行命令，助教将使用此作为最终的性能评分依据。请确保命令行以 $* 接受所有参数，因为最终正确性/性能测试所用的校验方法与当前给定版本不同，具有更多输入参数。可以明确，run.sh接受的前三个参数依次是 <target_program> <num_elements> <input_file>，但是测试时可能后面接受更多参数。
关于性能评分：（1）每组测试用例有一个性能线（不公布），超过性能线的同学将得到满分。（2）未达到性能线的同学，根据测试性能在 未达性能线同学 的排名给出每组测试用例的分数，每组测试用例各自排名。对于某组测试用例，未达到性能线的同学中，性能排名前 $10 \%$ 的同学得到 $90 \%$ 的分数，排名 $10 \%$ - $20 \%$ 的同学得到 $80 \%$ 的分数，依此类推。

以下给出 /home/course/hpc/assignments/2024/data/public/PA1 的 7 组公开测试用例的性能线（表示较优的性能水平）作为参考。同学可以参考该性能线调试优化程序，但不保证在公开数据上达到性能线就一定能在评分数据上达到性能线。

测试用例	性能线（运行时间）
data/100.dat	0.015 ms
data/1000.dat	0.07 ms
data/10000.dat	0.25 ms
data/100000.dat	1.2 ms
data/1000000.dat	6 ms
data/10000000.dat	75 ms
data/100000000.dat	770 ms

实验报告（ $10 \%$ ）
- 助教根据实验报告的完整性给出分数，需要写的内容在下一章实验提交中给出。

实验提交¶

实验代码与结果：
- 在截止日期之前将完成后的整个实验框架置于自己 home 目录下的 PA1 文件夹，如 /home/course/hpc/users/2020000000/PA1。为了节省空间， 务必删除所有自己调试用的 dat 文件。
实验报告：
- 将 PDF 文件 提交至网络学堂（无需提交代码工程）。
- 包含以下内容：
  1. odd_even_sort.cpp 中 sort 函数的源代码，并对实现进行简要说明（可以以代码注释的形式，或者单独写出）。
  2. 你所做的性能优化方式（如果有）以及效果。
  3. 给出在 $1 \times 1$ , $1 \times 2$ , $1 \times 4$ , $1 \times 8$ , $1 \times 16$ , $2 \times 16$ 进程（ $N \times P$ 表示 $N$ 台机器，每台机器 $P$ 个进程）及元素数量 $n = 100000000$ 的情况下 sort 函数的运行时间，及相对单进程的加速比。（此测试请使用助教提供的 100000000.dat）。

最后更新: 2024年4月6日

作者: Harry Chen (28.14%), Yuyang Jin (66.83%), 翟明书 (2.01%), huangshuhong (3.02%)