使用 SFML 的 OpenMP 和生命游戏可视化
OpenMP with Game of Life visualization using SFML
您好，我正在尝试比较 'Game of Life' 的串行和并行版本之间的速度。
我使用 SFML 库来可视化这样的生活游戏。
SFML window
串行逻辑很简单，如下所示。
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
int neighbor = 0;
// check 8 cells around.
// 1 2 3 -1
// 4 5 0
// 6 7 8 +1
// (1)
if (gamefieldSerial.isAvailableCell(UP(i), LEFT(j))) {
if(gamefieldSerial[UP(i)][LEFT(j)] == LIVE) neighbor++;
}
// (2)
if (gamefieldSerial.isAvailableCell(UP(i), j)) {
if (gamefieldSerial[UP(i)][j] == LIVE) neighbor++;
}
// (3)
if (gamefieldSerial.isAvailableCell(UP(i), RIGHT(j))) {
if (gamefieldSerial[UP(i)][RIGHT(j)] == LIVE) neighbor++;
}
// (4)
if (gamefieldSerial.isAvailableCell(i, LEFT(j))) {
if (gamefieldSerial[i][LEFT(j)] == LIVE) neighbor++;
}
// (5)
if (gamefieldSerial.isAvailableCell(i, RIGHT(j))) {
if (gamefieldSerial[i][RIGHT(j)] == LIVE) neighbor++;
}
// (6)
if (gamefieldSerial.isAvailableCell(DOWN(i), LEFT(j))) {
if (gamefieldSerial[DOWN(i)][LEFT(j)] == LIVE) neighbor++;
}
// (7)
if (gamefieldSerial.isAvailableCell(DOWN(i), j)) {
if (gamefieldSerial[DOWN(i)][j] == LIVE) neighbor++;
}
// (8)
if (gamefieldSerial.isAvailableCell(DOWN(i), RIGHT(j))) {
if (gamefieldSerial[DOWN(i)][RIGHT(j)] == LIVE) neighbor++;
}
// -- Rule of Game of Life
// Cell borns when exactly 3 neighbor is LIVE
// Cell remains alive when 2 or 3 neighbor is LIVE
// Cell with more than 3 neighbor dies with overpopulation
// Cell with less than 2 neighbor dies with underpopulation
if (gamefieldSerial[i][j] == DEAD) {
if (neighbor == 3) {
gamefieldSerial[i][j] = LIVE;
}
}
else if (gamefieldSerial[i][j] == LIVE) {
if (neighbor < 2 || neighbor > 3) {
gamefieldSerial[i][j] = DEAD;
}
}
}
在 768*256 个单元上，100 代耗时 3940ms。
但是在并行版本中我实现如下，
#pragma omp parallel for num_threads(4)
for (int t = 0; t < width * height; t++) {
int i = t / width;
int j = t % width;
int neighbor = 0;
// check 8 cells around.
// 1 2 3 -1
// 4 5 0
// 6 7 8 +1
// (1)
if (gamefieldParallel.isAvailableCell(UP(i), LEFT(j))) {
if (gamefieldParallel[UP(i)][LEFT(j)] == LIVE) neighbor++;
}
// (2)
if (gamefieldParallel.isAvailableCell(UP(i), j)) {
if (gamefieldParallel[UP(i)][j] == LIVE) neighbor++;
}
// (3)
if (gamefieldParallel.isAvailableCell(UP(i), RIGHT(j))) {
if (gamefieldParallel[UP(i)][RIGHT(j)] == LIVE) neighbor++;
}
// (4)
if (gamefieldParallel.isAvailableCell(i, LEFT(j))) {
if (gamefieldParallel[i][LEFT(j)] == LIVE) neighbor++;
}
// (5)
if (gamefieldParallel.isAvailableCell(i, RIGHT(j))) {
if (gamefieldParallel[i][RIGHT(j)] == LIVE) neighbor++;
}
// (6)
if (gamefieldParallel.isAvailableCell(DOWN(i), LEFT(j))) {
if (gamefieldParallel[DOWN(i)][LEFT(j)] == LIVE) neighbor++;
}
// (7)
if (gamefieldParallel.isAvailableCell(DOWN(i), j)) {
if (gamefieldParallel[DOWN(i)][j] == LIVE) neighbor++;
}
// (8)
if (gamefieldParallel.isAvailableCell(DOWN(i), RIGHT(j))) {
if (gamefieldParallel[DOWN(i)][RIGHT(j)] == LIVE) neighbor++;
}
// -- Rule of Game of Life
// Cell borns when exactly 3 neighbor is LIVE
// Cell remains alive when 2 or 3 neighbor is LIVE
// Cell with more than 3 neighbor dies with overpopulation
// Cell with less than 2 neighbor dies with underpopulation
if (gamefieldParallel[i][j] == DEAD) {
if (neighbor == 3) {
gamefieldParallel[i][j] = LIVE;
}
}
else if (gamefieldParallel[i][j] == LIVE) {
if (neighbor < 2 || neighbor > 3) {
gamefieldParallel[i][j] = DEAD;
}
}
}
在相同的环境下花费了 5746 毫秒。
我认为在 for 循环中应用 openMP 的 'for' 指令可以提高性能，但事实并非如此。
我应该换一种方式吗？
=============
gamefieldParallel 和 gamefieldSerial 都是 GameField class 的实例，它为单元格动态分配了 int** 字段变量。我正在使用运算符重载来像二维数组一样访问它。（抱歉英语不好！）
在您的串行版本和并行版本中，您都在迭代游戏字段时对其进行更新。这是两个版本的错误。假设您计算 gameField[0][0] 的新状态，然后更新它。现在您转到 gameField[0][1] --- 作为计算其新状态的一部分，您向左看 gameField[0][0] 已经包含该单元格的新更新状态，但必须应用生命游戏的规则第一个单元格的先前状态。
换句话说，你应该有一个只读（常量）oldGameField，然后将新状态填充到newGameField。计算完所有单元格后，您可以将新字段用作下一次游戏迭代的旧字段。
修复该错误实际上是解决性能问题的重要部分。
多线程
与其想象 4 个处理器执行这些更新，不如想象 4 个人用铅笔和纸来完成。因为您现在将 oldGameField 视为只读，所以复印旧页面并给每个人一份副本是安全的。每个人都知道没有其他人会更改旧页面，因此他们不必担心他们的副本会过时。
但是您仍然只有一页 newGameField。在您的串行方法中，只有一个人拥有专属于自己的页面和铅笔。现在您有四个人试图同时在同一页上绘图。与花在计算上的时间相比，他们浪费在彼此之间传递铅笔和纸张的时间更多！
四个人完成这项工作的时间确实比一个人单独完成要长。
这并不是硬件内部发生的事情的精确表示，但是当我们考虑任何锁定时 and/or 原子 OpenMP 可能正在使用，以及诸如处理器内核中的内存缓存之类的东西 - - 非常接近。
那么我们该如何解决呢？
您和您的三个朋友可以决定每人更新该字段的四分之一。也许你占据了董事会的整个前四分之一。下一个人拿第二个季度，依此类推。与其争夺一张 sheet 纸来绘制新的游戏领域，你们每个人都有自己的一张纸来绘制新状态的四分之一。
全部完成后，您快速将四张纸粘贴在一起，制作新的游戏场地页面。
这里的重点是确保每个线程都从没有人更改的内存中读取，并且每个线程只写入没有其他线程正在访问的内存。这意味着内核不会因内存写入而相互阻塞，并且当它们看到其他内核写入共享内存时也不必刷新它们的缓存。
确保每个线程的新游戏场内存没有足够接近以致干扰其他线程使用的内存是很棘手的。您通常需要了解有关内核中缓存行大小的一些信息，无论您的平台是否使用称为 "NUMA" 的东西，等等
我不知道 OpenMP - 但也许它有一些内置支持来帮助解决这个问题。
总结
- 将旧状态与新状态分开
- 您的线程都可以愉快地共享旧状态（因为在迭代期间没有人更改它）
- 将工作分成多个块 - 每个线程一个
- 为每个线程分配自己的内存来存储其结果。
- 所有线程完成后，让主线程将所有结果合并到一个组合的新游戏字段中。
GoL 是 OpenMP 并行化的完美样本，因为它是 令人尴尬的并行 - 计算当前一代中一个单元格的值不依赖于相邻单元格的计算。这里的问题是您正在读取和写入同一个数组，从实现的角度来看这是错误的。在您的顺序代码中，这只会导致单元格状态计算错误，但同时您 运行 会遇到错误共享等问题，这些问题会显着降低程序速度。此外，您已将两个嵌套循环替换为一个嵌套循环，并使用模运算计算行和列索引，这可能是减速的最大来源。速度变慢的另一个原因是内部循环中有并行区域 - 您正在为每一代激活该区域中的线程付出代价。
您需要做的是使用两个数组——一个用于上一代，一个用于当前。从前一个数组读取并写入后者。完成后，交换阵列并重复。在带有 OpenMP 的伪 C++ 中，解决方案如下所示：
#pragma omp parallel
{
// Generations loop (1)
for (int gen = 0; gen < NUM_GENERATIONS; gen++) {
// Compute the new current generation (2)
#pragma omp for
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
// Count the number of live neighbours of current[i][j] (3)
int neighbours = count_neighbours(current, i, j);
// Update the state of the current cell (4)
if (current[i][j] == DEAD && neighbours == 3)
next[i][j] = LIVE;
else if (current[i][j] == LIVE)
next[i][j] = (neighbours < 2 || neighbours > 3) ? DEAD : LIVE;
}
}
// The following block runs in the master thread (5)
#pragma omp master
{
// Swap the current and next arrays
std::swap(current, next);
// Display the board state (if necessary)
display(current);
}
// Synchronise the threads before the next iteration (6)
#pragma omp barrier
}
}
注意事项（数字对应代码注释中的数字）：
外部（世代）循环在并行区域内。这消除了每次迭代激活和停用区域的开销。
工作共享结构 for 应用于 运行 在电路板行上的循环。这足以优化并行化问题。如果能保证width乘以sizeofnext中的元素类型是64字节（大部分CPU上的缓存行大小）的倍数，就可以杜绝虚假共享的可能性.
计算邻居个数涉及到current数组中的值
新值进入 next 数组。
一旦下一代被完全计算出来，我们需要交换数组并使 next 变为 current 用于世代循环的下一次迭代。这应该由单个线程完成，在这种情况下，这个负担落在主线程上。请注意，如果 current 和 next 都是指向实际数组的 指针 ，则此交换最有效。为元素交换数组值元素很慢。交换指向这些数组的两个指针非常快。使用主线程还可以让您有机会进行 GUI 调用，例如 display()（假设这是将板绘制到屏幕上的函数）。
master 构造在退出时没有隐式屏障，因此我们需要显式同步线程，否则某些线程可能会在我们之前开始执行下一次迭代交换了数组。
如果不打算显示中间板的状态，代码如下：
// The following block runs in the master thread (5)
#pragma omp master
{
// Swap the current and next arrays
std::swap(current, next);
// Display the board state (if necessary)
display(current);
}
// Synchronise the threads before the next iteration (6)
#pragma omp barrier
可以替换为：
#pragma omp single
std::swap(current, next);
single 构造在退出时有隐式屏障，因此无需添加显式屏障。
我将主动提出另一个关于加速计算的建议。拥有所有这些条件
if (gamefield.isAvailableCell(UP(i), LEFT(j))) {
...
}
会减慢您的代码，因为如果没有条件，现代 CPU 会做得更好。此代码仅用于捕获模拟数组边界处的单元格。因此，不是检查每个单元格在给定方向上是否有邻居，而是简单地使电路板宽两个单元格（一个在行首，一个在行尾）和高两个单元格（顶部一行和一个在底部）并将多余的单元格留空（DEAD）。然后 isAvailableCell() 将始终是 true 并且您可以摆脱条件。请记住 运行 从 1 到 width/height 的循环。
您好，我正在尝试比较 'Game of Life' 的串行和并行版本之间的速度。 我使用 SFML 库来可视化这样的生活游戏。 SFML window 串行逻辑很简单，如下所示。
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
int neighbor = 0;
// check 8 cells around.
// 1 2 3 -1
// 4 5 0
// 6 7 8 +1
// (1)
if (gamefieldSerial.isAvailableCell(UP(i), LEFT(j))) {
if(gamefieldSerial[UP(i)][LEFT(j)] == LIVE) neighbor++;
}
// (2)
if (gamefieldSerial.isAvailableCell(UP(i), j)) {
if (gamefieldSerial[UP(i)][j] == LIVE) neighbor++;
}
// (3)
if (gamefieldSerial.isAvailableCell(UP(i), RIGHT(j))) {
if (gamefieldSerial[UP(i)][RIGHT(j)] == LIVE) neighbor++;
}
// (4)
if (gamefieldSerial.isAvailableCell(i, LEFT(j))) {
if (gamefieldSerial[i][LEFT(j)] == LIVE) neighbor++;
}
// (5)
if (gamefieldSerial.isAvailableCell(i, RIGHT(j))) {
if (gamefieldSerial[i][RIGHT(j)] == LIVE) neighbor++;
}
// (6)
if (gamefieldSerial.isAvailableCell(DOWN(i), LEFT(j))) {
if (gamefieldSerial[DOWN(i)][LEFT(j)] == LIVE) neighbor++;
}
// (7)
if (gamefieldSerial.isAvailableCell(DOWN(i), j)) {
if (gamefieldSerial[DOWN(i)][j] == LIVE) neighbor++;
}
// (8)
if (gamefieldSerial.isAvailableCell(DOWN(i), RIGHT(j))) {
if (gamefieldSerial[DOWN(i)][RIGHT(j)] == LIVE) neighbor++;
}
// -- Rule of Game of Life
// Cell borns when exactly 3 neighbor is LIVE
// Cell remains alive when 2 or 3 neighbor is LIVE
// Cell with more than 3 neighbor dies with overpopulation
// Cell with less than 2 neighbor dies with underpopulation
if (gamefieldSerial[i][j] == DEAD) {
if (neighbor == 3) {
gamefieldSerial[i][j] = LIVE;
}
}
else if (gamefieldSerial[i][j] == LIVE) {
if (neighbor < 2 || neighbor > 3) {
gamefieldSerial[i][j] = DEAD;
}
}
}
在 768*256 个单元上，100 代耗时 3940ms。 但是在并行版本中我实现如下，
#pragma omp parallel for num_threads(4)
for (int t = 0; t < width * height; t++) {
int i = t / width;
int j = t % width;
int neighbor = 0;
// check 8 cells around.
// 1 2 3 -1
// 4 5 0
// 6 7 8 +1
// (1)
if (gamefieldParallel.isAvailableCell(UP(i), LEFT(j))) {
if (gamefieldParallel[UP(i)][LEFT(j)] == LIVE) neighbor++;
}
// (2)
if (gamefieldParallel.isAvailableCell(UP(i), j)) {
if (gamefieldParallel[UP(i)][j] == LIVE) neighbor++;
}
// (3)
if (gamefieldParallel.isAvailableCell(UP(i), RIGHT(j))) {
if (gamefieldParallel[UP(i)][RIGHT(j)] == LIVE) neighbor++;
}
// (4)
if (gamefieldParallel.isAvailableCell(i, LEFT(j))) {
if (gamefieldParallel[i][LEFT(j)] == LIVE) neighbor++;
}
// (5)
if (gamefieldParallel.isAvailableCell(i, RIGHT(j))) {
if (gamefieldParallel[i][RIGHT(j)] == LIVE) neighbor++;
}
// (6)
if (gamefieldParallel.isAvailableCell(DOWN(i), LEFT(j))) {
if (gamefieldParallel[DOWN(i)][LEFT(j)] == LIVE) neighbor++;
}
// (7)
if (gamefieldParallel.isAvailableCell(DOWN(i), j)) {
if (gamefieldParallel[DOWN(i)][j] == LIVE) neighbor++;
}
// (8)
if (gamefieldParallel.isAvailableCell(DOWN(i), RIGHT(j))) {
if (gamefieldParallel[DOWN(i)][RIGHT(j)] == LIVE) neighbor++;
}
// -- Rule of Game of Life
// Cell borns when exactly 3 neighbor is LIVE
// Cell remains alive when 2 or 3 neighbor is LIVE
// Cell with more than 3 neighbor dies with overpopulation
// Cell with less than 2 neighbor dies with underpopulation
if (gamefieldParallel[i][j] == DEAD) {
if (neighbor == 3) {
gamefieldParallel[i][j] = LIVE;
}
}
else if (gamefieldParallel[i][j] == LIVE) {
if (neighbor < 2 || neighbor > 3) {
gamefieldParallel[i][j] = DEAD;
}
}
}
在相同的环境下花费了 5746 毫秒。 我认为在 for 循环中应用 openMP 的 'for' 指令可以提高性能，但事实并非如此。 我应该换一种方式吗？
============= gamefieldParallel 和 gamefieldSerial 都是 GameField class 的实例，它为单元格动态分配了 int** 字段变量。我正在使用运算符重载来像二维数组一样访问它。（抱歉英语不好！）
在您的串行版本和并行版本中，您都在迭代游戏字段时对其进行更新。这是两个版本的错误。假设您计算 gameField[0][0] 的新状态，然后更新它。现在您转到 gameField[0][1] --- 作为计算其新状态的一部分，您向左看 gameField[0][0] 已经包含该单元格的新更新状态，但必须应用生命游戏的规则第一个单元格的先前状态。
换句话说，你应该有一个只读（常量）oldGameField，然后将新状态填充到newGameField。计算完所有单元格后，您可以将新字段用作下一次游戏迭代的旧字段。
修复该错误实际上是解决性能问题的重要部分。
多线程
与其想象 4 个处理器执行这些更新，不如想象 4 个人用铅笔和纸来完成。因为您现在将 oldGameField 视为只读，所以复印旧页面并给每个人一份副本是安全的。每个人都知道没有其他人会更改旧页面，因此他们不必担心他们的副本会过时。
但是您仍然只有一页 newGameField。在您的串行方法中，只有一个人拥有专属于自己的页面和铅笔。现在您有四个人试图同时在同一页上绘图。与花在计算上的时间相比，他们浪费在彼此之间传递铅笔和纸张的时间更多！
四个人完成这项工作的时间确实比一个人单独完成要长。
这并不是硬件内部发生的事情的精确表示，但是当我们考虑任何锁定时 and/or 原子 OpenMP 可能正在使用，以及诸如处理器内核中的内存缓存之类的东西 - - 非常接近。
那么我们该如何解决呢？
您和您的三个朋友可以决定每人更新该字段的四分之一。也许你占据了董事会的整个前四分之一。下一个人拿第二个季度，依此类推。与其争夺一张 sheet 纸来绘制新的游戏领域，你们每个人都有自己的一张纸来绘制新状态的四分之一。
全部完成后，您快速将四张纸粘贴在一起，制作新的游戏场地页面。
这里的重点是确保每个线程都从没有人更改的内存中读取，并且每个线程只写入没有其他线程正在访问的内存。这意味着内核不会因内存写入而相互阻塞，并且当它们看到其他内核写入共享内存时也不必刷新它们的缓存。
确保每个线程的新游戏场内存没有足够接近以致干扰其他线程使用的内存是很棘手的。您通常需要了解有关内核中缓存行大小的一些信息，无论您的平台是否使用称为 "NUMA" 的东西，等等
我不知道 OpenMP - 但也许它有一些内置支持来帮助解决这个问题。
总结
- 将旧状态与新状态分开
- 您的线程都可以愉快地共享旧状态（因为在迭代期间没有人更改它）
- 将工作分成多个块 - 每个线程一个
- 为每个线程分配自己的内存来存储其结果。
- 所有线程完成后，让主线程将所有结果合并到一个组合的新游戏字段中。
GoL 是 OpenMP 并行化的完美样本，因为它是 令人尴尬的并行 - 计算当前一代中一个单元格的值不依赖于相邻单元格的计算。这里的问题是您正在读取和写入同一个数组，从实现的角度来看这是错误的。在您的顺序代码中，这只会导致单元格状态计算错误，但同时您 运行 会遇到错误共享等问题，这些问题会显着降低程序速度。此外，您已将两个嵌套循环替换为一个嵌套循环，并使用模运算计算行和列索引，这可能是减速的最大来源。速度变慢的另一个原因是内部循环中有并行区域 - 您正在为每一代激活该区域中的线程付出代价。
您需要做的是使用两个数组——一个用于上一代，一个用于当前。从前一个数组读取并写入后者。完成后，交换阵列并重复。在带有 OpenMP 的伪 C++ 中，解决方案如下所示：
#pragma omp parallel
{
// Generations loop (1)
for (int gen = 0; gen < NUM_GENERATIONS; gen++) {
// Compute the new current generation (2)
#pragma omp for
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
// Count the number of live neighbours of current[i][j] (3)
int neighbours = count_neighbours(current, i, j);
// Update the state of the current cell (4)
if (current[i][j] == DEAD && neighbours == 3)
next[i][j] = LIVE;
else if (current[i][j] == LIVE)
next[i][j] = (neighbours < 2 || neighbours > 3) ? DEAD : LIVE;
}
}
// The following block runs in the master thread (5)
#pragma omp master
{
// Swap the current and next arrays
std::swap(current, next);
// Display the board state (if necessary)
display(current);
}
// Synchronise the threads before the next iteration (6)
#pragma omp barrier
}
}
注意事项（数字对应代码注释中的数字）：
外部（世代）循环在并行区域内。这消除了每次迭代激活和停用区域的开销。
工作共享结构
for应用于 运行 在电路板行上的循环。这足以优化并行化问题。如果能保证width乘以sizeofnext中的元素类型是64字节（大部分CPU上的缓存行大小）的倍数，就可以杜绝虚假共享的可能性.计算邻居个数涉及到
current数组中的值新值进入
next数组。一旦下一代被完全计算出来，我们需要交换数组并使
next变为current用于世代循环的下一次迭代。这应该由单个线程完成，在这种情况下，这个负担落在主线程上。请注意，如果current和next都是指向实际数组的 指针 ，则此交换最有效。为元素交换数组值元素很慢。交换指向这些数组的两个指针非常快。使用主线程还可以让您有机会进行 GUI 调用，例如display()（假设这是将板绘制到屏幕上的函数）。master构造在退出时没有隐式屏障，因此我们需要显式同步线程，否则某些线程可能会在我们之前开始执行下一次迭代交换了数组。
如果不打算显示中间板的状态，代码如下：
// The following block runs in the master thread (5)
#pragma omp master
{
// Swap the current and next arrays
std::swap(current, next);
// Display the board state (if necessary)
display(current);
}
// Synchronise the threads before the next iteration (6)
#pragma omp barrier
可以替换为：
#pragma omp single
std::swap(current, next);
single 构造在退出时有隐式屏障，因此无需添加显式屏障。
我将主动提出另一个关于加速计算的建议。拥有所有这些条件
if (gamefield.isAvailableCell(UP(i), LEFT(j))) {
...
}
会减慢您的代码，因为如果没有条件，现代 CPU 会做得更好。此代码仅用于捕获模拟数组边界处的单元格。因此，不是检查每个单元格在给定方向上是否有邻居，而是简单地使电路板宽两个单元格（一个在行首，一个在行尾）和高两个单元格（顶部一行和一个在底部）并将多余的单元格留空（DEAD）。然后 isAvailableCell() 将始终是 true 并且您可以摆脱条件。请记住 运行 从 1 到 width/height 的循环。