DFS的Cython并行竞争条件

2024-05-03 • 问答

我正在尝试开发一种AI，以最佳方式玩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,clears,depth + 1 )
         moves[ i ].score += recursiveMove.score

      # Update bestMove
      if moves[ i ].score > bestMove.score:
         bestMove = moves[ i ]

   return bestMove

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

据我所见，您的代码至少有两个问题。

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为例，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_val是cdef double的Cython不会建立它，因为它会试图将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不support everything what openmp offers，而且在以下情况下很难看到并行代码中的问题看着简单的C代码，没有Cython所做的任何隐式魔术。

DFS的Cython并行竞争条件

chaoduncan 回答：DFS的Cython并行竞争条件

大家都在问