生命游戏并行化

编程实验 (基于 Linux)

截止时间：2025年1月12日 23:59

提交内容：

  1. 代码源文件 life-parallel.c：注意代码中应有必要的注释
  2. 实验报告 学号.pdf：简要描述实验中遇到的关键问题及解决方案、印象最深的 bugs、或者额外实现的功能等即可。不要复制粘贴代码，也不需要把正常执行结果截图放到报告中 (1～2 页)。

提交方式：TBD

生命游戏 (Game of Life) 是英国数学家 John Horton Conway 于 1970 年发明的一种细胞自动机 (cellular automaton)，它是 “即便简单的规则也能产生复杂和有趣的行为” 的生动展示。生命游戏同时是图灵完备的，也就是说理论上你可以利用这个模型完成现代计算机能做的所有事情 (该网站提供了生命游戏的一个在线试玩版本)。

以单线程串行方式实现生命游戏是一个典型的编程训练题，我们在本次实验的框架代码中也提供了一份 C 语言的参考实现。基于该框架代码，你需要将单线程的生命游戏并行化，通过锁 (locks)、条件变量 (condition variables) 和信号量 (semaphores) 的使用来实现正确的互斥和同步，从而在多核处理器上获得预期的加速比。

运行如下命令下载本实验的框架代码：

git clone https://git.nju.edu.cn/oslab/life.git
cd life

🗒️ 实验内容

生命游戏由一个二维矩阵世界构成 (框架代码中的 LifeBoard)，其中每个格子居住着一个活细胞 (在框架代码中以 o 来表示) 或死细胞 (以 . 来表示)。该世界中的每个细胞都会有一个初始状态，并在每次迭代时根据其周围八个相邻格子中细胞的状态 (活细胞和死细胞的数量) 来决定自己下一时刻的状态：

  1. 如果一个活细胞周围的八个相邻位置有 2 个或 3 个活细胞，则在下一轮该细胞继续存活；否则该细胞死亡 (因为资源不足、或者过度拥挤)；
  2. 如果一个死细胞周围的八个相邻位置恰好有 3 个活细胞，则在下一轮该细胞会复活；否则该细胞继续死亡。

上述规则决定了生命游戏中细胞的演化只由世界的初始状态决定，而不需要额外的输入 (即一种零玩家游戏)。在特定的初始状态下，世界的演化会展现出很多复杂而有趣的行为。目前，虽然人们已经发现了一些特殊的演化模式，但生命游戏是一个不可判定问题，即给定一个初始模式和一个后续模式，不存在可以判断该后续模式是否会出现的算法。

在本次实验中，我们考虑有边界的世界 (还可能是无边界、或循环边界的世界)，即二维矩阵世界的上下左右边界都总是死细胞，且不会在演化过程中复活。

例如，下面给出了 5 * 7 矩阵世界的生命游戏演化过程。以初始状态的第二行第六列为例，其初始状态为活细胞；在第一轮迭代时，由于其周围存在 2 个活细胞，因此该细胞继续存活；但在第二轮迭代时，由于其周围仅有 1 个活细胞，因此该细胞死亡。

.......        .......        .......        .......
.....o.        ...o.o.        ..oo...        ..ooo..
..oooo.   ->   ..oo.o.   ->   ..oo.o.   ->   .o.....   
..o..o.        ..o..o.        ..ooo..        ..o.o..
.......        .......        .......        .......
初始状态         第一轮          第二轮           第三轮

框架代码和实现需求

本次实验的框架代码中已经实现了串行版本的生命游戏，你可以在目录下直接运行 make 进行编译，并以如下方式来运行：

./life [steps] [initial_board_file]  # 例如 ./life 10 input/o0075

其中，initial_board_file 是存储初始世界状态的文件，steps 指明生命游戏演化的迭代次数，程序运行结束后将打印最终的世界状态。

框架代码中存储二维矩阵世界状态的结构体 LifeBoard 如下所示：

typedef struct {
  int width;           // 矩阵世界的宽度 (包含边界)
  int height;          // 矩阵世界的高度 (包含边界)
  LifeCell *cells;     // 一个一维数组，表示各个细胞的状态 (按行优先方式存放)
} LifeBoard;

你可以在 life.h 和 life.c 中找到读取、打印和操作 LifeBoard 的相关函数定义和实现，并在 life-serial.c 中找到串行版本的实现 (关于串行版本的理解可参考 LeetCode Solutions)。同时，input 目录下提供了五个初始世界状态文件可供测试 (文件的第一行记录了矩阵世界的高度和宽度)。

基于框架代码，你需要考虑如何对生命游戏的演化过程进行并行化，仔细思考其中的互斥和同步需求，并实现 life-parallel.c 文件中的如下函数，从而能以比串行版本更快的速度计算得到给定迭代次数下的 LifeBoard 状态 (该函数将在 main.c 中以类似串行版本的方式被调用以计算得到最终的 cells)：

void simulate_life_parallel(int threads, LifeBoard *state, int steps)

该函数的输入参数包括：

  • threads: 允许创建的线程个数上限 (不包括主线程，即你最多可以使用 threads + 1 个线程来进行计算)。注意该参数限定了代码运行过程中总共能创建的线程个数，而不是单一时刻能同时存在的最大线程个数 (可理解为程序运行过程中最多能调用 pthread_create() 多少次，而不能在线程总数不超过限定的情况下反复创建和销毁线程)；
  • state: 初始的世界状态；
  • steps: 生命游戏演化迭代次数。

注意本次实验中仅允许使用 pthread.h 和 semaphore.h 库中的如下 API (API 手册)：

  • 线程创建和结束：pthread_create()、pthread_exit()、pthread_yield()、pthread_join()
  • 互斥锁 (mutex): 以 pthread_mutex_ 为前缀的 API
  • 自旋锁 (spin): 以 pthread_spin_ 为前缀的 API
  • 条件变量 (cond): 以 pthread_cond_ 为前缀的 API
  • 信号量 (sem): 以 sem_ 为前缀的 API

对于生命游戏演化规则的实现，你可以直接复用串行版本中的合适代码片段。当然，你也可以设计不同的生命游戏实现方式，但需要确保不改变 LifeBoard 结构体的定义，并在 life-parallel.c 中包含所有额外定义的数据结构和函数实现。

📊 结果评估

我们会在特定的测试环境中编译和运行你提交的 life-parallel.c 文件来评估并行版本实现的正确性和执行速度，包括但不限于使用不同的 threads 个数、为程序运行分配不同的 CPU 个数、以及尝试以不同速度来推进不同线程的执行。

对于每一次测试，我们将采用如下方式进行评分，所有测试得分之和即为 OJ 返回的 score 分数：

  • 首先，如果并行版本能输出正确的结果 (即与串行版本一致)，则可获得该次测试 40% 的分数；
  • 其次，在允许最多 N 个线程的情况下，并行版本在具有 N 个 CPU 的运行环境中应能获得接近 N 倍的加速比。如果并行版本能获得预计的加速比，则可获得该次测试剩余 60% 的分数 (按加速比区间进行计算)；
  • 如果观察到并行版本执行超时 (一般情况下，比串行版本运行慢)、或者超出不合理的内存使用限制，则该次测试不得分。

注意提交的代码在运行过程中不能违反以下规则，否则会直接返回错误信息：

  • 更改了 life-parallel.c 中引用的头文件、或增加了新的头文件；
  • 使用了 pthread.h 和 semaphore.h 库中允许范围之外的 API；
  • 代码运行过程中创建了超过输入参数指定上限个数的线程。

我们测试环境使用的 Makefile 和 main.c 与框架代码中提供的类似，建议大家在提交前先自行编写测试代码来进行测试 (包括构造更多具有不同特征的初始世界状态文件)。

💭 Tips

框架代码的 Makefile 中会额外编译两个二进制文件，可用于检测一些错误情况：

  • ./life-tsan：由 ThreadSanitizer 编译，可以帮助你检测及调试竞争条件
  • ./life-asan：由 AddressSanitizer 编译，可以帮助你检测及调试内存错误

关于多线程编程的一些介绍：