您好,我正在尝试比较“生命游戏”的串行和并行版本之间的速度。我使用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代耗时3940毫秒。但是在并行版本中,我实现如下:
#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类的实例,该类已为单元动态分配了int **字段变量。我正在使用运算符重载来像二维数组一样访问它。(对不起,英语不好!)
在您的串行版本和并行版本中,您都在迭代时更新游戏字段。这是两个版本的错误。假设您计算gameField[0][0]
的新状态,然后对其进行更新。现在,您进入gameField[0][1]
---作为计算其新状态的一部分,向左看gameField[0][0]
,该位置已经包含该单元格的新更新状态,但是必须将生命游戏的规则应用于第一个单元格的< [上一个状态。
oldGameField
,然后将新状态填充到newGameField
中。计算完所有单元后,可以将新字段用作下一个游戏迭代的旧字段。修复该错误实际上是解决性能问题的重要部分。
多线程
oldGameField
视为只读,所以可以安全地复印旧页面并将副本提供给每个人。每个人都知道没有其他人会更改旧页面,因此他们不必担心自己的副本过时。但是您只能在newGameField
的页面上打印一页。在您的串行方式中,只有一个人,他们自己拥有页面和铅笔。现在,您有四个人试图同时在同一页上绘制。他们浪费的时间比花在计算上的时间还要多!从字面上看,完成一个工作需要四个人比一个人独自完成需要的时间更长。
这并不是要精确表示硬件内部的情况,但是当我们考虑到OpenMP可能正在使用任何锁定和/或原子时,以及处理器核心中的内存缓存之类的东西,它就非常接近了。
那么我们如何解决它?
一旦完成,就将您的四张纸快速粘贴在一起,以创建新的游戏领域页面。
这里的目的是确保每个线程都从内存中读取无人更改的内容,并且确保每个线程仅写入没有其他线程正在访问的内存。这意味着内核之间不会因内存写入而相互阻塞,并且在看到其他内核写入共享内存时也不必刷新其缓存。
确保每个线程的新游戏场内存距离不够近,不会对其他线程使用的内存造成干扰,这很棘手。通常,您需要了解一些有关内核中缓存行大小的信息,以及您的平台是否使用称为“ NUMA”的信息,等等。
我不知道OpenMP,但也许它具有一些内置支持来帮助您解决此问题。
摘要