Backtracking algorithm and OpenCL?

Hi guys!

I’m just starting out with OpenCL and want to know if I’ll get any performance improvement by porting over a backtracking algorithm (such as the one in a sudoku solver) to OpenCL?


OpenCL on GPU hardware is really optimized for data-parallel operation. Backtracking typically takes many many different code paths, which will perform very poorly on a GPU. Of course you still have more threads in parallel so you might win, but you won’t see anything like the gains you’d get from a data-parallel algorithm. If you can figure out how to make your backtracking algorithm data-parallel then you could get a big win.

I was thinking of starting out with OpenCL as well but how complex is it it to get that big win :slight_smile: thanks from me too for the reply its very helpful,