实验二：广度优先搜索¶

负责助教：师天麾 sth19@mails.tsinghua.edu.cn、王豪杰 haojie0429@gmail.com

通过实现并行 BFS 帮助熟悉 OpenMP 以及 OpenMP+MPI 混合编程。在保证正确性的前提下，我们鼓励通过探索不同的并行化策略以优化程序性能。

实验任务¶

在本次实验中，你需要分别使用 OpenMP 与 OpenMP+MPI 来实现一个并行的图算法：广度优先搜索（BFS）。相信你在之前的课程中对图与 BFS 有一定了解，所以在这里我们不再赘述。如果你对图与 BFS 仍然不太了解，可以通过书籍、博客与其他课程等多种途径进行学习。

本次实验中的图均为有向图，你可以在 graph.h 和 graph_internal.h 中找到其定义。我们建议你首先了解这些文件中的有向图的表示方法。有向图使用 CSR （Compressed Sparse Row，压缩稀疏行）格式存储，具体而言，图由有向边的数组（outgoing_edges 和 incominging_edges）表示，其中每条边由一个整数表示，该整数为这条有向边的终点的编号。所有边以源点编号为关键字排序，因此源点隐含在边的表示中。这种存储格式使得图的表示更为紧凑，并且一个源点的所有出边都连续地存储在内存中。例如，要遍历图中所有节点的出边，可以使用以下代码，该代码使用了 graph.h 中定义的函数（这些函数的实现在 graph_internal.h）：

for (int i=0; i<num_nodes(g); i++) {
  // Vertex is typedef'ed to an int. Vertex* points into g.outgoing_edges[]
  const Vertex* start = outgoing_begin(g, i);
  const Vertex* end = outgoing_end(g, i);
  for (const Vertex* v=start; v!=end; v++)
    printf("Edge %u %u\n", i, *v);
}

在 bfs_common.cpp 的 bfs_serial 函数中，我们提供了一个串行版本的 BFS 算法，这段代码能够计算出图中从 0 号节点（即根节点）到所有节点的最短距离，注意，图中每条边的长度都为 1。若一个节点无法从 0 号节点到达，则其距离为 -1。

在 graph 目录中有一些供你测试的图。为了对读图过程进行加速，图默认使用二进制格式存储。为了方便你自己构造一些图进行 debug 或进行其他测试，你可以根据 sample_graph.txt 学习如何以文本格式来存储图，并使用我们提供的代码将文本格式的图转为二进制格式的图。你可以通过 main_omp.cpp 中的 USE_BINARY_GRAPH 宏来选择使用二进制格式图还是文本格式图。将文本格式图转为二进制格式图的具体代码位于 graph.cpp 中的 store_graph_binary 函数（不过你可以不用看它的具体实现，只要知道文本格式图的具体格式是什么，然后 main 函数中的代码会自动帮你将文本格式图转为二进制格式图）。在将文本格式图转换为二进制格式图后，程序会退出，这时你需要重新修改 USE_BINARY_GRAPH 并 重新编译，来选择使用二进制格式图并从命令行输入相应文件名来运行程序。所有二进制格式图统一使用 .graph 后缀来与文本格式图进行区分。

实验步骤¶

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

$ cp -R /home/course/hpc/assignments/2021/PA2 ~/
$ cd ~/PA2/

具体任务¶

填写 bfs_omp.cpp 文件中的 bfs_omp 函数和 bfs_omp_mpi.cpp 文件中的 bfs_omp_mpi 函数，在这两个函数内分别使用 OpenMP 以及 OpenMP+MPI 实现并行化的 BFS 算法，最终得到从 0 号节点到所有节点的最短距离（每条边长度为 1）。

框架介绍¶

框架首先读入输入文件中的图并以CSR的格式存储，之后传递给 bfs_omp 函数和 bfs_omp_mpi 函数。
框架将在 BFS 之后进行检验，只有所有节点最短距离都正确才会输出计时，存在错误距离将输出 Results disagree。
框架对 bfs_omp 函数和 bfs_omp_mpi 函数进行多次运行并取平均时间，作为性能评判依据。其中 MPI 版本会在计时前进行进程间同步。计时输出如下：

...
Excution time of function bfs_omp is 11030.4212 ms.
...
Excution time of function bfs_omp_mpi is 11030.4212 ms.
...

运行流程¶

加载环境：spack load openmpi。
编译各个文件： make -j4（可以调整 Makefile 中的 CFLAGS 控制编译选项）。
运行 bfs_omp 对输入文件中的图进行 BFS：
```
$ srun -N 1 ./bfs_omp <input_file>
```
其中参数input_file是输入图文件名，如<PATH_TO_GRAPHS_DIRECTORY>/sample1.graph。
运行 bfs_omp_mpi 对输入文件中的图进行 BFS：
```
$ srun -N <nodes> -n <nprocs> ./bfs_omp <input_file>
```
其中三个参数的含义分别是：
- nodes : 运行的机器节点数；
- nprocs: 运行的进程数；
- input_file : 输入图文件名，如<PATH_TO_GRAPHS_DIRECTORY>/sample1.graph。

测试数据¶

助教在 /home/course/hpc/assignments/2021/data/public/PA2 下也提供了一些数据可供同学测试。在提供的代码框架中，已经将此数据目录链接到了 PA2/graph 目录中。由于数据文件较大，禁止将数据拷贝到自己的目录下，运行时直接向程序传入 graph/xxx.graph 即可。

用于评分的测试数据可能并不完全是 graph 中的数据。

优化策略¶

BFS算法有多种实现方式，我们提供的串行版本是用“Top Down”方式实现的 BFS。你可以尝试更为复杂的“Bottom Up”方式来实现 BFS，甚至可以将“Top Down”与“Bottom Up”混合（在不同 step 选择不同策略），以实现更高性能。在这里我们给出一些与“Bottom Up”相关的课件和资料供你参考，如有需要，你也可以自行查阅相关博客与论文。下面是一些参考：
- https://people.csail.mit.edu/jshun/6886-s18/lectures/lecture4-1.pdf
- https://parlab.eecs.berkeley.edu/sites/all/parlab/files/main.pdf
对于需要同步的代码，你可以使用 #pragma omp critical 或 #pragma omp atomic，也可以尝试使用原子操作 compare_and_swap 来获得更高性能。以及，是否存在可以避免使用 compare_and_swap 的条件？换句话说，某些情况下你是否可以提前知道 compare 会失败？
可以尝试将进程/线程与核绑定（ 尤其是 OpenMP+MPI 混合时 ），运行性能会更稳定（具体可阅读集群使用手册的 SLURM 使用部分）。
如果不确定自己的优化方法或实现是否符合规则，请与助教进行讨论。

注意事项¶

如果不知道要做什么，务必先 阅读并理解 bfs_common.cpp 中的串行实现。
你修改的文件应该仅限于 bfs_omp.cpp、bfs_omp_mpi.cpp、run_bfs_omp.sh、run_bfs_mpi.sh 和 Makefile。即使修改了其他文件（如用于调试等目的），也要确保在 不进行这些修改 的情况下，程序能够正确编译运行。助教将替换所有其他文件为下发的版本后进行评测，以确保评分的正确性和公平性。
bfs_omp.cpp和bfs_omp_mpi.cpp中的函数为空，需在填写函数后并编译后才能正确运行。

分数细则¶

对于每一部分得分，OpenMP 与 OpenMP+MPI 各占一半。

正确性¶

正确性得分共占 $60\%$ ，包含两部分：基础分（占 $10 \%$ ）和加速比得分（占 $50 \%$ ）。

对于基础分，助教可能使用符合要求的 任意线程数与进程数 来运行你的程序，如果你的代码运行结果与助教提供的串行代码（即 bfs_serial）运行结果相同，就可以获得该测试用例的基础分。有多组测试用例。你将获得通过的测试用例的分数，每个测试用例分数相同。

对于加速比得分，由于不同实现在不同情况下的性能表现可能不同，此部分最终的运行方式由同学确定，OpenMP 由同学自行设置线程数（以及线程绑定等），MPI 至多可以使用 4 机 112 进程 。我们提供了 run_bfs_omp.sh 和 run_bfs_mpi.sh，请同学修改脚本中的运行命令和环境变量，助教将使用此作为 最终的加速比得分的评分依据（运行方式如 ./run_bfs_omp.sh input_file）。加速比测试只针对 bfs_serial, bfs_omp 和 bfs_omp_mpi 函数的耗时，评价标准如下：

对于 OpenMP 程序，如果在 68m.graph 数据上 bfs_omp 相对 bfs_serial 的加速比 超过 $2$ ，则加速比合格，否则加速比不合格。对于每个测试用例，只有当你 获得了正确性基础分且加速比合格 ，方可获得该测试用例的加速比得分。注意，助教仅使用 68m.graph 数据上的加速比来决定你的 OpenMP 程序加速比是否合格，而不会对所有测试用例分别测试加速比（因为不同测试用例的潜在并行度可能差距较大）。
对于 OpenMP+MPI 程序，如果在 68m.graph 、200m.graph或500m.graph的任意一个数据图上 bfs_omp_mpi 相对 bfs_omp 的加速比 超过 $1.1$ （注意是与你提交的使用 run_bfs_omp.sh 的 OpenMP 版本相比）并且你的 OpenMP 版本加速比合格，则加速比合格，否则加速比不合格。对于每个测试用例，只有当你 获得了正确性基础分且加速比合格，方可获得该测试用例的加速比得分。同上，助教仅使用 68m.graph 、200m.graph和500m.graph数据图上的加速比来决定你的 OpenMP+MPI 程序加速比是否合格（只要三个数据图中任意一个图上的加速比超过 $1.1$ 即可）。

参考依据

助教编写的代码在 68m.graph 上的 OpenMP 版本相比串行版本加速比大于 $5$ ，OpenMP+MPI 相比 OpenMP 加速比大于 $2$ 。只要并行实现没有大问题，不必过于担心加速比得分。

性能¶

性能得分共占 $30\%$ 。

对于每组测试用例，只有当你获得了正确性基础分和加速比得分后，才能得到性能分。每组测试用例的性能分数相同。
助教依旧使用你提供的 run_bfs_omp.sh 和 run_bfs_mpi.sh 作为最终的性能评分依据。
性能测试只针对 bfs_omp 和 bfs_omp_mpi 函数。
根据你的性能在全体同学中的排名给出每组测试用例的分数：每组测试用例各自排名，性能排名前 $10 \%$ 的同学得到 $100 \%$ 的分数，排名 $10 \%$ - $20 \%$ 的同学得到 $90 \%$ 的分数，依此类推。对于任何测试用例，获得正确性分数的同学将至少获得 $10 \%$ 的性能分数。

实验报告¶

实验报告共占 $10\%$ ，助教根据实验报告给出分数，需要写的内容在下一章实验提交中给出。

实验提交¶

实验代码：
- 在截止日期之前将完成后的整个实验框架置于自己 home 目录下的 PA2 文件夹，如 /home/course/hpc/users/2020000000/PA2。为了节省空间， 务必删除所有自己调试用的 graph 文件。
实验报告：
- 将 PDF 文件 提交至网络学堂（无需代码）。
- 包含以下内容：
  1. bfs_omp.cpp 文件中的 bfs_omp 函数和 bfs_omp_mpi.cpp 文件中的 bfs_omp_mpi 函数的源代码，并对实现简要说明（可以作为代码注释或者单独写出）。
  2. 你所做的性能优化方式（如果有）以及效果。
  3. 对 OpenMP 版本，报告使用 $1$ , $7$ , $14$ , $28$ 线程 在 68m.graph 、200m.graph或500m.graph图下 bfs_omp 函数的运行时间（三个图选择一个报告即可），及相对单线程的加速比 。
  4. 对 OpenMP+MPI 版本，报告 $1\times1$ , $1\times2$ , $1\times4$ , $1\times14$ , $1\times28$ , $2\times1$ , $2\times2$ , $2\times4$ , $2\times14$ , $2\times28$ , $4\times1$ , $4\times2$ , $4\times4$ , $4\times14$ , $4\times28$ 进程（ $N\times P$ 表示 $N$ 台机器，每台机器 $P$ 个进程，线程数 $T$ 自定，但 $P \times T$ 不建议超过 28）在 68m.graph 、200m.graph或500m.graph图下 bfs_omp_mpi 函数的运行时间（三个图选择一个报告即可），及相对单进程的加速比 。此部分测试建议使用脚本提交运行、记录输出，以减少工作量。

最后更新: 2021年4月15日

作者: Harry Chen (46.38%), sth1997 (53.62%)