Depth Search in CUDA / OpenCL

Question

I'm halfway through the implementation of a parallel depth search algorithm in MPI, and I'm thinking of trying to do this in CUDA / OpenCL, just for fun / out of curiosity. The algorithm is simple, but not trivial. The single-core version in C is about 200 lines of code.

How many GPGPUs are suitable for this kind of problem?

Answer 1

Tree search operations are not so easy to implement CUDA. There are several articles such as

• "Lessons Learned from Studying the Backtrace Paradigm on the GPU" http://dl.acm.org/citation.cfm?id=2033458

And one more rather simple implementation (not quite large-scale implementation in my opinion)

• "Acceleration of large graph algorithms on a GPU using CUDA" Pavan Harish and P. J. Narayanan

The difficulty arises from the fact that tree operations usually involve decision making and different branches are made in accordance with decisions. Therefore, massively parallelizing operations without overlapping and doing redundant operations is quite difficult.

There are several approaches that use the Stack and Queue implementations to move trees.

Here you can find a similar question: Error: BFS when synchronizing CUDA