时间戳

首页 > 解决方案 > DFS 的 Cython 并行化竞争条件

python - DFS 的 Cython 并行化竞争条件

问题描述

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

我试图通过多线程迭代所有动作并递归到游戏树中的初始循环来加速它。我的想法是每个线程将最初可能的移动板分成块，并在单独的递归函数中进一步评估这些块。所有调用的函数都是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

标签： pythonmultithreadingrecursioncythonrace-condition

解决方案

Cython 做了一些魔术，这取决于微妙的事情，何时prange涉及 - 所以人们真的必须查看生成的 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是一个 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

如果Cython 不会构建它，因为它会尝试将其设为max_val私有（巧妙地变魔术）。但是现在，在线程之间共享（参见生成的 C 代码），并且应该保护对它的访问。如果没有，我们可以看到（可能需要多次运行才能触发竞争条件）结果：cdef doublemax_valmax_val

>>> 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 所做的任何隐式魔法。

推荐阅读