在CUDA/OpenCL中進行深度優先搜索

我在MPI中實現並行深度優先搜索算法的一半，我在考慮嘗試在CUDA/OpenCL中實現它，只是爲了好玩/出於好奇。該算法很簡單，但不是微不足道的。 C中的單核版本大約有200行代碼。在CUDA/OpenCL中進行深度優先搜索

GPGPU適合這種問題有多少？

2012-10-01 fhucho

樹搜索操作不是很容易在CUDA中實現。有一些文件，就像一個

而另一個相當簡單的實現（不是相當大規模並行執行在我看來）

困難來自這樣一個事實，即樹操作通常涉及決策制定，並根據決策採取不同的分支。因此，大規模並行操作而不重疊並進行冗餘操作是非常困難的。

有一些使用Stack和Queue實現來遍歷Trees的方法。

您可以在這裏找到一個類似的問題： Error: BFS on CUDA Synchronization

2012-10-01 10:57:46 phoad

感謝您的聯繫！ – fhucho

「困難來自這樣的事實：樹操作通常涉及決策制定，並根據決策採取不同的分支。」 @phoad - 我不能等動態並行:) –

有像「推測執行」的方法。儘管它降低了並行度，但它對於樹的生長和搜索算法可能是有益的。 – phoad

回答