DFS 的赛通并行化争用条件

Question

我正在尝试开发一个人工智能来最佳地玩 1 人棋盘游戏。我正在使用深度优先搜索到几个级别。

我试图通过多线程化初始循环遍历所有动作并递归到游戏树中来加快速度。我的想法是，每个线程都会将初始可能的移动板拆分为块，并在单独的递归函数中进一步评估这些块。所有调用的函数都nogil

但是，我遇到了我只能猜测的竞争条件，因为多线程解决方案给出了不同的结果，我不确定如何修复它。

cdef struct Move:
int x
int y
int score
cdef Move search( board_t& board, int prevClears, int maxDepth, int depth ) nogil:
cdef Move bestMove
cdef Move recursiveMove
cdef vector[ Move ] moves = generateMoves( board )
cdef board_t nextBoard
cdef int i, clears
bestMove.score = 0
# Split the initial possible move boards amongst threads
for i in prange( <int> moves.size(), nogil = True ):
# Applies move and calculates the move score
nextBoard = applyMove( board, moves[ i ], prevClears, maxDepth, depth )
# Recursively evaluate further moves
if maxDepth - depth > 0:
clears = countClears( nextBoard )
recursiveMove = recursiveSearch( nextBoard, moves[ i ], clears, maxDepth, depth + 1 )
moves[ i ].score += recursiveMove.score
# Update bestMove
if moves[ i ].score > bestMove.score:
bestMove = moves[ i ]
return bestMove

Answer 1

Cython会做一些魔法，这取决于微妙的事情，当涉及prange时 - 所以人们真的必须查看生成的C代码才能理解发生了什么。

据我所知，您的代码至少有 2 个问题。

1. 问题：bestMove未初始化。

%%cython -+
cdef struct Move:
...
def foo()
cdef Move bestMove
return bestMove

将生成以下 C 代码：

...
struct __pyx_t_XXX_Move __pyx_v_bestMove;
...
__pyx_r = __pyx_convert__to_py_struct____pyx_t_XXX_Move(__pyx_v_bestMove); if ...
return __pyx_r;

局部变量__pyx_v_bestMove将保持未初始化状态(参见例如此 SO-post(，即使很有可能，初始值也只由零组成。

例如，如果bestMove一个int，Cython会给出警告，但它不适用于结构。

2.问题：将bestMove线索分配给赛车条件。

顺便说一句，结果可能不仅不是最好的举动，甚至可能是一个非法的举动，因为它可能是其他指定的合法举动的组合(x- 、y、score- 来自不同合法行动的值(。

这是该问题的较小重现：

%%cython -c=-fopenmp --link-args=-fopenmp
# cython
cimport cython
from cython.parallel import prange
cdef struct A:
double a
@cython.boundscheck(False)
def search_max(double[::1] vals):
cdef A max_val = [-1.0] # initialized!
cdef int i
cdef int n = len(vals)
for i in prange(n, nogil=True):
if(vals[i]>max_val.a):
max_val.a = vals[i]
return max_val.a

如果max_valcdef doubleCython就不会建造它，因为它会试图使max_val私有(微妙的魔法(。但是现在，max_val在线程之间共享(请参阅生成的 C 代码(，并且应该保护对它的访问。如果没有，我们可以看到(可能需要多次运行才能触发竞争条件(结果：

>>> import numpy as np
>>> a = np.random.rand(1000)
>>> search_max(a)-search_max(a)
#0.0006253360398751351 but should be 0.0

能做什么？正如@DavidW所建议的，我们可以收集每个线程的最大值，然后在后处理步骤中找到绝对最大值 - 请参阅此SO-post，它导致：

%%cython -+ -c=-fopenmp --link-args=-fopenmp
cimport cython
from cython.parallel import prange, threadid
from libcpp.vector cimport vector
cimport openmp
cdef struct A:
double a
@cython.boundscheck(False)
def search_max(double[::1] vals):
cdef int i, tid
cdef int n = len(vals)
cdef vector[A] max_vals
# every thread gets its own max value:
NUM_THREADS = 4
max_vals.resize(NUM_THREADS, [-1.0])
for i in prange(n, nogil=True, num_threads = NUM_THREADS):
tid = threadid()
if(vals[i]>max_vals[tid].a):
max_vals[tid].a = vals[i]
#post process, collect results of threads:
cdef double res = -1.0
for i in range(NUM_THREADS):
if max_vals[i].a>res:
res = max_vals[i].a
return res

---

我认为将 openmp 功能与 C/C++ 一起使用并使用 Cython 包装生成的代码更容易且更不容易出错：Cython 不仅不支持 openmp 提供的所有内容，而且在查看简单的 C 代码时，很难看到并行代码中的问题，而 Cython 没有任何隐含的魔法。